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