2003/12/06 06:01:40

[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 dadf42b..52ac71b 100644 (file)
--- a/src/org/xwt/util/BalancedTree.java
+++ b/src/org/xwt/util/BalancedTree.java
@@ -29,11 +29,14 @@ public class BalancedTree {
         if (index < 0) index = 0;
         if (index > treeSize()) index = treeSize();
         int arg = allocateSlot(o);
-        if (root != 0) { insert(index, arg, root, 0, false, false); return; }
-        root = arg;
-        left[arg] = 0;
-        right[arg] = 0;
-        size[root] = 1;
+        if (root != 0) {
+            insert(index, arg, root, 0, false, false);
+        } else {
+            root = arg;
+            left[arg] = 0;
+            right[arg] = 0;
+            size[root] = 1;
+        }
     }
 
     /** clamps index to [0..treeSize()-1] and replaces the object at that index with object o */
@@ -75,7 +78,11 @@ public class BalancedTree {
                 return objects[cached_slot];
             }
         }
-
+        /*
+        cached_index = index;
+        cached_slot = get(index, root);
+        return objects[cached_slot];
+        */
         return objects[get(index, root)];
     }
 
@@ -180,8 +187,8 @@ public class BalancedTree {
         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");
-        balance(b, d);
-        balance(d, parent);
+        size[b] = 1 + size(left[b]) + size(right[b]);
+        size[d] = 1 + size(left[d]) + size(right[d]);
     }
 
     private void balance(int slot, int parent) {
@@ -206,6 +213,17 @@ public class BalancedTree {
 
         if (size[arg] != 0) throw new Error("double insertion");
 
+        if (replace) {
+            if (diff == 0) {
+                objects[slot] = objects[arg];
+                objects[arg] = null;
+                left[arg] = right[arg] = size[arg] = 0;
+            } else {
+                // since we already clamped the index
+                throw new Error("this should never happen");
+            }
+        }
+
         // we become the child of a former leaf
         if (slot <= 0) {
             int[] left = wentLeft ? BalancedTree.left : BalancedTree.right;
@@ -223,6 +241,7 @@ public class BalancedTree {
             if (slot == root) {
                 root = arg;
                 balance(slot, arg);
+                balance(arg, 0);
             } else {
                 (left[parent] == slot ? left : right)[parent] = arg;
                 balance(slot, arg);