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