2003/11/29 05:19:29

darcs-hash:20040130074222-2ba56-43e8bf590b5cfabc83571587b1d61e380a8f54a0.gz

diff --git a/src/org/xwt/util/BalancedTree.java b/src/org/xwt/util/BalancedTree.java
index 9e5aaec..dadf42b 100644 (file)
--- a/src/org/xwt/util/BalancedTree.java
+++ b/src/org/xwt/util/BalancedTree.java
@@ -57,7 +57,7 @@ public class BalancedTree {
         if (parent == 0) return size(left[slot]);             // we are on the far left edge
 
         // all nodes after parent and before us are in our left subtree
-        else return size(left[slot]) + indexNode(objects[parent]) + 1;
+        return size(left[slot]) + indexNode(objects[parent]) + 1;
     }
 
     /** returns the object at index; runs in O(log n) time unless cache hit */
@@ -173,22 +173,22 @@ public class BalancedTree {
         int[] right = toTheLeft ? BalancedTree.right : BalancedTree.left;
         int d = right[b];
         int c = left[d];
+        if (d <= 0) throw new Error("rotation error");
         left[d] = b;
         right[b] = c;
         if (parent == 0)              root = d;
         else if (left[parent] == b)   left[parent] = d;
         else if (right[parent] == b)  right[parent] = d;
         else throw new Error("rotate called with invalid parent");
-        size[b] = 1 + size(left[b]) + size(right[b]);
         balance(b, d);
-        size[d] = 1 + size(left[d]) + size(right[d]);
         balance(d, parent);
     }
 
     private void balance(int slot, int parent) {
+        if (slot <= 0) return;
+        size[slot] = 1 + size(left[slot]) + size(right[slot]);
         if (size(left[slot]) - 1 > 2 * size(right[slot])) rotate(false, slot, parent);
         else if (size(left[slot]) * 2 < size(right[slot]) - 1) rotate(true, slot, parent);
-        size[slot] = 1 + size(left[slot]) + size(right[slot]);
     }
 
 
@@ -259,11 +259,19 @@ public class BalancedTree {
         // we found the node to delete
         } else {
 
+            // fast path: it has no children
+            if (left[slot] <= 0 && right[slot] <= 0) {
+                if (parent == 0) root = 0;
+                else {
+                    int[] side = left[parent] == slot ? left : right;
+                    side[parent] = side[slot];      // fix parent's pointer
+                }
+                
             // fast path: it has no left child, so we replace it with its right child
-            if (left[slot] <= 0) {
+            } else 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
+                if (right[slot] > 0) left[leftmost(right[slot])] = left[slot];        // fix our successor-leaf's fake right ptr
                 balance(right[slot], parent);
 
             // fast path; it has no right child, so we replace it with its left child