BalancedTree: size[] sanity checking

darcs-hash:20040615085951-24bed-6559df8e79d524283c546bc6dc1ca1f2b67708ac.gz

diff --git a/src/org/ibex/util/BalancedTree.java b/src/org/ibex/util/BalancedTree.java
index be8be46..3fd04d8 100644 (file)
--- a/src/org/ibex/util/BalancedTree.java
+++ b/src/org/ibex/util/BalancedTree.java
@@ -267,7 +267,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 +279,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) {
@@ -335,7 +332,6 @@ 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
@@ -349,14 +345,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);
             }
@@ -450,6 +444,12 @@ public class BalancedTree {
             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]");
+            
+            int c = 0;
+            int n = leftmost(root);
+            while(n != 0) { c++; n = next(n); }
+            if(c != size[root]) throw new Error("size[] mismatch");
+            
             if(root != 0) check(root);
         } catch(Error e) {
             printTree();