private int root = 0; ///< the slot of the root element
- private int cached_index = 0;
- private int cached_slot = 0;
+ private int cached_index = -1;
+ private int cached_slot = -1;
// Public API //////////////////////////////////////////////////////////////////////////
/** clamps index to [0..treeSize()] and inserts object o *before* the specified index */
public final void insertNode(int index, Object o) {
- cached_slot = cached_index = 0;
+ cached_slot = cached_index = -1;
if (index < 0) index = 0;
if (index > treeSize()) index = treeSize();
int arg = allocateSlot(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) {
- cached_slot = cached_index = 0;
+ cached_slot = cached_index = -1;
if (index < 0) index = 0;
if (index > treeSize()) index = treeSize() - 1;
int arg = allocateSlot(o);
/** returns the index of o; runs in O((log n)^2) time unless cache hit */
public final int indexNode(Object o) {
- if (objects[cached_slot] == o) return cached_index;
+ 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)];
public final Object getNode(int index) {
if (index == cached_index) return objects[cached_slot];
- int distance = Math.abs(index - cached_index);
-
- // if the in-order distance between the cached node and the
- // target node is less than log(n), it's probably faster to
- // search directly.
- if (cached_index != 0 && (distance < 16) && ((2 << distance) < treeSize())) {
- while(cached_index > index) { cached_slot = prev(cached_slot); cached_index--; }
- while(cached_index < index) { cached_slot = next(cached_slot); cached_index++; }
- return objects[cached_slot];
+ if (cached_index != -1) {
+ int distance = Math.abs(index - cached_index);
+ // if the in-order distance between the cached node and the
+ // target node is less than log(n), it's probably faster to
+ // search directly.
+ if ((distance < 16) && ((2 << distance) < treeSize())) {
+ while(cached_index > index) { cached_slot = prev(cached_slot); cached_index--; }
+ while(cached_index < index) { cached_slot = next(cached_slot); cached_index++; }
+ return objects[cached_slot];
+ }
}
return objects[get(index, root)];
/** deletes the object at index, returning the deleted object */
public final Object deleteNode(int index) {
- // FIXME handle root deletion here
- cached_slot = cached_index = 0;
+ cached_slot = cached_index = -1;
int del = delete(index, root, 0);
left[del] = right[del] = size[del] = 0;
Object ret = objects[del];
// fast path: it has no left child, so we replace it with its right child
if (left[slot] < 0) {
- (left[parent] == slot ? left : right)[parent] = right[slot]; // fix parent's pointer
+ 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 left ptr
balance(right[slot], parent);
// fast path; it has no right child, so we replace it with its left child
} else if (right[slot] < 0) {
- (left[parent] == slot ? left : right)[parent] = left[slot]; // fix parent's pointer
+ 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);
int left_childs_rightmost = delete(size(left[slot]) - 1, left[slot], slot);
left[left_childs_rightmost] = left[slot];
left[left_childs_rightmost] = right[slot];
- (left[parent] == slot ? left : right)[parent] = left_childs_rightmost; // fix parent's pointer
+ 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);
}