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