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 // Implemented from http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/red_black.html
   5
   6 // 1. Every node is either red or black.
   7 // 2. Every leaf node is black; if a red node has no right or left child,
   8 //    pretend that an imaginary (sentinel) black node is there.
   9 // 3. If a node is red, then both its children are black.
  10 // 4. Every simple path from a node to a descendant leaf contains the
  11 //    same number of black nodes.
  12
  13
  14 // FIXME: ability to ask for n^th node; requires a descendant count
  15
  16 /** a red-black tree of arbitrary objects */
  17 public class RedBlackTree {
  18
  19     private static final boolean RED = false;
  20     private static final boolean BLACK = true;
  21
  22     private static final int DELETE = 0;
  23     private static final int INSERT = 1;
  24
  25     // These arrays are indexed by "slot", a totally meaningless number
  26     // assigned to each object object[slot] has index index[slot] and
  27     // color color[slot].  Note that slot 0 is reserved as "null".
  28
  29     // FEATURE: use a bitmask?
  30     private int[] left;          ///< if positive: left child's slot; if negative: predecessor's slot
  31     private int[] right;         ///< if positive: right child's slot; if negative: successor's slot
  32     private int[] size;          ///< the number of descendants of this node *including the node itself*
  33     private Object[] objects;    ///< every object in the tree has an entry here; ordering is completely random
  34
  35     private int root = 0;               ///< the slot of the root element
  36
  37     private int freeslot = 0;
  38
  39     private int leftmost(int slot) { return left[slot] <= 0 ? slot : leftmost(left[slot]); }
  40     private int rightmost(int slot) { return right[slot] <= 0 ? slot : rightmost(right[slot]); }
  41     private int next(int slot) { return right[slot] <= 0 ? -1 * right[slot] : leftmost(right[slot]); }
  42     private int prev(int slot) { return left[slot] <= 0 ? -1 * left[slot] : rightmost(left[slot]); }
  43
  44     //    parent             parent
  45     //      |                  |
  46     //      b                  d
  47     //     / \                / \
  48     //    a   d    < == >    b   e
  49     //       / \            / \
  50     //      c   e          a   c
  51     void rotate(boolean toTheLeft, int b, int parent) {
  52         if (b == 0) throw new Error("rotate called on the null slot");
  53         int[] left = toTheLeft ? this.left : this.right;
  54         int[] right = toTheLeft ? this.right : this.left;
  55         int d = right[b];
  56         if (d == 0) throw new Error("attempted to rotate a node with only one child in the wrong direction");
  57         int c = left[d];
  58         left[d] = b;
  59         right[b] = c;
  60         size[b] -= size[d];
  61         int csize = c <= 0 ? 0 : size[c] + 1;
  62         size[b] += csize;
  63         size[d] -= csize;
  64         size[d] += size[b];
  65         if (parent == 0)              root = d;
  66         else if (left[parent] == b)   left[parent] = d;
  67         else if (right[parent] == b)  right[parent] = d;
  68         else throw new Error("rotate called with invalid parent");
  69     }
  70
  71     public void balance(int slot, int parent) {
  72         if (slot == 0) return;
  73         if (size[left[slot]] > 2 * size[right[slot]]) {
  74             rotate(false, slot, parent);
  75         } else if (size[left[slot]] * 2 < size[right[slot]]) {
  76             rotate(true, slot, parent);
  77         }
  78         size[slot] = 1 + size[left[slot]] + size[right[slot]];
  79     }
  80
  81     // FIXME: maintain fakeptrs
  82
  83
  84     // private void intersection() { }
  85     // private void union() { }
  86     // private void subset() { }
  87
  88     private void insert(int idx, int arg, int slot, int parent) {
  89
  90         int diff = idx - size[left[slot]];
  91         if (slot == 0 || diff == 0) {
  92             if (size[arg] != 0) throw new Error("double insertion");
  93
  94             left[arg] = left[slot];   // steal slot's left subtree
  95             left[slot] = 0;
  96             right[arg] = slot;        // make slot our right subtree
  97
  98             // FIXME: if slot == 0 we can't use it to figure out which end of parent we belong on
  99             if (parent == 0) root = arg;
 100             else (left[parent] == slot ? left : right)[parent] = arg;
 101
 102             balance(slot, arg);
 103             balance(arg, slot);
 104             return;
 105         }
 106
 107         if (diff < 0) insert(idx, arg, left[slot], slot);
 108         else insert(idx - size[left[slot]] - 1, arg, right[slot], slot);
 109         balance(slot, parent);
 110     }
 111
 112     private int indexOf(int slot) {
 113         int parent = -1 * left[leftmost(slot)];
 114         if (parent == 0) return size[left[slot]];             // we are on the far left edge
 115         else return size[left[slot]] + indexOf(parent) + 1;   // all nodes after parent and before us are in our left subtree
 116     }
 117
 118     private int get(int idx, int slot) {
 119         int diff = idx - size[left[slot]];
 120         if (diff > 0) return get(diff - 1, right[slot]);
 121         else if (diff < 0) return get(idx, left[slot]);
 122         else return slot;
 123     }
 124
 125     // return slot that was deleted
 126     private int delete(int idx, int slot, int parent) {
 127         int diff = idx - size[left[slot]];
 128         if (slot == 0) return 0;
 129         else if (diff < 0) {
 130             int ret = delete(idx, left[slot], slot);
 131             balance(slot, parent);
 132             return ret;
 133
 134         } else if (diff > 0) {
 135             int ret = delete(diff - 1, right[slot], slot);
 136             balance(slot, parent);
 137             return ret;
 138
 139         } else {
 140             size[slot] = 0;
 141             if (left[slot] == 0) {
 142                 if (parent == 0) root = right[slot];
 143                 else (left[parent] == slot ? left : right)[parent] = right[slot];
 144                 right[slot] = 0;
 145                 balance(slot, parent);
 146             } else if (right[slot] == 0) {
 147                 if (parent == 0) root = left[slot];
 148                 else (left[parent] == slot ? left : right)[parent] = left[slot];
 149                 left[slot] = 0;
 150                 balance(slot, parent);
 151             } else {
 152                 int replacement = delete(idx - 1, slot, parent);
 153                 if (replacement != 0) {
 154                     left[replacement] = left[slot];
 155                     right[replacement] = right[slot];
 156                 }
 157                 if (parent == 0) root = replacement;
 158                 else (left[parent] == slot ? left : right)[parent] = replacement;
 159                 left[slot] = 0;
 160                 right[slot] = 0;
 161                 balance(replacement, parent);
 162             }
 163             return slot;
 164         }
 165     }
 166
 167 }