//
// Authors:
// Jb Evain <jbevain@novell.com>
+// Marek Safar (marek.safar@gmail.com)
//
// Copyright (C) 2010 Novell, Inc (http://www.novell.com)
+// Copyright (C) 2014 Xamarin Inc (http://www.xamarin.com)
//
// Permission is hereby granted, free of charge, to any person obtaining
// a copy of this software and associated documentation files (the
using System;
using System.Collections;
using System.Collections.Generic;
-using System.Linq;
using System.Runtime.Serialization;
using System.Runtime.InteropServices;
using System.Security;
}
public int Count {
- get { return tree.Count; }
+ get { return GetCount (); }
}
public T Max {
return GetItem (0);
}
+ internal virtual int GetCount ()
+ {
+ return tree.Count;
+ }
+
T GetItem (int index)
{
return ((Node) tree [index]).item;
}
public Enumerator GetEnumerator ()
+ {
+ return TryGetEnumerator ();
+ }
+
+ internal virtual Enumerator TryGetEnumerator ()
{
return new Enumerator (this);
}
IEnumerator<T> IEnumerable<T>.GetEnumerator ()
{
- return new Enumerator (this);
+ return GetEnumerator ();
}
IEnumerator IEnumerable.GetEnumerator ()
{
- return new Enumerator (this);
+ return GetEnumerator ();
}
public static IEqualityComparer<SortedSet<T>> CreateSetComparer ()
OnDeserialization (sender);
}
- [MonoTODO]
+ [MonoLimitation ("Isn't O(n) when other is SortedSet<T>")]
public void ExceptWith (IEnumerable<T> other)
{
- throw new NotImplementedException ();
+ if (other == this) {
+ Clear ();
+ return;
+ }
+
+ CheckArgumentNotNull (other, "other");
+ foreach (T item in other)
+ Remove (item);
}
public virtual SortedSet<T> GetViewBetween (T lowerValue, T upperValue)
return new SortedSubSet (this, lowerValue, upperValue);
}
- [MonoTODO]
+ [MonoLimitation ("Isn't O(n) when other is SortedSet<T>")]
public virtual void IntersectWith (IEnumerable<T> other)
{
- throw new NotImplementedException ();
+ CheckArgumentNotNull (other, "other");
+
+ RBTree newtree = new RBTree (helper);
+ foreach (T item in other) {
+ var node = tree.Remove (item);
+ if (node != null)
+ newtree.Intern (item, node);
+ }
+ tree = newtree;
}
- [MonoTODO]
public bool IsProperSubsetOf (IEnumerable<T> other)
{
- throw new NotImplementedException ();
+ CheckArgumentNotNull (other, "other");
+
+ if (Count == 0) {
+ foreach (T item in other)
+ return true; // this idiom means: if 'other' is non-empty, return true
+ return false;
+ }
+
+ return is_subset_of (other, true);
}
- [MonoTODO]
public bool IsProperSupersetOf (IEnumerable<T> other)
{
- throw new NotImplementedException ();
+ CheckArgumentNotNull (other, "other");
+
+ if (Count == 0)
+ return false;
+
+ return is_superset_of (other, true);
}
- [MonoTODO]
public bool IsSubsetOf (IEnumerable<T> other)
{
- throw new NotImplementedException ();
+ CheckArgumentNotNull (other, "other");
+
+ if (Count == 0)
+ return true;
+
+ return is_subset_of (other, false);
}
- [MonoTODO]
public bool IsSupersetOf (IEnumerable<T> other)
{
- throw new NotImplementedException ();
+ CheckArgumentNotNull (other, "other");
+
+ if (Count == 0) {
+ foreach (T item in other)
+ return false; // this idiom means: if 'other' is non-empty, return false
+ return true;
+ }
+
+ return is_superset_of (other, false);
+ }
+
+ // Precondition: Count != 0, other != null
+ bool is_subset_of (IEnumerable<T> other, bool proper)
+ {
+ SortedSet<T> that = nodups (other);
+
+ if (Count > that.Count)
+ return false;
+ // Count != 0 && Count <= that.Count => that.Count != 0
+ if (proper && Count == that.Count)
+ return false;
+ return that.covers (this);
+ }
+
+ // Precondition: Count != 0, other != null
+ bool is_superset_of (IEnumerable<T> other, bool proper)
+ {
+ SortedSet<T> that = nodups (other);
+
+ if (that.Count == 0)
+ return true;
+ if (Count < that.Count)
+ return false;
+ if (proper && Count == that.Count)
+ return false;
+ return this.covers (that);
}
- [MonoTODO]
public bool Overlaps (IEnumerable<T> other)
{
- throw new NotImplementedException ();
+ CheckArgumentNotNull (other, "other");
+
+ if (Count == 0)
+ return false;
+
+ // Don't use 'nodups' here. Only optimize the SortedSet<T> case
+ SortedSet<T> that = other as SortedSet<T>;
+ if (that != null && that.Comparer != Comparer)
+ that = null;
+
+ if (that != null)
+ return that.Count != 0 && overlaps (that);
+
+ foreach (T item in other)
+ if (Contains (item))
+ return true;
+ return false;
}
- [MonoTODO]
public bool SetEquals (IEnumerable<T> other)
{
- throw new NotImplementedException ();
+ CheckArgumentNotNull (other, "other");
+
+ if (Count == 0) {
+ foreach (T item in other)
+ return false;
+ return true;
+ }
+
+ SortedSet<T> that = nodups (other);
+
+ if (Count != that.Count)
+ return false;
+
+ using (var t = that.GetEnumerator ()) {
+ foreach (T item in this) {
+ if (!t.MoveNext ())
+ throw new SystemException ("count wrong somewhere: this longer than that");
+ if (Comparer.Compare (item, t.Current) != 0)
+ return false;
+ }
+ if (t.MoveNext ())
+ throw new SystemException ("count wrong somewhere: this shorter than that");
+ return true;
+ }
}
- [MonoTODO]
+ SortedSet<T> nodups (IEnumerable<T> other)
+ {
+ SortedSet<T> that = other as SortedSet<T>;
+ if (that != null && that.Comparer == Comparer)
+ return that;
+ return new SortedSet<T> (other, Comparer);
+ }
+
+ bool covers (SortedSet<T> that)
+ {
+ using (var t = that.GetEnumerator ()) {
+ if (!t.MoveNext ())
+ return true;
+ foreach (T item in this) {
+ int cmp = Comparer.Compare (item, t.Current);
+ if (cmp > 0)
+ return false;
+ if (cmp == 0 && !t.MoveNext ())
+ return true;
+ }
+ return false;
+ }
+ }
+
+ bool overlaps (SortedSet<T> that)
+ {
+ using (var t = that.GetEnumerator ()) {
+ if (!t.MoveNext ())
+ return false;
+ foreach (T item in this) {
+ int cmp;
+ while ((cmp = Comparer.Compare (item, t.Current)) > 0) {
+ if (!t.MoveNext ())
+ return false;
+ }
+ if (cmp == 0)
+ return true;
+ }
+ return false;
+ }
+ }
+
+ [MonoLimitation ("Isn't O(n) when other is SortedSet<T>")]
public void SymmetricExceptWith (IEnumerable<T> other)
{
- throw new NotImplementedException ();
+ if (other == this) {
+ Clear ();
+ return;
+ }
+
+ SortedSet<T> that_minus_this = new SortedSet<T> (Comparer);
+
+ // compute this - that and that - this in parallel
+ foreach (T item in nodups (other))
+ if (!Remove (item))
+ that_minus_this.Add (item);
+
+ UnionWith (that_minus_this);
}
- [MonoTODO]
+ [MonoLimitation ("Isn't O(n) when other is SortedSet<T>")]
public void UnionWith (IEnumerable<T> other)
{
- throw new NotImplementedException ();
+ CheckArgumentNotNull (other, "other");
+
+ foreach (T item in other)
+ Add (item);
}
- void ICollection<T>.Add (T item)
+ static void CheckArgumentNotNull (object arg, string name)
{
- Add (item);
+ if (arg == null)
+ throw new ArgumentNullException (name);
}
- void ICollection<T>.CopyTo (T [] array, int index)
+ void ICollection<T>.Add (T item)
{
- CopyTo (array, index, Count);
+ Add (item);
}
-
+
bool ICollection<T>.IsReadOnly {
get { return false; }
}
RBTree.NodeEnumerator host;
+ IComparer<T> comparer;
+
T current;
+ T upper;
internal Enumerator (SortedSet<T> set)
+ : this ()
{
host = set.tree.GetEnumerator ();
- current = default (T);
+ }
+
+ internal Enumerator (SortedSet<T> set, T lower, T upper)
+ : this ()
+ {
+ host = set.tree.GetSuffixEnumerator (lower);
+ comparer = set.Comparer;
+ this.upper = upper;
}
public T Current {
return false;
current = ((Node) host.Current).item;
- return true;
+ return comparer == null || comparer.Compare (upper, current) >= 0;
}
public void Dispose ()
this.set = set;
this.lower = lower;
this.upper = upper;
+
}
internal override T GetMin ()
{
- for (int i = 0; i < set.tree.Count; i++) {
- var item = set.GetItem (i);
- if (InRange (item))
- return item;
- }
+ RBTree.Node lb = null, ub = null;
+ set.tree.Bound (lower, ref lb, ref ub);
- return default (T);
+ if (ub == null || set.helper.Compare (upper, ub) < 0)
+ return default (T);
+
+ return ((Node) ub).item;
}
internal override T GetMax ()
{
- for (int i = set.tree.Count - 1; i >= 0; i--) {
- var item = set.GetItem (i);
- if (InRange (item))
- return item;
- }
+ RBTree.Node lb = null, ub = null;
+ set.tree.Bound (upper, ref lb, ref ub);
- return default (T);
+ if (lb == null || set.helper.Compare (lower, lb) > 0)
+ return default (T);
+
+ return ((Node) lb).item;
+ }
+
+ internal override int GetCount ()
+ {
+ int count = 0;
+ using (var e = set.tree.GetSuffixEnumerator (lower)) {
+ while (e.MoveNext () && set.helper.Compare (upper, e.Current) >= 0)
+ ++count;
+ }
+ return count;
}
internal override bool TryAdd (T item)
return new SortedSubSet (set, lowerValue, upperValue);
}
- public IEnumerator<T> GetEnumerator ()
+ internal override Enumerator TryGetEnumerator ()
{
- var yielding = false;
-
- foreach (Node node in set.tree) {
- var item = node.item;
-
- if (InRange (item)) {
- yield return item;
- yielding = true;
- } else if (yielding)
- yield break;
- }
+ return new Enumerator (set, lower, upper);
}
- IEnumerator<T> IEnumerable<T>.GetEnumerator ()
+ public override void IntersectWith (IEnumerable<T> other)
{
- return GetEnumerator ();
- }
+ CheckArgumentNotNull (other, "other");
- IEnumerator IEnumerable.GetEnumerator ()
- {
- return GetEnumerator ();
+ var slice = new SortedSet<T> (this);
+ slice.IntersectWith (other);
+
+ Clear ();
+ set.UnionWith (slice);
}
}
}
projects / mono.git / blobdiff