Author: raja
Date: 2007-04-29 15:15:54 -0400 (Sun, 29 Apr 2007)
New Revision: 76469
Added:
trunk/mcs/class/System/System.Collections.Generic/RBTree.cs
Modified:
trunk/mcs/class/System/System.Collections.Generic/ChangeLog
Log:
* RBTree.cs: New red-black tree implementation for use with SortedDictionary.
I'll integrate it into SortedDictionary tomorrow, if no one else gets to it.
Modified: trunk/mcs/class/System/System.Collections.Generic/ChangeLog
===================================================================
--- trunk/mcs/class/System/System.Collections.Generic/ChangeLog 2007-04-29
18:32:42 UTC (rev 76468)
+++ trunk/mcs/class/System/System.Collections.Generic/ChangeLog 2007-04-29
19:15:54 UTC (rev 76469)
@@ -1,3 +1,8 @@
+2007-04-30 Raja R Harinath <[EMAIL PROTECTED]>
+
+ * RBTree.cs: New red-black tree implementation for use with
+ SortedDictionary.
+
2007-04-19 Gert Driesen <[EMAIL PROTECTED]>
* Queue.cs: Fixed binary serialization, based on patch provided by
Added: trunk/mcs/class/System/System.Collections.Generic/RBTree.cs
===================================================================
--- trunk/mcs/class/System/System.Collections.Generic/RBTree.cs 2007-04-29
18:32:42 UTC (rev 76468)
+++ trunk/mcs/class/System/System.Collections.Generic/RBTree.cs 2007-04-29
19:15:54 UTC (rev 76469)
@@ -0,0 +1,747 @@
+//
+// System.Collections.Generic.RBTree
+//
+// Authors:
+// Raja R Harinath <[EMAIL PROTECTED]>
+//
+
+//
+// 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
+
+#if NET_2_0
+using System;
+using System.Collections;
+
+namespace System.Collections.Generic
+{
+ internal class RBTree<T> {
+ public class Node {
+ public Node left, right;
+ public T value;
+ 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 (T v)
+ {
+ value = v;
+ size_black = 2; // Size == 1, IsBlack = false
+ }
+
+#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 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 + " \\");
+ }
+#endif
+ }
+
+ Node root;
+ IComparer<T> cmp;
+ uint version;
+
+#if ONE_MEMBER_CACHE
+ [ThreadStatic]
+ static List<Node> cached_path;
+
+ static List<Node> alloc_path ()
+ {
+ if (cached_path == null)
+ return new List<Node> ();
+
+ List<Node> retval = cached_path;
+ cached_path = null;
+ retval.Clear ();
+ return retval;
+ }
+
+ static void release_path (List<Node> path)
+ {
+ cached_path = path;
+ }
+#else
+ static List<Node> alloc_path ()
+ {
+ return new List<Node> ();
+ }
+
+ static void release_path (List<Node> path)
+ {
+ }
+#endif
+
+ public RBTree () : this (Comparer<T>.Default)
+ {
+ }
+
+ public RBTree (IComparer<T> cmp)
+ {
+ this.cmp = cmp;
+ }
+
+ int Find (T value, List<Node> path)
+ {
+ if (root == null)
+ throw new SystemException ("Internal Error: no
tree");
+
+ int c = 0;
+ Node sibling = null;
+ Node current = root;
+
+ if (path != null)
+ path.Add (root);
+
+ while (current != null) {
+ c = cmp.Compare (value, current.value);
+ 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;
+ }
+
+ public void Insert (T value)
+ {
+ if (root == null) {
+ root = new Node (value);
+ root.IsBlack = true;
+ ++version;
+ return;
+ }
+
+ List<Node> path = alloc_path ();
+ int in_tree_cmp = Find (value, path);
+ if (in_tree_cmp == 0)
+ throw new ArgumentException ("value already in
the tree");
+
+ Node parent = path [path.Count - 3];
+ Node current = path [path.Count - 1] = new Node (value);
+
+ 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 (current, path);
+
+ // no need for a try .. finally, this is only used to
mitigate allocations/gc
+ release_path (path);
+
+ if (!root.IsBlack)
+ throw new SystemException ("Internal error:
root is not black");
+ ++version;
+ }
+
+ public Node Remove (T value)
+ {
+ if (root == null)
+ return null;
+
+ List<Node> path = alloc_path ();
+ int in_tree_cmp = Find (value, path);
+ if (in_tree_cmp != 0) {
+ release_path (path);
+ return null;
+ }
+
+ int curpos = path.Count - 1;
+ Node current = path [curpos];
+ T old_value = current.value;
+ bool changed = false;
+ for (; current.Size != 1; current = path [curpos]) {
+ Node next = current.left == null
+ ? left_most (current.right, null, path)
+ : right_most (current.left,
current.right, path);
+ current.value = next.value;
+ changed = true;
+ curpos = path.Count - 1;
+ if (next != path [curpos])
+ throw new SystemException ("Internal
error: path wrong");
+
+ }
+ if (changed)
+ current.value = old_value;
+
+ // 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)
+ rebalance_delete (path);
+
+ // no need for a try .. finally, this is only used to
mitigate allocations/gc
+ release_path (path);
+
+ if (root != null && !root.IsBlack)
+ throw new SystemException ("Internal Error:
root is not black");
+
+ ++version;
+ return current;
+ }
+
+ public bool Contains (T value)
+ {
+ return root != null && Find (value, null) == 0;
+ }
+
+ 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.Size > 1) {
+ 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;
+ }
+ }
+
+ if (index != 0)
+ throw new SystemException ("Internal
Error: index calculation");
+ return current;
+ }
+ }
+
+ public Enumerator GetEnumerator ()
+ {
+ return new Enumerator (this);
+ }
+
+ public NodeEnumerator GetNodeEnumerator ()
+ {
+ return new NodeEnumerator (this);
+ }
+
+#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
+
+ void rebalance_insert (Node current, List<Node> path)
+ {
+ for (int parpos = path.Count - 3; !path
[parpos].IsBlack; parpos -= 4) {
+ // uncle == parpos - 1, grandpa == parpos - 2,
great-grandpa = parpos - 4
+ if (path [parpos-1] == null || path
[parpos-1].IsBlack) {
+ rebalance_insert__rotate_final
(current, parpos, path);
+ return;
+ }
+
+ path [parpos].IsBlack = path [parpos-1].IsBlack
= true;
+
+ // move to the grandpa
+ current = path [parpos-2];
+ if (current == root) // => parpos == 2
+ return;
+
+ current.IsBlack = false;
+ }
+
+ }
+
+ void rebalance_delete (List<Node> path)
+ {
+ path.Add (null); path.Add (null); // accomodate a
rotation
+
+ for (int curpos = path.Count - 3; curpos > 0; curpos -=
2) {
+ Node current = path [curpos];
+ if (current != null && !current.IsBlack) {
+ current.IsBlack = true;
+ return;
+ }
+
+
+ Node sibling = path [curpos-1];
+
+ // current is black => sibling != null
+ if (!path [curpos-1].IsBlack) {
+ // current is black && sibling is red
+ // => both sibling.left and
sibling.right are not null and are black
+ curpos = ensure_sibling_black (curpos,
path);
+ 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;
+ }
+ }
+
+ void rebalance_insert__rotate_final (Node current, int parpos,
List<Node> path)
+ {
+ Node parent = path [parpos];
+ Node grandpa = path [parpos-2];
+
+ 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 (parpos == 2 ? null : path [parpos-4],
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);
+
+ 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 left_most (Node current, Node sibling, List<Node>
path)
+ {
+ for (;;) {
+ path.Add (sibling);
+ path.Add (current);
+ if (current.left == null)
+ return current;
+ sibling = current.right;
+ current = current.left;
+ }
+ }
+
+ // 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;
+ }
+ }
+
+ public struct Enumerator : IDisposable, IEnumerator,
IEnumerator<T> {
+ NodeEnumerator host;
+
+ internal Enumerator (RBTree<T> tree)
+ {
+ host = new NodeEnumerator (tree);
+ }
+
+ void IEnumerator.Reset ()
+ {
+ ((IEnumerator) host).Reset ();
+ }
+
+ public T Current {
+ get { return host.Current.value; }
+ }
+
+ object IEnumerator.Current {
+ get { return Current; }
+ }
+
+ public bool MoveNext ()
+ {
+ return host.MoveNext ();
+ }
+
+ public void Dispose ()
+ {
+ host.Dispose ();
+ }
+ }
+
+ public struct NodeEnumerator : IEnumerator, IEnumerator<Node> {
+ RBTree<T> tree;
+ uint version;
+
+ List<Node> path;
+ Node current;
+
+ internal NodeEnumerator (RBTree<T> tree)
+ {
+ this.tree = tree;
+ version = tree.version;
+ current = null;
+ path = null;
+ }
+
+ void IEnumerator.Reset ()
+ {
+ check_version ();
+ current = null;
+ path = null;
+ }
+
+ public Node Current {
+ get {
+ check_version ();
+ if (current == null)
+ throw new
InvalidOperationException ();
+ return current;
+ }
+ }
+
+ object IEnumerator.Current {
+ get { return Current; }
+ }
+
+ public bool MoveNext ()
+ {
+ check_version ();
+
+ if (current == null) {
+ if (tree.root == null || path != null)
+ return false;
+
+ path = new List<Node> ();
+ current = left_most (tree.root, null,
path);
+ return true;
+ }
+
+ if (current.right != null) {
+ // since we've already traversed
current.left, don't bother saving it in path
+ current = left_most (current.right,
null, path);
+ return true;
+ }
+
+ int parpos = path.Count - 3;
+ Node parent;
+ for (;;) {
+ parent = parpos < 0 ? null : path
[parpos];
+ if (parent == null)
+ break;
+ if (current == parent.left)
+ break;
+ current = parent;
+ parpos -= 2;
+ }
+
+ path.RemoveRange (parpos + 1, path.Count -
parpos - 1);
+ current = parent;
+
+ return current != null;
+ }
+
+ public void Dispose ()
+ {
+ current = null;
+ path = null;
+ tree = null;
+ }
+
+ void check_version ()
+ {
+ if (tree == null)
+ throw new ObjectDisposedException
("tree");
+ if (version != tree.version)
+ throw new InvalidOperationException
("tree modified");
+ }
+ }
+ }
+}
+
+#if TEST
+namespace Mono.ValidationTest {
+ using System.Collections.Generic;
+
+ class Test {
+ static void Main (string [] args)
+ {
+ Random r = new Random ();
+ Dictionary<int, int> d = new Dictionary<int, int> ();
+ RBTree<int> t = new RBTree<int> ();
+ int iters = args.Length == 0 ? 100000 : Int32.Parse
(args [0]);
+
+ for (int i = 0; i < iters; ++i) {
+ if ((i % 100) == 0)
+ t.VerifyInvariants ();
+
+ int n = r.Next ();
+ if (d.ContainsKey (n))
+ continue;
+ d [n] = n;
+
+ if (t.Contains (n))
+ throw new Exception ("tree says it has
a number it shouldn't");
+
+ try {
+ t.Insert (n);
+ } 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");
+
+ foreach (int n in t)
+ if (!d.ContainsKey (n))
+ throw new Exception ("tree has a number
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 j = 0;
+ foreach (int n in d.Keys) {
+ if ((j++ % 100) == 0)
+ t.VerifyInvariants ();
+ try {
+ if (t.Remove (n) == null)
+ throw new Exception ("tree says
it doesn't have a number it should");
+
+ } 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
+
+#endif
Property changes on: trunk/mcs/class/System/System.Collections.Generic/RBTree.cs
___________________________________________________________________
Name: svn:mime-type
+ text/cpp
Name: svn:eol-style
+ native
_______________________________________________
Mono-patches maillist - [email protected]
http://lists.ximian.com/mailman/listinfo/mono-patches