1 // Copyright (C) 2003 Adam Megacz <adam@xwt.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
16 /** a weight-balanced tree with fake leaves */
17 public class BalancedTree {
20 // Instance Variables ///////////////////////////////////////////////////////////////////
22 private int root = 0; ///< the slot of the root element
24 private int cached_index = -1;
25 private int cached_slot = -1;
27 // Public API //////////////////////////////////////////////////////////////////////////
29 /** the number of elements in the tree */
30 public final int treeSize() { return root == 0 ? 0 : size[root]; }
32 /** clamps index to [0..treeSize()] and inserts object o *before* the specified index */
33 public final void insertNode(int index, Object o) {
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);
48 /** clamps index to [0..treeSize()-1] and replaces the object at that index with object o */
49 public final void replaceNode(int index, Object o) {
50 cached_slot = cached_index = -1;
51 if (index < 0) index = 0;
52 if (index > treeSize()) index = treeSize() - 1;
53 int arg = allocateSlot(o);
54 if (root != 0) { insert(index, arg, root, 0, true, false); return; }
60 /** returns the index of o; runs in O((log n)^2) time unless cache hit */
61 public final int indexNode(Object o) {
62 if (cached_slot != -1 && objects[cached_slot] == o) return cached_index;
64 int slot = getSlot(o, o.hashCode() ^ this.hashCode());
65 int parent = -1 * left[leftmost(slot)];
66 if (parent == 0) return size(left[slot]); // we are on the far left edge
68 // all nodes after parent and before us are in our left subtree
69 return size(left[slot]) + (parent <= 0 ? 0 : indexNode(objects[parent])) + 1;
72 /** returns the object at index; runs in O(log n) time unless cache hit */
73 public final Object getNode(int index) {
74 if (index == cached_index) return objects[cached_slot];
76 if (cached_index != -1) {
77 int distance = Math.abs(index - cached_index);
78 // if the in-order distance between the cached node and the
79 // target node is less than log(n), it's probably faster to
81 if ((distance < 16) && ((2 << distance) < treeSize())) {
82 while(cached_index > index) { cached_slot = prev(cached_slot); cached_index--; }
83 while(cached_index < index) { cached_slot = next(cached_slot); cached_index++; }
84 return objects[cached_slot];
89 cached_slot = get(index, root);
90 return objects[cached_slot];
92 return objects[get(index, root)];
95 /** deletes the object at index, returning the deleted object */
96 public final Object deleteNode(int index) {
97 cached_slot = cached_index = -1;
98 int del = delete(index, root, 0);
99 left[del] = right[del] = size[del] = 0;
100 Object ret = objects[del];
106 // Node Data /////////////////////////////////////////////////////////////////////////
108 private final static int NUM_SLOTS = 64 * 1024;
111 * Every object inserted into *any* tree gets a "slot" in this
112 * array. The slot is determined by hashcode modulo the length of
113 * the array, with quadradic probing to resolve collisions. NOTE
114 * that the "slot" of a node is NOT the same as its index.
115 * Furthermore, if an object is inserted into multiple trees, that
116 * object will have multiple slots.
118 private static Object[] objects = new Object[NUM_SLOTS];
120 /// These two arrays hold the left and right children of each
121 /// slot; in other words, left[x] is the *slot* of the left child
122 /// of the node in slot x.
124 /// If x has no left child, then left[x] is -1 multiplied by the
125 /// slot of the node that precedes x; if x is the first node, then
126 /// left[x] is 0. The right[] array works the same way.
128 private static int[] left = new int[NUM_SLOTS];
129 private static int[] right = new int[NUM_SLOTS];
131 ///< the number of descendants of this node *including the node itself*
132 private static int[] size = new int[NUM_SLOTS];
135 // Slot Management //////////////////////////////////////////////////////////////////////
137 /** returns the slot holding object o; use null to allocate a new slot */
138 private int getSlot(Object o, int hash) {
139 // FIXME: check for full table
140 int dest = Math.abs(hash) % objects.length;
144 while (objects[dest] != o) {
145 if (dest == 0) dest++;
146 dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % objects.length);
153 /** allocates a new slot */
154 private int allocateSlot(Object o) {
155 // we XOR with our own hashcode so that we don't get tons of
156 // collisions when a single Object is inserted into multiple
158 int slot = getSlot(null, o.hashCode() ^ this.hashCode());
165 // Helpers /////////////////////////////////////////////////////////////////////////
167 private final int leftmost(int slot) { return left[slot] <= 0 ? slot : leftmost(left[slot]); }
168 private final int rightmost(int slot) { return right[slot] <= 0 ? slot : rightmost(right[slot]); }
169 private final int next(int slot) { return right[slot] <= 0 ? -1 * right[slot] : leftmost(right[slot]); }
170 private final int prev(int slot) { return left[slot] <= 0 ? -1 * left[slot] : rightmost(left[slot]); }
171 private final int size(int slot) { return slot <= 0 ? 0 : size[slot]; }
174 // Rotation and Balancing /////////////////////////////////////////////////////////////
183 // FIXME might be doing too much work here
184 private void rotate(boolean toTheLeft, int b, int parent) {
185 int[] left = toTheLeft ? BalancedTree.left : BalancedTree.right;
186 int[] right = toTheLeft ? BalancedTree.right : BalancedTree.left;
189 if (d <= 0) throw new Error("rotation error");
192 if (parent == 0) root = d;
193 else if (left[parent] == b) left[parent] = d;
194 else if (right[parent] == b) right[parent] = d;
195 else throw new Error("rotate called with invalid parent");
196 size[b] = 1 + size(left[b]) + size(right[b]);
197 size[d] = 1 + size(left[d]) + size(right[d]);
200 private void balance(int slot, int parent) {
201 if (slot <= 0) return;
202 size[slot] = 1 + size(left[slot]) + size(right[slot]);
203 if (size(left[slot]) - 1 > 2 * size(right[slot])) rotate(false, slot, parent);
204 else if (size(left[slot]) * 2 < size(right[slot]) - 1) rotate(true, slot, parent);
209 // Insert /////////////////////////////////////////////////////////////////////////
211 private void insert(int index, int arg, int slot, int parent, boolean replace, boolean wentLeft) {
212 int diff = slot <= 0 ? 0 : index - size(left[slot]);
213 if (slot > 0 && diff != 0) {
214 if (diff < 0) insert(index, arg, left[slot], slot, replace, true);
215 else insert(index - size(left[slot]) - 1, arg, right[slot], slot, replace, false);
216 balance(slot, parent);
220 if (size[arg] != 0) throw new Error("double insertion");
224 objects[slot] = objects[arg];
226 left[arg] = right[arg] = size[arg] = 0;
228 // since we already clamped the index
229 throw new Error("this should never happen");
233 // we become the child of a former leaf
235 int[] left = wentLeft ? BalancedTree.left : BalancedTree.right;
236 int[] right = wentLeft ? BalancedTree.right : BalancedTree.left;
239 right[arg] = -1 * parent;
240 balance(arg, parent);
242 // we take the place of a preexisting node
244 left[arg] = left[slot]; // steal slot's left subtree
245 left[slot] = -1 * arg;
246 right[arg] = slot; // make slot our right subtree
252 (left[parent] == slot ? left : right)[parent] = arg;
254 balance(arg, parent);
260 // Retrieval //////////////////////////////////////////////////////////////////////
262 private int get(int index, int slot) {
263 int diff = index - size(left[slot]);
264 if (diff > 0) return get(diff - 1, right[slot]);
265 else if (diff < 0) return get(index, left[slot]);
270 // Deletion //////////////////////////////////////////////////////////////////////
272 private int delete(int index, int slot, int parent) {
273 int diff = index - size(left[slot]);
275 int ret = delete(index, left[slot], slot);
276 balance(slot, parent);
279 } else if (diff > 0) {
280 int ret = delete(diff - 1, right[slot], slot);
281 balance(slot, parent);
284 // we found the node to delete
287 // fast path: it has no children
288 if (left[slot] <= 0 && right[slot] <= 0) {
289 if (parent == 0) root = 0;
291 int[] side = left[parent] == slot ? left : right;
292 side[parent] = side[slot]; // fix parent's pointer
295 // fast path: it has no left child, so we replace it with its right child
296 } else if (left[slot] <= 0) {
297 if (parent == 0) root = right[slot];
298 else (left[parent] == slot ? left : right)[parent] = right[slot]; // fix parent's pointer
299 if (right[slot] > 0) left[leftmost(right[slot])] = left[slot]; // fix our successor-leaf's fake right ptr
300 balance(right[slot], parent);
302 // fast path; it has no right child, so we replace it with its left child
303 } else if (right[slot] <= 0) {
304 if (parent == 0) root = left[slot];
305 else (left[parent] == slot ? left : right)[parent] = left[slot]; // fix parent's pointer
306 if (left[slot] > 0) right[rightmost(left[slot])] = right[slot]; // fix our successor-leaf's fake right ptr
307 balance(left[slot], parent);
309 // node to be deleted has two children, so we replace it with its left child's rightmost descendant
311 int left_childs_rightmost = delete(size(left[slot]) - 1, left[slot], slot);
312 left[left_childs_rightmost] = left[slot];
313 right[left_childs_rightmost] = right[slot];
314 if (parent == 0) root = left_childs_rightmost;
315 else (left[parent] == slot ? left : right)[parent] = left_childs_rightmost; // fix parent's pointer
316 balance(left_childs_rightmost, parent);