src/org/ibex/util/BalancedTree.java

   1 // Copyright (C) 2003 Adam Megacz <adam@ibex.org> all rights reserved.
   2 //
   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
   6 // relink clause")
   7
   8 package org.ibex.util;
   9
  10 // FEATURE: private void intersection() { }
  11 // FEATURE: private void union() { }
  12 // FEATURE: private void subset() { }
  13 // FEATURE: grow if we run out of slots
  14
  15 /** a weight-balanced tree with fake leaves */
  16 public class BalancedTree {
  17
  18
  19     // Instance Variables ///////////////////////////////////////////////////////////////////
  20
  21     private int root = 0;                         ///< the slot of the root element
  22
  23     private int cached_index = -1;
  24     private int cached_slot = -1;
  25
  26     // Public API //////////////////////////////////////////////////////////////////////////
  27
  28     /** the number of elements in the tree */
  29     public final int treeSize() { return root == 0 ? 0 : size[root]; }
  30
  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);
  38         if (root != 0) {
  39             insert(index, arg, root, 0, false, false);
  40         } else {
  41             root = arg;
  42             left[arg] = right[arg] = parent[arg] = 0;
  43             size[arg] = 1;
  44         }
  45     }
  46
  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);
  56     }
  57
  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;
  62
  63         int slot = getSlot(o);
  64         if(slot == -1) return -1;
  65
  66         int index = 0;
  67         while(true) {
  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
  73             slot = parent[slot];
  74             // if we just processed the root we're done
  75             if(slot == 0) break;
  76             // count the node we're currently on towards the index
  77             index++;
  78         }
  79         return index;
  80     }
  81
  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];
  85
  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
  90             // search directly.
  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];
  95             }
  96         }
  97         /*
  98         cached_index = index;
  99         cached_slot = get(index, root);
 100         return objects[cached_slot];
 101         */
 102         return objects[get(index, root)];
 103     }
 104
 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];
 112         objects[del] = null;
 113         return ret;
 114     }
 115
 116     public final synchronized void clear() {
 117         if(root == 0) return;
 118         int i = leftmost(root);
 119         do {
 120             int next = next(i);
 121             objects[i] = null;
 122             left[i] = right[i] = size[i] = parent[i] = 0;
 123             i = next;
 124         } while(i != 0);
 125         root = 0;
 126     }
 127
 128     protected void finalize() { clear(); }
 129
 130
 131     // Node Data /////////////////////////////////////////////////////////////////////////
 132
 133     private final static int NUM_SLOTS = 64 * 1024;
 134     // FEATURE: GROW - private final static int MAX_SLOT_DISTANCE = 32;
 135
 136     /**
 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.
 143      */
 144     private static Object[] objects = new Object[NUM_SLOTS];
 145
 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.
 149     ///
 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.
 153     ///
 154     private static int[] left = new int[NUM_SLOTS];
 155     private static int[] right = new int[NUM_SLOTS];
 156
 157     /// The parent of this node (0 if it is the root node)
 158     private static int[] parent = new int[NUM_SLOTS];
 159
 160     ///< the number of descendants of this node *including the node itself*
 161     private static int[] size = new int[NUM_SLOTS];
 162
 163
 164     // Slot Management //////////////////////////////////////////////////////////////////////
 165
 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
 170         // trees
 171         int dest = Math.abs(o.hashCode() ^ this.hashCode()) % objects.length;
 172         Object search = alloc ? null : o;
 173         int odest = dest;
 174         boolean plus = true;
 175         int tries = 1;
 176         while (objects[dest] != search || !(alloc || root(dest) == root)) {
 177             if (dest == 0) dest++;
 178             dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % objects.length);
 179             if (plus) tries++;
 180             plus = !plus;
 181             // FEATURE: GROW - if(tries > MAX_SLOT_DISTANCE) return -1;
 182         }
 183         return dest;
 184     }
 185
 186     /** returns the slots holding object o */
 187     private int getSlot(Object o) { return getSlot(o,false); }
 188
 189     /** allocates a new slot holding object o*/
 190     private int allocateSlot(Object o) {
 191         int slot = getSlot(o, true);
 192         // FEATURE: GROW - if(slot == -1) throw new Error("out of slots");
 193         objects[slot] = o;
 194         return slot;
 195     }
 196
 197
 198
 199     // Helpers /////////////////////////////////////////////////////////////////////////
 200
 201     private final int leftmost(int slot) { return left[slot] <= 0 ? slot : leftmost(left[slot]); }
 202     private final int rightmost(int slot) { return right[slot] <= 0 ? slot : rightmost(right[slot]); }
 203     private final int next(int slot) { return right[slot] <= 0 ? -1 * right[slot] : leftmost(right[slot]); }
 204     private final int prev(int slot) { return left[slot] <= 0 ? -1 * left[slot] : rightmost(left[slot]); }
 205     private final int sizeof(int slot) { return slot <= 0 ? 0 : size[slot]; }
 206     private final int root(int slot) { return parent[slot] == 0 ? slot : root(parent[slot]); }
 207
 208
 209     // Rotation and Balancing /////////////////////////////////////////////////////////////
 210
 211     //      p                  p
 212     //      |                  |
 213     //      b                  d
 214     //     / \                / \
 215     //    a   d    < == >    b   e
 216     //       / \            / \
 217     //      c   e          a   c
 218     // FIXME might be doing too much work here
 219     private void rotate(boolean toTheLeft, int b, int p) {
 220         int[] left = toTheLeft ? BalancedTree.left : BalancedTree.right;
 221         int[] right = toTheLeft ? BalancedTree.right : BalancedTree.left;
 222         int d = right[b];
 223         int c = left[d];
 224         if (d <= 0) throw new Error("rotation error");
 225         left[d] = b;
 226         if(size[b] <= 3) // b is now a leaf
 227             right[b] = -d;
 228         else
 229             right[b] = c;
 230         parent[b] = d;
 231         parent[d] = p;
 232         if(c > 0) parent[c] = b;
 233         if (p == 0)              root = d;
 234         else if (left[p] == b)   left[p] = d;
 235         else if (right[p] == b)  right[p] = d;
 236         else throw new Error("rotate called with invalid parent");
 237         size[b] = 1 + sizeof(left[b]) + sizeof(right[b]);
 238         size[d] = 1 + sizeof(left[d]) + sizeof(right[d]);
 239     }
 240
 241     private void balance(int slot, int p) {
 242         if (slot <= 0) return;
 243         size[slot] = 1 + sizeof(left[slot]) + sizeof(right[slot]);
 244         if (sizeof(left[slot]) - 1 > 2 * sizeof(right[slot])) rotate(false, slot, p);
 245         else if (sizeof(left[slot]) * 2 < sizeof(right[slot]) - 1) rotate(true, slot, p);
 246     }
 247
 248
 249
 250     // Insert /////////////////////////////////////////////////////////////////////////
 251
 252     private void insert(int index, int arg, int slot, int p, boolean replace, boolean wentLeft) {
 253         int diff = slot <= 0 ? 0 : index - sizeof(left[slot]);
 254         if (slot > 0 && diff != 0) {
 255             if (diff < 0) insert(index, arg, left[slot], slot, replace, true);
 256             else insert(index - sizeof(left[slot]) - 1, arg, right[slot], slot, replace, false);
 257             balance(slot, p);
 258             return;
 259         }
 260
 261         if (size[arg] != 0) throw new Error("double insertion");
 262
 263         // we are replacing an existing node
 264         if (replace) {
 265             if (diff != 0) throw new Error("this should never happen"); // since we already clamped the index
 266             if (p == 0)                 root = arg;
 267             else if (left[p] == slot)   left[p] = arg;
 268             else if (right[p] == slot)  right[p] = arg;
 269             left[arg] = left[slot];
 270             right[arg] = right[slot];
 271             size[arg] = size[slot];
 272             parent[arg] = parent[slot];
 273             if(left[slot] > 0) parent[left[slot]] = arg;
 274             if(right[slot] > 0) parent[right[slot]] = arg;
 275             objects[slot] = null;
 276             left[slot] = right[slot] = size[slot] = parent[slot] = 0;
 277
 278         // we become the child of a former leaf
 279         } else if (slot <= 0) {
 280             int[] left = wentLeft ? BalancedTree.left : BalancedTree.right;
 281             int[] right = wentLeft ? BalancedTree.right : BalancedTree.left;
 282             left[arg] = slot;
 283             left[p] = arg;
 284             right[arg] = -1 * p;
 285             parent[arg] = p;
 286             balance(arg, p);
 287
 288         // we take the place of a preexisting node
 289         } else {
 290             left[arg] = left[slot];   // steal slot's left subtree
 291             left[slot] = -1 * arg;
 292             right[arg] = slot;        // make slot our right subtree
 293             parent[arg] = parent[slot];
 294             parent[slot] = arg;
 295             if (slot == root) {
 296                 root = arg;
 297                 balance(slot, arg);
 298                 balance(arg, 0);
 299             } else {
 300                 if (left[p] == slot)        left[p] = arg;
 301                 else if (right[p] == slot)  right[p] = arg;
 302                 else throw new Error("should never happen");
 303                 balance(slot, arg);
 304                 balance(arg, p);
 305             }
 306         }
 307     }
 308
 309
 310     // Retrieval //////////////////////////////////////////////////////////////////////
 311
 312     private int get(int index, int slot) {
 313         int diff = index - sizeof(left[slot]);
 314         if (diff > 0) return get(diff - 1, right[slot]);
 315         else if (diff < 0) return get(index, left[slot]);
 316         else return slot;
 317     }
 318
 319
 320     // Deletion //////////////////////////////////////////////////////////////////////
 321
 322     private int delete(int index, int slot, int p) {
 323         int diff = index - sizeof(left[slot]);
 324         if (diff < 0) {
 325             int ret = delete(index, left[slot], slot);
 326             balance(slot, p);
 327             return ret;
 328
 329         } else if (diff > 0) {
 330             int ret = delete(diff - 1, right[slot], slot);
 331             balance(slot, p);
 332             return ret;
 333
 334         // we found the node to delete
 335         } else {
 336
 337             // fast path: it has no children
 338             if (left[slot] <= 0 && right[slot] <= 0) {
 339                 if (p == 0) root = 0;
 340                 else {
 341                     int[] side = left[p] == slot ? left : right;
 342                     side[p] = side[slot];      // fix parent's pointer
 343                 }
 344
 345             // fast path: it has no left child, so we replace it with its right child
 346             } else if (left[slot] <= 0) {
 347                 if (p == 0) root = right[slot];
 348                 else (left[p] == slot ? left : right)[p] = right[slot];     // fix parent's pointer
 349                 parent[right[slot]] = p;
 350                 left[leftmost(right[slot])] = left[slot];                             // fix our successor-leaf's fake right ptr
 351                 balance(right[slot], p);
 352
 353             // fast path; it has no right child, so we replace it with its left child
 354             } else if (right[slot] <= 0) {
 355                 if (p == 0) root = left[slot];
 356                 else (left[p] == slot ? left : right)[p] = left[slot];      // fix parent's pointer
 357                 parent[left[slot]] = p;
 358                 right[rightmost(left[slot])] = right[slot];                           // fix our successor-leaf's fake right ptr
 359                 balance(left[slot], p);
 360
 361             // node to be deleted has two children, so we replace it with its left child's rightmost descendant
 362             } else {
 363                 int left_childs_rightmost = delete(sizeof(left[slot]) - 1, left[slot], slot);
 364                 left[left_childs_rightmost] = left[slot];
 365                 right[left_childs_rightmost] = right[slot];
 366                 if(left[slot] > 0) parent[left[slot]] = left_childs_rightmost;
 367                 if(right[slot] > 0) parent[right[slot]] = left_childs_rightmost;
 368                 parent[left_childs_rightmost] = parent[slot];
 369                 if (p == 0) root = left_childs_rightmost;
 370                 else (left[p] == slot ? left : right)[p] = left_childs_rightmost;     // fix parent's pointer
 371                 balance(left_childs_rightmost, p);
 372             }
 373
 374             return slot;
 375         }
 376     }
 377
 378     // Debugging ///////////////////////////////////////////////////////////////////////////
 379
 380     public void printTree() {
 381         if(root == 0) System.err.println("Tree is empty");
 382         else printTree(root,0,false);
 383     }
 384     private void printTree(int node,int indent,boolean l) {
 385         for(int i=0;i<indent;i++) System.err.print("   ");
 386         if(node < 0) System.err.println((l?"Prev: " : "Next: ") + -node);
 387         else if(node == 0)  System.err.println(l ? "Start" : "End");
 388         else {
 389             System.err.print("" + node + ": " + objects[node]);
 390             System.err.println(" Parent: " + parent[node]);
 391             printTree(left[node],indent+1,true);
 392             printTree(right[node],indent+1,false);
 393         }
 394     }
 395 }