2003/11/28 03:06:56

[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 0ef3b38..5020547 100644 (file)
--- a/src/org/xwt/util/BalancedTree.java
+++ b/src/org/xwt/util/BalancedTree.java
@@ -80,14 +80,19 @@ public class BalancedTree {
 
     /** deletes the object at index, returning the deleted object */
     public final Object deleteNode(int index) {
+        // FIXME handle root deletion here
         cached_slot = cached_index = 0;
-        return delete(index, root, 0);
+        int del = delete(index, root, 0);
+        left[del] = right[del] = size[del] = 0;
+        Object ret = objects[del];
+        objects[del] = null;
+        return ret;
     }
 
 
     // Node Data /////////////////////////////////////////////////////////////////////////
 
-    private final static int NUM_SLOTS = 265 * 1024;
+    private final static int NUM_SLOTS = 64 * 1024;
 
     /**
      * Every object inserted into *any* tree gets a "slot" in this
@@ -228,46 +233,43 @@ public class BalancedTree {
 
     // Deletion //////////////////////////////////////////////////////////////////////
 
-    private Object delete(int index, int slot, int parent) {
+    private int delete(int index, int slot, int parent) {
         int diff = index - size(left[slot]);
         if (diff < 0) {
-            Object ret = delete(index, left[slot], slot);
+            int ret = delete(index, left[slot], slot);
             balance(slot, parent);
             return ret;
 
         } else if (diff > 0) {
-            Object ret = delete(diff - 1, right[slot], slot);
+            int ret = delete(diff - 1, right[slot], slot);
             balance(slot, parent);
             return ret;
 
+        // we found the node to delete
         } else {
-            if (left[slot] == 0) {
-                if (parent == 0) root = right[slot];
-                else (left[parent] == slot ? left : right)[parent] = right[slot];
-                right[slot] = 0;
-                balance(slot, parent);
-            } else if (right[slot] == 0) {
-                if (parent == 0) root = left[slot];
-                else (left[parent] == slot ? left : right)[parent] = left[slot];
-                left[slot] = 0;
-                balance(slot, parent);
+
+            // fast path: it has no left child, so we replace it with its right child
+            if (left[slot] < 0) {
+                (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) {
+                (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
+                balance(left[slot], parent);
+
+            // node to be deleted has two children, so we replace it with its left child's rightmost descendant
             } else {
-                Object replacement_object = delete(index - 1, slot, parent);
-                int replacement = allocateSlot(replacement_object);
-                if (replacement != 0) {
-                    left[replacement] = left[slot];
-                    right[replacement] = right[slot];
-                }
-                if (parent == 0) root = replacement;
-                else (left[parent] == slot ? left : right)[parent] = replacement;
-                left[slot] = 0;
-                right[slot] = 0;
-                balance(replacement, parent);
+                int left_childs_rightmost = delete(size(left[slot]) - 1, left[slot], slot);
+                left[left_childs_rightmost] = left[slot];
+                left[left_childs_rightmost] = right[slot];
+                (left[parent] == slot ? left : right)[parent] = left_childs_rightmost;     // fix parent's pointer
+                balance(left_childs_rightmost, parent);
             }
-            Object ret = objects[slot];
-            size[slot] = 0;
-            objects[slot] = null;
-            return ret;
+
+            return slot;
         }
     }