source: trunk/CrypPlugins/WorkspaceManager/View/VisualComponents/CryptoLineView/PowerCollections/OrderedSet.cs @ 1927

Last change on this file since 1927 was 1927, checked in by matkovic, 11 years ago

-added PowerCollection library
-added QuadTree
-improved path finding performance

File size: 68.8 KB
Line 
1//******************************
2// Written by Peter Golde
3// Copyright (c) 2004-2007, Wintellect
4//
5// Use and restribution of this code is subject to the license agreement
6// contained in the file "License.txt" accompanying this file.
7//******************************
8
9using System;
10using System.Collections.Generic;
11
12namespace Wintellect.PowerCollections
13{
14    /// <summary>
15    /// OrderedSet&lt;T&gt; is a collection that contains items of type T.
16    /// The item are maintained in a sorted order, and duplicate items are not allowed. Each item has
17    /// an index in the set: the smallest item has index 0, the next smallest item has index 1,
18    /// and so forth.
19    /// </summary>
20    /// <remarks>
21    /// <p>The items are compared in one of three ways. If T implements IComparable&lt;TKey&gt; or IComparable,
22    /// then the CompareTo method of that interface will be used to compare items. Alternatively, a comparison
23    /// function can be passed in either as a delegate, or as an instance of IComparer&lt;TKey&gt;.</p>
24    /// <p>OrderedSet is implemented as a balanced binary tree. Inserting, deleting, and looking up an
25    /// an element all are done in log(N) type, where N is the number of keys in the tree.</p>
26    /// <p><see cref="Set&lt;T&gt;"/> is similar, but uses hashing instead of comparison, and does not maintain
27    /// the items in sorted order.</p>
28    ///</remarks>
29    ///<seealso cref="Set&lt;T&gt;"/>
30    [Serializable]
31    public class OrderedSet<T> : CollectionBase<T>, ICollection<T>, ICloneable
32    {
33        // The comparer used to compare items.
34        private readonly IComparer<T> comparer;
35
36        // The red-black tree that actually does the work of storing the items.
37        private RedBlackTree<T> tree;
38
39        #region Constructors
40
41        /// <summary>
42        /// Creates a new OrderedSet. The T must implement IComparable&lt;T&gt;
43        /// or IComparable.
44        /// The CompareTo method of this interface will be used to compare items in this set.
45        /// </summary>
46        ///<remarks>
47        /// Items that are null are permitted, and will be sorted before all other items.
48        ///</remarks>
49        /// <exception cref="InvalidOperationException">T does not implement IComparable&lt;TKey&gt;.</exception>
50        public OrderedSet(): 
51            this(Comparers.DefaultComparer<T>())
52        {
53        }
54
55        /// <summary>
56        /// Creates a new OrderedSet. The passed delegate will be used to compare items in this set.
57        /// </summary>
58        /// <param name="comparison">A delegate to a method that will be used to compare items.</param>
59        public OrderedSet(Comparison<T> comparison) :
60            this(Comparers.ComparerFromComparison(comparison))
61        {
62        }
63
64        /// <summary>
65        /// Creates a new OrderedSet. The Compare method of the passed comparison object
66        /// will be used to compare items in this set.
67        /// </summary>
68        /// <remarks>
69        /// The GetHashCode and Equals methods of the provided IComparer&lt;T&gt; will never
70        /// be called, and need not be implemented.
71        /// </remarks>
72        /// <param name="comparer">An instance of IComparer&lt;T&gt; that will be used to compare items.</param>
73        public OrderedSet(IComparer<T> comparer)
74        {
75            if (comparer == null)
76                throw new ArgumentNullException("comparer");
77
78            this.comparer = comparer;
79            tree = new RedBlackTree<T>(comparer);
80        }
81
82        /// <summary>
83        /// Creates a new OrderedSet. The T must implement IComparable&lt;T&gt;
84        /// or IComparable.
85        /// The CompareTo method of this interface will be used to compare items in this set. The set is
86        /// initialized with all the items in the given collection.
87        /// </summary>
88        ///<remarks>
89        /// Items that are null are permitted, and will be sorted before all other items.
90        ///</remarks>
91        /// <param name="collection">A collection with items to be placed into the OrderedSet.</param>
92        /// <exception cref="InvalidOperationException">T does not implement IComparable&lt;TKey&gt;.</exception>
93        public OrderedSet(IEnumerable<T> collection): 
94            this(collection, Comparers.DefaultComparer<T>())
95        {
96        }
97
98        /// <summary>
99        /// Creates a new OrderedSet. The passed delegate will be used to compare items in this set.
100        /// The set is initialized with all the items in the given collection.
101        /// </summary>
102        /// <param name="collection">A collection with items to be placed into the OrderedSet.</param>
103        /// <param name="comparison">A delegate to a method that will be used to compare items.</param>
104        public OrderedSet(IEnumerable<T> collection, Comparison<T> comparison):
105            this(collection, Comparers.ComparerFromComparison(comparison))
106        {
107        }
108
109        /// <summary>
110        /// Creates a new OrderedSet. The Compare method of the passed comparison object
111        /// will be used to compare items in this set. The set is
112        /// initialized with all the items in the given collection.
113        /// </summary>
114        /// <remarks>
115        /// The GetHashCode and Equals methods of the provided IComparer&lt;T&gt; will never
116        /// be called, and need not be implemented.
117        /// </remarks>
118        /// <param name="collection">A collection with items to be placed into the OrderedSet.</param>
119        /// <param name="comparer">An instance of IComparer&lt;T&gt; that will be used to compare items.</param>
120        public OrderedSet(IEnumerable<T> collection, IComparer<T> comparer):
121            this(comparer)
122        {
123            AddMany(collection);
124        }
125
126        /// <summary>
127        /// Creates a new OrderedSet given a comparer and a tree that contains the data. Used
128        /// internally for Clone.
129        /// </summary>
130        /// <param name="comparer">Comparer for the set.</param>
131        /// <param name="tree">Data for the set.</param>
132        private OrderedSet(IComparer<T> comparer, RedBlackTree<T> tree)
133        {
134            this.comparer = comparer;
135            this.tree = tree;
136        }
137
138        #endregion Constructors
139
140        #region Cloning
141
142        /// <summary>
143        /// Makes a shallow clone of this set; i.e., if items of the
144        /// set are reference types, then they are not cloned. If T is a value type,
145        /// then each element is copied as if by simple assignment.
146        /// </summary>
147        /// <remarks>Cloning the set takes time O(N), where N is the number of items in the set.</remarks>
148        /// <returns>The cloned set.</returns>
149        object ICloneable.Clone()
150        {
151            return this.Clone();     
152        }
153
154        /// <summary>
155        /// Makes a shallow clone of this set; i.e., if items of the
156        /// set are reference types, then they are not cloned. If T is a value type,
157        /// then each element is copied as if by simple assignment.
158        /// </summary>
159        /// <remarks>Cloning the set takes time O(N), where N is the number of items in the set.</remarks>
160        /// <returns>The cloned set.</returns>
161        public OrderedSet<T> Clone()
162        {
163            OrderedSet<T> newSet = new OrderedSet<T>(comparer, tree.Clone());
164            return newSet;
165        }
166
167        /// <summary>
168        /// Makes a deep clone of this set. A new set is created with a clone of
169        /// each element of this set, by calling ICloneable.Clone on each element. If T is
170        /// a value type, then each element is copied as if by simple assignment.
171        /// </summary>
172        /// <remarks><para>If T is a reference type, it must implement
173        /// ICloneable. Otherwise, an InvalidOperationException is thrown.</para>
174        /// <para>Cloning the set takes time O(N log N), where N is the number of items in the set.</para></remarks>
175        /// <returns>The cloned set.</returns>
176        /// <exception cref="InvalidOperationException">T is a reference type that does not implement ICloneable.</exception>
177        public OrderedSet<T> CloneContents() 
178        {
179            bool itemIsValueType;
180            if (!Util.IsCloneableType(typeof(T), out itemIsValueType))
181                throw new InvalidOperationException(string.Format(Strings.TypeNotCloneable, typeof(T).FullName));
182
183            OrderedSet<T> clone = new OrderedSet<T>(comparer);
184
185            // Clone each item, and add it to the new ordered set.
186            foreach (T item in this) {
187                T itemClone;
188
189                if (itemIsValueType)
190                    itemClone = item;
191                else {
192                    if (item == null)
193                        itemClone = default(T);    // Really null, because we know T is a reference type
194                    else
195                        itemClone = (T)(((ICloneable)item).Clone());
196                }
197
198                clone.Add(itemClone);
199            }
200
201            return clone;
202        }
203
204        #endregion Cloning
205
206        #region Basic collection containment
207
208        /// <summary>
209        /// Returns the IComparer&lt;T&gt; used to compare items in this set.
210        /// </summary>
211        /// <value>If the set was created using a comparer, that comparer is returned. If the set was
212        /// created using a comparison delegate, then a comparer equivalent to that delegate
213        /// is returned. Otherwise
214        /// the default comparer for T (Comparer&lt;T&gt;.Default) is returned.</value>
215        public IComparer<T> Comparer
216        {
217            get
218            {
219                return this.comparer;
220            }
221        }
222
223        /// <summary>
224        /// Returns the number of items in the set.
225        /// </summary>
226        /// <remarks>The size of the set is returned in constant time.</remarks>
227        /// <value>The number of items in the set.</value>
228        public sealed override int Count
229        {
230            get {
231                return tree.ElementCount;
232            }
233        }
234
235        /// <summary>
236        /// Returns an enumerator that enumerates all the items in the set.
237        /// The items are enumerated in sorted order.
238        /// </summary>
239        /// <remarks>
240        /// <p>Typically, this method is not called directly. Instead the "foreach" statement is used
241        /// to enumerate the items, which uses this method implicitly.</p>
242        /// <p>If an item is added to or deleted from the set while it is being enumerated, then
243        /// the enumeration will end with an InvalidOperationException.</p>
244        /// <p>Enumeration all the items in the set takes time O(N log N), where N is the number
245        /// of items in the set.</p>
246        /// </remarks>
247        /// <returns>An enumerator for enumerating all the items in the OrderedSet.</returns>           
248        public sealed override IEnumerator<T> GetEnumerator()
249        {
250            return tree.GetEnumerator();
251        }
252
253        /// <summary>
254        /// Determines if this set contains an item equal to <paramref name="item"/>. The set
255        /// is not changed.
256        /// </summary>
257        /// <remarks>Searching the set for an item takes time O(log N), where N is the number of items in the set.</remarks>
258        /// <param name="item">The item to search for.</param>
259        /// <returns>True if the set contains <paramref name="item"/>. False if the set does not contain <paramref name="item"/>.</returns>
260        public sealed override bool Contains(T item)
261        {
262            T dummy;
263            return tree.Find(item, false, false, out dummy);
264        }
265
266        /// <summary>
267        /// <para>Determines if this set contains an item equal to <paramref name="item"/>, according to the
268        /// comparison mechanism that was used when the set was created. The set
269        /// is not changed.</para>
270        /// <para>If the set does contain an item equal to <paramref name="item"/>, then the item from the set is returned.</para>
271        /// </summary>
272        /// <remarks>Searching the set for an item takes time O(log N), where N is the number of items in the set.</remarks>
273        /// <example>
274        /// In the following example, the set contains strings which are compared in a case-insensitive manner.
275        /// <code>
276        /// OrderedSet&lt;string&gt; set = new OrderedSet&lt;string&gt;(StringComparer.CurrentCultureIgnoreCase);
277        /// set.Add("HELLO");
278        /// string s;
279        /// bool b = set.TryGetItem("Hello", out s);   // b receives true, s receives "HELLO".
280        /// </code>
281        /// </example>
282        /// <param name="item">The item to search for.</param>
283        /// <param name="foundItem">Returns the item from the set that was equal to <paramref name="item"/>.</param>
284        /// <returns>True if the set contains <paramref name="item"/>. False if the set does not contain <paramref name="item"/>.</returns>
285        public bool TryGetItem(T item, out T foundItem)
286        {
287            return tree.Find(item, true, false, out foundItem);
288        }
289
290        #endregion
291
292        #region Index by sorted order
293
294        /// <summary>
295        /// Get the item by its index in the sorted order. The smallest item has index 0,
296        /// the next smallest item has index 1, and the largest item has index Count-1.
297        /// </summary>
298        /// <remarks>The indexer takes time O(log N), which N is the number of items in
299        /// the set.</remarks>
300        /// <param name="index">The index to get the item by.</param>
301        /// <returns>The item at the given index.</returns>
302        /// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is
303        /// less than zero or greater than or equal to Count.</exception>
304        public T this[int index]
305        {
306            get {
307                if (index < 0 || index >= Count)
308                    throw new ArgumentOutOfRangeException("index");
309
310                return tree.GetItemByIndex(index);
311            }
312        }
313
314        /// <summary>
315        /// Get the index of the given item in the sorted order. The smallest item has index 0,
316        /// the next smallest item has index 1, and the largest item has index Count-1.
317        /// </summary>
318        /// <remarks>Finding the index takes time O(log N), which N is the number of items in
319        /// the set.</remarks>
320        /// <param name="item">The item to get the index of.</param>
321        /// <returns>The index of the item in the sorted set, or -1 if the item is not present
322        /// in the set.</returns>
323        public int IndexOf(T item)
324        {
325            return tree.FindIndex(item, true);
326        }
327
328        #endregion
329
330        #region Adding elements
331
332        /// <summary>
333        /// Adds a new item to the set. If the set already contains an item equal to
334        /// <paramref name="item"/>, that item is replaced with <paramref name="item"/>.
335        /// </summary>
336        /// <remarks>
337        /// <para>Equality between items is determined by the comparison instance or delegate used
338        /// to create the set.</para>
339        /// <para>Adding an item takes time O(log N), where N is the number of items in the set.</para></remarks>
340        /// <param name="item">The item to add to the set.</param>
341        /// <returns>True if the set already contained an item equal to <paramref name="item"/> (which was replaced), false
342        /// otherwise.</returns>
343        public new bool Add(T item)
344        {
345            T dummy;
346            return ! tree.Insert(item, DuplicatePolicy.ReplaceFirst, out dummy);
347        }
348
349        /// <summary>
350        /// Adds a new item to the set. If the set already contains an item equal to
351        /// <paramref name="item"/>, that item is replaces with <paramref name="item"/>.
352        /// </summary>
353        /// <remarks>
354        /// <para>Equality between items is determined by the comparison instance or delegate used
355        /// to create the set.</para>
356        /// <para>Adding an item takes time O(log N), where N is the number of items in the set.</para></remarks>
357        /// <param name="item">The item to add to the set.</param>
358        void ICollection<T>.Add(T item)
359        {
360            Add(item);
361        }
362
363        /// <summary>
364        /// Adds all the items in <paramref name="collection"/> to the set. If the set already contains an item equal to
365        /// one of the items in <paramref name="collection"/>, that item will be replaced.
366        /// </summary>
367        /// <remarks>
368        /// <para>Equality between items is determined by the comparison instance or delegate used
369        /// to create the set.</para>
370        /// <para>Adding the collection takes time O(M log N), where N is the number of items in the set, and M is the
371        /// number of items in <paramref name="collection"/>.</para></remarks>
372        /// <param name="collection">A collection of items to add to the set.</param>
373        public void AddMany(IEnumerable<T> collection)
374        {
375            if (collection == null)
376                throw new ArgumentNullException("collection");
377
378            // If we're adding ourselves, then there is nothing to do.
379            if (object.ReferenceEquals(collection, this))
380                return;
381
382            foreach (T item in collection)
383                Add(item);
384        }
385
386        #endregion Adding elements
387
388        #region Removing elements
389
390        /// <summary>
391        /// Searches the set for an item equal to <paramref name="item"/>, and if found,
392        /// removes it from the set. If not found, the set is unchanged.
393        /// </summary>
394        /// <remarks>
395        /// <para>Equality between items is determined by the comparison instance or delegate used
396        /// to create the set.</para>
397        /// <para>Removing an item from the set takes time O(log N), where N is the number of items in the set.</para></remarks>
398        /// <param name="item">The item to remove.</param>
399        /// <returns>True if <paramref name="item"/> was found and removed. False if <paramref name="item"/> was not in the set.</returns>
400        public sealed override bool Remove(T item)
401        {
402            T dummy;
403            return tree.Delete(item, true, out dummy);
404        }
405
406        /// <summary>
407        /// Removes all the items in <paramref name="collection"/> from the set. Items
408        /// not present in the set are ignored.
409        /// </summary>
410        /// <remarks>
411        /// <para>Equality between items is determined by the comparison instance or delegate used
412        /// to create the set.</para>
413        /// <para>Removing the collection takes time O(M log N), where N is the number of items in the set, and M is the
414        /// number of items in <paramref name="collection"/>.</para></remarks>
415        /// <param name="collection">A collection of items to remove from the set.</param>
416        /// <returns>The number of items removed from the set.</returns>
417        /// <exception cref="ArgumentNullException"><paramref name="collection"/> is null.</exception>
418        public int RemoveMany(IEnumerable<T> collection)
419        {
420            if (collection == null)
421                throw new ArgumentNullException("collection");
422
423            int count = 0;
424
425            if (collection == this) {
426                count = Count;
427                Clear();            // special case, otherwise we will throw.
428            }
429            else {
430                foreach (T item in collection) {
431                    if (Remove(item))
432                        ++count;
433                }
434            }
435
436            return count;
437        }
438
439        /// <summary>
440        /// Removes all items from the set.
441        /// </summary>
442        /// <remarks>Clearing the sets takes a constant amount of time, regardless of the number of items in it.</remarks>
443        public sealed override void Clear()
444        {
445            tree.StopEnumerations();  // Invalidate any enumerations.
446
447            // The simplest and fastest way is simply to throw away the old tree and create a new one.
448            tree = new RedBlackTree<T>(comparer);
449        }
450
451        #endregion Removing elements
452
453        #region First/last items
454
455        /// <summary>
456        /// If the collection is empty, throw an invalid operation exception.
457        /// </summary>
458        /// <exception cref="InvalidOperationException">The set is empty.</exception>
459        private void CheckEmpty()
460        {
461            if (Count == 0)
462                throw new InvalidOperationException(Strings.CollectionIsEmpty);
463        }
464
465        /// <summary>
466        /// Returns the first item in the set: the item
467        /// that would appear first if the set was enumerated. This is also
468        /// the smallest item in the set.
469        /// </summary>
470        /// <remarks>GetFirst() takes time O(log N), where N is the number of items in the set.</remarks>
471        /// <returns>The first item in the set. </returns>
472        /// <exception cref="InvalidOperationException">The set is empty.</exception>
473        public T GetFirst()
474        {
475            T item;
476            CheckEmpty();
477            tree.FirstItemInRange(tree.EntireRangeTester, out item);
478            return item;
479        }
480
481        /// <summary>
482        /// Returns the lastl item in the set: the item
483        /// that would appear last if the set was enumerated. This is also the
484        /// largest item in the set.
485        /// </summary>
486        /// <remarks>GetLast() takes time O(log N), where N is the number of items in the set.</remarks>
487        /// <returns>The lastl item in the set. </returns>
488        /// <exception cref="InvalidOperationException">The set is empty.</exception>
489        public T GetLast()
490        {
491            T item;
492            CheckEmpty();
493            tree.LastItemInRange(tree.EntireRangeTester, out item);
494            return item;
495        }
496
497        /// <summary>
498        /// Removes the first item in the set. This is also the smallest item in the set.
499        /// </summary>
500        /// <remarks>RemoveFirst() takes time O(log N), where N is the number of items in the set.</remarks>
501        /// <returns>The item that was removed, which was the smallest item in the set. </returns>
502        /// <exception cref="InvalidOperationException">The set is empty.</exception>
503        public T RemoveFirst()
504        {
505            CheckEmpty();
506            T item;
507            tree.DeleteItemFromRange(tree.EntireRangeTester, true, out item);
508            return item;
509        }
510
511        /// <summary>
512        /// Removes the last item in the set. This is also the largest item in the set.
513        /// </summary>
514        /// <remarks>RemoveLast() takes time O(log N), where N is the number of items in the set.</remarks>
515        /// <returns>The item that was removed, which was the largest item in the set. </returns>
516        /// <exception cref="InvalidOperationException">The set is empty.</exception>
517        public T RemoveLast()
518        {
519            CheckEmpty();
520            T item;
521            tree.DeleteItemFromRange(tree.EntireRangeTester, false, out item);
522            return item;
523        }
524
525        #endregion
526
527        #region Set operations
528
529        /// <summary>
530        /// Check that this set and another set were created with the same comparison
531        /// mechanism. Throws exception if not compatible.
532        /// </summary>
533        /// <param name="otherSet">Other set to check comparision mechanism.</param>
534        /// <exception cref="InvalidOperationException">If otherSet and this set don't use the same method for comparing items.</exception>
535        private void CheckConsistentComparison(OrderedSet<T> otherSet) 
536        {
537            if (otherSet == null)
538                throw new ArgumentNullException("otherSet");
539
540            if (!object.Equals(comparer, otherSet.comparer))
541                throw new InvalidOperationException(Strings.InconsistentComparisons);
542        }
543
544        /// <summary>
545        /// Determines if this set is a superset of another set. Neither set is modified.
546        /// This set is a superset of <paramref name="otherSet"/> if every element in
547        /// <paramref name="otherSet"/> is also in this set.
548        /// <remarks>IsSupersetOf is computed in time O(M log N), where M is the size of the
549        /// <paramref name="otherSet"/>, and N is the size of the this set.</remarks>
550        /// </summary>
551        /// <param name="otherSet">OrderedSet to compare to.</param>
552        /// <returns>True if this is a superset of <paramref name="otherSet"/>.</returns>
553        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
554        public bool IsSupersetOf(OrderedSet<T> otherSet)
555        {
556            CheckConsistentComparison(otherSet);
557
558            if (otherSet.Count > this.Count)
559                return false;     // Can't be a superset of a bigger set
560
561            // Check each item in the other set to make sure it is in this set.
562            foreach (T item in otherSet) {
563                if (!this.Contains(item))
564                    return false;
565            }
566
567            return true;
568        }
569
570        /// <summary>
571        /// Determines if this set is a proper superset of another set. Neither set is modified.
572        /// This set is a proper superset of <paramref name="otherSet"/> if every element in
573        /// <paramref name="otherSet"/> is also in this set.
574        /// Additionally, this set must have strictly more items than <paramref name="otherSet"/>.
575        /// </summary>
576        /// <remarks>IsProperSupersetOf is computed in time O(M log N), where M is the number of unique items in
577        /// <paramref name="otherSet"/>.</remarks>
578        /// <param name="otherSet">OrderedSet to compare to.</param>
579        /// <returns>True if this is a proper superset of <paramref name="otherSet"/>.</returns>
580        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
581        public bool IsProperSupersetOf(OrderedSet<T> otherSet)
582        {
583            CheckConsistentComparison(otherSet);
584
585            if (otherSet.Count >= this.Count)
586                return false;     // Can't be a proper superset of a bigger or equal set
587
588            return IsSupersetOf(otherSet);
589        }
590
591        /// <summary>
592        /// Determines if this set is a subset of another set. Neither set is modified.
593        /// This set is a subset of <paramref name="otherSet"/> if every element in this set
594        /// is also in <paramref name="otherSet"/>.
595        /// </summary>
596        /// <remarks>IsSubsetOf is computed in time O(N log M), where M is the size of the
597        /// <paramref name="otherSet"/>, and N is the size of the this set.</remarks>
598        /// <param name="otherSet">Set to compare to.</param>
599        /// <returns>True if this is a subset of <paramref name="otherSet"/>.</returns>
600        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
601        public bool IsSubsetOf(OrderedSet<T> otherSet)
602        {
603            return otherSet.IsSupersetOf(this);
604        }
605
606
607        /// <summary>
608        /// Determines if this set is a proper subset of another set. Neither set is modified.
609        /// This set is a subset of <paramref name="otherSet"/> if every element in this set
610        /// is also in <paramref name="otherSet"/>. Additionally, this set must have strictly
611        /// fewer items than <paramref name="otherSet"/>.
612        /// </summary>
613        /// <remarks>IsSubsetOf is computed in time O(N log M), where M is the size of the
614        /// <paramref name="otherSet"/>, and N is the size of the this set.</remarks>
615        /// <param name="otherSet">Set to compare to.</param>
616        /// <returns>True if this is a proper subset of <paramref name="otherSet"/>.</returns>
617        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
618        public bool IsProperSubsetOf(OrderedSet<T> otherSet)
619        {
620            return otherSet.IsProperSupersetOf(this);
621        }
622
623        /// <summary>
624        /// Determines if this set is equal to another set. This set is equal to
625        /// <paramref name="otherSet"/> if they contain the same items.
626        /// </summary>
627        /// <remarks>IsEqualTo is computed in time O(N), where N is the number of items in
628        /// this set.</remarks>
629        /// <param name="otherSet">Set to compare to</param>
630        /// <returns>True if this set is equal to <paramref name="otherSet"/>, false otherwise.</returns>
631        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
632        public bool IsEqualTo(OrderedSet<T> otherSet)
633        {
634            CheckConsistentComparison(otherSet);
635
636            // Must be the same size.
637            if (otherSet.Count != this.Count)
638                return false;
639
640            // Since both sets are ordered, we can simply compare items in order.
641            using (IEnumerator<T> enum1 = this.GetEnumerator(), enum2 = otherSet.GetEnumerator()) {
642                bool continue1, continue2;
643
644                for (; ; ) {
645                    continue1 = enum1.MoveNext(); continue2 = enum2.MoveNext();
646                    if (!continue1 || !continue2)
647                        break;
648
649                    if (comparer.Compare(enum1.Current, enum2.Current) != 0)
650                        return false;     // the two items are not equal.
651                }
652
653                // If both continue1 and continue2 are false, we reached the end of both sequences at the same
654                // time and found success. If one is true and one is false, the sequences were of difference lengths -- failure.
655                return (continue1 == continue2);
656            }
657        }
658
659        /// <summary>
660        /// Computes the union of this set with another set. The union of two sets
661        /// is all items that appear in either or both of the sets. This set receives
662        /// the union of the two sets, the other set is unchanged.
663        /// </summary>
664        /// <remarks>
665        /// <para>If equal items appear in both sets, the union will include an arbitrary choice of one of the
666        /// two equal items.</para>
667        /// <para>The union of two sets is computed in time O(M + N log M), where M is the size of the
668        /// larger set, and N is the size of the smaller set.</para>
669        /// </remarks>
670        /// <param name="otherSet">Set to union with.</param>
671        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
672        public void UnionWith(OrderedSet<T> otherSet)
673        {
674            CheckConsistentComparison(otherSet);
675
676            AddMany(otherSet);
677
678            // CONSIDER: if RedBlackTree cloning is O(N), then if otherSet is much larger, better to clone it,
679            // add all of the current into it, and replace.
680        }
681
682        /// <summary>
683        /// Determines if this set is disjoint from another set. Two sets are disjoint
684        /// if no item from one set is equal to any item in the other set.
685        /// </summary>
686        /// <remarks>
687        /// <para>The answer is computed in time O(N log M), where M is the size of the
688        /// larger set, and N is the size of the smaller set.</para>
689        /// </remarks>
690        /// <param name="otherSet">Set to check disjointness with.</param>
691        /// <returns>True if the two sets are disjoint, false otherwise.</returns>
692        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
693        public bool IsDisjointFrom(OrderedSet<T> otherSet)
694        {
695            CheckConsistentComparison(otherSet);
696            OrderedSet<T> smaller, larger;
697            if (otherSet.Count > this.Count) {
698                smaller = this; larger = otherSet;
699            }
700            else {
701                smaller = otherSet; larger = this;
702            }
703
704            foreach (T item in smaller) {
705                if (larger.Contains(item))
706                    return false;
707            }
708
709            return true;
710        }
711
712        /// <summary>
713        /// Computes the union of this set with another set. The union of two sets
714        /// is all items that appear in either or both of the sets. A new set is
715        /// created with the union of the sets and is returned. This set and the other set
716        /// are unchanged.
717        /// </summary>
718        /// <remarks>
719        /// <para>If equal items appear in both sets, the union will include an arbitrary choice of one of the
720        /// two equal items.</para>
721        /// <para>The union of two sets is computed in time O(M + N log M), where M is the size of the
722        /// larger set, and N is the size of the smaller set.</para>
723        /// </remarks>
724        /// <param name="otherSet">Set to union with.</param>
725        /// <returns>The union of the two sets.</returns>
726        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
727        public OrderedSet<T> Union(OrderedSet<T> otherSet)
728        {
729            CheckConsistentComparison(otherSet);
730            OrderedSet<T> smaller, larger, result;
731            if (otherSet.Count > this.Count) {
732                smaller = this; larger = otherSet;
733            }
734            else {
735                smaller = otherSet; larger = this;
736            }
737
738            result = larger.Clone();
739            result.AddMany(smaller);
740            return result;
741        }
742
743        /// <summary>
744        /// Computes the intersection of this set with another set. The intersection of two sets
745        /// is all items that appear in both of the sets. This set receives
746        /// the intersection of the two sets, the other set is unchanged.
747        /// </summary>
748        /// <remarks>
749        /// <para>When equal items appear in both sets, the intersection will include an arbitrary choice of one of the
750        /// two equal items.</para>
751        /// <para>The intersection of two sets is computed in time O(N log M), where M is the size of the
752        /// larger set, and N is the size of the smaller set.</para>
753        /// </remarks>
754        /// <param name="otherSet">Set to intersection with.</param>
755        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
756        public void IntersectionWith(OrderedSet<T> otherSet)
757        {
758            CheckConsistentComparison(otherSet);
759            tree.StopEnumerations();
760
761            OrderedSet<T> smaller, larger;
762            if (otherSet.Count > this.Count) {
763                smaller = this; larger = otherSet;
764            }
765            else {
766                smaller = otherSet; larger = this;
767            }
768
769            T dummy;
770            RedBlackTree<T> newTree = new RedBlackTree<T>(comparer);
771
772            foreach (T item in smaller) {
773                if (larger.Contains(item))
774                    newTree.Insert(item, DuplicatePolicy.ReplaceFirst, out dummy);
775            }
776
777            tree = newTree;
778        }
779
780        /// <summary>
781        /// Computes the intersection of this set with another set. The intersection of two sets
782        /// is all items that appear in both of the sets. A new set is
783        /// created with the intersection of the sets and is returned. This set and the other set
784        /// are unchanged.
785        /// </summary>
786        /// <remarks>
787        /// <para>When equal items appear in both sets, the intersection will include an arbitrary choice of one of the
788        /// two equal items.</para>
789        /// <para>The intersection of two sets is computed in time O(N log M), where M is the size of the
790        /// larger set, and N is the size of the smaller set.</para>
791        /// </remarks>
792        /// <param name="otherSet">Set to intersection with.</param>
793        /// <returns>The intersection of the two sets.</returns>
794        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
795        public OrderedSet<T> Intersection(OrderedSet<T> otherSet)
796        {
797            CheckConsistentComparison(otherSet);
798            OrderedSet<T> smaller, larger, result;
799            if (otherSet.Count > this.Count) {
800                smaller = this; larger = otherSet;
801            }
802            else {
803                smaller = otherSet; larger = this;
804            }
805
806            result = new OrderedSet<T>(comparer);
807            foreach (T item in smaller) {
808                if (larger.Contains(item))
809                    result.Add(item);
810            }
811
812            return result;
813        }
814
815        /// <summary>
816        /// Computes the difference of this set with another set. The difference of these two sets
817        /// is all items that appear in this set, but not in <paramref name="otherSet"/>. This set receives
818        /// the difference of the two sets; the other set is unchanged.
819        /// </summary>
820        /// <remarks>
821        /// <para>The difference of two sets is computed in time O(M + N log M), where M is the size of the
822        /// larger set, and N is the size of the smaller set.</para>
823        /// </remarks>
824        /// <param name="otherSet">Set to difference with.</param>
825        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
826        public void DifferenceWith(OrderedSet<T> otherSet)
827        {
828            // Difference with myself is nothing. This check is needed because the
829            // main algorithm doesn't work correctly otherwise.
830            if (this == otherSet)
831                Clear();
832
833            CheckConsistentComparison(otherSet);
834
835            if (otherSet.Count < this.Count){
836                foreach (T item in otherSet) {
837                    this.Remove(item);
838                }
839            }
840            else {
841                RemoveAll(delegate(T item) { return otherSet.Contains(item); });
842            }
843        }
844
845        /// <summary>
846        /// Computes the difference of this set with another set. The difference of these two sets
847        /// is all items that appear in this set, but not in <paramref name="otherSet"/>. A new set is
848        /// created with the difference of the sets and is returned. This set and the other set
849        /// are unchanged.
850        /// </summary>
851        /// <remarks>
852        /// <para>The difference of two sets is computed in time O(M + N log M), where M is the size of the
853        /// larger set, and N is the size of the smaller set.</para>
854        /// </remarks>
855        /// <param name="otherSet">Set to difference with.</param>
856        /// <returns>The difference of the two sets.</returns>
857        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
858        public OrderedSet<T> Difference(OrderedSet<T> otherSet)
859        {
860            CheckConsistentComparison(otherSet);
861            OrderedSet<T> result = this.Clone();
862            result.DifferenceWith(otherSet);
863            return result;
864        }
865
866        /// <summary>
867        /// Computes the symmetric difference of this set with another set. The symmetric difference of two sets
868        /// is all items that appear in either of the sets, but not both. This set receives
869        /// the symmetric difference of the two sets; the other set is unchanged.
870        /// </summary>
871        /// <remarks>
872        /// <para>The symmetric difference of two sets is computed in time O(M + N log M), where M is the size of the
873        /// larger set, and N is the size of the smaller set.</para>
874        /// </remarks>
875        /// <param name="otherSet">Set to symmetric difference with.</param>
876        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
877        public void SymmetricDifferenceWith(OrderedSet<T> otherSet)
878        {
879            // Symmetric difference with myself is nothing. This check is needed because the
880            // main algorithm doesn't work correctly otherwise.
881            if (this == otherSet)
882                Clear();
883
884            CheckConsistentComparison(otherSet);
885
886            // CONSIDER: if otherSet is larger, better to clone it and reverse the below?
887            foreach (T item in otherSet) {
888                if (this.Contains(item))
889                    this.Remove(item);
890                else
891                    this.Add(item);
892            }
893        }
894
895        /// <summary>
896        /// Computes the symmetric difference of this set with another set. The symmetric difference of two sets
897        /// is all items that appear in either of the sets, but not both. A new set is
898        /// created with the symmetric difference of the sets and is returned. This set and the other set
899        /// are unchanged.
900        /// </summary>
901        /// <remarks>
902        /// <para>The symmetric difference of two sets is computed in time O(M + N log M), where M is the size of the
903        /// larger set, and N is the size of the smaller set.</para>
904        /// </remarks>
905        /// <param name="otherSet">Set to symmetric difference with.</param>
906        /// <returns>The symmetric difference of the two sets.</returns>
907        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
908        public OrderedSet<T> SymmetricDifference(OrderedSet<T> otherSet)
909        {
910            CheckConsistentComparison(otherSet);
911            OrderedSet<T> smaller, larger, result;
912            if (otherSet.Count > this.Count) {
913                smaller = this; larger = otherSet;
914            }
915            else {
916                smaller = otherSet; larger = this;
917            }
918
919            result = larger.Clone();
920            foreach (T item in smaller) {
921                if (result.Contains(item))
922                    result.Remove(item);
923                else
924                    result.Add(item);
925            }
926
927            return result;
928        }
929
930        #endregion Set operations
931
932        #region Read-only list view
933
934        /// <summary>
935        /// Get a read-only list view of the items in this ordered set. The
936        /// items in the list are in sorted order, with the smallest item
937        /// at index 0. This view does not copy any data, and reflects any
938        /// changes to the underlying OrderedSet.
939        /// </summary>
940        /// <returns>A read-only IList&lt;T&gt; view onto this OrderedSet.</returns>
941        public IList<T> AsList()
942        {
943            return new ListView(this, tree.EntireRangeTester, true, false);
944        }
945
946        /// <summary>
947        /// The nested class that provides a read-only list view
948        /// of all or part of the collection.
949        /// </summary>
950        [Serializable]
951        private class ListView : ReadOnlyListBase<T>
952        {
953            private readonly OrderedSet<T> mySet;
954            private readonly RedBlackTree<T>.RangeTester rangeTester;   // range tester for the range being used.
955            private readonly bool entireTree;                   // is the view the whole tree?
956            private readonly bool reversed;                     // is the view reversed?
957
958            /// <summary>
959            /// Create a new list view wrapped the given set.
960            /// </summary>
961            /// <param name="mySet"></param>
962            /// <param name="rangeTester">Range tester that defines the range being used.</param>
963            /// <param name="entireTree">If true, then rangeTester defines the entire tree. Used to optimize some operations.</param>
964            /// <param name="reversed">Is the view enuemerated in reverse order?</param>
965            public ListView(OrderedSet<T> mySet, RedBlackTree<T>.RangeTester rangeTester, bool entireTree, bool reversed)
966            {
967                this.mySet = mySet;
968                this.rangeTester = rangeTester;
969                this.entireTree = entireTree;
970                this.reversed = reversed;
971            }
972
973            public override int Count
974            {
975                get
976                {
977                    if (entireTree)
978                        return mySet.Count;
979                    else {
980                        // Note: we can't cache the result of this call because the underlying
981                        // set can change, which would make the cached value incorrect.
982                        return mySet.tree.CountRange(rangeTester);
983                    }
984                }
985            }
986
987            public override T this[int index]
988            {
989                get
990                {
991                    if (entireTree) {
992                        if (reversed)
993                            return mySet[mySet.Count - 1 - index];
994                        else
995                            return mySet[index];
996                    }
997                    else {
998                        T dummy;
999                        int firstIndex = mySet.tree.FirstItemInRange(rangeTester, out dummy);
1000                        int lastIndex = mySet.tree.LastItemInRange(rangeTester, out dummy);
1001                        if (firstIndex < 0 || lastIndex < 0 || index < 0 || index >= (lastIndex - firstIndex + 1))
1002                            throw new ArgumentOutOfRangeException("index");
1003
1004                        if (reversed) 
1005                            return mySet[lastIndex - index];
1006                        else 
1007                            return mySet[firstIndex + index];
1008                    }
1009                }
1010            }
1011
1012            public override int IndexOf(T item)
1013            {
1014                if (entireTree) {
1015                    if (reversed)
1016                        return mySet.Count - 1 - mySet.IndexOf(item);
1017                    else
1018                        return mySet.IndexOf(item);
1019                }
1020                else {
1021                    T dummy;
1022
1023                    if (rangeTester(item) != 0)
1024                        return -1;
1025
1026                    if (reversed) {
1027                        int indexInSet = mySet.tree.FindIndex(item, false);
1028                        if (indexInSet < 0)
1029                            return -1;
1030                        int indexOfEnd = mySet.tree.LastItemInRange(rangeTester, out dummy);
1031                        return indexOfEnd - indexInSet;
1032
1033                    }
1034                    else {
1035                        int indexInSet = mySet.tree.FindIndex(item, true);
1036                        if (indexInSet < 0)
1037                            return -1;
1038                        int indexOfStart = mySet.tree.FirstItemInRange(rangeTester, out dummy);
1039                        return indexInSet - indexOfStart;
1040                    }
1041                }
1042            }
1043        }
1044
1045        #endregion Read-only list view
1046
1047        #region Sub-views
1048
1049        /// <summary>
1050        /// Returns a View collection that can be used for enumerating the items in the set in
1051        /// reversed order.
1052        /// </summary>
1053        ///<remarks>
1054        ///<p>Typically, this method is used in conjunction with a foreach statement. For example:
1055        ///<code>
1056        /// foreach(T item in set.Reversed()) {
1057        ///    // process item
1058        /// }
1059        ///</code></p>
1060        /// <p>If an item is added to or deleted from the set while the View is being enumerated, then
1061        /// the enumeration will end with an InvalidOperationException.</p>
1062        ///<p>Calling Reverse does not copy the data in the tree, and the operation takes constant time.</p>
1063        ///</remarks>
1064        /// <returns>An OrderedSet.View of items in reverse order.</returns>
1065        public View Reversed()   // A reversed view that can be enumerated
1066        {
1067            return new View(this, tree.EntireRangeTester, true, true);
1068        }
1069
1070        /// <summary>
1071        /// Returns a View collection that can be used for enumerating a range of the items in the set..
1072        /// Only items that are greater than <paramref name="from"/> and
1073        /// less than <paramref name="to"/> are included. The items are enumerated in sorted order.
1074        /// Items equal to the end points of the range can be included or excluded depending on the
1075        /// <paramref name="fromInclusive"/> and <paramref name="toInclusive"/> parameters.
1076        /// </summary>
1077        ///<remarks>
1078        ///<p>If <paramref name="from"/> is greater than <paramref name="to"/>, the returned collection is empty. </p>
1079        ///<p>Typically, this method is used in conjunction with a foreach statement. For example:
1080        ///<code>
1081        /// foreach(T item in set.Range(from, true, to, false)) {
1082        ///    // process item
1083        /// }
1084        ///</code></p>
1085        /// <p>If an item is added to or deleted from the set while the View is being enumerated, then
1086        /// the enumeration will end with an InvalidOperationException.</p>
1087        ///<p>Calling Range does not copy the data in the tree, and the operation takes constant time.</p>
1088        ///</remarks>
1089        /// <param name="from">The lower bound of the range.</param>
1090        /// <param name="fromInclusive">If true, the lower bound is inclusive--items equal to the lower bound will
1091        /// be included in the range. If false, the lower bound is exclusive--items equal to the lower bound will not
1092        /// be included in the range.</param>
1093        /// <param name="to">The upper bound of the range. </param>
1094        /// <param name="toInclusive">If true, the upper bound is inclusive--items equal to the upper bound will
1095        /// be included in the range. If false, the upper bound is exclusive--items equal to the upper bound will not
1096        /// be included in the range.</param>
1097        /// <returns>An OrderedSet.View of items in the given range.</returns>
1098        public View Range(T from, bool fromInclusive, T to, bool toInclusive)  // A partial view that can be enumerated
1099        {
1100            return new View(this, tree.DoubleBoundedRangeTester(from, fromInclusive, to, toInclusive), false, false);
1101        }
1102
1103        /// <summary>
1104        /// Returns a View collection that can be used for enumerating a range of the items in the set..
1105        /// Only items that are greater than (and optionally, equal to) <paramref name="from"/> are included.
1106        /// The items are enumerated in sorted order. Items equal to <paramref name="from"/> can be included
1107        /// or excluded depending on the <paramref name="fromInclusive"/> parameter.
1108        /// </summary>
1109        ///<remarks>
1110        ///<p>Typically, this method is used in conjunction with a foreach statement. For example:
1111        ///<code>
1112        /// foreach(T item in set.RangeFrom(from, true)) {
1113        ///    // process item
1114        /// }
1115        ///</code></p>
1116        /// <p>If an item is added to or deleted from the set while the View is being enumerated, then
1117        /// the enumeration will end with an InvalidOperationException.</p>
1118        ///<p>Calling RangeFrom does not copy the data in the tree, and the operation takes constant time.</p>
1119        ///</remarks>
1120        /// <param name="from">The lower bound of the range.</param>
1121        /// <param name="fromInclusive">If true, the lower bound is inclusive--items equal to the lower bound will
1122        /// be included in the range. If false, the lower bound is exclusive--items equal to the lower bound will not
1123        /// be included in the range.</param>
1124        /// <returns>An OrderedSet.View of items in the given range.</returns>
1125        public View RangeFrom(T from, bool fromInclusive)  // A partial view that can be enumerated
1126        {
1127            return new View(this, tree.LowerBoundedRangeTester(from, fromInclusive), false, false);
1128        }
1129
1130        /// <summary>
1131        /// Returns a View collection that can be used for enumerating a range of the items in the set..
1132        /// Only items that are less than (and optionally, equal to) <paramref name="to"/> are included.
1133        /// The items are enumerated in sorted order. Items equal to <paramref name="to"/> can be included
1134        /// or excluded depending on the <paramref name="toInclusive"/> parameter.
1135        /// </summary>
1136        ///<remarks>
1137        ///<p>Typically, this method is used in conjunction with a foreach statement. For example:
1138        ///<code>
1139        /// foreach(T item in set.RangeTo(to, false)) {
1140        ///    // process item
1141        /// }
1142        ///</code></p>
1143        /// <p>If an item is added to or deleted from the set while the View is being enumerated, then
1144        /// the enumeration will end with an InvalidOperationException.</p>
1145        ///<p>Calling RangeTo does not copy the data in the tree, and the operation takes constant time.</p>
1146        ///</remarks>
1147        /// <param name="to">The upper bound of the range. </param>
1148        /// <param name="toInclusive">If true, the upper bound is inclusive--items equal to the upper bound will
1149        /// be included in the range. If false, the upper bound is exclusive--items equal to the upper bound will not
1150        /// be included in the range.</param>
1151        /// <returns>An OrderedSet.View of items in the given range.</returns>
1152        public View RangeTo(T to, bool toInclusive)  // A partial view that can be enumerated
1153        {
1154            return new View(this, tree.UpperBoundedRangeTester(to, toInclusive), false, false);
1155        }
1156
1157        #endregion
1158       
1159        #region View nested class
1160   
1161        /// <summary>
1162        /// The OrderedSet&lt;T&gt;.View class is used to look at a subset of the Items
1163        /// inside an ordered set. It is returned from the Range, RangeTo, RangeFrom, and Reversed methods.
1164        /// </summary>
1165        ///<remarks>
1166        /// <p>Views are dynamic. If the underlying set changes, the view changes in sync. If a change is made
1167        /// to the view, the underlying set changes accordingly.</p>
1168        ///<p>Typically, this class is used in conjunction with a foreach statement to enumerate the items
1169        /// in a subset of the OrderedSet. For example:</p>
1170        ///<code>
1171        /// foreach(T item in set.Range(from, to)) {
1172        ///    // process item
1173        /// }
1174        ///</code>
1175        ///</remarks>
1176        [Serializable]
1177        public class View : CollectionBase<T>, ICollection<T>
1178        {
1179            private readonly OrderedSet<T> mySet;
1180            private readonly RedBlackTree<T>.RangeTester rangeTester;   // range tester for the range being used.
1181            private readonly bool entireTree;                   // is the view the whole tree?
1182            private readonly bool reversed;                     // is the view reversed?
1183
1184            /// <summary>
1185            /// Initialize the view.
1186            /// </summary>
1187            /// <param name="mySet">OrderedSet being viewed</param>
1188            /// <param name="rangeTester">Range tester that defines the range being used.</param>
1189            /// <param name="entireTree">If true, then rangeTester defines the entire tree. Used to optimize some operations.</param>
1190            /// <param name="reversed">Is the view enuemerated in reverse order?</param>
1191            internal View(OrderedSet<T> mySet, RedBlackTree<T>.RangeTester rangeTester, bool entireTree, bool reversed)
1192            {
1193                this.mySet = mySet;
1194                this.rangeTester = rangeTester;
1195                this.entireTree = entireTree;
1196                this.reversed = reversed;
1197            }
1198
1199            /// <summary>
1200            /// Determine if the given item lies within the bounds of this view.
1201            /// </summary>
1202            /// <param name="item">Item to test.</param>
1203            /// <returns>True if the item is within the bounds of this view.</returns>
1204            private bool ItemInView(T item)
1205            {
1206                return rangeTester(item) == 0;
1207            }
1208
1209            /// <summary>
1210            /// Enumerate all the items in this view.
1211            /// </summary>
1212            /// <returns>An IEnumerator&lt;T&gt; with the items in this view.</returns>
1213            public sealed override IEnumerator<T> GetEnumerator()
1214            {
1215                if (reversed)
1216                    return mySet.tree.EnumerateRangeReversed(rangeTester).GetEnumerator();
1217                else
1218                    return mySet.tree.EnumerateRange(rangeTester).GetEnumerator();
1219            }
1220
1221            /// <summary>
1222            /// Number of items in this view.
1223            /// </summary>
1224            /// <value>Number of items that lie within the bounds the view.</value>
1225            public sealed override int Count
1226            {
1227                get {
1228                    if (entireTree)
1229                        return mySet.Count;
1230                    else {
1231                        // Note: we can't cache the result of this call because the underlying
1232                        // set can change, which would make the cached value incorrect.
1233                        return mySet.tree.CountRange(rangeTester);
1234                    }
1235                }
1236            }
1237
1238            /// <summary>
1239            /// Removes all the items within this view from the underlying set.
1240            /// </summary>
1241            /// <example>The following removes all the items that start with "A" from an OrderedSet.
1242            /// <code>
1243            /// set.Range("A", "B").Clear();
1244            /// </code>
1245            /// </example>
1246            public sealed override void Clear()
1247            {
1248                if (entireTree) {
1249                    mySet.Clear();   // much faster than DeleteRange
1250                }
1251                else {
1252                    mySet.tree.DeleteRange(rangeTester);
1253                }
1254            }
1255
1256            /// <summary>
1257            /// Adds a new item to the set underlying this View. If the set already contains an item equal to
1258            /// <paramref name="item"/>, that item is replaces with <paramref name="item"/>. If
1259            /// <paramref name="item"/> is outside the range of this view, an InvalidOperationException
1260            /// is thrown.
1261            /// </summary>
1262            /// <remarks>
1263            /// <para>Equality between items is determined by the comparison instance or delegate used
1264            /// to create the set.</para>
1265            /// <para>Adding an item takes time O(log N), where N is the number of items in the set.</para></remarks>
1266            /// <param name="item">The item to add.</param>
1267            /// <returns>True if the set already contained an item equal to <paramref name="item"/> (which was replaced), false
1268            /// otherwise.</returns>
1269            public new bool Add(T item)
1270            {
1271                if (!ItemInView(item))
1272                    throw new ArgumentException(Strings.OutOfViewRange, "item");
1273                else
1274                    return mySet.Add(item);
1275            }
1276
1277            /// <summary>
1278            /// Adds a new item to the set underlying this View. If the set already contains an item equal to
1279            /// <paramref name="item"/>, that item is replaces with <paramref name="item"/>. If
1280            /// <paramref name="item"/> is outside the range of this view, an InvalidOperationException
1281            /// is thrown.
1282            /// </summary>
1283            /// <remarks>
1284            /// <para>Equality between items is determined by the comparison instance or delegate used
1285            /// to create the set.</para>
1286            /// <para>Adding an item takes time O(log N), where N is the number of items in the set.</para></remarks>
1287            /// <param name="item">The item to add.</param>
1288            void ICollection<T>.Add(T item)
1289            {
1290                Add(item);
1291            }
1292
1293            /// <summary>
1294            /// Searches the underlying set for an item equal to <paramref name="item"/>, and if found,
1295            /// removes it from the set. If not found, the set is unchanged. If the item is outside
1296            /// the range of this view, the set is unchanged.
1297            /// </summary>
1298            /// <remarks>
1299            /// <para>Equality between items is determined by the comparison instance or delegate used
1300            /// to create the set.</para>
1301            /// <para>Removing an item from the set takes time O(log N), where N is the number of items in the set.</para></remarks>
1302            /// <param name="item">The item to remove.</param>
1303            /// <returns>True if <paramref name="item"/> was found and removed. False if <paramref name="item"/> was not in the set, or
1304            /// was outside the range of this view.</returns>
1305            public sealed override bool Remove(T item)
1306            {
1307                if (!ItemInView(item))
1308                    return false;
1309                else
1310                    return mySet.Remove(item);
1311            }
1312
1313            /// <summary>
1314            /// Determines if this view of the set contains an item equal to <paramref name="item"/>. The set
1315            /// is not changed. If
1316            /// </summary>
1317            /// <remarks>Searching the set for an item takes time O(log N), where N is the number of items in the set.</remarks>
1318            /// <param name="item">The item to search for.</param>
1319            /// <returns>True if the set contains <paramref name="item"/>, and <paramref name="item"/> is within
1320            /// the range of this view. False otherwise.</returns>
1321            public sealed override bool Contains(T item)
1322            {
1323                if (!ItemInView(item))
1324                    return false;
1325                else
1326                    return mySet.Contains(item);
1327            }
1328
1329            /// <summary>
1330            /// Get the index of the given item in the view. The smallest item in the view has index 0,
1331            /// the next smallest item has index 1, and the largest item has index Count-1.
1332            /// </summary>
1333            /// <remarks>Finding the index takes time O(log N), which N is the number of items in
1334            /// the set.</remarks>
1335            /// <param name="item">The item to get the index of.</param>
1336            /// <returns>The index of the item in the view, or -1 if the item is not present
1337            /// in the view.</returns>
1338            public int IndexOf(T item)
1339            {
1340                if (entireTree) {
1341                    if (reversed) {
1342                        int indexInSet = mySet.tree.FindIndex(item, false);
1343                        if (indexInSet < 0)
1344                            return -1;
1345
1346                        return mySet.Count - 1 - indexInSet;
1347                    }
1348                    else {
1349                        return mySet.tree.FindIndex(item, true);
1350                    }
1351                }
1352                else {
1353                    T dummy;
1354
1355                    if (!ItemInView(item))
1356                        return -1;
1357
1358                    if (reversed) {
1359                        int indexInSet = mySet.tree.FindIndex(item, false);
1360                        if (indexInSet < 0)
1361                            return -1;
1362                        int indexOfEnd = mySet.tree.LastItemInRange(rangeTester, out dummy);
1363                        return indexOfEnd - indexInSet;
1364
1365                    }
1366                    else {
1367                        int indexInSet = mySet.tree.FindIndex(item, true);
1368                        if (indexInSet < 0)
1369                            return -1;
1370                        int indexOfStart = mySet.tree.FirstItemInRange(rangeTester, out dummy);
1371                        return indexInSet - indexOfStart;
1372                    }
1373                }
1374            }
1375
1376            /// <summary>
1377            /// Get the item by its index in the sorted order. The smallest item in the view has index 0,
1378            /// the next smallest item has index 1, and the largest item has index Count-1.
1379            /// </summary>
1380            /// <remarks>The indexer takes time O(log N), which N is the number of items in
1381            /// the set.</remarks>
1382            /// <param name="index">The index to get the item by.</param>
1383            /// <returns>The item at the given index.</returns>
1384            /// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is
1385            /// less than zero or greater than or equal to Count.</exception>
1386            public T this[int index]
1387            {
1388                get
1389                {
1390                    if (entireTree) {
1391                        if (reversed) {
1392                            return mySet[mySet.Count - 1 - index];
1393                        }
1394                        else {
1395                            return mySet[index];
1396                        }
1397                    }
1398                    else {
1399                        T dummy;
1400                        int firstIndex = mySet.tree.FirstItemInRange(rangeTester, out dummy);
1401                        int lastIndex = mySet.tree.LastItemInRange(rangeTester, out dummy);
1402                        if (firstIndex < 0 || lastIndex < 0 || index < 0 || index >= (lastIndex - firstIndex + 1))
1403                            throw new ArgumentOutOfRangeException("index");
1404
1405                        if (reversed) 
1406                            return mySet[lastIndex - index];
1407                        else 
1408                            return mySet[firstIndex + index];
1409                    }
1410                }
1411            }
1412
1413            /// <summary>
1414            /// Get a read-only list view of the items in this view. The
1415            /// items in the list are in sorted order, with the smallest item
1416            /// at index 0. This view does not copy any data, and reflects any
1417            /// changes to the underlying OrderedSet.
1418            /// </summary>
1419            /// <returns>A read-only IList&lt;T&gt; view onto this view.</returns>
1420            public IList<T> AsList()
1421            {
1422                return new ListView(mySet, rangeTester, entireTree, reversed);
1423            }
1424
1425            /// <summary>
1426            /// Creates a new View that has the same items as this view, in the reversed order.
1427            /// </summary>
1428            /// <returns>A new View that has the reversed order of this view, with the same upper
1429            /// and lower bounds.</returns>
1430            public View Reversed()
1431            {
1432                return new View(mySet, rangeTester, entireTree, !reversed);
1433            }
1434
1435            /// <summary>
1436            /// Returns the first item in this view: the item
1437            /// that would appear first if the view was enumerated.
1438            /// </summary>
1439            /// <remarks>GetFirst() takes time O(log N), where N is the number of items in the set.</remarks>
1440            /// <returns>The first item in the view. </returns>
1441            /// <exception cref="InvalidOperationException">The view has no items in it.</exception>
1442            public T GetFirst()
1443            {
1444                T item;
1445                int found;
1446
1447                if (reversed)
1448                    found = mySet.tree.LastItemInRange(rangeTester, out item);
1449                else
1450                    found = mySet.tree.FirstItemInRange(rangeTester, out item);
1451
1452                if (found < 0)
1453                    throw new InvalidOperationException(Strings.CollectionIsEmpty);
1454
1455                return item;
1456            }
1457
1458            /// <summary>
1459            /// Returns the last item in the view: the item
1460            /// that would appear last if the view was enumerated.
1461            /// </summary>
1462            /// <remarks>GetLast() takes time O(log N), where N is the number of items in the set.</remarks>
1463            /// <returns>The last item in the view. </returns>
1464            /// <exception cref="InvalidOperationException">The view has no items in it.</exception>
1465            public T GetLast()
1466            {
1467                T item;
1468                int found;
1469
1470                if (reversed)
1471                    found = mySet.tree.FirstItemInRange(rangeTester, out item);
1472                else
1473                    found = mySet.tree.LastItemInRange(rangeTester, out item);
1474
1475                if (found < 0)
1476                    throw new InvalidOperationException(Strings.CollectionIsEmpty);
1477
1478                return item;
1479            }
1480        }
1481
1482        #endregion
1483    }
1484}
Note: See TracBrowser for help on using the repository browser.