1 // Copyright 2000-2005 the Contributors, as shown in the revision logs.
2 // Licensed under the Apache Public Source License 2.0 ("the License").
3 // You may not use this file except in compliance with the License.
7 // FEATURE: private void intersection() { }
8 // FEATURE: private void union() { }
9 // FEATURE: private void subset() { }
10 // FEATURE: grow if we run out of slots
12 // FEATURE: Add the cached_index stuff back in
14 /** a weight-balanced tree with fake leaves */
15 public class BalancedTree {
16 private static final boolean DEBUG = true;
18 // Instance Variables ///////////////////////////////////////////////////////////////////
20 private int root = 0; ///< the slot of the root element
22 private int cached_index = -1;
23 private int cached_slot = -1;
25 private FinalizationHelper fh;
27 // Public API //////////////////////////////////////////////////////////////////////////
29 /** the number of elements in the tree */
30 public final int treeSize() {
31 synchronized(BalancedTree.class) {
32 return root == 0 ? 0 : size[root];
36 /** clamps index to [0..treeSize()] and inserts object o *before* the specified index */
37 public final void insertNode(int index, Object o) {
38 synchronized(BalancedTree.class) {
39 if(DEBUG) leafCheck();
40 if(o == null) throw new Error("can't insert nulls in the balanced tree");
41 cached_slot = cached_index = -1;
42 if (index < 0) index = 0;
43 if (index > treeSize()) index = treeSize();
44 int arg = allocateSlot(o);
46 insert(index, arg, root, 0, false, false);
48 if(fh == null) fh = new FinalizationHelper(this);
50 left[arg] = right[arg] = parent[arg] = 0;
54 if(DEBUG) leafCheck();
58 /** clamps index to [0..treeSize()-1] and replaces the object at that index with object o */
59 public final void replaceNode(int index, Object o) {
60 synchronized(BalancedTree.class) {
61 if(DEBUG) leafCheck();
62 if(o == null) throw new Error("can't insert nulls in the balanced tree");
63 cached_slot = cached_index = -1;
64 if(root == 0) throw new Error("called replaceNode() on an empty tree");
65 if (index < 0) index = 0;
66 if (index >= treeSize()) index = treeSize() - 1;
67 int arg = allocateSlot(o);
68 insert(index, arg, root, 0, true, false);
70 if(DEBUG) leafCheck();
74 /** returns the index of o; runs in O((log n)^2) time unless cache hit */
75 public final int indexNode(Object o) {
76 synchronized(BalancedTree.class) {
77 if(o == null) return -1;
78 if (cached_slot != -1 && objects[cached_slot] == o) return cached_index;
80 int slot = getSlot(o);
81 if(slot == -1) return -1;
85 // everything to the left is before us so add that to the index
86 index += sizeof(left[slot]);
87 // we are before anything on the right
88 while(left[parent[slot]] == slot) slot = parent[slot];
89 // we end of the first node who isn't on the left, go to the node that has as its child
91 // if we just processed the root we're done
93 // count the node we're currently on towards the index
100 /** returns the object at index; runs in O(log n) time unless cache hit */
101 public final Object getNode(int index) {
102 synchronized(BalancedTree.class) {
103 if(DEBUG) leafCheck();
104 if (index == cached_index) return objects[cached_slot];
106 if (cached_index != -1) {
107 int distance = Math.abs(index - cached_index);
108 // if the in-order distance between the cached node and the
109 // target node is less than log(n), it's probably faster to
111 if ((distance < 16) && ((2 << distance) < treeSize())) {
112 while(cached_index > index) { cached_slot = prev(cached_slot); cached_index--; }
113 while(cached_index < index) { cached_slot = next(cached_slot); cached_index++; }
114 return objects[cached_slot];
118 cached_index = index;
119 cached_slot = get(index, root);
120 return objects[cached_slot];
122 return objects[get(index, root)];
126 /** deletes the object at index, returning the deleted object */
127 public final Object deleteNode(int index) {
128 synchronized(BalancedTree.class) {
129 if(DEBUG) leafCheck();
130 cached_slot = cached_index = -1;
131 // FIXME: left[], right[], size[], and parent[] aren't getting cleared properly somewhere in here where a node had two children
132 int del = delete(index, root, 0);
133 left[del] = right[del] = size[del] = parent[del] = 0;
134 Object ret = objects[del];
137 if(DEBUG) leafCheck();
142 public final void clear() {
143 synchronized(BalancedTree.class) {
144 if(root == 0) return;
145 int i = leftmost(root);
149 left[i] = right[i] = size[i] = parent[i] = 0;
157 // Node Data /////////////////////////////////////////////////////////////////////////
159 private final static int NUM_SLOTS = 64 * 1024;
160 // FEATURE: GROW - private final static int MAX_SLOT_DISTANCE = 32;
163 * Every object inserted into *any* tree gets a "slot" in this
164 * array. The slot is determined by hashcode modulo the length of
165 * the array, with quadradic probing to resolve collisions. NOTE
166 * that the "slot" of a node is NOT the same as its index.
167 * Furthermore, if an object is inserted into multiple trees, that
168 * object will have multiple slots.
170 private static Object[] objects = new Object[NUM_SLOTS];
172 /// These two arrays hold the left and right children of each
173 /// slot; in other words, left[x] is the *slot* of the left child
174 /// of the node in slot x.
176 /// If x has no left child, then left[x] is -1 multiplied by the
177 /// slot of the node that precedes x; if x is the first node, then
178 /// left[x] is 0. The right[] array works the same way.
180 private static int[] left = new int[NUM_SLOTS];
181 private static int[] right = new int[NUM_SLOTS];
183 /// The parent of this node (0 if it is the root node)
184 private static int[] parent = new int[NUM_SLOTS];
186 ///< the number of descendants of this node *including the node itself*
187 private static int[] size = new int[NUM_SLOTS];
190 // Slot Management //////////////////////////////////////////////////////////////////////
192 /** if alloc == false returns the slot holding object o. if alloc is true returns a new slot for obejct o */
193 private int getSlot(Object o, boolean alloc) {
194 // we XOR with our own hashcode so that we don't get tons of
195 // collisions when a single Object is inserted into multiple
197 int dest = Math.abs(o.hashCode() ^ this.hashCode()) % objects.length;
198 Object search = alloc ? null : o;
202 if(dest == 0) dest=1;
203 while (objects[dest] != search || !(alloc || root(dest) == root)) {
204 dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % objects.length);
205 if (dest == 0) dest=1;
208 // FEATURE: GROW - if(tries > MAX_SLOT_DISTANCE) return -1;
213 /** returns the slots holding object o */
214 private int getSlot(Object o) { return getSlot(o,false); }
216 /** allocates a new slot holding object o*/
217 private int allocateSlot(Object o) {
218 int slot = getSlot(o, true);
219 // FEATURE: GROW - if(slot == -1) throw new Error("out of slots");
226 // Helpers /////////////////////////////////////////////////////////////////////////
228 // FEATURE: These might be faster if they aren't recursive
229 private final int leftmost(int slot) { return left[slot] <= 0 ? slot : leftmost(left[slot]); }
230 private final int rightmost(int slot) { return right[slot] <= 0 ? slot : rightmost(right[slot]); }
231 private final int sizeof(int slot) { return slot <= 0 ? 0 : size[slot]; }
232 private final int root(int slot) { return parent[slot] == 0 ? slot : root(parent[slot]); }
234 private int next(int node) {
235 if(right[node] > 0) {
237 while(left[node] > 0) node = left[node];
240 int p = parent[node];
241 while(right[p] == node) { node = p; p = parent[node]; };
246 private int prev(int node) {
249 while(right[node] > 0) node = right[node];
252 int p = parent[node];
253 while(left[p] == node) { node = p; p = parent[node]; }
258 // Rotation and Balancing /////////////////////////////////////////////////////////////
267 // FIXME might be doing too much work here
268 private void rotate(boolean toTheLeft, int b, int p) {
269 int[] left = toTheLeft ? BalancedTree.left : BalancedTree.right;
270 int[] right = toTheLeft ? BalancedTree.right : BalancedTree.left;
273 if (d == 0) throw new Error("rotation error");
279 if(c != 0) parent[c] = b;
281 if (p == 0) root = d;
282 else if (left[p] == b) left[p] = d;
283 else if (right[p] == b) right[p] = d;
284 else throw new Error("rotate called with invalid parent");
285 size[b] = 1 + sizeof(left[b]) + sizeof(right[b]);
286 size[d] = 1 + sizeof(left[d]) + sizeof(right[d]);
289 private void balance(int slot, int p) {
290 if (slot <= 0) return;
291 size[slot] = 1 + sizeof(left[slot]) + sizeof(right[slot]);
292 if (sizeof(left[slot]) - 1 > 2 * sizeof(right[slot])) rotate(false, slot, p);
293 else if (sizeof(left[slot]) * 2 < sizeof(right[slot]) - 1) rotate(true, slot, p);
298 // Insert /////////////////////////////////////////////////////////////////////////
300 private void insert(int index, int arg, int slot, int p, boolean replace, boolean wentLeft) {
301 int diff = slot == 0 ? 0 : index - sizeof(left[slot]);
302 if (slot != 0 && diff != 0) {
303 if (diff < 0) insert(index, arg, left[slot], slot, replace, true);
304 else insert(index - sizeof(left[slot]) - 1, arg, right[slot], slot, replace, false);
309 if (size[arg] != 0) throw new Error("double insertion");
313 // we are replacing an existing node
315 if (diff != 0) throw new Error("this should never happen"); // since we already clamped the index
316 if (p == 0) root = arg;
317 else if (left[p] == slot) left[p] = arg;
318 else if (right[p] == slot) right[p] = arg;
319 else throw new Error("should never happen");
320 left[arg] = left[slot];
321 right[arg] = right[slot];
322 size[arg] = size[slot];
323 parent[arg] = parent[slot];
324 if(left[slot] != 0) parent[left[slot]] = arg;
325 if(right[slot] != 0) parent[right[slot]] = arg;
326 objects[slot] = null;
327 left[slot] = right[slot] = size[slot] = parent[slot] = 0;
330 // we become the child of a former leaf
331 } else if (slot == 0) {
332 int[] left = wentLeft ? BalancedTree.left : BalancedTree.right;
333 int[] right = wentLeft ? BalancedTree.right : BalancedTree.left;
334 // FEATURE: Might be doing too much work here
341 // we take the place of a preexisting node
344 left[arg] = left[slot]; // steal slot's left subtree
346 right[arg] = slot; // make slot our right subtree
347 parent[arg] = parent[slot];
349 if(left[arg] != 0) parent[left[arg]] = arg;
355 if (left[p] == slot) left[p] = arg;
356 else if (right[p] == slot) right[p] = arg;
357 else throw new Error("should never happen");
365 // Retrieval //////////////////////////////////////////////////////////////////////
367 private int get(int index, int slot) {
368 int diff = index - sizeof(left[slot]);
369 if (diff > 0) return get(diff - 1, right[slot]);
370 else if (diff < 0) return get(index, left[slot]);
375 // Deletion //////////////////////////////////////////////////////////////////////
377 private int delete(int index, int slot, int p) {
378 int diff = index - sizeof(left[slot]);
380 int ret = delete(index, left[slot], slot);
384 } else if (diff > 0) {
385 int ret = delete(diff - 1, right[slot], slot);
389 // we found the node to delete
392 // fast path: it has no children
393 if (left[slot] == 0 && right[slot] == 0) {
394 if (p == 0) root = 0;
396 int[] side = left[p] == slot ? left : right;
397 side[p] = side[slot]; // fix parent's pointer
400 // fast path: it has no left child, so we replace it with its right child
401 } else if (left[slot] == 0) {
402 if (p == 0) root = right[slot];
403 else (left[p] == slot ? left : right)[p] = right[slot]; // fix parent's pointer
404 parent[right[slot]] = p;
405 left[leftmost(right[slot])] = left[slot]; // fix our successor-leaf's fake right ptr
406 balance(right[slot], p);
408 // fast path; it has no right child, so we replace it with its left child
409 } else if (right[slot] == 0) {
410 if (p == 0) root = left[slot];
411 else (left[p] == slot ? left : right)[p] = left[slot]; // fix parent's pointer
412 parent[left[slot]] = p;
413 right[rightmost(left[slot])] = right[slot]; // fix our successor-leaf's fake right ptr
414 balance(left[slot], p);
416 // node to be deleted has two children, so we replace it with its left child's rightmost descendant
418 int left_childs_rightmost = delete(sizeof(left[slot]) - 1, left[slot], slot);
419 left[left_childs_rightmost] = left[slot];
420 right[left_childs_rightmost] = right[slot];
421 if(left[slot] != 0) parent[left[slot]] = left_childs_rightmost;
422 if(right[slot] != 0) parent[right[slot]] = left_childs_rightmost;
423 parent[left_childs_rightmost] = parent[slot];
424 if (p == 0) root = left_childs_rightmost;
425 else (left[p] == slot ? left : right)[p] = left_childs_rightmost; // fix parent's pointer
426 balance(left_childs_rightmost, p);
433 static class FinalizationHelper {
434 private BalancedTree bt;
435 FinalizationHelper(BalancedTree bt) { this.bt = bt; }
436 protected void finalize() { bt.clear(); }
439 // Debugging ///////////////////////////////////////////////////////////////////////////
441 public void check() { check(false); }
442 public void check(boolean expensive) {
443 if(expensive) System.err.println("--> Running expensive balanced tree checks");
446 for(int i=0;i<NUM_SLOTS;i++)
447 if(left[i] < 0 || right[i] < 0) throw new Error("someone inserted a negative number");
448 if(parent[root] != 0) throw new Error("parent of the root isn't 0");
449 if(left[0] != 0 || right[0] != 0 || size[0] != 0 || parent[0] != 0)
450 throw new Error("someone messed with [0]");
453 int n = leftmost(root);
454 while(n != 0) { c++; n = next(n); }
455 if(c != size[root]) throw new Error("size[] mismatch");
457 if(root != 0) check(root);
464 private void check(int node) {
465 //if(next(node) != next2(node)) throw new Error("next(" + node + ") != next2(" + node + ")");
466 //if(prev(node) != prev2(node)) throw new Error("prev(" + node + ") != prev2(" + node + ")");
469 if(parent[left[node]] != node) throw new Error("parent node mismatch on left child of " + node);
472 if(right[node] > 0) {
473 if(parent[right[node]] != node) throw new Error("parent node mismatch on right child of " + node);
478 public void printTree() {
479 if(root == 0) System.err.println("Tree is empty");
480 else printTree(root,0,false);
483 private void printTree(int node,int indent,boolean l) {
484 for(int i=0;i<indent;i++) System.err.print(" ");
485 if(node == 0) System.err.println("None");
487 System.err.print("" + node + ": " + objects[node]);
488 System.err.println(" Parent: " + parent[node] + " Size: " + size[node]);
489 printTree(left[node],indent+1,true);
490 printTree(right[node],indent+1,false);
494 public static void main(String[] args) {
495 BalancedTree t = new BalancedTree();
496 for(int i=0;i<args.length;i++)
497 t.insertNode(i,args[i]);
499 for(int n = t.leftmost(t.root); n != 0; n = t.next(n)) {
500 System.err.println("Next: " + n);
502 for(int n = t.rightmost(t.root); n != 0; n = t.prev(n)) {
503 System.err.println("Prev: " + n);
507 public void leafCheck() throws RuntimeException {
508 if (!validateLeaves()) {
511 throw new RuntimeException("bad tree: forward != back");
515 public boolean validateLeaves() {
516 int[] forward = getLeavesForward();
517 int[] backward = getLeavesBackward();
518 if (forward.length != backward.length) {
521 else if (forward.length > 0) {
522 for (int i = 0;i<forward.length;i++) {
523 if (forward[i] != backward[forward.length - i - 1]) {
531 public void printLeaves() {
532 System.out.println("");
533 int[] forward = getLeavesForward();
534 int[] backward = getLeavesBackward();
535 if (forward.length > 0) {
536 System.err.println("forward: " + backward.length);
537 for (int i = 0;i<forward.length;i++) {
538 System.err.println(forward[i]);
541 if (backward.length > 0) {
542 System.err.println("backward: " + backward.length);
543 for (int i = backward.length-1;i>=0;i--) {
544 System.err.println(backward[i]);
549 public int[] getLeavesForward() {
550 int[] leaves = new int[size[root]];
551 if (size[root] > 0) {
552 leaves[0] = leftmost(root);
553 for (int i=1;i < leaves.length;i++) {
554 leaves[i] = next(leaves[i-1]);
560 public int[] getLeavesBackward() {
561 int[] leaves = new int[size[root]];
562 if (size[root] > 0) {
563 leaves[0] = rightmost(root);
564 for (int i=1;i < leaves.length;i++) {
565 leaves[i] = prev(leaves[i-1]);
571 public void validateTree() {
572 if(root == 0) System.err.println("Tree is empty");
573 else validateTree(root,0,false);
574 System.err.println("");
576 private void validateTree(int node,int indent,boolean l) {
578 else if(node == 0) {}
580 System.err.println((l?"Prev: " : "Next: ") + -node);
581 validateTree(left[node],indent+1,true);
582 validateTree(right[node],indent+1,false);