source: trunk/CrypPlugins/WorkspaceManager/View/VisualComponents/CryptoLineView/PowerCollections/Set.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: 34.9 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    /// Set&lt;T&gt; is a collection that contains items of type T.
16    /// The item are maintained in a haphazard, unpredictable order, and duplicate items are not allowed.
17    /// </summary>
18    /// <remarks>
19    /// <p>The items are compared in one of two ways. If T implements IComparable&lt;T&gt;
20    /// then the Equals method of that interface will be used to compare items, otherwise the Equals
21    /// method from Object will be used. Alternatively, an instance of IComparer&lt;T&gt; can be passed
22    /// to the constructor to use to compare items.</p>
23    /// <p>Set is implemented as a hash table. Inserting, deleting, and looking up an
24    /// an element all are done in approximately constant time, regardless of the number of items in the Set.</p>
25    /// <p><see cref="OrderedSet&lt;T&gt;"/> is similar, but uses comparison instead of hashing, and does maintains
26    /// the items in sorted order.</p>
27    ///</remarks>
28    ///<seealso cref="OrderedSet&lt;T&gt;"/>
29    [Serializable]
30    public class Set<T> : CollectionBase<T>, ICollection<T>, ICloneable
31    {
32        // The comparer used to hash/compare items.
33        private readonly IEqualityComparer<T> equalityComparer;
34
35        // The hash table that actually does the work of storing the items.
36        private Hash<T> hash;
37
38        #region Constructors
39
40        /// <summary>
41        /// Creates a new Set. The Equals method and GetHashCode method on T
42        /// will be used to compare items for equality.
43        /// </summary>
44        ///<remarks>
45        /// Items that are null are permitted, and will be sorted before all other items.
46        ///</remarks>
47        public Set(): 
48            this(EqualityComparer<T>.Default)
49        {
50        }
51
52        /// <summary>
53        /// Creates a new Set. The Equals and GetHashCode method of the passed comparer object
54        /// will be used to compare items in this set.
55        /// </summary>
56        /// <param name="equalityComparer">An instance of IEqualityComparer&lt;T&gt; that will be used to compare items.</param>
57        public Set(IEqualityComparer<T> equalityComparer)
58        {
59            if (equalityComparer == null)
60                throw new ArgumentNullException("equalityComparer");
61
62            this.equalityComparer = equalityComparer;
63            hash = new Hash<T>(equalityComparer);
64        }
65
66        /// <summary>
67        /// Creates a new Set. The Equals method and GetHashCode method on T
68        /// will be used to compare items for equality.
69        /// </summary>
70        ///<remarks>
71        /// Items that are null are permitted.
72        ///</remarks>
73        /// <param name="collection">A collection with items to be placed into the Set.</param>
74        public Set(IEnumerable<T> collection): 
75            this(collection, EqualityComparer<T>.Default)
76        {
77        }
78
79        /// <summary>
80        /// Creates a new Set. The Equals and GetHashCode method of the passed comparer object
81        /// will be used to compare items in this set. The set is
82        /// initialized with all the items in the given collection.
83        /// </summary>
84        /// <param name="collection">A collection with items to be placed into the Set.</param>
85        /// <param name="equalityComparer">An instance of IEqualityComparer&lt;T&gt; that will be used to compare items.</param>
86        public Set(IEnumerable<T> collection, IEqualityComparer<T> equalityComparer)
87           : this(equalityComparer)
88        {
89            AddMany(collection);
90        }
91
92        /// <summary>
93        /// Creates a new Set given a comparer and a tree that contains the data. Used
94        /// internally for Clone.
95        /// </summary>
96        /// <param name="equalityComparer">EqualityComparer for the set.</param>
97        /// <param name="hash">Data for the set.</param>
98        private Set(IEqualityComparer<T> equalityComparer, Hash<T> hash)
99        {
100            this.equalityComparer = equalityComparer;
101            this.hash = hash;
102        }
103
104        #endregion Constructors
105
106        #region Cloning
107
108        /// <summary>
109        /// Makes a shallow clone of this set; i.e., if items of the
110        /// set are reference types, then they are not cloned. If T is a value type,
111        /// then each element is copied as if by simple assignment.
112        /// </summary>
113        /// <remarks>Cloning the set takes time O(N), where N is the number of items in the set.</remarks>
114        /// <returns>The cloned set.</returns>
115        object ICloneable.Clone()
116        {
117            return this.Clone();
118        }
119
120        /// <summary>
121        /// Makes a shallow clone of this set; i.e., if items of the
122        /// set are reference types, then they are not cloned. If T is a value type,
123        /// then each element is copied as if by simple assignment.
124        /// </summary>
125        /// <remarks>Cloning the set takes time O(N), where N is the number of items in the set.</remarks>
126        /// <returns>The cloned set.</returns>
127        public Set<T> Clone()
128        {
129            Set<T> newSet = new Set<T>(equalityComparer, hash.Clone(null));
130            return newSet; 
131        }
132
133        /// <summary>
134        /// Makes a deep clone of this set. A new set is created with a clone of
135        /// each element of this set, by calling ICloneable.Clone on each element. If T is
136        /// a value type, then each element is copied as if by simple assignment.
137        /// </summary>
138        /// <remarks><para>If T is a reference type, it must implement
139        /// ICloneable. Otherwise, an InvalidOperationException is thrown.</para>
140        /// <para>Cloning the set takes time O(N), where N is the number of items in the set.</para></remarks>
141        /// <returns>The cloned set.</returns>
142        /// <exception cref="InvalidOperationException">T is a reference type that does not implement ICloneable.</exception>
143        public Set<T> CloneContents()
144        {
145            bool itemIsValueType;
146            if (!Util.IsCloneableType(typeof(T), out itemIsValueType))
147                throw new InvalidOperationException(string.Format(Strings.TypeNotCloneable, typeof(T).FullName));
148
149            Set<T> clone = new Set<T>(equalityComparer);
150
151            // Clone each item, and add it to the new ordered set.
152            foreach (T item in this) {
153                T itemClone;
154
155                if (itemIsValueType)
156                    itemClone = item;
157                else {
158                    if (item == null)
159                        itemClone = default(T);    // Really null, because we know T is a reference type
160                    else
161                        itemClone = (T)(((ICloneable)item).Clone());
162                }
163
164                clone.Add(itemClone);
165            }
166
167            return clone;
168        }
169
170        #endregion Cloning
171
172        #region Basic collection containment
173
174        /// <summary>
175        /// Returns the IEqualityComparer&lt;T&gt; used to compare items in this set.
176        /// </summary>
177        /// <value>If the set was created using a comparer, that comparer is returned. Otherwise
178        /// the default comparer for T (EqualityComparer&lt;T&gt;.Default) is returned.</value>
179        public IEqualityComparer<T> Comparer
180        {
181            get
182            {
183                return this.equalityComparer;
184            }
185        }
186
187        /// <summary>
188        /// Returns the number of items in the set.
189        /// </summary>
190        /// <remarks>The size of the set is returned in constant time.</remarks>
191        /// <value>The number of items in the set.</value>
192        public sealed override int Count
193        {
194            get
195            {
196                return hash.ElementCount;
197            }
198        }
199
200        /// <summary>
201        /// Returns an enumerator that enumerates all the items in the set.
202        /// The items are enumerated in sorted order.
203        /// </summary>
204        /// <remarks>
205        /// <p>Typically, this method is not called directly. Instead the "foreach" statement is used
206        /// to enumerate the items, which uses this method implicitly.</p>
207        /// <p>If an item is added to or deleted from the set while it is being enumerated, then
208        /// the enumeration will end with an InvalidOperationException.</p>
209        /// <p>Enumerating all the items in the set takes time O(N), where N is the number
210        /// of items in the set.</p>
211        /// </remarks>
212        /// <returns>An enumerator for enumerating all the items in the Set.</returns>         
213        public sealed override IEnumerator<T> GetEnumerator()
214        {
215            return hash.GetEnumerator();
216        }
217
218        /// <summary>
219        /// Determines if this set contains an item equal to <paramref name="item"/>. The set
220        /// is not changed.
221        /// </summary>
222        /// <remarks>Searching the set for an item takes approximately constant time, regardless of the number of items in the set.</remarks>
223        /// <param name="item">The item to search for.</param>
224        /// <returns>True if the set contains <paramref name="item"/>. False if the set does not contain <paramref name="item"/>.</returns>
225        public sealed override bool Contains(T item)
226        {
227            T dummy;
228            return hash.Find(item, false, out dummy);
229        }
230
231        /// <summary>
232        /// <para>Determines if this set contains an item equal to <paramref name="item"/>, according to the
233        /// comparison mechanism that was used when the set was created. The set
234        /// is not changed.</para>
235        /// <para>If the set does contain an item equal to <paramref name="item"/>, then the item from the set is returned.</para>
236        /// </summary>
237        /// <remarks>Searching the set for an item takes approximately constant time, regardless of the number of items in the set.</remarks>
238        /// <example>
239        /// In the following example, the set contains strings which are compared in a case-insensitive manner.
240        /// <code>
241        /// Set&lt;string&gt; set = new Set&lt;string&gt;(StringComparer.CurrentCultureIgnoreCase);
242        /// set.Add("HELLO");
243        /// string s;
244        /// bool b = set.TryGetItem("Hello", out s);   // b receives true, s receives "HELLO".
245        /// </code>
246        /// </example>
247        /// <param name="item">The item to search for.</param>
248        /// <param name="foundItem">Returns the item from the set that was equal to <paramref name="item"/>.</param>
249        /// <returns>True if the set contains <paramref name="item"/>. False if the set does not contain <paramref name="item"/>.</returns>
250        public bool TryGetItem(T item, out T foundItem)
251        {
252            return hash.Find(item, false, out foundItem);
253        }
254
255        #endregion
256
257        #region Adding elements
258
259        /// <summary>
260        /// Adds a new item to the set. If the set already contains an item equal to
261        /// <paramref name="item"/>, that item is replaced with <paramref name="item"/>.
262        /// </summary>
263        /// <remarks>
264        /// <para>Equality between items is determined by the comparison instance or delegate used
265        /// to create the set.</para>
266        /// <para>Adding an item takes approximately constant time, regardless of the number of items in the set.</para></remarks>
267        /// <param name="item">The item to add to the set.</param>
268        /// <returns>True if the set already contained an item equal to <paramref name="item"/> (which was replaced), false
269        /// otherwise.</returns>
270        public new bool Add(T item)
271        {
272            T dummy;
273            return !hash.Insert(item, true, out dummy);
274        }
275
276        /// <summary>
277        /// Adds a new item to the set. If the set already contains an item equal to
278        /// <paramref name="item"/>, that item is replaced with <paramref name="item"/>.
279        /// </summary>
280        /// <remarks>
281        /// <para>Equality between items is determined by the comparison instance or delegate used
282        /// to create the set.</para>
283        /// <para>Adding an item takes approximately constant time, regardless of the number of items in the set.</para></remarks>
284        /// <param name="item">The item to add to the set.</param>
285        /// <returns>True if the set already contained an item equal to <paramref name="item"/> (which was replaced), false
286        /// otherwise.</returns>
287        void ICollection<T>.Add(T item)
288        {
289            Add(item);
290        }
291
292        /// <summary>
293        /// Adds all the items in <paramref name="collection"/> to the set. If the set already contains an item equal to
294        /// one of the items in <paramref name="collection"/>, that item will be replaced.
295        /// </summary>
296        /// <remarks>
297        /// <para>Equality between items is determined by the comparison instance or delegate used
298        /// to create the set.</para>
299        /// <para>Adding the collection takes time O(M), where M is the
300        /// number of items in <paramref name="collection"/>.</para></remarks>
301        /// <param name="collection">A collection of items to add to the set.</param>
302        public void AddMany(IEnumerable<T> collection)
303        {
304            if (collection == null)
305                throw new ArgumentNullException("collection");
306
307            // If we're adding ourselves, then there is nothing to do.
308            if (object.ReferenceEquals(collection, this))
309                return;
310
311            foreach (T item in collection)
312                Add(item);
313        }
314
315        #endregion Adding elements
316
317        #region Removing elements
318
319        /// <summary>
320        /// Searches the set for an item equal to <paramref name="item"/>, and if found,
321        /// removes it from the set. If not found, the set is unchanged.
322        /// </summary>
323        /// <remarks>
324        /// <para>Equality between items is determined by the comparison instance or delegate used
325        /// to create the set.</para>
326        /// <para>Removing an item from the set takes approximately constant time, regardless of the size of the set.</para></remarks>
327        /// <param name="item">The item to remove.</param>
328        /// <returns>True if <paramref name="item"/> was found and removed. False if <paramref name="item"/> was not in the set.</returns>
329        public sealed override bool Remove(T item)
330        {
331            T dummy;
332            return hash.Delete(item, out dummy);
333        }
334
335        /// <summary>
336        /// Removes all the items in <paramref name="collection"/> from the set.
337        /// </summary>
338        /// <remarks>
339        /// <para>Equality between items is determined by the comparison instance or delegate used
340        /// to create the set.</para>
341        /// <para>Removing the collection takes time O(M), where M is the
342        /// number of items in <paramref name="collection"/>.</para></remarks>
343        /// <param name="collection">A collection of items to remove from the set.</param>
344        /// <returns>The number of items removed from the set.</returns>
345        /// <exception cref="ArgumentNullException"><paramref name="collection"/> is null.</exception>
346        public int RemoveMany(IEnumerable<T> collection)
347        {
348            if (collection == null)
349                throw new ArgumentNullException("collection");
350
351            int count = 0;
352
353            if (collection == this) {
354                count = Count;
355                Clear();            // special case, otherwise we will throw.
356            }
357            else {
358                foreach (T item in collection) {
359                    if (Remove(item))
360                        ++count;
361                }
362            }
363
364            return count;
365        }
366
367        /// <summary>
368        /// Removes all items from the set.
369        /// </summary>
370        /// <remarks>Clearing the set takes a constant amount of time, regardless of the number of items in it.</remarks>
371        public sealed override void Clear()
372        {
373            hash.StopEnumerations();  // Invalidate any enumerations.
374
375            // The simplest and fastest way is simply to throw away the old tree and create a new one.
376            hash = new Hash<T>(equalityComparer);
377        }
378
379        #endregion Removing elements
380
381        #region Set operations
382
383        /// <summary>
384        /// Check that this set and another set were created with the same comparison
385        /// mechanism. Throws exception if not compatible.
386        /// </summary>
387        /// <param name="otherSet">Other set to check comparision mechanism.</param>
388        /// <exception cref="InvalidOperationException">If otherSet and this set don't use the same method for comparing items.</exception>
389        private void CheckConsistentComparison(Set<T> otherSet)
390        {
391            if (otherSet == null)
392                throw new ArgumentNullException("otherSet");
393
394            if (!object.Equals(equalityComparer, otherSet.equalityComparer))
395                throw new InvalidOperationException(Strings.InconsistentComparisons);
396        }
397
398        /// <summary>
399        /// Determines if this set is a superset of another set. Neither set is modified.
400        /// This set is a superset of <paramref name="otherSet"/> if every element in
401        /// <paramref name="otherSet"/> is also in this set.
402        /// <remarks>IsSupersetOf is computed in time O(M), where M is the size of the
403        /// <paramref name="otherSet"/>.</remarks>
404        /// </summary>
405        /// <param name="otherSet">Set to compare to.</param>
406        /// <returns>True if this is a superset of <paramref name="otherSet"/>.</returns>
407        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
408        public bool IsSupersetOf(Set<T> otherSet)
409        {
410            CheckConsistentComparison(otherSet);
411
412            if (otherSet.Count > this.Count)
413                return false;     // Can't be a superset of a bigger set
414
415            // Check each item in the other set to make sure it is in this set.
416            foreach (T item in otherSet) {
417                if (!this.Contains(item))
418                    return false;
419            }
420
421            return true; 
422        }
423
424        /// <summary>
425        /// Determines if this set is a proper superset of another set. Neither set is modified.
426        /// This set is a proper superset of <paramref name="otherSet"/> if every element in
427        /// <paramref name="otherSet"/> is also in this set.
428        /// Additionally, this set must have strictly more items than <paramref name="otherSet"/>.
429        /// </summary>
430        /// <remarks>IsProperSubsetOf is computed in time O(M), where M is the size of
431        /// <paramref name="otherSet"/>.</remarks>
432        /// <param name="otherSet">Set to compare to.</param>
433        /// <returns>True if this is a proper superset of <paramref name="otherSet"/>.</returns>
434        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
435        public bool IsProperSupersetOf(Set<T> otherSet)
436        {
437            CheckConsistentComparison(otherSet);
438
439            if (otherSet.Count >= this.Count)
440                return false;     // Can't be a proper superset of a bigger or equal set
441
442            return IsSupersetOf(otherSet);
443        }
444
445        /// <summary>
446        /// Determines if this set is a subset of another set. Neither set is modified.
447        /// This set is a subset of <paramref name="otherSet"/> if every element in this set
448        /// is also in <paramref name="otherSet"/>.
449        /// </summary>
450        /// <remarks>IsSubsetOf is computed in time O(N), where N is the size of the this set.</remarks>
451        /// <param name="otherSet">Set to compare to.</param>
452        /// <returns>True if this is a subset of <paramref name="otherSet"/>.</returns>
453        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
454        public bool IsSubsetOf(Set<T> otherSet)
455        {
456            return otherSet.IsSupersetOf(this);
457        }
458
459        /// <summary>
460        /// Determines if this set is a proper subset of another set. Neither set is modified.
461        /// This set is a subset of <paramref name="otherSet"/> if every element in this set
462        /// is also in <paramref name="otherSet"/>. Additionally, this set must have strictly
463        /// fewer items than <paramref name="otherSet"/>.
464        /// </summary>
465        /// <remarks>IsProperSubsetOf is computed in time O(N), where N is the size of the this set.</remarks>
466        /// <param name="otherSet">Set to compare to.</param>
467        /// <returns>True if this is a proper subset of <paramref name="otherSet"/>.</returns>
468        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
469        public bool IsProperSubsetOf(Set<T> otherSet)
470        {
471            return otherSet.IsProperSupersetOf(this);
472        }
473
474        /// <summary>
475        /// Determines if this set is equal to another set. This set is equal to
476        /// <paramref name="otherSet"/> if they contain the same items.
477        /// </summary>
478        /// <remarks>IsEqualTo is computed in time O(N), where N is the number of items in
479        /// this set.</remarks>
480        /// <param name="otherSet">Set to compare to</param>
481        /// <returns>True if this set is equal to <paramref name="otherSet"/>, false otherwise.</returns>
482        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
483        public bool IsEqualTo(Set<T> otherSet)
484        {
485            CheckConsistentComparison(otherSet);
486
487            // Must be the same size.
488            if (otherSet.Count != this.Count)
489                return false;
490
491            // Check each item in the other set to make sure it is in this set.
492            foreach (T item in otherSet) {
493                if (!this.Contains(item))
494                    return false;
495            }
496
497            return true;
498        }
499
500        /// <summary>
501        /// Determines if this set is disjoint from another set. Two sets are disjoint
502        /// if no item from one set is equal to any item in the other set.
503        /// </summary>
504        /// <remarks>
505        /// <para>The answer is computed in time O(N), where N is the size of the smaller set.</para>
506        /// </remarks>
507        /// <param name="otherSet">Set to check disjointness with.</param>
508        /// <returns>True if the two sets are disjoint, false otherwise.</returns>
509        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
510        public bool IsDisjointFrom(Set<T> otherSet)
511        {
512            CheckConsistentComparison(otherSet);
513            Set<T> smaller, larger;
514            if (otherSet.Count > this.Count) {
515                smaller = this; larger = otherSet;
516            }
517            else {
518                smaller = otherSet; larger = this;
519            }
520
521            foreach (T item in smaller) {
522                if (larger.Contains(item))
523                    return false;
524            }
525
526            return true;
527        }
528
529        /// <summary>
530        /// Computes the union of this set with another set. The union of two sets
531        /// is all items that appear in either or both of the sets. This set receives
532        /// the union of the two sets, the other set is unchanged.
533        /// </summary>
534        /// <remarks>
535        /// <para>If equal items appear in both sets, the union will include an arbitrary choice of one of the
536        /// two equal items.</para>
537        /// <para>The union of two sets is computed in time O(M + N), where M is the size of the
538        /// larger set, and N is the size of the smaller set.</para>
539        /// </remarks>
540        /// <param name="otherSet">Set to union with.</param>
541        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
542        public void UnionWith(Set<T> otherSet)
543        {
544            CheckConsistentComparison(otherSet);
545
546            AddMany(otherSet);
547        }
548
549        /// <summary>
550        /// Computes the union of this set with another set. The union of two sets
551        /// is all items that appear in either or both of the sets. A new set is
552        /// created with the union of the sets and is returned. This set and the other set
553        /// are unchanged.
554        /// </summary>
555        /// <remarks>
556        /// <para>If equal items appear in both sets, the union will include an arbitrary choice of one of the
557        /// two equal items.</para>
558        /// <para>The union of two sets is computed in time O(M + N), where M is the size of the
559        /// one set, and N is the size of the other set.</para>
560        /// </remarks>
561        /// <param name="otherSet">Set to union with.</param>
562        /// <returns>The union of the two sets.</returns>
563        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
564        public Set<T> Union(Set<T> otherSet)
565        {
566            CheckConsistentComparison(otherSet);
567            Set<T> smaller, larger, result;
568            if (otherSet.Count > this.Count) {
569                smaller = this; larger = otherSet;
570            }
571            else {
572                smaller = otherSet; larger = this;
573            }
574
575            result = larger.Clone();
576            result.AddMany(smaller);
577            return result; 
578        }
579
580        /// <summary>
581        /// Computes the intersection of this set with another set. The intersection of two sets
582        /// is all items that appear in both of the sets. This set receives
583        /// the intersection of the two sets, the other set is unchanged.
584        /// </summary>
585        /// <remarks>
586        /// <para>When equal items appear in both sets, the intersection will include an arbitrary choice of one of the
587        /// two equal items.</para>
588        /// <para>The intersection of two sets is computed in time O(N), where N is the size of the smaller set.</para>
589        /// </remarks>
590        /// <param name="otherSet">Set to intersection with.</param>
591        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
592        public void IntersectionWith(Set<T> otherSet)
593        {
594            CheckConsistentComparison(otherSet);
595            hash.StopEnumerations();
596
597            Set<T> smaller, larger;
598            if (otherSet.Count > this.Count) {
599                smaller = this; larger = otherSet;
600            }
601            else {
602                smaller = otherSet; larger = this;
603            }
604
605            T dummy;
606            Hash<T> newHash = new Hash<T>(equalityComparer);
607
608            foreach (T item in smaller) {
609                if (larger.Contains(item))
610                    newHash.Insert(item, true, out dummy);
611            }
612
613            hash = newHash;
614        }
615
616        /// <summary>
617        /// Computes the intersection of this set with another set. The intersection of two sets
618        /// is all items that appear in both of the sets. A new set is
619        /// created with the intersection of the sets and is returned. This set and the other set
620        /// are unchanged.
621        /// </summary>
622        /// <remarks>
623        /// <para>When equal items appear in both sets, the intersection will include an arbitrary choice of one of the
624        /// two equal items.</para>
625        /// <para>The intersection of two sets is computed in time O(N), where N is the size of the smaller set.</para>
626        /// </remarks>
627        /// <param name="otherSet">Set to intersection with.</param>
628        /// <returns>The intersection of the two sets.</returns>
629        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
630        public Set<T> Intersection(Set<T> otherSet)
631        {
632            CheckConsistentComparison(otherSet);
633            Set<T> smaller, larger, result;
634            if (otherSet.Count > this.Count) {
635                smaller = this; larger = otherSet;
636            }
637            else {
638                smaller = otherSet; larger = this;
639            }
640
641            result = new Set<T>(equalityComparer);
642            foreach (T item in smaller) {
643                if (larger.Contains(item))
644                    result.Add(item);
645            }
646
647            return result; 
648        }
649
650        /// <summary>
651        /// Computes the difference of this set with another set. The difference of these two sets
652        /// is all items that appear in this set, but not in <paramref name="otherSet"/>. This set receives
653        /// the difference of the two sets; the other set is unchanged.
654        /// </summary>
655        /// <remarks>
656        /// <para>The difference of two sets is computed in time O(N), where N is the size of the smaller set.</para>
657        /// </remarks>
658        /// <param name="otherSet">Set to difference with.</param>
659        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
660        public void DifferenceWith(Set<T> otherSet)
661        {
662            // Difference with myself is nothing. This check is needed because the
663            // main algorithm doesn't work correctly otherwise.
664            if (this == otherSet)
665                Clear();
666
667            CheckConsistentComparison(otherSet);
668
669            if (otherSet.Count < this.Count) {
670                foreach (T item in otherSet) {
671                    this.Remove(item);
672                }
673            }
674            else {
675                RemoveAll(delegate(T item) { return otherSet.Contains(item); });
676            }
677        }
678
679        /// <summary>
680        /// Computes the difference of this set with another set. The difference of these two sets
681        /// is all items that appear in this set, but not in <paramref name="otherSet"/>. A new set is
682        /// created with the difference of the sets and is returned. This set and the other set
683        /// are unchanged.
684        /// </summary>
685        /// <remarks>
686        /// <para>The difference of two sets is computed in time O(N), where N is the size of the smaller set.</para>
687        /// </remarks>
688        /// <param name="otherSet">Set to difference with.</param>
689        /// <returns>The difference of the two sets.</returns>
690        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
691        public Set<T> Difference(Set<T> otherSet)
692        {
693            CheckConsistentComparison(otherSet);
694            Set<T> result = this.Clone();
695            result.DifferenceWith(otherSet);
696            return result; 
697        }
698
699        /// <summary>
700        /// Computes the symmetric difference of this set with another set. The symmetric difference of two sets
701        /// is all items that appear in either of the sets, but not both. This set receives
702        /// the symmetric difference of the two sets; the other set is unchanged.
703        /// </summary>
704        /// <remarks>
705        /// <para>The symmetric difference of two sets is computed in time O(N), where N is the size of the smaller set.</para>
706        /// </remarks>
707        /// <param name="otherSet">Set to symmetric difference with.</param>
708        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
709        public void SymmetricDifferenceWith(Set<T> otherSet)
710        {
711            // main algorithm doesn't work correctly otherwise.
712            if (this == otherSet)
713                Clear();
714
715            CheckConsistentComparison(otherSet);
716
717            if (otherSet.Count > this.Count) {
718                hash.StopEnumerations();
719                Hash<T> newHash = otherSet.hash.Clone(null);
720                T dummy;
721
722                foreach (T item in this) {
723                    if (newHash.Find(item, false, out dummy))
724                        newHash.Delete(item, out dummy);
725                    else
726                        newHash.Insert(item, true, out dummy);
727                }
728                this.hash = newHash;
729            }
730            else {
731                foreach (T item in otherSet) {
732                    if (this.Contains(item))
733                        this.Remove(item);
734                    else
735                        this.Add(item);
736                }
737            }
738        }
739
740        /// <summary>
741        /// Computes the symmetric difference of this set with another set. The symmetric difference of two sets
742        /// is all items that appear in either of the sets, but not both. A new set is
743        /// created with the symmetric difference of the sets and is returned. This set and the other set
744        /// are unchanged.
745        /// </summary>
746        /// <remarks>
747        /// <para>The symmetric difference of two sets is computed in time O(N), where N is the size of the smaller set.</para>
748        /// </remarks>
749        /// <param name="otherSet">Set to symmetric difference with.</param>
750        /// <returns>The symmetric difference of the two sets.</returns>
751        /// <exception cref="InvalidOperationException">This set and <paramref name="otherSet"/> don't use the same method for comparing items.</exception>
752        public Set<T> SymmetricDifference(Set<T> otherSet)
753        {
754            CheckConsistentComparison(otherSet);
755            Set<T> smaller, larger, result;
756            if (otherSet.Count > this.Count) {
757                smaller = this; larger = otherSet;
758            }
759            else {
760                smaller = otherSet; larger = this;
761            }
762
763            result = larger.Clone();
764            foreach (T item in smaller) {
765                if (result.Contains(item))
766                    result.Remove(item);
767                else
768                    result.Add(item);
769            }
770
771            return result;
772        }
773
774        #endregion Set operations
775
776    }
777}
Note: See TracBrowser for help on using the repository browser.