// FEATURE: private void union() { }
// FEATURE: private void subset() { }
// FEATURE: grow if we run out of slots
+// FEATURE: finalizer
/** a weight-balanced tree with fake leaves */
public class BalancedTree {
// Public API //////////////////////////////////////////////////////////////////////////
/** the number of elements in the tree */
- public int size() { return root == 0 ? 0 : size[root]; }
+ public final int treeSize() { return root == 0 ? 0 : size[root]; }
- /** clamps index to [0..size()] and inserts object o *before* the specified index */
- public void insert(int index, Object o) {
+ /** clamps index to [0..treeSize()] and inserts object o *before* the specified index */
+ public final void insertNode(int index, Object o) {
if (index < 0) index = 0;
- if (index > size()) index = size();
+ if (index > treeSize()) index = treeSize();
int arg = allocateSlot(o);
- if (root != 0) { insert(index, arg, root, 0, false); return; }
+ if (root != 0) { insert(index, arg, root, 0, false, false); return; }
root = arg;
left[arg] = 0;
right[arg] = 0;
+ size[root] = 1;
}
- /** clamps index to [0..size()-1] and replaces the object at that index with object o */
- public void replace(int index, Object o) {
+ /** clamps index to [0..treeSize()-1] and replaces the object at that index with object o */
+ public final void replaceNode(int index, Object o) {
if (index < 0) index = 0;
- if (index > size()) index = size() - 1;
+ if (index > treeSize()) index = treeSize() - 1;
int arg = allocateSlot(o);
- if (root != 0) { insert(index, arg, root, 0, true); return; }
+ if (root != 0) { insert(index, arg, root, 0, true, false); return; }
root = arg;
left[arg] = 0;
right[arg] = 0;
}
/** returns the index of o; runs in O((log n)^2) time */
- public int index(Object o) {
+ public final int indexNode(Object o) {
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
// all nodes after parent and before us are in our left subtree
- else return size(left[slot]) + index(objects[parent]) + 1;
+ else return size(left[slot]) + indexNode(objects[parent]) + 1;
}
/** returns the object at index; runs in O(log n) time */
- public Object get(int index) {
+ public final Object getNode(int index) {
return objects[get(index, root)];
}
/** deletes the object at index, returning the deleted object */
- public Object delete(int index) {
+ public final Object deleteNode(int index) {
return delete(index, root, 0);
}
boolean plus = true;
int tries = 1;
while (objects[dest] != o) {
+ if (dest == 0) dest++;
dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % objects.length);
if (plus) tries++;
plus = !plus;
// a d < == > b e
// / \ / \
// c e a c
+ // FIXME might be doing too much work here
private void rotate(boolean toTheLeft, int b, int parent) {
int[] left = toTheLeft ? BalancedTree.left : BalancedTree.right;
int[] right = toTheLeft ? BalancedTree.right : BalancedTree.left;
int c = left[d];
left[d] = b;
right[b] = c;
- size[b] = size(left[b]) + size(c);
- size[d] = size[b] + size(right[d]);
if (parent == 0) root = d;
else if (left[parent] == b) left[parent] = d;
else if (right[parent] == b) right[parent] = d;
else throw new Error("rotate called with invalid parent");
+ size[b] = 1 + size(left[b]) + size(right[b]);
+ balance(b, d);
+ size[d] = 1 + size(left[d]) + size(right[d]);
+ balance(d, parent);
}
private void balance(int slot, int parent) {
// Insert /////////////////////////////////////////////////////////////////////////
- private void insert(int index, int arg, int slot, int parent, boolean replace) {
+ private void insert(int index, int arg, int slot, int parent, boolean replace, boolean wentLeft) {
int diff = slot <= 0 ? 0 : index - size(left[slot]);
- if (slot >= 0 && diff != 0) {
- if (diff <= 0) insert(index, arg, left[slot], slot, replace);
- else insert(index - size(left[slot]) - 1, arg, right[slot], slot, replace);
+ if (slot > 0 && diff != 0) {
+ if (diff < 0) insert(index, arg, left[slot], slot, replace, true);
+ else insert(index - size(left[slot]) - 1, arg, right[slot], slot, replace, false);
balance(slot, parent);
return;
}
// we become the child of a former leaf
if (slot <= 0) {
- int[] left = BalancedTree.left[parent] == slot ? BalancedTree.left : BalancedTree.right;
- int[] right = BalancedTree.left[parent] == slot ? BalancedTree.right : BalancedTree.left;
+ int[] left = wentLeft ? BalancedTree.left : BalancedTree.right;
+ int[] right = wentLeft ? BalancedTree.right : BalancedTree.left;
left[arg] = slot;
- right[arg] = parent;
left[parent] = arg;
+ right[arg] = -1 * parent;
balance(arg, parent);
- // we become the child of a preexisting node
+ // we take the place of a preexisting node
} else {
left[arg] = left[slot]; // steal slot's left subtree
- left[slot] = arg;
+ left[slot] = -1 * arg;
right[arg] = slot; // make slot our right subtree
- if (slot == root) root = arg;
- (left[parent] == slot ? left : right)[parent] = arg;
- balance(slot, arg);
- balance(arg, parent);
+ if (slot == root) {
+ root = arg;
+ balance(slot, arg);
+ } else {
+ (left[parent] == slot ? left : right)[parent] = arg;
+ balance(slot, arg);
+ balance(arg, parent);
+ }
}
}
projects / org.ibex.core.git / blobdiff