/** the number of elements in the tree */
public final int treeSize() { return root == 0 ? 0 : size[root]; }
-
+
/** 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");
// collisions when a single Object is inserted into multiple
// trees
int dest = Math.abs(o.hashCode() ^ this.hashCode()) % objects.length;
- if (dest == 0) dest = 1;
Object search = alloc ? null : o;
int odest = dest;
boolean plus = true;
int tries = 1;
while (objects[dest] != search || !(alloc || root(dest) == root)) {
+ if (dest == 0) dest++;
dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % objects.length);
- if (dest == 0) dest=1;
if (plus) tries++;
plus = !plus;
// FEATURE: GROW - if(tries > MAX_SLOT_DISTANCE) return -1;
int c = left[d];
if (d <= 0) throw new Error("rotation error");
left[d] = b;
- right[b] = c <= 0 ? -d : c;
+ 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;
// we found the node to delete
} else {
+
// fast path: it has no children
if (left[slot] <= 0 && right[slot] <= 0) {
if (p == 0) root = 0;
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 (p == 0) root = right[slot];