1 // Copyright (C) 2003 Adam Megacz <adam@ibex.org> all rights reserved.
3 // You may modify, copy, and redistribute this code under the terms of
4 // the GNU Library Public License version 2.1, with the exception of
5 // the portion of clause 6a after the semicolon (aka the "obnoxious
10 // FEATURE: private void intersection() { }
11 // FEATURE: private void union() { }
12 // FEATURE: private void subset() { }
13 // FEATURE: grow if we run out of slots
15 /** a weight-balanced tree with fake leaves */
16 public class BalancedTree {
19 // Instance Variables ///////////////////////////////////////////////////////////////////
21 private int root = 0; ///< the slot of the root element
23 private int cached_index = -1;
24 private int cached_slot = -1;
26 // Public API //////////////////////////////////////////////////////////////////////////
28 /** the number of elements in the tree */
29 public final int treeSize() { return root == 0 ? 0 : size[root]; }
31 /** clamps index to [0..treeSize()] and inserts object o *before* the specified index */
32 public final synchronized void insertNode(int index, Object o) {
33 if(o == null) throw new Error("can't insert nulls in the balanced tree");
34 cached_slot = cached_index = -1;
35 if (index < 0) index = 0;
36 if (index > treeSize()) index = treeSize();
37 int arg = allocateSlot(o);
39 insert(index, arg, root, 0, false, false);
42 left[arg] = right[arg] = parent[arg] = 0;
47 /** clamps index to [0..treeSize()-1] and replaces the object at that index with object o */
48 public final synchronized void replaceNode(int index, Object o) {
49 if(o == null) throw new Error("can't insert nulls in the balanced tree");
50 cached_slot = cached_index = -1;
51 if(root == 0) throw new Error("called replaceNode() on an empty tree");
52 if (index < 0) index = 0;
53 if (index >= treeSize()) index = treeSize() - 1;
54 int arg = allocateSlot(o);
55 insert(index, arg, root, 0, true, false);
58 /** returns the index of o; runs in O((log n)^2) time unless cache hit */
59 public final synchronized int indexNode(Object o) {
60 if(o == null) return -1;
61 if (cached_slot != -1 && objects[cached_slot] == o) return cached_index;
63 int slot = getSlot(o);
64 if(slot == -1) return -1;
68 // everything to the left is before us so add that to the index
69 index += sizeof(left[slot]);
70 // we are before anything on the right
71 while(left[parent[slot]] == slot) slot = parent[slot];
72 // we end of the first node who isn't on the left, go to the node that has as its child
74 // if we just processed the root we're done
76 // count the node we're currently on towards the index
82 /** returns the object at index; runs in O(log n) time unless cache hit */
83 public final synchronized Object getNode(int index) {
84 if (index == cached_index) return objects[cached_slot];
86 if (cached_index != -1) {
87 int distance = Math.abs(index - cached_index);
88 // if the in-order distance between the cached node and the
89 // target node is less than log(n), it's probably faster to
91 if ((distance < 16) && ((2 << distance) < treeSize())) {
92 while(cached_index > index) { cached_slot = prev(cached_slot); cached_index--; }
93 while(cached_index < index) { cached_slot = next(cached_slot); cached_index++; }
94 return objects[cached_slot];
99 cached_slot = get(index, root);
100 return objects[cached_slot];
102 return objects[get(index, root)];
105 /** deletes the object at index, returning the deleted object */
106 public final synchronized Object deleteNode(int index) {
107 cached_slot = cached_index = -1;
108 // FIXME: left[], right[], size[], and parent[] aren't getting cleared properly somewhere in here where a node had two children
109 int del = delete(index, root, 0);
110 left[del] = right[del] = size[del] = parent[del] = 0;
111 Object ret = objects[del];
116 public final synchronized void clear() {
117 if(root == 0) return;
118 int i = leftmost(root);
122 left[i] = right[i] = size[i] = parent[i] = 0;
128 protected void finalize() { clear(); }
131 // Node Data /////////////////////////////////////////////////////////////////////////
133 private final static int NUM_SLOTS = 64 * 1024;
134 // FEATURE: GROW - private final static int MAX_SLOT_DISTANCE = 32;
137 * Every object inserted into *any* tree gets a "slot" in this
138 * array. The slot is determined by hashcode modulo the length of
139 * the array, with quadradic probing to resolve collisions. NOTE
140 * that the "slot" of a node is NOT the same as its index.
141 * Furthermore, if an object is inserted into multiple trees, that
142 * object will have multiple slots.
144 private static Object[] objects = new Object[NUM_SLOTS];
146 /// These two arrays hold the left and right children of each
147 /// slot; in other words, left[x] is the *slot* of the left child
148 /// of the node in slot x.
150 /// If x has no left child, then left[x] is -1 multiplied by the
151 /// slot of the node that precedes x; if x is the first node, then
152 /// left[x] is 0. The right[] array works the same way.
154 private static int[] left = new int[NUM_SLOTS];
155 private static int[] right = new int[NUM_SLOTS];
157 /// The parent of this node (0 if it is the root node)
158 private static int[] parent = new int[NUM_SLOTS];
160 ///< the number of descendants of this node *including the node itself*
161 private static int[] size = new int[NUM_SLOTS];
164 // Slot Management //////////////////////////////////////////////////////////////////////
166 /** if alloc == false returns the slot holding object o. if alloc is true returns a new slot for obejct o */
167 private int getSlot(Object o, boolean alloc) {
168 // we XOR with our own hashcode so that we don't get tons of
169 // collisions when a single Object is inserted into multiple
171 int dest = Math.abs(o.hashCode() ^ this.hashCode()) % objects.length;
172 if (dest == 0) dest = 1;
173 Object search = alloc ? null : o;
177 while (objects[dest] != search || !(alloc || root(dest) == root)) {
178 dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % objects.length);
179 if (dest == 0) dest=1;
182 // FEATURE: GROW - if(tries > MAX_SLOT_DISTANCE) return -1;
187 /** returns the slots holding object o */
188 private int getSlot(Object o) { return getSlot(o,false); }
190 /** allocates a new slot holding object o*/
191 private int allocateSlot(Object o) {
192 int slot = getSlot(o, true);
193 // FEATURE: GROW - if(slot == -1) throw new Error("out of slots");
200 // Helpers /////////////////////////////////////////////////////////////////////////
202 private final int leftmost(int slot) { return left[slot] <= 0 ? slot : leftmost(left[slot]); }
203 private final int rightmost(int slot) { return right[slot] <= 0 ? slot : rightmost(right[slot]); }
204 private final int next(int slot) { return right[slot] <= 0 ? -1 * right[slot] : leftmost(right[slot]); }
205 private final int prev(int slot) { return left[slot] <= 0 ? -1 * left[slot] : rightmost(left[slot]); }
206 private final int sizeof(int slot) { return slot <= 0 ? 0 : size[slot]; }
207 private final int root(int slot) { return parent[slot] == 0 ? slot : root(parent[slot]); }
210 // Rotation and Balancing /////////////////////////////////////////////////////////////
219 // FIXME might be doing too much work here
220 private void rotate(boolean toTheLeft, int b, int p) {
221 int[] left = toTheLeft ? BalancedTree.left : BalancedTree.right;
222 int[] right = toTheLeft ? BalancedTree.right : BalancedTree.left;
225 if (d <= 0) throw new Error("rotation error");
227 right[b] = c <= 0 ? -d : c;
230 if(c > 0) parent[c] = b;
232 if (p == 0) root = d;
233 else if (left[p] == b) left[p] = d;
234 else if (right[p] == b) right[p] = d;
235 else throw new Error("rotate called with invalid parent");
236 size[b] = 1 + sizeof(left[b]) + sizeof(right[b]);
237 size[d] = 1 + sizeof(left[d]) + sizeof(right[d]);
240 private void balance(int slot, int p) {
241 if (slot <= 0) return;
242 size[slot] = 1 + sizeof(left[slot]) + sizeof(right[slot]);
243 if (sizeof(left[slot]) - 1 > 2 * sizeof(right[slot])) rotate(false, slot, p);
244 else if (sizeof(left[slot]) * 2 < sizeof(right[slot]) - 1) rotate(true, slot, p);
249 // Insert /////////////////////////////////////////////////////////////////////////
251 private void insert(int index, int arg, int slot, int p, boolean replace, boolean wentLeft) {
252 int diff = slot <= 0 ? 0 : index - sizeof(left[slot]);
253 if (slot > 0 && diff != 0) {
254 if (diff < 0) insert(index, arg, left[slot], slot, replace, true);
255 else insert(index - sizeof(left[slot]) - 1, arg, right[slot], slot, replace, false);
260 if (size[arg] != 0) throw new Error("double insertion");
262 // we are replacing an existing node
264 if (diff != 0) throw new Error("this should never happen"); // since we already clamped the index
265 if (p == 0) root = arg;
266 else if (left[p] == slot) left[p] = arg;
267 else if (right[p] == slot) right[p] = arg;
268 left[arg] = left[slot];
269 right[arg] = right[slot];
270 size[arg] = size[slot];
271 parent[arg] = parent[slot];
272 if(left[slot] > 0) parent[left[slot]] = arg;
273 if(right[slot] > 0) parent[right[slot]] = arg;
274 objects[slot] = null;
275 left[slot] = right[slot] = size[slot] = parent[slot] = 0;
277 // we become the child of a former leaf
278 } else if (slot <= 0) {
279 int[] left = wentLeft ? BalancedTree.left : BalancedTree.right;
280 int[] right = wentLeft ? BalancedTree.right : BalancedTree.left;
287 // we take the place of a preexisting node
289 left[arg] = left[slot]; // steal slot's left subtree
290 left[slot] = -1 * arg;
291 right[arg] = slot; // make slot our right subtree
292 parent[arg] = parent[slot];
299 if (left[p] == slot) left[p] = arg;
300 else if (right[p] == slot) right[p] = arg;
301 else throw new Error("should never happen");
309 // Retrieval //////////////////////////////////////////////////////////////////////
311 private int get(int index, int slot) {
312 int diff = index - sizeof(left[slot]);
313 if (diff > 0) return get(diff - 1, right[slot]);
314 else if (diff < 0) return get(index, left[slot]);
319 // Deletion //////////////////////////////////////////////////////////////////////
321 private int delete(int index, int slot, int p) {
322 int diff = index - sizeof(left[slot]);
324 int ret = delete(index, left[slot], slot);
328 } else if (diff > 0) {
329 int ret = delete(diff - 1, right[slot], slot);
333 // we found the node to delete
335 // fast path: it has no children
336 if (left[slot] <= 0 && right[slot] <= 0) {
337 if (p == 0) root = 0;
339 int[] side = left[p] == slot ? left : right;
340 side[p] = side[slot]; // fix parent's pointer
342 // fast path: it has no left child, so we replace it with its right child
343 } else if (left[slot] <= 0) {
344 if (p == 0) root = right[slot];
345 else (left[p] == slot ? left : right)[p] = right[slot]; // fix parent's pointer
346 parent[right[slot]] = p;
347 left[leftmost(right[slot])] = left[slot]; // fix our successor-leaf's fake right ptr
348 balance(right[slot], p);
350 // fast path; it has no right child, so we replace it with its left child
351 } else if (right[slot] <= 0) {
352 if (p == 0) root = left[slot];
353 else (left[p] == slot ? left : right)[p] = left[slot]; // fix parent's pointer
354 parent[left[slot]] = p;
355 right[rightmost(left[slot])] = right[slot]; // fix our successor-leaf's fake right ptr
356 balance(left[slot], p);
358 // node to be deleted has two children, so we replace it with its left child's rightmost descendant
360 int left_childs_rightmost = delete(sizeof(left[slot]) - 1, left[slot], slot);
361 left[left_childs_rightmost] = left[slot];
362 right[left_childs_rightmost] = right[slot];
363 if(left[slot] > 0) parent[left[slot]] = left_childs_rightmost;
364 if(right[slot] > 0) parent[right[slot]] = left_childs_rightmost;
365 parent[left_childs_rightmost] = parent[slot];
366 if (p == 0) root = left_childs_rightmost;
367 else (left[p] == slot ? left : right)[p] = left_childs_rightmost; // fix parent's pointer
368 balance(left_childs_rightmost, p);
375 // Debugging ///////////////////////////////////////////////////////////////////////////
377 public void printTree() {
378 if(root == 0) System.err.println("Tree is empty");
379 else printTree(root,0,false);
381 private void printTree(int node,int indent,boolean l) {
382 for(int i=0;i<indent;i++) System.err.print(" ");
383 if(node < 0) System.err.println((l?"Prev: " : "Next: ") + -node);
384 else if(node == 0) System.err.println(l ? "Start" : "End");
386 System.err.print("" + node + ": " + objects[node]);
387 System.err.println(" Parent: " + parent[node]);
388 printTree(left[node],indent+1,true);
389 printTree(right[node],indent+1,false);