5 // Jb Evain <jbevain@novell.com>
6 // Marek Safra (marek.safar@gmail.com)
8 // Copyright (C) 2010 Novell, Inc (http://www.novell.com)
9 // Copyright (C) 2014 Xamarin Inc (http://www.xamarin.com)
11 // Permission is hereby granted, free of charge, to any person obtaining
12 // a copy of this software and associated documentation files (the
13 // "Software"), to deal in the Software without restriction, including
14 // without limitation the rights to use, copy, modify, merge, publish,
15 // distribute, sublicense, and/or sell copies of the Software, and to
16 // permit persons to whom the Software is furnished to do so, subject to
17 // the following conditions:
19 // The above copyright notice and this permission notice shall be
20 // included in all copies or substantial portions of the Software.
22 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
23 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
24 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
25 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
26 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
27 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
28 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
32 using System.Collections;
33 using System.Collections.Generic;
34 using System.Runtime.Serialization;
35 using System.Runtime.InteropServices;
36 using System.Security;
37 using System.Security.Permissions;
38 using System.Diagnostics;
40 // SortedSet is basically implemented as a reduction of SortedDictionary<K, V>
44 namespace System.Collections.Generic {
47 [DebuggerDisplay ("Count={Count}")]
48 [DebuggerTypeProxy (typeof (CollectionDebuggerView))]
49 public class SortedSet<T> : ISet<T>, ICollection, ISerializable, IDeserializationCallback
51 class Node : RBTree.Node {
60 public override void SwapValue (RBTree.Node other)
69 class NodeHelper : RBTree.INodeHelper<T> {
71 static NodeHelper Default = new NodeHelper (Comparer<T>.Default);
73 public IComparer<T> comparer;
75 public int Compare (T item, RBTree.Node node)
77 return comparer.Compare (item, ((Node) node).item);
80 public RBTree.Node CreateNode (T item)
82 return new Node (item);
85 NodeHelper (IComparer<T> comparer)
87 this.comparer = comparer;
90 public static NodeHelper GetHelper (IComparer<T> comparer)
92 if (comparer == null || comparer == Comparer<T>.Default)
95 return new NodeHelper (comparer);
101 SerializationInfo si;
104 : this (Comparer<T>.Default)
108 public SortedSet (IEnumerable<T> collection)
109 : this (collection, Comparer<T>.Default)
113 public SortedSet (IEnumerable<T> collection, IComparer<T> comparer)
116 if (collection == null)
117 throw new ArgumentNullException ("collection");
119 foreach (var item in collection)
123 public SortedSet (IComparer<T> comparer)
125 this.helper = NodeHelper.GetHelper (comparer);
126 this.tree = new RBTree (this.helper);
129 protected SortedSet (SerializationInfo info, StreamingContext context)
134 public IComparer<T> Comparer {
135 get { return helper.comparer; }
139 get { return GetCount (); }
143 get { return GetMax (); }
147 get { return GetMin (); }
150 internal virtual T GetMax ()
155 return GetItem (tree.Count - 1);
158 internal virtual T GetMin ()
166 internal virtual int GetCount ()
171 T GetItem (int index)
173 return ((Node) tree [index]).item;
176 public bool Add (T item)
178 return TryAdd (item);
181 internal virtual bool TryAdd (T item)
183 var node = new Node (item);
184 return tree.Intern (item, node) == node;
187 public virtual void Clear ()
192 public virtual bool Contains (T item)
194 return tree.Lookup (item) != null;
197 public void CopyTo (T [] array)
199 CopyTo (array, 0, Count);
202 public void CopyTo (T [] array, int index)
204 CopyTo (array, index, Count);
207 public void CopyTo (T [] array, int index, int count)
210 throw new ArgumentNullException ("array");
212 throw new ArgumentOutOfRangeException ("index");
213 if (index > array.Length)
214 throw new ArgumentException ("index larger than largest valid index of array");
215 if (array.Length - index < count)
216 throw new ArgumentException ("destination array cannot hold the requested elements");
218 foreach (Node node in tree) {
222 array [index++] = node.item;
226 public bool Remove (T item)
228 return TryRemove (item);
231 internal virtual bool TryRemove (T item)
233 return tree.Remove (item) != null;
236 public int RemoveWhere (Predicate<T> match)
238 var array = ToArray ();
241 foreach (var item in array) {
252 public IEnumerable<T> Reverse ()
254 for (int i = tree.Count - 1; i >= 0; i--)
255 yield return GetItem (i);
260 var array = new T [this.Count];
265 public Enumerator GetEnumerator ()
267 return TryGetEnumerator ();
270 internal virtual Enumerator TryGetEnumerator ()
272 return new Enumerator (this);
275 IEnumerator<T> IEnumerable<T>.GetEnumerator ()
277 return GetEnumerator ();
280 IEnumerator IEnumerable.GetEnumerator ()
282 return GetEnumerator ();
285 public static IEqualityComparer<SortedSet<T>> CreateSetComparer ()
287 return CreateSetComparer (EqualityComparer<T>.Default);
291 public static IEqualityComparer<SortedSet<T>> CreateSetComparer (IEqualityComparer<T> memberEqualityComparer)
293 throw new NotImplementedException ();
297 protected virtual void GetObjectData (SerializationInfo info, StreamingContext context)
299 throw new NotImplementedException ();
302 void ISerializable.GetObjectData (SerializationInfo info, StreamingContext context)
304 GetObjectData (info, context);
308 protected virtual void OnDeserialization (object sender)
313 throw new NotImplementedException ();
316 void IDeserializationCallback.OnDeserialization (object sender)
318 OnDeserialization (sender);
321 [MonoLimitation ("Isn't O(n) when other is SortedSet<T>")]
322 public void ExceptWith (IEnumerable<T> other)
329 CheckArgumentNotNull (other, "other");
330 foreach (T item in other)
334 public virtual SortedSet<T> GetViewBetween (T lowerValue, T upperValue)
336 if (Comparer.Compare (lowerValue, upperValue) > 0)
337 throw new ArgumentException ("The lowerValue is bigger than upperValue");
339 return new SortedSubSet (this, lowerValue, upperValue);
342 [MonoLimitation ("Isn't O(n) when other is SortedSet<T>")]
343 public virtual void IntersectWith (IEnumerable<T> other)
345 CheckArgumentNotNull (other, "other");
347 RBTree newtree = new RBTree (helper);
348 foreach (T item in other) {
349 var node = tree.Remove (item);
351 newtree.Intern (item, node);
356 public bool IsProperSubsetOf (IEnumerable<T> other)
358 CheckArgumentNotNull (other, "other");
361 foreach (T item in other)
362 return true; // this idiom means: if 'other' is non-empty, return true
366 return is_subset_of (other, true);
369 public bool IsProperSupersetOf (IEnumerable<T> other)
371 CheckArgumentNotNull (other, "other");
376 return is_superset_of (other, true);
379 public bool IsSubsetOf (IEnumerable<T> other)
381 CheckArgumentNotNull (other, "other");
386 return is_subset_of (other, false);
389 public bool IsSupersetOf (IEnumerable<T> other)
391 CheckArgumentNotNull (other, "other");
394 foreach (T item in other)
395 return false; // this idiom means: if 'other' is non-empty, return false
399 return is_superset_of (other, false);
402 // Precondition: Count != 0, other != null
403 bool is_subset_of (IEnumerable<T> other, bool proper)
405 SortedSet<T> that = nodups (other);
407 if (Count > that.Count)
409 // Count != 0 && Count <= that.Count => that.Count != 0
410 if (proper && Count == that.Count)
412 return that.covers (this);
415 // Precondition: Count != 0, other != null
416 bool is_superset_of (IEnumerable<T> other, bool proper)
418 SortedSet<T> that = nodups (other);
422 if (Count < that.Count)
424 if (proper && Count == that.Count)
426 return this.covers (that);
429 public bool Overlaps (IEnumerable<T> other)
431 CheckArgumentNotNull (other, "other");
436 // Don't use 'nodups' here. Only optimize the SortedSet<T> case
437 SortedSet<T> that = other as SortedSet<T>;
438 if (that != null && that.Comparer != Comparer)
442 return that.Count != 0 && overlaps (that);
444 foreach (T item in other)
450 public bool SetEquals (IEnumerable<T> other)
452 CheckArgumentNotNull (other, "other");
455 foreach (T item in other)
460 SortedSet<T> that = nodups (other);
462 if (Count != that.Count)
465 using (var t = that.GetEnumerator ()) {
466 foreach (T item in this) {
468 throw new SystemException ("count wrong somewhere: this longer than that");
469 if (Comparer.Compare (item, t.Current) != 0)
473 throw new SystemException ("count wrong somewhere: this shorter than that");
478 SortedSet<T> nodups (IEnumerable<T> other)
480 SortedSet<T> that = other as SortedSet<T>;
481 if (that != null && that.Comparer == Comparer)
483 return new SortedSet<T> (other, Comparer);
486 bool covers (SortedSet<T> that)
488 using (var t = that.GetEnumerator ()) {
491 foreach (T item in this) {
492 int cmp = Comparer.Compare (item, t.Current);
495 if (cmp == 0 && !t.MoveNext ())
502 bool overlaps (SortedSet<T> that)
504 using (var t = that.GetEnumerator ()) {
507 foreach (T item in this) {
509 while ((cmp = Comparer.Compare (item, t.Current)) > 0) {
520 [MonoLimitation ("Isn't O(n) when other is SortedSet<T>")]
521 public void SymmetricExceptWith (IEnumerable<T> other)
528 SortedSet<T> that_minus_this = new SortedSet<T> (Comparer);
530 // compute this - that and that - this in parallel
531 foreach (T item in nodups (other))
533 that_minus_this.Add (item);
535 UnionWith (that_minus_this);
538 [MonoLimitation ("Isn't O(n) when other is SortedSet<T>")]
539 public void UnionWith (IEnumerable<T> other)
541 CheckArgumentNotNull (other, "other");
543 foreach (T item in other)
547 static void CheckArgumentNotNull (object arg, string name)
550 throw new ArgumentNullException (name);
553 void ICollection<T>.Add (T item)
558 bool ICollection<T>.IsReadOnly {
559 get { return false; }
562 void ICollection.CopyTo (Array array, int index)
567 throw new ArgumentNullException ("array");
568 if (index < 0 || array.Length <= index)
569 throw new ArgumentOutOfRangeException ("index");
570 if (array.Length - index < Count)
571 throw new ArgumentException ();
573 foreach (Node node in tree)
574 array.SetValue (node.item, index++);
577 bool ICollection.IsSynchronized {
578 get { return false; }
581 // TODO:Is this correct? If this is wrong,please fix.
582 object ICollection.SyncRoot {
587 public struct Enumerator : IEnumerator<T>, IDisposable {
589 RBTree.NodeEnumerator host;
591 IComparer<T> comparer;
596 internal Enumerator (SortedSet<T> set)
599 host = set.tree.GetEnumerator ();
602 internal Enumerator (SortedSet<T> set, T lower, T upper)
605 host = set.tree.GetSuffixEnumerator (lower);
606 comparer = set.Comparer;
611 get { return current; }
614 object IEnumerator.Current {
616 host.check_current ();
617 return ((Node) host.Current).item;
621 public bool MoveNext ()
623 if (!host.MoveNext ())
626 current = ((Node) host.Current).item;
627 return comparer == null || comparer.Compare (upper, current) >= 0;
630 public void Dispose ()
635 void IEnumerator.Reset ()
642 sealed class SortedSubSet : SortedSet<T>, IEnumerable<T>, IEnumerable {
648 public SortedSubSet (SortedSet<T> set, T lower, T upper)
649 : base (set.Comparer)
657 internal override T GetMin ()
659 RBTree.Node lb = null, ub = null;
660 set.tree.Bound (lower, ref lb, ref ub);
662 if (ub == null || set.helper.Compare (upper, ub) < 0)
665 return ((Node) ub).item;
668 internal override T GetMax ()
670 RBTree.Node lb = null, ub = null;
671 set.tree.Bound (upper, ref lb, ref ub);
673 if (lb == null || set.helper.Compare (lower, lb) > 0)
676 return ((Node) lb).item;
679 internal override int GetCount ()
682 using (var e = set.tree.GetSuffixEnumerator (lower)) {
683 while (e.MoveNext () && set.helper.Compare (upper, e.Current) >= 0)
689 internal override bool TryAdd (T item)
692 throw new ArgumentOutOfRangeException ("item");
694 return set.TryAdd (item);
697 internal override bool TryRemove (T item)
702 return set.TryRemove (item);
705 public override bool Contains (T item)
710 return set.Contains (item);
713 public override void Clear ()
715 set.RemoveWhere (InRange);
718 bool InRange (T item)
720 return Comparer.Compare (item, lower) >= 0
721 && Comparer.Compare (item, upper) <= 0;
724 public override SortedSet<T> GetViewBetween (T lowerValue, T upperValue)
726 if (Comparer.Compare (lowerValue, upperValue) > 0)
727 throw new ArgumentException ("The lowerValue is bigger than upperValue");
728 if (!InRange (lowerValue))
729 throw new ArgumentOutOfRangeException ("lowerValue");
730 if (!InRange (upperValue))
731 throw new ArgumentOutOfRangeException ("upperValue");
733 return new SortedSubSet (set, lowerValue, upperValue);
736 internal override Enumerator TryGetEnumerator ()
738 return new Enumerator (set, lower, upper);
741 public override void IntersectWith (IEnumerable<T> other)
743 CheckArgumentNotNull (other, "other");
745 var slice = new SortedSet<T> (this);
746 slice.IntersectWith (other);
749 set.UnionWith (slice);