2003/11/29 04:52:58

[org.ibex.core.git] / src / org / xwt / util / BalancedTree.java

diff --git a/src/org/xwt/util/BalancedTree.java b/src/org/xwt/util/BalancedTree.java
index b27eab3..9e5aaec 100644 (file)
--- a/src/org/xwt/util/BalancedTree.java
+++ b/src/org/xwt/util/BalancedTree.java
@@ -103,9 +103,20 @@ public class BalancedTree {
      * object will have multiple slots.
      */
     private static Object[] objects = new Object[NUM_SLOTS];
-    private static int[] left = new int[NUM_SLOTS];      ///< if positive: left child's slot; if negative: predecessor's slot
-    private static int[] right = new int[NUM_SLOTS];     ///< if positive: right child's slot; if negative: successor's slot
-    private static int[] size = new int[NUM_SLOTS];      ///< the number of descendants of this node *including the node itself*
+
+    /// These two arrays hold the left and right children of each
+    /// slot; in other words, left[x] is the *slot* of the left child
+    /// of the node in slot x.
+    ///
+    /// If x has no left child, then left[x] is -1 multiplied by the
+    /// slot of the node that precedes x; if x is the first node, then
+    /// left[x] is 0.  The right[] array works the same way.
+    ///
+    private static int[] left = new int[NUM_SLOTS];
+    private static int[] right = new int[NUM_SLOTS];
+
+    ///< the number of descendants of this node *including the node itself*
+    private static int[] size = new int[NUM_SLOTS];
 
 
     // Slot Management //////////////////////////////////////////////////////////////////////
@@ -249,14 +260,14 @@ public class BalancedTree {
         } else {
 
             // fast path: it has no left child, so we replace it with its right child
-            if (left[slot] < 0) {
+            if (left[slot] <= 0) {
                 if (parent == 0) root = right[slot];
                 else (left[parent] == slot ? left : right)[parent] = right[slot];     // fix parent's pointer
                 if (right[slot] > 0) left[leftmost(right[slot])] = left[slot];        // fix our successor-leaf's fake left ptr
                 balance(right[slot], parent);
 
             // fast path; it has no right child, so we replace it with its left child
-            } else if (right[slot] < 0) {
+            } else if (right[slot] <= 0) {
                 if (parent == 0) root = left[slot];
                 else (left[parent] == slot ? left : right)[parent] = left[slot];      // fix parent's pointer
                 if (left[slot] > 0) right[rightmost(left[slot])] = right[slot];       // fix our successor-leaf's fake right ptr