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     private static final boolean DEBUG = true;
  20
  21     // Instance Variables ///////////////////////////////////////////////////////////////////
  22
  23     private int root = 0;                         ///< the slot of the root element
  24
  25     private int cached_index = -1;
  26     private int cached_slot = -1;
  27
  28     private FinalizationHelper fh;
  29
  30     // Public API //////////////////////////////////////////////////////////////////////////
  31
  32     /** the number of elements in the tree */
  33     public final int treeSize() {
  34         synchronized(BalancedTree.class) {
  35             return root == 0 ? 0 : size[root];
  36         }
  37     }
  38
  39     /** clamps index to [0..treeSize()] and inserts object o *before* the specified index */
  40     public final void insertNode(int index, Object o) {
  41         synchronized(BalancedTree.class) {
  42         if(DEBUG) leafCheck();
  43         if(o == null) throw new Error("can't insert nulls in the balanced tree");
  44         cached_slot = cached_index = -1;
  45         if (index < 0) index = 0;
  46         if (index > treeSize()) index = treeSize();
  47         int arg = allocateSlot(o);
  48         if (root != 0) {
  49             insert(index, arg, root, 0, false, false);
  50         } else {
  51             if(fh == null) fh = new FinalizationHelper(this);
  52             root = arg;
  53             left[arg] = right[arg] = parent[arg] = 0;
  54             size[arg] = 1;
  55         }
  56         if(DEBUG) check();
  57         if(DEBUG) leafCheck();
  58         }
  59     }
  60
  61     /** clamps index to [0..treeSize()-1] and replaces the object at that index with object o */
  62     public final void replaceNode(int index, Object o) {
  63         synchronized(BalancedTree.class) {
  64         if(DEBUG) leafCheck();
  65         if(o == null) throw new Error("can't insert nulls in the balanced tree");
  66         cached_slot = cached_index = -1;
  67         if(root == 0) throw new Error("called replaceNode() on an empty tree");
  68         if (index < 0) index = 0;
  69         if (index >= treeSize()) index = treeSize() - 1;
  70         int arg = allocateSlot(o);
  71         insert(index, arg, root, 0, true, false);
  72         if(DEBUG) check();
  73         if(DEBUG) leafCheck();
  74         }
  75     }
  76
  77     /** returns the index of o; runs in O((log n)^2) time unless cache hit */
  78     public final int indexNode(Object o) {
  79         synchronized(BalancedTree.class) {
  80         if(o == null) return -1;
  81         if (cached_slot != -1 && objects[cached_slot] == o) return cached_index;
  82
  83         int slot = getSlot(o);
  84         if(slot == -1) return -1;
  85
  86         int index = 0;
  87         while(true) {
  88             // everything to the left is before us so add that to the index
  89             index += sizeof(left[slot]);
  90             // we are before anything on the right
  91             while(left[parent[slot]] == slot) slot = parent[slot];
  92             // we end of the first node who isn't on the left, go to the node that has as its child
  93             slot = parent[slot];
  94             // if we just processed the root we're done
  95             if(slot == 0) break;
  96             // count the node we're currently on towards the index
  97             index++;
  98         }
  99         return index;
 100         }
 101     }
 102
 103     /** returns the object at index; runs in O(log n) time unless cache hit */
 104     public final Object getNode(int index) {
 105         synchronized(BalancedTree.class) {
 106         if(DEBUG) leafCheck();
 107         if (index == cached_index) return objects[cached_slot];
 108
 109         if (cached_index != -1) {
 110             int distance = Math.abs(index - cached_index);
 111             // if the in-order distance between the cached node and the
 112             // target node is less than log(n), it's probably faster to
 113             // search directly.
 114             if ((distance < 16) && ((2 << distance) < treeSize())) {
 115                 while(cached_index > index) { cached_slot = prev(cached_slot); cached_index--; }
 116                 while(cached_index < index) { cached_slot = next(cached_slot); cached_index++; }
 117                 return objects[cached_slot];
 118             }
 119         }
 120         /*
 121         cached_index = index;
 122         cached_slot = get(index, root);
 123         return objects[cached_slot];
 124         */
 125         return objects[get(index, root)];
 126         }
 127     }
 128
 129     /** deletes the object at index, returning the deleted object */
 130     public final Object deleteNode(int index) {
 131         synchronized(BalancedTree.class) {
 132         if(DEBUG) leafCheck();
 133         cached_slot = cached_index = -1;
 134         // FIXME: left[], right[], size[], and parent[] aren't getting cleared properly somewhere in here where a node had two children
 135         int del = delete(index, root, 0);
 136         left[del] = right[del] = size[del] = parent[del] = 0;
 137         Object ret = objects[del];
 138         objects[del] = null;
 139         if(DEBUG) check();
 140         if(DEBUG) leafCheck();
 141         return ret;
 142         }
 143     }
 144
 145     public final void clear() {
 146         synchronized(BalancedTree.class) {
 147         if(root == 0) return;
 148         int i = leftmost(root);
 149         do {
 150             int next = next(i);
 151             objects[i] = null;
 152             left[i] = right[i] = size[i] = parent[i] = 0;
 153             i = next;
 154         } while(i != 0);
 155         root = 0;
 156         }
 157         if(DEBUG) check();
 158     }
 159
 160     // Node Data /////////////////////////////////////////////////////////////////////////
 161
 162     private final static int NUM_SLOTS = 64 * 1024;
 163     // FEATURE: GROW - private final static int MAX_SLOT_DISTANCE = 32;
 164
 165     /**
 166      * Every object inserted into *any* tree gets a "slot" in this
 167      * array.  The slot is determined by hashcode modulo the length of
 168      * the array, with quadradic probing to resolve collisions.  NOTE
 169      * that the "slot" of a node is NOT the same as its index.
 170      * Furthermore, if an object is inserted into multiple trees, that
 171      * object will have multiple slots.
 172      */
 173     private static Object[] objects = new Object[NUM_SLOTS];
 174
 175     /// These two arrays hold the left and right children of each
 176     /// slot; in other words, left[x] is the *slot* of the left child
 177     /// of the node in slot x.
 178     ///
 179     /// If x has no left child, then left[x] is -1 multiplied by the
 180     /// slot of the node that precedes x; if x is the first node, then
 181     /// left[x] is 0.  The right[] array works the same way.
 182     ///
 183     private static int[] left = new int[NUM_SLOTS];
 184     private static int[] right = new int[NUM_SLOTS];
 185
 186     /// The parent of this node (0 if it is the root node)
 187     private static int[] parent = new int[NUM_SLOTS];
 188
 189     ///< the number of descendants of this node *including the node itself*
 190     private static int[] size = new int[NUM_SLOTS];
 191
 192
 193     // Slot Management //////////////////////////////////////////////////////////////////////
 194
 195     /** if alloc == false returns the slot holding object o. if alloc is true returns a new slot for obejct o */
 196     private int getSlot(Object o, boolean alloc) {
 197         // we XOR with our own hashcode so that we don't get tons of
 198         // collisions when a single Object is inserted into multiple
 199         // trees
 200         int dest = Math.abs(o.hashCode() ^ this.hashCode()) % objects.length;
 201         Object search = alloc ? null : o;
 202         int odest = dest;
 203         boolean plus = true;
 204         int tries = 1;
 205         if(dest == 0) dest=1;
 206         while (objects[dest] != search || !(alloc || root(dest) == root)) {
 207             dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % objects.length);
 208             if (dest == 0) dest=1;
 209             if (plus) tries++;
 210             plus = !plus;
 211             // FEATURE: GROW - if(tries > MAX_SLOT_DISTANCE) return -1;
 212         }
 213         return dest;
 214     }
 215
 216     /** returns the slots holding object o */
 217     private int getSlot(Object o) { return getSlot(o,false); }
 218
 219     /** allocates a new slot holding object o*/
 220     private int allocateSlot(Object o) {
 221         int slot = getSlot(o, true);
 222         // FEATURE: GROW - if(slot == -1) throw new Error("out of slots");
 223         objects[slot] = o;
 224         return slot;
 225     }
 226
 227
 228
 229     // Helpers /////////////////////////////////////////////////////////////////////////
 230
 231     // FEATURE: These might be faster if they aren't recursive
 232     private final int leftmost(int slot) { return left[slot] <= 0 ? slot : leftmost(left[slot]); }
 233     private final int rightmost(int slot) { return right[slot] <= 0 ? slot : rightmost(right[slot]); }
 234     private final int sizeof(int slot) { return slot <= 0 ? 0 : size[slot]; }
 235     private final int root(int slot) { return parent[slot] == 0 ? slot : root(parent[slot]); }
 236
 237     private int next(int node) {
 238         if(right[node] > 0) {
 239             node = right[node];
 240             while(left[node] > 0) node = left[node];
 241             return node;
 242         } else {
 243             int p = parent[node];
 244             while(right[p] == node) { node = p; p = parent[node]; };
 245             return p;
 246         }
 247     }
 248
 249     private int prev(int node) {
 250         if(left[node] > 0) {
 251             node = left[node];
 252             while(right[node] > 0) node = right[node];
 253             return node;
 254         } else {
 255             int p = parent[node];
 256             while(left[p] == node) { node = p; p = parent[node]; }
 257             return p;
 258         }
 259     }
 260
 261     // Rotation and Balancing /////////////////////////////////////////////////////////////
 262
 263     //      p                  p
 264     //      |                  |
 265     //      b                  d
 266     //     / \                / \
 267     //    a   d    < == >    b   e
 268     //       / \            / \
 269     //      c   e          a   c
 270     // FIXME might be doing too much work here
 271     private void rotate(boolean toTheLeft, int b, int p) {
 272         int[] left = toTheLeft ? BalancedTree.left : BalancedTree.right;
 273         int[] right = toTheLeft ? BalancedTree.right : BalancedTree.left;
 274         int d = right[b];
 275         int c = left[d];
 276         if (d == 0) throw new Error("rotation error");
 277         left[d] = b;
 278         right[b] = c;
 279
 280         parent[b] = d;
 281         parent[d] = p;
 282         if(c != 0) parent[c] = b;
 283
 284         if (p == 0)              root = d;
 285         else if (left[p] == b)   left[p] = d;
 286         else if (right[p] == b)  right[p] = d;
 287         else throw new Error("rotate called with invalid parent");
 288         size[b] = 1 + sizeof(left[b]) + sizeof(right[b]);
 289         size[d] = 1 + sizeof(left[d]) + sizeof(right[d]);
 290     }
 291
 292     private void balance(int slot, int p) {
 293         if (slot <= 0) return;
 294         size[slot] = 1 + sizeof(left[slot]) + sizeof(right[slot]);
 295         if (sizeof(left[slot]) - 1 > 2 * sizeof(right[slot])) rotate(false, slot, p);
 296         else if (sizeof(left[slot]) * 2 < sizeof(right[slot]) - 1) rotate(true, slot, p);
 297     }
 298
 299
 300
 301     // Insert /////////////////////////////////////////////////////////////////////////
 302
 303     private void insert(int index, int arg, int slot, int p, boolean replace, boolean wentLeft) {
 304         int diff = slot == 0 ? 0 : index - sizeof(left[slot]);
 305         if (slot != 0 && diff != 0) {
 306             if (diff < 0) insert(index, arg, left[slot], slot, replace, true);
 307             else insert(index - sizeof(left[slot]) - 1, arg, right[slot], slot, replace, false);
 308             balance(slot, p);
 309             return;
 310         }
 311
 312         if (size[arg] != 0) throw new Error("double insertion");
 313
 314         if(DEBUG) check();
 315
 316         // we are replacing an existing node
 317         if (replace) {
 318             if (diff != 0) throw new Error("this should never happen"); // since we already clamped the index
 319             if (p == 0)                 root = arg;
 320             else if (left[p] == slot)   left[p] = arg;
 321             else if (right[p] == slot)  right[p] = arg;
 322             else throw new Error("should never happen");
 323             left[arg] = left[slot];
 324             right[arg] = right[slot];
 325             size[arg] = size[slot];
 326             parent[arg] = parent[slot];
 327             if(left[slot] != 0) parent[left[slot]] = arg;
 328             if(right[slot] != 0) parent[right[slot]] = arg;
 329             objects[slot] = null;
 330             left[slot] = right[slot] = size[slot] = parent[slot] = 0;
 331             if(DEBUG) check();
 332
 333         // we become the child of a former leaf
 334         } else if (slot == 0) {
 335             int[] left = wentLeft ? BalancedTree.left : BalancedTree.right;
 336             int[] right = wentLeft ? BalancedTree.right : BalancedTree.left;
 337             // FEATURE: Might be doing too much work here
 338             left[arg] = slot;
 339             right[arg] = 0;
 340             parent[arg] = p;
 341             left[p] = arg;
 342             balance(arg, p);
 343
 344         // we take the place of a preexisting node
 345         } else {
 346             if(DEBUG) check();
 347             left[arg] = left[slot];   // steal slot's left subtree
 348             left[slot] = 0;
 349             right[arg] = slot;        // make slot our right subtree
 350             parent[arg] = parent[slot];
 351             parent[slot] = arg;
 352             if(left[arg] != 0) parent[left[arg]] = arg;
 353             if (slot == root) {
 354                 root = arg;
 355                 balance(slot, arg);
 356                 balance(arg, 0);
 357             } else {
 358                 if (left[p] == slot)        left[p] = arg;
 359                 else if (right[p] == slot)  right[p] = arg;
 360                 else throw new Error("should never happen");
 361                 balance(slot, arg);
 362                 balance(arg, p);
 363             }
 364         }
 365     }
 366
 367
 368     // Retrieval //////////////////////////////////////////////////////////////////////
 369
 370     private int get(int index, int slot) {
 371         int diff = index - sizeof(left[slot]);
 372         if (diff > 0) return get(diff - 1, right[slot]);
 373         else if (diff < 0) return get(index, left[slot]);
 374         else return slot;
 375     }
 376
 377
 378     // Deletion //////////////////////////////////////////////////////////////////////
 379
 380     private int delete(int index, int slot, int p) {
 381         int diff = index - sizeof(left[slot]);
 382         if (diff < 0) {
 383             int ret = delete(index, left[slot], slot);
 384             balance(slot, p);
 385             return ret;
 386
 387         } else if (diff > 0) {
 388             int ret = delete(diff - 1, right[slot], slot);
 389             balance(slot, p);
 390             return ret;
 391
 392         // we found the node to delete
 393         } else {
 394
 395             // fast path: it has no children
 396             if (left[slot] == 0 && right[slot] == 0) {
 397                 if (p == 0) root = 0;
 398                 else {
 399                     int[] side = left[p] == slot ? left : right;
 400                     side[p] = side[slot];      // fix parent's pointer
 401                 }
 402
 403             // fast path: it has no left child, so we replace it with its right child
 404             } else if (left[slot] == 0) {
 405                 if (p == 0) root = right[slot];
 406                 else (left[p] == slot ? left : right)[p] = right[slot];     // fix parent's pointer
 407                 parent[right[slot]] = p;
 408                 left[leftmost(right[slot])] = left[slot];                             // fix our successor-leaf's fake right ptr
 409                 balance(right[slot], p);
 410
 411             // fast path; it has no right child, so we replace it with its left child
 412             } else if (right[slot] == 0) {
 413                 if (p == 0) root = left[slot];
 414                 else (left[p] == slot ? left : right)[p] = left[slot];      // fix parent's pointer
 415                 parent[left[slot]] = p;
 416                 right[rightmost(left[slot])] = right[slot];                           // fix our successor-leaf's fake right ptr
 417                 balance(left[slot], p);
 418
 419             // node to be deleted has two children, so we replace it with its left child's rightmost descendant
 420             } else {
 421                 int left_childs_rightmost = delete(sizeof(left[slot]) - 1, left[slot], slot);
 422                 left[left_childs_rightmost] = left[slot];
 423                 right[left_childs_rightmost] = right[slot];
 424                 if(left[slot] != 0) parent[left[slot]] = left_childs_rightmost;
 425                 if(right[slot] != 0) parent[right[slot]] = left_childs_rightmost;
 426                 parent[left_childs_rightmost] = parent[slot];
 427                 if (p == 0) root = left_childs_rightmost;
 428                 else (left[p] == slot ? left : right)[p] = left_childs_rightmost;     // fix parent's pointer
 429                 balance(left_childs_rightmost, p);
 430             }
 431
 432             return slot;
 433         }
 434     }
 435
 436     static class FinalizationHelper {
 437         private BalancedTree bt;
 438         FinalizationHelper(BalancedTree bt) { this.bt = bt; }
 439         protected void finalize() { bt.clear(); }
 440     }
 441
 442     // Debugging ///////////////////////////////////////////////////////////////////////////
 443
 444     public void check() { check(false); }
 445     public void check(boolean expensive) {
 446         if(expensive) System.err.println("--> Running expensive balanced tree checks");
 447         try {
 448             if(expensive)
 449                 for(int i=0;i<NUM_SLOTS;i++)
 450                     if(left[i] < 0 || right[i] < 0) throw new Error("someone inserted a negative number");
 451             if(parent[root] != 0) throw new Error("parent of the root isn't 0");
 452             if(left[0] != 0 || right[0] != 0 || size[0] != 0 || parent[0] != 0)
 453                 throw new Error("someone messed with [0]");
 454
 455             int c = 0;
 456             int n = leftmost(root);
 457             while(n != 0) { c++; n = next(n); }
 458             if(c != size[root]) throw new Error("size[] mismatch");
 459
 460             if(root != 0) check(root);
 461         } catch(Error e) {
 462             printTree();
 463             throw e;
 464         }
 465     }
 466
 467     private void check(int node) {
 468         //if(next(node) != next2(node)) throw new Error("next(" + node + ") != next2(" + node + ")");
 469         //if(prev(node) != prev2(node)) throw new Error("prev(" + node + ") != prev2(" + node + ")");
 470
 471         if(left[node] > 0) {
 472             if(parent[left[node]] != node) throw new Error("parent node mismatch on left child of " + node);
 473             check(left[node]);
 474         }
 475         if(right[node] > 0) {
 476             if(parent[right[node]] != node) throw new Error("parent node mismatch on right child of " + node);
 477             check(right[node]);
 478         }
 479     }
 480
 481     public void printTree() {
 482         if(root == 0) System.err.println("Tree is empty");
 483         else printTree(root,0,false);
 484     }
 485
 486     private void printTree(int node,int indent,boolean l) {
 487         for(int i=0;i<indent;i++) System.err.print("   ");
 488         if(node == 0) System.err.println("None");
 489         else {
 490             System.err.print("" + node + ": " + objects[node]);
 491             System.err.println(" Parent: " + parent[node] + " Size: " + size[node]);
 492             printTree(left[node],indent+1,true);
 493             printTree(right[node],indent+1,false);
 494         }
 495     }
 496
 497     public static void main(String[] args) {
 498         BalancedTree t = new BalancedTree();
 499         for(int i=0;i<args.length;i++)
 500             t.insertNode(i,args[i]);
 501         t.printTree();
 502         for(int n = t.leftmost(t.root); n != 0; n = t.next(n)) {
 503             System.err.println("Next: " + n);
 504         }
 505         for(int n = t.rightmost(t.root); n != 0; n = t.prev(n)) {
 506             System.err.println("Prev: " + n);
 507         }
 508     }
 509
 510     public void leafCheck() throws RuntimeException {
 511         if (!validateLeaves()) {
 512                 printLeaves();
 513                 printTree();
 514                 throw new RuntimeException("bad tree: forward != back");
 515         }
 516     }
 517
 518     public boolean validateLeaves() {
 519         int[] forward = getLeavesForward();
 520         int[] backward = getLeavesBackward();
 521         if (forward.length != backward.length) {
 522                 return false;
 523         }
 524         else if (forward.length > 0) {
 525                 for (int i = 0;i<forward.length;i++) {
 526                         if (forward[i] != backward[forward.length - i - 1]) {
 527                                 return false;
 528                         }
 529                 }
 530         }
 531         return true;
 532     }
 533
 534     public void printLeaves() {
 535         System.out.println("");
 536         int[] forward = getLeavesForward();
 537         int[] backward = getLeavesBackward();
 538         if (forward.length > 0) {
 539                 System.err.println("forward:  " + backward.length);
 540                 for (int i = 0;i<forward.length;i++) {
 541                         System.err.println(forward[i]);
 542                 }
 543         }
 544         if (backward.length > 0) {
 545                 System.err.println("backward: " + backward.length);
 546                 for (int i = backward.length-1;i>=0;i--) {
 547                         System.err.println(backward[i]);
 548                 }
 549         }
 550     }
 551
 552     public int[] getLeavesForward() {
 553         int[] leaves = new int[size[root]];
 554         if (size[root] > 0) {
 555                 leaves[0] = leftmost(root);
 556                 for (int i=1;i < leaves.length;i++) {
 557                         leaves[i] = next(leaves[i-1]);
 558                 }
 559         }
 560                 return leaves;
 561     }
 562
 563     public int[] getLeavesBackward() {
 564         int[] leaves = new int[size[root]];
 565         if (size[root] > 0) {
 566                 leaves[0] = rightmost(root);
 567                 for (int i=1;i < leaves.length;i++) {
 568                         leaves[i] = prev(leaves[i-1]);
 569                 }
 570         }
 571         return leaves;
 572     }
 573
 574     public void validateTree() {
 575         if(root == 0) System.err.println("Tree is empty");
 576         else validateTree(root,0,false);
 577         System.err.println("");
 578     }
 579     private void validateTree(int node,int indent,boolean l) {
 580         if(node < 0) {}
 581         else if(node == 0)  {}
 582         else {
 583                 System.err.println((l?"Prev: " : "Next: ") + -node);
 584             validateTree(left[node],indent+1,true);
 585             validateTree(right[node],indent+1,false);
 586         }
 587     }
 588
 589 }