src/org/xwt/util/BalancedTree.java

   1 // Copyright (C) 2003 Adam Megacz <adam@xwt.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.xwt.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 // FEATURE: finalizer
  15
  16 /** a weight-balanced tree with fake leaves */
  17 public class BalancedTree {
  18
  19
  20     // Instance Variables ///////////////////////////////////////////////////////////////////
  21
  22     private int root = 0;                         ///< the slot of the root element
  23
  24     private int cached_index = -1;
  25     private int cached_slot = -1;
  26
  27     // Public API //////////////////////////////////////////////////////////////////////////
  28
  29     /** the number of elements in the tree */
  30     public final int treeSize() { return root == 0 ? 0 : size[root]; }
  31
  32     /** clamps index to [0..treeSize()] and inserts object o *before* the specified index */
  33     public final synchronized 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);
  38         if (root != 0) {
  39             insert(index, arg, root, 0, false, false);
  40         } else {
  41             root = arg;
  42             left[arg] = 0;
  43             right[arg] = 0;
  44             size[root] = 1;
  45         }
  46     }
  47
  48     /** clamps index to [0..treeSize()-1] and replaces the object at that index with object o */
  49     public final synchronized 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; }
  55         root = arg;
  56         left[arg] = 0;
  57         right[arg] = 0;
  58     }
  59
  60     /** returns the index of o; runs in O((log n)^2) time unless cache hit */
  61     public final synchronized int indexNode(Object o) {
  62         if (cached_slot != -1 && objects[cached_slot] == o) return cached_index;
  63
  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
  67
  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;
  70     }
  71
  72     /** returns the object at index; runs in O(log n) time unless cache hit */
  73     public final synchronized Object getNode(int index) {
  74         if (index == cached_index) return objects[cached_slot];
  75
  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
  80             // search directly.
  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];
  85             }
  86         }
  87         /*
  88         cached_index = index;
  89         cached_slot = get(index, root);
  90         return objects[cached_slot];
  91         */
  92         return objects[get(index, root)];
  93     }
  94
  95     /** deletes the object at index, returning the deleted object */
  96     public final synchronized 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];
 101         objects[del] = null;
 102         return ret;
 103     }
 104
 105
 106     // Node Data /////////////////////////////////////////////////////////////////////////
 107
 108     private final static int NUM_SLOTS = 64 * 1024;
 109
 110     /**
 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.
 117      */
 118     private static Object[] objects = new Object[NUM_SLOTS];
 119
 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.
 123     ///
 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.
 127     ///
 128     private static int[] left = new int[NUM_SLOTS];
 129     private static int[] right = new int[NUM_SLOTS];
 130
 131     ///< the number of descendants of this node *including the node itself*
 132     private static int[] size = new int[NUM_SLOTS];
 133
 134
 135     // Slot Management //////////////////////////////////////////////////////////////////////
 136
 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;
 141         int odest = dest;
 142         boolean plus = true;
 143         int tries = 1;
 144         while (objects[dest] != o) {
 145             if (dest == 0) dest++;
 146             dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % objects.length);
 147             if (plus) tries++;
 148             plus = !plus;
 149         }
 150         return dest;
 151     }
 152
 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
 157         // trees
 158         int slot = getSlot(null, o.hashCode() ^ this.hashCode());
 159         objects[slot] = o;
 160         return slot;
 161     }
 162
 163
 164
 165     // Helpers /////////////////////////////////////////////////////////////////////////
 166
 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]; }
 172
 173
 174     // Rotation and Balancing /////////////////////////////////////////////////////////////
 175
 176     //    parent             parent
 177     //      |                  |
 178     //      b                  d
 179     //     / \                / \
 180     //    a   d    < == >    b   e
 181     //       / \            / \
 182     //      c   e          a   c
 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;
 187         int d = right[b];
 188         int c = left[d];
 189         if (d <= 0) throw new Error("rotation error");
 190         left[d] = b;
 191         right[b] = c;
 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]);
 198     }
 199
 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);
 205     }
 206
 207
 208
 209     // Insert /////////////////////////////////////////////////////////////////////////
 210
 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);
 217             return;
 218         }
 219
 220         if (size[arg] != 0) throw new Error("double insertion");
 221
 222         if (replace) {
 223             if (diff == 0) {
 224                 objects[slot] = objects[arg];
 225                 objects[arg] = null;
 226                 left[arg] = right[arg] = size[arg] = 0;
 227             } else {
 228                 // since we already clamped the index
 229                 throw new Error("this should never happen");
 230             }
 231         }
 232
 233         // we become the child of a former leaf
 234         if (slot <= 0) {
 235             int[] left = wentLeft ? BalancedTree.left : BalancedTree.right;
 236             int[] right = wentLeft ? BalancedTree.right : BalancedTree.left;
 237             left[arg] = slot;
 238             left[parent] = arg;
 239             right[arg] = -1 * parent;
 240             balance(arg, parent);
 241
 242         // we take the place of a preexisting node
 243         } else {
 244             left[arg] = left[slot];   // steal slot's left subtree
 245             left[slot] = -1 * arg;
 246             right[arg] = slot;        // make slot our right subtree
 247             if (slot == root) {
 248                 root = arg;
 249                 balance(slot, arg);
 250                 balance(arg, 0);
 251             } else {
 252                 (left[parent] == slot ? left : right)[parent] = arg;
 253                 balance(slot, arg);
 254                 balance(arg, parent);
 255             }
 256         }
 257     }
 258
 259
 260     // Retrieval //////////////////////////////////////////////////////////////////////
 261
 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]);
 266         else return slot;
 267     }
 268
 269
 270     // Deletion //////////////////////////////////////////////////////////////////////
 271
 272     private int delete(int index, int slot, int parent) {
 273         int diff = index - size(left[slot]);
 274         if (diff < 0) {
 275             int ret = delete(index, left[slot], slot);
 276             balance(slot, parent);
 277             return ret;
 278
 279         } else if (diff > 0) {
 280             int ret = delete(diff - 1, right[slot], slot);
 281             balance(slot, parent);
 282             return ret;
 283
 284         // we found the node to delete
 285         } else {
 286
 287             // fast path: it has no children
 288             if (left[slot] <= 0 && right[slot] <= 0) {
 289                 if (parent == 0) root = 0;
 290                 else {
 291                     int[] side = left[parent] == slot ? left : right;
 292                     side[parent] = side[slot];      // fix parent's pointer
 293                 }
 294
 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);
 301
 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);
 308
 309             // node to be deleted has two children, so we replace it with its left child's rightmost descendant
 310             } else {
 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);
 317             }
 318
 319             return slot;
 320         }
 321     }
 322
 323 }