2003/11/30 02:15: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 9e5aaec..0aebcde 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 */
@@ -57,7 +60,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 */
@@ -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)];
     }
 
@@ -173,22 +180,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]);
     }
 
 
@@ -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);
@@ -259,11 +278,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