src/org/ibex/util/BalancedTree.java

   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.
   4
   5 package org.ibex.util;
   6
   7 // FEATURE: private void intersection() { }
   8 // FEATURE: private void union() { }
   9 // FEATURE: private void subset() { }
  10 // FEATURE: grow if we run out of slots
  11
  12 // FEATURE: Add the cached_index stuff back in
  13
  14 /** a weight-balanced tree with fake leaves */
  15 public class BalancedTree {
  16     private static final boolean DEBUG = true;
  17
  18     // Instance Variables ///////////////////////////////////////////////////////////////////
  19
  20     private int root = 0;                         ///< the slot of the root element
  21
  22     private int cached_index = -1;
  23     private int cached_slot = -1;
  24
  25     private FinalizationHelper fh;
  26
  27     // Public API //////////////////////////////////////////////////////////////////////////
  28
  29     /** the number of elements in the tree */
  30     public final int treeSize() {
  31         synchronized(BalancedTree.class) {
  32             return root == 0 ? 0 : size[root];
  33         }
  34     }
  35
  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);
  45         if (root != 0) {
  46             insert(index, arg, root, 0, false, false);
  47         } else {
  48             if(fh == null) fh = new FinalizationHelper(this);
  49             root = arg;
  50             left[arg] = right[arg] = parent[arg] = 0;
  51             size[arg] = 1;
  52         }
  53         if(DEBUG) check();
  54         if(DEBUG) leafCheck();
  55         }
  56     }
  57
  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);
  69         if(DEBUG) check();
  70         if(DEBUG) leafCheck();
  71         }
  72     }
  73
  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;
  79
  80         int slot = getSlot(o);
  81         if(slot == -1) return -1;
  82
  83         int index = 0;
  84         while(true) {
  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
  90             slot = parent[slot];
  91             // if we just processed the root we're done
  92             if(slot == 0) break;
  93             // count the node we're currently on towards the index
  94             index++;
  95         }
  96         return index;
  97         }
  98     }
  99
 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];
 105
 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
 110             // search directly.
 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];
 115             }
 116         }
 117         /*
 118         cached_index = index;
 119         cached_slot = get(index, root);
 120         return objects[cached_slot];
 121         */
 122         return objects[get(index, root)];
 123         }
 124     }
 125
 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];
 135         objects[del] = null;
 136         if(DEBUG) check();
 137         if(DEBUG) leafCheck();
 138         return ret;
 139         }
 140     }
 141
 142     public final void clear() {
 143         synchronized(BalancedTree.class) {
 144         if(root == 0) return;
 145         int i = leftmost(root);
 146         do {
 147             int next = next(i);
 148             objects[i] = null;
 149             left[i] = right[i] = size[i] = parent[i] = 0;
 150             i = next;
 151         } while(i != 0);
 152         root = 0;
 153         }
 154         if(DEBUG) check();
 155     }
 156
 157     // Node Data /////////////////////////////////////////////////////////////////////////
 158
 159     private final static int NUM_SLOTS = 64 * 1024;
 160     // FEATURE: GROW - private final static int MAX_SLOT_DISTANCE = 32;
 161
 162     /**
 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.
 169      */
 170     private static Object[] objects = new Object[NUM_SLOTS];
 171
 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.
 175     ///
 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.
 179     ///
 180     private static int[] left = new int[NUM_SLOTS];
 181     private static int[] right = new int[NUM_SLOTS];
 182
 183     /// The parent of this node (0 if it is the root node)
 184     private static int[] parent = new int[NUM_SLOTS];
 185
 186     ///< the number of descendants of this node *including the node itself*
 187     private static int[] size = new int[NUM_SLOTS];
 188
 189
 190     // Slot Management //////////////////////////////////////////////////////////////////////
 191
 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
 196         // trees
 197         int dest = Math.abs(o.hashCode() ^ this.hashCode()) % objects.length;
 198         Object search = alloc ? null : o;
 199         int odest = dest;
 200         boolean plus = true;
 201         int tries = 1;
 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;
 206             if (plus) tries++;
 207             plus = !plus;
 208             // FEATURE: GROW - if(tries > MAX_SLOT_DISTANCE) return -1;
 209         }
 210         return dest;
 211     }
 212
 213     /** returns the slots holding object o */
 214     private int getSlot(Object o) { return getSlot(o,false); }
 215
 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");
 220         objects[slot] = o;
 221         return slot;
 222     }
 223
 224
 225
 226     // Helpers /////////////////////////////////////////////////////////////////////////
 227
 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]); }
 233
 234     private int next(int node) {
 235         if(right[node] > 0) {
 236             node = right[node];
 237             while(left[node] > 0) node = left[node];
 238             return node;
 239         } else {
 240             int p = parent[node];
 241             while(right[p] == node) { node = p; p = parent[node]; };
 242             return p;
 243         }
 244     }
 245
 246     private int prev(int node) {
 247         if(left[node] > 0) {
 248             node = left[node];
 249             while(right[node] > 0) node = right[node];
 250             return node;
 251         } else {
 252             int p = parent[node];
 253             while(left[p] == node) { node = p; p = parent[node]; }
 254             return p;
 255         }
 256     }
 257
 258     // Rotation and Balancing /////////////////////////////////////////////////////////////
 259
 260     //      p                  p
 261     //      |                  |
 262     //      b                  d
 263     //     / \                / \
 264     //    a   d    < == >    b   e
 265     //       / \            / \
 266     //      c   e          a   c
 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;
 271         int d = right[b];
 272         int c = left[d];
 273         if (d == 0) throw new Error("rotation error");
 274         left[d] = b;
 275         right[b] = c;
 276
 277         parent[b] = d;
 278         parent[d] = p;
 279         if(c != 0) parent[c] = b;
 280
 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]);
 287     }
 288
 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);
 294     }
 295
 296
 297
 298     // Insert /////////////////////////////////////////////////////////////////////////
 299
 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);
 305             balance(slot, p);
 306             return;
 307         }
 308
 309         if (size[arg] != 0) throw new Error("double insertion");
 310
 311         if(DEBUG) check();
 312
 313         // we are replacing an existing node
 314         if (replace) {
 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;
 328             if(DEBUG) check();
 329
 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
 335             left[arg] = slot;
 336             right[arg] = 0;
 337             parent[arg] = p;
 338             left[p] = arg;
 339             balance(arg, p);
 340
 341         // we take the place of a preexisting node
 342         } else {
 343             if(DEBUG) check();
 344             left[arg] = left[slot];   // steal slot's left subtree
 345             left[slot] = 0;
 346             right[arg] = slot;        // make slot our right subtree
 347             parent[arg] = parent[slot];
 348             parent[slot] = arg;
 349             if(left[arg] != 0) parent[left[arg]] = arg;
 350             if (slot == root) {
 351                 root = arg;
 352                 balance(slot, arg);
 353                 balance(arg, 0);
 354             } else {
 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");
 358                 balance(slot, arg);
 359                 balance(arg, p);
 360             }
 361         }
 362     }
 363
 364
 365     // Retrieval //////////////////////////////////////////////////////////////////////
 366
 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]);
 371         else return slot;
 372     }
 373
 374
 375     // Deletion //////////////////////////////////////////////////////////////////////
 376
 377     private int delete(int index, int slot, int p) {
 378         int diff = index - sizeof(left[slot]);
 379         if (diff < 0) {
 380             int ret = delete(index, left[slot], slot);
 381             balance(slot, p);
 382             return ret;
 383
 384         } else if (diff > 0) {
 385             int ret = delete(diff - 1, right[slot], slot);
 386             balance(slot, p);
 387             return ret;
 388
 389         // we found the node to delete
 390         } else {
 391
 392             // fast path: it has no children
 393             if (left[slot] == 0 && right[slot] == 0) {
 394                 if (p == 0) root = 0;
 395                 else {
 396                     int[] side = left[p] == slot ? left : right;
 397                     side[p] = side[slot];      // fix parent's pointer
 398                 }
 399
 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);
 407
 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);
 415
 416             // node to be deleted has two children, so we replace it with its left child's rightmost descendant
 417             } else {
 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);
 427             }
 428
 429             return slot;
 430         }
 431     }
 432
 433     static class FinalizationHelper {
 434         private BalancedTree bt;
 435         FinalizationHelper(BalancedTree bt) { this.bt = bt; }
 436         protected void finalize() { bt.clear(); }
 437     }
 438
 439     // Debugging ///////////////////////////////////////////////////////////////////////////
 440
 441     public void check() { check(false); }
 442     public void check(boolean expensive) {
 443         if(expensive) System.err.println("--> Running expensive balanced tree checks");
 444         try {
 445             if(expensive)
 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]");
 451
 452             int c = 0;
 453             int n = leftmost(root);
 454             while(n != 0) { c++; n = next(n); }
 455             if(c != size[root]) throw new Error("size[] mismatch");
 456
 457             if(root != 0) check(root);
 458         } catch(Error e) {
 459             printTree();
 460             throw e;
 461         }
 462     }
 463
 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 + ")");
 467
 468         if(left[node] > 0) {
 469             if(parent[left[node]] != node) throw new Error("parent node mismatch on left child of " + node);
 470             check(left[node]);
 471         }
 472         if(right[node] > 0) {
 473             if(parent[right[node]] != node) throw new Error("parent node mismatch on right child of " + node);
 474             check(right[node]);
 475         }
 476     }
 477
 478     public void printTree() {
 479         if(root == 0) System.err.println("Tree is empty");
 480         else printTree(root,0,false);
 481     }
 482
 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");
 486         else {
 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);
 491         }
 492     }
 493
 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]);
 498         t.printTree();
 499         for(int n = t.leftmost(t.root); n != 0; n = t.next(n)) {
 500             System.err.println("Next: " + n);
 501         }
 502         for(int n = t.rightmost(t.root); n != 0; n = t.prev(n)) {
 503             System.err.println("Prev: " + n);
 504         }
 505     }
 506
 507     public void leafCheck() throws RuntimeException {
 508         if (!validateLeaves()) {
 509                 printLeaves();
 510                 printTree();
 511                 throw new RuntimeException("bad tree: forward != back");
 512         }
 513     }
 514
 515     public boolean validateLeaves() {
 516         int[] forward = getLeavesForward();
 517         int[] backward = getLeavesBackward();
 518         if (forward.length != backward.length) {
 519                 return false;
 520         }
 521         else if (forward.length > 0) {
 522                 for (int i = 0;i<forward.length;i++) {
 523                         if (forward[i] != backward[forward.length - i - 1]) {
 524                                 return false;
 525                         }
 526                 }
 527         }
 528         return true;
 529     }
 530
 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]);
 539                 }
 540         }
 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]);
 545                 }
 546         }
 547     }
 548
 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]);
 555                 }
 556         }
 557                 return leaves;
 558     }
 559
 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]);
 566                 }
 567         }
 568         return leaves;
 569     }
 570
 571     public void validateTree() {
 572         if(root == 0) System.err.println("Tree is empty");
 573         else validateTree(root,0,false);
 574         System.err.println("");
 575     }
 576     private void validateTree(int node,int indent,boolean l) {
 577         if(node < 0) {}
 578         else if(node == 0)  {}
 579         else {
 580                 System.err.println((l?"Prev: " : "Next: ") + -node);
 581             validateTree(left[node],indent+1,true);
 582             validateTree(right[node],indent+1,false);
 583         }
 584     }
 585
 586 }