src/org/xwt/util/BalancedTree.java

   1 // Copyright 2003 Adam Megacz, see the COPYING file for licensing [GPL]
   2 package org.xwt.util;
   3
   4 // FEATURE: private void intersection() { }
   5 // FEATURE: private void union() { }
   6 // FEATURE: private void subset() { }
   7 // FEATURE: grow if we run out of slots
   8 // FEATURE: finalizer
   9
  10 /** a weight-balanced tree with fake leaves */
  11 public class BalancedTree {
  12
  13
  14     // Instance Variables ///////////////////////////////////////////////////////////////////
  15
  16     private int root = 0;                         ///< the slot of the root element
  17
  18     private int cached_index = -1;
  19     private int cached_slot = -1;
  20
  21     // Public API //////////////////////////////////////////////////////////////////////////
  22
  23     /** the number of elements in the tree */
  24     public final int treeSize() { return root == 0 ? 0 : size[root]; }
  25
  26     /** clamps index to [0..treeSize()] and inserts object o *before* the specified index */
  27     public final void insertNode(int index, Object o) {
  28         cached_slot = cached_index = -1;
  29         if (index < 0) index = 0;
  30         if (index > treeSize()) index = treeSize();
  31         int arg = allocateSlot(o);
  32         if (root != 0) {
  33             insert(index, arg, root, 0, false, false);
  34         } else {
  35             root = arg;
  36             left[arg] = 0;
  37             right[arg] = 0;
  38             size[root] = 1;
  39         }
  40     }
  41
  42     /** clamps index to [0..treeSize()-1] and replaces the object at that index with object o */
  43     public final void replaceNode(int index, Object o) {
  44         cached_slot = cached_index = -1;
  45         if (index < 0) index = 0;
  46         if (index > treeSize()) index = treeSize() - 1;
  47         int arg = allocateSlot(o);
  48         if (root != 0) { insert(index, arg, root, 0, true, false); return; }
  49         root = arg;
  50         left[arg] = 0;
  51         right[arg] = 0;
  52     }
  53
  54     /** returns the index of o; runs in O((log n)^2) time unless cache hit */
  55     public final int indexNode(Object o) {
  56         if (cached_slot != -1 && objects[cached_slot] == o) return cached_index;
  57
  58         int slot = getSlot(o, o.hashCode() ^ this.hashCode());
  59         int parent = -1 * left[leftmost(slot)];
  60         if (parent == 0) return size(left[slot]);             // we are on the far left edge
  61
  62         // all nodes after parent and before us are in our left subtree
  63         return size(left[slot]) + indexNode(objects[parent]) + 1;
  64     }
  65
  66     /** returns the object at index; runs in O(log n) time unless cache hit */
  67     public final Object getNode(int index) {
  68         if (index == cached_index) return objects[cached_slot];
  69
  70         if (cached_index != -1) {
  71             int distance = Math.abs(index - cached_index);
  72             // if the in-order distance between the cached node and the
  73             // target node is less than log(n), it's probably faster to
  74             // search directly.
  75             if ((distance < 16) && ((2 << distance) < treeSize())) {
  76                 while(cached_index > index) { cached_slot = prev(cached_slot); cached_index--; }
  77                 while(cached_index < index) { cached_slot = next(cached_slot); cached_index++; }
  78                 return objects[cached_slot];
  79             }
  80         }
  81         /*
  82         cached_index = index;
  83         cached_slot = get(index, root);
  84         return objects[cached_slot];
  85         */
  86         return objects[get(index, root)];
  87     }
  88
  89     /** deletes the object at index, returning the deleted object */
  90     public final Object deleteNode(int index) {
  91         cached_slot = cached_index = -1;
  92         int del = delete(index, root, 0);
  93         left[del] = right[del] = size[del] = 0;
  94         Object ret = objects[del];
  95         objects[del] = null;
  96         return ret;
  97     }
  98
  99
 100     // Node Data /////////////////////////////////////////////////////////////////////////
 101
 102     private final static int NUM_SLOTS = 64 * 1024;
 103
 104     /**
 105      * Every object inserted into *any* tree gets a "slot" in this
 106      * array.  The slot is determined by hashcode modulo the length of
 107      * the array, with quadradic probing to resolve collisions.  NOTE
 108      * that the "slot" of a node is NOT the same as its index.
 109      * Furthermore, if an object is inserted into multiple trees, that
 110      * object will have multiple slots.
 111      */
 112     private static Object[] objects = new Object[NUM_SLOTS];
 113
 114     /// These two arrays hold the left and right children of each
 115     /// slot; in other words, left[x] is the *slot* of the left child
 116     /// of the node in slot x.
 117     ///
 118     /// If x has no left child, then left[x] is -1 multiplied by the
 119     /// slot of the node that precedes x; if x is the first node, then
 120     /// left[x] is 0.  The right[] array works the same way.
 121     ///
 122     private static int[] left = new int[NUM_SLOTS];
 123     private static int[] right = new int[NUM_SLOTS];
 124
 125     ///< the number of descendants of this node *including the node itself*
 126     private static int[] size = new int[NUM_SLOTS];
 127
 128
 129     // Slot Management //////////////////////////////////////////////////////////////////////
 130
 131     /** returns the slot holding object o; use null to allocate a new slot */
 132     private int getSlot(Object o, int hash) {
 133         // FIXME: check for full table
 134         int dest = Math.abs(hash) % objects.length;
 135         int odest = dest;
 136         boolean plus = true;
 137         int tries = 1;
 138         while (objects[dest] != o) {
 139             if (dest == 0) dest++;
 140             dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % objects.length);
 141             if (plus) tries++;
 142             plus = !plus;
 143         }
 144         return dest;
 145     }
 146
 147     /** allocates a new slot */
 148     private int allocateSlot(Object o) {
 149         // we XOR with our own hashcode so that we don't get tons of
 150         // collisions when a single Object is inserted into multiple
 151         // trees
 152         int slot = getSlot(null, o.hashCode() ^ this.hashCode());
 153         objects[slot] = o;
 154         return slot;
 155     }
 156
 157
 158
 159     // Helpers /////////////////////////////////////////////////////////////////////////
 160
 161     private final int leftmost(int slot) { return left[slot] <= 0 ? slot : leftmost(left[slot]); }
 162     private final int rightmost(int slot) { return right[slot] <= 0 ? slot : rightmost(right[slot]); }
 163     private final int next(int slot) { return right[slot] <= 0 ? -1 * right[slot] : leftmost(right[slot]); }
 164     private final int prev(int slot) { return left[slot] <= 0 ? -1 * left[slot] : rightmost(left[slot]); }
 165     private final int size(int slot) { return slot <= 0 ? 0 : size[slot]; }
 166
 167
 168     // Rotation and Balancing /////////////////////////////////////////////////////////////
 169
 170     //    parent             parent
 171     //      |                  |
 172     //      b                  d
 173     //     / \                / \
 174     //    a   d    < == >    b   e
 175     //       / \            / \
 176     //      c   e          a   c
 177     // FIXME might be doing too much work here
 178     private void rotate(boolean toTheLeft, int b, int parent) {
 179         int[] left = toTheLeft ? BalancedTree.left : BalancedTree.right;
 180         int[] right = toTheLeft ? BalancedTree.right : BalancedTree.left;
 181         int d = right[b];
 182         int c = left[d];
 183         if (d <= 0) throw new Error("rotation error");
 184         left[d] = b;
 185         right[b] = c;
 186         if (parent == 0)              root = d;
 187         else if (left[parent] == b)   left[parent] = d;
 188         else if (right[parent] == b)  right[parent] = d;
 189         else throw new Error("rotate called with invalid parent");
 190         size[b] = 1 + size(left[b]) + size(right[b]);
 191         size[d] = 1 + size(left[d]) + size(right[d]);
 192     }
 193
 194     private void balance(int slot, int parent) {
 195         if (slot <= 0) return;
 196         size[slot] = 1 + size(left[slot]) + size(right[slot]);
 197         if (size(left[slot]) - 1 > 2 * size(right[slot])) rotate(false, slot, parent);
 198         else if (size(left[slot]) * 2 < size(right[slot]) - 1) rotate(true, slot, parent);
 199     }
 200
 201
 202
 203     // Insert /////////////////////////////////////////////////////////////////////////
 204
 205     private void insert(int index, int arg, int slot, int parent, boolean replace, boolean wentLeft) {
 206         int diff = slot <= 0 ? 0 : index - size(left[slot]);
 207         if (slot > 0 && diff != 0) {
 208             if (diff < 0) insert(index, arg, left[slot], slot, replace, true);
 209             else insert(index - size(left[slot]) - 1, arg, right[slot], slot, replace, false);
 210             balance(slot, parent);
 211             return;
 212         }
 213
 214         if (size[arg] != 0) throw new Error("double insertion");
 215
 216         if (replace) {
 217             if (diff == 0) {
 218                 objects[slot] = objects[arg];
 219                 objects[arg] = null;
 220                 left[arg] = right[arg] = size[arg] = 0;
 221             } else {
 222                 // since we already clamped the index
 223                 throw new Error("this should never happen");
 224             }
 225         }
 226
 227         // we become the child of a former leaf
 228         if (slot <= 0) {
 229             int[] left = wentLeft ? BalancedTree.left : BalancedTree.right;
 230             int[] right = wentLeft ? BalancedTree.right : BalancedTree.left;
 231             left[arg] = slot;
 232             left[parent] = arg;
 233             right[arg] = -1 * parent;
 234             balance(arg, parent);
 235
 236         // we take the place of a preexisting node
 237         } else {
 238             left[arg] = left[slot];   // steal slot's left subtree
 239             left[slot] = -1 * arg;
 240             right[arg] = slot;        // make slot our right subtree
 241             if (slot == root) {
 242                 root = arg;
 243                 balance(slot, arg);
 244                 balance(arg, 0);
 245             } else {
 246                 (left[parent] == slot ? left : right)[parent] = arg;
 247                 balance(slot, arg);
 248                 balance(arg, parent);
 249             }
 250         }
 251     }
 252
 253
 254     // Retrieval //////////////////////////////////////////////////////////////////////
 255
 256     private int get(int index, int slot) {
 257         int diff = index - size(left[slot]);
 258         if (diff > 0) return get(diff - 1, right[slot]);
 259         else if (diff < 0) return get(index, left[slot]);
 260         else return slot;
 261     }
 262
 263
 264     // Deletion //////////////////////////////////////////////////////////////////////
 265
 266     private int delete(int index, int slot, int parent) {
 267         int diff = index - size(left[slot]);
 268         if (diff < 0) {
 269             int ret = delete(index, left[slot], slot);
 270             balance(slot, parent);
 271             return ret;
 272
 273         } else if (diff > 0) {
 274             int ret = delete(diff - 1, right[slot], slot);
 275             balance(slot, parent);
 276             return ret;
 277
 278         // we found the node to delete
 279         } else {
 280
 281             // fast path: it has no children
 282             if (left[slot] <= 0 && right[slot] <= 0) {
 283                 if (parent == 0) root = 0;
 284                 else {
 285                     int[] side = left[parent] == slot ? left : right;
 286                     side[parent] = side[slot];      // fix parent's pointer
 287                 }
 288
 289             // fast path: it has no left child, so we replace it with its right child
 290             } else if (left[slot] <= 0) {
 291                 if (parent == 0) root = right[slot];
 292                 else (left[parent] == slot ? left : right)[parent] = right[slot];     // fix parent's pointer
 293                 if (right[slot] > 0) left[leftmost(right[slot])] = left[slot];        // fix our successor-leaf's fake right ptr
 294                 balance(right[slot], parent);
 295
 296             // fast path; it has no right child, so we replace it with its left child
 297             } else if (right[slot] <= 0) {
 298                 if (parent == 0) root = left[slot];
 299                 else (left[parent] == slot ? left : right)[parent] = left[slot];      // fix parent's pointer
 300                 if (left[slot] > 0) right[rightmost(left[slot])] = right[slot];       // fix our successor-leaf's fake right ptr
 301                 balance(left[slot], parent);
 302
 303             // node to be deleted has two children, so we replace it with its left child's rightmost descendant
 304             } else {
 305                 int left_childs_rightmost = delete(size(left[slot]) - 1, left[slot], slot);
 306                 left[left_childs_rightmost] = left[slot];
 307                 left[left_childs_rightmost] = right[slot];
 308                 if (parent == 0) root = left_childs_rightmost;
 309                 else (left[parent] == slot ? left : right)[parent] = left_childs_rightmost;     // fix parent's pointer
 310                 balance(left_childs_rightmost, parent);
 311             }
 312
 313             return slot;
 314         }
 315     }
 316
 317 }