Project

General

Profile

Download (122 KB) Statistics
| Revision:

root / branches / compiler / cSharp / ooasCompiler / src / libs / c5 / docNet / c5doc / userguide.htm @ 3

1 
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
2 
<html>
3 
<head>
4 
  <title>C5 User's Guide</title>
5 
  <style>
6 
<!--
7 
.revvid      { color: #FFFFFF; background-color: #00AA00; font-weight: bold }
8 
-->
9 
  </style>
10 
</head>
11 
<body>
12 
<h1><a class="mozTocH1" name="mozTocId905770"></a>C5 User's guide for
13 
prerelease version 0.5</h1>
14 
<h2><a class="mozTocH2" name="mozTocId507311"></a>Table of contents</h2>
15 
<ul class="readonly" id="mozToc">
16 
<!--mozToc h1 1 h2 2 h3 3 h4 4 h5 5 h6 6--><li><a href="#mozTocId905770">C5
17 
User's guide for prerelease version 0.5</a>
18 
    <ul>
19 
      <li><a href="#mozTocId507311">Table of contents</a></li>
20 
    </ul>
21 
  </li>
22 
  <li><a href="#mozTocId564527">Overview</a></li>
23 
  <li><a href="#mozTocId86956">Interfaces</a>
24 
    <ul>
25 
      <li><a href="#mozTocId21725">"Proper" collection interfaces</a></li>
26 
      <li><a href="#mozTocId721827">Dictionary interfaces</a></li>
27 
      <li><a href="#mozTocId908053">Query result interfaces</a></li>
28 
    </ul>
29 
  </li>
30 
  <li><a href="#mozTocId110895">To construct a collection</a>
31 
    <ul>
32 
      <li><a href="#mozTocId850165">To use an external equalityComparer</a></li>
33 
      <li><a href="#mozTocId162938">To use an external comparer</a></li>
34 
      <li><a href="#mozTocId957374">To make collections of collections</a></li>
35 
    </ul>
36 
  </li>
37 
  <li><a href="#mozTocId486186">Special topics</a>
38 
    <ul>
39 
      <li><a href="#mozTocId48263">To choose a set or bag collection</a></li>
40 
      <li><a href="#mozTocId929755">To work on part of a list: list
41 
views</a></li>
42 
      <li><a href="#mozTocId650306">To work with persistent red-black
43 
trees</a></li>
44 
      <li><a href="#mozTocId553609">To implement new collection classes
45 
or subclass an existing one</a></li>
46 
      <li><a href="#mozTocId753674">To present a read only view of a
47 
collection</a></li>
48 
    </ul>
49 
  </li>
50 
  <li><a href="#mozTocId6619">Collection classes by data structure/class</a></li>
51 
  <li><a href="#mozTocId393559">Planned architecture or interface
52 
changes for first release</a></li>
53 
  <li><a href="#mozTocId336849">Performance details for proper
54 
collection classes</a></li>
55 
  <li><a href="#mozTocId712409">Performance details for dictionary
56 
classes</a></li>
57 
</ul>
58 
<h1><a class="mozTocH1" name="mozTocId564527"></a>Overview<br>
59 
</h1>
60 
<p>C5 is a comprehensive library of collection classes for the <a
61 
 href="http://www.ecma-international.org/publications/standards/Ecma-335.htm">Common
62 
Language Infrastructure</a> (CLI). This guide describes prerelease
63 
version 0.5 of&nbsp; C5. <br>
64 
</p>
65 
<p>C5 is a
66 
refactoring and extension of the <a
67 
 href="http://www.dina.kvl.dk/%7Esestoft/gcsharp/index.html#collection">generic
68 
collection classes</a> developed by Peter Sestoft while visiting
69 
Microsoft
70 
Research in Cambridge.</p>
71 
<p> Unless stated otherwise types mentioned below will belong to the
72 
"C5"
73 
namespace; and all code examples assume a "using C5;" clause (and no
74 
"using System.Collection.Generics;" clause)..&nbsp;</p>
75 
<p>The goals in the development of the library has been</p>
76 
<ul>
77 
  <li>
78 
    <p class="MsoNormal"><span style="" lang="EN-US">To create a
79 
library of collection classes for the CLI that can assist expert and
80 
non-expert programmers on the platform to develop correct and efficient
81 
applications.</span> </p>
82 
  </li>
83 
  <li>
84 
    <p class="MsoNormal"><span style="" lang="EN-US">The library should
85 
at least fill the gaps in the standard &#8220;System.Collections.Generics&#8221;
86 
namespace compared to standard collection class libraries for related
87 
object oriented languages like Java, and utilize the new facilities for
88 
generic </span><span style="" lang="EN-US">programming. Microsoft
89 
recently (mid 2004) seems to have changed their minds and ntend to
90 
bridge that gap in the beta2 version of VS 2005 due at the end of 2004.</span>
91 
    </p>
92 
  </li>
93 
</ul>
94 
<p>In order to fulfill the efficiency goal, the library utilizes
95 
first-class <a href="#datastructures">data structures</a>
96 
inside its collection classes. The library has been constructed with
97 
the modern
98 
object oriented programming principle of&nbsp; "<a href="#Interfaces">code
99 
to interfaces, not to implementations</a>" in mind, while the interface
100 
architecture has been carefully crafted to reflect the efficient data
101 
structures
102 
actually existence.</p>
103 
<p>A collection in the sense of this library is a plain "collection of
104 
items of a single type". A collection does not impose any other logical
105 
structure on its items than perhaps uniqueness or sequence ordering.</p>
106 
<p>The main division line among the collection classes of this library
107 
is the
108 
distinction between <a href="#Proper%20collection%20interfaces">"proper"
109 
collections</a> and <a href="#Dictionary%20interfaces">dictionaries</a>.
110 
A
111 
dictionary is a class that defines a partial function (or map) from one
112 
item
113 
type (the keys) to another one (the values). A dictionary can be viewed
114 
as a
115 
collection of (key,value) pairs having the property of defining a
116 
partial
117 
function.</p>
118 
<p>The item type for the collection classes are always given by generic
119 
parameters. For a proper collection, there will be a single parameter,
120 
customarily called T, as in HashSet&lt;T&gt;. For a dictionary there
121 
will be two - the key and value types -
122 
as in HashDictionary&lt;K,V&gt;.</p>
123 
<p>A collection class, or rather the data structure inside, can be
124 
either
125 
equality based or comparison based. An equality based collection will
126 
have an
127 
associated so-called equalityComparer of type <a href="main.htm#T:C5.IEqualityComparer%601">IEqualityComparer&lt;T&gt;</a>,
128 
where T is the item type of the collection. A comparison based
129 
collection has an
130 
associated comparer of type <a href="main.htm#T:C5.IComparer%601">IComparer&lt;T&gt;</a>.
131 
The section below on <a href="#Constructing">creation</a> of
132 
collection classes
133 
explains how the equalityComparers and comparers are chosen. NB: this design will
134 
be modified soon, cf. <a href="#planned">Planned changes</a>.<br>
135 
</p>
136 
<p>Collection classes in the library have either set or bag semantics.
137 
A set
138 
collection can at most contain one copy of an item, while bag
139 
collections may
140 
contain several. One can programmatically see at runtime if an editable
141 
collection class has set or bag semantics by checking the <a
142 
 href="main.htm#P:C5.IExtensible%601.AllowsDuplicates">
143 
AllowsDuplicates</a>
144 
property. At compile time, refer to the <a href="#set%20or%20bag">set
145 
or bag table</a>
146 
below for an overview. <br>
147 
</p>
148 
<h1><a class="mozTocH1" name="mozTocId86956"></a><a name="Interfaces">Interfaces</a></h1>
149 
<p>The C5 library is designed to make it easy to program to interfaces
150 
instead
151 
of implementations. In particular, all public properties and methods of
152 
the
153 
collection classes belong to their implemented interfaces (except for
154 
the odd
155 
special diagnostic method and the odd mistake to be weeded out before
156 
release). The typical programming style
157 
would be</p>
158 
<blockquote>
159 
  <p><code>IList&lt;int&gt; lst = new LinkedList&lt;int&gt;();<br>
160 
lst.Add(7);</code></p>
161 
</blockquote>
162 
<p>instead of&nbsp;</p>
163 
<blockquote>
164 
  <p><code> LinkedList&lt;int&gt; lst = new LinkedList&lt;int&gt;();<br>
165 
lst.Add(7);</code></p>
166 
</blockquote>
167 
<p>Note that with this programming style, the Add call will be compiled
168 
to an
169 
interface call instead of a (virtual) method call, but interface calls
170 
on the
171 
CLR (at least the Microsoft implementation) are at most very slightly
172 
slower
173 
than virtual calls, so one should not shun the interface style for
174 
performance
175 
reasons.</p>
176 
<p>We will discuss the collection classes available in C5 structured
177 
according
178 
to the main functional interfaces of the <a
179 
 href="#Proper%20collection%20interfaces">proper
180 
collections</a>, the <a href="#Dictionary%20interfaces">dictionaries</a>
181 
and the
182 
interfaces of <a href="#Query%20result%20interfaces">query results</a>.</p>
183 
<h2><a class="mozTocH2" name="mozTocId21725"></a><a
184 
 name="Proper collection interfaces">"Proper" collection interfaces</a></h2>
185 
<p>The following diagam shows the type hierarchy of the proper
186 
collection classes:</p>
187 
<p><img alt="Interface hierarchy" src="ClsdiagWork.png"
188 
 style="width: 757px; height: 498px;"><br>
189 
The&nbsp;most important interfaces - those that are directly
190 
implemented by
191 
collection classes - are listed to the left in this table with a short
192 
description in the middle and all implementing classes to the
193 
right.&nbsp;</p>
194 
<p>Please see also the <a href="#PerformanceProper">complete
195 
complexity table</a>
196 
for more comprehensive guidance.</p>
197 
<p>To identify which classes are equalityComparer or comparer based and which
198 
classes
199 
implement set or bag we use the following symbols:</p>
200 
<table border="1" width="471">
201 
  <tbody>
202 
    <tr>
203 
      <td width="116">set: <code class="revvid">S</code> </td>
204 
      <td width="117"> bag: <code class="revvid">B</code> </td>
205 
      <td width="117"> equalityComparer: <code class="revvid">H</code> </td>
206 
      <td width="117"> comparer: <code class="revvid">C</code> </td>
207 
    </tr>
208 
  </tbody>
209 
</table>
210 
<table border="1" width="100%">
211 
  <tbody>
212 
    <tr>
213 
      <th width="19%">Interface</th>
214 
      <th width="52%">Short description</th>
215 
      <th width="29%">Implementing classes</th>
216 
    </tr>
217 
    <tr>
218 
      <td valign="top" width="19%"><a
219 
 href="main.htm#T:C5.ICollection%601">ICollection&lt;T&gt;</a>&nbsp;</td>
220 
      <td valign="top" width="52%">This is the fundamental&nbsp;type
221 
of&nbsp; updateable collections. It has operations for searching for
222 
items, for adding, updating and removing one or a bunch of items, for
223 
clearing the collection and transforming the collection to an
224 
array.&nbsp;
225 
      <p>If one only needs these operations, the hash set and hash bag
226 
classes are fastest for if we have a equalityComparer for the items and the
227 
red-black tree classes are fastest if we must use a comparer.</p>
228 
      </td>
229 
      <td valign="top" width="29%"><code class="revvid">SH</code> <a
230 
 href="main.htm#T:C5.HashSet%601">HashSet&lt;T&gt;</a><br>
231 
      <code class="revvid">BH</code> <a
232 
 href="main.htm#T:C5.HashBag%601">HashBag&lt;T&gt;</a><br>
233 
      <code class="revvid">BH</code> <a
234 
 href="main.htm#T:C5.LinkedList%601">LinkedList&lt;T&gt;</a><br>
235 
      <code class="revvid">SH</code> <a
236 
 href="main.htm#T:C5.HashedLinkedList%601">HashedLinkedList&lt;T&gt;</a><br>
237 
      <code class="revvid">BH</code> <a
238 
 href="main.htm#T:C5.ArrayList%601">ArrayList&lt;T&gt;</a><br>
239 
      <code class="revvid">SH</code> <a
240 
 href="main.htm#T:C5.HashedArrayList%601"> HashedArrayList&lt;T&gt;<br>
241 
      </a> <code class="revvid">SC</code> <a
242 
 href="main.htm#T:C5.SortedArray%601"> SortedArray&lt;T&gt;</a><br>
243 
      <code class="revvid">SC</code> <a
244 
 href="main.htm#T:C5.TreeSet%601"> TreeSet&lt;T&gt;</a><br>
245 
      <code class="revvid">BC</code> <a
246 
 href="main.htm#T:C5.TreeBag%601"> TreeBag&lt;T&gt;</a></td>
247 
    </tr>
248 
    <tr>
249 
      <td valign="top" width="19%"><a
250 
 href="main.htm#T:C5.IPriorityQueue%601">IPriorityQueue&lt;T&gt;</a>&nbsp;</td>
251 
      <td valign="top" width="52%">This is a special case in the
252 
library, being the only type of updateable collection interface that
253 
does not implement IEditableCollection&lt;T&gt;. The reason for its
254 
presence is the specialized "heap" data structures for priority queues
255 
that only support these operations.
256 
      <p>If one only needs these the priority queue operations and is
257 
satisfied with bag semantics, then IntervalHeap&lt;P&gt;&nbsp; is the
258 
fastest choice. </p>
259 
      </td>
260 
      <td valign="top" width="29%"> <code class="revvid">BC</code> <a
261 
 href="main.htm#T:C5.IntervalHeap%601">IntervalHeap&lt;T&gt;</a><br>
262 
      <code class="revvid">SC</code> <a
263 
 href="main.htm#T:C5.TreeSet%601"> TreeSet&lt;T&gt;</a><br>
264 
      <code class="revvid">BC</code> <a
265 
 href="main.htm#T:C5.TreeBag%601"> TreeBag&lt;T&gt;</a></td>
266 
    </tr>
267 
    <tr>
268 
      <td valign="top" width="19%"><a href="main.htm#T:C5.IList%601">IList&lt;T&gt;</a>&nbsp;</td>
269 
      <td valign="top" width="52%">This is an updateable collection
270 
with sequence order imposed on the items by the user at insertion time
271 
or by later rearrangements.&nbsp;
272 
      <p>There are two main base data structures: dynamic arrays and
273 
doubly linked lists with very different complexity profile.&nbsp;The
274 
plain linked list is fast for operations at the end points only, while
275 
the plain array list have very fast lookups by index, but update
276 
operations are only fast at the right end point.&nbsp;</p>
277 
      <p>The Hashed- variants employ an index based on a hash table.
278 
This speeds up lookups by item considerably and for the linked list
279 
variant also insertions before or after specific items. The index
280 
changes the classes from bags to sets.&nbsp;</p>
281 
      <p>The hashed variants more than double the time of otherwise
282 
fast update operations, and should only be used when really
283 
needed.&nbsp;</p>
284 
      </td>
285 
      <td valign="top" width="29%"> <code class="revvid">BH</code> <a
286 
 href="main.htm#T:C5.LinkedList%601"> LinkedList&lt;T&gt;</a><br>
287 
      <code class="revvid">SH</code> <a
288 
 href="main.htm#T:C5.HashedLinkedList%601"> HashedLinkedList&lt;T&gt;</a><br>
289 
      <code class="revvid">BH</code> <a
290 
 href="main.htm#T:C5.ArrayList%601"> ArrayList&lt;T&gt;</a><br>
291 
      <code class="revvid">SH</code> <a
292 
 href="main.htm#T:C5.HashedArrayList%601"> HashedArrayList&lt;T&gt;</a></td>
293 
    </tr>
294 
    <tr>
295 
      <td valign="top" width="19%"><a
296 
 href="main.htm#T:C5.IIndexedSorted%601">IIndexedSorted&lt;T&gt;</a>&nbsp;</td>
297 
      <td valign="top" width="52%">This is an updateable collection
298 
with sequence order given by a comparer.&nbsp;
299 
      <p>There are two main data structures inside the implementations:
300 
red-black search trees and a dynamic array kept sorted at all times.</p>
301 
      <p>The differences are chiefly that the trees have much faster
302 
update operations, while the sorted array is somewhat faster at index
303 
lookups. In fact, the sorted array should only be used for static
304 
operation, where the collection is created and populated and then not
305 
changed again. </p>
306 
      </td>
307 
      <td valign="top" width="29%"> <code class="revvid">SC</code> <a
308 
 href="main.htm#T:C5.SortedArray%601"> SortedArray&lt;T&gt;</a><br>
309 
      <code class="revvid">SC</code> <a
310 
 href="main.htm#T:C5.TreeSet%601"> TreeSet&lt;T&gt;</a><br>
311 
      <code class="revvid">BC</code> <a
312 
 href="main.htm#T:C5.TreeBag%601"> TreeBag&lt;T&gt;</a></td>
313 
    </tr>
314 
    <tr>
315 
      <td valign="top" width="19%"><a
316 
 href="main.htm#T:C5.IPersistentSorted%601">IPersistentSorted&lt;T&gt;</a>&nbsp;</td>
317 
      <td valign="top" width="52%">This is a sorted collection that
318 
support very fast clones that themselves are sorted. The only
319 
implementation is the tree implementation with set and bag variants. </td>
320 
      <td valign="top" width="29%"> <code class="revvid">SC</code> <a
321 
 href="main.htm#T:C5.TreeSet%601"> TreeSet&lt;T&gt;</a><br>
322 
      <code class="revvid">BC</code> <a
323 
 href="main.htm#T:C5.TreeBag%601"> TreeBag&lt;T&gt;</a></td>
324 
    </tr>
325 
  </tbody>
326 
</table>
327 
<h2><a class="mozTocH2" name="mozTocId721827"></a><a
328 
 name="Dictionary interfaces">Dictionary interfaces</a></h2>
329 
<p>There are two dictionary interfaces:</p>
330 
<table border="1" width="100%">
331 
  <tbody>
332 
    <tr>
333 
      <th valign="top" width="19%">Interface</th>
334 
      <th width="56%">Short description</th>
335 
      <th width="25%">Implementing classes</th>
336 
    </tr>
337 
    <tr>
338 
      <td valign="top" width="19%"><a
339 
 href="main.htm#T:C5.IDictionary%602">IDictionary&lt;K,V&gt;</a> </td>
340 
      <td width="56%">This is the base dictionary interface.&nbsp;
341 
      <p>The choice is that one should use the hash dictionary unless
342 
one only has a comparer for the items, in which case the tree
343 
dictionary can be used.&nbsp; </p>
344 
      </td>
345 
      <td width="25%"><a href="main.htm#T:C5.HashDictionary%602">HashDictionary&lt;K,V&gt;</a><br>
346 
      <a href="main.htm#T:C5.TreeDictionary%602">TreeDictionary&lt;K,V&gt;</a></td>
347 
    </tr>
348 
    <tr>
349 
      <td valign="top" width="19%"><a
350 
 href="main.htm#T:C5.ISortedDictionary%602">ISortedDictionary&lt;K,V&gt;</a>
351 
      </td>
352 
      <td width="56%">This is a dictionary based on a comparer for the
353 
keys. There is only the tree implementation.&nbsp; </td>
354 
      <td width="25%"><a href="main.htm#T:C5.TreeDictionary%602">TreeDictionary&lt;K,V&gt;</a></td>
355 
    </tr>
356 
  </tbody>
357 
</table>
358 
<h2><a class="mozTocH2" name="mozTocId908053"></a><a
359 
 name="Query result interfaces">Query result interfaces</a></h2>
360 
<p>Some of the most basic collection interfaces have an important usage
361 
as the
362 
types of results of queries to collections, although these interfaces
363 
also
364 
appear at the base of the other collection interfaces and even as the
365 
types of
366 
synthetic collections. The interfaces in question are the standard
367 
System.Collections.Generics.IEnumerable&lt;T&gt;,
368 
<a href="main.htm#T:C5.ICollectionValue%601">ICollectionValue&lt;T&gt;</a>,
369 
<a href="main.htm#T:C5.IDirectedEnumerable%601">IDirectedEnumerable&lt;T&gt;</a>
370 
and <a href="main.htm#T:C5.IDirectedCollectionValue%601">IDirectedCollectionValue&lt;T&gt;</a>.</p>
371 
<p>The differences between the "Enumerable" and "Collection"
372 
variants are that the "Enumerable" variant only knows how to
373 
enumerate through its items, the "Collection" variants also knows how
374 
many items it has (without having to walk through an enumeration). The
375 
"Directed" variants are used for results of queries to sequenced
376 
collections (implementing <a href="main.htm#T:C5.ISequenced%601">ISequenced&lt;T&gt;</a>)
377 
and therefore have a non-implementation dependent enumeration order.
378 
The
379 
"Directed" variants supports two operations, <a
380 
 href="main.htm#M:C5.IDirectedCollectionValue%601.Backwards">Backwards()</a>
381 
to enable enumeration in the opposite direction and <a
382 
 href="main.htm#P:C5.IDirectedEnumerable%601.Direction">Direction</a>
383 
to tell if the enumeration order is forwards or backwards with respect
384 
to the
385 
original collection.</p>
386 
<p>Note: operations on an enumerator created by the GetEnumerator()
387 
method on System.Collections.Generics.IEnumerable&lt;T&gt; cannot be
388 
interleaved with update
389 
operations on
390 
the underlying collection.</p>
391 
<p>Note: for all enumerators in the library the operations have O(1)
392 
amortized
393 
complexity.</p>
394 
<h1><a class="mozTocH1" name="mozTocId110895"></a>To <a
395 
 name="Constructing">construct</a> a collection</h1>
396 
<p>All collections classes in C5 have (zero parameter) default
397 
constructors. So
398 
if we want to make a linked list of items of some type, <code>TheType</code>,
399 
and add an item to the list we will do</p>
400 
<p><code>&nbsp;&nbsp;&nbsp; IList&lt;TheType&gt; lst = new
401 
LinkedList&lt;TheType&gt;();<br>
402 
&nbsp;&nbsp;&nbsp; TheType t = ...;<br>
403 
&nbsp;&nbsp;&nbsp; lst.Add(t);</code></p>
404 
<p>The collection classes have no constructors that will take an array
405 
or a
406 
collection as parameter for prepopulating the collection, use the <a
407 
 href="file:///C:/home/kokholm/c5/vs/C5/main.htm#M:C5.ISink%601.AddAll%28C5.IEnumerable%7B%210%7D%29">
408 
AddAll</a> method
409 
instead. NB: in the released version, expect constructors with an
410 
enumerable as argument and constructors with a variable number of
411 
arguments ("params") for the initialization of the collection, see the <a
412 
 href="#planned">planned changes</a> section.<br>
413 
</p>
414 
<p>Some collection classes are governed by internal parameters that one
415 
can give
416 
non-default values at creation time (<code>fill</code> in <a
417 
 href="main.htm#T:C5.HashSet%601">HashSet&lt;T&gt;</a>,&nbsp;
418 
<a href="main.htm#T:C5.HashBag%601">HashBag&lt;T&gt;</a>, <a
419 
 href="main.htm#T:C5.HashDictionary%602">HashDictionary&lt;K,V&gt;</a>)
420 
or use internal tables that one can expand in advance if one has
421 
expectations of
422 
how large the collection will grow (HashSet&lt;T&gt;,&nbsp;
423 
HashBag&lt;T&gt;, HashDictionary&lt;K,V&gt;, <a
424 
 href="main.htm#T:C5.ArrayList%601">ArrayList&lt;T&gt;</a>,
425 
<a href="main.htm#T:C5.HashedArrayList%601"> HashedArrayList&lt;T&gt;</a>,
426 
<a href="main.htm#T:C5.SortedArray%601">SortedArray&lt;T&gt;</a>,
427 
<a href="main.htm#T:C5.IntervalHeap%601">IntervalHeap&lt;T&gt;</a>).</p>
428 
<p>For equality-based collection classes, these constructors will use a
429 
default
430 
equalityComparer to define equality of items according to the following table:</p>
431 
<table border="1">
432 
  <tbody>
433 
    <tr>
434 
      <th>T</th>
435 
      <th>default equalityComparer (implements IEqualityComparer&lt;T&gt;)</th>
436 
      <th>Equality and hash code by</th>
437 
    </tr>
438 
    <tr>
439 
      <td>int</td>
440 
      <td><a href="main.htm#T:C5.IntEqualityComparer">IntEqualityComparer</a></td>
441 
      <td>Equals and hash code of integer</td>
442 
    </tr>
443 
    <tr>
444 
      <td>other value type</td>
445 
      <td><a href="main.htm#T:C5.DefaultValueTypeEqualityComparer%601">DefaultValueTypeEqualityComparer&lt;T&gt;</a></td>
446 
      <td>methods inherited from object</td>
447 
    </tr>
448 
    <tr>
449 
      <td>IEditableCollection&lt;S&gt;</td>
450 
      <td><a href="main.htm#T:C5.EqualityComparerBuilder.UnsequencedEqualityComparer%602">EqualityComparerBuilder.UnsequencedEqualityComparer&lt;S,IEditableCollection&lt;S&gt;&gt;</a></td>
451 
      <td>contents without regards to sequence</td>
452 
    </tr>
453 
    <tr>
454 
      <td>ISequenced&lt;S&gt;</td>
455 
      <td><a href="main.htm#T:C5.EqualityComparerBuilder.SequencedEqualityComparer%602">EqualityComparerBuilder.SequencedEqualityComparer&lt;S,IEditableCollection&lt;S&gt;&gt;</a></td>
456 
      <td>contents with regards to sequence</td>
457 
    </tr>
458 
    <tr>
459 
      <td>other reference type</td>
460 
      <td><a href="main.htm#T:C5.DefaultReferenceTypeEqualityComparer%601">DefaultReferenceTypeEqualityComparer&lt;T&gt;</a></td>
461 
      <td>methods inherited from object</td>
462 
    </tr>
463 
  </tbody>
464 
</table>
465 
<p>For comparison-based collection classes, these constructors will use
466 
a
467 
default comparer:</p>
468 
<table border="1">
469 
  <tbody>
470 
    <tr>
471 
      <th>T</th>
472 
      <th>default comparer&nbsp;<br>
473 
(implements IComparer&lt;T&gt;)</th>
474 
      <th>Comparison by</th>
475 
    </tr>
476 
    <tr>
477 
      <td>int</td>
478 
      <td>IC</td>
479 
      <td>Standard integer comparison</td>
480 
    </tr>
481 
    <tr>
482 
      <td>implementing IComparable&lt;T&gt;</td>
483 
      <td><a href="main.htm#T:C5.NaturalComparer%601">NaturalComparer&lt;T&gt;</a></td>
484 
      <td>The CompareTo(T o)&nbsp; instance method</td>
485 
    </tr>
486 
    <tr>
487 
      <td>other implementing System.IComparable</td>
488 
      <td><a href="main.htm#T:C5.NaturalComparerO%601">NaturalComparerO&lt;T&gt;</a></td>
489 
      <td>The CompareTo(object o) instance method</td>
490 
    </tr>
491 
    <tr>
492 
      <td>other</td>
493 
      <td>-</td>
494 
      <td><i>collection class constructor throws an exception</i></td>
495 
    </tr>
496 
  </tbody>
497 
</table>
498 
<p>Sometimes, the default equalityComparer or comparer is not the right one for
499 
the
500 
problem at hand. In that case one must get hold on a equalityComparer or comparer
501 
of the
502 
right kind and supply it to one of the constructors of the collection
503 
classes
504 
that supports such a parameter. The procedure is demonstrated in the
505 
sections
506 
below on <a href="#external%20equalityComparer">external equalityComparers</a>, <a
507 
 href="#external%20comparer">external
508 
comparers</a> and <a href="#collections%20of%20collections">collections
509 
as items</a>.<br>
510 
</p>
511 
<p>NB: in the released version, expect the equalityComparers and comparers to be
512 
of the System.Collections.Generics.IComparer&lt;T&gt; type, see the <a
513 
 href="userguide.htm#planned">planned changes</a> section.</p>
514 
<h2><a class="mozTocH2" name="mozTocId850165"></a>To use an <a
515 
 name="external equalityComparer"> external equalityComparer</a></h2>
516 
<p>In addition to the helper classes referenced above, the library has
517 
the
518 
helper class <a href="main.htm#T:C5.KeyValuePairEqualityComparer%602">KeyValuePairEqualityComparer&lt;K,V&gt;</a>
519 
to construct a equalityComparer for pairs of the type <a
520 
 href="main.htm#T:C5.KeyValuePair%602">KeyValuePair&lt;K,V&gt;</a>,
521 
the type of entry of a K to V dictionary. The constructed equalityComparer will
522 
only take
523 
the first component of the pair into account. We can use these classes
524 
in the
525 
following way to make a linked list (with hash index) of pairs of
526 
strings
527 
identified by their first components using some custom equalityComparer on
528 
strings:</p>
529 
<blockquote>
530 
  <p><code>IEqualityComparer&lt;string&gt; csh = ...;<br>
531 
IEqualityComparer&lt;KeyValuePair&lt;string,string&gt;&gt; cph =&nbsp;<br>
532 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
533 
new KeyValuePairEqualityComparer&lt;string,string&gt;(csh);<br>
534 
IList&lt;KeyValuePair&lt;string,string&gt;&gt; lst =<br>
535 
  </code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<code>
536 
new HashedLinkedList&lt;KeyValuePair&lt;string,string&gt;&gt;(cph);<br>
537 
lst.Add(new KeyValuePair&lt;string,string&gt;("abe","kat"));</code></p>
538 
</blockquote>
539 
<p>One may, of course, program a equalityComparer oneself. This one should always
540 
do if
541 
the item type is defined as a struct (value type) that does not
542 
override the
543 
Equals and GetHashCode methods of object, since in that case the
544 
default equalityComparer
545 
will use the slow default versions of those methods supplied by the
546 
runtime via
547 
reflection.&nbsp;</p>
548 
<h2><a class="mozTocH2" name="mozTocId162938"></a>To use an <a
549 
 name="external comparer"> external comparer</a></h2>
550 
<p>There is a helper class for comparer of pairs: <a
551 
 href="main.htm#T:C5.KeyValuePairEqualityComparer%602">KeyValuePairComparer&lt;K,V&gt;</a>.
552 
We will show an example of a custom comparer. Imagine wanting to
553 
compare double
554 
precision floating point numbers with a tolerance. The following code
555 
snippet
556 
shows how one could make a tree set out of such numbers:</p>
557 
<blockquote>
558 
  <p><code>class DC : IComparer&lt;double&gt; {<br>
559 
&nbsp;&nbsp; const double eps = 1E-10;<br>
560 
&nbsp;&nbsp; int Compare(double a, double b)&nbsp;<br>
561 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; {return a &gt; b + eps ? 1 : a &lt; b -
562 
eps ? -1 : 0;}<br>
563 
}<br>
564 
  <br>
565 
void dowork() {<br>
566 
&nbsp;&nbsp; IComparer&lt;double&gt; dc = new DC();<br>
567 
&nbsp;&nbsp; ISorted&lt;double&gt; tree = new TreeSet&lt;double&gt;(dc);<br>
568 
&nbsp;&nbsp; tree.Add(3.45);<br>
569 
&nbsp;&nbsp; ...<br>
570 
}</code></p>
571 
</blockquote>
572 
<p>In this particular case, one would have to make sure, that two
573 
different
574 
floating point numbers are only identified by the comparer if they
575 
really should
576 
represent the same value and not by coincidence.</p>
577 
<h2><a class="mozTocH2" name="mozTocId957374"></a>To make <a
578 
 name="collections of collections"> collections of collections</a></h2>
579 
<p>When one wants to use a collection whose items itself are of
580 
collection type,
581 
one usually wants the interior collections to be identified by contents
582 
- either
583 
according to or irrespective of sequence order. An example could be
584 
transformations of <a
585 
 href="http://www.dina.kvl.dk/%7Esestoft/gcsharp/index.html#regexp">Finite
586 
Automatons</a>. The default equalityComparers and the EqualityComparerBuilder classes
587 
mentioned
588 
above may help to construct such collections of collections as in the
589 
examples
590 
that follow:</p>
591 
<p>To make an array list of sequenced collections identified by
592 
contents in
593 
sequenced fashion one would simply do:</p>
594 
<blockquote>
595 
  <p><code>ArrayList&lt;ISequenced&lt;int&gt;&gt; lst = new
596 
ArrayList&lt;ISequenced&lt;int&gt;&gt;();</code></p>
597 
</blockquote>
598 
<p>To make a linked list of linked lists identified by contents
599 
unsequenced, explicitly
600 
construct the collection equalityComparer:</p>
601 
<blockquote>
602 
  <p><code>IEqualityComparer&lt;LinkedList&lt;int&gt;&gt; lsth =<br>
603 
  </code>&nbsp;&nbsp;&nbsp;&nbsp; <code>new
604 
EqualityComparerBuilder.UnsequencedEqualityComparer&lt;int,LinkedList&lt;int&gt;&gt;();<br>
605 
LinkedList&lt;LinkedList&lt;int&gt;&gt; lst =<br>
606 
&nbsp;&nbsp; new LinkedList&lt;LinkedList&lt;int&gt;&gt;(lsth);</code></p>
607 
</blockquote>
608 
<p>If for some strange reason one would like to make a hash set of
609 
linked lists
610 
with the lists identified by reference equality one would simply do:</p>
611 
<blockquote>
612 
  <p><code>HashSet&lt;LinkedList&lt;int&gt;&gt; lst = new
613 
HashSet&lt;LinkedList&lt;int&gt;&gt;();</code></p>
614 
</blockquote>
615 
<p>If for even stranger reasons one would make a hash set of
616 
ISequenced&lt;int&gt; collections with the collections identified by
617 
reference
618 
equality one would do like this:</p>
619 
<blockquote>
620 
  <p><code>IEqualityComparer&lt;</code><code>ISequenced</code><code>&lt;int&gt;&gt;
621 
lsth =<br>
622 
  </code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <code>new
623 
DefaultReferenceTypeEqualityComparer&lt;</code><code>ISequenced</code><code>&lt;int&gt;&gt;();<br>
624 
HashSet&lt;</code><code>ISequenced</code><code>&lt;int&gt;&gt; lst =<br>
625 
&nbsp;&nbsp; new HashSet&lt;</code><code>ISequenced</code><code>&lt;int&gt;&gt;(lsth);</code></p>
626 
</blockquote>
627 
<h1><a class="mozTocH1" name="mozTocId486186"></a>Special topics</h1>
628 
<h2><a class="mozTocH2" name="mozTocId48263"></a>To choose a <a
629 
 name="set or bag"> set or bag</a> collection</h2>
630 
<p>The following table shows which of the collection classes have set
631 
semantics
632 
and which have bag semantics. All the implemented classes have fixed,
633 
compiled in semantics. <br>
634 
</p>
635 
<p>Note: when in a set collection, methods with an Add in the name will
636 
ignore
637 
attempts to add an item already there or flag the failed attempt by a
638 
Boolean return value; methods with an Insert in the name (only in
639 
lists) will throw an
640 
exception.</p>
641 
<table border="1" width="38%">
642 
  <tbody>
643 
    <tr>
644 
      <td valign="top" width="6%"><a href="main.htm#T:C5.HashSet%601">HashSet&lt;T&gt;</a></td>
645 
      <td valign="top" width="5%">set</td>
646 
    </tr>
647 
    <tr>
648 
      <td valign="top" width="6%"> <a href="main.htm#T:C5.HashBag%601">HashBag&lt;T&gt;</a></td>
649 
      <td valign="top" width="5%">bag</td>
650 
    </tr>
651 
    <tr>
652 
      <td valign="top" width="6%"> <a
653 
 href="main.htm#T:C5.LinkedList%601"> LinkedList&lt;T&gt;</a></td>
654 
      <td valign="top" width="5%">bag</td>
655 
    </tr>
656 
    <tr>
657 
      <td valign="top" width="6%"> <a
658 
 href="main.htm#T:C5.HashedLinkedList%601"> HashedLinkedList&lt;T&gt;</a></td>
659 
      <td valign="top" width="5%">set</td>
660 
    </tr>
661 
    <tr>
662 
      <td valign="top" width="6%"> <a
663 
 href="main.htm#T:C5.ArrayList%601"> ArrayList&lt;T&gt;</a></td>
664 
      <td valign="top" width="5%">bag</td>
665 
    </tr>
666 
    <tr>
667 
      <td valign="top" width="6%"> <a
668 
 href="main.htm#T:C5.HashedArrayList%601"> HashedArrayList&lt;T&gt; </a>
669 
      </td>
670 
      <td valign="top" width="5%">set</td>
671 
    </tr>
672 
    <tr>
673 
      <td valign="top" width="6%"> <a
674 
 href="main.htm#T:C5.SortedArray%601"> SortedArray&lt;T&gt;</a></td>
675 
      <td valign="top" width="5%">set</td>
676 
    </tr>
677 
    <tr>
678 
      <td valign="top" width="6%"> <a href="main.htm#T:C5.TreeSet%601">TreeSet&lt;T&gt;</a></td>
679 
      <td valign="top" width="5%">set</td>
680 
    </tr>
681 
    <tr>
682 
      <td valign="top" width="6%"> <a href="main.htm#T:C5.TreeBag%601">TreeBag&lt;T&gt;</a></td>
683 
      <td valign="top" width="5%">bag</td>
684 
    </tr>
685 
    <tr>
686 
      <td valign="top" width="6%"><a
687 
 href="main.htm#T:C5.IntervalHeap%601">IntervalHeap&lt;T&gt;</a></td>
688 
      <td valign="top" width="5%">bag</td>
689 
    </tr>
690 
  </tbody>
691 
</table>
692 
<h2><a class="mozTocH2" name="mozTocId929755"></a>To work on part of a
693 
list: list views</h2>
694 
<p>The IList&lt;T&gt; interface supports via the <a
695 
 href="main.htm#M:C5.IList%601.View%28System.Int32,System.Int32%29">
696 
View</a>
697 
method the functionality that one can zoom in on part of a list and use
698 
it as an
699 
IList&lt;T&gt; in its own right while having updates to the view passed
700 
through
701 
to the base (original) IList&lt;T&gt;. Using the <a
702 
 href="main.htm#M:C5.IList%601.Slide%28System.Int32%29">Slide</a>
703 
method calls, one may move the view around the base list. Using Slide
704 
repeatedly
705 
one can implement safe ways to iterate over a list while updating it.
706 
The
707 
IList&lt;T&gt; interface also has properties <a
708 
 href="main.htm#P:C5.IList%601.Underlying">Underlying</a>
709 
and <a href="main.htm#P:C5.IList%601.Offset">Offset</a> showing the
710 
base list of a
711 
view and the current site of a view.</p>
712 
<p>One can create a view on a view, but the new view will have the
713 
original base
714 
list as base. A view will be invalidated if an update operation is
715 
performed on
716 
the base list by any other means than through this particular view.</p>
717 
<p>The following code snippet shows a silly example of iterating over a
718 
list,
719 
doing an insertion each time certain combination of items are seen (the
720 
example
721 
iterates right to left and inserts 666 whenever two consecutive items
722 
have an
723 
odd difference):</p>
724 
<blockquote>
725 
  <p><code>IList&lt;int&gt; lst = ...;<br>
726 
IList&lt;int&gt; view = lst.CreateView(lst.Count-2, 2);<br>
727 
while (true) {<br>
728 
&nbsp;&nbsp;&nbsp; if ((view.Last - view.First) % 2 == 1)<br>
729 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; view.Insert(1, 666);<br>
730 
&nbsp;&nbsp;&nbsp; if (view.Offset == 0)<br>
731 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; break;<br>
732 
&nbsp;&nbsp;&nbsp; else<br>
733 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; view.Slide(-1,2);<br>
734 
}</code></p>
735 
</blockquote>
736 
<h2><a class="mozTocH2" name="mozTocId650306"></a>To work with
737 
persistent red-black trees</h2>
738 
<p>The search tree implementation in the library is based on node copy
739 
persistent red-black trees. The persistence is exposed in the <a
740 
 href="main.htm#M:C5.IPersistentSorted%601.Snapshot">Snapshot</a>
741 
method that can be considered a very fast and space-saving way of
742 
making a
743 
read-only clone of the tree. When using persistence, the space use of a
744 
red-black tree in this implementation is linear in the number of
745 
operations
746 
since the creation of the tree.</p>
747 
<p>One use of persistence could be to safely enumerate a tree
748 
interleaved with
749 
updates:</p>
750 
<blockquote>
751 
  <p><code>IPersistentSorted&lt;int&gt; tree = new TreeSet&lt;int&gt;();<br>
752 
tree.Add(5);<br>
753 
...<br>
754 
ISorted&lt;int&gt; snap = tree.Snapshot();<br>
755 
foreach (int i in snap)<br>
756 
&nbsp;&nbsp;&nbsp; tree.Add(i+7);</code></p>
757 
</blockquote>
758 
<p>The GUITester project of the complete library source code contains
759 
an
760 
interesting (standard) usage of persistent search trees to the
761 
geometric problem
762 
of constructing an efficient data structure for point location in a
763 
division of
764 
the plane given by a list of line segments.</p>
765 
<h2><a class="mozTocH2" name="mozTocId553609"></a>To implement new
766 
collection classes or subclass an existing one</h2>
767 
<p>All interface methods and properties of the collection classes
768 
implemented in
769 
the library are virtual and so it should be safe to subclass these
770 
classes. Some
771 
classes may have protected members if they are subclassed in the
772 
library itself.
773 
We refer to the detailed reference manuals and the library source for
774 
information on the protected members and their role in subclassing.</p>
775 
<p>There is a sequence of helper classes designed to be used as base
776 
classes of
777 
collection classes: <a href="main.htm#T:C5.EnumerableBase%601">EnumerableBase&lt;T&gt;</a>,
778 
<a href="main.htm#T:C5.CollectionValueBase%601">CollectionValueBase&lt;T&gt;</a>,
779 
<a href="main.htm#T:C5.CollectionBase%601">CollectionBase&lt;T&gt;</a>,
780 
<a href="main.htm#T:C5.SequencedBase%601">SequencedBase&lt;T&gt;</a>
781 
and <a href="main.htm#T:C5.ArrayBase%601">ArrayBase&lt;T&gt;</a>.
782 
Please see the reference manual and the library source code for
783 
documentation
784 
and examples.</p>
785 
<p>As for dictionaries, the DictionaryBase&lt;K,V&gt; class will
786 
construct a
787 
class implementing IDictionary&lt;K,V&gt; by simply plugging in a set
788 
implementation.</p>
789 
<h2><a class="mozTocH2" name="mozTocId753674"></a>To present a read
790 
only view of a collection</h2>
791 
<p>The library contains a long list of wrapper classes all with name
792 
starting
793 
with Guarded having the purpose of creating a read-only view of an
794 
existing
795 
collection. The wrapping is done by the constructors of the classes. If
796 
we want
797 
to give some code access to only lookup operations on a, say, list we
798 
can do as
799 
follows:</p>
800 
<blockquote>
801 
  <p><code>IList&lt;int&gt; lst;<br>
802 
...<br>
803 
IList&lt;int&gt; rolst = new GList&lt;int&gt;(lst);<br>
804 
OtherObject.dowork(rolst);</code></p>
805 
</blockquote>
806 
<p>Please see the reference manual for details on available wrapper
807 
classes.</p>
808 
<h1><a class="mozTocH1" name="mozTocId6619"></a><a name="datastructures">Collection
809 
classes by data structure/class</a></h1>
810 
<p>The following table&nbsp;shows the underlying data structure of the
811 
various collection classes.</p>
812 
<table border="1">
813 
  <tbody>
814 
    <tr>
815 
      <th>Data structure</th>
816 
      <th>Classes</th>
817 
      <th>Primary Interfaces</th>
818 
    </tr>
819 
    <tr>
820 
      <td>hash table</td>
821 
      <td>HashSet&lt;T&gt;</td>
822 
      <td> ICollection&lt;T&gt;</td>
823 
    </tr>
824 
    <tr>
825 
      <td>hash table</td>
826 
      <td>HashBag&lt;T&gt;</td>
827 
      <td> ICollection&lt;T&gt;</td>
828 
    </tr>
829 
    <tr>
830 
      <td>hash table</td>
831 
      <td>HashDictionary&lt;K,V&gt;</td>
832 
      <td>IDictionary&lt;K,V&gt;</td>
833 
    </tr>
834 
    <tr>
835 
      <td>linked list</td>
836 
      <td>LinkedList&lt;T&gt;</td>
837 
      <td>IList&lt;T&gt;</td>
838 
    </tr>
839 
    <tr>
840 
      <td>linked list with hash index</td>
841 
      <td>HashedLinkedList&lt;T&gt;</td>
842 
      <td>IList&lt;T&gt;</td>
843 
    </tr>
844 
    <tr>
845 
      <td>dynamic array</td>
846 
      <td>ArrayList&lt;T&gt;</td>
847 
      <td>IList&lt;T&gt;</td>
848 
    </tr>
849 
    <tr>
850 
      <td>dynamic array with hash index</td>
851 
      <td>HashedArrayList&lt;T&gt;</td>
852 
      <td>IList&lt;T&gt;</td>
853 
    </tr>
854 
    <tr>
855 
      <td>sorted dynamic array</td>
856 
      <td>SortedArray&lt;T&gt;</td>
857 
      <td>IIndexedSorted&lt;T&gt;</td>
858 
    </tr>
859 
    <tr>
860 
      <td>heap</td>
861 
      <td>IntervalHeap&lt;T&gt;</td>
862 
      <td>IPriorityQueue&lt;T&gt;</td>
863 
    </tr>
864 
    <tr>
865 
      <td>red-black search tree</td>
866 
      <td>TreeSet&lt;T&gt;</td>
867 
      <td>IIndexedSorted&lt;T&gt;, IPersistentSorted&lt;T&gt;</td>
868 
    </tr>
869 
    <tr>
870 
      <td>red-black search tree</td>
871 
      <td>TreeBag&lt;T&gt;</td>
872 
      <td>IIndexedSorted&lt;T&gt;, IPersistentSorted&lt;T&gt;</td>
873 
    </tr>
874 
    <tr>
875 
      <td>red-black search tree</td>
876 
      <td>TreeDictionary&lt;K,V&gt;</td>
877 
      <td>ISortedDictionary&lt;K,V&gt;</td>
878 
    </tr>
879 
  </tbody>
880 
</table>
881 
<br>
882 
<h1><a class="mozTocH1" name="mozTocId393559"></a>&lt;&gt;<a
883 
 name="planned"></a>Planned<span style="font-weight: bold;"> </span>architecture
884 
or interface changes
885 
for first release<br>
886 
</h1>
887 
<ol>
888 
  <li>Eliminate the use of our own generic equality/comparator types,
889 
C5.IComparer&lt;T&gt; and C5.IEqualityComparer&lt;T&gt; and use the new design of
890 
VS 2005 beta1 in the form of the combined
891 
System.Collections.Generic.IComparer&lt;T&gt;.</li>
892 
  <li>Vararg (params) constructors? (And IEnum do.)</li>
893 
  <li>Possibly extended use of "wildcard style" operations like
894 
AddAll&lt;U&gt;(IEnumerable&lt;U&gt; items)?</li>
895 
  <li>Make all collection classes clonable and serializable.</li>
896 
</ol>
897 
<h1><a class="mozTocH1" name="mozTocId336849"></a><a
898 
 name="PerformanceProper">Performance</a> details for proper collection
899 
classes</h1>
900 
<p>This section overviews the complexities of cc public methods and
901 
property
902 
accesses.</p>
903 
<p>In the table below, for lack of space we use the following numbers
904 
to
905 
identify collection classes:</p>
906 
<table border="1">
907 
  <tbody>
908 
    <tr>
909 
      <th>Class</th>
910 
      <th>Column</th>
911 
    </tr>
912 
    <tr>
913 
      <td>HashSet&lt;T&gt;</td>
914 
      <td>HS</td>
915 
    </tr>
916 
    <tr>
917 
      <td>HashBag&lt;T&gt;</td>
918 
      <td>HB</td>
919 
    </tr>
920 
    <tr>
921 
      <td>ArrayList&lt;T&gt;</td>
922 
      <td>AL</td>
923 
    </tr>
924 
    <tr>
925 
      <td>LinkedList&lt;T&gt;</td>
926 
      <td>LL</td>
927 
    </tr>
928 
    <tr>
929 
      <td>HashedArrayList&lt;T&gt;</td>
930 
      <td>HAL</td>
931 
    </tr>
932 
    <tr>
933 
      <td>HashedLinkedList&lt;T&gt;</td>
934 
      <td>HLL</td>
935 
    </tr>
936 
    <tr>
937 
      <td>TreeSet&lt;T&gt;</td>
938 
      <td>RBTS</td>
939 
    </tr>
940 
    <tr>
941 
      <td>TreeBag&lt;T&gt;</td>
942 
      <td>RBTB</td>
943 
    </tr>
944 
    <tr>
945 
      <td>SortedArray&lt;T&gt;</td>
946 
      <td>SA</td>
947 
    </tr>
948 
    <tr>
949 
      <td>IntervalHeap&lt;T&gt;</td>
950 
      <td>IH</td>
951 
    </tr>
952 
  </tbody>
953 
</table>
954 
<p>And the following special symbols:&nbsp;</p>
955 
<p>
956 
n size of collection,&nbsp;<br>
957 
m size of argument if collection-: not supported<br>
958 
*: means: suboptimal complexity (library is in error)<br>
959 
$: special at end: the operation is much faster at the start and/or end
960 
(end for
961 
array list, both for linked list)
962 
</p>
963 
<p>Note: we do not show return type&nbsp; or parameters for methods,
964 
just mark
965 
with ()<br>
966 
Note: we ignore time for reclaiming of internal array space (e.g. Clear)<br>
967 
User supplied operations like comparers or equalityComparers are assumed to be
968 
O(1)</p>
969 
<table border="1" height="2893" width="100%">
970 
  <tbody>
971 
    <tr>
972 
      <th height="23" width="9%">Member</th>
973 
      <th height="23" width="8%">HS</th>
974 
      <th height="23" width="8%">HB</th>
975 
      <th height="23" width="8%">AL</th>
976 
      <th height="23" width="8%">LL</th>
977 
      <th height="23" width="8%">HAL</th>
978 
      <th height="23" width="8%">HLL</th>
979 
      <th height="23" width="8%">RBTS</th>
980 
      <th height="23" width="8%">RBTB</th>
981 
      <th height="23" width="9%">SA</th>
982 
      <th height="23" width="9%">IH</th>
983 
    </tr>
984 
    <tr>
985 
      <td height="22" width="14%"><i><font color="#808080" size="2">&nbsp;IEnumerable&lt;T&gt;</font></i></td>
986 
      <td height="22" width="8%">&nbsp;&nbsp;</td>
987 
      <td height="22" width="8%">&nbsp;</td>
988 
      <td height="22" width="8%">&nbsp;</td>
989 
      <td height="22" width="8%">&nbsp;</td>
990 
      <td height="22" width="8%">&nbsp;</td>
991 
      <td height="22" width="8%">&nbsp;</td>
992 
      <td height="22" width="8%">&nbsp;</td>
993 
      <td height="22" width="8%">&nbsp;</td>
994 
      <td height="22" width="9%">&nbsp;</td>
995 
      <td height="22" width="9%">&nbsp;</td>
996 
    </tr>
997 
    <tr>
998 
      <td height="22" width="9%"><font size="2">GetEnumerator()</font></td>
999 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1000 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1001 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1002 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1003 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1004 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1005 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1006 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1007 
      <td height="22" width="9%"><font size="2">O(1)</font></td>
1008 
      <td height="22" width="9%"><font size="2">O(1)</font></td>
1009 
    </tr>
1010 
    <tr>
1011 
      <td height="22" width="14%"><i><font color="#808080" size="2">IDirectedEnumerable&lt;T&gt;</font></i></td>
1012 
      <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
1013 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1014 
 size="2">HB</font></i></td>
1015 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1016 
 size="2">AL</font></i></td>
1017 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1018 
 size="2">LL</font></i></td>
1019 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1020 
 size="2">HAL</font></i></td>
1021 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1022 
 size="2">HLL</font></i></td>
1023 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1024 
 size="2">RBTS</font></i></td>
1025 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1026 
 size="2">RBTB</font></i></td>
1027 
      <td align="center" height="22" width="9%"><i><font color="#808080"
1028 
 size="2">SA</font></i></td>
1029 
      <td align="center" height="22" width="9%"><i><font color="#808080"
1030 
 size="2">IH</font></i></td>
1031 
    </tr>
1032 
    <tr>
1033 
      <td height="22" width="18%"><font size="2">Direction</font></td>
1034 
      <td height="22" width="8%"><font size="2">-</font></td>
1035 
      <td height="22" width="8%"><font size="2">-</font></td>
1036 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1037 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1038 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1039 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1040 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1041 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1042 
      <td height="22" width="9%"><font size="2">O(1)</font></td>
1043 
      <td height="22" width="9%"><font size="2">-</font></td>
1044 
    </tr>
1045 
    <tr>
1046 
      <td height="22" width="18%"><font size="2">Backwards()</font></td>
1047 
      <td height="22" width="8%"><font size="2">-</font></td>
1048 
      <td height="22" width="8%"><font size="2">-</font></td>
1049 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1050 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1051 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1052 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1053 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1054 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1055 
      <td height="22" width="9%"><font size="2">O(1)</font></td>
1056 
      <td height="22" width="9%"><font size="2">-</font></td>
1057 
    </tr>
1058 
    <tr>
1059 
      <td height="22" width="14%"><i><font color="#808080" size="2">ICollectionValue&lt;T&gt;</font></i></td>
1060 
      <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
1061 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1062 
 size="2">HB</font></i></td>
1063 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1064 
 size="2">AL</font></i></td>
1065 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1066 
 size="2">LL</font></i></td>
1067 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1068 
 size="2">HAL</font></i></td>
1069 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1070 
 size="2">HLL</font></i></td>
1071 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1072 
 size="2">RBTS</font></i></td>
1073 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1074 
 size="2">RBTB</font></i></td>
1075 
      <td align="center" height="22" width="9%"><i><font color="#808080"
1076 
 size="2">SA</font></i></td>
1077 
      <td align="center" height="22" width="9%"><i><font color="#808080"
1078 
 size="2">IH</font></i></td>
1079 
    </tr>
1080 
    <tr>
1081 
      <td height="22" width="9%"><font size="2">Count</font></td>
1082 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1083 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1084 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1085 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1086 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1087 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1088 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1089 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1090 
      <td height="22" width="9%"><font size="2">O(1)</font></td>
1091 
      <td height="22" width="9%"><font size="2">O(1)</font></td>
1092 
    </tr>
1093 
    <tr>
1094 
      <td height="22" width="18%"><font size="2">CopyTo</font></td>
1095 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1096 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1097 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1098 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1099 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1100 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1101 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1102 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1103 
      <td height="22" width="9%"><font size="2">O(n)</font></td>
1104 
      <td height="22" width="9%"><font size="2">O(n)</font></td>
1105 
    </tr>
1106 
    <tr>
1107 
      <td height="22" width="9%"><font size="2">ToArray</font></td>
1108 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1109 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1110 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1111 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1112 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1113 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1114 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1115 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1116 
      <td height="22" width="9%"><font size="2">O(n)</font></td>
1117 
      <td height="22" width="9%"><font size="2">-</font></td>
1118 
    </tr>
1119 
    <tr>
1120 
      <td height="22" width="9%"><font size="2">Apply()</font></td>
1121 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1122 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1123 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1124 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1125 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1126 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1127 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1128 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1129 
      <td height="22" width="9%"><font size="2">O(n)</font></td>
1130 
      <td height="22" width="9%"><font size="2">O(n)</font></td>
1131 
    </tr>
1132 
    <tr>
1133 
      <td height="22" width="9%"><font size="2">Exists()</font></td>
1134 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1135 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1136 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1137 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1138 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1139 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1140 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1141 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1142 
      <td height="22" width="9%"><font size="2">O(n)</font></td>
1143 
      <td height="22" width="9%"><font size="2">O(n)</font></td>
1144 
    </tr>
1145 
    <tr>
1146 
      <td height="22" width="9%"><font size="2">All()</font></td>
1147 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1148 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1149 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1150 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1151 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1152 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1153 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1154 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1155 
      <td height="22" width="9%"><font size="2">O(n)</font></td>
1156 
      <td height="22" width="9%"><font size="2">O(n)</font></td>
1157 
    </tr>
1158 
    <tr>
1159 
      <td height="22" width="14%"><i><font color="#808080" size="2">IDirectedCollectionValue&lt;T&gt;</font></i></td>
1160 
      <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
1161 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1162 
 size="2">HB</font></i></td>
1163 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1164 
 size="2">AL</font></i></td>
1165 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1166 
 size="2">LL</font></i></td>
1167 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1168 
 size="2">HAL</font></i></td>
1169 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1170 
 size="2">HLL</font></i></td>
1171 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1172 
 size="2">RBTS</font></i></td>
1173 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1174 
 size="2">RBTB</font></i></td>
1175 
      <td align="center" height="22" width="9%"><i><font color="#808080"
1176 
 size="2">SA</font></i></td>
1177 
      <td align="center" height="22" width="9%"><i><font color="#808080"
1178 
 size="2">IH</font></i></td>
1179 
    </tr>
1180 
    <tr>
1181 
      <td height="22" width="18%"><font size="2">Backwards()</font></td>
1182 
      <td height="22" width="8%"><font size="2">-</font></td>
1183 
      <td height="22" width="8%"><font size="2">-</font></td>
1184 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1185 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1186 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1187 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1188 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1189 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1190 
      <td height="22" width="9%"><font size="2">O(1)</font></td>
1191 
      <td height="22" width="9%"><font size="2">-</font></td>
1192 
    </tr>
1193 
    <tr>
1194 
      <td height="22" width="13%"><i><font color="#808080" size="2">IExtensible&lt;T&gt;</font></i></td>
1195 
      <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
1196 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1197 
 size="2">HB</font></i></td>
1198 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1199 
 size="2">AL</font></i></td>
1200 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1201 
 size="2">LL</font></i></td>
1202 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1203 
 size="2">HAL</font></i></td>
1204 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1205 
 size="2">HLL</font></i></td>
1206 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1207 
 size="2">RBTS</font></i></td>
1208 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1209 
 size="2">RBTB</font></i></td>
1210 
      <td align="center" height="22" width="9%"><i><font color="#808080"
1211 
 size="2">SA</font></i></td>
1212 
      <td align="center" height="22" width="9%"><i><font color="#808080"
1213 
 size="2">IH</font></i></td>
1214 
    </tr>
1215 
    <tr>
1216 
      <td height="22" width="9%"><font size="2">AllowsDuplicates</font></td>
1217 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1218 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1219 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1220 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1221 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1222 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1223 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1224 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1225 
      <td height="22" width="9%"><font size="2">O(1)</font></td>
1226 
      <td height="22" width="9%"><font size="2">O(1)</font></td>
1227 
    </tr>
1228 
    <tr>
1229 
      <td height="22" width="9%"><font size="2">SyncRoot</font></td>
1230 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1231 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1232 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1233 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1234 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1235 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1236 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1237 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1238 
      <td height="22" width="9%"><font size="2">O(1)</font></td>
1239 
      <td height="22" width="9%"><font size="2">O(1)</font></td>
1240 
    </tr>
1241 
    <tr>
1242 
      <td height="22" width="9%"><font size="2">IsEmpty</font></td>
1243 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1244 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1245 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1246 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1247 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1248 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1249 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1250 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1251 
      <td height="22" width="9%"><font size="2">O(1)</font></td>
1252 
      <td height="22" width="9%"><font size="2">O(1)</font></td>
1253 
    </tr>
1254 
    <tr>
1255 
      <td height="22" width="9%"><font size="2">Add</font></td>
1256 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1257 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1258 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1259 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1260 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1261 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1262 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
1263 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
1264 
      <td height="22" width="9%"><font size="2">O(n)</font></td>
1265 
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
1266 
    </tr>
1267 
    <tr>
1268 
      <td height="22" width="9%"><font size="2">AddAll</font></td>
1269 
      <td height="22" width="8%"><font size="2">O(m)</font></td>
1270 
      <td height="22" width="8%"><font size="2">O(m)</font></td>
1271 
      <td height="22" width="8%"><font size="2">O(m)</font></td>
1272 
      <td height="22" width="8%"><font size="2">O(m)</font></td>
1273 
      <td height="22" width="8%"><font size="2">O(m)</font></td>
1274 
      <td height="22" width="8%"><font size="2">O(m)</font></td>
1275 
      <td height="22" width="8%"><font size="2">O(mlog n)</font></td>
1276 
      <td height="22" width="8%"><font size="2">O(mlog n)</font></td>
1277 
      <td height="22" width="9%"><font size="2">O(mlog n)</font></td>
1278 
      <td height="22" width="9%"><font size="2">??</font></td>
1279 
    </tr>
1280 
    <tr>
1281 
      <td height="22" width="14%"><i><font color="#808080" size="2">ICollection&lt;T&gt;</font></i></td>
1282 
      <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
1283 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1284 
 size="2">HB</font></i></td>
1285 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1286 
 size="2">AL</font></i></td>
1287 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1288 
 size="2">LL</font></i></td>
1289 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1290 
 size="2">HAL</font></i></td>
1291 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1292 
 size="2">HLL</font></i></td>
1293 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1294 
 size="2">RBTS</font></i></td>
1295 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1296 
 size="2">RBTB</font></i></td>
1297 
      <td align="center" height="22" width="9%"><i><font color="#808080"
1298 
 size="2">SA</font></i></td>
1299 
      <td align="center" height="22" width="9%"><i><font color="#808080"
1300 
 size="2">IH</font></i></td>
1301 
    </tr>
1302 
    <tr>
1303 
      <td height="22" width="9%"><font size="2">IsReadOnly</font></td>
1304 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1305 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1306 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1307 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1308 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1309 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1310 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1311 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1312 
      <td height="22" width="9%"><font size="2">O(1)</font></td>
1313 
      <td height="22" width="9%"><font size="2">-</font></td>
1314 
    </tr>
1315 
    <tr>
1316 
      <td height="22" width="9%"><font size="2">ContainsSpeed</font></td>
1317 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1318 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1319 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1320 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1321 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1322 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1323 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1324 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1325 
      <td height="22" width="9%"><font size="2">O(1)</font></td>
1326 
      <td height="22" width="9%"><font size="2">-</font></td>
1327 
    </tr>
1328 
    <tr>
1329 
      <td height="22" width="9%"><font size="2">GetHashCode</font></td>
1330 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1331 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1332 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1333 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1334 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1335 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1336 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1337 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1338 
      <td height="22" width="9%"><font size="2">O(1)</font></td>
1339 
      <td height="22" width="9%"><font size="2">-</font></td>
1340 
    </tr>
1341 
    <tr>
1342 
      <td height="22" width="9%"><font size="2">Equals</font></td>
1343 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1344 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1345 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1346 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1347 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1348 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1349 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1350 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1351 
      <td height="22" width="9%"><font size="2">O(1)</font></td>
1352 
      <td height="22" width="9%"><font size="2">-</font></td>
1353 
    </tr>
1354 
    <tr>
1355 
      <td height="22" width="9%"><font size="2">Contains</font></td>
1356 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1357 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1358 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1359 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1360 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1361 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1362 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
1363 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
1364 
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
1365 
      <td height="22" width="9%"><font size="2">-</font></td>
1366 
    </tr>
1367 
    <tr>
1368 
      <td height="22" width="9%"><font size="2">ContainsCount</font></td>
1369 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1370 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1371 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1372 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1373 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1374 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1375 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
1376 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
1377 
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
1378 
      <td height="22" width="9%"><font size="2">-</font></td>
1379 
    </tr>
1380 
    <tr>
1381 
      <td height="22" width="9%"><font size="2">ContainsAll</font></td>
1382 
      <td height="22" width="8%"><font size="2">O(m)</font></td>
1383 
      <td height="22" width="8%"><font size="2">O(m)</font></td>
1384 
      <td height="22" width="8%"><font size="2">O(mn)*</font></td>
1385 
      <td height="22" width="8%"><font size="2">O(mn)*</font></td>
1386 
      <td height="22" width="8%"><font size="2">O(m)</font></td>
1387 
      <td height="22" width="8%"><font size="2">O(m)</font></td>
1388 
      <td height="22" width="8%"><font size="2">O(m logn)</font></td>
1389 
      <td height="22" width="8%"><font size="2">O(m logn)</font></td>
1390 
      <td height="22" width="9%"><font size="2">O(m logn)</font></td>
1391 
      <td height="22" width="9%"><font size="2">-</font></td>
1392 
    </tr>
1393 
    <tr>
1394 
      <td height="22" width="9%"><font size="2">Find</font></td>
1395 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1396 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1397 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1398 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1399 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1400 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1401 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
1402 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
1403 
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
1404 
      <td height="22" width="9%"><font size="2">-</font></td>
1405 
    </tr>
1406 
    <tr>
1407 
      <td height="22" width="9%"><font size="2">FindOrAdd</font></td>
1408 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1409 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1410 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1411 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1412 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1413 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1414 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
1415 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
1416 
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
1417 
      <td height="22" width="9%"><font size="2">-</font></td>
1418 
    </tr>
1419 
    <tr>
1420 
      <td height="22" width="9%"><font size="2">Update</font></td>
1421 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1422 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1423 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1424 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1425 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1426 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1427 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
1428 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
1429 
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
1430 
      <td height="22" width="9%"><font size="2">-</font></td>
1431 
    </tr>
1432 
    <tr>
1433 
      <td height="22" width="9%"><font size="2">UpdateOrAdd</font></td>
1434 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1435 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1436 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1437 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1438 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1439 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1440 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
1441 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
1442 
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
1443 
      <td height="22" width="9%"><font size="2">-</font></td>
1444 
    </tr>
1445 
    <tr>
1446 
      <td height="22" width="9%"><font size="2">Remove</font></td>
1447 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1448 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1449 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1450 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1451 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1452 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1453 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
1454 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
1455 
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
1456 
      <td height="22" width="9%"><font size="2">-</font></td>
1457 
    </tr>
1458 
    <tr>
1459 
      <td height="22" width="9%"><font size="2">RemoveWithReturn</font></td>
1460 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1461 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1462 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1463 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1464 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1465 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1466 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
1467 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
1468 
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
1469 
      <td height="22" width="9%"><font size="2">-</font></td>
1470 
    </tr>
1471 
    <tr>
1472 
      <td height="22" width="9%"><font size="2">RemoveAllCopies</font></td>
1473 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1474 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1475 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1476 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1477 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1478 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1479 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
1480 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
1481 
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
1482 
      <td height="22" width="9%"><font size="2">-</font></td>
1483 
    </tr>
1484 
    <tr>
1485 
      <td height="22" width="9%"><font size="2">RemoveAll</font></td>
1486 
      <td height="22" width="8%"><font size="2">O(m)</font></td>
1487 
      <td height="22" width="8%"><font size="2">O(m)</font></td>
1488 
      <td height="22" width="8%"><font size="2">O(mn)*</font></td>
1489 
      <td height="22" width="8%"><font size="2">O(mn)*</font></td>
1490 
      <td height="22" width="8%"><font size="2">O(m+n)</font></td>
1491 
      <td height="22" width="8%"><font size="2">O(m)</font></td>
1492 
      <td height="22" width="8%"><font size="2">O(m logn)</font></td>
1493 
      <td height="22" width="8%"><font size="2">O(m logn)</font></td>
1494 
      <td height="22" width="9%"><font size="2">O(m logn)</font></td>
1495 
      <td height="22" width="9%"><font size="2">-</font></td>
1496 
    </tr>
1497 
    <tr>
1498 
      <td height="22" width="9%"><font size="2">Clear</font></td>
1499 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1500 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1501 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1502 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1503 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1504 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1505 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1506 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1507 
      <td height="22" width="9%"><font size="2">O(1)</font></td>
1508 
      <td height="22" width="9%"><font size="2">-</font></td>
1509 
    </tr>
1510 
    <tr>
1511 
      <td height="22" width="9%"><font size="2">RetainAll</font></td>
1512 
      <td height="22" width="8%"><font size="2">O(m)?</font></td>
1513 
      <td height="22" width="8%"><font size="2">O(m)</font></td>
1514 
      <td height="22" width="8%"><font size="2">O(mn)*</font></td>
1515 
      <td height="22" width="8%"><font size="2">O(mn)*</font></td>
1516 
      <td height="22" width="8%"><font size="2">O(m+n)</font></td>
1517 
      <td height="22" width="8%"><font size="2">O(m)</font></td>
1518 
      <td height="22" width="8%"><font size="2">O(m logn)</font></td>
1519 
      <td height="22" width="8%"><font size="2">O(m logn)</font></td>
1520 
      <td height="22" width="9%"><font size="2">O(m logn)</font></td>
1521 
      <td height="22" width="9%"><font size="2">-</font></td>
1522 
    </tr>
1523 
    <tr>
1524 
      <td height="22" width="14%"><i><font color="#808080" size="2">ISequenced&lt;T&gt;</font></i></td>
1525 
      <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
1526 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1527 
 size="2">HB</font></i></td>
1528 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1529 
 size="2">AL</font></i></td>
1530 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1531 
 size="2">LL</font></i></td>
1532 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1533 
 size="2">HAL</font></i></td>
1534 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1535 
 size="2">HLL</font></i></td>
1536 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1537 
 size="2">RBTS</font></i></td>
1538 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1539 
 size="2">RBTB</font></i></td>
1540 
      <td align="center" height="22" width="9%"><i><font color="#808080"
1541 
 size="2">SA</font></i></td>
1542 
      <td align="center" height="22" width="9%"><i><font color="#808080"
1543 
 size="2">IH</font></i></td>
1544 
    </tr>
1545 
    <tr>
1546 
      <td height="22" width="9%"><font size="2">GetHashCode</font></td>
1547 
      <td height="22" width="8%"><font size="2">-</font></td>
1548 
      <td height="22" width="8%"><font size="2">-</font></td>
1549 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1550 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1551 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1552 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1553 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1554 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1555 
      <td height="22" width="9%"><font size="2">O(1)</font></td>
1556 
      <td height="22" width="9%"><font size="2">-</font></td>
1557 
    </tr>
1558 
    <tr>
1559 
      <td height="22" width="9%"><font size="2">Equals</font></td>
1560 
      <td height="22" width="8%"><font size="2">-</font></td>
1561 
      <td height="22" width="8%"><font size="2">-</font></td>
1562 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1563 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1564 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1565 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1566 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1567 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1568 
      <td height="22" width="9%"><font size="2">O(1)</font></td>
1569 
      <td height="22" width="9%"><font size="2">-</font></td>
1570 
    </tr>
1571 
    <tr>
1572 
      <td height="22" width="14%"><i><font color="#808080" size="2">IIndexed&lt;T&gt;</font></i></td>
1573 
      <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
1574 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1575 
 size="2">HB</font></i></td>
1576 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1577 
 size="2">AL</font></i></td>
1578 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1579 
 size="2">LL</font></i></td>
1580 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1581 
 size="2">HAL</font></i></td>
1582 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1583 
 size="2">HLL</font></i></td>
1584 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1585 
 size="2">RBTS</font></i></td>
1586 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1587 
 size="2">RBTB</font></i></td>
1588 
      <td align="center" height="22" width="9%"><i><font color="#808080"
1589 
 size="2">SA</font></i></td>
1590 
      <td align="center" height="22" width="9%"><i><font color="#808080"
1591 
 size="2">IH</font></i></td>
1592 
    </tr>
1593 
    <tr>
1594 
      <td height="22" width="9%"><font size="2">this[i]</font></td>
1595 
      <td height="22" width="8%"><font size="2">-</font></td>
1596 
      <td height="22" width="8%"><font size="2">-</font></td>
1597 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1598 
      <td height="22" width="8%"><font size="2">O(n)$</font></td>
1599 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1600 
      <td height="22" width="8%"><font size="2">O(n)$</font></td>
1601 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
1602 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
1603 
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
1604 
      <td height="22" width="9%"><font size="2">-</font></td>
1605 
    </tr>
1606 
    <tr>
1607 
      <td height="22" width="9%"><font size="2">this[start,end]</font></td>
1608 
      <td height="22" width="8%"><font size="2">-</font></td>
1609 
      <td height="22" width="8%"><font size="2">-</font></td>
1610 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1611 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1612 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1613 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1614 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
1615 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
1616 
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
1617 
      <td height="22" width="9%"><font size="2">-</font></td>
1618 
    </tr>
1619 
    <tr>
1620 
      <td height="22" width="9%"><font size="2">IndexOf()</font></td>
1621 
      <td height="22" width="8%"><font size="2">-</font></td>
1622 
      <td height="22" width="8%"><font size="2">-</font></td>
1623 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1624 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1625 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1626 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1627 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
1628 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
1629 
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
1630 
      <td height="22" width="9%"><font size="2">-</font></td>
1631 
    </tr>
1632 
    <tr>
1633 
      <td height="22" width="9%"><font size="2">LastIndexOf()</font></td>
1634 
      <td height="22" width="8%"><font size="2">-</font></td>
1635 
      <td height="22" width="8%"><font size="2">-</font></td>
1636 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1637 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1638 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1639 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1640 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
1641 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
1642 
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
1643 
      <td height="22" width="9%"><font size="2">-</font></td>
1644 
    </tr>
1645 
    <tr>
1646 
      <td height="22" width="9%"><font size="2">RemoveAt</font></td>
1647 
      <td height="22" width="8%"><font size="2">-</font></td>
1648 
      <td height="22" width="8%"><font size="2">-</font></td>
1649 
      <td height="22" width="8%"><font size="2">O(n)$</font></td>
1650 
      <td height="22" width="8%"><font size="2">O(n)$</font></td>
1651 
      <td height="22" width="8%"><font size="2">O(n)$</font></td>
1652 
      <td height="22" width="8%"><font size="2">O(n)$</font></td>
1653 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
1654 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
1655 
      <td height="22" width="9%"><font size="2">O(n)</font></td>
1656 
      <td height="22" width="9%"><font size="2">-</font></td>
1657 
    </tr>
1658 
    <tr>
1659 
      <td height="22" width="9%"><font size="2">RemoveInterval</font></td>
1660 
      <td height="22" width="8%"><font size="2">-</font></td>
1661 
      <td height="22" width="8%"><font size="2">-</font></td>
1662 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1663 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1664 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1665 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1666 
      <td height="22" width="8%"><font size="2">O(n log n)*</font></td>
1667 
      <td height="22" width="8%"><font size="2">O(n log n)*</font></td>
1668 
      <td height="22" width="9%"><font size="2">O(n)</font></td>
1669 
      <td height="22" width="9%"><font size="2">-</font></td>
1670 
    </tr>
1671 
    <tr>
1672 
      <td height="22" width="14%"><i><font color="#808080" size="2">IList&lt;T&gt;</font></i></td>
1673 
      <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
1674 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1675 
 size="2">HB</font></i></td>
1676 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1677 
 size="2">AL</font></i></td>
1678 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1679 
 size="2">LL</font></i></td>
1680 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1681 
 size="2">HAL</font></i></td>
1682 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1683 
 size="2">HLL</font></i></td>
1684 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1685 
 size="2">RBTS</font></i></td>
1686 
      <td align="center" height="22" width="8%"><i><font color="#808080"
1687 
 size="2">RBTB</font></i></td>
1688 
      <td align="center" height="22" width="9%"><i><font color="#808080"
1689 
 size="2">SA</font></i></td>
1690 
      <td align="center" height="22" width="9%"><i><font color="#808080"
1691 
 size="2">IH</font></i></td>
1692 
    </tr>
1693 
    <tr>
1694 
      <td height="22" width="9%"><font size="2">First</font></td>
1695 
      <td height="22" width="8%"><font size="2">-</font></td>
1696 
      <td height="22" width="8%"><font size="2">-</font></td>
1697 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1698 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1699 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1700 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1701 
      <td height="22" width="8%"><font size="2">-</font></td>
1702 
      <td height="22" width="8%"><font size="2">-</font></td>
1703 
      <td height="22" width="9%"><font size="2">-</font></td>
1704 
      <td height="22" width="9%"><font size="2">-</font></td>
1705 
    </tr>
1706 
    <tr>
1707 
      <td height="22" width="9%"><font size="2">Last</font></td>
1708 
      <td height="22" width="8%"><font size="2">-</font></td>
1709 
      <td height="22" width="8%"><font size="2">-</font></td>
1710 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1711 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1712 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1713 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1714 
      <td height="22" width="8%"><font size="2">-</font></td>
1715 
      <td height="22" width="8%"><font size="2">-</font></td>
1716 
      <td height="22" width="9%"><font size="2">-</font></td>
1717 
      <td height="22" width="9%"><font size="2">-</font></td>
1718 
    </tr>
1719 
    <tr>
1720 
      <td height="22" width="9%"><font size="2">FIFO</font></td>
1721 
      <td height="22" width="8%"><font size="2">-</font></td>
1722 
      <td height="22" width="8%"><font size="2">-</font></td>
1723 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1724 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1725 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1726 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1727 
      <td height="22" width="8%"><font size="2">-</font></td>
1728 
      <td height="22" width="8%"><font size="2">-</font></td>
1729 
      <td height="22" width="9%"><font size="2">-</font></td>
1730 
      <td height="22" width="9%"><font size="2">-</font></td>
1731 
    </tr>
1732 
    <tr>
1733 
      <td height="22" width="9%"><font size="2">this[i]</font></td>
1734 
      <td height="22" width="8%"><font size="2">-</font></td>
1735 
      <td height="22" width="8%"><font size="2">-</font></td>
1736 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1737 
      <td height="22" width="8%"><font size="2">O(n)$</font></td>
1738 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1739 
      <td height="22" width="8%"><font size="2">O(n)$</font></td>
1740 
      <td height="22" width="8%"><font size="2">-</font></td>
1741 
      <td height="22" width="8%"><font size="2">-</font></td>
1742 
      <td height="22" width="9%"><font size="2">-</font></td>
1743 
      <td height="22" width="9%"><font size="2">-</font></td>
1744 
    </tr>
1745 
    <tr>
1746 
      <td height="22" width="9%"><font size="2">Base</font></td>
1747 
      <td height="22" width="8%"><font size="2">-</font></td>
1748 
      <td height="22" width="8%"><font size="2">-</font></td>
1749 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1750 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1751 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1752 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1753 
      <td height="22" width="8%"><font size="2">-</font></td>
1754 
      <td height="22" width="8%"><font size="2">-</font></td>
1755 
      <td height="22" width="9%"><font size="2">-</font></td>
1756 
      <td height="22" width="9%"><font size="2">-</font></td>
1757 
    </tr>
1758 
    <tr>
1759 
      <td height="22" width="9%"><font size="2">Offset</font></td>
1760 
      <td height="22" width="8%"><font size="2">-</font></td>
1761 
      <td height="22" width="8%"><font size="2">-</font></td>
1762 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1763 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1764 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1765 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1766 
      <td height="22" width="8%"><font size="2">-</font></td>
1767 
      <td height="22" width="8%"><font size="2">-</font></td>
1768 
      <td height="22" width="9%"><font size="2">-</font></td>
1769 
      <td height="22" width="9%"><font size="2">-</font></td>
1770 
    </tr>
1771 
    <tr>
1772 
      <td height="22" width="9%"><font size="2">Map()</font></td>
1773 
      <td height="22" width="8%"><font size="2">-</font></td>
1774 
      <td height="22" width="8%"><font size="2">-</font></td>
1775 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1776 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1777 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1778 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1779 
      <td height="22" width="8%"><font size="2">-</font></td>
1780 
      <td height="22" width="8%"><font size="2">-</font></td>
1781 
      <td height="22" width="9%"><font size="2">-</font></td>
1782 
      <td height="22" width="9%"><font size="2">-</font></td>
1783 
    </tr>
1784 
    <tr>
1785 
      <td height="22" width="9%"><font size="2">Insert()</font></td>
1786 
      <td height="22" width="8%"><font size="2">-</font></td>
1787 
      <td height="22" width="8%"><font size="2">-</font></td>
1788 
      <td height="22" width="8%"><font size="2">O(n)$</font></td>
1789 
      <td height="22" width="8%"><font size="2">O(n)$</font></td>
1790 
      <td height="22" width="8%"><font size="2">O(n)$</font></td>
1791 
      <td height="22" width="8%"><font size="2">O(n)$</font></td>
1792 
      <td height="22" width="8%"><font size="2">-</font></td>
1793 
      <td height="22" width="8%"><font size="2">-</font></td>
1794 
      <td height="22" width="9%"><font size="2">-</font></td>
1795 
      <td height="22" width="9%"><font size="2">-</font></td>
1796 
    </tr>
1797 
    <tr>
1798 
      <td height="22" width="9%"><font size="2">InsertFirst()</font></td>
1799 
      <td height="22" width="8%"><font size="2">-</font></td>
1800 
      <td height="22" width="8%"><font size="2">-</font></td>
1801 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1802 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1803 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1804 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1805 
      <td height="22" width="8%"><font size="2">-</font></td>
1806 
      <td height="22" width="8%"><font size="2">-</font></td>
1807 
      <td height="22" width="9%"><font size="2">-</font></td>
1808 
      <td height="22" width="9%"><font size="2">-</font></td>
1809 
    </tr>
1810 
    <tr>
1811 
      <td height="22" width="9%"><font size="2">InsertLast()</font></td>
1812 
      <td height="22" width="8%"><font size="2">-</font></td>
1813 
      <td height="22" width="8%"><font size="2">-</font></td>
1814 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1815 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1816 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1817 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1818 
      <td height="22" width="8%"><font size="2">-</font></td>
1819 
      <td height="22" width="8%"><font size="2">-</font></td>
1820 
      <td height="22" width="9%"><font size="2">-</font></td>
1821 
      <td height="22" width="9%"><font size="2">-</font></td>
1822 
    </tr>
1823 
    <tr>
1824 
      <td height="22" width="9%"><font size="2">InsertBefore()</font></td>
1825 
      <td height="22" width="8%"><font size="2">-</font></td>
1826 
      <td height="22" width="8%"><font size="2">-</font></td>
1827 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1828 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1829 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1830 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1831 
      <td height="22" width="8%"><font size="2">-</font></td>
1832 
      <td height="22" width="8%"><font size="2">-</font></td>
1833 
      <td height="22" width="9%"><font size="2">-</font></td>
1834 
      <td height="22" width="9%"><font size="2">-</font></td>
1835 
    </tr>
1836 
    <tr>
1837 
      <td height="22" width="9%"><font size="2">InsertAfter()</font></td>
1838 
      <td height="22" width="8%"><font size="2">-</font></td>
1839 
      <td height="22" width="8%"><font size="2">-</font></td>
1840 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1841 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1842 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1843 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1844 
      <td height="22" width="8%"><font size="2">-</font></td>
1845 
      <td height="22" width="8%"><font size="2">-</font></td>
1846 
      <td height="22" width="9%"><font size="2">-</font></td>
1847 
      <td height="22" width="9%"><font size="2">-</font></td>
1848 
    </tr>
1849 
    <tr>
1850 
      <td height="22" width="9%"><font size="2">InsertAll()</font></td>
1851 
      <td height="22" width="8%"><font size="2">-</font></td>
1852 
      <td height="22" width="8%"><font size="2">-</font></td>
1853 
      <td height="22" width="8%"><font size="2">O(m+n)</font></td>
1854 
      <td height="22" width="8%"><font size="2">O(m+n)</font></td>
1855 
      <td height="22" width="8%"><font size="2">O(m+n)</font></td>
1856 
      <td height="22" width="8%"><font size="2">O(m+n)</font></td>
1857 
      <td height="22" width="8%"><font size="2">-</font></td>
1858 
      <td height="22" width="8%"><font size="2">-</font></td>
1859 
      <td height="22" width="9%"><font size="2">-</font></td>
1860 
      <td height="22" width="9%"><font size="2">-</font></td>
1861 
    </tr>
1862 
    <tr>
1863 
      <td height="22" width="9%"><font size="2">FindAll()</font></td>
1864 
      <td height="22" width="8%"><font size="2">-</font></td>
1865 
      <td height="22" width="8%"><font size="2">-</font></td>
1866 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1867 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1868 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1869 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1870 
      <td height="22" width="8%"><font size="2">-</font></td>
1871 
      <td height="22" width="8%"><font size="2">-</font></td>
1872 
      <td height="22" width="9%"><font size="2">-</font></td>
1873 
      <td height="22" width="9%"><font size="2">-</font></td>
1874 
    </tr>
1875 
    <tr>
1876 
      <td height="22" width="9%"><font size="2">Remove()</font></td>
1877 
      <td height="22" width="8%"><font size="2">-</font></td>
1878 
      <td height="22" width="8%"><font size="2">-</font></td>
1879 
      <td height="22" width="8%"><font size="2">O(n)$</font></td>
1880 
      <td height="22" width="8%"><font size="2">(1)</font></td>
1881 
      <td height="22" width="8%"><font size="2">O(n)$</font></td>
1882 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1883 
      <td height="22" width="8%"><font size="2">-</font></td>
1884 
      <td height="22" width="8%"><font size="2">-</font></td>
1885 
      <td height="22" width="9%"><font size="2">-</font></td>
1886 
      <td height="22" width="9%"><font size="2">-</font></td>
1887 
    </tr>
1888 
    <tr>
1889 
      <td height="22" width="9%"><font size="2">RemoveFirst()</font></td>
1890 
      <td height="22" width="8%"><font size="2">-</font></td>
1891 
      <td height="22" width="8%"><font size="2">-</font></td>
1892 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1893 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1894 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1895 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1896 
      <td height="22" width="8%"><font size="2">-</font></td>
1897 
      <td height="22" width="8%"><font size="2">-</font></td>
1898 
      <td height="22" width="9%"><font size="2">-</font></td>
1899 
      <td height="22" width="9%"><font size="2">-</font></td>
1900 
    </tr>
1901 
    <tr>
1902 
      <td height="22" width="9%"><font size="2">RemoveLast()</font></td>
1903 
      <td height="22" width="8%"><font size="2">-</font></td>
1904 
      <td height="22" width="8%"><font size="2">-</font></td>
1905 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1906 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1907 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1908 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1909 
      <td height="22" width="8%"><font size="2">-</font></td>
1910 
      <td height="22" width="8%"><font size="2">-</font></td>
1911 
      <td height="22" width="9%"><font size="2">-</font></td>
1912 
      <td height="22" width="9%"><font size="2">-</font></td>
1913 
    </tr>
1914 
    <tr>
1915 
      <td height="22" width="9%"><font size="2">View()</font></td>
1916 
      <td height="22" width="8%"><font size="2">-</font></td>
1917 
      <td height="22" width="8%"><font size="2">-</font></td>
1918 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1919 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1920 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
1921 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1922 
      <td height="22" width="8%"><font size="2">-</font></td>
1923 
      <td height="22" width="8%"><font size="2">-</font></td>
1924 
      <td height="22" width="9%"><font size="2">-</font></td>
1925 
      <td height="22" width="9%"><font size="2">-</font></td>
1926 
    </tr>
1927 
    <tr>
1928 
      <td height="22" width="9%"><font size="2">Slide() (amount: d)</font></td>
1929 
      <td height="22" width="8%"><font size="2">-</font></td>
1930 
      <td height="22" width="8%"><font size="2">-</font></td>
1931 
      <td height="22" width="8%"><font size="2">O(d)</font></td>
1932 
      <td height="22" width="8%"><font size="2">O(d)</font></td>
1933 
      <td height="22" width="8%"><font size="2">O(d)</font></td>
1934 
      <td height="22" width="8%"><font size="2">O(d)</font></td>
1935 
      <td height="22" width="8%"><font size="2">-</font></td>
1936 
      <td height="22" width="8%"><font size="2">-</font></td>
1937 
      <td height="22" width="9%"><font size="2">-</font></td>
1938 
      <td height="22" width="9%"><font size="2">-</font></td>
1939 
    </tr>
1940 
    <tr>
1941 
      <td height="22" width="9%"><font size="2">Reverse()</font></td>
1942 
      <td height="22" width="8%"><font size="2">-</font></td>
1943 
      <td height="22" width="8%"><font size="2">-</font></td>
1944 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1945 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1946 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1947 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1948 
      <td height="22" width="8%"><font size="2">-</font></td>
1949 
      <td height="22" width="8%"><font size="2">-</font></td>
1950 
      <td height="22" width="9%"><font size="2">-</font></td>
1951 
      <td height="22" width="9%"><font size="2">-</font></td>
1952 
    </tr>
1953 
    <tr>
1954 
      <td height="22" width="9%"><font size="2">IsSorted()</font></td>
1955 
      <td height="22" width="8%"><font size="2">-</font></td>
1956 
      <td height="22" width="8%"><font size="2">-</font></td>
1957 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1958 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1959 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1960 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1961 
      <td height="22" width="8%"><font size="2">-</font></td>
1962 
      <td height="22" width="8%"><font size="2">-</font></td>
1963 
      <td height="22" width="9%"><font size="2">-</font></td>
1964 
      <td height="22" width="9%"><font size="2">-</font></td>
1965 
    </tr>
1966 
    <tr>
1967 
      <td height="22" width="9%"><font size="2">Sort()</font></td>
1968 
      <td height="22" width="8%"><font size="2">-</font></td>
1969 
      <td height="22" width="8%"><font size="2">-</font></td>
1970 
      <td height="22" width="8%"><font size="2">O(n log n)</font></td>
1971 
      <td height="22" width="8%"><font size="2">O(n log n)</font></td>
1972 
      <td height="22" width="8%"><font size="2">O(n log n)</font></td>
1973 
      <td height="22" width="8%"><font size="2">O(n log n)</font></td>
1974 
      <td height="22" width="8%"><font size="2">-</font></td>
1975 
      <td height="22" width="8%"><font size="2">-</font></td>
1976 
      <td height="22" width="9%"><font size="2">-</font></td>
1977 
      <td height="22" width="9%"><font size="2">-</font></td>
1978 
    </tr>
1979 
    <tr>
1980 
      <td height="22" width="9%"><font size="2">Shuffle()</font></td>
1981 
      <td height="22" width="8%"><font size="2">-</font></td>
1982 
      <td height="22" width="8%"><font size="2">-</font></td>
1983 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1984 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1985 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1986 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
1987 
      <td height="22" width="8%"><font size="2">-</font></td>
1988 
      <td height="22" width="8%"><font size="2">-</font></td>
1989 
      <td height="22" width="9%"><font size="2">-</font></td>
1990 
      <td height="22" width="9%"><font size="2">-</font></td>
1991 
    </tr>
1992 
    <tr>
1993 
      <td height="22" width="14%"><i><font color="#808080" size="2">IPriorityQueue&lt;T&gt;</font></i></td>
1994 
      <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
1995 
      <td height="22" width="8%"><i><font color="#808080" size="2">HB</font></i></td>
1996 
      <td height="22" width="8%"><i><font color="#808080" size="2">AL</font></i></td>
1997 
      <td height="22" width="8%"><i><font color="#808080" size="2">LL</font></i></td>
1998 
      <td height="22" width="8%"><i><font color="#808080" size="2">HAL</font></i></td>
1999 
      <td height="22" width="8%"><i><font color="#808080" size="2">HLL</font></i></td>
2000 
      <td height="22" width="8%"><i><font color="#808080" size="2">RBTS</font></i></td>
2001 
      <td height="22" width="8%"><i><font color="#808080" size="2">RBTB</font></i></td>
2002 
      <td height="22" width="9%"><i><font color="#808080" size="2">SA</font></i></td>
2003 
      <td height="22" width="9%"><i><font color="#808080" size="2">IH</font></i></td>
2004 
    </tr>
2005 
    <tr>
2006 
      <td height="22" width="9%"><font size="2">FindMin()</font></td>
2007 
      <td height="22" width="8%"><font size="2">-</font></td>
2008 
      <td height="22" width="8%"><font size="2">-</font></td>
2009 
      <td height="22" width="8%"><font size="2">-</font></td>
2010 
      <td height="22" width="8%"><font size="2">-</font></td>
2011 
      <td height="22" width="8%"><font size="2">-</font></td>
2012 
      <td height="22" width="8%"><font size="2">-</font></td>
2013 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2014 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2015 
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
2016 
      <td height="22" width="9%"><font size="2">O(1)</font></td>
2017 
    </tr>
2018 
    <tr>
2019 
      <td height="22" width="9%"><font size="2">DeleteMin()</font></td>
2020 
      <td height="22" width="8%"><font size="2">-</font></td>
2021 
      <td height="22" width="8%"><font size="2">-</font></td>
2022 
      <td height="22" width="8%"><font size="2">-</font></td>
2023 
      <td height="22" width="8%"><font size="2">-</font></td>
2024 
      <td height="22" width="8%"><font size="2">-</font></td>
2025 
      <td height="22" width="8%"><font size="2">-</font></td>
2026 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2027 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2028 
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
2029 
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
2030 
    </tr>
2031 
    <tr>
2032 
      <td height="22" width="9%"><font size="2">FindMax()</font></td>
2033 
      <td height="22" width="8%"><font size="2">-</font></td>
2034 
      <td height="22" width="8%"><font size="2">-</font></td>
2035 
      <td height="22" width="8%"><font size="2">-</font></td>
2036 
      <td height="22" width="8%"><font size="2">-</font></td>
2037 
      <td height="22" width="8%"><font size="2">-</font></td>
2038 
      <td height="22" width="8%"><font size="2">-</font></td>
2039 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2040 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2041 
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
2042 
      <td height="22" width="9%"><font size="2">O(1)</font></td>
2043 
    </tr>
2044 
    <tr>
2045 
      <td height="30" width="9%"><font size="2">DeleteMax()</font></td>
2046 
      <td height="30" width="8%"><font size="2">-</font></td>
2047 
      <td height="30" width="8%"><font size="2">-</font></td>
2048 
      <td height="30" width="8%"><font size="2">-</font></td>
2049 
      <td height="30" width="8%"><font size="2">-</font></td>
2050 
      <td height="30" width="8%"><font size="2">-</font></td>
2051 
      <td height="30" width="8%"><font size="2">-</font></td>
2052 
      <td height="30" width="8%"><font size="2">O(log n)</font></td>
2053 
      <td height="30" width="8%"><font size="2">O(log n)</font></td>
2054 
      <td height="30" width="9%"><font size="2">O(log n)</font></td>
2055 
      <td height="30" width="9%"><font size="2">O(log n)</font></td>
2056 
    </tr>
2057 
    <tr>
2058 
      <td height="30" width="9%"> <font size="2">Comparer</font></td>
2059 
      <td height="30" width="8%"> <font size="2">-</font></td>
2060 
      <td height="30" width="8%"> <font size="2">-</font></td>
2061 
      <td height="30" width="8%"> <font size="2">-</font></td>
2062 
      <td height="30" width="8%"> <font size="2">-</font></td>
2063 
      <td height="30" width="8%"> <font size="2">-</font></td>
2064 
      <td height="30" width="8%"> <font size="2">-</font></td>
2065 
      <td height="30" width="8%"> <font size="2">O(1)</font></td>
2066 
      <td height="30" width="8%"> <font size="2">O(1)</font></td>
2067 
      <td height="30" width="9%"> <font size="2">O(1)</font></td>
2068 
      <td height="30" width="9%"> <font size="2">O(1)</font></td>
2069 
    </tr>
2070 
    <tr>
2071 
      <td height="22" width="14%"><i><font color="#808080" size="2">ISorted&lt;T&gt;</font></i></td>
2072 
      <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
2073 
      <td height="22" width="8%"><i><font color="#808080" size="2">HB</font></i></td>
2074 
      <td height="22" width="8%"><i><font color="#808080" size="2">AL</font></i></td>
2075 
      <td height="22" width="8%"><i><font color="#808080" size="2">LL</font></i></td>
2076 
      <td height="22" width="8%"><i><font color="#808080" size="2">HAL</font></i></td>
2077 
      <td height="22" width="8%"><i><font color="#808080" size="2">HLL</font></i></td>
2078 
      <td height="22" width="8%"><i><font color="#808080" size="2">RBTS</font></i></td>
2079 
      <td height="22" width="8%"><i><font color="#808080" size="2">RBTB</font></i></td>
2080 
      <td height="22" width="9%"><i><font color="#808080" size="2">SA</font></i></td>
2081 
      <td height="22" width="9%"><i><font color="#808080" size="2">IH</font></i></td>
2082 
    </tr>
2083 
    <tr>
2084 
      <td height="22" width="9%"><font size="2">Predecessor</font></td>
2085 
      <td height="22" width="8%"><font size="2">-</font></td>
2086 
      <td height="22" width="8%"><font size="2">-</font></td>
2087 
      <td height="22" width="8%"><font size="2">-</font></td>
2088 
      <td height="22" width="8%"><font size="2">-</font></td>
2089 
      <td height="22" width="8%"><font size="2">-</font></td>
2090 
      <td height="22" width="8%"><font size="2">-</font></td>
2091 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2092 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2093 
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
2094 
      <td height="22" width="9%"><font size="2">-</font></td>
2095 
    </tr>
2096 
    <tr>
2097 
      <td height="22" width="9%"><font size="2">Successor</font></td>
2098 
      <td height="22" width="8%"><font size="2">-</font></td>
2099 
      <td height="22" width="8%"><font size="2">-</font></td>
2100 
      <td height="22" width="8%"><font size="2">-</font></td>
2101 
      <td height="22" width="8%"><font size="2">-</font></td>
2102 
      <td height="22" width="8%"><font size="2">-</font></td>
2103 
      <td height="22" width="8%"><font size="2">-</font></td>
2104 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2105 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2106 
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
2107 
      <td height="22" width="9%"><font size="2">-</font></td>
2108 
    </tr>
2109 
    <tr>
2110 
      <td height="22" width="9%"><font size="2">WeakPredecessor</font></td>
2111 
      <td height="22" width="8%"><font size="2">-</font></td>
2112 
      <td height="22" width="8%"><font size="2">-</font></td>
2113 
      <td height="22" width="8%"><font size="2">-</font></td>
2114 
      <td height="22" width="8%"><font size="2">-</font></td>
2115 
      <td height="22" width="8%"><font size="2">-</font></td>
2116 
      <td height="22" width="8%"><font size="2">-</font></td>
2117 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2118 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2119 
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
2120 
      <td height="22" width="9%"><font size="2">-</font></td>
2121 
    </tr>
2122 
    <tr>
2123 
      <td height="22" width="9%"><font size="2">WeakSuccessor</font></td>
2124 
      <td height="22" width="8%"><font size="2">-</font></td>
2125 
      <td height="22" width="8%"><font size="2">-</font></td>
2126 
      <td height="22" width="8%"><font size="2">-</font></td>
2127 
      <td height="22" width="8%"><font size="2">-</font></td>
2128 
      <td height="22" width="8%"><font size="2">-</font></td>
2129 
      <td height="22" width="8%"><font size="2">-</font></td>
2130 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2131 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2132 
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
2133 
      <td height="22" width="9%"><font size="2">-</font></td>
2134 
    </tr>
2135 
    <tr>
2136 
      <td height="22" width="9%"><font size="2">Cut</font></td>
2137 
      <td height="22" width="8%"><font size="2">-</font></td>
2138 
      <td height="22" width="8%"><font size="2">-</font></td>
2139 
      <td height="22" width="8%"><font size="2">-</font></td>
2140 
      <td height="22" width="8%"><font size="2">-</font></td>
2141 
      <td height="22" width="8%"><font size="2">-</font></td>
2142 
      <td height="22" width="8%"><font size="2">-</font></td>
2143 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2144 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2145 
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
2146 
      <td height="22" width="9%"><font size="2">-</font></td>
2147 
    </tr>
2148 
    <tr>
2149 
      <td height="22" width="9%"><font size="2">RangeFrom</font></td>
2150 
      <td height="22" width="8%"><font size="2">-</font></td>
2151 
      <td height="22" width="8%"><font size="2">-</font></td>
2152 
      <td height="22" width="8%"><font size="2">-</font></td>
2153 
      <td height="22" width="8%"><font size="2">-</font></td>
2154 
      <td height="22" width="8%"><font size="2">-</font></td>
2155 
      <td height="22" width="8%"><font size="2">-</font></td>
2156 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2157 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2158 
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
2159 
      <td height="22" width="9%"><font size="2">-</font></td>
2160 
    </tr>
2161 
    <tr>
2162 
      <td height="22" width="9%"><font size="2">RangeFromTo</font></td>
2163 
      <td height="22" width="8%"><font size="2">-</font></td>
2164 
      <td height="22" width="8%"><font size="2">-</font></td>
2165 
      <td height="22" width="8%"><font size="2">-</font></td>
2166 
      <td height="22" width="8%"><font size="2">-</font></td>
2167 
      <td height="22" width="8%"><font size="2">-</font></td>
2168 
      <td height="22" width="8%"><font size="2">-</font></td>
2169 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2170 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2171 
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
2172 
      <td height="22" width="9%"><font size="2">-</font></td>
2173 
    </tr>
2174 
    <tr>
2175 
      <td height="22" width="9%"><font size="2">RangeTo</font></td>
2176 
      <td height="22" width="8%"><font size="2">-</font></td>
2177 
      <td height="22" width="8%"><font size="2">-</font></td>
2178 
      <td height="22" width="8%"><font size="2">-</font></td>
2179 
      <td height="22" width="8%"><font size="2">-</font></td>
2180 
      <td height="22" width="8%"><font size="2">-</font></td>
2181 
      <td height="22" width="8%"><font size="2">-</font></td>
2182 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2183 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2184 
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
2185 
      <td height="22" width="9%"><font size="2">-</font></td>
2186 
    </tr>
2187 
    <tr>
2188 
      <td height="22" width="9%"><font size="2">RangeAll</font></td>
2189 
      <td height="22" width="8%"><font size="2">-</font></td>
2190 
      <td height="22" width="8%"><font size="2">-</font></td>
2191 
      <td height="22" width="8%"><font size="2">-</font></td>
2192 
      <td height="22" width="8%"><font size="2">-</font></td>
2193 
      <td height="22" width="8%"><font size="2">-</font></td>
2194 
      <td height="22" width="8%"><font size="2">-</font></td>
2195 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
2196 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
2197 
      <td height="22" width="9%"><font size="2">O(1)</font></td>
2198 
      <td height="22" width="9%"><font size="2">-</font></td>
2199 
    </tr>
2200 
    <tr>
2201 
      <td height="22" width="9%"><font size="2">AddSorted</font></td>
2202 
      <td height="22" width="8%"><font size="2">-</font></td>
2203 
      <td height="22" width="8%"><font size="2">-</font></td>
2204 
      <td height="22" width="8%"><font size="2">-</font></td>
2205 
      <td height="22" width="8%"><font size="2">-</font></td>
2206 
      <td height="22" width="8%"><font size="2">-</font></td>
2207 
      <td height="22" width="8%"><font size="2">-</font></td>
2208 
      <td height="22" width="8%"><font size="2">?</font></td>
2209 
      <td height="22" width="8%"><font size="2">?</font></td>
2210 
      <td height="22" width="9%"><font size="2">?</font></td>
2211 
      <td height="22" width="9%"><font size="2">-</font></td>
2212 
    </tr>
2213 
    <tr>
2214 
      <td height="22" width="9%"><font size="2">RemoveRangeFrom</font></td>
2215 
      <td height="22" width="8%"><font size="2">-</font></td>
2216 
      <td height="22" width="8%"><font size="2">-</font></td>
2217 
      <td height="22" width="8%"><font size="2">-</font></td>
2218 
      <td height="22" width="8%"><font size="2">-</font></td>
2219 
      <td height="22" width="8%"><font size="2">-</font></td>
2220 
      <td height="22" width="8%"><font size="2">-</font></td>
2221 
      <td height="22" width="8%"><font size="2">O(nlog n)*</font></td>
2222 
      <td height="22" width="8%"><font size="2">O(nlog n)*</font></td>
2223 
      <td height="22" width="9%"><font size="2">O(n)</font></td>
2224 
      <td height="22" width="9%"><font size="2">-</font></td>
2225 
    </tr>
2226 
    <tr>
2227 
      <td height="22" width="9%"><font size="2">RemoveRangeFromTo</font></td>
2228 
      <td height="22" width="8%"><font size="2">-</font></td>
2229 
      <td height="22" width="8%"><font size="2">-</font></td>
2230 
      <td height="22" width="8%"><font size="2">-</font></td>
2231 
      <td height="22" width="8%"><font size="2">-</font></td>
2232 
      <td height="22" width="8%"><font size="2">-</font></td>
2233 
      <td height="22" width="8%"><font size="2">-</font></td>
2234 
      <td height="22" width="8%"><font size="2">O(nlog n)*</font></td>
2235 
      <td height="22" width="8%"><font size="2">O(nlog n)*</font></td>
2236 
      <td height="22" width="9%"><font size="2">O(n)</font></td>
2237 
      <td height="22" width="9%"><font size="2">-</font></td>
2238 
    </tr>
2239 
    <tr>
2240 
      <td height="22" width="9%"><font size="2">RemoveRangeTo</font></td>
2241 
      <td height="22" width="8%"><font size="2">-</font></td>
2242 
      <td height="22" width="8%"><font size="2">-</font></td>
2243 
      <td height="22" width="8%"><font size="2">-</font></td>
2244 
      <td height="22" width="8%"><font size="2">-</font></td>
2245 
      <td height="22" width="8%"><font size="2">-</font></td>
2246 
      <td height="22" width="8%"><font size="2">-</font></td>
2247 
      <td height="22" width="8%"><font size="2">O(nlog n)*</font></td>
2248 
      <td height="22" width="8%"><font size="2">O(nlog n)*</font></td>
2249 
      <td height="22" width="9%"><font size="2">O(n)</font></td>
2250 
      <td height="22" width="9%"><font size="2">-</font></td>
2251 
    </tr>
2252 
    <tr>
2253 
      <td height="22" width="14%"><i><font color="#808080" size="2">IIndexedSorted&lt;T&gt;</font></i></td>
2254 
      <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
2255 
      <td height="22" width="8%"><i><font color="#808080" size="2">HB</font></i></td>
2256 
      <td height="22" width="8%"><i><font color="#808080" size="2">AL</font></i></td>
2257 
      <td height="22" width="8%"><i><font color="#808080" size="2">LL</font></i></td>
2258 
      <td height="22" width="8%"><i><font color="#808080" size="2">HAL</font></i></td>
2259 
      <td height="22" width="8%"><i><font color="#808080" size="2">HLL</font></i></td>
2260 
      <td height="22" width="8%"><i><font color="#808080" size="2">RBTS</font></i></td>
2261 
      <td height="22" width="8%"><i><font color="#808080" size="2">RBTB</font></i></td>
2262 
      <td height="22" width="9%"><i><font color="#808080" size="2">SA</font></i></td>
2263 
      <td height="22" width="9%"><i><font color="#808080" size="2">IH</font></i></td>
2264 
    </tr>
2265 
    <tr>
2266 
      <td height="22" width="9%"><font size="2">Map</font></td>
2267 
      <td height="22" width="8%"><font size="2">-</font></td>
2268 
      <td height="22" width="8%"><font size="2">-</font></td>
2269 
      <td height="22" width="8%"><font size="2">-</font></td>
2270 
      <td height="22" width="8%"><font size="2">-</font></td>
2271 
      <td height="22" width="8%"><font size="2">-</font></td>
2272 
      <td height="22" width="8%"><font size="2">-</font></td>
2273 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
2274 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
2275 
      <td height="22" width="9%"><font size="2">O(n)</font></td>
2276 
      <td height="22" width="9%"><font size="2">-</font></td>
2277 
    </tr>
2278 
    <tr>
2279 
      <td height="22" width="9%"><font size="2">CountFrom</font></td>
2280 
      <td height="22" width="8%"><font size="2">-</font></td>
2281 
      <td height="22" width="8%"><font size="2">-</font></td>
2282 
      <td height="22" width="8%"><font size="2">-</font></td>
2283 
      <td height="22" width="8%"><font size="2">-</font></td>
2284 
      <td height="22" width="8%"><font size="2">-</font></td>
2285 
      <td height="22" width="8%"><font size="2">-</font></td>
2286 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2287 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2288 
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
2289 
      <td height="22" width="9%"><font size="2">-</font></td>
2290 
    </tr>
2291 
    <tr>
2292 
      <td height="22" width="9%"><font size="2">CountFromTo</font></td>
2293 
      <td height="22" width="8%"><font size="2">-</font></td>
2294 
      <td height="22" width="8%"><font size="2">-</font></td>
2295 
      <td height="22" width="8%"><font size="2">-</font></td>
2296 
      <td height="22" width="8%"><font size="2">-</font></td>
2297 
      <td height="22" width="8%"><font size="2">-</font></td>
2298 
      <td height="22" width="8%"><font size="2">-</font></td>
2299 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2300 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2301 
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
2302 
      <td height="22" width="9%"><font size="2">-</font></td>
2303 
    </tr>
2304 
    <tr>
2305 
      <td height="22" width="9%"><font size="2">CountTo</font></td>
2306 
      <td height="22" width="8%"><font size="2">-</font></td>
2307 
      <td height="22" width="8%"><font size="2">-</font></td>
2308 
      <td height="22" width="8%"><font size="2">-</font></td>
2309 
      <td height="22" width="8%"><font size="2">-</font></td>
2310 
      <td height="22" width="8%"><font size="2">-</font></td>
2311 
      <td height="22" width="8%"><font size="2">-</font></td>
2312 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2313 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2314 
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
2315 
      <td height="22" width="9%"><font size="2">-</font></td>
2316 
    </tr>
2317 
    <tr>
2318 
      <td height="22" width="9%"><font size="2">RangeFrom</font></td>
2319 
      <td height="22" width="8%"><font size="2">-</font></td>
2320 
      <td height="22" width="8%"><font size="2">-</font></td>
2321 
      <td height="22" width="8%"><font size="2">-</font></td>
2322 
      <td height="22" width="8%"><font size="2">-</font></td>
2323 
      <td height="22" width="8%"><font size="2">-</font></td>
2324 
      <td height="22" width="8%"><font size="2">-</font></td>
2325 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2326 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2327 
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
2328 
      <td height="22" width="9%"><font size="2">-</font></td>
2329 
    </tr>
2330 
    <tr>
2331 
      <td height="22" width="9%"><font size="2">RangeFromTo</font></td>
2332 
      <td height="22" width="8%"><font size="2">-</font></td>
2333 
      <td height="22" width="8%"><font size="2">-</font></td>
2334 
      <td height="22" width="8%"><font size="2">-</font></td>
2335 
      <td height="22" width="8%"><font size="2">-</font></td>
2336 
      <td height="22" width="8%"><font size="2">-</font></td>
2337 
      <td height="22" width="8%"><font size="2">-</font></td>
2338 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2339 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2340 
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
2341 
      <td height="22" width="9%"><font size="2">-</font></td>
2342 
    </tr>
2343 
    <tr>
2344 
      <td height="22" width="9%"><font size="2">RangeTo</font></td>
2345 
      <td height="22" width="8%"><font size="2">-</font></td>
2346 
      <td height="22" width="8%"><font size="2">-</font></td>
2347 
      <td height="22" width="8%"><font size="2">-</font></td>
2348 
      <td height="22" width="8%"><font size="2">-</font></td>
2349 
      <td height="22" width="8%"><font size="2">-</font></td>
2350 
      <td height="22" width="8%"><font size="2">-</font></td>
2351 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2352 
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
2353 
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
2354 
      <td height="22" width="9%"><font size="2">-</font></td>
2355 
    </tr>
2356 
    <tr>
2357 
      <td height="22" width="9%"><font size="2">FindAll</font></td>
2358 
      <td height="22" width="8%"><font size="2">-</font></td>
2359 
      <td height="22" width="8%"><font size="2">-</font></td>
2360 
      <td height="22" width="8%"><font size="2">-</font></td>
2361 
      <td height="22" width="8%"><font size="2">-</font></td>
2362 
      <td height="22" width="8%"><font size="2">-</font></td>
2363 
      <td height="22" width="8%"><font size="2">-</font></td>
2364 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
2365 
      <td height="22" width="8%"><font size="2">O(n)</font></td>
2366 
      <td height="22" width="9%"><font size="2">O(n)</font></td>
2367 
      <td height="22" width="9%"><font size="2">-</font></td>
2368 
    </tr>
2369 
    <tr>
2370 
      <td height="22" width="14%"><i><font color="#808080" size="2">IPersistentSorted&lt;T&gt;</font></i></td>
2371 
      <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
2372 
      <td height="22" width="8%"><i><font color="#808080" size="2">HB</font></i></td>
2373 
      <td height="22" width="8%"><i><font color="#808080" size="2">AL</font></i></td>
2374 
      <td height="22" width="8%"><i><font color="#808080" size="2">LL</font></i></td>
2375 
      <td height="22" width="8%"><i><font color="#808080" size="2">HAL</font></i></td>
2376 
      <td height="22" width="8%"><i><font color="#808080" size="2">HLL</font></i></td>
2377 
      <td height="22" width="8%"><i><font color="#808080" size="2">RBTS</font></i></td>
2378 
      <td height="22" width="8%"><i><font color="#808080" size="2">RBTB</font></i></td>
2379 
      <td height="22" width="9%"><i><font color="#808080" size="2">SA</font></i></td>
2380 
      <td height="22" width="9%"><i><font color="#808080" size="2">IH</font></i></td>
2381 
    </tr>
2382 
    <tr>
2383 
      <td height="22" width="9%"><font size="2">Snapshot()</font></td>
2384 
      <td height="22" width="8%"><font size="2">-</font></td>
2385 
      <td height="22" width="8%"><font size="2">-</font></td>
2386 
      <td height="22" width="8%"><font size="2">-</font></td>
2387 
      <td height="22" width="8%"><font size="2">-</font></td>
2388 
      <td height="22" width="8%"><font size="2">-</font></td>
2389 
      <td height="22" width="8%"><font size="2">-</font></td>
2390 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
2391 
      <td height="22" width="8%"><font size="2">O(1)</font></td>
2392 
      <td height="22" width="9%"><font size="2">-</font></td>
2393 
      <td height="22" width="9%"><font size="2">-</font></td>
2394 
    </tr>
2395 
  </tbody>
2396 
</table>
2397 
<h1><a class="mozTocH1" name="mozTocId712409"></a><a
2398 
 name="PerformanceDict">Performance</a> details for dictionary classes</h1>
2399 
<table border="1" width="467">
2400 
  <tbody>
2401 
    <tr>
2402 
      <th width="302">Member</th>
2403 
      <th width="79">HashDictionary&lt;K,V&gt;</th>
2404 
      <th width="64">TreeDictionary&lt;K,V&gt;</th>
2405 
    </tr>
2406 
    <tr>
2407 
      <td width="302"><i><font color="#808080" size="2">IEnumerable&lt;KeyValuePair&lt;K,V&gt;&gt;</font></i></td>
2408 
      <td width="79"><font color="#808080">&nbsp;</font></td>
2409 
      <td width="64">&nbsp;</td>
2410 
    </tr>
2411 
    <tr>
2412 
      <td width="302"><font size="2">GetEnumerator()</font></td>
2413 
      <td width="79"><font size="2">O(1)</font></td>
2414 
      <td width="64"><font size="2">O(1)</font></td>
2415 
    </tr>
2416 
    <tr>
2417 
      <td width="302"><i><font color="#808080" size="2">IDictionary&lt;K,V&gt;</font></i></td>
2418 
      <td width="79"><font color="#808080">&nbsp;</font></td>
2419 
      <td width="64">&nbsp;</td>
2420 
    </tr>
2421 
    <tr>
2422 
      <td width="302"><font size="2">this[key]</font></td>
2423 
      <td width="79"><font size="2">O(1)</font></td>
2424 
      <td width="64"><font size="2">O(log n)</font></td>
2425 
    </tr>
2426 
    <tr>
2427 
      <td width="302"><font size="2">Count</font></td>
2428 
      <td width="79"><font size="2">O(1)</font></td>
2429 
      <td width="64"><font size="2">O(1)</font></td>
2430 
    </tr>
2431 
    <tr>
2432 
      <td width="302"><font size="2">IsReadOnly</font></td>
2433 
      <td width="79"><font size="2">O(1)</font></td>
2434 
      <td width="64"><font size="2">O(1)</font></td>
2435 
    </tr>
2436 
    <tr>
2437 
      <td width="302"><font size="2">SyncRoot</font></td>
2438 
      <td width="79"><font size="2">O(1)</font></td>
2439 
      <td width="64"><font size="2">O(1)</font></td>
2440 
    </tr>
2441 
    <tr>
2442 
      <td width="302"><font size="2">Keys</font></td>
2443 
      <td width="79"><font size="2">O(1)</font></td>
2444 
      <td width="64"><font size="2">O(1)</font></td>
2445 
    </tr>
2446 
    <tr>
2447 
      <td width="302"><font size="2">Values</font></td>
2448 
      <td width="79"><font size="2">O(1)</font></td>
2449 
      <td width="64"><font size="2">O(1)</font></td>
2450 
    </tr>
2451 
    <tr>
2452 
      <td width="302"><font size="2">Add()</font></td>
2453 
      <td width="79"><font size="2">O(1)</font></td>
2454 
      <td height="22" width="64"><font size="2">O(log n)</font></td>
2455 
    </tr>
2456 
    <tr>
2457 
      <td width="302"><font size="2">Remove()</font></td>
2458 
      <td width="79"><font size="2">O(1)</font></td>
2459 
      <td height="22" width="64"><font size="2">O(log n)</font></td>
2460 
    </tr>
2461 
    <tr>
2462 
      <td width="302"><font size="2">Clear()</font></td>
2463 
      <td width="79"><font size="2">O(1)</font></td>
2464 
      <td height="22" width="64"><font size="2">O(1)</font></td>
2465 
    </tr>
2466 
    <tr>
2467 
      <td width="302"><font size="2">Contains()</font></td>
2468 
      <td width="79"><font size="2">O(1)</font></td>
2469 
      <td height="22" width="64"><font size="2">O(log n)</font></td>
2470 
    </tr>
2471 
    <tr>
2472 
      <td width="302"><font size="2">Find()</font></td>
2473 
      <td width="79"><font size="2">O(1)</font></td>
2474 
      <td height="22" width="64"><font size="2">O(log n)</font></td>
2475 
    </tr>
2476 
    <tr>
2477 
      <td width="302"><font size="2">Update()</font></td>
2478 
      <td width="79"><font size="2">O(1)</font></td>
2479 
      <td height="22" width="64"><font size="2">O(log n)</font></td>
2480 
    </tr>
2481 
    <tr>
2482 
      <td width="302"><font size="2">FindOrAdd</font></td>
2483 
      <td width="79"><font size="2">O(1)</font></td>
2484 
      <td height="22" width="64"><font size="2">O(log n)</font></td>
2485 
    </tr>
2486 
    <tr>
2487 
      <td width="302"><font size="2">UpdateOrAdd</font></td>
2488 
      <td width="79"><font size="2">O(1)</font></td>
2489 
      <td height="22" width="64"><font size="2">O(log n)</font></td>
2490 
    </tr>
2491 
    <tr>
2492 
      <td width="302"><i><font color="#808080" size="2">ISortedDictionary&lt;K,V&gt;</font></i></td>
2493 
      <td width="79"><font color="#808080">&nbsp;</font></td>
2494 
      <td width="64">&nbsp;</td>
2495 
    </tr>
2496 
    <tr>
2497 
      <td height="22" width="302"><font size="2">Predecessor</font></td>
2498 
      <td width="79"><font size="2">-</font></td>
2499 
      <td height="22" width="64"><font size="2">O(log n)</font></td>
2500 
    </tr>
2501 
    <tr>
2502 
      <td height="22" width="302"><font size="2">Successor</font></td>
2503 
      <td width="79"><font size="2">-</font></td>
2504 
      <td height="22" width="64"><font size="2">O(log n)</font></td>
2505 
    </tr>
2506 
    <tr>
2507 
      <td height="22" width="302"><font size="2">WeakPredecessor</font></td>
2508 
      <td width="79"><font size="2">-</font></td>
2509 
      <td height="22" width="64"><font size="2">O(log n)</font></td>
2510 
    </tr>
2511 
    <tr>
2512 
      <td height="22" width="302"><font size="2">WeakSuccessor</font></td>
2513 
      <td width="79"><font size="2">-</font></td>
2514 
      <td height="22" width="64"><font size="2">O(log n)</font></td>
2515 
    </tr>
2516 
  </tbody>
2517 
</table>
2518 
</body>
2519 
</html>