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 // FEATURE: Add the cached_index stuff back in
  16
  17 /** a weight-balanced tree with fake leaves */
  18 public class BalancedTree {
  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() {
  30         synchronized(BalancedTree.class) {
  31             return root == 0 ? 0 : size[root];
  32         }
  33     }
  34
  35     /** clamps index to [0..treeSize()] and inserts object o *before* the specified index */
  36     public final void insertNode(int index, Object o) {
  37         synchronized(BalancedTree.class) {
  38         if(o == null) throw new Error("can't insert nulls in the balanced tree");
  39         cached_slot = cached_index = -1;
  40         if (index < 0) index = 0;
  41         if (index > treeSize()) index = treeSize();
  42         int arg = allocateSlot(o);
  43         if (root != 0) {
  44             insert(index, arg, root, 0, false, false);
  45         } else {
  46             root = arg;
  47             left[arg] = right[arg] = parent[arg] = 0;
  48             size[arg] = 1;
  49         }
  50         }
  51     }
  52
  53     /** clamps index to [0..treeSize()-1] and replaces the object at that index with object o */
  54     public final void replaceNode(int index, Object o) {
  55         synchronized(BalancedTree.class) {
  56         if(o == null) throw new Error("can't insert nulls in the balanced tree");
  57         cached_slot = cached_index = -1;
  58         if(root == 0) throw new Error("called replaceNode() on an empty tree");
  59         if (index < 0) index = 0;
  60         if (index >= treeSize()) index = treeSize() - 1;
  61         int arg = allocateSlot(o);
  62         insert(index, arg, root, 0, true, false);
  63         }
  64     }
  65
  66     /** returns the index of o; runs in O((log n)^2) time unless cache hit */
  67     public final int indexNode(Object o) {
  68         synchronized(BalancedTree.class) {
  69         if(o == null) return -1;
  70         if (cached_slot != -1 && objects[cached_slot] == o) return cached_index;
  71
  72         int slot = getSlot(o);
  73         if(slot == -1) return -1;
  74
  75         int index = 0;
  76         while(true) {
  77             // everything to the left is before us so add that to the index
  78             index += sizeof(left[slot]);
  79             // we are before anything on the right
  80             while(left[parent[slot]] == slot) slot = parent[slot];
  81             // we end of the first node who isn't on the left, go to the node that has as its child
  82             slot = parent[slot];
  83             // if we just processed the root we're done
  84             if(slot == 0) break;
  85             // count the node we're currently on towards the index
  86             index++;
  87         }
  88         return index;
  89         }
  90     }
  91
  92     /** returns the object at index; runs in O(log n) time unless cache hit */
  93     public final Object getNode(int index) {
  94         synchronized(BalancedTree.class) {
  95         if (index == cached_index) return objects[cached_slot];
  96
  97         if (cached_index != -1) {
  98             int distance = Math.abs(index - cached_index);
  99             // if the in-order distance between the cached node and the
 100             // target node is less than log(n), it's probably faster to
 101             // search directly.
 102             if ((distance < 16) && ((2 << distance) < treeSize())) {
 103                 while(cached_index > index) { cached_slot = prev(cached_slot); cached_index--; }
 104                 while(cached_index < index) { cached_slot = next(cached_slot); cached_index++; }
 105                 return objects[cached_slot];
 106             }
 107         }
 108         /*
 109         cached_index = index;
 110         cached_slot = get(index, root);
 111         return objects[cached_slot];
 112         */
 113         return objects[get(index, root)];
 114         }
 115     }
 116
 117     /** deletes the object at index, returning the deleted object */
 118     public final Object deleteNode(int index) {
 119         synchronized(BalancedTree.class) {
 120         cached_slot = cached_index = -1;
 121         // FIXME: left[], right[], size[], and parent[] aren't getting cleared properly somewhere in here where a node had two children
 122         int del = delete(index, root, 0);
 123         left[del] = right[del] = size[del] = parent[del] = 0;
 124         Object ret = objects[del];
 125         objects[del] = null;
 126         return ret;
 127         }
 128     }
 129
 130     public final void clear() {
 131         synchronized(BalancedTree.class) {
 132         if(root == 0) return;
 133         int i = leftmost(root);
 134         do {
 135             int next = next(i);
 136             objects[i] = null;
 137             left[i] = right[i] = size[i] = parent[i] = 0;
 138             i = next;
 139         } while(i != 0);
 140         root = 0;
 141         }
 142     }
 143
 144     // Node Data /////////////////////////////////////////////////////////////////////////
 145
 146     private final static int NUM_SLOTS = 64 * 1024;
 147     // FEATURE: GROW - private final static int MAX_SLOT_DISTANCE = 32;
 148
 149     /**
 150      * Every object inserted into *any* tree gets a "slot" in this
 151      * array.  The slot is determined by hashcode modulo the length of
 152      * the array, with quadradic probing to resolve collisions.  NOTE
 153      * that the "slot" of a node is NOT the same as its index.
 154      * Furthermore, if an object is inserted into multiple trees, that
 155      * object will have multiple slots.
 156      */
 157     private static Object[] objects = new Object[NUM_SLOTS];
 158
 159     /// These two arrays hold the left and right children of each
 160     /// slot; in other words, left[x] is the *slot* of the left child
 161     /// of the node in slot x.
 162     ///
 163     /// If x has no left child, then left[x] is -1 multiplied by the
 164     /// slot of the node that precedes x; if x is the first node, then
 165     /// left[x] is 0.  The right[] array works the same way.
 166     ///
 167     private static int[] left = new int[NUM_SLOTS];
 168     private static int[] right = new int[NUM_SLOTS];
 169
 170     /// The parent of this node (0 if it is the root node)
 171     private static int[] parent = new int[NUM_SLOTS];
 172
 173     ///< the number of descendants of this node *including the node itself*
 174     private static int[] size = new int[NUM_SLOTS];
 175
 176
 177     // Slot Management //////////////////////////////////////////////////////////////////////
 178
 179     /** if alloc == false returns the slot holding object o. if alloc is true returns a new slot for obejct o */
 180     private int getSlot(Object o, boolean alloc) {
 181         // we XOR with our own hashcode so that we don't get tons of
 182         // collisions when a single Object is inserted into multiple
 183         // trees
 184         int dest = Math.abs(o.hashCode() ^ this.hashCode()) % objects.length;
 185         Object search = alloc ? null : o;
 186         int odest = dest;
 187         boolean plus = true;
 188         int tries = 1;
 189         if(dest == 0) dest=1;
 190         while (objects[dest] != search || !(alloc || root(dest) == root)) {
 191             dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % objects.length);
 192             if (dest == 0) dest=1;
 193             if (plus) tries++;
 194             plus = !plus;
 195             // FEATURE: GROW - if(tries > MAX_SLOT_DISTANCE) return -1;
 196         }
 197         return dest;
 198     }
 199
 200     /** returns the slots holding object o */
 201     private int getSlot(Object o) { return getSlot(o,false); }
 202
 203     /** allocates a new slot holding object o*/
 204     private int allocateSlot(Object o) {
 205         int slot = getSlot(o, true);
 206         // FEATURE: GROW - if(slot == -1) throw new Error("out of slots");
 207         objects[slot] = o;
 208         return slot;
 209     }
 210
 211
 212
 213     // Helpers /////////////////////////////////////////////////////////////////////////
 214
 215     // FEATURE: These might be faster if they aren't recursive
 216     private final int leftmost(int slot) { return left[slot] <= 0 ? slot : leftmost(left[slot]); }
 217     private final int rightmost(int slot) { return right[slot] <= 0 ? slot : rightmost(right[slot]); }
 218     private final int sizeof(int slot) { return slot <= 0 ? 0 : size[slot]; }
 219     private final int root(int slot) { return parent[slot] == 0 ? slot : root(parent[slot]); }
 220
 221     private int next(int node) {
 222         if(right[node] > 0) {
 223             node = right[node];
 224             while(left[node] > 0) node = left[node];
 225             return node;
 226         } else {
 227             int p = parent[node];
 228             while(right[p] == node) { node = p; p = parent[node]; };
 229             return p;
 230         }
 231     }
 232
 233     private int prev(int node) {
 234         if(left[node] > 0) {
 235             node = left[node];
 236             while(right[node] > 0) node = right[node];
 237             return node;
 238         } else {
 239             int p = parent[node];
 240             while(left[p] == node) { node = p; p = parent[node]; }
 241             return p;
 242         }
 243     }
 244
 245     // Rotation and Balancing /////////////////////////////////////////////////////////////
 246
 247     //      p                  p
 248     //      |                  |
 249     //      b                  d
 250     //     / \                / \
 251     //    a   d    < == >    b   e
 252     //       / \            / \
 253     //      c   e          a   c
 254     // FIXME might be doing too much work here
 255     private void rotate(boolean toTheLeft, int b, int p) {
 256         int[] left = toTheLeft ? BalancedTree.left : BalancedTree.right;
 257         int[] right = toTheLeft ? BalancedTree.right : BalancedTree.left;
 258         int d = right[b];
 259         int c = left[d];
 260         if (d == 0) throw new Error("rotation error");
 261         left[d] = b;
 262         right[b] = c;
 263
 264         parent[b] = d;
 265         parent[d] = p;
 266         if(c != 0) parent[c] = b;
 267
 268         if (p == 0)              root = d;
 269         else if (left[p] == b)   left[p] = d;
 270         else if (right[p] == b)  right[p] = d;
 271         else throw new Error("rotate called with invalid parent");
 272         size[b] = 1 + sizeof(left[b]) + sizeof(right[b]);
 273         size[d] = 1 + sizeof(left[d]) + sizeof(right[d]);
 274     }
 275
 276     private void balance(int slot, int p) {
 277         if (slot <= 0) return;
 278         size[slot] = 1 + sizeof(left[slot]) + sizeof(right[slot]);
 279         if (sizeof(left[slot]) - 1 > 2 * sizeof(right[slot])) rotate(false, slot, p);
 280         else if (sizeof(left[slot]) * 2 < sizeof(right[slot]) - 1) rotate(true, slot, p);
 281     }
 282
 283
 284
 285     // Insert /////////////////////////////////////////////////////////////////////////
 286
 287     private void insert(int index, int arg, int slot, int p, boolean replace, boolean wentLeft) {
 288         int diff = slot == 0 ? 0 : index - sizeof(left[slot]);
 289         if (slot != 0 && diff != 0) {
 290             if (diff < 0) insert(index, arg, left[slot], slot, replace, true);
 291             else insert(index - sizeof(left[slot]) - 1, arg, right[slot], slot, replace, false);
 292             balance(slot, p);
 293             return;
 294         }
 295
 296         if (size[arg] != 0) throw new Error("double insertion");
 297
 298         // we are replacing an existing node
 299         if (replace) {
 300             if (diff != 0) throw new Error("this should never happen"); // since we already clamped the index
 301             if (p == 0)                 root = arg;
 302             else if (left[p] == slot)   left[p] = arg;
 303             else if (right[p] == slot)  right[p] = arg;
 304             else throw new Error("should never happen");
 305             left[arg] = left[slot];
 306             right[arg] = right[slot];
 307             size[arg] = size[slot];
 308             parent[arg] = parent[slot];
 309             if(left[slot] != 0) parent[left[slot]] = arg;
 310             if(right[slot] != 0) parent[right[slot]] = arg;
 311             objects[slot] = null;
 312             left[slot] = right[slot] = size[slot] = parent[slot] = 0;
 313
 314         // we become the child of a former leaf
 315         } else if (slot == 0) {
 316             int[] left = wentLeft ? BalancedTree.left : BalancedTree.right;
 317             int[] right = wentLeft ? BalancedTree.right : BalancedTree.left;
 318             // FEATURE: Might be doing too much work here
 319             left[arg] = slot;
 320             right[arg] = 0;
 321             parent[arg] = p;
 322             left[p] = arg;
 323             balance(arg, p);
 324
 325         // we take the place of a preexisting node
 326         } else {
 327             left[arg] = left[slot];   // steal slot's left subtree
 328             left[slot] = 0;
 329             right[arg] = slot;        // make slot our right subtree
 330             parent[arg] = parent[slot];
 331             parent[slot] = arg;
 332             if(left[arg] != 0) parent[left[arg]] = arg;
 333             if (slot == root) {
 334                 root = arg;
 335                 balance(slot, arg);
 336                 balance(arg, 0);
 337             } else {
 338                 if (left[p] == slot)        left[p] = arg;
 339                 else if (right[p] == slot)  right[p] = arg;
 340                 else throw new Error("should never happen");
 341                 balance(slot, arg);
 342                 balance(arg, p);
 343             }
 344         }
 345     }
 346
 347
 348     // Retrieval //////////////////////////////////////////////////////////////////////
 349
 350     private int get(int index, int slot) {
 351         int diff = index - sizeof(left[slot]);
 352         if (diff > 0) return get(diff - 1, right[slot]);
 353         else if (diff < 0) return get(index, left[slot]);
 354         else return slot;
 355     }
 356
 357
 358     // Deletion //////////////////////////////////////////////////////////////////////
 359
 360     private int delete(int index, int slot, int p) {
 361         int diff = index - sizeof(left[slot]);
 362         if (diff < 0) {
 363             int ret = delete(index, left[slot], slot);
 364             balance(slot, p);
 365             return ret;
 366
 367         } else if (diff > 0) {
 368             int ret = delete(diff - 1, right[slot], slot);
 369             balance(slot, p);
 370             return ret;
 371
 372         // we found the node to delete
 373         } else {
 374
 375             // fast path: it has no children
 376             if (left[slot] == 0 && right[slot] == 0) {
 377                 if (p == 0) root = 0;
 378                 else {
 379                     int[] side = left[p] == slot ? left : right;
 380                     side[p] = side[slot];      // fix parent's pointer
 381                 }
 382
 383             // fast path: it has no left child, so we replace it with its right child
 384             } else if (left[slot] == 0) {
 385                 if (p == 0) root = right[slot];
 386                 else (left[p] == slot ? left : right)[p] = right[slot];     // fix parent's pointer
 387                 parent[right[slot]] = p;
 388                 left[leftmost(right[slot])] = left[slot];                             // fix our successor-leaf's fake right ptr
 389                 balance(right[slot], p);
 390
 391             // fast path; it has no right child, so we replace it with its left child
 392             } else if (right[slot] == 0) {
 393                 if (p == 0) root = left[slot];
 394                 else (left[p] == slot ? left : right)[p] = left[slot];      // fix parent's pointer
 395                 parent[left[slot]] = p;
 396                 right[rightmost(left[slot])] = right[slot];                           // fix our successor-leaf's fake right ptr
 397                 balance(left[slot], p);
 398
 399             // node to be deleted has two children, so we replace it with its left child's rightmost descendant
 400             } else {
 401                 int left_childs_rightmost = delete(sizeof(left[slot]) - 1, left[slot], slot);
 402                 left[left_childs_rightmost] = left[slot];
 403                 right[left_childs_rightmost] = right[slot];
 404                 if(left[slot] != 0) parent[left[slot]] = left_childs_rightmost;
 405                 if(right[slot] != 0) parent[right[slot]] = left_childs_rightmost;
 406                 parent[left_childs_rightmost] = parent[slot];
 407                 if (p == 0) root = left_childs_rightmost;
 408                 else (left[p] == slot ? left : right)[p] = left_childs_rightmost;     // fix parent's pointer
 409                 balance(left_childs_rightmost, p);
 410             }
 411
 412             return slot;
 413         }
 414     }
 415
 416     protected void finalize() { clear(); }
 417
 418     public void printTree() {
 419         if(root == 0) System.err.println("Tree is empty");
 420         else printTree(root,0,false);
 421     }
 422
 423     private void printTree(int node,int indent,boolean l) {
 424         for(int i=0;i<indent;i++) System.err.print("   ");
 425         if(node == 0) System.err.println("None");
 426         else {
 427             System.err.print("" + node + ": " + objects[node]);
 428             System.err.println(" Parent: " + parent[node] + " Size: " + size[node]);
 429             printTree(left[node],indent+1,true);
 430             printTree(right[node],indent+1,false);
 431         }
 432     }
 433 }