X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=src%2Forg%2Fibex%2Futil%2FBalancedTree.java;h=dd993a0dc5e8984003da3e256b66c6c45a36c145;hb=3f8aa5300e178e8975b0edc896a5a9d303e7bdf3;hp=be8be46f04e9d7199bc0410c94614cd6dd62c8a1;hpb=9f6088ca9ac462999a202ab33ac45656c3c9bd3c;p=org.ibex.core.git

diff --git a/src/org/ibex/util/BalancedTree.java b/src/org/ibex/util/BalancedTree.java
index be8be46..dd993a0 100644
--- a/src/org/ibex/util/BalancedTree.java
+++ b/src/org/ibex/util/BalancedTree.java
@@ -16,8 +16,6 @@ package org.ibex.util;
 
 /** a weight-balanced tree with fake leaves */
 public class BalancedTree {
-    private static final boolean DEBUG = true;
-
     // Instance Variables ///////////////////////////////////////////////////////////////////
 
     private int root = 0;                         ///< the slot of the root element
@@ -25,8 +23,6 @@ public class BalancedTree {
     private int cached_index = -1;
     private int cached_slot = -1;
     
-    private FinalizationHelper fh;
-
     // Public API //////////////////////////////////////////////////////////////////////////
 
     /** the number of elements in the tree */
@@ -47,12 +43,10 @@ public class BalancedTree {
         if (root != 0) {
             insert(index, arg, root, 0, false, false);
         } else {
-            if(fh == null) fh = new FinalizationHelper(this);
             root = arg;
             left[arg] = right[arg] = parent[arg] = 0;
             size[arg] = 1;
         }
-        if(DEBUG) check();
         }
     }
 
@@ -66,7 +60,6 @@ public class BalancedTree {
         if (index >= treeSize()) index = treeSize() - 1;
         int arg = allocateSlot(o);
         insert(index, arg, root, 0, true, false);
-        if(DEBUG) check();
         }
     }
 
@@ -130,7 +123,6 @@ public class BalancedTree {
         left[del] = right[del] = size[del] = parent[del] = 0;
         Object ret = objects[del];
         objects[del] = null;
-        if(DEBUG) check();
         return ret;
         }
     }
@@ -147,7 +139,6 @@ public class BalancedTree {
         } while(i != 0);
         root = 0;
         }
-        if(DEBUG) check();
     }
 
     // Node Data /////////////////////////////////////////////////////////////////////////
@@ -267,7 +258,6 @@ public class BalancedTree {
         int d = right[b];
         int c = left[d];
         if (d == 0) throw new Error("rotation error");
-        if(DEBUG) check();
         left[d] = b;
         right[b] = c;
         
@@ -280,9 +270,7 @@ public class BalancedTree {
         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; }
+        size[d] = 1 + sizeof(left[d]) + sizeof(right[d]);        
     }
 
     private void balance(int slot, int p) {
@@ -307,8 +295,6 @@ 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
@@ -324,7 +310,6 @@ public class BalancedTree {
             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) {
@@ -335,12 +320,10 @@ public class BalancedTree {
             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] = 0;
             right[arg] = slot;        // make slot our right subtree
@@ -349,14 +332,12 @@ public class BalancedTree {
             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);
             }
@@ -431,46 +412,9 @@ public class BalancedTree {
             return slot;
         }
     }
-    
-    static class FinalizationHelper {
-        private BalancedTree bt;
-        FinalizationHelper(BalancedTree bt) { this.bt = bt; }
-        protected void finalize() { bt.clear(); }
-    }
 
-    // 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]);
-        }
-    }
-        
+    protected void finalize() { clear(); }
+
     public void printTree() {
         if(root == 0) System.err.println("Tree is empty");
         else printTree(root,0,false);
@@ -486,17 +430,4 @@ 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);
-        }        
-    }
 }