//
// 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;
SerializationInfo si;
public SortedSet ()
- : this (null as IComparer<T>)
+ : this (Comparer<T>.Default)
{
}
+ public SortedSet (IEnumerable<T> collection)
+ : this (collection, Comparer<T>.Default)
+ {
+ }
+
+ public SortedSet (IEnumerable<T> collection, IComparer<T> comparer)
+ : this (comparer)
+ {
+ if (collection == null)
+ throw new ArgumentNullException ("collection");
+
+ foreach (var item in collection)
+ Add (item);
+ }
+
public SortedSet (IComparer<T> comparer)
{
this.helper = NodeHelper.GetHelper (comparer);
}
public int Count {
- get { return (int) tree.Count; }
+ get { return GetCount (); }
}
- [MonoTODO]
public T Max {
- get { throw new NotImplementedException (); }
+ get { return GetMax (); }
}
- [MonoTODO]
public T Min {
- get { throw new NotImplementedException (); }
+ get { return GetMin (); }
+ }
+
+ internal virtual T GetMax ()
+ {
+ if (tree.Count == 0)
+ return default (T);
+
+ return GetItem (tree.Count - 1);
+ }
+
+ internal virtual T GetMin ()
+ {
+ if (tree.Count == 0)
+ return default (T);
+
+ return GetItem (0);
+ }
+
+ internal virtual int GetCount ()
+ {
+ return tree.Count;
+ }
+
+ T GetItem (int index)
+ {
+ return ((Node) tree [index]).item;
+ }
+
+ public bool Add (T item)
+ {
+ return TryAdd (item);
}
- public virtual bool Add (T item)
+ internal virtual bool TryAdd (T item)
{
var node = new Node (item);
return tree.Intern (item, node) == node;
CopyTo (array, 0, Count);
}
- public virtual void CopyTo (T [] array, int index)
+ public void CopyTo (T [] array, int index)
{
CopyTo (array, index, Count);
}
}
}
- public virtual bool Remove (T item)
+ public bool Remove (T item)
+ {
+ return TryRemove (item);
+ }
+
+ internal virtual bool TryRemove (T item)
{
return tree.Remove (item) != null;
}
- [MonoTODO]
public int RemoveWhere (Predicate<T> match)
{
- throw new NotImplementedException ();
+ var array = ToArray ();
+
+ int count = 0;
+ foreach (var item in array) {
+ if (!match (item))
+ continue;
+
+ Remove (item);
+ count++;
+ }
+
+ return count;
}
- [MonoTODO]
public IEnumerable<T> Reverse ()
{
- throw new NotImplementedException ();
+ for (int i = tree.Count - 1; i >= 0; i--)
+ yield return GetItem (i);
+ }
+
+ T [] ToArray ()
+ {
+ var array = new T [this.Count];
+ CopyTo (array);
+ return array;
}
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]
- public virtual void ExceptWith (IEnumerable<T> other)
+ [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);
}
- [MonoTODO]
- public virtual void GetViewBetween (T lowerValue, T upperValue)
+ public virtual SortedSet<T> GetViewBetween (T lowerValue, T upperValue)
{
- throw new NotImplementedException ();
+ if (Comparer.Compare (lowerValue, upperValue) > 0)
+ throw new ArgumentException ("The lowerValue is bigger than 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 virtual bool IsProperSubsetOf (IEnumerable<T> other)
+ 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 virtual bool IsProperSupersetOf (IEnumerable<T> other)
+ 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 virtual bool IsSubsetOf (IEnumerable<T> other)
+ 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 virtual bool IsSupersetOf (IEnumerable<T> other)
+ 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);
}
- [MonoTODO]
- public virtual bool IsPropertSubsetOf (IEnumerable<T> other)
+ // Precondition: Count != 0, other != null
+ bool is_subset_of (IEnumerable<T> other, bool proper)
{
- throw new NotImplementedException ();
+ 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);
}
- [MonoTODO]
- public virtual bool Overlaps (IEnumerable<T> other)
+ // Precondition: Count != 0, other != null
+ bool is_superset_of (IEnumerable<T> other, bool proper)
{
- throw new NotImplementedException ();
+ 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 virtual bool SetEquals (IEnumerable<T> other)
+ 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 virtual void SymmetricExceptWith (IEnumerable<T> other)
+ 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]
- public virtual void UnionWith (IEnumerable<T> other)
+ SortedSet<T> nodups (IEnumerable<T> other)
{
- throw new NotImplementedException ();
+ 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)
+ {
+ 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);
+ }
+
+ [MonoLimitation ("Isn't O(n) when other is SortedSet<T>")]
+ public void UnionWith (IEnumerable<T> other)
+ {
+ CheckArgumentNotNull (other, "other");
+
+ foreach (T item in other)
+ Add (item);
+ }
+
+ static void CheckArgumentNotNull (object arg, string name)
+ {
+ if (arg == null)
+ throw new ArgumentNullException (name);
}
void ICollection<T>.Add (T item)
{
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 ()
host.Reset ();
}
}
+
+ [Serializable]
+ sealed class SortedSubSet : SortedSet<T>, IEnumerable<T>, IEnumerable {
+
+ SortedSet<T> set;
+ T lower;
+ T upper;
+
+ public SortedSubSet (SortedSet<T> set, T lower, T upper)
+ : base (set.Comparer)
+ {
+ this.set = set;
+ this.lower = lower;
+ this.upper = upper;
+
+ }
+
+ internal override T GetMin ()
+ {
+ RBTree.Node lb = null, ub = null;
+ set.tree.Bound (lower, ref lb, ref ub);
+
+ if (ub == null || set.helper.Compare (upper, ub) < 0)
+ return default (T);
+
+ return ((Node) ub).item;
+ }
+
+ internal override T GetMax ()
+ {
+ RBTree.Node lb = null, ub = null;
+ set.tree.Bound (upper, ref lb, ref ub);
+
+ 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)
+ {
+ if (!InRange (item))
+ throw new ArgumentOutOfRangeException ("item");
+
+ return set.TryAdd (item);
+ }
+
+ internal override bool TryRemove (T item)
+ {
+ if (!InRange (item))
+ return false;
+
+ return set.TryRemove (item);
+ }
+
+ public override bool Contains (T item)
+ {
+ if (!InRange (item))
+ return false;
+
+ return set.Contains (item);
+ }
+
+ public override void Clear ()
+ {
+ set.RemoveWhere (InRange);
+ }
+
+ bool InRange (T item)
+ {
+ return Comparer.Compare (item, lower) >= 0
+ && Comparer.Compare (item, upper) <= 0;
+ }
+
+ public override SortedSet<T> GetViewBetween (T lowerValue, T upperValue)
+ {
+ if (Comparer.Compare (lowerValue, upperValue) > 0)
+ throw new ArgumentException ("The lowerValue is bigger than upperValue");
+ if (!InRange (lowerValue))
+ throw new ArgumentOutOfRangeException ("lowerValue");
+ if (!InRange (upperValue))
+ throw new ArgumentOutOfRangeException ("upperValue");
+
+ return new SortedSubSet (set, lowerValue, upperValue);
+ }
+
+ internal override Enumerator TryGetEnumerator ()
+ {
+ return new Enumerator (set, lower, upper);
+ }
+
+ public override void IntersectWith (IEnumerable<T> other)
+ {
+ CheckArgumentNotNull (other, "other");
+
+ var slice = new SortedSet<T> (this);
+ slice.IntersectWith (other);
+
+ Clear ();
+ set.UnionWith (slice);
+ }
+ }
}
}
projects / mono.git / blobdiff