From c124fdde2dd49e31125da6885aa75f79464452f0 Mon Sep 17 00:00:00 2001
From: megacz <megacz@xwt.org>
Date: Fri, 30 Jan 2004 07:42:15 +0000
Subject: [PATCH] 2003/11/28 03:16:06

darcs-hash:20040130074215-2ba56-4bf8b9d46737986a444e8baa53de777a28857dd3.gz
---
 src/org/xwt/util/BalancedTree.java |   41 +++++++++++++++++++-----------------
 1 file changed, 22 insertions(+), 19 deletions(-)

diff --git a/src/org/xwt/util/BalancedTree.java b/src/org/xwt/util/BalancedTree.java
index 5020547..b27eab3 100644
--- a/src/org/xwt/util/BalancedTree.java
+++ b/src/org/xwt/util/BalancedTree.java
@@ -15,8 +15,8 @@ public class BalancedTree {
 
     private int root = 0;                         ///< the slot of the root element
 
-    private int cached_index = 0;
-    private int cached_slot = 0;
+    private int cached_index = -1;
+    private int cached_slot = -1;
 
     // Public API //////////////////////////////////////////////////////////////////////////
 
@@ -25,7 +25,7 @@ public class BalancedTree {
 
     /** clamps index to [0..treeSize()] and inserts object o *before* the specified index */
     public final void insertNode(int index, Object o) {
-        cached_slot = cached_index = 0;
+        cached_slot = cached_index = -1;
         if (index < 0) index = 0;
         if (index > treeSize()) index = treeSize();
         int arg = allocateSlot(o);
@@ -38,7 +38,7 @@ public class BalancedTree {
 
     /** clamps index to [0..treeSize()-1] and replaces the object at that index with object o */
     public final void replaceNode(int index, Object o) {
-        cached_slot = cached_index = 0;
+        cached_slot = cached_index = -1;
         if (index < 0) index = 0;
         if (index > treeSize()) index = treeSize() - 1;
         int arg = allocateSlot(o);
@@ -50,7 +50,7 @@ public class BalancedTree {
 
     /** returns the index of o; runs in O((log n)^2) time unless cache hit */
     public final int indexNode(Object o) { 
-        if (objects[cached_slot] == o) return cached_index;
+        if (cached_slot != -1 && objects[cached_slot] == o) return cached_index;
 
         int slot = getSlot(o, o.hashCode() ^ this.hashCode());
         int parent = -1 * left[leftmost(slot)];
@@ -64,15 +64,16 @@ public class BalancedTree {
     public final Object getNode(int index) {
         if (index == cached_index) return objects[cached_slot];
 
-        int distance = Math.abs(index - cached_index);
-
-        // if the in-order distance between the cached node and the
-        // target node is less than log(n), it's probably faster to
-        // search directly.
-        if (cached_index != 0 && (distance < 16) && ((2 << distance) < treeSize())) {
-            while(cached_index > index) { cached_slot = prev(cached_slot); cached_index--; }
-            while(cached_index < index) { cached_slot = next(cached_slot); cached_index++; }
-            return objects[cached_slot];
+        if (cached_index != -1) {
+            int distance = Math.abs(index - cached_index);
+            // if the in-order distance between the cached node and the
+            // target node is less than log(n), it's probably faster to
+            // search directly.
+            if ((distance < 16) && ((2 << distance) < treeSize())) {
+                while(cached_index > index) { cached_slot = prev(cached_slot); cached_index--; }
+                while(cached_index < index) { cached_slot = next(cached_slot); cached_index++; }
+                return objects[cached_slot];
+            }
         }
 
         return objects[get(index, root)];
@@ -80,8 +81,7 @@ 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;
+        cached_slot = cached_index = -1;
         int del = delete(index, root, 0);
         left[del] = right[del] = size[del] = 0;
         Object ret = objects[del];
@@ -250,13 +250,15 @@ public class BalancedTree {
 
             // 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 (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
                 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 (parent == 0) root = left[slot];
+                else (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);
 
@@ -265,7 +267,8 @@ public class BalancedTree {
                 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
+                if (parent == 0) root = left_childs_rightmost;
+                else (left[parent] == slot ? left : right)[parent] = left_childs_rightmost;     // fix parent's pointer
                 balance(left_childs_rightmost, parent);
             }
 
-- 
1.7.10.4