SortedSet<T> comparison between Mono and Microsoft

MonoSortedSet.cs

//
// SortedSet.cs
//
// Authors:
//  Jb Evain  <jbevain@novell.com>
//
// Copyright (C) 2010 Novell, Inc (http://www.novell.com)
//
// Permission is hereby granted, free of charge, to any person obtaining
// a copy of this software and associated documentation files (the
// "Software"), to deal in the Software without restriction, including
// without limitation the rights to use, copy, modify, merge, publish,
// distribute, sublicense, and/or sell copies of the Software, and to
// permit persons to whom the Software is furnished to do so, subject to
// the following conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
// LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
//

using System;
using System.Collections;
using System.Collections.Generic;
using System.Runtime.Serialization;
using System.Runtime.InteropServices;
using System.Security;
using System.Security.Permissions;
using System.Diagnostics;

// MonoSortedSet is basically implemented as a reduction of SortedDictionary<K, V>


namespace System.Collections.Generic {

	[Serializable]
	[DebuggerDisplay ("Count={Count}")]
	public class MonoSortedSet<T> : ISet<T>, ICollection, ISerializable, IDeserializationCallback
	{
		class Node : RBTree.Node {

			public T item;

			public Node (T item)
			{
				this.item = item;
			}

			public override void SwapValue (RBTree.Node other)
			{
				var o = (Node) other;
				var i = this.item;
				this.item = o.item;
				o.item = i;
			}
		}

		class NodeHelper : RBTree.INodeHelper<T> {

			static NodeHelper Default = new NodeHelper (Comparer<T>.Default);

			public IComparer<T> comparer;

			public int Compare (T item, RBTree.Node node)
			{
				return comparer.Compare (item, ((Node) node).item);
			}

			public RBTree.Node CreateNode (T item)
			{
				return new Node (item);
			}

			NodeHelper (IComparer<T> comparer)
			{
				this.comparer = comparer;
			}

			public static NodeHelper GetHelper (IComparer<T> comparer)
			{
				if (comparer == null || comparer == Comparer<T>.Default)
					return Default;

				return new NodeHelper (comparer);
			}
		}

		RBTree tree;
		NodeHelper helper;
		SerializationInfo si;

		public MonoSortedSet ()
			: this (Comparer<T>.Default)
		{
		}

		public MonoSortedSet (IEnumerable<T> collection)
			: this (collection, Comparer<T>.Default)
		{
		}

		public MonoSortedSet (IEnumerable<T> collection, IComparer<T> comparer)
			: this (comparer)
		{
			if (collection == null)
				throw new ArgumentNullException ("collection");

			foreach (var item in collection)
				Add (item);
		}

		public MonoSortedSet (IComparer<T> comparer)
		{
			this.helper = NodeHelper.GetHelper (comparer);
			this.tree = new RBTree (this.helper);
		}

		protected MonoSortedSet (SerializationInfo info, StreamingContext context)
		{
			this.si = info;
		}

		public IComparer<T> Comparer {
			get { return helper.comparer; }
		}

		public int Count {
			get { return GetCount (); }
		}

		public T Max {
			get { return GetMax (); }
		}

		public T Min {
			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);
		}

		internal virtual bool TryAdd (T item)
		{
			var node = new Node (item);
			return tree.Intern (item, node) == node;
		}

		public virtual void Clear ()
		{
			tree.Clear ();
		}

		public virtual bool Contains (T item)
		{
			return tree.Lookup (item) != null;
		}

		public void CopyTo (T [] array)
		{
			CopyTo (array, 0, Count);
		}

		public void CopyTo (T [] array, int index)
		{
			CopyTo (array, index, Count);
		}

		public void CopyTo (T [] array, int index, int count)
		{
			if (array == null)
				throw new ArgumentNullException ("array");
			if (index < 0)
				throw new ArgumentOutOfRangeException ("index");
			if (index > array.Length)
				throw new ArgumentException ("index larger than largest valid index of array");
			if (array.Length - index < count)
				throw new ArgumentException ("destination array cannot hold the requested elements");

			foreach (Node node in tree) {
				if (count-- == 0)
					break;

				array [index++] = node.item;
			}
		}

		public bool Remove (T item)
		{
			return TryRemove (item);
		}

		internal virtual bool TryRemove (T item)
		{
			return tree.Remove (item) != null;
		}

		public int RemoveWhere (Predicate<T> match)
		{
			var array = ToArray ();

			int count = 0;
			foreach (var item in array) {
				if (!match (item))
					continue;

				Remove (item);
				count++;
			}

			return count;
		}

		public IEnumerable<T> Reverse ()
		{
			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 GetEnumerator ();
		}

		IEnumerator IEnumerable.GetEnumerator ()
		{
			return GetEnumerator ();
		}

		public static IEqualityComparer<MonoSortedSet<T>> CreateSetComparer ()
		{
			return CreateSetComparer (EqualityComparer<T>.Default);
		}

		public static IEqualityComparer<MonoSortedSet<T>> CreateSetComparer (IEqualityComparer<T> memberEqualityComparer)
		{
			throw new NotImplementedException ();
		}

		protected virtual void GetObjectData (SerializationInfo info, StreamingContext context)
		{
			throw new NotImplementedException ();
		}

		void ISerializable.GetObjectData (SerializationInfo info, StreamingContext context)
		{
			GetObjectData (info, context);
		}

		protected virtual void OnDeserialization (object sender)
		{
			if (si == null)
				return;

			throw new NotImplementedException ();
		}

		void IDeserializationCallback.OnDeserialization (object sender)
		{
			OnDeserialization (sender);
		}

		public void ExceptWith (IEnumerable<T> other)
		{
			CheckArgumentNotNull (other, "other");
			foreach (T item in other)
				Remove (item);
		}

		public virtual MonoSortedSet<T> GetViewBetween (T lowerValue, T upperValue)
		{
			if (Comparer.Compare (lowerValue, upperValue) > 0)
				throw new ArgumentException ("The lowerValue is bigger than upperValue");

			return new SortedSubSet (this, lowerValue, upperValue);
		}

		public virtual void IntersectWith (IEnumerable<T> other)
		{
			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;
		}

		public bool IsProperSubsetOf (IEnumerable<T> other)
		{
			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);
		}

		public bool IsProperSupersetOf (IEnumerable<T> other)
		{
			CheckArgumentNotNull (other, "other");

			if (Count == 0)
				return false;

			return is_superset_of (other, true);
		}

		public bool IsSubsetOf (IEnumerable<T> other)
		{
			CheckArgumentNotNull (other, "other");

			if (Count == 0)
				return true;

			return is_subset_of (other, false);
		}

		public bool IsSupersetOf (IEnumerable<T> other)
		{
			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)
		{
			MonoSortedSet<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)
		{
			MonoSortedSet<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);
		}

		public bool Overlaps (IEnumerable<T> other)
		{
			CheckArgumentNotNull (other, "other");

			if (Count == 0)
				return false;

			// Don't use 'nodups' here.  Only optimize the MonoSortedSet<T> case
			MonoSortedSet<T> that = other as MonoSortedSet<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;
		}

		public bool SetEquals (IEnumerable<T> other)
		{
			CheckArgumentNotNull (other, "other");

			if (Count == 0) {
				foreach (T item in other)
					return false;
				return true;
			}

			MonoSortedSet<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;
			}
		}

		MonoSortedSet<T> nodups (IEnumerable<T> other)
		{
			MonoSortedSet<T> that = other as MonoSortedSet<T>;
			if (that != null && that.Comparer == Comparer)
				return that;
			return new MonoSortedSet<T> (other, Comparer);
		}

		bool covers (MonoSortedSet<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 (MonoSortedSet<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;
			}
		}

		public void SymmetricExceptWith (IEnumerable<T> other)
		{
			MonoSortedSet<T> that_minus_this = new MonoSortedSet<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);
		}

		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; }
		}

		void ICollection.CopyTo (Array array, int index)
		{
			if (Count == 0)
				return;
			if (array == null)
				throw new ArgumentNullException ("array");
			if (index < 0 || array.Length <= index)
				throw new ArgumentOutOfRangeException ("index");
			if (array.Length - index < Count)
				throw new ArgumentException ();

			foreach (Node node in tree)
				array.SetValue (node.item, index++);
		}

		bool ICollection.IsSynchronized {
			get { return false; }
		}

		// TODO:Is this correct? If this is wrong,please fix.
		object ICollection.SyncRoot {
			get { return this; }
		}

		[Serializable]
		public struct Enumerator : IEnumerator<T>, IDisposable {

			RBTree.NodeEnumerator host;

			IComparer<T> comparer;

			T current;
			T upper;

			internal Enumerator (MonoSortedSet<T> set)
				: this ()
			{
				host = set.tree.GetEnumerator ();
			}

			internal Enumerator (MonoSortedSet<T> set, T lower, T upper)
				: this ()
			{
				host = set.tree.GetSuffixEnumerator (lower);
				comparer = set.Comparer;
				this.upper = upper;
			}

			public T Current {
				get { return current; }
			}

			object IEnumerator.Current {
				get {
					host.check_current ();
					return ((Node) host.Current).item;
				}
			}

			public bool MoveNext ()
			{
				if (!host.MoveNext ())
					return false;

				current = ((Node) host.Current).item;
				return comparer == null || comparer.Compare (upper, current) >= 0;
			}

			public void Dispose ()
			{
				host.Dispose ();
			}

			void IEnumerator.Reset ()
			{
				host.Reset ();
			}
		}

		[Serializable]
		sealed class SortedSubSet : MonoSortedSet<T>, IEnumerable<T>, IEnumerable {

			MonoSortedSet<T> set;
			T lower;
			T upper;

			public SortedSubSet (MonoSortedSet<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 MonoSortedSet<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 MonoSortedSet<T> (this);
				slice.IntersectWith (other);

				Clear ();
				set.UnionWith (slice);
			}
		}
	}
}

Program.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace ConsoleApplication1
{
    class Program
    {
        static void TestMs()
        {
            var s = new SortedSet<int>();
            int n = 100000;
            var rand = new Random(1000000007);
            int sum = 0;
            for (int i = 0; i < n; ++i)
            {
                s.Add(rand.Next());
                if (rand.Next() % 2 == 0)
                {
                    int l = rand.Next(int.MaxValue / 2 - 10);
                    int r = l + rand.Next(int.MaxValue / 2 - 10);
                    var t = s.GetViewBetween(l, r);
                    sum += t.Min;
                }
            }
        }

        static void TestMono()
        {
            var s = new MonoSortedSet<int>();
            int n = 100000;
            var rand = new Random(1000000007);
            int sum = 0;
            for (int i = 0; i < n; ++i)
            {
                s.Add(rand.Next());
                if (rand.Next() % 2 == 0)
                {
                    int l = rand.Next(int.MaxValue / 2 - 10);
                    int r = l + rand.Next(int.MaxValue / 2 - 10);
                    var t = s.GetViewBetween(l, r);
                    sum += t.Min;
                }
            }
        }

        static void Main(string[] args)
        {
            Stopwatch watch = new Stopwatch();

            watch.Start();
            TestMs();
            watch.Stop();

            Console.WriteLine("ms version time:{0}", watch.ElapsedMilliseconds);
            watch.Reset();

            watch.Start();
            TestMono();
            Console.WriteLine("mono version time:{0}", watch.ElapsedMilliseconds);

            Console.ReadLine();
        }
    }
}

RBTree.cs

//
// System.Collections.Generic.RBTree
//
// Authors:
//   Raja R Harinath <rharinath@novell.com>
//

//
// Copyright (C) 2007, Novell, Inc.
//
// Permission is hereby granted, free of charge, to any person obtaining
// a copy of this software and associated documentation files (the
// "Software"), to deal in the Software without restriction, including
// without limitation the rights to use, copy, modify, merge, publish,
// distribute, sublicense, and/or sell copies of the Software, and to
// permit persons to whom the Software is furnished to do so, subject to
// the following conditions:
// 
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
// 
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
// LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
//

#define ONE_MEMBER_CACHE

using System;
using System.Collections;

namespace System.Collections.Generic
{
    [Serializable]
    internal class RBTree : IEnumerable, IEnumerable<RBTree.Node>
    {
        public interface INodeHelper<T>
        {
            int Compare(T key, Node node);
            Node CreateNode(T key);
        }

        public abstract class Node
        {
            public Node left, right;
            uint size_black;

            const uint black_mask = 1;
            const int black_shift = 1;
            public bool IsBlack
            {
                get { return (size_black & black_mask) == black_mask; }
                set { size_black = value ? (size_black | black_mask) : (size_black & ~black_mask); }
            }

            public uint Size
            {
                get { return size_black >> black_shift; }
                set { size_black = (value << black_shift) | (size_black & black_mask); }
            }

            public uint FixSize()
            {
                Size = 1;
                if (left != null)
                    Size += left.Size;
                if (right != null)
                    Size += right.Size;
                return Size;
            }

            public Node()
            {
                size_black = 2; // Size == 1, IsBlack = false
            }

            public abstract void SwapValue(Node other);

#if TEST
			public int VerifyInvariants ()
			{
				int black_depth_l = 0;
				int black_depth_r = 0;
				uint size = 1;
				bool child_is_red = false;
				if (left != null) {
					black_depth_l = left.VerifyInvariants ();
					size += left.Size;
					child_is_red |= !left.IsBlack;
				}

				if (right != null) {
					black_depth_r = right.VerifyInvariants ();
					size += right.Size;
					child_is_red |= !right.IsBlack;
				}

				if (black_depth_l != black_depth_r)
					throw new SystemException ("Internal error: black depth mismatch");

				if (!IsBlack && child_is_red)
					throw new SystemException ("Internal error: red-red conflict");
				if (Size != size)
					throw new SystemException ("Internal error: metadata error");

				return black_depth_l + (IsBlack ? 1 : 0);
			}

			public abstract void Dump (string indent);
#endif
        }

        Node root;
        object hlp;
        uint version;

#if ONE_MEMBER_CACHE
#if TARGET_JVM
		static readonly LocalDataStoreSlot _cachedPathStore = System.Threading.Thread.AllocateDataSlot ();

		static List<Node> cached_path {
			get { return (List<Node>) System.Threading.Thread.GetData (_cachedPathStore); }
			set { System.Threading.Thread.SetData (_cachedPathStore, value); }
		}
#else
        [ThreadStatic]
        static List<Node> cached_path;
#endif

        static List<Node> alloc_path()
        {
            if (cached_path == null)
                return new List<Node>();

            List<Node> path = cached_path;
            cached_path = null;
            return path;
        }

        static void release_path(List<Node> path)
        {
            if (cached_path == null || cached_path.Capacity < path.Capacity)
            {
                path.Clear();
                cached_path = path;
            }
        }
#else
		static List<Node> alloc_path ()
		{
			return new List<Node> ();
		}

		static void release_path (List<Node> path)
		{
		}
#endif

        public RBTree(object hlp)
        {
            // hlp is INodeHelper<T> for some T
            this.hlp = hlp;
        }

        public void Clear()
        {
            root = null;
            ++version;
        }

        // if key is already in the tree, return the node associated with it
        // if not, insert new_node into the tree, and return it
        public Node Intern<T>(T key, Node new_node)
        {
            if (root == null)
            {
                if (new_node == null)
                    new_node = ((INodeHelper<T>)hlp).CreateNode(key);
                root = new_node;
                root.IsBlack = true;
                ++version;
                return root;
            }

            List<Node> path = alloc_path();
            int in_tree_cmp = find_key(key, path);
            Node retval = path[path.Count - 1];
            if (retval == null)
            {
                if (new_node == null)
                    new_node = ((INodeHelper<T>)hlp).CreateNode(key);
                retval = do_insert(in_tree_cmp, new_node, path);
            }
            // no need for a try .. finally, this is only used to mitigate allocations
            release_path(path);
            return retval;
        }

        // returns the just-removed node (or null if the value wasn't in the tree)
        public Node Remove<T>(T key)
        {
            if (root == null)
                return null;

            List<Node> path = alloc_path();
            int in_tree_cmp = find_key(key, path);
            Node retval = null;
            if (in_tree_cmp == 0)
                retval = do_remove(path);
            // no need for a try .. finally, this is only used to mitigate allocations
            release_path(path);
            return retval;
        }

        public Node Lookup<T>(T key)
        {
            INodeHelper<T> hlp = (INodeHelper<T>)this.hlp;
            Node current = root;
            while (current != null)
            {
                int c = hlp.Compare(key, current);
                if (c == 0)
                    break;
                current = c < 0 ? current.left : current.right;
            }
            return current;
        }

        public void Bound<T>(T key, ref Node lower, ref Node upper)
        {
            INodeHelper<T> hlp = (INodeHelper<T>)this.hlp;
            Node current = root;
            while (current != null)
            {
                int c = hlp.Compare(key, current);
                if (c <= 0)
                    upper = current;
                if (c >= 0)
                    lower = current;
                if (c == 0)
                    break;
                current = c < 0 ? current.left : current.right;
            }
        }

        public int Count
        {
            get { return root == null ? 0 : (int)root.Size; }
        }

        public Node this[int index]
        {
            get
            {
                if (index < 0 || index >= Count)
                    throw new IndexOutOfRangeException("index");

                Node current = root;
                while (current != null)
                {
                    int left_size = current.left == null ? 0 : (int)current.left.Size;
                    if (index == left_size)
                        return current;
                    if (index < left_size)
                    {
                        current = current.left;
                    }
                    else
                    {
                        index -= left_size + 1;
                        current = current.right;
                    }
                }
                throw new SystemException("Internal Error: index calculation");
            }
        }

        public NodeEnumerator GetEnumerator()
        {
            return new NodeEnumerator(this);
        }

        // Get an enumerator that starts at 'key' or the next higher element in the tree
        public NodeEnumerator GetSuffixEnumerator<T>(T key)
        {
            var pennants = new Stack<Node>();
            INodeHelper<T> hlp = (INodeHelper<T>)this.hlp;
            Node current = root;
            while (current != null)
            {
                int c = hlp.Compare(key, current);
                if (c <= 0)
                    pennants.Push(current);
                if (c == 0)
                    break;
                current = c < 0 ? current.left : current.right;
            }
            return new NodeEnumerator(this, pennants);
        }

        IEnumerator<Node> IEnumerable<Node>.GetEnumerator()
        {
            return GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

#if TEST
		public void VerifyInvariants ()
		{
			if (root != null) {
				if (!root.IsBlack)
					throw new SystemException ("Internal Error: root is not black");
				root.VerifyInvariants ();
			}
		}

		public void Dump ()
		{
			if (root != null)
				root.Dump ("");
		}
#endif

        // Pre-condition: root != null
        int find_key<T>(T key, List<Node> path)
        {
            INodeHelper<T> hlp = (INodeHelper<T>)this.hlp;
            int c = 0;
            Node sibling = null;
            Node current = root;

            if (path != null)
                path.Add(root);

            while (current != null)
            {
                c = hlp.Compare(key, current);
                if (c == 0)
                    return c;

                if (c < 0)
                {
                    sibling = current.right;
                    current = current.left;
                }
                else
                {
                    sibling = current.left;
                    current = current.right;
                }

                if (path != null)
                {
                    path.Add(sibling);
                    path.Add(current);
                }
            }

            return c;
        }

        Node do_insert(int in_tree_cmp, Node current, List<Node> path)
        {
            path[path.Count - 1] = current;
            Node parent = path[path.Count - 3];

            if (in_tree_cmp < 0)
                parent.left = current;
            else
                parent.right = current;
            for (int i = 0; i < path.Count - 2; i += 2)
                ++path[i].Size;

            if (!parent.IsBlack)
                rebalance_insert(path);

            if (!root.IsBlack)
                throw new SystemException("Internal error: root is not black");

            ++version;
            return current;
        }

        Node do_remove(List<Node> path)
        {
            int curpos = path.Count - 1;

            Node current = path[curpos];
            if (current.left != null)
            {
                Node pred = right_most(current.left, current.right, path);
                current.SwapValue(pred);
                if (pred.left != null)
                {
                    Node ppred = pred.left;
                    path.Add(null); path.Add(ppred);
                    pred.SwapValue(ppred);
                }
            }
            else if (current.right != null)
            {
                Node succ = current.right;
                path.Add(null); path.Add(succ);
                current.SwapValue(succ);
            }

            curpos = path.Count - 1;
            current = path[curpos];

            if (current.Size != 1)
                throw new SystemException("Internal Error: red-black violation somewhere");

            // remove it from our data structures
            path[curpos] = null;
            node_reparent(curpos == 0 ? null : path[curpos - 2], current, 0, null);

            for (int i = 0; i < path.Count - 2; i += 2)
                --path[i].Size;

            if (current.IsBlack)
            {
                current.IsBlack = false;
                if (curpos != 0)
                    rebalance_delete(path);
            }

            if (root != null && !root.IsBlack)
                throw new SystemException("Internal Error: root is not black");

            ++version;
            return current;
        }

        // Pre-condition: current is red
        void rebalance_insert(List<Node> path)
        {
            int curpos = path.Count - 1;
            do
            {
                // parent == curpos-2, uncle == curpos-3, grandpa == curpos-4
                if (path[curpos - 3] == null || path[curpos - 3].IsBlack)
                {
                    rebalance_insert__rotate_final(curpos, path);
                    return;
                }

                path[curpos - 2].IsBlack = path[curpos - 3].IsBlack = true;

                curpos -= 4; // move to the grandpa

                if (curpos == 0) // => current == root
                    return;
                path[curpos].IsBlack = false;
            } while (!path[curpos - 2].IsBlack);
        }

        // Pre-condition: current is black
        void rebalance_delete(List<Node> path)
        {
            int curpos = path.Count - 1;
            do
            {
                Node sibling = path[curpos - 1];
                // current is black => sibling != null
                if (!sibling.IsBlack)
                {
                    // current is black && sibling is red 
                    // => both sibling.left and sibling.right are black, and are not null
                    curpos = ensure_sibling_black(curpos, path);
                    // one of the nephews became the new sibling -- in either case, sibling != null
                    sibling = path[curpos - 1];
                }

                if ((sibling.left != null && !sibling.left.IsBlack) ||
                    (sibling.right != null && !sibling.right.IsBlack))
                {
                    rebalance_delete__rotate_final(curpos, path);
                    return;
                }

                sibling.IsBlack = false;

                curpos -= 2; // move to the parent

                if (curpos == 0)
                    return;
            } while (path[curpos].IsBlack);
            path[curpos].IsBlack = true;
        }

        void rebalance_insert__rotate_final(int curpos, List<Node> path)
        {
            Node current = path[curpos];
            Node parent = path[curpos - 2];
            Node grandpa = path[curpos - 4];

            uint grandpa_size = grandpa.Size;

            Node new_root;

            bool l1 = parent == grandpa.left;
            bool l2 = current == parent.left;
            if (l1 && l2)
            {
                grandpa.left = parent.right; parent.right = grandpa;
                new_root = parent;
            }
            else if (l1 && !l2)
            {
                grandpa.left = current.right; current.right = grandpa;
                parent.right = current.left; current.left = parent;
                new_root = current;
            }
            else if (!l1 && l2)
            {
                grandpa.right = current.left; current.left = grandpa;
                parent.left = current.right; current.right = parent;
                new_root = current;
            }
            else
            { // (!l1 && !l2)
                grandpa.right = parent.left; parent.left = grandpa;
                new_root = parent;
            }

            grandpa.FixSize(); grandpa.IsBlack = false;
            if (new_root != parent)
                parent.FixSize(); /* parent is red already, so no need to set it */

            new_root.IsBlack = true;
            node_reparent(curpos == 4 ? null : path[curpos - 6], grandpa, grandpa_size, new_root);
        }

        // Pre-condition: sibling is black, and one of sibling.left and sibling.right is red
        void rebalance_delete__rotate_final(int curpos, List<Node> path)
        {
            //Node current = path [curpos];
            Node sibling = path[curpos - 1];
            Node parent = path[curpos - 2];

            uint parent_size = parent.Size;
            bool parent_was_black = parent.IsBlack;

            Node new_root;
            if (parent.right == sibling)
            {
                // if far nephew is black
                if (sibling.right == null || sibling.right.IsBlack)
                {
                    // => near nephew is red, move it up
                    Node nephew = sibling.left;
                    parent.right = nephew.left; nephew.left = parent;
                    sibling.left = nephew.right; nephew.right = sibling;
                    new_root = nephew;
                }
                else
                {
                    parent.right = sibling.left; sibling.left = parent;
                    sibling.right.IsBlack = true;
                    new_root = sibling;
                }
            }
            else
            {
                // if far nephew is black
                if (sibling.left == null || sibling.left.IsBlack)
                {
                    // => near nephew is red, move it up
                    Node nephew = sibling.right;
                    parent.left = nephew.right; nephew.right = parent;
                    sibling.right = nephew.left; nephew.left = sibling;
                    new_root = nephew;
                }
                else
                {
                    parent.left = sibling.right; sibling.right = parent;
                    sibling.left.IsBlack = true;
                    new_root = sibling;
                }
            }

            parent.FixSize(); parent.IsBlack = true;
            if (new_root != sibling)
                sibling.FixSize(); /* sibling is already black, so no need to set it */

            new_root.IsBlack = parent_was_black;
            node_reparent(curpos == 2 ? null : path[curpos - 4], parent, parent_size, new_root);
        }

        // Pre-condition: sibling is red (=> parent, sibling.left and sibling.right are black)
        int ensure_sibling_black(int curpos, List<Node> path)
        {
            Node current = path[curpos];
            Node sibling = path[curpos - 1];
            Node parent = path[curpos - 2];

            bool current_on_left;
            uint parent_size = parent.Size;

            if (parent.right == sibling)
            {
                parent.right = sibling.left; sibling.left = parent;
                current_on_left = true;
            }
            else
            {
                parent.left = sibling.right; sibling.right = parent;
                current_on_left = false;
            }

            parent.FixSize(); parent.IsBlack = false;

            sibling.IsBlack = true;
            node_reparent(curpos == 2 ? null : path[curpos - 4], parent, parent_size, sibling);

            // accomodate the rotation
            if (curpos + 1 == path.Count)
            {
                path.Add(null);
                path.Add(null);
            }

            path[curpos - 2] = sibling;
            path[curpos - 1] = current_on_left ? sibling.right : sibling.left;
            path[curpos] = parent;
            path[curpos + 1] = current_on_left ? parent.right : parent.left;
            path[curpos + 2] = current;

            return curpos + 2;
        }

        void node_reparent(Node orig_parent, Node orig, uint orig_size, Node updated)
        {
            if (updated != null && updated.FixSize() != orig_size)
                throw new SystemException("Internal error: rotation");

            if (orig == root)
                root = updated;
            else if (orig == orig_parent.left)
                orig_parent.left = updated;
            else if (orig == orig_parent.right)
                orig_parent.right = updated;
            else
                throw new SystemException("Internal error: path error");
        }

        // Pre-condition: current != null
        static Node right_most(Node current, Node sibling, List<Node> path)
        {
            for (; ; )
            {
                path.Add(sibling);
                path.Add(current);
                if (current.right == null)
                    return current;
                sibling = current.left;
                current = current.right;
            }
        }

        [Serializable]
        public struct NodeEnumerator : IEnumerator, IEnumerator<Node>
        {
            RBTree tree;
            uint version;

            Stack<Node> pennants, init_pennants;

            internal NodeEnumerator(RBTree tree)
                : this()
            {
                this.tree = tree;
                version = tree.version;
            }

            internal NodeEnumerator(RBTree tree, Stack<Node> init_pennants)
                : this(tree)
            {
                this.init_pennants = init_pennants;
            }

            public void Reset()
            {
                check_version();
                pennants = null;
            }

            public Node Current
            {
                get { return pennants.Peek(); }
            }

            object IEnumerator.Current
            {
                get
                {
                    check_current();
                    return Current;
                }
            }

            public bool MoveNext()
            {
                check_version();

                Node next;
                if (pennants == null)
                {
                    if (tree.root == null)
                        return false;
                    if (init_pennants != null)
                    {
                        pennants = init_pennants;
                        init_pennants = null;
                        return pennants.Count != 0;
                    }
                    pennants = new Stack<Node>();
                    next = tree.root;
                }
                else
                {
                    if (pennants.Count == 0)
                        return false;
                    Node current = pennants.Pop();
                    next = current.right;
                }
                for (; next != null; next = next.left)
                    pennants.Push(next);

                return pennants.Count != 0;
            }

            public void Dispose()
            {
                tree = null;
                pennants = null;
            }

            void check_version()
            {
                if (tree == null)
                    throw new ObjectDisposedException("enumerator");
                if (version != tree.version)
                    throw new InvalidOperationException("tree modified");
            }

            internal void check_current()
            {
                check_version();
                if (pennants == null)
                    throw new InvalidOperationException("state invalid before the first MoveNext()");
            }
        }
    }
}

#if TEST
namespace Mono.ValidationTest {
	using System.Collections.Generic;

	internal class TreeSet<T> : IEnumerable<T>, IEnumerable
	{
		public class Node : RBTree.Node {
			public T value;

			public Node (T v)
			{
				value = v;
			}

			public override void SwapValue (RBTree.Node other)
			{
				Node o = (Node) other;
				T v = value;
				value = o.value;
				o.value = v;
			}

			public override void Dump (string indent)
			{
				Console.WriteLine ("{0}{1} {2}({3})", indent, value, IsBlack ? "*" : "", Size);
				if (left != null)
					left.Dump (indent + "  /");
				if (right != null)
					right.Dump (indent + "  \\");
			}
		}

		public class NodeHelper : RBTree.INodeHelper<T> {
			IComparer<T> cmp;

			public int Compare (T value, RBTree.Node node)
			{
				return cmp.Compare (value, ((Node) node).value);
			}

			public RBTree.Node CreateNode (T value)
			{
				return new Node (value);
			}

			private NodeHelper (IComparer<T> cmp)
			{
				this.cmp = cmp;
			}
			static NodeHelper Default = new NodeHelper (Comparer<T>.Default);
			public static NodeHelper GetHelper (IComparer<T> cmp)
			{
				if (cmp == null || cmp == Comparer<T>.Default)
					return Default;
				return new NodeHelper (cmp);
			}
		}

		public struct Enumerator : IDisposable, IEnumerator, IEnumerator<T> {
			RBTree.NodeEnumerator host;

			internal Enumerator (TreeSet<T> tree)
			{
				host = new RBTree.NodeEnumerator (tree.tree);
			}

			void IEnumerator.Reset ()
			{
				host.Reset ();
			}

			public T Current {
				get { return ((Node) host.Current).value; }
			}

			object IEnumerator.Current {
				get { return Current; }
			}

			public bool MoveNext ()
			{
				return host.MoveNext ();
			}

			public void Dispose ()
			{
				host.Dispose ();
			}
		}

		RBTree tree;

		public TreeSet () : this (null)
		{
		}

		public TreeSet (IComparer<T> cmp)
		{
			tree = new RBTree (NodeHelper.GetHelper (cmp));
		}

		IEnumerator IEnumerable.GetEnumerator ()
		{
			return GetEnumerator ();
		}

		IEnumerator<T> IEnumerable<T>.GetEnumerator ()
		{
			return GetEnumerator ();
		}

		public Enumerator GetEnumerator ()
		{
			return new Enumerator (this);
		}

		// returns true if the value was inserted, false if the value already existed in the tree
		public bool Insert (T value)
		{
			RBTree.Node n = new Node (value);
			return tree.Intern (value, n) == n;
		}

		// returns true if the value was removed, false if the value didn't exist in the tree
		public bool Remove (T value)
		{
			return tree.Remove (value) != null;
		}

		public bool Contains (T value)
		{
			return tree.Lookup (value) != null;
		}

		public T this [int index] {
			get { return ((Node) tree [index]).value; }
		}

		public int Count {
			get { return (int) tree.Count; }
		}

		public void VerifyInvariants ()
		{
			tree.VerifyInvariants ();
		}

		public void Dump ()
		{
			tree.Dump ();
		}
	}
	
	class Test {
		static void Main (string [] args)
		{
			Random r = new Random ();
			Dictionary<int, int> d = new Dictionary<int, int> ();
			TreeSet<int> t = new TreeSet<int> ();
			int iters = args.Length == 0 ? 100000 : Int32.Parse (args [0]);
			int watermark = 1;

			for (int i = 0; i < iters; ++i) {
				if (i >= watermark) {
					watermark += 1 + watermark/4;
					t.VerifyInvariants ();
				}

				int n = r.Next ();
				if (d.ContainsKey (n))
					continue;
				d [n] = n;

				try {
					if (t.Contains (n))
						throw new Exception ("tree says it has a number it shouldn't");
					if (!t.Insert (n))
						throw new Exception ("tree says it has a number it shouldn't");
				} catch {
					Console.Error.WriteLine ("Exception while inserting {0} in iteration {1}", n, i);
					throw;
				}
			}
			t.VerifyInvariants ();
			if (d.Count != t.Count)
				throw new Exception ("tree count is wrong?");

			Console.WriteLine ("Tree has {0} elements", t.Count);

			foreach (int n in d.Keys)
				if (!t.Contains (n))
					throw new Exception ("tree says it doesn't have a number it should");

			Dictionary<int, int> d1 = new Dictionary<int, int> (d);

			int prev = -1;
			foreach (int n in t) {
				if (n < prev)
					throw new Exception ("iteration out of order");
				if (!d1.Remove (n))
					throw new Exception ("tree has a number it shouldn't");
				prev = n;
			}

			if (d1.Count != 0)
				throw new Exception ("tree has numbers it shouldn't");

			for (int i = 0; i < iters; ++i) {
				int n = r.Next ();
				if (!d.ContainsKey (n)) {
					if (t.Contains (n))
						throw new Exception ("tree says it doesn't have a number it should");
				} else if (!t.Contains (n)) {
					throw new Exception ("tree says it has a number it shouldn't");
				}
			}

			int count = t.Count;
			foreach (int n in d.Keys) {
				if (count <= watermark) {
					watermark -= watermark/4;
					t.VerifyInvariants ();
				}
				try {
					if (!t.Remove (n))
						throw new Exception ("tree says it doesn't have a number it should");
					--count;
					if (t.Count != count)
						throw new Exception ("Remove didn't remove exactly one element");
				} catch {
					Console.Error.WriteLine ("While trying to remove {0} from tree of size {1}", n, t.Count);
					t.Dump ();
					t.VerifyInvariants ();
					throw;
				}
				if (t.Contains (n))
					throw new Exception ("tree says it has a number it shouldn't");
			}
			t.VerifyInvariants ();

			if (t.Count != 0)
				throw new Exception ("tree claims to have elements");
		}
	}
}
#endif

result

ms version time:34883
mono version time:407