diff options
Diffstat (limited to 'mcs/class/Mono.C5/doc/docbuild/userguide.htm')
| -rw-r--r-- | mcs/class/Mono.C5/doc/docbuild/userguide.htm | 2519 |
1 files changed, 0 insertions, 2519 deletions
diff --git a/mcs/class/Mono.C5/doc/docbuild/userguide.htm b/mcs/class/Mono.C5/doc/docbuild/userguide.htm deleted file mode 100644 index cea0e026e0e..00000000000 --- a/mcs/class/Mono.C5/doc/docbuild/userguide.htm +++ /dev/null @@ -1,2519 +0,0 @@ -<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
-<html>
-<head>
- <title>C5 User's Guide</title>
- <style>
-<!--
-.revvid { color: #FFFFFF; background-color: #00AA00; font-weight: bold }
--->
- </style>
-</head>
-<body>
-<h1><a class="mozTocH1" name="mozTocId905770"></a>C5 User's guide for
-prerelease version 0.5</h1>
-<h2><a class="mozTocH2" name="mozTocId507311"></a>Table of contents</h2>
-<ul class="readonly" id="mozToc">
-<!--mozToc h1 1 h2 2 h3 3 h4 4 h5 5 h6 6--><li><a href="#mozTocId905770">C5
-User's guide for prerelease version 0.5</a>
- <ul>
- <li><a href="#mozTocId507311">Table of contents</a></li>
- </ul>
- </li>
- <li><a href="#mozTocId564527">Overview</a></li>
- <li><a href="#mozTocId86956">Interfaces</a>
- <ul>
- <li><a href="#mozTocId21725">"Proper" collection interfaces</a></li>
- <li><a href="#mozTocId721827">Dictionary interfaces</a></li>
- <li><a href="#mozTocId908053">Query result interfaces</a></li>
- </ul>
- </li>
- <li><a href="#mozTocId110895">To construct a collection</a>
- <ul>
- <li><a href="#mozTocId850165">To use an external equalityComparer</a></li>
- <li><a href="#mozTocId162938">To use an external comparer</a></li>
- <li><a href="#mozTocId957374">To make collections of collections</a></li>
- </ul>
- </li>
- <li><a href="#mozTocId486186">Special topics</a>
- <ul>
- <li><a href="#mozTocId48263">To choose a set or bag collection</a></li>
- <li><a href="#mozTocId929755">To work on part of a list: list
-views</a></li>
- <li><a href="#mozTocId650306">To work with persistent red-black
-trees</a></li>
- <li><a href="#mozTocId553609">To implement new collection classes
-or subclass an existing one</a></li>
- <li><a href="#mozTocId753674">To present a read only view of a
-collection</a></li>
- </ul>
- </li>
- <li><a href="#mozTocId6619">Collection classes by data structure/class</a></li>
- <li><a href="#mozTocId393559">Planned architecture or interface
-changes for first release</a></li>
- <li><a href="#mozTocId336849">Performance details for proper
-collection classes</a></li>
- <li><a href="#mozTocId712409">Performance details for dictionary
-classes</a></li>
-</ul>
-<h1><a class="mozTocH1" name="mozTocId564527"></a>Overview<br>
-</h1>
-<p>C5 is a comprehensive library of collection classes for the <a
- href="http://www.ecma-international.org/publications/standards/Ecma-335.htm">Common
-Language Infrastructure</a> (CLI). This guide describes prerelease
-version 0.5 of C5. <br>
-</p>
-<p>C5 is a
-refactoring and extension of the <a
- href="http://www.dina.kvl.dk/%7Esestoft/gcsharp/index.html#collection">generic
-collection classes</a> developed by Peter Sestoft while visiting
-Microsoft
-Research in Cambridge.</p>
-<p> Unless stated otherwise types mentioned below will belong to the
-"C5"
-namespace; and all code examples assume a "using C5;" clause (and no
-"using System.Collection.Generics;" clause).. </p>
-<p>The goals in the development of the library has been</p>
-<ul>
- <li>
- <p class="MsoNormal"><span style="" lang="EN-US">To create a
-library of collection classes for the CLI that can assist expert and
-non-expert programmers on the platform to develop correct and efficient
-applications.</span> </p>
- </li>
- <li>
- <p class="MsoNormal"><span style="" lang="EN-US">The library should
-at least fill the gaps in the standard “System.Collections.Generics”
-namespace compared to standard collection class libraries for related
-object oriented languages like Java, and utilize the new facilities for
-generic </span><span style="" lang="EN-US">programming. Microsoft
-recently (mid 2004) seems to have changed their minds and ntend to
-bridge that gap in the beta2 version of VS 2005 due at the end of 2004.</span>
- </p>
- </li>
-</ul>
-<p>In order to fulfill the efficiency goal, the library utilizes
-first-class <a href="#datastructures">data structures</a>
-inside its collection classes. The library has been constructed with
-the modern
-object oriented programming principle of "<a href="#Interfaces">code
-to interfaces, not to implementations</a>" in mind, while the interface
-architecture has been carefully crafted to reflect the efficient data
-structures
-actually existence.</p>
-<p>A collection in the sense of this library is a plain "collection of
-items of a single type". A collection does not impose any other logical
-structure on its items than perhaps uniqueness or sequence ordering.</p>
-<p>The main division line among the collection classes of this library
-is the
-distinction between <a href="#Proper%20collection%20interfaces">"proper"
-collections</a> and <a href="#Dictionary%20interfaces">dictionaries</a>.
-A
-dictionary is a class that defines a partial function (or map) from one
-item
-type (the keys) to another one (the values). A dictionary can be viewed
-as a
-collection of (key,value) pairs having the property of defining a
-partial
-function.</p>
-<p>The item type for the collection classes are always given by generic
-parameters. For a proper collection, there will be a single parameter,
-customarily called T, as in HashSet<T>. For a dictionary there
-will be two - the key and value types -
-as in HashDictionary<K,V>.</p>
-<p>A collection class, or rather the data structure inside, can be
-either
-equality based or comparison based. An equality based collection will
-have an
-associated so-called equalityComparer of type <a href="main.htm#T:C5.IEqualityComparer%601">IEqualityComparer<T></a>,
-where T is the item type of the collection. A comparison based
-collection has an
-associated comparer of type <a href="main.htm#T:C5.IComparer%601">IComparer<T></a>.
-The section below on <a href="#Constructing">creation</a> of
-collection classes
-explains how the equalityComparers and comparers are chosen. NB: this design will
-be modified soon, cf. <a href="#planned">Planned changes</a>.<br>
-</p>
-<p>Collection classes in the library have either set or bag semantics.
-A set
-collection can at most contain one copy of an item, while bag
-collections may
-contain several. One can programmatically see at runtime if an editable
-collection class has set or bag semantics by checking the <a
- href="main.htm#P:C5.IExtensible%601.AllowsDuplicates">
-AllowsDuplicates</a>
-property. At compile time, refer to the <a href="#set%20or%20bag">set
-or bag table</a>
-below for an overview. <br>
-</p>
-<h1><a class="mozTocH1" name="mozTocId86956"></a><a name="Interfaces">Interfaces</a></h1>
-<p>The C5 library is designed to make it easy to program to interfaces
-instead
-of implementations. In particular, all public properties and methods of
-the
-collection classes belong to their implemented interfaces (except for
-the odd
-special diagnostic method and the odd mistake to be weeded out before
-release). The typical programming style
-would be</p>
-<blockquote>
- <p><code>IList<int> lst = new LinkedList<int>();<br>
-lst.Add(7);</code></p>
-</blockquote>
-<p>instead of </p>
-<blockquote>
- <p><code> LinkedList<int> lst = new LinkedList<int>();<br>
-lst.Add(7);</code></p>
-</blockquote>
-<p>Note that with this programming style, the Add call will be compiled
-to an
-interface call instead of a (virtual) method call, but interface calls
-on the
-CLR (at least the Microsoft implementation) are at most very slightly
-slower
-than virtual calls, so one should not shun the interface style for
-performance
-reasons.</p>
-<p>We will discuss the collection classes available in C5 structured
-according
-to the main functional interfaces of the <a
- href="#Proper%20collection%20interfaces">proper
-collections</a>, the <a href="#Dictionary%20interfaces">dictionaries</a>
-and the
-interfaces of <a href="#Query%20result%20interfaces">query results</a>.</p>
-<h2><a class="mozTocH2" name="mozTocId21725"></a><a
- name="Proper collection interfaces">"Proper" collection interfaces</a></h2>
-<p>The following diagam shows the type hierarchy of the proper
-collection classes:</p>
-<p><img alt="Interface hierarchy" src="ClsdiagWork.png"
- style="width: 757px; height: 498px;"><br>
-The most important interfaces - those that are directly
-implemented by
-collection classes - are listed to the left in this table with a short
-description in the middle and all implementing classes to the
-right. </p>
-<p>Please see also the <a href="#PerformanceProper">complete
-complexity table</a>
-for more comprehensive guidance.</p>
-<p>To identify which classes are equalityComparer or comparer based and which
-classes
-implement set or bag we use the following symbols:</p>
-<table border="1" width="471">
- <tbody>
- <tr>
- <td width="116">set: <code class="revvid">S</code> </td>
- <td width="117"> bag: <code class="revvid">B</code> </td>
- <td width="117"> equalityComparer: <code class="revvid">H</code> </td>
- <td width="117"> comparer: <code class="revvid">C</code> </td>
- </tr>
- </tbody>
-</table>
-<table border="1" width="100%">
- <tbody>
- <tr>
- <th width="19%">Interface</th>
- <th width="52%">Short description</th>
- <th width="29%">Implementing classes</th>
- </tr>
- <tr>
- <td valign="top" width="19%"><a
- href="main.htm#T:C5.ICollection%601">ICollection<T></a> </td>
- <td valign="top" width="52%">This is the fundamental type
-of updateable collections. It has operations for searching for
-items, for adding, updating and removing one or a bunch of items, for
-clearing the collection and transforming the collection to an
-array.
- <p>If one only needs these operations, the hash set and hash bag
-classes are fastest for if we have a equalityComparer for the items and the
-red-black tree classes are fastest if we must use a comparer.</p>
- </td>
- <td valign="top" width="29%"><code class="revvid">SH</code> <a
- href="main.htm#T:C5.HashSet%601">HashSet<T></a><br>
- <code class="revvid">BH</code> <a
- href="main.htm#T:C5.HashBag%601">HashBag<T></a><br>
- <code class="revvid">BH</code> <a
- href="main.htm#T:C5.LinkedList%601">LinkedList<T></a><br>
- <code class="revvid">SH</code> <a
- href="main.htm#T:C5.HashedLinkedList%601">HashedLinkedList<T></a><br>
- <code class="revvid">BH</code> <a
- href="main.htm#T:C5.ArrayList%601">ArrayList<T></a><br>
- <code class="revvid">SH</code> <a
- href="main.htm#T:C5.HashedArrayList%601"> HashedArrayList<T><br>
- </a> <code class="revvid">SC</code> <a
- href="main.htm#T:C5.SortedArray%601"> SortedArray<T></a><br>
- <code class="revvid">SC</code> <a
- href="main.htm#T:C5.TreeSet%601"> TreeSet<T></a><br>
- <code class="revvid">BC</code> <a
- href="main.htm#T:C5.TreeBag%601"> TreeBag<T></a></td>
- </tr>
- <tr>
- <td valign="top" width="19%"><a
- href="main.htm#T:C5.IPriorityQueue%601">IPriorityQueue<T></a> </td>
- <td valign="top" width="52%">This is a special case in the
-library, being the only type of updateable collection interface that
-does not implement IEditableCollection<T>. The reason for its
-presence is the specialized "heap" data structures for priority queues
-that only support these operations.
- <p>If one only needs these the priority queue operations and is
-satisfied with bag semantics, then IntervalHeap<P> is the
-fastest choice. </p>
- </td>
- <td valign="top" width="29%"> <code class="revvid">BC</code> <a
- href="main.htm#T:C5.IntervalHeap%601">IntervalHeap<T></a><br>
- <code class="revvid">SC</code> <a
- href="main.htm#T:C5.TreeSet%601"> TreeSet<T></a><br>
- <code class="revvid">BC</code> <a
- href="main.htm#T:C5.TreeBag%601"> TreeBag<T></a></td>
- </tr>
- <tr>
- <td valign="top" width="19%"><a href="main.htm#T:C5.IList%601">IList<T></a> </td>
- <td valign="top" width="52%">This is an updateable collection
-with sequence order imposed on the items by the user at insertion time
-or by later rearrangements.
- <p>There are two main base data structures: dynamic arrays and
-doubly linked lists with very different complexity profile. The
-plain linked list is fast for operations at the end points only, while
-the plain array list have very fast lookups by index, but update
-operations are only fast at the right end point. </p>
- <p>The Hashed- variants employ an index based on a hash table.
-This speeds up lookups by item considerably and for the linked list
-variant also insertions before or after specific items. The index
-changes the classes from bags to sets. </p>
- <p>The hashed variants more than double the time of otherwise
-fast update operations, and should only be used when really
-needed. </p>
- </td>
- <td valign="top" width="29%"> <code class="revvid">BH</code> <a
- href="main.htm#T:C5.LinkedList%601"> LinkedList<T></a><br>
- <code class="revvid">SH</code> <a
- href="main.htm#T:C5.HashedLinkedList%601"> HashedLinkedList<T></a><br>
- <code class="revvid">BH</code> <a
- href="main.htm#T:C5.ArrayList%601"> ArrayList<T></a><br>
- <code class="revvid">SH</code> <a
- href="main.htm#T:C5.HashedArrayList%601"> HashedArrayList<T></a></td>
- </tr>
- <tr>
- <td valign="top" width="19%"><a
- href="main.htm#T:C5.IIndexedSorted%601">IIndexedSorted<T></a> </td>
- <td valign="top" width="52%">This is an updateable collection
-with sequence order given by a comparer.
- <p>There are two main data structures inside the implementations:
-red-black search trees and a dynamic array kept sorted at all times.</p>
- <p>The differences are chiefly that the trees have much faster
-update operations, while the sorted array is somewhat faster at index
-lookups. In fact, the sorted array should only be used for static
-operation, where the collection is created and populated and then not
-changed again. </p>
- </td>
- <td valign="top" width="29%"> <code class="revvid">SC</code> <a
- href="main.htm#T:C5.SortedArray%601"> SortedArray<T></a><br>
- <code class="revvid">SC</code> <a
- href="main.htm#T:C5.TreeSet%601"> TreeSet<T></a><br>
- <code class="revvid">BC</code> <a
- href="main.htm#T:C5.TreeBag%601"> TreeBag<T></a></td>
- </tr>
- <tr>
- <td valign="top" width="19%"><a
- href="main.htm#T:C5.IPersistentSorted%601">IPersistentSorted<T></a> </td>
- <td valign="top" width="52%">This is a sorted collection that
-support very fast clones that themselves are sorted. The only
-implementation is the tree implementation with set and bag variants. </td>
- <td valign="top" width="29%"> <code class="revvid">SC</code> <a
- href="main.htm#T:C5.TreeSet%601"> TreeSet<T></a><br>
- <code class="revvid">BC</code> <a
- href="main.htm#T:C5.TreeBag%601"> TreeBag<T></a></td>
- </tr>
- </tbody>
-</table>
-<h2><a class="mozTocH2" name="mozTocId721827"></a><a
- name="Dictionary interfaces">Dictionary interfaces</a></h2>
-<p>There are two dictionary interfaces:</p>
-<table border="1" width="100%">
- <tbody>
- <tr>
- <th valign="top" width="19%">Interface</th>
- <th width="56%">Short description</th>
- <th width="25%">Implementing classes</th>
- </tr>
- <tr>
- <td valign="top" width="19%"><a
- href="main.htm#T:C5.IDictionary%602">IDictionary<K,V></a> </td>
- <td width="56%">This is the base dictionary interface.
- <p>The choice is that one should use the hash dictionary unless
-one only has a comparer for the items, in which case the tree
-dictionary can be used. </p>
- </td>
- <td width="25%"><a href="main.htm#T:C5.HashDictionary%602">HashDictionary<K,V></a><br>
- <a href="main.htm#T:C5.TreeDictionary%602">TreeDictionary<K,V></a></td>
- </tr>
- <tr>
- <td valign="top" width="19%"><a
- href="main.htm#T:C5.ISortedDictionary%602">ISortedDictionary<K,V></a>
- </td>
- <td width="56%">This is a dictionary based on a comparer for the
-keys. There is only the tree implementation. </td>
- <td width="25%"><a href="main.htm#T:C5.TreeDictionary%602">TreeDictionary<K,V></a></td>
- </tr>
- </tbody>
-</table>
-<h2><a class="mozTocH2" name="mozTocId908053"></a><a
- name="Query result interfaces">Query result interfaces</a></h2>
-<p>Some of the most basic collection interfaces have an important usage
-as the
-types of results of queries to collections, although these interfaces
-also
-appear at the base of the other collection interfaces and even as the
-types of
-synthetic collections. The interfaces in question are the standard
-System.Collections.Generics.IEnumerable<T>,
-<a href="main.htm#T:C5.ICollectionValue%601">ICollectionValue<T></a>,
-<a href="main.htm#T:C5.IDirectedEnumerable%601">IDirectedEnumerable<T></a>
-and <a href="main.htm#T:C5.IDirectedCollectionValue%601">IDirectedCollectionValue<T></a>.</p>
-<p>The differences between the "Enumerable" and "Collection"
-variants are that the "Enumerable" variant only knows how to
-enumerate through its items, the "Collection" variants also knows how
-many items it has (without having to walk through an enumeration). The
-"Directed" variants are used for results of queries to sequenced
-collections (implementing <a href="main.htm#T:C5.ISequenced%601">ISequenced<T></a>)
-and therefore have a non-implementation dependent enumeration order.
-The
-"Directed" variants supports two operations, <a
- href="main.htm#M:C5.IDirectedCollectionValue%601.Backwards">Backwards()</a>
-to enable enumeration in the opposite direction and <a
- href="main.htm#P:C5.IDirectedEnumerable%601.Direction">Direction</a>
-to tell if the enumeration order is forwards or backwards with respect
-to the
-original collection.</p>
-<p>Note: operations on an enumerator created by the GetEnumerator()
-method on System.Collections.Generics.IEnumerable<T> cannot be
-interleaved with update
-operations on
-the underlying collection.</p>
-<p>Note: for all enumerators in the library the operations have O(1)
-amortized
-complexity.</p>
-<h1><a class="mozTocH1" name="mozTocId110895"></a>To <a
- name="Constructing">construct</a> a collection</h1>
-<p>All collections classes in C5 have (zero parameter) default
-constructors. So
-if we want to make a linked list of items of some type, <code>TheType</code>,
-and add an item to the list we will do</p>
-<p><code> IList<TheType> lst = new
-LinkedList<TheType>();<br>
- TheType t = ...;<br>
- lst.Add(t);</code></p>
-<p>The collection classes have no constructors that will take an array
-or a
-collection as parameter for prepopulating the collection, use the <a
- href="file:///C:/home/kokholm/c5/vs/C5/main.htm#M:C5.ISink%601.AddAll%28C5.IEnumerable%7B%210%7D%29">
-AddAll</a> method
-instead. NB: in the released version, expect constructors with an
-enumerable as argument and constructors with a variable number of
-arguments ("params") for the initialization of the collection, see the <a
- href="#planned">planned changes</a> section.<br>
-</p>
-<p>Some collection classes are governed by internal parameters that one
-can give
-non-default values at creation time (<code>fill</code> in <a
- href="main.htm#T:C5.HashSet%601">HashSet<T></a>,
-<a href="main.htm#T:C5.HashBag%601">HashBag<T></a>, <a
- href="main.htm#T:C5.HashDictionary%602">HashDictionary<K,V></a>)
-or use internal tables that one can expand in advance if one has
-expectations of
-how large the collection will grow (HashSet<T>,
-HashBag<T>, HashDictionary<K,V>, <a
- href="main.htm#T:C5.ArrayList%601">ArrayList<T></a>,
-<a href="main.htm#T:C5.HashedArrayList%601"> HashedArrayList<T></a>,
-<a href="main.htm#T:C5.SortedArray%601">SortedArray<T></a>,
-<a href="main.htm#T:C5.IntervalHeap%601">IntervalHeap<T></a>).</p>
-<p>For equality-based collection classes, these constructors will use a
-default
-equalityComparer to define equality of items according to the following table:</p>
-<table border="1">
- <tbody>
- <tr>
- <th>T</th>
- <th>default equalityComparer (implements IEqualityComparer<T>)</th>
- <th>Equality and hash code by</th>
- </tr>
- <tr>
- <td>int</td>
- <td><a href="main.htm#T:C5.IntEqualityComparer">IntEqualityComparer</a></td>
- <td>Equals and hash code of integer</td>
- </tr>
- <tr>
- <td>other value type</td>
- <td><a href="main.htm#T:C5.DefaultValueTypeEqualityComparer%601">DefaultValueTypeEqualityComparer<T></a></td>
- <td>methods inherited from object</td>
- </tr>
- <tr>
- <td>IEditableCollection<S></td>
- <td><a href="main.htm#T:C5.EqualityComparerBuilder.UnsequencedEqualityComparer%602">EqualityComparerBuilder.UnsequencedEqualityComparer<S,IEditableCollection<S>></a></td>
- <td>contents without regards to sequence</td>
- </tr>
- <tr>
- <td>ISequenced<S></td>
- <td><a href="main.htm#T:C5.EqualityComparerBuilder.SequencedEqualityComparer%602">EqualityComparerBuilder.SequencedEqualityComparer<S,IEditableCollection<S>></a></td>
- <td>contents with regards to sequence</td>
- </tr>
- <tr>
- <td>other reference type</td>
- <td><a href="main.htm#T:C5.DefaultReferenceTypeEqualityComparer%601">DefaultReferenceTypeEqualityComparer<T></a></td>
- <td>methods inherited from object</td>
- </tr>
- </tbody>
-</table>
-<p>For comparison-based collection classes, these constructors will use
-a
-default comparer:</p>
-<table border="1">
- <tbody>
- <tr>
- <th>T</th>
- <th>default comparer <br>
-(implements IComparer<T>)</th>
- <th>Comparison by</th>
- </tr>
- <tr>
- <td>int</td>
- <td>IC</td>
- <td>Standard integer comparison</td>
- </tr>
- <tr>
- <td>implementing IComparable<T></td>
- <td><a href="main.htm#T:C5.NaturalComparer%601">NaturalComparer<T></a></td>
- <td>The CompareTo(T o) instance method</td>
- </tr>
- <tr>
- <td>other implementing System.IComparable</td>
- <td><a href="main.htm#T:C5.NaturalComparerO%601">NaturalComparerO<T></a></td>
- <td>The CompareTo(object o) instance method</td>
- </tr>
- <tr>
- <td>other</td>
- <td>-</td>
- <td><i>collection class constructor throws an exception</i></td>
- </tr>
- </tbody>
-</table>
-<p>Sometimes, the default equalityComparer or comparer is not the right one for
-the
-problem at hand. In that case one must get hold on a equalityComparer or comparer
-of the
-right kind and supply it to one of the constructors of the collection
-classes
-that supports such a parameter. The procedure is demonstrated in the
-sections
-below on <a href="#external%20equalityComparer">external equalityComparers</a>, <a
- href="#external%20comparer">external
-comparers</a> and <a href="#collections%20of%20collections">collections
-as items</a>.<br>
-</p>
-<p>NB: in the released version, expect the equalityComparers and comparers to be
-of the System.Collections.Generics.IComparer<T> type, see the <a
- href="userguide.htm#planned">planned changes</a> section.</p>
-<h2><a class="mozTocH2" name="mozTocId850165"></a>To use an <a
- name="external equalityComparer"> external equalityComparer</a></h2>
-<p>In addition to the helper classes referenced above, the library has
-the
-helper class <a href="main.htm#T:C5.KeyValuePairEqualityComparer%602">KeyValuePairEqualityComparer<K,V></a>
-to construct a equalityComparer for pairs of the type <a
- href="main.htm#T:C5.KeyValuePair%602">KeyValuePair<K,V></a>,
-the type of entry of a K to V dictionary. The constructed equalityComparer will
-only take
-the first component of the pair into account. We can use these classes
-in the
-following way to make a linked list (with hash index) of pairs of
-strings
-identified by their first components using some custom equalityComparer on
-strings:</p>
-<blockquote>
- <p><code>IEqualityComparer<string> csh = ...;<br>
-IEqualityComparer<KeyValuePair<string,string>> cph = <br>
-
-new KeyValuePairEqualityComparer<string,string>(csh);<br>
-IList<KeyValuePair<string,string>> lst =<br>
- </code> <code>
-new HashedLinkedList<KeyValuePair<string,string>>(cph);<br>
-lst.Add(new KeyValuePair<string,string>("abe","kat"));</code></p>
-</blockquote>
-<p>One may, of course, program a equalityComparer oneself. This one should always
-do if
-the item type is defined as a struct (value type) that does not
-override the
-Equals and GetHashCode methods of object, since in that case the
-default equalityComparer
-will use the slow default versions of those methods supplied by the
-runtime via
-reflection. </p>
-<h2><a class="mozTocH2" name="mozTocId162938"></a>To use an <a
- name="external comparer"> external comparer</a></h2>
-<p>There is a helper class for comparer of pairs: <a
- href="main.htm#T:C5.KeyValuePairEqualityComparer%602">KeyValuePairComparer<K,V></a>.
-We will show an example of a custom comparer. Imagine wanting to
-compare double
-precision floating point numbers with a tolerance. The following code
-snippet
-shows how one could make a tree set out of such numbers:</p>
-<blockquote>
- <p><code>class DC : IComparer<double> {<br>
- const double eps = 1E-10;<br>
- int Compare(double a, double b) <br>
- {return a > b + eps ? 1 : a < b -
-eps ? -1 : 0;}<br>
-}<br>
- <br>
-void dowork() {<br>
- IComparer<double> dc = new DC();<br>
- ISorted<double> tree = new TreeSet<double>(dc);<br>
- tree.Add(3.45);<br>
- ...<br>
-}</code></p>
-</blockquote>
-<p>In this particular case, one would have to make sure, that two
-different
-floating point numbers are only identified by the comparer if they
-really should
-represent the same value and not by coincidence.</p>
-<h2><a class="mozTocH2" name="mozTocId957374"></a>To make <a
- name="collections of collections"> collections of collections</a></h2>
-<p>When one wants to use a collection whose items itself are of
-collection type,
-one usually wants the interior collections to be identified by contents
-- either
-according to or irrespective of sequence order. An example could be
-transformations of <a
- href="http://www.dina.kvl.dk/%7Esestoft/gcsharp/index.html#regexp">Finite
-Automatons</a>. The default equalityComparers and the EqualityComparerBuilder classes
-mentioned
-above may help to construct such collections of collections as in the
-examples
-that follow:</p>
-<p>To make an array list of sequenced collections identified by
-contents in
-sequenced fashion one would simply do:</p>
-<blockquote>
- <p><code>ArrayList<ISequenced<int>> lst = new
-ArrayList<ISequenced<int>>();</code></p>
-</blockquote>
-<p>To make a linked list of linked lists identified by contents
-unsequenced, explicitly
-construct the collection equalityComparer:</p>
-<blockquote>
- <p><code>IEqualityComparer<LinkedList<int>> lsth =<br>
- </code> <code>new
-EqualityComparerBuilder.UnsequencedEqualityComparer<int,LinkedList<int>>();<br>
-LinkedList<LinkedList<int>> lst =<br>
- new LinkedList<LinkedList<int>>(lsth);</code></p>
-</blockquote>
-<p>If for some strange reason one would like to make a hash set of
-linked lists
-with the lists identified by reference equality one would simply do:</p>
-<blockquote>
- <p><code>HashSet<LinkedList<int>> lst = new
-HashSet<LinkedList<int>>();</code></p>
-</blockquote>
-<p>If for even stranger reasons one would make a hash set of
-ISequenced<int> collections with the collections identified by
-reference
-equality one would do like this:</p>
-<blockquote>
- <p><code>IEqualityComparer<</code><code>ISequenced</code><code><int>>
-lsth =<br>
- </code> <code>new
-DefaultReferenceTypeEqualityComparer<</code><code>ISequenced</code><code><int>>();<br>
-HashSet<</code><code>ISequenced</code><code><int>> lst =<br>
- new HashSet<</code><code>ISequenced</code><code><int>>(lsth);</code></p>
-</blockquote>
-<h1><a class="mozTocH1" name="mozTocId486186"></a>Special topics</h1>
-<h2><a class="mozTocH2" name="mozTocId48263"></a>To choose a <a
- name="set or bag"> set or bag</a> collection</h2>
-<p>The following table shows which of the collection classes have set
-semantics
-and which have bag semantics. All the implemented classes have fixed,
-compiled in semantics. <br>
-</p>
-<p>Note: when in a set collection, methods with an Add in the name will
-ignore
-attempts to add an item already there or flag the failed attempt by a
-Boolean return value; methods with an Insert in the name (only in
-lists) will throw an
-exception.</p>
-<table border="1" width="38%">
- <tbody>
- <tr>
- <td valign="top" width="6%"><a href="main.htm#T:C5.HashSet%601">HashSet<T></a></td>
- <td valign="top" width="5%">set</td>
- </tr>
- <tr>
- <td valign="top" width="6%"> <a href="main.htm#T:C5.HashBag%601">HashBag<T></a></td>
- <td valign="top" width="5%">bag</td>
- </tr>
- <tr>
- <td valign="top" width="6%"> <a
- href="main.htm#T:C5.LinkedList%601"> LinkedList<T></a></td>
- <td valign="top" width="5%">bag</td>
- </tr>
- <tr>
- <td valign="top" width="6%"> <a
- href="main.htm#T:C5.HashedLinkedList%601"> HashedLinkedList<T></a></td>
- <td valign="top" width="5%">set</td>
- </tr>
- <tr>
- <td valign="top" width="6%"> <a
- href="main.htm#T:C5.ArrayList%601"> ArrayList<T></a></td>
- <td valign="top" width="5%">bag</td>
- </tr>
- <tr>
- <td valign="top" width="6%"> <a
- href="main.htm#T:C5.HashedArrayList%601"> HashedArrayList<T> </a>
- </td>
- <td valign="top" width="5%">set</td>
- </tr>
- <tr>
- <td valign="top" width="6%"> <a
- href="main.htm#T:C5.SortedArray%601"> SortedArray<T></a></td>
- <td valign="top" width="5%">set</td>
- </tr>
- <tr>
- <td valign="top" width="6%"> <a href="main.htm#T:C5.TreeSet%601">TreeSet<T></a></td>
- <td valign="top" width="5%">set</td>
- </tr>
- <tr>
- <td valign="top" width="6%"> <a href="main.htm#T:C5.TreeBag%601">TreeBag<T></a></td>
- <td valign="top" width="5%">bag</td>
- </tr>
- <tr>
- <td valign="top" width="6%"><a
- href="main.htm#T:C5.IntervalHeap%601">IntervalHeap<T></a></td>
- <td valign="top" width="5%">bag</td>
- </tr>
- </tbody>
-</table>
-<h2><a class="mozTocH2" name="mozTocId929755"></a>To work on part of a
-list: list views</h2>
-<p>The IList<T> interface supports via the <a
- href="main.htm#M:C5.IList%601.View%28System.Int32,System.Int32%29">
-View</a>
-method the functionality that one can zoom in on part of a list and use
-it as an
-IList<T> in its own right while having updates to the view passed
-through
-to the base (original) IList<T>. Using the <a
- href="main.htm#M:C5.IList%601.Slide%28System.Int32%29">Slide</a>
-method calls, one may move the view around the base list. Using Slide
-repeatedly
-one can implement safe ways to iterate over a list while updating it.
-The
-IList<T> interface also has properties <a
- href="main.htm#P:C5.IList%601.Underlying">Underlying</a>
-and <a href="main.htm#P:C5.IList%601.Offset">Offset</a> showing the
-base list of a
-view and the current site of a view.</p>
-<p>One can create a view on a view, but the new view will have the
-original base
-list as base. A view will be invalidated if an update operation is
-performed on
-the base list by any other means than through this particular view.</p>
-<p>The following code snippet shows a silly example of iterating over a
-list,
-doing an insertion each time certain combination of items are seen (the
-example
-iterates right to left and inserts 666 whenever two consecutive items
-have an
-odd difference):</p>
-<blockquote>
- <p><code>IList<int> lst = ...;<br>
-IList<int> view = lst.CreateView(lst.Count-2, 2);<br>
-while (true) {<br>
- if ((view.Last - view.First) % 2 == 1)<br>
- view.Insert(1, 666);<br>
- if (view.Offset == 0)<br>
- break;<br>
- else<br>
- view.Slide(-1,2);<br>
-}</code></p>
-</blockquote>
-<h2><a class="mozTocH2" name="mozTocId650306"></a>To work with
-persistent red-black trees</h2>
-<p>The search tree implementation in the library is based on node copy
-persistent red-black trees. The persistence is exposed in the <a
- href="main.htm#M:C5.IPersistentSorted%601.Snapshot">Snapshot</a>
-method that can be considered a very fast and space-saving way of
-making a
-read-only clone of the tree. When using persistence, the space use of a
-red-black tree in this implementation is linear in the number of
-operations
-since the creation of the tree.</p>
-<p>One use of persistence could be to safely enumerate a tree
-interleaved with
-updates:</p>
-<blockquote>
- <p><code>IPersistentSorted<int> tree = new TreeSet<int>();<br>
-tree.Add(5);<br>
-...<br>
-ISorted<int> snap = tree.Snapshot();<br>
-foreach (int i in snap)<br>
- tree.Add(i+7);</code></p>
-</blockquote>
-<p>The GUITester project of the complete library source code contains
-an
-interesting (standard) usage of persistent search trees to the
-geometric problem
-of constructing an efficient data structure for point location in a
-division of
-the plane given by a list of line segments.</p>
-<h2><a class="mozTocH2" name="mozTocId553609"></a>To implement new
-collection classes or subclass an existing one</h2>
-<p>All interface methods and properties of the collection classes
-implemented in
-the library are virtual and so it should be safe to subclass these
-classes. Some
-classes may have protected members if they are subclassed in the
-library itself.
-We refer to the detailed reference manuals and the library source for
-information on the protected members and their role in subclassing.</p>
-<p>There is a sequence of helper classes designed to be used as base
-classes of
-collection classes: <a href="main.htm#T:C5.EnumerableBase%601">EnumerableBase<T></a>,
-<a href="main.htm#T:C5.CollectionValueBase%601">CollectionValueBase<T></a>,
-<a href="main.htm#T:C5.CollectionBase%601">CollectionBase<T></a>,
-<a href="main.htm#T:C5.SequencedBase%601">SequencedBase<T></a>
-and <a href="main.htm#T:C5.ArrayBase%601">ArrayBase<T></a>.
-Please see the reference manual and the library source code for
-documentation
-and examples.</p>
-<p>As for dictionaries, the DictionaryBase<K,V> class will
-construct a
-class implementing IDictionary<K,V> by simply plugging in a set
-implementation.</p>
-<h2><a class="mozTocH2" name="mozTocId753674"></a>To present a read
-only view of a collection</h2>
-<p>The library contains a long list of wrapper classes all with name
-starting
-with Guarded having the purpose of creating a read-only view of an
-existing
-collection. The wrapping is done by the constructors of the classes. If
-we want
-to give some code access to only lookup operations on a, say, list we
-can do as
-follows:</p>
-<blockquote>
- <p><code>IList<int> lst;<br>
-...<br>
-IList<int> rolst = new GList<int>(lst);<br>
-OtherObject.dowork(rolst);</code></p>
-</blockquote>
-<p>Please see the reference manual for details on available wrapper
-classes.</p>
-<h1><a class="mozTocH1" name="mozTocId6619"></a><a name="datastructures">Collection
-classes by data structure/class</a></h1>
-<p>The following table shows the underlying data structure of the
-various collection classes.</p>
-<table border="1">
- <tbody>
- <tr>
- <th>Data structure</th>
- <th>Classes</th>
- <th>Primary Interfaces</th>
- </tr>
- <tr>
- <td>hash table</td>
- <td>HashSet<T></td>
- <td> ICollection<T></td>
- </tr>
- <tr>
- <td>hash table</td>
- <td>HashBag<T></td>
- <td> ICollection<T></td>
- </tr>
- <tr>
- <td>hash table</td>
- <td>HashDictionary<K,V></td>
- <td>IDictionary<K,V></td>
- </tr>
- <tr>
- <td>linked list</td>
- <td>LinkedList<T></td>
- <td>IList<T></td>
- </tr>
- <tr>
- <td>linked list with hash index</td>
- <td>HashedLinkedList<T></td>
- <td>IList<T></td>
- </tr>
- <tr>
- <td>dynamic array</td>
- <td>ArrayList<T></td>
- <td>IList<T></td>
- </tr>
- <tr>
- <td>dynamic array with hash index</td>
- <td>HashedArrayList<T></td>
- <td>IList<T></td>
- </tr>
- <tr>
- <td>sorted dynamic array</td>
- <td>SortedArray<T></td>
- <td>IIndexedSorted<T></td>
- </tr>
- <tr>
- <td>heap</td>
- <td>IntervalHeap<T></td>
- <td>IPriorityQueue<T></td>
- </tr>
- <tr>
- <td>red-black search tree</td>
- <td>TreeSet<T></td>
- <td>IIndexedSorted<T>, IPersistentSorted<T></td>
- </tr>
- <tr>
- <td>red-black search tree</td>
- <td>TreeBag<T></td>
- <td>IIndexedSorted<T>, IPersistentSorted<T></td>
- </tr>
- <tr>
- <td>red-black search tree</td>
- <td>TreeDictionary<K,V></td>
- <td>ISortedDictionary<K,V></td>
- </tr>
- </tbody>
-</table>
-<br>
-<h1><a class="mozTocH1" name="mozTocId393559"></a><><a
- name="planned"></a>Planned<span style="font-weight: bold;"> </span>architecture
-or interface changes
-for first release<br>
-</h1>
-<ol>
- <li>Eliminate the use of our own generic equality/comparator types,
-C5.IComparer<T> and C5.IEqualityComparer<T> and use the new design of
-VS 2005 beta1 in the form of the combined
-System.Collections.Generic.IComparer<T>.</li>
- <li>Vararg (params) constructors? (And IEnum do.)</li>
- <li>Possibly extended use of "wildcard style" operations like
-AddAll<U>(IEnumerable<U> items)?</li>
- <li>Make all collection classes clonable and serializable.</li>
-</ol>
-<h1><a class="mozTocH1" name="mozTocId336849"></a><a
- name="PerformanceProper">Performance</a> details for proper collection
-classes</h1>
-<p>This section overviews the complexities of cc public methods and
-property
-accesses.</p>
-<p>In the table below, for lack of space we use the following numbers
-to
-identify collection classes:</p>
-<table border="1">
- <tbody>
- <tr>
- <th>Class</th>
- <th>Column</th>
- </tr>
- <tr>
- <td>HashSet<T></td>
- <td>HS</td>
- </tr>
- <tr>
- <td>HashBag<T></td>
- <td>HB</td>
- </tr>
- <tr>
- <td>ArrayList<T></td>
- <td>AL</td>
- </tr>
- <tr>
- <td>LinkedList<T></td>
- <td>LL</td>
- </tr>
- <tr>
- <td>HashedArrayList<T></td>
- <td>HAL</td>
- </tr>
- <tr>
- <td>HashedLinkedList<T></td>
- <td>HLL</td>
- </tr>
- <tr>
- <td>TreeSet<T></td>
- <td>RBTS</td>
- </tr>
- <tr>
- <td>TreeBag<T></td>
- <td>RBTB</td>
- </tr>
- <tr>
- <td>SortedArray<T></td>
- <td>SA</td>
- </tr>
- <tr>
- <td>IntervalHeap<T></td>
- <td>IH</td>
- </tr>
- </tbody>
-</table>
-<p>And the following special symbols: </p>
-<p>
-n size of collection, <br>
-m size of argument if collection-: not supported<br>
-*: means: suboptimal complexity (library is in error)<br>
-$: special at end: the operation is much faster at the start and/or end
-(end for
-array list, both for linked list)
-</p>
-<p>Note: we do not show return type or parameters for methods,
-just mark
-with ()<br>
-Note: we ignore time for reclaiming of internal array space (e.g. Clear)<br>
-User supplied operations like comparers or equalityComparers are assumed to be
-O(1)</p>
-<table border="1" height="2893" width="100%">
- <tbody>
- <tr>
- <th height="23" width="9%">Member</th>
- <th height="23" width="8%">HS</th>
- <th height="23" width="8%">HB</th>
- <th height="23" width="8%">AL</th>
- <th height="23" width="8%">LL</th>
- <th height="23" width="8%">HAL</th>
- <th height="23" width="8%">HLL</th>
- <th height="23" width="8%">RBTS</th>
- <th height="23" width="8%">RBTB</th>
- <th height="23" width="9%">SA</th>
- <th height="23" width="9%">IH</th>
- </tr>
- <tr>
- <td height="22" width="14%"><i><font color="#808080" size="2"> IEnumerable<T></font></i></td>
- <td height="22" width="8%"> </td>
- <td height="22" width="8%"> </td>
- <td height="22" width="8%"> </td>
- <td height="22" width="8%"> </td>
- <td height="22" width="8%"> </td>
- <td height="22" width="8%"> </td>
- <td height="22" width="8%"> </td>
- <td height="22" width="8%"> </td>
- <td height="22" width="9%"> </td>
- <td height="22" width="9%"> </td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">GetEnumerator()</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="9%"><font size="2">O(1)</font></td>
- <td height="22" width="9%"><font size="2">O(1)</font></td>
- </tr>
- <tr>
- <td height="22" width="14%"><i><font color="#808080" size="2">IDirectedEnumerable<T></font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">HB</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">AL</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">LL</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">HAL</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">HLL</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">RBTS</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">RBTB</font></i></td>
- <td align="center" height="22" width="9%"><i><font color="#808080"
- size="2">SA</font></i></td>
- <td align="center" height="22" width="9%"><i><font color="#808080"
- size="2">IH</font></i></td>
- </tr>
- <tr>
- <td height="22" width="18%"><font size="2">Direction</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="9%"><font size="2">O(1)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="18%"><font size="2">Backwards()</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="9%"><font size="2">O(1)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="14%"><i><font color="#808080" size="2">ICollectionValue<T></font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">HB</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">AL</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">LL</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">HAL</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">HLL</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">RBTS</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">RBTB</font></i></td>
- <td align="center" height="22" width="9%"><i><font color="#808080"
- size="2">SA</font></i></td>
- <td align="center" height="22" width="9%"><i><font color="#808080"
- size="2">IH</font></i></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">Count</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="9%"><font size="2">O(1)</font></td>
- <td height="22" width="9%"><font size="2">O(1)</font></td>
- </tr>
- <tr>
- <td height="22" width="18%"><font size="2">CopyTo</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="9%"><font size="2">O(n)</font></td>
- <td height="22" width="9%"><font size="2">O(n)</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">ToArray</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="9%"><font size="2">O(n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">Apply()</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="9%"><font size="2">O(n)</font></td>
- <td height="22" width="9%"><font size="2">O(n)</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">Exists()</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="9%"><font size="2">O(n)</font></td>
- <td height="22" width="9%"><font size="2">O(n)</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">All()</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="9%"><font size="2">O(n)</font></td>
- <td height="22" width="9%"><font size="2">O(n)</font></td>
- </tr>
- <tr>
- <td height="22" width="14%"><i><font color="#808080" size="2">IDirectedCollectionValue<T></font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">HB</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">AL</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">LL</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">HAL</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">HLL</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">RBTS</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">RBTB</font></i></td>
- <td align="center" height="22" width="9%"><i><font color="#808080"
- size="2">SA</font></i></td>
- <td align="center" height="22" width="9%"><i><font color="#808080"
- size="2">IH</font></i></td>
- </tr>
- <tr>
- <td height="22" width="18%"><font size="2">Backwards()</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="9%"><font size="2">O(1)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="13%"><i><font color="#808080" size="2">IExtensible<T></font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">HB</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">AL</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">LL</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">HAL</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">HLL</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">RBTS</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">RBTB</font></i></td>
- <td align="center" height="22" width="9%"><i><font color="#808080"
- size="2">SA</font></i></td>
- <td align="center" height="22" width="9%"><i><font color="#808080"
- size="2">IH</font></i></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">AllowsDuplicates</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="9%"><font size="2">O(1)</font></td>
- <td height="22" width="9%"><font size="2">O(1)</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">SyncRoot</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="9%"><font size="2">O(1)</font></td>
- <td height="22" width="9%"><font size="2">O(1)</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">IsEmpty</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="9%"><font size="2">O(1)</font></td>
- <td height="22" width="9%"><font size="2">O(1)</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">Add</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(n)</font></td>
- <td height="22" width="9%"><font size="2">O(log n)</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">AddAll</font></td>
- <td height="22" width="8%"><font size="2">O(m)</font></td>
- <td height="22" width="8%"><font size="2">O(m)</font></td>
- <td height="22" width="8%"><font size="2">O(m)</font></td>
- <td height="22" width="8%"><font size="2">O(m)</font></td>
- <td height="22" width="8%"><font size="2">O(m)</font></td>
- <td height="22" width="8%"><font size="2">O(m)</font></td>
- <td height="22" width="8%"><font size="2">O(mlog n)</font></td>
- <td height="22" width="8%"><font size="2">O(mlog n)</font></td>
- <td height="22" width="9%"><font size="2">O(mlog n)</font></td>
- <td height="22" width="9%"><font size="2">??</font></td>
- </tr>
- <tr>
- <td height="22" width="14%"><i><font color="#808080" size="2">ICollection<T></font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">HB</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">AL</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">LL</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">HAL</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">HLL</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">RBTS</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">RBTB</font></i></td>
- <td align="center" height="22" width="9%"><i><font color="#808080"
- size="2">SA</font></i></td>
- <td align="center" height="22" width="9%"><i><font color="#808080"
- size="2">IH</font></i></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">IsReadOnly</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="9%"><font size="2">O(1)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">ContainsSpeed</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="9%"><font size="2">O(1)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">GetHashCode</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="9%"><font size="2">O(1)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">Equals</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="9%"><font size="2">O(1)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">Contains</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">ContainsCount</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">ContainsAll</font></td>
- <td height="22" width="8%"><font size="2">O(m)</font></td>
- <td height="22" width="8%"><font size="2">O(m)</font></td>
- <td height="22" width="8%"><font size="2">O(mn)*</font></td>
- <td height="22" width="8%"><font size="2">O(mn)*</font></td>
- <td height="22" width="8%"><font size="2">O(m)</font></td>
- <td height="22" width="8%"><font size="2">O(m)</font></td>
- <td height="22" width="8%"><font size="2">O(m logn)</font></td>
- <td height="22" width="8%"><font size="2">O(m logn)</font></td>
- <td height="22" width="9%"><font size="2">O(m logn)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">Find</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">FindOrAdd</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">Update</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">UpdateOrAdd</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">Remove</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">RemoveWithReturn</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">RemoveAllCopies</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">RemoveAll</font></td>
- <td height="22" width="8%"><font size="2">O(m)</font></td>
- <td height="22" width="8%"><font size="2">O(m)</font></td>
- <td height="22" width="8%"><font size="2">O(mn)*</font></td>
- <td height="22" width="8%"><font size="2">O(mn)*</font></td>
- <td height="22" width="8%"><font size="2">O(m+n)</font></td>
- <td height="22" width="8%"><font size="2">O(m)</font></td>
- <td height="22" width="8%"><font size="2">O(m logn)</font></td>
- <td height="22" width="8%"><font size="2">O(m logn)</font></td>
- <td height="22" width="9%"><font size="2">O(m logn)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">Clear</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="9%"><font size="2">O(1)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">RetainAll</font></td>
- <td height="22" width="8%"><font size="2">O(m)?</font></td>
- <td height="22" width="8%"><font size="2">O(m)</font></td>
- <td height="22" width="8%"><font size="2">O(mn)*</font></td>
- <td height="22" width="8%"><font size="2">O(mn)*</font></td>
- <td height="22" width="8%"><font size="2">O(m+n)</font></td>
- <td height="22" width="8%"><font size="2">O(m)</font></td>
- <td height="22" width="8%"><font size="2">O(m logn)</font></td>
- <td height="22" width="8%"><font size="2">O(m logn)</font></td>
- <td height="22" width="9%"><font size="2">O(m logn)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="14%"><i><font color="#808080" size="2">ISequenced<T></font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">HB</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">AL</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">LL</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">HAL</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">HLL</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">RBTS</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">RBTB</font></i></td>
- <td align="center" height="22" width="9%"><i><font color="#808080"
- size="2">SA</font></i></td>
- <td align="center" height="22" width="9%"><i><font color="#808080"
- size="2">IH</font></i></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">GetHashCode</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="9%"><font size="2">O(1)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">Equals</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="9%"><font size="2">O(1)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="14%"><i><font color="#808080" size="2">IIndexed<T></font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">HB</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">AL</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">LL</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">HAL</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">HLL</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">RBTS</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">RBTB</font></i></td>
- <td align="center" height="22" width="9%"><i><font color="#808080"
- size="2">SA</font></i></td>
- <td align="center" height="22" width="9%"><i><font color="#808080"
- size="2">IH</font></i></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">this[i]</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(n)$</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(n)$</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">this[start,end]</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">IndexOf()</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">LastIndexOf()</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">RemoveAt</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(n)$</font></td>
- <td height="22" width="8%"><font size="2">O(n)$</font></td>
- <td height="22" width="8%"><font size="2">O(n)$</font></td>
- <td height="22" width="8%"><font size="2">O(n)$</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">RemoveInterval</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n log n)*</font></td>
- <td height="22" width="8%"><font size="2">O(n log n)*</font></td>
- <td height="22" width="9%"><font size="2">O(n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="14%"><i><font color="#808080" size="2">IList<T></font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">HB</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">AL</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">LL</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">HAL</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">HLL</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">RBTS</font></i></td>
- <td align="center" height="22" width="8%"><i><font color="#808080"
- size="2">RBTB</font></i></td>
- <td align="center" height="22" width="9%"><i><font color="#808080"
- size="2">SA</font></i></td>
- <td align="center" height="22" width="9%"><i><font color="#808080"
- size="2">IH</font></i></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">First</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">Last</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">FIFO</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">this[i]</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(n)$</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(n)$</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">Base</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">Offset</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">Map()</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">Insert()</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(n)$</font></td>
- <td height="22" width="8%"><font size="2">O(n)$</font></td>
- <td height="22" width="8%"><font size="2">O(n)$</font></td>
- <td height="22" width="8%"><font size="2">O(n)$</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">InsertFirst()</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">InsertLast()</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">InsertBefore()</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">InsertAfter()</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">InsertAll()</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(m+n)</font></td>
- <td height="22" width="8%"><font size="2">O(m+n)</font></td>
- <td height="22" width="8%"><font size="2">O(m+n)</font></td>
- <td height="22" width="8%"><font size="2">O(m+n)</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">FindAll()</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">Remove()</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(n)$</font></td>
- <td height="22" width="8%"><font size="2">(1)</font></td>
- <td height="22" width="8%"><font size="2">O(n)$</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">RemoveFirst()</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">RemoveLast()</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">View()</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">Slide() (amount: d)</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(d)</font></td>
- <td height="22" width="8%"><font size="2">O(d)</font></td>
- <td height="22" width="8%"><font size="2">O(d)</font></td>
- <td height="22" width="8%"><font size="2">O(d)</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">Reverse()</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">IsSorted()</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">Sort()</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(n log n)</font></td>
- <td height="22" width="8%"><font size="2">O(n log n)</font></td>
- <td height="22" width="8%"><font size="2">O(n log n)</font></td>
- <td height="22" width="8%"><font size="2">O(n log n)</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">Shuffle()</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="14%"><i><font color="#808080" size="2">IPriorityQueue<T></font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">HB</font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">AL</font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">LL</font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">HAL</font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">HLL</font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">RBTS</font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">RBTB</font></i></td>
- <td height="22" width="9%"><i><font color="#808080" size="2">SA</font></i></td>
- <td height="22" width="9%"><i><font color="#808080" size="2">IH</font></i></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">FindMin()</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(1)</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">DeleteMin()</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(log n)</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">FindMax()</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(1)</font></td>
- </tr>
- <tr>
- <td height="30" width="9%"><font size="2">DeleteMax()</font></td>
- <td height="30" width="8%"><font size="2">-</font></td>
- <td height="30" width="8%"><font size="2">-</font></td>
- <td height="30" width="8%"><font size="2">-</font></td>
- <td height="30" width="8%"><font size="2">-</font></td>
- <td height="30" width="8%"><font size="2">-</font></td>
- <td height="30" width="8%"><font size="2">-</font></td>
- <td height="30" width="8%"><font size="2">O(log n)</font></td>
- <td height="30" width="8%"><font size="2">O(log n)</font></td>
- <td height="30" width="9%"><font size="2">O(log n)</font></td>
- <td height="30" width="9%"><font size="2">O(log n)</font></td>
- </tr>
- <tr>
- <td height="30" width="9%"> <font size="2">Comparer</font></td>
- <td height="30" width="8%"> <font size="2">-</font></td>
- <td height="30" width="8%"> <font size="2">-</font></td>
- <td height="30" width="8%"> <font size="2">-</font></td>
- <td height="30" width="8%"> <font size="2">-</font></td>
- <td height="30" width="8%"> <font size="2">-</font></td>
- <td height="30" width="8%"> <font size="2">-</font></td>
- <td height="30" width="8%"> <font size="2">O(1)</font></td>
- <td height="30" width="8%"> <font size="2">O(1)</font></td>
- <td height="30" width="9%"> <font size="2">O(1)</font></td>
- <td height="30" width="9%"> <font size="2">O(1)</font></td>
- </tr>
- <tr>
- <td height="22" width="14%"><i><font color="#808080" size="2">ISorted<T></font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">HB</font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">AL</font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">LL</font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">HAL</font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">HLL</font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">RBTS</font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">RBTB</font></i></td>
- <td height="22" width="9%"><i><font color="#808080" size="2">SA</font></i></td>
- <td height="22" width="9%"><i><font color="#808080" size="2">IH</font></i></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">Predecessor</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">Successor</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">WeakPredecessor</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">WeakSuccessor</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">Cut</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">RangeFrom</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">RangeFromTo</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">RangeTo</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">RangeAll</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="9%"><font size="2">O(1)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">AddSorted</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">?</font></td>
- <td height="22" width="8%"><font size="2">?</font></td>
- <td height="22" width="9%"><font size="2">?</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">RemoveRangeFrom</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(nlog n)*</font></td>
- <td height="22" width="8%"><font size="2">O(nlog n)*</font></td>
- <td height="22" width="9%"><font size="2">O(n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">RemoveRangeFromTo</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(nlog n)*</font></td>
- <td height="22" width="8%"><font size="2">O(nlog n)*</font></td>
- <td height="22" width="9%"><font size="2">O(n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">RemoveRangeTo</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(nlog n)*</font></td>
- <td height="22" width="8%"><font size="2">O(nlog n)*</font></td>
- <td height="22" width="9%"><font size="2">O(n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="14%"><i><font color="#808080" size="2">IIndexedSorted<T></font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">HB</font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">AL</font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">LL</font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">HAL</font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">HLL</font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">RBTS</font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">RBTB</font></i></td>
- <td height="22" width="9%"><i><font color="#808080" size="2">SA</font></i></td>
- <td height="22" width="9%"><i><font color="#808080" size="2">IH</font></i></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">Map</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="9%"><font size="2">O(n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">CountFrom</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">CountFromTo</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">CountTo</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">RangeFrom</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">RangeFromTo</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">RangeTo</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="8%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">O(log n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">FindAll</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="8%"><font size="2">O(n)</font></td>
- <td height="22" width="9%"><font size="2">O(n)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- <tr>
- <td height="22" width="14%"><i><font color="#808080" size="2">IPersistentSorted<T></font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">HB</font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">AL</font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">LL</font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">HAL</font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">HLL</font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">RBTS</font></i></td>
- <td height="22" width="8%"><i><font color="#808080" size="2">RBTB</font></i></td>
- <td height="22" width="9%"><i><font color="#808080" size="2">SA</font></i></td>
- <td height="22" width="9%"><i><font color="#808080" size="2">IH</font></i></td>
- </tr>
- <tr>
- <td height="22" width="9%"><font size="2">Snapshot()</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">-</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="8%"><font size="2">O(1)</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- <td height="22" width="9%"><font size="2">-</font></td>
- </tr>
- </tbody>
-</table>
-<h1><a class="mozTocH1" name="mozTocId712409"></a><a
- name="PerformanceDict">Performance</a> details for dictionary classes</h1>
-<table border="1" width="467">
- <tbody>
- <tr>
- <th width="302">Member</th>
- <th width="79">HashDictionary<K,V></th>
- <th width="64">TreeDictionary<K,V></th>
- </tr>
- <tr>
- <td width="302"><i><font color="#808080" size="2">IEnumerable<KeyValuePair<K,V>></font></i></td>
- <td width="79"><font color="#808080"> </font></td>
- <td width="64"> </td>
- </tr>
- <tr>
- <td width="302"><font size="2">GetEnumerator()</font></td>
- <td width="79"><font size="2">O(1)</font></td>
- <td width="64"><font size="2">O(1)</font></td>
- </tr>
- <tr>
- <td width="302"><i><font color="#808080" size="2">IDictionary<K,V></font></i></td>
- <td width="79"><font color="#808080"> </font></td>
- <td width="64"> </td>
- </tr>
- <tr>
- <td width="302"><font size="2">this[key]</font></td>
- <td width="79"><font size="2">O(1)</font></td>
- <td width="64"><font size="2">O(log n)</font></td>
- </tr>
- <tr>
- <td width="302"><font size="2">Count</font></td>
- <td width="79"><font size="2">O(1)</font></td>
- <td width="64"><font size="2">O(1)</font></td>
- </tr>
- <tr>
- <td width="302"><font size="2">IsReadOnly</font></td>
- <td width="79"><font size="2">O(1)</font></td>
- <td width="64"><font size="2">O(1)</font></td>
- </tr>
- <tr>
- <td width="302"><font size="2">SyncRoot</font></td>
- <td width="79"><font size="2">O(1)</font></td>
- <td width="64"><font size="2">O(1)</font></td>
- </tr>
- <tr>
- <td width="302"><font size="2">Keys</font></td>
- <td width="79"><font size="2">O(1)</font></td>
- <td width="64"><font size="2">O(1)</font></td>
- </tr>
- <tr>
- <td width="302"><font size="2">Values</font></td>
- <td width="79"><font size="2">O(1)</font></td>
- <td width="64"><font size="2">O(1)</font></td>
- </tr>
- <tr>
- <td width="302"><font size="2">Add()</font></td>
- <td width="79"><font size="2">O(1)</font></td>
- <td height="22" width="64"><font size="2">O(log n)</font></td>
- </tr>
- <tr>
- <td width="302"><font size="2">Remove()</font></td>
- <td width="79"><font size="2">O(1)</font></td>
- <td height="22" width="64"><font size="2">O(log n)</font></td>
- </tr>
- <tr>
- <td width="302"><font size="2">Clear()</font></td>
- <td width="79"><font size="2">O(1)</font></td>
- <td height="22" width="64"><font size="2">O(1)</font></td>
- </tr>
- <tr>
- <td width="302"><font size="2">Contains()</font></td>
- <td width="79"><font size="2">O(1)</font></td>
- <td height="22" width="64"><font size="2">O(log n)</font></td>
- </tr>
- <tr>
- <td width="302"><font size="2">Find()</font></td>
- <td width="79"><font size="2">O(1)</font></td>
- <td height="22" width="64"><font size="2">O(log n)</font></td>
- </tr>
- <tr>
- <td width="302"><font size="2">Update()</font></td>
- <td width="79"><font size="2">O(1)</font></td>
- <td height="22" width="64"><font size="2">O(log n)</font></td>
- </tr>
- <tr>
- <td width="302"><font size="2">FindOrAdd</font></td>
- <td width="79"><font size="2">O(1)</font></td>
- <td height="22" width="64"><font size="2">O(log n)</font></td>
- </tr>
- <tr>
- <td width="302"><font size="2">UpdateOrAdd</font></td>
- <td width="79"><font size="2">O(1)</font></td>
- <td height="22" width="64"><font size="2">O(log n)</font></td>
- </tr>
- <tr>
- <td width="302"><i><font color="#808080" size="2">ISortedDictionary<K,V></font></i></td>
- <td width="79"><font color="#808080"> </font></td>
- <td width="64"> </td>
- </tr>
- <tr>
- <td height="22" width="302"><font size="2">Predecessor</font></td>
- <td width="79"><font size="2">-</font></td>
- <td height="22" width="64"><font size="2">O(log n)</font></td>
- </tr>
- <tr>
- <td height="22" width="302"><font size="2">Successor</font></td>
- <td width="79"><font size="2">-</font></td>
- <td height="22" width="64"><font size="2">O(log n)</font></td>
- </tr>
- <tr>
- <td height="22" width="302"><font size="2">WeakPredecessor</font></td>
- <td width="79"><font size="2">-</font></td>
- <td height="22" width="64"><font size="2">O(log n)</font></td>
- </tr>
- <tr>
- <td height="22" width="302"><font size="2">WeakSuccessor</font></td>
- <td width="79"><font size="2">-</font></td>
- <td height="22" width="64"><font size="2">O(log n)</font></td>
- </tr>
- </tbody>
-</table>
-</body>
-</html>
|