+// FEATURE: private void intersection() { }
+// FEATURE: private void union() { }
+// FEATURE: private void subset() { }
+// FEATURE: grow if we run out of slots
+// FEATURE: finalizer
+
+/** a weight-balanced tree with fake leaves */
+public class BalancedTree {
+
+
+ // Instance Variables ///////////////////////////////////////////////////////////////////
+
+ private int root = 0; ///< the slot of the root element
+
+ private int cached_index = -1;
+ private int cached_slot = -1;
+
+ // Public API //////////////////////////////////////////////////////////////////////////
+
+ /** 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) {
+ 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);
+ } 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 synchronized void replaceNode(int index, Object o) {
+ cached_slot = cached_index = -1;
+ if (index < 0) index = 0;
+ if (index > treeSize()) index = treeSize() - 1;
+ int arg = allocateSlot(o);
+ 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 unless cache hit */
+ public final synchronized int indexNode(Object o) {
+ 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
+ return size(left[slot]) + (parent <= 0 ? 0 : indexNode(objects[parent])) + 1;
+ }
+
+ /** returns the object at index; runs in O(log n) time unless cache hit */
+ public final synchronized Object getNode(int index) {
+ if (index == 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 synchronized Object deleteNode(int index) {
+ 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 = 64 * 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];
+
+ /// 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];