// Copyright 2003 Adam Megacz, see the COPYING file for licensing [GPL]
package org.xwt.util;
-// Implemented from http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/red_black.html
+// FEATURE: private void intersection() { }
+// FEATURE: private void union() { }
+// FEATURE: private void subset() { }
+// FEATURE: grow if we run out of slots
-// 1. Every node is either red or black.
-// 2. Every leaf node is black; if a red node has no right or left child,
-// pretend that an imaginary (sentinel) black node is there.
-// 3. If a node is red, then both its children are black.
-// 4. Every simple path from a node to a descendant leaf contains the
-// same number of black nodes.
+/** a weight-balanced tree with fake leaves */
+public class BalancedTree {
-// FIXME: ability to ask for n^th node; requires a descendant count
+ // Instance Variables ///////////////////////////////////////////////////////////////////
-/** a red-black tree of arbitrary objects */
-public class RedBlackTree {
+ private int root = 0; ///< the slot of the root element
- private static final boolean RED = false;
- private static final boolean BLACK = true;
- private static final int DELETE = 0;
- private static final int INSERT = 1;
+ // Public API //////////////////////////////////////////////////////////////////////////
- // These arrays are indexed by "slot", a totally meaningless number
- // assigned to each object object[slot] has index index[slot] and
- // color color[slot]. Note that slot 0 is reserved as "null".
+ /** the number of elements in the tree */
+ public int size() { return root == 0 ? 0 : size[root]; }
- // FEATURE: use a bitmask?
- private int[] left; ///< if positive: left child's slot; if negative: predecessor's slot
- private int[] right; ///< if positive: right child's slot; if negative: successor's slot
- private int[] size; ///< the number of descendants of this node *including the node itself*
- private Object[] objects; ///< every object in the tree has an entry here; ordering is completely random
+ /** clamps index to [0..size()] and inserts object o *before* the specified index */
+ public void insert(int index, Object o) {
+ if (index < 0) index = 0;
+ if (index > size()) index = size();
+ int arg = allocateSlot(o);
+ if (root != 0) { insert(index, arg, root, 0, false); return; }
+ root = arg;
+ left[arg] = 0;
+ right[arg] = 0;
+ }
+
+ /** clamps index to [0..size()-1] and replaces the object at that index with object o */
+ public void replace(int index, Object o) {
+ if (index < 0) index = 0;
+ if (index > size()) index = size() - 1;
+ int arg = allocateSlot(o);
+ if (root != 0) { insert(index, arg, root, 0, true); 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) {
+ 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;
+ }
+
+ /** returns the object at index; runs in O(log n) time */
+ public Object get(int index) {
+ return objects[get(index, root)];
+ }
+
+ /** deletes the object at index, returning the deleted object */
+ public Object delete(int index) {
+ return delete(index, root, 0);
+ }
+
+
+ // Node Data /////////////////////////////////////////////////////////////////////////
+
+ private final static int NUM_SLOTS = 265 * 1024;
+
+ /**
+ * Every object inserted into *any* tree gets a "slot" in this
+ * array. The slot is determined by hashcode modulo the length of
+ * the array, with quadradic probing to resolve collisions. NOTE
+ * that the "slot" of a node is NOT the same as its index.
+ * Furthermore, if an object is inserted into multiple trees, that
+ * 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*
+
+
+ // 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;
+ int odest = dest;
+ boolean plus = true;
+ int tries = 1;
+ while (objects[dest] != o) {
+ dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % objects.length);
+ if (plus) tries++;
+ plus = !plus;
+ }
+ return dest;
+ }
+
+ /** allocates a new slot */
+ 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());
+ objects[slot] = o;
+ return slot;
+ }
+
+
+
+ // Helpers /////////////////////////////////////////////////////////////////////////
- private int root = 0; ///< the slot of the root element
-
- private int freeslot = 0;
+ private final int leftmost(int slot) { return left[slot] <= 0 ? slot : leftmost(left[slot]); }
+ private final int rightmost(int slot) { return right[slot] <= 0 ? slot : rightmost(right[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 int leftmost(int slot) { return left[slot] <= 0 ? slot : leftmost(left[slot]); }
- private int rightmost(int slot) { return right[slot] <= 0 ? slot : rightmost(right[slot]); }
- private int next(int slot) { return right[slot] <= 0 ? -1 * right[slot] : leftmost(right[slot]); }
- private int prev(int slot) { return left[slot] <= 0 ? -1 * left[slot] : rightmost(left[slot]); }
+
+ // Rotation and Balancing /////////////////////////////////////////////////////////////
// parent parent
// | |
// a d < == > b e
// / \ / \
// c e a c
- void rotate(boolean toTheLeft, int b, int parent) {
- if (b == 0) throw new Error("rotate called on the null slot");
- int[] left = toTheLeft ? this.left : this.right;
- int[] right = toTheLeft ? this.right : this.left;
+ private void rotate(boolean toTheLeft, int b, int parent) {
+ int[] left = toTheLeft ? BalancedTree.left : BalancedTree.right;
+ int[] right = toTheLeft ? BalancedTree.right : BalancedTree.left;
int d = right[b];
- if (d == 0) throw new Error("attempted to rotate a node with only one child in the wrong direction");
int c = left[d];
left[d] = b;
right[b] = c;
- size[b] -= size[d];
- int csize = c <= 0 ? 0 : size[c] + 1;
- size[b] += csize;
- size[d] -= csize;
- size[d] += size[b];
+ size[b] = size(left[b]) + size(c);
+ size[d] = size[b] + size(right[d]);
if (parent == 0) root = d;
else if (left[parent] == b) left[parent] = d;
else if (right[parent] == b) right[parent] = d;
else throw new Error("rotate called with invalid parent");
}
- public void balance(int slot, int parent) {
- if (slot == 0) return;
- if (size[left[slot]] > 2 * size[right[slot]]) {
- rotate(false, slot, parent);
- } else if (size[left[slot]] * 2 < size[right[slot]]) {
- rotate(true, slot, parent);
- }
- size[slot] = 1 + size[left[slot]] + size[right[slot]];
+ 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]);
}
- // FIXME: maintain fakeptrs
- // private void intersection() { }
- // private void union() { }
- // private void subset() { }
+ // Insert /////////////////////////////////////////////////////////////////////////
+
+ private void insert(int index, int arg, int slot, int parent, boolean replace) {
+ 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);
+ balance(slot, parent);
+ return;
+ }
- private void insert(int idx, int arg, int slot, int parent) {
+ if (size[arg] != 0) throw new Error("double insertion");
- int diff = idx - size[left[slot]];
- if (slot == 0 || diff == 0) {
- if (size[arg] != 0) throw new Error("double insertion");
+ // 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;
+ left[arg] = slot;
+ right[arg] = parent;
+ left[parent] = arg;
+ balance(arg, parent);
+ // we become the child of a preexisting node
+ } else {
left[arg] = left[slot]; // steal slot's left subtree
- left[slot] = 0;
+ left[slot] = arg;
right[arg] = slot; // make slot our right subtree
-
- // FIXME: if slot == 0 we can't use it to figure out which end of parent we belong on
- if (parent == 0) root = arg;
- else (left[parent] == slot ? left : right)[parent] = arg;
-
+ if (slot == root) root = arg;
+ (left[parent] == slot ? left : right)[parent] = arg;
balance(slot, arg);
- balance(arg, slot);
- return;
+ balance(arg, parent);
}
-
- if (diff < 0) insert(idx, arg, left[slot], slot);
- else insert(idx - size[left[slot]] - 1, arg, right[slot], slot);
- balance(slot, parent);
}
- private int indexOf(int slot) {
- int parent = -1 * left[leftmost(slot)];
- if (parent == 0) return size[left[slot]]; // we are on the far left edge
- else return size[left[slot]] + indexOf(parent) + 1; // all nodes after parent and before us are in our left subtree
- }
- private int get(int idx, int slot) {
- int diff = idx - size[left[slot]];
+ // Retrieval //////////////////////////////////////////////////////////////////////
+
+ private int get(int index, int slot) {
+ int diff = index - size(left[slot]);
if (diff > 0) return get(diff - 1, right[slot]);
- else if (diff < 0) return get(idx, left[slot]);
+ else if (diff < 0) return get(index, left[slot]);
else return slot;
}
- // return slot that was deleted
- private int delete(int idx, int slot, int parent) {
- int diff = idx - size[left[slot]];
- if (slot == 0) return 0;
- else if (diff < 0) {
- int ret = delete(idx, left[slot], slot);
+
+ // Deletion //////////////////////////////////////////////////////////////////////
+
+ private Object delete(int index, int slot, int parent) {
+ int diff = index - size(left[slot]);
+ if (diff < 0) {
+ Object ret = delete(index, left[slot], slot);
balance(slot, parent);
return ret;
} else if (diff > 0) {
- int ret = delete(diff - 1, right[slot], slot);
+ Object ret = delete(diff - 1, right[slot], slot);
balance(slot, parent);
return ret;
} else {
- size[slot] = 0;
if (left[slot] == 0) {
if (parent == 0) root = right[slot];
else (left[parent] == slot ? left : right)[parent] = right[slot];
left[slot] = 0;
balance(slot, parent);
} else {
- int replacement = delete(idx - 1, slot, parent);
+ Object replacement_object = delete(index - 1, slot, parent);
+ int replacement = allocateSlot(replacement_object);
if (replacement != 0) {
left[replacement] = left[slot];
right[replacement] = right[slot];
right[slot] = 0;
balance(replacement, parent);
}
- return slot;
+ Object ret = objects[slot];
+ size[slot] = 0;
+ objects[slot] = null;
+ return ret;
}
}
projects / org.ibex.core.git / commitdiff