Author: raja
Date: 2007-05-02 03:39:08 -0400 (Wed, 02 May 2007)
New Revision: 76554
Modified:
trunk/mcs/class/System/System.Collections.Generic/ChangeLog
trunk/mcs/class/System/System.Collections.Generic/RBTree.cs
Log:
* RBTree.cs (do_remove): Remove some redundant assignments/checks.
(NodeEnumerator): Simplify. Keep track of a list of
right-pennants that need to be traversed next, rather than
comparing parent pointers.
The usual nit-picking followup
Modified: trunk/mcs/class/System/System.Collections.Generic/ChangeLog
===================================================================
--- trunk/mcs/class/System/System.Collections.Generic/ChangeLog 2007-05-02
01:20:52 UTC (rev 76553)
+++ trunk/mcs/class/System/System.Collections.Generic/ChangeLog 2007-05-02
07:39:08 UTC (rev 76554)
@@ -1,3 +1,10 @@
+2007-05-02 Raja R Harinath <[EMAIL PROTECTED]>
+
+ * RBTree.cs (do_remove): Remove some redundant assignments/checks.
+ (NodeEnumerator): Simplify. Keep track of a list of
+ right-pennants that need to be traversed next, rather than
+ comparing parent pointers.
+
2007-05-02 Raja R Harinath <[EMAIL PROTECTED]>
Make add and remove operations O(log n).
Modified: trunk/mcs/class/System/System.Collections.Generic/RBTree.cs
===================================================================
--- trunk/mcs/class/System/System.Collections.Generic/RBTree.cs 2007-05-02
01:20:52 UTC (rev 76553)
+++ trunk/mcs/class/System/System.Collections.Generic/RBTree.cs 2007-05-02
07:39:08 UTC (rev 76554)
@@ -321,26 +321,23 @@
{
int curpos = path.Count - 1;
- Node n1 = path [curpos];
- Node n2 = null;
- Node n3 = null;
-
- if (n1.left != null) {
- n2 = right_most (n1.left, n1.right, path);
- n3 = n2.left == null ? null : right_most
(n2.left, null, path);
- } else if (n1.right != null) {
- n2 = left_most (n1.right, n1.left, path);
- n3 = n2.right == null ? null : left_most
(n2.right, null, path);
+ 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);
}
- if (n2 != null) {
- n1.SwapValue (n2);
- if (n3 != null)
- n2.SwapValue (n3);
- }
-
curpos = path.Count - 1;
- Node current = path [curpos];
+ current = path [curpos];
if (current.Size != 1)
throw new SystemException ("Internal Error:
red-black violation somewhere");
@@ -554,19 +551,6 @@
}
// 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 (;;) {
@@ -583,30 +567,26 @@
RBTree tree;
uint version;
- List<Node> path;
- Node current;
+ Stack<Node> pennants;
internal NodeEnumerator (RBTree tree)
{
this.tree = tree;
version = tree.version;
- current = null;
- path = null;
+ pennants = null;
}
public void Reset ()
{
- check_version ();
- current = null;
- path = null;
+ if (tree == null)
+ throw new ObjectDisposedException
("enumerator");
+ pennants = null;
}
public Node Current {
get {
check_version ();
- if (current == null)
- throw new
InvalidOperationException ();
- return current;
+ return pennants.Peek ();
}
}
@@ -618,50 +598,34 @@
{
check_version ();
- if (current == null) {
- if (tree.root == null || path != null)
+ Node next;
+ if (pennants == null) {
+ if (tree.root == null)
return false;
-
- path = new List<Node> ();
-
- // sentinel: "parent" of root is null
- path.Add (null);
- current = left_most (tree.root, null,
path);
- return true;
+ 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);
- 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;
- while ((parent = path [parpos]) != null) {
- if (current == parent.left)
- break;
- current = parent;
- parpos -= 2;
- }
-
- path.RemoveRange (parpos + 1, path.Count -
parpos - 1);
- current = parent;
-
- return current != null;
+ return pennants.Count != 0;
}
public void Dispose ()
{
- current = null;
- path = null;
tree = null;
+ pennants = null;
}
void check_version ()
{
if (tree == null)
- throw new ObjectDisposedException
("tree");
+ throw new ObjectDisposedException
("enumerator");
if (version != tree.version)
throw new InvalidOperationException
("tree modified");
}
@@ -856,9 +820,14 @@
Dictionary<int, int> d1 = new Dictionary<int, int> (d);
- foreach (int n in t)
+ 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");
_______________________________________________
Mono-patches maillist - [email protected]
http://lists.ximian.com/mailman/listinfo/mono-patches
