minor java.util.TreeMap bug

[Archie Cobbs]

Timothy Stack writes:
> er...  NIL.parent points to the parent node, which points to its parent
> node, and so on.

OK, now I believe you :-) Thanks for the test.

Try the patch below (my debug version of kaffe just exits instead
of throwing OutOfMemoryError for some reason, so I can't run your
test).

After this patch, NIL.parent should always stay equal to null.
Does it look right to you?

-Archie

___________________________________________________________________________
Archie Cobbs   *   Whistle Communications, Inc.  *   http://www.whistle.com

--- kaffe/libraries/javalib/java/util/TreeMap.java	Mon Sep 25 11:33:46 2000
+++ java/util/TreeMap.java	Tue Sep 26 13:53:17 2000
@@ -13,6 +13,7 @@
  * Author: Archie L. Cobbs <archie at whistle.com>
  *
  * Based on an (unrestricted) C version by: Thomas Niemann <niemannt at home.com>
+ * most recently sited at: http://wannabe.guru.org/alg/node21.html
  */
 
 package java.util;
@@ -313,7 +314,7 @@
 			for (y = node.right; y.left != NIL; y = y.left);
 		}
 
-		// Set x to y's only child
+		// Set x to y's only child, or NIL if no children
 		if (y.left != NIL) {
 			x = y.left;
 		} else {
@@ -321,7 +322,8 @@
 		}
 
 		// Remove y from the parent chain
-		x.parent = y.parent;
+		if (x != NIL)
+			x.parent = y.parent;
 		if (y.parent != null) {
 			if (y == y.parent.left) {
 				y.parent.left = x;
@@ -337,7 +339,7 @@
 			node.value = y.value;
 		}
 
-		if (y.color == BLACK) {
+		if (y.color == BLACK && x != NIL) {
 			deleteFixup(x);
 		}
 	}