From 423313d6dee0542c63569172bcbd2465aa07008d Mon Sep 17 00:00:00 2001
From: brian <brian@brianweb.net>
Date: Tue, 15 Jun 2004 07:58:30 +0000
Subject: [PATCH] balanced tree fixes round 1

darcs-hash:20040615075830-24bed-0923a63a9bb10024f4d9778a9adc45f8bb0f7537.gz
---
 src/org/ibex/util/BalancedTree.java |  130 +++++++++++++++++++++++++++++------
 1 file changed, 108 insertions(+), 22 deletions(-)

diff --git a/src/org/ibex/util/BalancedTree.java b/src/org/ibex/util/BalancedTree.java
index 3e751fd..54e5a71 100644
--- a/src/org/ibex/util/BalancedTree.java
+++ b/src/org/ibex/util/BalancedTree.java
@@ -12,9 +12,11 @@ package org.ibex.util;
 // FEATURE: private void subset() { }
 // FEATURE: grow if we run out of slots
 
+// FEATURE: Add the cached_index stuff back in 
+
 /** a weight-balanced tree with fake leaves */
 public class BalancedTree {
-
+    private static final boolean DEBUG = true;
 
     // Instance Variables ///////////////////////////////////////////////////////////////////
 
@@ -50,6 +52,7 @@ public class BalancedTree {
             left[arg] = right[arg] = parent[arg] = 0;
             size[arg] = 1;
         }
+        if(DEBUG) check();
         }
     }
 
@@ -63,6 +66,7 @@ public class BalancedTree {
         if (index >= treeSize()) index = treeSize() - 1;
         int arg = allocateSlot(o);
         insert(index, arg, root, 0, true, false);
+        if(DEBUG) check();
         }
     }
 
@@ -126,6 +130,7 @@ public class BalancedTree {
         left[del] = right[del] = size[del] = parent[del] = 0;
         Object ret = objects[del];
         objects[del] = null;
+        if(DEBUG) check();
         return ret;
         }
     }
@@ -142,6 +147,7 @@ public class BalancedTree {
         } while(i != 0);
         root = 0;
         }
+        if(DEBUG) check();
     }
 
     // Node Data /////////////////////////////////////////////////////////////////////////
@@ -215,13 +221,35 @@ public class BalancedTree {
 
     // Helpers /////////////////////////////////////////////////////////////////////////
 
+    // FEATURE: These might be faster if they aren't recursive
     private final int leftmost(int slot) { return left[slot] <= 0 ? slot : leftmost(left[slot]); }
     private final int rightmost(int slot) { return right[slot] <= 0 ? slot : rightmost(right[slot]); }
-    private final int next(int slot) { return right[slot] <= 0 ? -1 * right[slot] : leftmost(right[slot]); }
-    private final int prev(int slot) { return left[slot] <= 0 ? -1 * left[slot] : rightmost(left[slot]); }
     private final int sizeof(int slot) { return slot <= 0 ? 0 : size[slot]; }
     private final int root(int slot) { return parent[slot] == 0 ? slot : root(parent[slot]); }
 
+    private int next(int node) {
+        if(right[node] > 0) {
+            node = right[node];
+            while(left[node] > 0) node = left[node];
+            return node;
+        } else {
+            int p = parent[node];
+            while(right[p] == node) { node = p; p = parent[node]; };
+            return p;
+        }
+    }
+    
+    private int prev(int node) {
+        if(left[node] > 0) {
+            node = left[node];
+            while(right[node] > 0) node = right[node];
+            return node;
+        } else {
+            int p = parent[node];
+            while(left[p] == node) { node = p; p = parent[node]; }
+            return p;
+        }
+    }
 
     // Rotation and Balancing /////////////////////////////////////////////////////////////
 
@@ -238,19 +266,23 @@ 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");
+        if (d == 0) throw new Error("rotation error");
+        if(DEBUG) check();
         left[d] = b;
-        right[b] = c <= 0 ? -d : c;
+        right[b] = c;
         
         parent[b] = d;
         parent[d] = p;
-        if(c > 0) parent[c] = b;
+        if(c != 0) parent[c] = b;
+        
         if (p == 0)              root = d;
         else if (left[p] == b)   left[p] = d;
         else if (right[p] == b)  right[p] = d;
         else throw new Error("rotate called with invalid parent");
         size[b] = 1 + sizeof(left[b]) + sizeof(right[b]);
         size[d] = 1 + sizeof(left[d]) + sizeof(right[d]);
+        
+        if(DEBUG) try { check(); } catch(Error e) { System.err.println("rotate: " + toTheLeft + "," + b + "," + p); throw e; }
     }
 
     private void balance(int slot, int p) {
@@ -265,8 +297,8 @@ public class BalancedTree {
     // Insert /////////////////////////////////////////////////////////////////////////
 
     private void insert(int index, int arg, int slot, int p, boolean replace, boolean wentLeft) {
-        int diff = slot <= 0 ? 0 : index - sizeof(left[slot]);
-        if (slot > 0 && diff != 0) {
+        int diff = slot == 0 ? 0 : index - sizeof(left[slot]);
+        if (slot != 0 && diff != 0) {
             if (diff < 0) insert(index, arg, left[slot], slot, replace, true);
             else insert(index - sizeof(left[slot]) - 1, arg, right[slot], slot, replace, false);
             balance(slot, p);
@@ -275,46 +307,56 @@ public class BalancedTree {
 
         if (size[arg] != 0) throw new Error("double insertion");
 
+        if(DEBUG) check();
+
         // we are replacing an existing node
         if (replace) {
             if (diff != 0) throw new Error("this should never happen"); // since we already clamped the index
             if (p == 0)                 root = arg;
             else if (left[p] == slot)   left[p] = arg;
             else if (right[p] == slot)  right[p] = arg;
+            else throw new Error("should never happen");
             left[arg] = left[slot];
             right[arg] = right[slot];
             size[arg] = size[slot];
             parent[arg] = parent[slot];
-            if(left[slot] > 0) parent[left[slot]] = arg;
-            if(right[slot] > 0) parent[right[slot]] = arg;
+            if(left[slot] != 0) parent[left[slot]] = arg;
+            if(right[slot] != 0) parent[right[slot]] = arg;
             objects[slot] = null;
             left[slot] = right[slot] = size[slot] = parent[slot] = 0;
-        
+            if(DEBUG) check();
+            
         // we become the child of a former leaf
-        } else if (slot <= 0) {
+        } else if (slot == 0) {
             int[] left = wentLeft ? BalancedTree.left : BalancedTree.right;
             int[] right = wentLeft ? BalancedTree.right : BalancedTree.left;
+            // FEATURE: Might be doing too much work here
             left[arg] = slot;
-            left[p] = arg;
-            right[arg] = -1 * p;
+            right[arg] = 0;
             parent[arg] = p;
+            left[p] = arg;
+            if(DEBUG) check();
             balance(arg, p);
 
         // we take the place of a preexisting node
         } else {
+            if(DEBUG) check();
             left[arg] = left[slot];   // steal slot's left subtree
-            left[slot] = -1 * arg;
+            left[slot] = 0;
             right[arg] = slot;        // make slot our right subtree
             parent[arg] = parent[slot];
             parent[slot] = arg;
+            if(left[arg] != 0) parent[left[arg]] = arg;
             if (slot == root) {
                 root = arg;
+                if(DEBUG) check();
                 balance(slot, arg);
                 balance(arg, 0);
             } else {
                 if (left[p] == slot)        left[p] = arg;
                 else if (right[p] == slot)  right[p] = arg;
                 else throw new Error("should never happen");
+                if(DEBUG) check();
                 balance(slot, arg);
                 balance(arg, p);
             }
@@ -350,7 +392,7 @@ public class BalancedTree {
         } else {
 
             // fast path: it has no children
-            if (left[slot] <= 0 && right[slot] <= 0) {
+            if (left[slot] == 0 && right[slot] == 0) {
                 if (p == 0) root = 0;
                 else {
                     int[] side = left[p] == slot ? left : right;
@@ -358,7 +400,7 @@ public class BalancedTree {
                 }
                 
             // fast path: it has no left child, so we replace it with its right child
-            } else if (left[slot] <= 0) {
+            } else if (left[slot] == 0) {
                 if (p == 0) root = right[slot];
                 else (left[p] == slot ? left : right)[p] = right[slot];     // fix parent's pointer
                 parent[right[slot]] = p;
@@ -366,7 +408,7 @@ public class BalancedTree {
                 balance(right[slot], p);
 
             // fast path; it has no right child, so we replace it with its left child
-            } else if (right[slot] <= 0) {
+            } else if (right[slot] == 0) {
                 if (p == 0) root = left[slot];
                 else (left[p] == slot ? left : right)[p] = left[slot];      // fix parent's pointer
                 parent[left[slot]] = p;
@@ -378,8 +420,8 @@ public class BalancedTree {
                 int left_childs_rightmost = delete(sizeof(left[slot]) - 1, left[slot], slot);
                 left[left_childs_rightmost] = left[slot];
                 right[left_childs_rightmost] = right[slot];
-                if(left[slot] > 0) parent[left[slot]] = left_childs_rightmost;
-                if(right[slot] > 0) parent[right[slot]] = left_childs_rightmost;
+                if(left[slot] != 0) parent[left[slot]] = left_childs_rightmost;
+                if(right[slot] != 0) parent[right[slot]] = left_childs_rightmost;
                 parent[left_childs_rightmost] = parent[slot];
                 if (p == 0) root = left_childs_rightmost;
                 else (left[p] == slot ? left : right)[p] = left_childs_rightmost;     // fix parent's pointer
@@ -398,14 +440,45 @@ public class BalancedTree {
 
     // Debugging ///////////////////////////////////////////////////////////////////////////
     
+    public void check() { check(false); }
+    public void check(boolean expensive) {
+        if(expensive) System.err.println("--> Running expensive balanced tree checks");
+        try {
+            if(expensive) 
+                for(int i=0;i<NUM_SLOTS;i++) 
+                    if(left[i] < 0 || right[i] < 0) throw new Error("someone inserted a negative number");
+            if(parent[root] != 0) throw new Error("parent of the root isn't 0");
+            if(left[0] != 0 || right[0] != 0 || size[0] != 0 || parent[0] != 0)
+                throw new Error("someone messed with [0]");
+            if(root != 0) check(root);
+        } catch(Error e) {
+            printTree();
+            throw e;
+        }
+    }
+    
+    private void check(int node) {
+        //if(next(node) != next2(node)) throw new Error("next(" + node + ") != next2(" + node + ")");
+        //if(prev(node) != prev2(node)) throw new Error("prev(" + node + ") != prev2(" + node + ")");
+        
+        if(left[node] > 0) {
+            if(parent[left[node]] != node) throw new Error("parent node mismatch on left child of " + node);
+            check(left[node]);
+        }
+        if(right[node] > 0) {
+            if(parent[right[node]] != node) throw new Error("parent node mismatch on right child of " + node);
+            check(right[node]);
+        }
+    }
+        
     public void printTree() {
         if(root == 0) System.err.println("Tree is empty");
         else printTree(root,0,false);
     }
+    
     private void printTree(int node,int indent,boolean l) {
         for(int i=0;i<indent;i++) System.err.print("   ");
-        if(node < 0) System.err.println((l?"Prev: " : "Next: ") + -node);
-        else if(node == 0)  System.err.println(l ? "Start" : "End");
+        if(node == 0) System.err.println("None");
         else {
             System.err.print("" + node + ": " + objects[node]);
             System.err.println(" Parent: " + parent[node]);
@@ -413,4 +486,17 @@ public class BalancedTree {
             printTree(right[node],indent+1,false);
         }
     }
+    
+    public static void main(String[] args) {
+        BalancedTree t = new BalancedTree();
+        for(int i=0;i<args.length;i++)
+            t.insertNode(i,args[i]);
+        t.printTree();
+        for(int n = t.leftmost(t.root); n != 0; n = t.next(n)) {
+            System.err.println("Next: " + n);
+        }
+        for(int n = t.rightmost(t.root); n != 0; n = t.prev(n)) {
+            System.err.println("Prev: " + n);
+        }        
+    }
 }
-- 
1.7.10.4