+ /** 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 /////////////////////////////////////////////////////////////////////////