2003/11/27 05:10:32

[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 99ec34f..3f78424 100644 (file)
--- a/src/org/xwt/util/BalancedTree.java
+++ b/src/org/xwt/util/BalancedTree.java
@@ -5,6 +5,7 @@ package org.xwt.util;
 // FEATURE: private void union() { }
 // FEATURE: private void subset() { }
 // FEATURE: grow if we run out of slots
+// FEATURE: finalizer
 
 /** a weight-balanced tree with fake leaves */
 public class BalancedTree {
@@ -130,6 +131,7 @@ public class BalancedTree {
     //    a   d    < == >    b   e
     //       / \            / \
     //      c   e          a   c
+    // FIXME might be doing too much work here
     private void rotate(boolean toTheLeft, int b, int parent) {
         int[] left = toTheLeft ? BalancedTree.left : BalancedTree.right;
         int[] right = toTheLeft ? BalancedTree.right : BalancedTree.left;
@@ -137,19 +139,19 @@ public class BalancedTree {
         int c = left[d];
         left[d] = b;
         right[b] = c;
-        size[b] = size(left[b]) + size(c);
-        size[d] = size[b] + size(right[d]);
         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 (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]);
     }
 
@@ -182,10 +184,14 @@ public class BalancedTree {
             left[arg] = left[slot];   // steal slot's left subtree
             left[slot] = -1 * arg;
             right[arg] = slot;        // make slot our right subtree
-            if (slot == root) root = arg;
-            (left[parent] == slot ? left : right)[parent] = arg;
-            balance(slot, arg);
-            balance(arg, parent);
+            if (slot == root) {
+                root = arg;
+                balance(slot, arg);
+            } else {
+                (left[parent] == slot ? left : right)[parent] = arg;
+                balance(slot, arg);
+                balance(arg, parent);
+            }
         }
     }