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