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 | |
---|
9 | using System; |
---|
10 | using System.Collections.Generic; |
---|
11 | |
---|
12 | |
---|
13 | namespace Wintellect.PowerCollections |
---|
14 | { |
---|
15 | /// <summary> |
---|
16 | /// Bag<T> 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<T> |
---|
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<T> 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<string>, 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<T>"/> 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<T>"/> |
---|
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<T> 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<T> 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<T> 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<T>.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<T> 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 | } |
---|