// 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;
}
private void balance(int slot, int parent) {
+ /*
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);
+ */
size[slot] = 1 + size(left[slot]) + size(right[slot]);
}
// 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;