source: trunk/CrypPlugins/WorkspaceManager/View/VisualComponents/CryptoLineView/PowerCollections/Bag.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: 46.5 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
12
13namespace Wintellect.PowerCollections
14{
15    /// <summary>
16    /// Bag&lt;T&gt; is a collection that contains items of type T.
17    /// Unlike a Set, duplicate items (items that compare equal to each other) are allowed in an Bag.
18    /// </summary>
19    /// <remarks>
20    /// <p>The items are compared in one of two ways. If T implements IComparable&lt;T&gt;
21    /// then the Equals method of that interface will be used to compare items, otherwise the Equals
22    /// method from Object will be used. Alternatively, an instance of IComparer&lt;T&gt; can be passed
23    /// to the constructor to use to compare items.</p>
24    /// <p>Bag is implemented as a hash table. Inserting, deleting, and looking up an
25    /// an element all are done in approximately constant time, regardless of the number of items in the bag.</p>
26    /// <p>When multiple equal items are stored in the bag, they are stored as a representative item and a count.
27    /// If equal items can be distinguished, this may be noticable. For example, if a case-insensitive
28    /// comparer is used with a Bag&lt;string&gt;, and both "hello", and "HELLO" are added to the bag, then the
29    /// bag will appear to contain two copies of "hello" (the representative item).</p>
30    /// <p><see cref="OrderedBag&lt;T&gt;"/> is similar, but uses comparison instead of hashing, maintain
31    /// the items in sorted order, and stores distinct copies of items that compare equal.</p>
32    ///</remarks>
33    ///<seealso cref="OrderedBag&lt;T&gt;"/>
34    [Serializable]
35    public class Bag<T> : CollectionBase<T>, ICloneable
36    {
37        // The comparer used to compare KeyValuePairs. Equals and GetHashCode are used.
38        private readonly IEqualityComparer<KeyValuePair<T,int>> equalityComparer;
39
40        // The comparer used to compare items. Kept just for the Comparer property.
41        private readonly IEqualityComparer<T> keyEqualityComparer;
42
43        // The hash that actually does the work of storing the items. Each item is
44        // stored as a representative item, and a count.
45        private Hash<KeyValuePair<T, int>> hash;   
46
47        // The total number of items stored in the bag.
48        private int count;
49
50        /// <summary>
51        /// Helper function to create a new KeyValuePair struct with an item and a count.
52        /// </summary>
53        /// <param name="item">The item.</param>
54        /// <param name="count">The number of appearances.</param>
55        /// <returns>A new KeyValuePair.</returns>
56        private static KeyValuePair<T, int> NewPair(T item, int count)
57        {
58            KeyValuePair<T, int> pair = new KeyValuePair<T,int>(item, count);
59            return pair;
60        }
61
62        /// <summary>
63        /// Helper function to create a new KeyValuePair struct with a count of zero.
64        /// </summary>
65        /// <param name="item">The item.</param>
66        /// <returns>A new KeyValuePair.</returns>
67        private static KeyValuePair<T, int> NewPair(T item)
68        {
69            KeyValuePair<T, int> pair = new KeyValuePair<T, int>(item, 0);
70            return pair;
71        }
72
73        #region Constructors
74
75        /// <summary>
76        /// Creates a new Bag.
77        /// </summary>
78        ///<remarks>
79        /// Items that are null are permitted.
80        ///</remarks>
81        public Bag(): 
82            this(EqualityComparer<T>.Default)
83        {
84        }
85
86        /// <summary>
87        /// Creates a new Bag. The Equals and GetHashCode methods of the passed comparison object
88        /// will be used to compare items in this bag for equality.
89        /// </summary>
90        /// <param name="equalityComparer">An instance of IEqualityComparer&lt;T&gt; that will be used to compare items.</param>
91        public Bag(IEqualityComparer<T> equalityComparer)
92        {
93            if (equalityComparer == null)
94                throw new ArgumentNullException("equalityComparer");
95
96            this.keyEqualityComparer = equalityComparer;
97            this.equalityComparer = Comparers.EqualityComparerKeyValueFromComparerKey<T, int>(equalityComparer);
98            this.hash = new Hash<KeyValuePair<T, int>>(this.equalityComparer);
99        }
100
101        /// <summary>
102        /// Creates a new Bag. The bag is
103        /// initialized with all the items in the given collection.
104        /// </summary>
105        ///<remarks>
106        /// Items that are null are permitted.
107        ///</remarks>
108        /// <param name="collection">A collection with items to be placed into the Bag.</param>
109        public Bag(IEnumerable<T> collection): 
110            this(collection, EqualityComparer<T>.Default)
111        {
112        }
113
114        /// <summary>
115        /// Creates a new Bag. The Equals and GetHashCode methods of the passed comparison object
116        /// will be used to compare items in this bag. The bag is
117        /// initialized with all the items in the given collection.
118        /// </summary>
119        /// <param name="collection">A collection with items to be placed into the Bag.</param>
120        /// <param name="equalityComparer">An instance of IEqualityComparer&lt;T&gt; that will be used to compare items.</param>
121        public Bag(IEnumerable<T> collection, IEqualityComparer<T> equalityComparer)
122            : this(equalityComparer)
123        {
124            AddMany(collection);
125        }
126
127        /// <summary>
128        /// Creates a new Bag given a comparer and a hash that contains the data. Used
129        /// internally for Clone.
130        /// </summary>
131        /// <param name="equalityComparer">IEqualityComparer for the bag.</param>
132        /// <param name="keyEqualityComparer">IEqualityComparer for the key.</param>
133        /// <param name="hash">Data for the bag.</param>
134        /// <param name="count">Size of the bag.</param>
135        private Bag(IEqualityComparer<KeyValuePair<T, int>> equalityComparer, IEqualityComparer<T> keyEqualityComparer, Hash<KeyValuePair<T,int>> hash, int count)
136        {
137            this.equalityComparer = equalityComparer;
138            this.keyEqualityComparer = keyEqualityComparer;
139            this.hash = hash;
140            this.count = count;
141        }
142
143        #endregion Constructors
144
145        #region Cloning
146
147        /// <summary>
148        /// Makes a shallow clone of this bag; i.e., if items of the
149        /// bag are reference types, then they are not cloned. If T is a value type,
150        /// then each element is copied as if by simple assignment.
151        /// </summary>
152        /// <remarks>Cloning the bag takes time O(N), where N is the number of items in the bag.</remarks>
153        /// <returns>The cloned bag.</returns>
154        object ICloneable.Clone()
155        {
156            return this.Clone();
157        }
158
159        /// <summary>
160        /// Makes a shallow clone of this bag; i.e., if items of the
161        /// bag are reference types, then they are not cloned. If T is a value type,
162        /// then each element is copied as if by simple assignment.
163        /// </summary>
164        /// <remarks>Cloning the bag takes time O(N), where N is the number of unquie items in the bag.</remarks>
165        /// <returns>The cloned bag.</returns>
166        public Bag<T> Clone()
167        {
168            Bag<T> newBag = new Bag<T>(equalityComparer, keyEqualityComparer, hash.Clone(null), count);
169            return newBag;
170        }
171
172        /// <summary>
173        /// Makes a deep clone of this bag. A new bag is created with a clone of
174        /// each element of this bag, by calling ICloneable.Clone on each element. If T is
175        /// a value type, then each element is copied as if by simple assignment.
176        /// </summary>
177        /// <remarks><para>If T is a reference type, it must implement
178        /// ICloneable. Otherwise, an InvalidOperationException is thrown.</para>
179        /// <para>Cloning the bag takes time O(N log N), where N is the number of items in the bag.</para></remarks>
180        /// <returns>The cloned bag.</returns>
181        /// <exception cref="InvalidOperationException">T is a reference type that does not implement ICloneable.</exception>
182        public Bag<T> CloneContents()
183        {
184            bool itemIsValueType;
185            if (!Util.IsCloneableType(typeof(T), out itemIsValueType))
186                throw new InvalidOperationException(string.Format(Strings.TypeNotCloneable, typeof(T).FullName));
187
188            Hash<KeyValuePair<T,int>> newHash = new Hash<KeyValuePair<T,int>>(equalityComparer);
189
190            // Clone each item, and add it to the new ordered bag.
191            foreach (KeyValuePair<T, int> pair in hash) {
192                KeyValuePair<T, int> newPair, dummy;
193                T newKey;
194
195                if (!itemIsValueType && pair.Key != null)
196                    newKey = (T)(((ICloneable)pair.Key).Clone());
197                else
198                    newKey = pair.Key;
199
200                newPair = NewPair(newKey, pair.Value);
201
202                newHash.Insert(newPair, true, out dummy);
203            }
204
205            return new Bag<T>(equalityComparer, keyEqualityComparer, newHash, count); 
206        }
207
208        #endregion Cloning
209
210        #region Basic collection containment
211
212        /// <summary>
213        /// Returns the IEqualityComparer&lt;T&gt; used to compare items in this bag.
214        /// </summary>
215        /// <value>If the bag was created using a comparer, that comparer is returned. Otherwise
216        /// the default comparer for T (EqualityComparer&lt;T&gt;.Default) is returned.</value>
217        public IEqualityComparer<T> Comparer
218        {
219            get
220            {
221                return keyEqualityComparer;
222            }
223        }
224
225        /// <summary>
226        /// Returns the number of items in the bag.
227        /// </summary>
228        /// <remarks>The size of the bag is returned in constant time.</remarks>
229        /// <value>The number of items in the bag.</value>
230        public sealed override int Count
231        {
232            get
233            {
234                return count;
235            }
236        }
237
238        /// <summary>
239        /// Returns the number of copies of <paramref name="item"/> in the bag.
240        /// </summary>
241        /// <remarks>NumberOfCopies() takes approximately constant time, no matter how many items
242        /// are stored in the bag.</remarks>
243        /// <param name="item">The item to search for in the bag.</param>
244        /// <returns>The number of items in the bag that compare equal to <paramref name="item"/>.</returns>
245        public int NumberOfCopies(T item)
246        {
247            KeyValuePair<T, int> foundPair;
248            if (hash.Find(NewPair(item), false, out foundPair)) 
249                return foundPair.Value;
250            else
251                return 0;
252        }
253
254        /// <summary>
255        /// Returns the representative item stored in the bag that is equal to
256        /// the provided item. Also returns the number of copies of the item in the bag.
257        /// </summary>
258        /// <param name="item">Item to find in the bag.</param>
259        /// <param name="representative">If one or more items equal to <paramref name="item"/> are present in the
260        /// bag, returns the representative item. If no items equal to <paramref name="item"/> are stored in the bag,
261        /// returns <paramref name="item"/>.</param>
262        /// <returns>The number of items equal to <paramref name="item"/> stored in the bag.</returns>
263        public int GetRepresentativeItem(T item, out T representative)
264        {
265            KeyValuePair<T, int> foundPair;
266            if (hash.Find(NewPair(item), false, out foundPair)) {
267                representative = foundPair.Key;
268                return foundPair.Value;
269            }
270            else {
271                representative = item;
272                return 0;
273            }
274        }
275
276        /// <summary>
277        /// Returns an enumerator that enumerates all the items in the bag.
278        /// If an item is present multiple times in the bag, the representative item is yielded by the
279        /// enumerator multiple times. The order of enumeration is haphazard and may change.
280        /// </summary>
281        /// <remarks>
282        /// <p>Typically, this method is not called directly. Instead the "foreach" statement is used
283        /// to enumerate the items, which uses this method implicitly.</p>
284        /// <p>If an item is added to or deleted from the bag while it is being enumerated, then
285        /// the enumeration will end with an InvalidOperationException.</p>
286        /// <p>Enumeration all the items in the bag takes time O(N), where N is the number
287        /// of items in the bag.</p>
288        /// </remarks>
289        /// <returns>An enumerator for enumerating all the items in the Bag.</returns>         
290        public sealed override IEnumerator<T> GetEnumerator()
291        {
292            foreach (KeyValuePair<T, int> pair in hash) {
293                for (int i = 0; i < pair.Value; ++i)
294                    yield return pair.Key;
295            }
296        }
297
298        /// <summary>
299        /// Determines if this bag contains an item equal to <paramref name="item"/>. The bag
300        /// is not changed.
301        /// </summary>
302        /// <remarks>Searching the bag for an item takes time O(log N), where N is the number of items in the bag.</remarks>
303        /// <param name="item">The item to search for.</param>
304        /// <returns>True if the bag contains <paramref name="item"/>. False if the bag does not contain <paramref name="item"/>.</returns>
305        public sealed override bool Contains(T item)
306        {
307            KeyValuePair<T, int> dummy;
308            return hash.Find(NewPair(item), false, out dummy);
309        }
310
311        /// <summary>
312        /// Enumerates all the items in the bag, but enumerates equal items
313        /// just once, even if they occur multiple times in the bag.
314        /// </summary>
315        /// <remarks>If the bag is changed while items are being enumerated, the
316        /// enumeration will terminate with an InvalidOperationException.</remarks>
317        /// <returns>An IEnumerable&lt;T&gt; that enumerates the unique items.</returns>
318        public IEnumerable<T> DistinctItems()
319        {
320            foreach (KeyValuePair<T, int> pair in hash) {
321                yield return pair.Key;
322            }
323        }
324
325        #endregion
326
327
328        #region Adding elements
329
330        /// <summary>
331        /// Adds a new item to the bag. Since bags can contain duplicate items, the item
332        /// is added even if the bag already contains an item equal to <paramref name="item"/>. In
333        /// this case, the count of items for the representative item is increased by one, but the existing
334        /// represetative item is unchanged.
335        /// </summary>
336        /// <remarks>
337        /// <para>Adding an item takes approximately constant time, regardless of the number of items in the bag.</para></remarks>
338        /// <param name="item">The item to add to the bag.</param>
339        public sealed override void Add(T item)
340        {
341            KeyValuePair<T, int> pair = NewPair(item, 1);
342            KeyValuePair<T, int> existing, newPair;
343            if (! hash.Insert(pair, false, out existing)) {
344                // The item already existed, so update the count instead.
345                newPair = NewPair(existing.Key, existing.Value + 1);
346                hash.Insert(newPair, true, out pair);
347            }
348            ++count;
349        }
350
351        // CONSIDER: add an example to the documentation below.
352        /// <summary>
353        /// Adds a new item to the bag. Since bags can contain duplicate items, the item
354        /// is added even if the bag already contains an item equal to <paramref name="item"/>. In
355        /// this case (unlike Add), the new item becomes the representative item.
356        /// </summary>
357        /// <remarks>
358        /// <para>Adding an item takes approximately constant time, regardless of the number of items in the bag.</para></remarks>
359        /// <param name="item">The item to add to the bag.</param>
360        public void AddRepresentative(T item)
361        {
362            KeyValuePair<T, int> pair = NewPair(item, 1);
363            KeyValuePair<T, int> existing, newPair;
364            if (!hash.Insert(pair, false, out existing)) {
365                // The item already existed, so update the count instead.
366                newPair = NewPair(pair.Key, existing.Value + 1);
367                hash.Insert(newPair, true, out pair);
368            }
369            ++count;
370        }
371
372        /// <summary>
373        /// Changes the number of copies of an existing item in the bag, or adds the indicated number
374        /// of copies of the item to the bag.
375        /// </summary>
376        /// <remarks>
377        /// <para>Changing the number of copies takes approximately constant time, regardless of the number of items in the bag.</para></remarks>
378        /// <param name="item">The item to change the number of copies of. This may or may not already be present in the bag.</param>
379        /// <param name="numCopies">The new number of copies of the item.</param>
380        public void ChangeNumberOfCopies(T item, int numCopies)
381        {
382            if (numCopies == 0)
383                RemoveAllCopies(item);
384            else {
385                KeyValuePair<T, int> dummy, existing, newPair;
386                if (hash.Find(NewPair(item), false, out existing)) {
387                    count += numCopies - existing.Value;
388                    newPair = NewPair(existing.Key, numCopies);
389                }
390                else {
391                    count += numCopies;
392                    newPair = NewPair(item, numCopies);
393                }
394                hash.Insert(newPair, true, out dummy);
395            }
396        }
397
398        /// <summary>
399        /// Adds all the items in <paramref name="collection"/> to the bag.
400        /// </summary>
401        /// <remarks>
402        /// <para>Adding the collection takes time O(M log N), where N is the number of items in the bag, and M is the
403        /// number of items in <paramref name="collection"/>.</para></remarks>
404        /// <param name="collection">A collection of items to add to the bag.</param>
405        public void AddMany(IEnumerable<T> collection)
406        {
407            if (collection == null)
408                throw new ArgumentNullException("collection");
409
410            // If we're adding ourselves, we need to copy to a separate array to avoid modification
411            // during enumeration.
412            if (this == collection)
413                collection = this.ToArray();
414
415            foreach (T item in collection)
416                Add(item);
417        }
418
419        #endregion Adding elements
420
421        #region Removing elements
422
423        /// <summary>
424        /// Searches the bag for one item equal to <paramref name="item"/>, and if found,
425        /// removes it from the bag. If not found, the bag is unchanged.
426        /// </summary>
427        /// <remarks>
428        /// <para>Equality between items is determined by the comparison instance or delegate used
429        /// to create the bag.</para>
430        /// <para>Removing an item from the bag takes approximated constant time,
431        /// regardless of the number of items in the bag.</para></remarks>
432        /// <param name="item">The item to remove.</param>
433        /// <returns>True if <paramref name="item"/> was found and removed. False if <paramref name="item"/> was not in the bag.</returns>
434        public sealed override bool Remove(T item)
435        {
436            KeyValuePair<T, int> removed, newPair;
437            if (hash.Delete(NewPair(item), out removed)) {
438                if (removed.Value > 1) {
439                    // Only want to remove one copied, so add back in with a reduced count.
440                    KeyValuePair<T, int> dummy;
441                    newPair = NewPair(removed.Key, removed.Value - 1);
442                    hash.Insert(newPair, true, out dummy);
443                }
444                --count;
445                return true;
446            }
447            else
448                return false;
449        }
450
451        /// <summary>
452        /// Searches the bag for all items equal to <paramref name="item"/>, and
453        /// removes all of them from the bag. If not found, the bag is unchanged.
454        /// </summary>
455        /// <remarks>
456        /// <para>Equality between items is determined by the comparer instance used
457        /// to create the bag.</para>
458        /// <para>RemoveAllCopies() takes time O(M log N), where N is the total number of items in the bag, and M is
459        /// the number of items equal to <paramref name="item"/>.</para></remarks>
460        /// <param name="item">The item to remove.</param>
461        /// <returns>The number of copies of <paramref name="item"/> that were found and removed. </returns>
462        public int RemoveAllCopies(T item)
463        {
464            KeyValuePair<T, int> removed;
465            if (hash.Delete(NewPair(item), out removed)) {
466                count -= removed.Value;
467                return removed.Value;
468            }
469            else
470                return 0;
471        }
472
473        /// <summary>
474        /// Removes all the items in <paramref name="collection"/> from the bag. Items that
475        /// are not present in the bag are ignored.
476        /// </summary>
477        /// <remarks>
478        /// <para>Equality between items is determined by the comparer instance used
479        /// to create the bag.</para>
480        /// <para>Removing the collection takes time O(M), where M is the
481        /// number of items in <paramref name="collection"/>.</para></remarks>
482        /// <param name="collection">A collection of items to remove from the bag.</param>
483        /// <returns>The number of items removed from the bag.</returns>
484        /// <exception cref="ArgumentNullException"><paramref name="collection"/> is null.</exception>
485        public int RemoveMany(IEnumerable<T> collection)
486        {
487            if (collection == null)
488                throw new ArgumentNullException("collection");
489
490            int removeCount = 0;
491
492            if (collection == this) {
493                removeCount = Count;
494                Clear();            // special case, otherwise we will throw.
495            }
496            else {
497                foreach (T item in collection) {
498                    if (Remove(item))
499                        ++removeCount;
500                }
501            }
502
503            return removeCount;
504        }
505
506        /// <summary>
507        /// Removes all items from the bag.
508        /// </summary>
509        /// <remarks>Clearing the bag takes a constant amount of time, regardless of the number of items in it.</remarks>
510        public sealed override void Clear()
511        {
512            hash.StopEnumerations();  // Invalidate any enumerations.
513
514            // The simplest and fastest way is simply to throw away the old hash and create a new one.
515            hash = new Hash<KeyValuePair<T, int>>(equalityComparer);
516            count = 0;
517        }
518
519        #endregion Removing elements
520
521        #region Set operations
522
523        /// <summary>
524        /// Check that this bag and another bag were created with the same comparison
525        /// mechanism. Throws exception if not compatible.
526        /// </summary>
527        /// <param name="otherBag">Other bag to check comparision mechanism.</param>
528        /// <exception cref="InvalidOperationException">If otherBag and this bag don't use the same method for comparing items.</exception>
529        private void CheckConsistentComparison(Bag<T> otherBag)
530        {
531            if (otherBag == null)
532                throw new ArgumentNullException("otherBag");
533
534            if (!object.Equals(equalityComparer, otherBag.equalityComparer))
535                throw new InvalidOperationException(Strings.InconsistentComparisons);
536        }
537
538        /// <summary>
539        /// Determines if this bag is equal to another bag. This bag is equal to
540        /// <paramref name="otherBag"/> if they contain the same number of
541        /// of copies of equal elements.
542        /// </summary>
543        /// <remarks>IsSupersetOf is computed in time O(N), where N is the number of unique items in
544        /// this bag.</remarks>
545        /// <param name="otherBag">Bag to compare to</param>
546        /// <returns>True if this bag is equal to <paramref name="otherBag"/>, false otherwise.</returns>
547        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
548        public bool IsEqualTo(Bag<T> otherBag)
549        {
550            CheckConsistentComparison(otherBag);
551
552            // Must be the same size.
553            if (otherBag.Count != this.Count)
554                return false;
555
556            // Check each item to make sure it is in this set the same number of times.
557            foreach (T item in otherBag.DistinctItems()) {
558                if (this.NumberOfCopies(item) != otherBag.NumberOfCopies(item))
559                    return false;
560            }
561
562            return true;
563        }
564
565        /// <summary>
566        /// Determines if this bag is a superset of another bag. Neither bag is modified.
567        /// This bag is a superset of <paramref name="otherBag"/> if every element in
568        /// <paramref name="otherBag"/> is also in this bag, at least the same number of
569        /// times.
570        /// </summary>
571        /// <remarks>IsSupersetOf is computed in time O(M), where M is the number of unique items in
572        /// <paramref name="otherBag"/>.</remarks>
573        /// <param name="otherBag">Bag to compare to.</param>
574        /// <returns>True if this is a superset of <paramref name="otherBag"/>.</returns>
575        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
576        public bool IsSupersetOf(Bag<T> otherBag)
577        {
578            CheckConsistentComparison(otherBag);
579
580            if (otherBag.Count > this.Count)
581                return false;     // Can't be a superset of a bigger set
582
583            // Check each item in the other set to make sure it is in this set.
584            foreach (T item in otherBag.DistinctItems()) {
585                if (this.NumberOfCopies(item) < otherBag.NumberOfCopies(item))
586                    return false;
587            }
588
589            return true;
590        }
591
592        /// <summary>
593        /// Determines if this bag is a proper superset of another bag. Neither bag is modified.
594        /// This bag is a proper superset of <paramref name="otherBag"/> if every element in
595        /// <paramref name="otherBag"/> is also in this bag, at least the same number of
596        /// times. Additional, this bag must have strictly more items than <paramref name="otherBag"/>.
597        /// </summary>
598        /// <remarks>IsProperSupersetOf is computed in time O(M), where M is the number of unique items in
599        /// <paramref name="otherBag"/>.</remarks>
600        /// <param name="otherBag">Set to compare to.</param>
601        /// <returns>True if this is a proper superset of <paramref name="otherBag"/>.</returns>
602        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
603        public bool IsProperSupersetOf(Bag<T> otherBag)
604        {
605            CheckConsistentComparison(otherBag);
606
607            if (otherBag.Count >= this.Count)
608                return false;     // Can't be a proper superset of a bigger or equal set
609
610            return IsSupersetOf(otherBag);
611        }
612
613        /// <summary>
614        /// Determines if this bag is a subset of another ba11 items in this bag.
615        /// </summary>
616        /// <param name="otherBag">Bag to compare to.</param>
617        /// <returns>True if this is a subset of <paramref name="otherBag"/>.</returns>
618        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
619        public bool IsSubsetOf(Bag<T> otherBag)
620        {
621            return otherBag.IsSupersetOf(this);
622        }
623
624        /// <summary>
625        /// Determines if this bag is a proper subset of another bag. Neither bag is modified.
626        /// This bag is a subset of <paramref name="otherBag"/> if every element in this bag
627        /// is also in <paramref name="otherBag"/>, at least the same number of
628        /// times. Additional, this bag must have strictly fewer items than <paramref name="otherBag"/>.
629        /// </summary>
630        /// <remarks>IsProperSubsetOf is computed in time O(N), where N is the number of unique items in this bag.</remarks>
631        /// <param name="otherBag">Bag to compare to.</param>
632        /// <returns>True if this is a proper subset of <paramref name="otherBag"/>.</returns>
633        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
634        public bool IsProperSubsetOf(Bag<T> otherBag)
635        {
636            return otherBag.IsProperSupersetOf(this);
637        }
638
639        /// <summary>
640        /// Determines if this bag is disjoint from another bag. Two bags are disjoint
641        /// if no item from one set is equal to any item in the other bag.
642        /// </summary>
643        /// <remarks>
644        /// <para>The answer is computed in time O(N), where N is the size of the smaller set.</para>
645        /// </remarks>
646        /// <param name="otherBag">Bag to check disjointness with.</param>
647        /// <returns>True if the two bags are disjoint, false otherwise.</returns>
648        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
649        public bool IsDisjointFrom(Bag<T> otherBag)
650        {
651            CheckConsistentComparison(otherBag);
652            Bag<T> smaller, larger;
653            if (otherBag.Count > this.Count) {
654                smaller = this; larger = otherBag;
655            }
656            else {
657                smaller = otherBag; larger = this;
658            }
659
660            foreach (T item in smaller.DistinctItems()) {
661                if (larger.Contains(item))
662                    return false;
663            }
664
665            return true;
666        }
667
668        /// <summary>
669        /// Computes the union of this bag with another bag. The union of two bags
670        /// is all items from both of the bags. If an item appears X times in one bag,
671        /// and Y times in the other bag, the union contains the item Maximum(X,Y) times. This bag receives
672        /// the union of the two bags, the other bag is unchanged.
673        /// </summary>
674        /// <remarks>
675        /// <para>The union of two bags is computed in time O(M+N), where M and N are the size of the
676        /// two bags.</para>
677        /// </remarks>
678        /// <param name="otherBag">Bag to union with.</param>
679        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
680        public void UnionWith(Bag<T> otherBag)
681        {
682            CheckConsistentComparison(otherBag);
683
684            if (otherBag == this)
685                return;             // Nothing to do
686
687            int copiesInThis, copiesInOther;
688
689            // Enumerate each of the items in the other bag. Add items that need to be
690            // added to this bag.
691            foreach (T item in otherBag.DistinctItems()) {
692                copiesInThis = this.NumberOfCopies(item);
693                copiesInOther = otherBag.NumberOfCopies(item);
694
695                if (copiesInOther > copiesInThis)
696                    ChangeNumberOfCopies(item, copiesInOther);
697            } 
698        }
699
700        /// <summary>
701        /// Computes the union of this bag with another bag. The union of two bags
702        /// is all items from both of the bags.  If an item appears X times in one bag,
703        /// and Y times in the other bag, the union contains the item Maximum(X,Y) times. A new bag is
704        /// created with the union of the bags and is returned. This bag and the other bag
705        /// are unchanged.
706        /// </summary>
707        /// <remarks>
708        /// <para>The union of two bags is computed in time O(M+N), where M and N are the size of the two bags.</para>
709        /// </remarks>
710        /// <param name="otherBag">Bag to union with.</param>
711        /// <returns>The union of the two bags.</returns>
712        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
713        public Bag<T> Union(Bag<T> otherBag)
714        {
715            CheckConsistentComparison(otherBag);
716
717            Bag<T> smaller, larger, result;
718            if (otherBag.Count > this.Count) {
719                smaller = this; larger = otherBag;
720            }
721            else {
722                smaller = otherBag; larger = this;
723            }
724
725            result = larger.Clone();
726            result.UnionWith(smaller);
727            return result; 
728        }
729
730        /// <summary>
731        /// Computes the sum of this bag with another bag. The sum of two bags
732        /// is all items from both of the bags. If an item appears X times in one bag,
733        /// and Y times in the other bag, the sum contains the item (X+Y) times. This bag receives
734        /// the sum of the two bags, the other bag is unchanged.
735        /// </summary>
736        /// <remarks>
737        /// <para>The sum of two bags is computed in time O(M), where M is the size of the
738        /// other bag..</para>
739        /// </remarks>
740        /// <param name="otherBag">Bag to sum with.</param>
741        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
742        public void SumWith(Bag<T> otherBag)
743        {
744            CheckConsistentComparison(otherBag);
745
746            if (this == otherBag) {
747                // Not very efficient, but an uncommon case.
748                AddMany(otherBag);
749                return;
750            }
751
752            int copiesInThis, copiesInOther;
753
754            // Enumerate each of the items in the other bag. Add items that need to be
755            // added to this bag.
756            foreach (T item in otherBag.DistinctItems()) {
757                copiesInThis = this.NumberOfCopies(item);
758                copiesInOther = otherBag.NumberOfCopies(item);
759
760                ChangeNumberOfCopies(item, copiesInThis + copiesInOther);
761            }
762        }
763
764        /// <summary>
765        /// Computes the sum of this bag with another bag. he sum of two bags
766        /// is all items from both of the bags.  If an item appears X times in one bag,
767        /// and Y times in the other bag, the sum contains the item (X+Y) times. A new bag is
768        /// created with the sum of the bags and is returned. This bag and the other bag
769        /// are unchanged.
770        /// </summary>
771        /// <remarks>
772        /// <para>The sum of two bags is computed in time O(M + N log M), where M is the size of the
773        /// larger bag, and N is the size of the smaller bag.</para>
774        /// </remarks>
775        /// <param name="otherBag">Bag to sum with.</param>
776        /// <returns>The sum of the two bags.</returns>
777        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
778        public Bag<T> Sum(Bag<T> otherBag)
779        {
780            CheckConsistentComparison(otherBag);
781
782            Bag<T> smaller, larger, result;
783            if (otherBag.Count > this.Count) {
784                smaller = this; larger = otherBag;
785            }
786            else {
787                smaller = otherBag; larger = this;
788            }
789
790            result = larger.Clone();
791            result.SumWith(smaller);
792            return result;
793        }
794
795        /// <summary>
796        /// Computes the intersection of this bag with another bag. The intersection of two bags
797        /// is all items that appear in both of the bags. If an item appears X times in one bag,
798        /// and Y times in the other bag, the sum contains the item Minimum(X,Y) times. This bag receives
799        /// the intersection of the two bags, the other bag is unchanged.
800        /// </summary>
801        /// <remarks>
802        /// <para>When equal items appear in both bags, the intersection will include an arbitrary choice of one of the
803        /// two equal items.</para>
804        /// <para>The intersection of two bags is computed in time O(N), where N is the size of the smaller bag.</para>
805        /// </remarks>
806        /// <param name="otherBag">Bag to intersection with.</param>
807        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
808        public void IntersectionWith(Bag<T> otherBag)
809        {
810            CheckConsistentComparison(otherBag);
811
812            hash.StopEnumerations();
813
814            Bag<T> smaller, larger;
815            if (otherBag.Count > this.Count) {
816                smaller = this; larger = otherBag;
817            }
818            else {
819                smaller = otherBag; larger = this;
820            }
821
822            KeyValuePair<T,int> dummy;
823            Hash<KeyValuePair<T, int>> newHash = new Hash<KeyValuePair<T, int>>(equalityComparer);
824            int newCount = 0;
825            int copiesInSmaller, copiesInLarger, copies;
826
827            // Enumerate each of the items in the smaller bag. Add items that need to be
828            // added to the intersection.
829            foreach (T item in smaller.DistinctItems()) {
830                copiesInLarger = larger.NumberOfCopies(item);
831                copiesInSmaller = smaller.NumberOfCopies(item);
832                copies = Math.Min(copiesInLarger, copiesInSmaller);
833                if (copies > 0) {
834                    newHash.Insert(NewPair(item, copies), true, out dummy);
835                    newCount += copies;
836                }
837            }
838
839            hash = newHash;
840            count = newCount;
841        }
842
843        /// <summary>
844        /// Computes the intersection of this bag with another bag. The intersection of two bags
845        /// is all items that appear in both of the bags. If an item appears X times in one bag,
846        /// and Y times in the other bag, the intersection contains the item Minimum(X,Y) times. A new bag is
847        /// created with the intersection of the bags and is returned. This bag and the other bag
848        /// are unchanged.
849        /// </summary>
850        /// <remarks>
851        /// <para>When equal items appear in both bags, the intersection will include an arbitrary choice of one of the
852        /// two equal items.</para>
853        /// <para>The intersection of two bags is computed in time O(N), where N is the size of the smaller bag.</para>
854        /// </remarks>
855        /// <param name="otherBag">Bag to intersection with.</param>
856        /// <returns>The intersection of the two bags.</returns>
857        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
858        public Bag<T> Intersection(Bag<T> otherBag)
859        {
860            CheckConsistentComparison(otherBag);
861
862            Bag<T> smaller, larger, result;
863            if (otherBag.Count > this.Count) {
864                smaller = this; larger = otherBag;
865            }
866            else {
867                smaller = otherBag; larger = this;
868            }
869
870            int copiesInSmaller, copiesInLarger, copies;
871
872            // Enumerate each of the items in the smaller bag. Add items that need to be
873            // added to the intersection.
874            result = new Bag<T>(keyEqualityComparer);
875            foreach (T item in smaller.DistinctItems()) {
876                copiesInLarger = larger.NumberOfCopies(item);
877                copiesInSmaller = smaller.NumberOfCopies(item);
878                copies = Math.Min(copiesInLarger, copiesInSmaller);
879                if (copies > 0) 
880                    result.ChangeNumberOfCopies(item, copies);
881            }
882
883            return result; 
884        }
885
886        /// <summary>
887        /// Computes the difference of this bag with another bag. The difference of these two bags
888        /// is all items that appear in this bag, but not in <paramref name="otherBag"/>. If an item appears X times in this bag,
889        /// and Y times in the other bag, the difference contains the item X - Y times (zero times if Y >= X). This bag receives
890        /// the difference of the two bags; the other bag is unchanged.
891        /// </summary>
892        /// <remarks>
893        /// <para>The difference of two bags is computed in time O(M), where M is the size of the
894        /// other bag.</para>
895        /// </remarks>
896        /// <param name="otherBag">Bag to difference with.</param>
897        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
898        public void DifferenceWith(Bag<T> otherBag)
899        {
900            CheckConsistentComparison(otherBag);
901
902            if (this == otherBag) {
903                Clear();
904                return;
905            }
906
907            int copiesInThis, copiesInOther, copies;
908
909            // Enumerate each of the items in the other bag. Remove items that need to be
910            // removed from this bag.
911            foreach (T item in otherBag.DistinctItems()) {
912                copiesInThis = this.NumberOfCopies(item);
913                copiesInOther = otherBag.NumberOfCopies(item);
914                copies = copiesInThis - copiesInOther;
915                if (copies < 0)
916                    copies = 0;
917
918                ChangeNumberOfCopies(item, copies);
919            }
920        }
921
922        /// <summary>
923        /// Computes the difference of this bag with another bag. The difference of these two bags
924        /// is all items that appear in this bag, but not in <paramref name="otherBag"/>. If an item appears X times in this bag,
925        /// and Y times in the other bag, the difference contains the item X - Y times (zero times if Y >= X).  A new bag is
926        /// created with the difference of the bags and is returned. This bag and the other bag
927        /// are unchanged.
928        /// </summary>
929        /// <remarks>
930        /// <para>The difference of two bags is computed in time O(M + N), where M and N are the size
931        /// of the two bags.</para>
932        /// </remarks>
933        /// <param name="otherBag">Bag to difference with.</param>
934        /// <returns>The difference of the two bags.</returns>
935        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
936        public Bag<T> Difference(Bag<T> otherBag)
937        {
938            Bag<T> result;
939
940            CheckConsistentComparison(otherBag);
941
942            result = this.Clone();
943            result.DifferenceWith(otherBag);
944            return result; 
945        }
946
947        /// <summary>
948        /// Computes the symmetric difference of this bag with another bag. The symmetric difference of two bags
949        /// is all items that appear in either of the bags, but not both. If an item appears X times in one bag,
950        /// and Y times in the other bag, the symmetric difference contains the item AbsoluteValue(X - Y) times. This bag receives
951        /// the symmetric difference of the two bags; the other bag is unchanged.
952        /// </summary>
953        /// <remarks>
954        /// <para>The symmetric difference of two bags is computed in time O(M + N), where M is the size of the
955        /// larger bag, and N is the size of the smaller bag.</para>
956        /// </remarks>
957        /// <param name="otherBag">Bag to symmetric difference with.</param>
958        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
959        public void SymmetricDifferenceWith(Bag<T> otherBag)
960        {
961            CheckConsistentComparison(otherBag);
962
963            if (this == otherBag) {
964                Clear();
965                return;
966            }
967
968            int copiesInThis, copiesInOther, copies;
969
970            // Enumerate each of the items in the other bag. Add items that need to be
971            // added to this bag.
972            foreach (T item in otherBag.DistinctItems()) {
973                copiesInThis = this.NumberOfCopies(item);
974                copiesInOther = otherBag.NumberOfCopies(item);
975                copies = Math.Abs(copiesInThis - copiesInOther);
976
977                if (copies != copiesInThis)
978                    ChangeNumberOfCopies(item, copies);
979            }
980        }
981
982        /// <summary>
983        /// Computes the symmetric difference of this bag with another bag. The symmetric difference of two bags
984        /// is all items that appear in either of the bags, but not both. If an item appears X times in one bag,
985        /// and Y times in the other bag, the symmetric difference contains the item AbsoluteValue(X - Y) times. A new bag is
986        /// created with the symmetric difference of the bags and is returned. This bag and the other bag
987        /// are unchanged.
988        /// </summary>
989        /// <remarks>
990        /// <para>The symmetric difference of two bags is computed in time O(M + N), where M is the size of the
991        /// larger bag, and N is the size of the smaller bag.</para>
992        /// </remarks>
993        /// <param name="otherBag">Bag to symmetric difference with.</param>
994        /// <returns>The symmetric difference of the two bags.</returns>
995        /// <exception cref="InvalidOperationException">This bag and <paramref name="otherBag"/> don't use the same method for comparing items.</exception>
996        public Bag<T> SymmetricDifference(Bag<T> otherBag)
997        {
998            CheckConsistentComparison(otherBag);
999
1000            Bag<T> smaller, larger, result;
1001            if (otherBag.Count > this.Count) {
1002                smaller = this; larger = otherBag;
1003            }
1004            else {
1005                smaller = otherBag; larger = this;
1006            }
1007
1008            result = larger.Clone();
1009            result.SymmetricDifferenceWith(smaller);
1010            return result;
1011        }
1012
1013        #endregion Set operations
1014    }
1015}
Note: See TracBrowser for help on using the repository browser.