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 = 0;
  19     private int cached_slot = 0;
  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 = 0;
  29         if (index < 0) index = 0;
  30         if (index > treeSize()) index = treeSize();
  31         int arg = allocateSlot(o);
  32         if (root != 0) { insert(index, arg, root, 0, false, false); return; }
  33         root = arg;
  34         left[arg] = 0;
  35         right[arg] = 0;
  36         size[root] = 1;
  37     }
  38
  39     /** clamps index to [0..treeSize()-1] and replaces the object at that index with object o */
  40     public final void replaceNode(int index, Object o) {
  41         cached_slot = cached_index = 0;
  42         if (index < 0) index = 0;
  43         if (index > treeSize()) index = treeSize() - 1;
  44         int arg = allocateSlot(o);
  45         if (root != 0) { insert(index, arg, root, 0, true, false); return; }
  46         root = arg;
  47         left[arg] = 0;
  48         right[arg] = 0;
  49     }
  50
  51     /** returns the index of o; runs in O((log n)^2) time unless cache hit */
  52     public final int indexNode(Object o) {
  53         if (objects[cached_slot] == o) return cached_index;
  54
  55         int slot = getSlot(o, o.hashCode() ^ this.hashCode());
  56         int parent = -1 * left[leftmost(slot)];
  57         if (parent == 0) return size(left[slot]);             // we are on the far left edge
  58
  59         // all nodes after parent and before us are in our left subtree
  60         else return size(left[slot]) + indexNode(objects[parent]) + 1;
  61     }
  62
  63     /** returns the object at index; runs in O(log n) time unless cache hit */
  64     public final Object getNode(int index) {
  65         if (index == cached_index) return objects[cached_slot];
  66
  67         int distance = Math.abs(index - cached_index);
  68
  69         // if the in-order distance between the cached node and the
  70         // target node is less than log(n), it's probably faster to
  71         // search directly.
  72         if (cached_index != 0 && (distance < 16) && ((2 << distance) < treeSize())) {
  73             while(cached_index > index) { cached_slot = prev(cached_slot); cached_index--; }
  74             while(cached_index < index) { cached_slot = next(cached_slot); cached_index++; }
  75             return objects[cached_slot];
  76         }
  77
  78         return objects[get(index, root)];
  79     }
  80
  81     /** deletes the object at index, returning the deleted object */
  82     public final Object deleteNode(int index) {
  83         cached_slot = cached_index = 0;
  84         return delete(index, root, 0);
  85     }
  86
  87
  88     // Node Data /////////////////////////////////////////////////////////////////////////
  89
  90     private final static int NUM_SLOTS = 265 * 1024;
  91
  92     /**
  93      * Every object inserted into *any* tree gets a "slot" in this
  94      * array.  The slot is determined by hashcode modulo the length of
  95      * the array, with quadradic probing to resolve collisions.  NOTE
  96      * that the "slot" of a node is NOT the same as its index.
  97      * Furthermore, if an object is inserted into multiple trees, that
  98      * object will have multiple slots.
  99      */
 100     private static Object[] objects = new Object[NUM_SLOTS];
 101     private static int[] left = new int[NUM_SLOTS];      ///< if positive: left child's slot; if negative: predecessor's slot
 102     private static int[] right = new int[NUM_SLOTS];     ///< if positive: right child's slot; if negative: successor's slot
 103     private static int[] size = new int[NUM_SLOTS];      ///< the number of descendants of this node *including the node itself*
 104
 105
 106     // Slot Management //////////////////////////////////////////////////////////////////////
 107
 108     /** returns the slot holding object o; use null to allocate a new slot */
 109     private int getSlot(Object o, int hash) {
 110         // FIXME: check for full table
 111         int dest = Math.abs(hash) % objects.length;
 112         int odest = dest;
 113         boolean plus = true;
 114         int tries = 1;
 115         while (objects[dest] != o) {
 116             if (dest == 0) dest++;
 117             dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % objects.length);
 118             if (plus) tries++;
 119             plus = !plus;
 120         }
 121         return dest;
 122     }
 123
 124     /** allocates a new slot */
 125     private int allocateSlot(Object o) {
 126         // we XOR with our own hashcode so that we don't get tons of
 127         // collisions when a single Object is inserted into multiple
 128         // trees
 129         int slot = getSlot(null, o.hashCode() ^ this.hashCode());
 130         objects[slot] = o;
 131         return slot;
 132     }
 133
 134
 135
 136     // Helpers /////////////////////////////////////////////////////////////////////////
 137
 138     private final int leftmost(int slot) { return left[slot] <= 0 ? slot : leftmost(left[slot]); }
 139     private final int rightmost(int slot) { return right[slot] <= 0 ? slot : rightmost(right[slot]); }
 140     private final int next(int slot) { return right[slot] <= 0 ? -1 * right[slot] : leftmost(right[slot]); }
 141     private final int prev(int slot) { return left[slot] <= 0 ? -1 * left[slot] : rightmost(left[slot]); }
 142     private final int size(int slot) { return slot <= 0 ? 0 : size[slot]; }
 143
 144
 145     // Rotation and Balancing /////////////////////////////////////////////////////////////
 146
 147     //    parent             parent
 148     //      |                  |
 149     //      b                  d
 150     //     / \                / \
 151     //    a   d    < == >    b   e
 152     //       / \            / \
 153     //      c   e          a   c
 154     // FIXME might be doing too much work here
 155     private void rotate(boolean toTheLeft, int b, int parent) {
 156         int[] left = toTheLeft ? BalancedTree.left : BalancedTree.right;
 157         int[] right = toTheLeft ? BalancedTree.right : BalancedTree.left;
 158         int d = right[b];
 159         int c = left[d];
 160         left[d] = b;
 161         right[b] = c;
 162         if (parent == 0)              root = d;
 163         else if (left[parent] == b)   left[parent] = d;
 164         else if (right[parent] == b)  right[parent] = d;
 165         else throw new Error("rotate called with invalid parent");
 166         size[b] = 1 + size(left[b]) + size(right[b]);
 167         balance(b, d);
 168         size[d] = 1 + size(left[d]) + size(right[d]);
 169         balance(d, parent);
 170     }
 171
 172     private void balance(int slot, int parent) {
 173         if (size(left[slot]) - 1 > 2 * size(right[slot])) rotate(false, slot, parent);
 174         else if (size(left[slot]) * 2 < size(right[slot]) - 1) rotate(true, slot, parent);
 175         size[slot] = 1 + size(left[slot]) + size(right[slot]);
 176     }
 177
 178
 179
 180     // Insert /////////////////////////////////////////////////////////////////////////
 181
 182     private void insert(int index, int arg, int slot, int parent, boolean replace, boolean wentLeft) {
 183         int diff = slot <= 0 ? 0 : index - size(left[slot]);
 184         if (slot > 0 && diff != 0) {
 185             if (diff < 0) insert(index, arg, left[slot], slot, replace, true);
 186             else insert(index - size(left[slot]) - 1, arg, right[slot], slot, replace, false);
 187             balance(slot, parent);
 188             return;
 189         }
 190
 191         if (size[arg] != 0) throw new Error("double insertion");
 192
 193         // we become the child of a former leaf
 194         if (slot <= 0) {
 195             int[] left = wentLeft ? BalancedTree.left : BalancedTree.right;
 196             int[] right = wentLeft ? BalancedTree.right : BalancedTree.left;
 197             left[arg] = slot;
 198             left[parent] = arg;
 199             right[arg] = -1 * parent;
 200             balance(arg, parent);
 201
 202         // we take the place of a preexisting node
 203         } else {
 204             left[arg] = left[slot];   // steal slot's left subtree
 205             left[slot] = -1 * arg;
 206             right[arg] = slot;        // make slot our right subtree
 207             if (slot == root) {
 208                 root = arg;
 209                 balance(slot, arg);
 210             } else {
 211                 (left[parent] == slot ? left : right)[parent] = arg;
 212                 balance(slot, arg);
 213                 balance(arg, parent);
 214             }
 215         }
 216     }
 217
 218
 219     // Retrieval //////////////////////////////////////////////////////////////////////
 220
 221     private int get(int index, int slot) {
 222         int diff = index - size(left[slot]);
 223         if (diff > 0) return get(diff - 1, right[slot]);
 224         else if (diff < 0) return get(index, left[slot]);
 225         else return slot;
 226     }
 227
 228
 229     // Deletion //////////////////////////////////////////////////////////////////////
 230
 231     private Object delete(int index, int slot, int parent) {
 232         int diff = index - size(left[slot]);
 233         if (diff < 0) {
 234             Object ret = delete(index, left[slot], slot);
 235             balance(slot, parent);
 236             return ret;
 237
 238         } else if (diff > 0) {
 239             Object ret = delete(diff - 1, right[slot], slot);
 240             balance(slot, parent);
 241             return ret;
 242
 243         } else {
 244             if (left[slot] == 0) {
 245                 if (parent == 0) root = right[slot];
 246                 else (left[parent] == slot ? left : right)[parent] = right[slot];
 247                 right[slot] = 0;
 248                 balance(slot, parent);
 249             } else if (right[slot] == 0) {
 250                 if (parent == 0) root = left[slot];
 251                 else (left[parent] == slot ? left : right)[parent] = left[slot];
 252                 left[slot] = 0;
 253                 balance(slot, parent);
 254             } else {
 255                 Object replacement_object = delete(index - 1, slot, parent);
 256                 int replacement = allocateSlot(replacement_object);
 257                 if (replacement != 0) {
 258                     left[replacement] = left[slot];
 259                     right[replacement] = right[slot];
 260                 }
 261                 if (parent == 0) root = replacement;
 262                 else (left[parent] == slot ? left : right)[parent] = replacement;
 263                 left[slot] = 0;
 264                 right[slot] = 0;
 265                 balance(replacement, parent);
 266             }
 267             Object ret = objects[slot];
 268             size[slot] = 0;
 269             objects[slot] = null;
 270             return ret;
 271         }
 272     }
 273
 274 }