/** 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
left[arg] = right[arg] = parent[arg] = 0;
size[arg] = 1;
}
- if(DEBUG) check();
}
}
if (index >= treeSize()) index = treeSize() - 1;
int arg = allocateSlot(o);
insert(index, arg, root, 0, true, false);
- if(DEBUG) check();
}
}
left[del] = right[del] = size[del] = parent[del] = 0;
Object ret = objects[del];
objects[del] = null;
- if(DEBUG) check();
return ret;
}
}
} while(i != 0);
root = 0;
}
- if(DEBUG) check();
}
// Node Data /////////////////////////////////////////////////////////////////////////
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(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) {
// 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
protected void finalize() { 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]");
-
- 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();
- 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);
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);
- }
- }*/
}