2003/11/27 22:42:43

[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 3f78424..0ef3b38 100644 (file)
--- a/src/org/xwt/util/BalancedTree.java
+++ b/src/org/xwt/util/BalancedTree.java
@@ -15,6 +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;
 
     // Public API //////////////////////////////////////////////////////////////////////////
 
@@ -23,6 +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;
         if (index < 0) index = 0;
         if (index > treeSize()) index = treeSize();
         int arg = allocateSlot(o);
@@ -35,6 +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;
         if (index < 0) index = 0;
         if (index > treeSize()) index = treeSize() - 1;
         int arg = allocateSlot(o);
@@ -44,8 +48,10 @@ public class BalancedTree {
         right[arg] = 0;
     }
 
-    /** returns the index of o; runs in O((log n)^2) time */
+    /** 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;
+
         int slot = getSlot(o, o.hashCode() ^ this.hashCode());
         int parent = -1 * left[leftmost(slot)];
         if (parent == 0) return size(left[slot]);             // we are on the far left edge
@@ -54,13 +60,27 @@ public class BalancedTree {
         else return size(left[slot]) + indexNode(objects[parent]) + 1;
     }
 
-    /** returns the object at index; runs in O(log n) time */
+    /** returns the object at index; runs in O(log n) time unless cache hit */
     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];
+        }
+
         return objects[get(index, root)];
     }
 
     /** deletes the object at index, returning the deleted object */
     public final Object deleteNode(int index) {
+        cached_slot = cached_index = 0;
         return delete(index, root, 0);
     }