// 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 {
/** clamps index to [0..treeSize()] and inserts object o *before* the specified index */
public final synchronized void insertNode(int index, Object o) {
+ if(o == null) throw new Error("can't insert nulls in the balanced tree");
cached_slot = cached_index = -1;
if (index < 0) index = 0;
if (index > treeSize()) index = treeSize();
insert(index, arg, root, 0, false, false);
} else {
root = arg;
- left[arg] = 0;
- right[arg] = 0;
- size[root] = 1;
+ left[arg] = right[arg] = parent[arg] = 0;
+ size[arg] = 1;
}
}
/** clamps index to [0..treeSize()-1] and replaces the object at that index with object o */
public final synchronized void replaceNode(int index, Object o) {
+ if(o == null) throw new Error("can't insert nulls in the balanced tree");
cached_slot = cached_index = -1;
+ if(root == 0) throw new Error("called replaceNode() on an empty tree");
if (index < 0) index = 0;
- if (index > treeSize()) index = treeSize() - 1;
+ if (index >= treeSize()) index = treeSize() - 1;
int arg = allocateSlot(o);
- if (root != 0) { insert(index, arg, root, 0, true, false); return; }
- root = arg;
- left[arg] = 0;
- right[arg] = 0;
+ insert(index, arg, root, 0, true, false);
}
/** returns the index of o; runs in O((log n)^2) time unless cache hit */
public final synchronized int indexNode(Object o) {
+ if(o == null) return -1;
if (cached_slot != -1 && objects[cached_slot] == o) return cached_index;
- 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
- return size(left[slot]) + (parent <= 0 ? 0 : indexNode(objects[parent])) + 1;
+ int slot = getSlot(o);
+ if(slot == -1) return -1;
+
+ int index = 0;
+ while(true) {
+ // everything to the left is before us so add that to the index
+ index += size(left[slot]);
+ // we are before anything on the right
+ while(left[parent[slot]] == slot) slot = parent[slot];
+ // we end of the first node who isn't on the left, go to the node that has as its child
+ slot = parent[slot];
+ // if we just processed the root we're done
+ if(slot == 0) break;
+ // count the node we're currently on towards the index
+ index++;
+ }
+ return index;
}
/** returns the object at index; runs in O(log n) time unless cache hit */
/** deletes the object at index, returning the deleted object */
public final synchronized Object deleteNode(int index) {
cached_slot = cached_index = -1;
+ // FIXME: left[], right[], size[], and parent[] aren't getting cleared properly somewhere in here where a node had two children
int del = delete(index, root, 0);
- left[del] = right[del] = size[del] = 0;
+ left[del] = right[del] = size[del] = parent[del] = 0;
Object ret = objects[del];
objects[del] = null;
return ret;
}
+
+ public final synchronized void clear() {
+ if(root == 0) return;
+ int i = leftmost(root);
+ do {
+ int next = next(i);
+ objects[i] = null;
+ left[i] = right[i] = size[i] = parent[i] = 0;
+ i = next;
+ } while(i != 0);
+ root = 0;
+ }
+
+ protected void finalize() { clear(); }
// Node Data /////////////////////////////////////////////////////////////////////////
private final static int NUM_SLOTS = 64 * 1024;
+ // FEATURE: GROW - private final static int MAX_SLOT_DISTANCE = 32;
/**
* Every object inserted into *any* tree gets a "slot" in this
///
private static int[] left = new int[NUM_SLOTS];
private static int[] right = new int[NUM_SLOTS];
+
+ /// The parent of this node (0 if it is the root node)
+ private static int[] parent = new int[NUM_SLOTS];
///< the number of descendants of this node *including the node itself*
private static int[] size = new int[NUM_SLOTS];
// Slot Management //////////////////////////////////////////////////////////////////////
-
- /** returns the slot holding object o; use null to allocate a new slot */
- private int getSlot(Object o, int hash) {
- // FIXME: check for full table
- int dest = Math.abs(hash) % objects.length;
+
+ /** if alloc == false returns the slot holding object o. if alloc is true returns a new slot for obejct o */
+ private int getSlot(Object o, boolean alloc) {
+ // we XOR with our own hashcode so that we don't get tons of
+ // collisions when a single Object is inserted into multiple
+ // trees
+ int dest = Math.abs(o.hashCode() ^ this.hashCode()) % objects.length;
+ Object search = alloc ? null : o;
int odest = dest;
boolean plus = true;
int tries = 1;
- while (objects[dest] != o) {
+ while (objects[dest] != search || !(alloc || root(dest) == root)) {
if (dest == 0) dest++;
dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % objects.length);
if (plus) tries++;
plus = !plus;
+ // FEATURE: GROW - if(tries > MAX_SLOT_DISTANCE) return -1;
}
return dest;
}
- /** allocates a new slot */
+ /** returns the slots holding object o */
+ private int getSlot(Object o) { return getSlot(o,false); }
+
+ /** allocates a new slot holding object o*/
private int allocateSlot(Object o) {
- // we XOR with our own hashcode so that we don't get tons of
- // collisions when a single Object is inserted into multiple
- // trees
- int slot = getSlot(null, o.hashCode() ^ this.hashCode());
+ int slot = getSlot(o, true);
+ // FEATURE: GROW - if(slot == -1) throw new Error("out of slots");
objects[slot] = o;
return 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 size(int slot) { return slot <= 0 ? 0 : size[slot]; }
+ private final int root(int slot) { return parent[slot] == 0 ? slot : root(parent[slot]); }
// Rotation and Balancing /////////////////////////////////////////////////////////////
- // parent parent
+ // p p
// | |
// b d
// / \ / \
// / \ / \
// c e a c
// FIXME might be doing too much work here
- private void rotate(boolean toTheLeft, int b, int parent) {
+ private void rotate(boolean toTheLeft, int b, int p) {
int[] left = toTheLeft ? BalancedTree.left : BalancedTree.right;
int[] right = toTheLeft ? BalancedTree.right : BalancedTree.left;
int d = right[b];
int c = left[d];
if (d <= 0) throw new Error("rotation error");
left[d] = b;
- right[b] = c;
- if (parent == 0) root = d;
- else if (left[parent] == b) left[parent] = d;
- else if (right[parent] == b) right[parent] = d;
+ if(size[b] <= 3) // b is now a leaf
+ right[b] = -d;
+ else
+ right[b] = c;
+ parent[b] = d;
+ parent[d] = p;
+ 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 + size(left[b]) + size(right[b]);
size[d] = 1 + size(left[d]) + size(right[d]);
}
- private void balance(int slot, int parent) {
+ private void balance(int slot, int p) {
if (slot <= 0) return;
size[slot] = 1 + size(left[slot]) + size(right[slot]);
- if (size(left[slot]) - 1 > 2 * size(right[slot])) rotate(false, slot, parent);
- else if (size(left[slot]) * 2 < size(right[slot]) - 1) rotate(true, slot, parent);
+ if (size(left[slot]) - 1 > 2 * size(right[slot])) rotate(false, slot, p);
+ else if (size(left[slot]) * 2 < size(right[slot]) - 1) rotate(true, slot, p);
}
// Insert /////////////////////////////////////////////////////////////////////////
- private void insert(int index, int arg, int slot, int parent, boolean replace, boolean wentLeft) {
+ private void insert(int index, int arg, int slot, int p, 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, true);
else insert(index - size(left[slot]) - 1, arg, right[slot], slot, replace, false);
- balance(slot, parent);
+ balance(slot, p);
return;
}
if (size[arg] != 0) throw new Error("double insertion");
+ // we are replacing an existing node
if (replace) {
- if (diff == 0) {
- objects[slot] = objects[arg];
- objects[arg] = null;
- left[arg] = right[arg] = size[arg] = 0;
- } else {
- // since we already clamped the index
- throw new Error("this should never happen");
- }
- }
-
+ 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;
+ 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;
+ objects[slot] = null;
+ left[slot] = right[slot] = size[slot] = parent[slot] = 0;
+
// we become the child of a former leaf
- if (slot <= 0) {
+ } else if (slot <= 0) {
int[] left = wentLeft ? BalancedTree.left : BalancedTree.right;
int[] right = wentLeft ? BalancedTree.right : BalancedTree.left;
left[arg] = slot;
- left[parent] = arg;
- right[arg] = -1 * parent;
- balance(arg, parent);
+ left[p] = arg;
+ right[arg] = -1 * p;
+ parent[arg] = p;
+ balance(arg, p);
// we take the place of a preexisting node
} else {
left[arg] = left[slot]; // steal slot's left subtree
left[slot] = -1 * arg;
right[arg] = slot; // make slot our right subtree
+ parent[arg] = parent[slot];
+ parent[slot] = arg;
if (slot == root) {
root = arg;
balance(slot, arg);
balance(arg, 0);
} else {
- (left[parent] == slot ? left : right)[parent] = arg;
+ if (left[p] == slot) left[p] = arg;
+ else if (right[p] == slot) right[p] = arg;
+ else throw new Error("should never happen");
balance(slot, arg);
- balance(arg, parent);
+ balance(arg, p);
}
}
}
// Deletion //////////////////////////////////////////////////////////////////////
- private int delete(int index, int slot, int parent) {
+ private int delete(int index, int slot, int p) {
int diff = index - size(left[slot]);
if (diff < 0) {
int ret = delete(index, left[slot], slot);
- balance(slot, parent);
+ balance(slot, p);
return ret;
} else if (diff > 0) {
int ret = delete(diff - 1, right[slot], slot);
- balance(slot, parent);
+ balance(slot, p);
return ret;
// we found the node to delete
// fast path: it has no children
if (left[slot] <= 0 && right[slot] <= 0) {
- if (parent == 0) root = 0;
+ if (p == 0) root = 0;
else {
- int[] side = left[parent] == slot ? left : right;
- side[parent] = side[slot]; // fix parent's pointer
+ int[] side = left[p] == slot ? left : right;
+ side[p] = side[slot]; // fix parent's pointer
}
// fast path: it has no left child, so we replace it with its right child
} else if (left[slot] <= 0) {
- if (parent == 0) root = right[slot];
- else (left[parent] == slot ? left : right)[parent] = right[slot]; // fix parent's pointer
- if (right[slot] > 0) left[leftmost(right[slot])] = left[slot]; // fix our successor-leaf's fake right ptr
- balance(right[slot], parent);
+ if (p == 0) root = right[slot];
+ else (left[p] == slot ? left : right)[p] = right[slot]; // fix parent's pointer
+ parent[right[slot]] = p;
+ left[leftmost(right[slot])] = left[slot]; // fix our successor-leaf's fake right ptr
+ balance(right[slot], p);
// fast path; it has no right child, so we replace it with its left child
} else if (right[slot] <= 0) {
- if (parent == 0) root = left[slot];
- else (left[parent] == slot ? left : right)[parent] = left[slot]; // fix parent's pointer
- if (left[slot] > 0) right[rightmost(left[slot])] = right[slot]; // fix our successor-leaf's fake right ptr
- balance(left[slot], parent);
+ if (p == 0) root = left[slot];
+ else (left[p] == slot ? left : right)[p] = left[slot]; // fix parent's pointer
+ parent[left[slot]] = p;
+ right[rightmost(left[slot])] = right[slot]; // fix our successor-leaf's fake right ptr
+ balance(left[slot], p);
// node to be deleted has two children, so we replace it with its left child's rightmost descendant
} else {
int left_childs_rightmost = delete(size(left[slot]) - 1, left[slot], slot);
left[left_childs_rightmost] = left[slot];
right[left_childs_rightmost] = right[slot];
- if (parent == 0) root = left_childs_rightmost;
- else (left[parent] == slot ? left : right)[parent] = left_childs_rightmost; // fix parent's pointer
- balance(left_childs_rightmost, parent);
+ 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
+ balance(left_childs_rightmost, p);
}
return slot;
}
}
+ // Debugging ///////////////////////////////////////////////////////////////////////////
+
+ 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");
+ else {
+ System.err.print("" + node + ": " + objects[node]);
+ System.err.println(" Parent: " + parent[node]);
+ printTree(left[node],indent+1,true);
+ printTree(right[node],indent+1,false);
+ }
+ }
}
projects / org.ibex.core.git / commitdiff