-// Copyright 2003 Adam Megacz, see the COPYING file for licensing [GPL]
+// Copyright (C) 2003 Adam Megacz <adam@xwt.org> all rights reserved.
+//
+// You may modify, copy, and redistribute this code under the terms of
+// the GNU Library Public License version 2.1, with the exception of
+// the portion of clause 6a after the semicolon (aka the "obnoxious
+// relink clause")
+
package org.xwt.util;
// FEATURE: private void intersection() { }
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);
- if (root != 0) { insert(index, arg, root, 0, false, false); return; }
- root = arg;
- left[arg] = 0;
- right[arg] = 0;
- size[root] = 1;
+ if (root != 0) {
+ insert(index, arg, root, 0, false, false);
+ } else {
+ root = arg;
+ left[arg] = 0;
+ right[arg] = 0;
+ size[root] = 1;
+ }
}
/** 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)];
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]) + indexNode(objects[parent]) + 1;
+ return size(left[slot]) + indexNode(objects[parent]) + 1;
}
/** returns the object at index; runs in O(log n) time unless cache hit */
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];
+ }
}
-
+ /*
+ cached_index = index;
+ cached_slot = get(index, root);
+ return objects[cached_slot];
+ */
return objects[get(index, root)];
}
/** deletes the object at index, returning the deleted object */
public final Object deleteNode(int index) {
- cached_slot = cached_index = 0;
- return delete(index, root, 0);
+ cached_slot = cached_index = -1;
+ int del = delete(index, root, 0);
+ left[del] = right[del] = size[del] = 0;
+ Object ret = objects[del];
+ objects[del] = null;
+ return ret;
}
// Node Data /////////////////////////////////////////////////////////////////////////
- private final static int NUM_SLOTS = 265 * 1024;
+ private final static int NUM_SLOTS = 64 * 1024;
/**
* Every object inserted into *any* tree gets a "slot" in this
* object will have multiple slots.
*/
private static Object[] objects = new Object[NUM_SLOTS];
- private static int[] left = new int[NUM_SLOTS]; ///< if positive: left child's slot; if negative: predecessor's slot
- private static int[] right = new int[NUM_SLOTS]; ///< if positive: right child's slot; if negative: successor's slot
- private static int[] size = new int[NUM_SLOTS]; ///< the number of descendants of this node *including the node itself*
+
+ /// These two arrays hold the left and right children of each
+ /// slot; in other words, left[x] is the *slot* of the left child
+ /// of the node in slot x.
+ ///
+ /// If x has no left child, then left[x] is -1 multiplied by the
+ /// slot of the node that precedes x; if x is the first node, then
+ /// left[x] is 0. The right[] array works the same way.
+ ///
+ private static int[] left = new int[NUM_SLOTS];
+ private static int[] right = 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 //////////////////////////////////////////////////////////////////////
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 (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) {
+ 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);
- size[slot] = 1 + size(left[slot]) + size(right[slot]);
}
if (size[arg] != 0) throw new Error("double insertion");
+ 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");
+ }
+ }
+
// we become the child of a former leaf
if (slot <= 0) {
int[] left = wentLeft ? BalancedTree.left : BalancedTree.right;
if (slot == root) {
root = arg;
balance(slot, arg);
+ balance(arg, 0);
} else {
(left[parent] == slot ? left : right)[parent] = arg;
balance(slot, arg);
// Deletion //////////////////////////////////////////////////////////////////////
- private Object delete(int index, int slot, int parent) {
+ private int delete(int index, int slot, int parent) {
int diff = index - size(left[slot]);
if (diff < 0) {
- Object ret = delete(index, left[slot], slot);
+ int ret = delete(index, left[slot], slot);
balance(slot, parent);
return ret;
} else if (diff > 0) {
- Object ret = delete(diff - 1, right[slot], slot);
+ int ret = delete(diff - 1, right[slot], slot);
balance(slot, parent);
return ret;
+ // we found the node to delete
} else {
- if (left[slot] == 0) {
+
+ // fast path: it has no children
+ if (left[slot] <= 0 && right[slot] <= 0) {
+ if (parent == 0) root = 0;
+ else {
+ int[] side = left[parent] == slot ? left : right;
+ side[parent] = 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];
- right[slot] = 0;
- balance(slot, parent);
- } else if (right[slot] == 0) {
+ 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);
+
+ // 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];
- left[slot] = 0;
- balance(slot, parent);
+ 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);
+
+ // node to be deleted has two children, so we replace it with its left child's rightmost descendant
} else {
- Object replacement_object = delete(index - 1, slot, parent);
- int replacement = allocateSlot(replacement_object);
- if (replacement != 0) {
- left[replacement] = left[slot];
- right[replacement] = right[slot];
- }
- if (parent == 0) root = replacement;
- else (left[parent] == slot ? left : right)[parent] = replacement;
- left[slot] = 0;
- right[slot] = 0;
- balance(replacement, 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];
+ 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);
}
- Object ret = objects[slot];
- size[slot] = 0;
- objects[slot] = null;
- return ret;
+
+ return slot;
}
}
projects / org.ibex.core.git / blobdiff