5 // Jb Evain <jbevain@novell.com>
7 // Copyright (C) 2010 Novell, Inc (http://www.novell.com)
9 // Permission is hereby granted, free of charge, to any person obtaining
10 // a copy of this software and associated documentation files (the
11 // "Software"), to deal in the Software without restriction, including
12 // without limitation the rights to use, copy, modify, merge, publish,
13 // distribute, sublicense, and/or sell copies of the Software, and to
14 // permit persons to whom the Software is furnished to do so, subject to
15 // the following conditions:
17 // The above copyright notice and this permission notice shall be
18 // included in all copies or substantial portions of the Software.
20 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
21 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
22 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
23 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
24 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
25 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
26 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
30 using System.Collections;
31 using System.Collections.Generic;
33 using System.Runtime.Serialization;
34 using System.Runtime.InteropServices;
35 using System.Security;
36 using System.Security.Permissions;
37 using System.Diagnostics;
39 // SortedSet is basically implemented as a reduction of SortedDictionary<K, V>
43 namespace System.Collections.Generic {
46 [DebuggerDisplay ("Count={Count}")]
47 [DebuggerTypeProxy (typeof (CollectionDebuggerView))]
48 public class SortedSet<T> : ISet<T>, ICollection, ISerializable, IDeserializationCallback
50 class Node : RBTree.Node {
59 public override void SwapValue (RBTree.Node other)
68 class NodeHelper : RBTree.INodeHelper<T> {
70 static NodeHelper Default = new NodeHelper (Comparer<T>.Default);
72 public IComparer<T> comparer;
74 public int Compare (T item, RBTree.Node node)
76 return comparer.Compare (item, ((Node) node).item);
79 public RBTree.Node CreateNode (T item)
81 return new Node (item);
84 NodeHelper (IComparer<T> comparer)
86 this.comparer = comparer;
89 public static NodeHelper GetHelper (IComparer<T> comparer)
91 if (comparer == null || comparer == Comparer<T>.Default)
94 return new NodeHelper (comparer);
100 SerializationInfo si;
103 : this (Comparer<T>.Default)
107 public SortedSet (IEnumerable<T> collection)
108 : this (collection, Comparer<T>.Default)
112 public SortedSet (IEnumerable<T> collection, IComparer<T> comparer)
115 if (collection == null)
116 throw new ArgumentNullException ("collection");
118 foreach (var item in collection)
122 public SortedSet (IComparer<T> comparer)
124 this.helper = NodeHelper.GetHelper (comparer);
125 this.tree = new RBTree (this.helper);
128 protected SortedSet (SerializationInfo info, StreamingContext context)
133 public IComparer<T> Comparer {
134 get { return helper.comparer; }
138 get { return GetCount (); }
142 get { return GetMax (); }
146 get { return GetMin (); }
149 internal virtual T GetMax ()
154 return GetItem (tree.Count - 1);
157 internal virtual T GetMin ()
165 internal virtual int GetCount ()
170 T GetItem (int index)
172 return ((Node) tree [index]).item;
175 public bool Add (T item)
177 return TryAdd (item);
180 internal virtual bool TryAdd (T item)
182 var node = new Node (item);
183 return tree.Intern (item, node) == node;
186 public virtual void Clear ()
191 public virtual bool Contains (T item)
193 return tree.Lookup (item) != null;
196 public void CopyTo (T [] array)
198 CopyTo (array, 0, Count);
201 public void CopyTo (T [] array, int index)
203 CopyTo (array, index, Count);
206 public void CopyTo (T [] array, int index, int count)
209 throw new ArgumentNullException ("array");
211 throw new ArgumentOutOfRangeException ("index");
212 if (index > array.Length)
213 throw new ArgumentException ("index larger than largest valid index of array");
214 if (array.Length - index < count)
215 throw new ArgumentException ("destination array cannot hold the requested elements");
217 foreach (Node node in tree) {
221 array [index++] = node.item;
225 public bool Remove (T item)
227 return TryRemove (item);
230 internal virtual bool TryRemove (T item)
232 return tree.Remove (item) != null;
235 public int RemoveWhere (Predicate<T> match)
237 var array = ToArray ();
240 foreach (var item in array) {
251 public IEnumerable<T> Reverse ()
253 for (int i = tree.Count - 1; i >= 0; i--)
254 yield return GetItem (i);
259 var array = new T [this.Count];
264 public Enumerator GetEnumerator ()
266 return TryGetEnumerator ();
269 internal virtual Enumerator TryGetEnumerator ()
271 return new Enumerator (this);
274 IEnumerator<T> IEnumerable<T>.GetEnumerator ()
276 return GetEnumerator ();
279 IEnumerator IEnumerable.GetEnumerator ()
281 return GetEnumerator ();
284 public static IEqualityComparer<SortedSet<T>> CreateSetComparer ()
286 return CreateSetComparer (EqualityComparer<T>.Default);
290 public static IEqualityComparer<SortedSet<T>> CreateSetComparer (IEqualityComparer<T> memberEqualityComparer)
292 throw new NotImplementedException ();
296 protected virtual void GetObjectData (SerializationInfo info, StreamingContext context)
298 throw new NotImplementedException ();
301 void ISerializable.GetObjectData (SerializationInfo info, StreamingContext context)
303 GetObjectData (info, context);
307 protected virtual void OnDeserialization (object sender)
312 throw new NotImplementedException ();
315 void IDeserializationCallback.OnDeserialization (object sender)
317 OnDeserialization (sender);
320 [MonoLimitation ("Isn't O(n) when other is SortedSet<T>")]
321 public void ExceptWith (IEnumerable<T> other)
323 CheckArgumentNotNull (other, "other");
324 foreach (T item in other)
328 public virtual SortedSet<T> GetViewBetween (T lowerValue, T upperValue)
330 if (Comparer.Compare (lowerValue, upperValue) > 0)
331 throw new ArgumentException ("The lowerValue is bigger than upperValue");
333 return new SortedSubSet (this, lowerValue, upperValue);
336 [MonoLimitation ("Isn't O(n) when other is SortedSet<T>")]
337 public virtual void IntersectWith (IEnumerable<T> other)
339 CheckArgumentNotNull (other, "other");
341 RBTree newtree = new RBTree (helper);
342 foreach (T item in other) {
343 var node = tree.Remove (item);
345 newtree.Intern (item, node);
350 public bool IsProperSubsetOf (IEnumerable<T> other)
352 CheckArgumentNotNull (other, "other");
355 foreach (T item in other)
356 return true; // this idiom means: if 'other' is non-empty, return true
360 return is_subset_of (other, true);
363 public bool IsProperSupersetOf (IEnumerable<T> other)
365 CheckArgumentNotNull (other, "other");
370 return is_superset_of (other, true);
373 public bool IsSubsetOf (IEnumerable<T> other)
375 CheckArgumentNotNull (other, "other");
380 return is_subset_of (other, false);
383 public bool IsSupersetOf (IEnumerable<T> other)
385 CheckArgumentNotNull (other, "other");
388 foreach (T item in other)
389 return false; // this idiom means: if 'other' is non-empty, return false
393 return is_superset_of (other, false);
396 // Precondition: Count != 0, other != null
397 bool is_subset_of (IEnumerable<T> other, bool proper)
399 SortedSet<T> that = nodups (other);
401 if (Count > that.Count)
403 // Count != 0 && Count <= that.Count => that.Count != 0
404 if (proper && Count == that.Count)
406 return that.covers (this);
409 // Precondition: Count != 0, other != null
410 bool is_superset_of (IEnumerable<T> other, bool proper)
412 SortedSet<T> that = nodups (other);
416 if (Count < that.Count)
418 if (proper && Count == that.Count)
420 return this.covers (that);
423 public bool Overlaps (IEnumerable<T> other)
425 CheckArgumentNotNull (other, "other");
430 // Don't use 'nodups' here. Only optimize the SortedSet<T> case
431 SortedSet<T> that = other as SortedSet<T>;
432 if (that != null && that.Comparer != Comparer)
436 return that.Count != 0 && overlaps (that);
438 foreach (T item in other)
444 public bool SetEquals (IEnumerable<T> other)
446 CheckArgumentNotNull (other, "other");
449 foreach (T item in other)
454 SortedSet<T> that = nodups (other);
456 if (Count != that.Count)
459 using (var t = that.GetEnumerator ()) {
460 foreach (T item in this) {
462 throw new SystemException ("count wrong somewhere: this longer than that");
463 if (Comparer.Compare (item, t.Current) != 0)
467 throw new SystemException ("count wrong somewhere: this shorter than that");
472 SortedSet<T> nodups (IEnumerable<T> other)
474 SortedSet<T> that = other as SortedSet<T>;
475 if (that != null && that.Comparer == Comparer)
477 return new SortedSet<T> (other, Comparer);
480 bool covers (SortedSet<T> that)
482 using (var t = that.GetEnumerator ()) {
485 foreach (T item in this) {
486 int cmp = Comparer.Compare (item, t.Current);
489 if (cmp == 0 && !t.MoveNext ())
496 bool overlaps (SortedSet<T> that)
498 using (var t = that.GetEnumerator ()) {
501 foreach (T item in this) {
503 while ((cmp = Comparer.Compare (item, t.Current)) > 0) {
514 [MonoLimitation ("Isn't O(n) when other is SortedSet<T>")]
515 public void SymmetricExceptWith (IEnumerable<T> other)
517 SortedSet<T> that_minus_this = new SortedSet<T> (Comparer);
519 // compute this - that and that - this in parallel
520 foreach (T item in nodups (other))
522 that_minus_this.Add (item);
524 UnionWith (that_minus_this);
527 [MonoLimitation ("Isn't O(n) when other is SortedSet<T>")]
528 public void UnionWith (IEnumerable<T> other)
530 CheckArgumentNotNull (other, "other");
532 foreach (T item in other)
536 static void CheckArgumentNotNull (object arg, string name)
539 throw new ArgumentNullException (name);
542 void ICollection<T>.Add (T item)
547 void ICollection<T>.CopyTo (T [] array, int index)
549 CopyTo (array, index, Count);
552 bool ICollection<T>.IsReadOnly {
553 get { return false; }
556 void ICollection.CopyTo (Array array, int index)
561 throw new ArgumentNullException ("array");
562 if (index < 0 || array.Length <= index)
563 throw new ArgumentOutOfRangeException ("index");
564 if (array.Length - index < Count)
565 throw new ArgumentException ();
567 foreach (Node node in tree)
568 array.SetValue (node.item, index++);
571 bool ICollection.IsSynchronized {
572 get { return false; }
575 // TODO:Is this correct? If this is wrong,please fix.
576 object ICollection.SyncRoot {
581 public struct Enumerator : IEnumerator<T>, IDisposable {
583 RBTree.NodeEnumerator host;
585 IComparer<T> comparer;
590 internal Enumerator (SortedSet<T> set)
593 host = set.tree.GetEnumerator ();
596 internal Enumerator (SortedSet<T> set, T lower, T upper)
599 host = set.tree.GetSuffixEnumerator (lower);
600 comparer = set.Comparer;
605 get { return current; }
608 object IEnumerator.Current {
610 host.check_current ();
611 return ((Node) host.Current).item;
615 public bool MoveNext ()
617 if (!host.MoveNext ())
620 current = ((Node) host.Current).item;
621 return comparer == null || comparer.Compare (upper, current) >= 0;
624 public void Dispose ()
629 void IEnumerator.Reset ()
636 sealed class SortedSubSet : SortedSet<T>, IEnumerable<T>, IEnumerable {
642 public SortedSubSet (SortedSet<T> set, T lower, T upper)
643 : base (set.Comparer)
651 internal override T GetMin ()
653 RBTree.Node lb = null, ub = null;
654 set.tree.Bound (lower, ref lb, ref ub);
656 if (ub == null || set.helper.Compare (upper, ub) < 0)
659 return ((Node) ub).item;
662 internal override T GetMax ()
664 RBTree.Node lb = null, ub = null;
665 set.tree.Bound (upper, ref lb, ref ub);
667 if (lb == null || set.helper.Compare (lower, lb) > 0)
670 return ((Node) lb).item;
673 internal override int GetCount ()
676 using (var e = set.tree.GetSuffixEnumerator (lower)) {
677 while (e.MoveNext () && set.helper.Compare (upper, e.Current) >= 0)
683 internal override bool TryAdd (T item)
686 throw new ArgumentOutOfRangeException ("item");
688 return set.TryAdd (item);
691 internal override bool TryRemove (T item)
696 return set.TryRemove (item);
699 public override bool Contains (T item)
704 return set.Contains (item);
707 public override void Clear ()
709 set.RemoveWhere (InRange);
712 bool InRange (T item)
714 return Comparer.Compare (item, lower) >= 0
715 && Comparer.Compare (item, upper) <= 0;
718 public override SortedSet<T> GetViewBetween (T lowerValue, T upperValue)
720 if (Comparer.Compare (lowerValue, upperValue) > 0)
721 throw new ArgumentException ("The lowerValue is bigger than upperValue");
722 if (!InRange (lowerValue))
723 throw new ArgumentOutOfRangeException ("lowerValue");
724 if (!InRange (upperValue))
725 throw new ArgumentOutOfRangeException ("upperValue");
727 return new SortedSubSet (set, lowerValue, upperValue);
730 internal override Enumerator TryGetEnumerator ()
732 return new Enumerator (set, lower, upper);
735 public override void IntersectWith (IEnumerable<T> other)
737 CheckArgumentNotNull (other, "other");
739 var slice = new SortedSet<T> (this);
740 slice.IntersectWith (other);
743 set.UnionWith (slice);