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;
32 using System.Runtime.Serialization;
33 using System.Runtime.InteropServices;
34 using System.Security;
35 using System.Security.Permissions;
36 using System.Diagnostics;
38 // SortedSet is basically implemented as a reduction of SortedDictionary<K, V>
42 namespace System.Collections.Generic {
45 [DebuggerDisplay ("Count={Count}")]
46 [DebuggerTypeProxy (typeof (CollectionDebuggerView))]
47 public class SortedSet<T> : ISet<T>, ICollection, ISerializable, IDeserializationCallback
49 class Node : RBTree.Node {
58 public override void SwapValue (RBTree.Node other)
67 class NodeHelper : RBTree.INodeHelper<T> {
69 static NodeHelper Default = new NodeHelper (Comparer<T>.Default);
71 public IComparer<T> comparer;
73 public int Compare (T item, RBTree.Node node)
75 return comparer.Compare (item, ((Node) node).item);
78 public RBTree.Node CreateNode (T item)
80 return new Node (item);
83 NodeHelper (IComparer<T> comparer)
85 this.comparer = comparer;
88 public static NodeHelper GetHelper (IComparer<T> comparer)
90 if (comparer == null || comparer == Comparer<T>.Default)
93 return new NodeHelper (comparer);
102 : this (Comparer<T>.Default)
106 public SortedSet (IEnumerable<T> collection)
107 : this (collection, Comparer<T>.Default)
111 public SortedSet (IEnumerable<T> collection, IComparer<T> comparer)
114 if (collection == null)
115 throw new ArgumentNullException ("collection");
117 foreach (var item in collection)
121 public SortedSet (IComparer<T> comparer)
123 this.helper = NodeHelper.GetHelper (comparer);
124 this.tree = new RBTree (this.helper);
127 protected SortedSet (SerializationInfo info, StreamingContext context)
132 public IComparer<T> Comparer {
133 get { return helper.comparer; }
137 get { return GetCount (); }
141 get { return GetMax (); }
145 get { return GetMin (); }
148 internal virtual T GetMax ()
153 return GetItem (tree.Count - 1);
156 internal virtual T GetMin ()
164 internal virtual int GetCount ()
169 T GetItem (int index)
171 return ((Node) tree [index]).item;
174 public bool Add (T item)
176 return TryAdd (item);
179 internal virtual bool TryAdd (T item)
181 var node = new Node (item);
182 return tree.Intern (item, node) == node;
185 public virtual void Clear ()
190 public virtual bool Contains (T item)
192 return tree.Lookup (item) != null;
195 public void CopyTo (T [] array)
197 CopyTo (array, 0, Count);
200 public void CopyTo (T [] array, int index)
202 CopyTo (array, index, Count);
205 public void CopyTo (T [] array, int index, int count)
208 throw new ArgumentNullException ("array");
210 throw new ArgumentOutOfRangeException ("index");
211 if (index > array.Length)
212 throw new ArgumentException ("index larger than largest valid index of array");
213 if (array.Length - index < count)
214 throw new ArgumentException ("destination array cannot hold the requested elements");
216 foreach (Node node in tree) {
220 array [index++] = node.item;
224 public bool Remove (T item)
226 return TryRemove (item);
229 internal virtual bool TryRemove (T item)
231 return tree.Remove (item) != null;
234 public int RemoveWhere (Predicate<T> match)
236 var array = ToArray ();
239 foreach (var item in array) {
250 public IEnumerable<T> Reverse ()
252 for (int i = tree.Count - 1; i >= 0; i--)
253 yield return GetItem (i);
258 var array = new T [this.Count];
263 public Enumerator GetEnumerator ()
265 return TryGetEnumerator ();
268 internal virtual Enumerator TryGetEnumerator ()
270 return new Enumerator (this);
273 IEnumerator<T> IEnumerable<T>.GetEnumerator ()
275 return GetEnumerator ();
278 IEnumerator IEnumerable.GetEnumerator ()
280 return GetEnumerator ();
283 public static IEqualityComparer<SortedSet<T>> CreateSetComparer ()
285 return CreateSetComparer (EqualityComparer<T>.Default);
289 public static IEqualityComparer<SortedSet<T>> CreateSetComparer (IEqualityComparer<T> memberEqualityComparer)
291 throw new NotImplementedException ();
295 protected virtual void GetObjectData (SerializationInfo info, StreamingContext context)
297 throw new NotImplementedException ();
300 void ISerializable.GetObjectData (SerializationInfo info, StreamingContext context)
302 GetObjectData (info, context);
306 protected virtual void OnDeserialization (object sender)
311 throw new NotImplementedException ();
314 void IDeserializationCallback.OnDeserialization (object sender)
316 OnDeserialization (sender);
319 [MonoLimitation ("Isn't O(n) when other is SortedSet<T>")]
320 public void ExceptWith (IEnumerable<T> other)
322 CheckArgumentNotNull (other, "other");
323 foreach (T item in other)
327 public virtual SortedSet<T> GetViewBetween (T lowerValue, T upperValue)
329 if (Comparer.Compare (lowerValue, upperValue) > 0)
330 throw new ArgumentException ("The lowerValue is bigger than upperValue");
332 return new SortedSubSet (this, lowerValue, upperValue);
335 [MonoLimitation ("Isn't O(n) when other is SortedSet<T>")]
336 public virtual void IntersectWith (IEnumerable<T> other)
338 CheckArgumentNotNull (other, "other");
340 RBTree newtree = new RBTree (helper);
341 foreach (T item in other) {
342 var node = tree.Remove (item);
344 newtree.Intern (item, node);
349 public bool IsProperSubsetOf (IEnumerable<T> other)
351 CheckArgumentNotNull (other, "other");
354 foreach (T item in other)
355 return true; // this idiom means: if 'other' is non-empty, return true
359 return is_subset_of (other, true);
362 public bool IsProperSupersetOf (IEnumerable<T> other)
364 CheckArgumentNotNull (other, "other");
369 return is_superset_of (other, true);
372 public bool IsSubsetOf (IEnumerable<T> other)
374 CheckArgumentNotNull (other, "other");
379 return is_subset_of (other, false);
382 public bool IsSupersetOf (IEnumerable<T> other)
384 CheckArgumentNotNull (other, "other");
387 foreach (T item in other)
388 return false; // this idiom means: if 'other' is non-empty, return false
392 return is_superset_of (other, false);
395 // Precondition: Count != 0, other != null
396 bool is_subset_of (IEnumerable<T> other, bool proper)
398 SortedSet<T> that = nodups (other);
400 if (Count > that.Count)
402 // Count != 0 && Count <= that.Count => that.Count != 0
403 if (proper && Count == that.Count)
405 return that.covers (this);
408 // Precondition: Count != 0, other != null
409 bool is_superset_of (IEnumerable<T> other, bool proper)
411 SortedSet<T> that = nodups (other);
415 if (Count < that.Count)
417 if (proper && Count == that.Count)
419 return this.covers (that);
422 public bool Overlaps (IEnumerable<T> other)
424 CheckArgumentNotNull (other, "other");
429 // Don't use 'nodups' here. Only optimize the SortedSet<T> case
430 SortedSet<T> that = other as SortedSet<T>;
431 if (that != null && that.Comparer != Comparer)
435 return that.Count != 0 && overlaps (that);
437 foreach (T item in other)
443 public bool SetEquals (IEnumerable<T> other)
445 CheckArgumentNotNull (other, "other");
448 foreach (T item in other)
453 SortedSet<T> that = nodups (other);
455 if (Count != that.Count)
458 using (var t = that.GetEnumerator ()) {
459 foreach (T item in this) {
461 throw new SystemException ("count wrong somewhere: this longer than that");
462 if (Comparer.Compare (item, t.Current) != 0)
466 throw new SystemException ("count wrong somewhere: this shorter than that");
471 SortedSet<T> nodups (IEnumerable<T> other)
473 SortedSet<T> that = other as SortedSet<T>;
474 if (that != null && that.Comparer == Comparer)
476 return new SortedSet<T> (other, Comparer);
479 bool covers (SortedSet<T> that)
481 using (var t = that.GetEnumerator ()) {
484 foreach (T item in this) {
485 int cmp = Comparer.Compare (item, t.Current);
488 if (cmp == 0 && !t.MoveNext ())
495 bool overlaps (SortedSet<T> that)
497 using (var t = that.GetEnumerator ()) {
500 foreach (T item in this) {
502 while ((cmp = Comparer.Compare (item, t.Current)) > 0) {
513 [MonoLimitation ("Isn't O(n) when other is SortedSet<T>")]
514 public void SymmetricExceptWith (IEnumerable<T> other)
516 SortedSet<T> that_minus_this = new SortedSet<T> (Comparer);
518 // compute this - that and that - this in parallel
519 foreach (T item in nodups (other))
521 that_minus_this.Add (item);
523 UnionWith (that_minus_this);
526 [MonoLimitation ("Isn't O(n) when other is SortedSet<T>")]
527 public void UnionWith (IEnumerable<T> other)
529 CheckArgumentNotNull (other, "other");
531 foreach (T item in other)
535 static void CheckArgumentNotNull (object arg, string name)
538 throw new ArgumentNullException (name);
541 void ICollection<T>.Add (T item)
546 void ICollection<T>.CopyTo (T [] array, int index)
548 CopyTo (array, index, Count);
551 bool ICollection<T>.IsReadOnly {
552 get { return false; }
555 void ICollection.CopyTo (Array array, int index)
560 throw new ArgumentNullException ("array");
561 if (index < 0 || array.Length <= index)
562 throw new ArgumentOutOfRangeException ("index");
563 if (array.Length - index < Count)
564 throw new ArgumentException ();
566 foreach (Node node in tree)
567 array.SetValue (node.item, index++);
570 bool ICollection.IsSynchronized {
571 get { return false; }
574 // TODO:Is this correct? If this is wrong,please fix.
575 object ICollection.SyncRoot {
580 public struct Enumerator : IEnumerator<T>, IDisposable {
582 RBTree.NodeEnumerator host;
584 IComparer<T> comparer;
589 internal Enumerator (SortedSet<T> set)
592 host = set.tree.GetEnumerator ();
595 internal Enumerator (SortedSet<T> set, T lower, T upper)
598 host = set.tree.GetSuffixEnumerator (lower);
599 comparer = set.Comparer;
604 get { return current; }
607 object IEnumerator.Current {
609 host.check_current ();
610 return ((Node) host.Current).item;
614 public bool MoveNext ()
616 if (!host.MoveNext ())
619 current = ((Node) host.Current).item;
620 return comparer == null || comparer.Compare (upper, current) >= 0;
623 public void Dispose ()
628 void IEnumerator.Reset ()
635 sealed class SortedSubSet : SortedSet<T>, IEnumerable<T>, IEnumerable {
641 public SortedSubSet (SortedSet<T> set, T lower, T upper)
642 : base (set.Comparer)
650 internal override T GetMin ()
652 RBTree.Node lb = null, ub = null;
653 set.tree.Bound (lower, ref lb, ref ub);
655 if (ub == null || set.helper.Compare (upper, ub) < 0)
658 return ((Node) ub).item;
661 internal override T GetMax ()
663 RBTree.Node lb = null, ub = null;
664 set.tree.Bound (upper, ref lb, ref ub);
666 if (lb == null || set.helper.Compare (lower, lb) > 0)
669 return ((Node) lb).item;
672 internal override int GetCount ()
675 using (var e = set.tree.GetSuffixEnumerator (lower)) {
676 while (e.MoveNext () && set.helper.Compare (upper, e.Current) >= 0)
682 internal override bool TryAdd (T item)
685 throw new ArgumentOutOfRangeException ("item");
687 return set.TryAdd (item);
690 internal override bool TryRemove (T item)
695 return set.TryRemove (item);
698 public override bool Contains (T item)
703 return set.Contains (item);
706 public override void Clear ()
708 set.RemoveWhere (InRange);
711 bool InRange (T item)
713 return Comparer.Compare (item, lower) >= 0
714 && Comparer.Compare (item, upper) <= 0;
717 public override SortedSet<T> GetViewBetween (T lowerValue, T upperValue)
719 if (Comparer.Compare (lowerValue, upperValue) > 0)
720 throw new ArgumentException ("The lowerValue is bigger than upperValue");
721 if (!InRange (lowerValue))
722 throw new ArgumentOutOfRangeException ("lowerValue");
723 if (!InRange (upperValue))
724 throw new ArgumentOutOfRangeException ("upperValue");
726 return new SortedSubSet (set, lowerValue, upperValue);
729 internal override Enumerator TryGetEnumerator ()
731 return new Enumerator (set, lower, upper);
734 public override void IntersectWith (IEnumerable<T> other)
736 CheckArgumentNotNull (other, "other");
738 var slice = new SortedSet<T> (this);
739 slice.IntersectWith (other);
742 set.UnionWith (slice);