src/org/xwt/util/RedBlackTree.java

   1 // Copyright 2003 Adam Megacz, see the COPYING file for licensing [GPL]
   2 package org.xwt.util;
   3
   4 /** a red-black tree of arbitrary objects */
   5 public class RedBlackTree {
   6
   7     private static boolean RED = false;
   8     private static boolean BLACK = true;
   9
  10     // These arrays are indexed by "slot", a totally meaningless number
  11     // assigned to each object object[slot] has index index[slot] and
  12     // color color[slot].  Note that slot 0 is reserved as "null".
  13
  14     /** every object in the tree has an entry here; ordering is completely random */
  15     private Object[] objects;
  16
  17     /** the color of each object */
  18     private boolean[] color;
  19
  20     /** the slot of this object's parent */
  21     private int[] parent;
  22
  23     /** the slot of this object's left child */
  24     private int[] left;
  25
  26     /** the slot of this object's right child */
  27     private int[] right;
  28
  29     /** the index of each element; ie how many objects are "before" it in the logical ordering */
  30     private int[] index;
  31
  32     /** the slot of the root element */
  33     private int root = 0;
  34
  35     /** returns the slot of the newly-inserted object */
  36     /*
  37     public int insertBefore(int slot, Object newObject) { left = cell; cell.parent = this; cell.fixAfterInsertion(); }
  38     public int insertAfterMe(int slot, Object newObject) { right = cell; cell.parent = this; cell.fixAfterInsertion(); }
  39
  40     private void    setColor(int slot, boolean c) { if (objects[slot] != null) color[slot] = c; }
  41
  42     // FIXME: we can drop all this since all the 0th elements are the defaults, right?
  43     private boolean color(int slot) { return objects[slot] == null ? BLACK : color[slot]; }
  44     private int     left(int slot) { return objects[slot] == null ? 0 : left[slot]; }
  45     private int     right(int slot) { return objects[slot] == null ? 0 : right[slot]; }
  46
  47     public void remove(int slot) { remove(slot, index[slot], root); }
  48
  49     private void seek(int slot, int idx, int cur, int operation) {
  50         if (index[cur] > idx) {
  51             remove(slot, idx, left[cur], operation);
  52         } else if (index[cur] < idx) {
  53             remove(slot, idx, right[cur], operation);
  54         } else {
  55             switch(operation) {
  56                 case REMOVE:
  57                 case INSERT:
  58             }
  59         }
  60     }
  61
  62     public void removeNode() {
  63
  64         // handle case where we are only node
  65         if (left == null && right == null && parent == null) return;
  66
  67         // if strictly internal, swap places with a successor
  68         if (left != null && right != null) swapPosition(this, nextSibling());
  69
  70         // Start fixup at replacement node (normally a child).
  71         // But if no children, fake it by using self
  72         if (left == null && right == null) {
  73
  74             if (test(BLACK)) fixAfterDeletion();
  75
  76             // Unlink  (Couldn't before since fixAfterDeletion needs parent ptr)
  77
  78             if (parent != null) {
  79                 if (this == parent.left)
  80                     parent.left = null;
  81                 else if (this == parent.right)
  82                     parent.right = null;
  83                 parent = null;
  84             }
  85
  86         } else {
  87             Box replacement = left;
  88             if  (replacement == null) replacement = right;
  89
  90             // link replacement to parent
  91             replacement.parent = parent;
  92
  93             if (parent == null) root = replacement;
  94             else if (this == parent.left)  parent.left  = replacement;
  95             else parent.right = replacement;
  96
  97             left = null;
  98             right = null;
  99             parent = null;
 100
 101             // fix replacement
 102             if (test(BLACK)) replacement.fixAfterDeletion();
 103
 104         }
 105     }
 106
 107     // Swap the linkages of two nodes in a tree.
 108     void swapPosition(Box x, Box y) {
 109
 110     // Too messy. TODO: find sequence of assigments that are always OK
 111
 112         Box px = x.parent;
 113         boolean xpl = px != null && x == px.left;
 114         Box lx = x.left;
 115         Box rx = x.right;
 116
 117         Box py = y.parent;
 118         boolean ypl = py != null && y == py.left;
 119         Box ly = y.left;
 120         Box ry = y.right;
 121
 122         if (x == py) {
 123             y.parent = px;
 124             if (px != null) if (xpl) px.left = y; else px.right = y;
 125             x.parent = y;
 126             if (ypl) {
 127                 y.left = x;
 128                 y.right = rx; if (rx != null) rx.parent = y;
 129             }
 130             else {
 131                 y.right = x;
 132                 y.left = lx;   if (lx != null) lx.parent = y;
 133             }
 134             x.left = ly;   if (ly != null) ly.parent = x;
 135             x.right = ry;  if (ry != null) ry.parent = x;
 136
 137         } else if (y == px) {
 138             x.parent = py;
 139             if (py != null) if (ypl) py.left = x; else py.right = x;
 140             y.parent = x;
 141             if (xpl) {
 142                 x.left = y;
 143                 x.right = ry; if (ry != null) ry.parent = x;
 144             }
 145             else {
 146                 x.right = y;
 147                 x.left = ly;   if (ly != null) ly.parent = x;
 148             }
 149             y.left = lx;   if (lx != null) lx.parent = y;
 150             y.right = rx;  if (rx != null) rx.parent = y;
 151
 152         } else {
 153             x.parent = py; if (py != null) if (ypl) py.left = x; else py.right = x;
 154             x.left = ly;   if (ly != null) ly.parent = x;
 155             x.right = ry;  if (ry != null) ry.parent = x;
 156
 157             y.parent = px; if (px != null) if (xpl) px.left = y; else px.right = y;
 158             y.left = lx;   if (lx != null) lx.parent = y;
 159             y.right = rx;  if (rx != null) rx.parent = y;
 160         }
 161
 162         boolean c = x.test(BLACK);
 163         if (y.test(BLACK)) x.set(BLACK); else x.clear(BLACK);
 164         if (c) y.set(BLACK); else y.clear(BLACK);
 165
 166         if (root == x) root = y;
 167         else if (root == y) root = x;
 168     }
 169
 170     void rotateLeft() {
 171         Box r = right;
 172         right = r.left;
 173         if (r.left != null) r.left.parent = this;
 174         r.parent = parent;
 175         if (parent == null) root = r;
 176         else if (parent.left == this) parent.left = r;
 177         else parent.right = r;
 178         r.left = this;
 179         parent = r;
 180     }
 181
 182     void rotateRight() {
 183         Box l = left;
 184         left = l.right;
 185         if (l.right != null) l.right.parent = this;
 186         l.parent = parent;
 187         if (parent == null) root = l;
 188         else if (parent.right == this) parent.right = l;
 189         else parent.left = l;
 190         l.right = this;
 191         parent = l;
 192     }
 193
 194     void fixAfterInsertion() {
 195         clear(BLACK);
 196         Box x = this;
 197
 198         while (x != null && x != root && !x.parent.test(BLACK)) {
 199             if (parent[x] == left(parent[parent[x]])) {
 200                 Box y = right(parent[parent[x]]);
 201                 if (color(y) == RED) {
 202                     setColor(parent[x], BLACK);
 203                     setColor(y, BLACK);
 204                     setColor(parent[parent[x]], RED);
 205                     x = parent[parent[x]];
 206                 }
 207                 else {
 208                     if (x == right(parent[x])) {
 209                         x = parent[x];
 210                         x.rotateLeft();
 211                     }
 212                     setColor(parent[x], BLACK);
 213                     setColor(parent[parent[x]], RED);
 214                     if (parent[parent[x]] != null)
 215                         parent[parent[x]].rotateRight();
 216                 }
 217             }
 218             else {
 219                 Box y = left(parent[parent[x]]);
 220                 if (color(y) == RED) {
 221                     setColor(parent[x], BLACK);
 222                     setColor(y, BLACK);
 223                     setColor(parent[parent[x]], RED);
 224                     x = parent[parent[x]];
 225                 }
 226                 else {
 227                     if (x == left(parent[x])) {
 228                         x = parent[x];
 229                         x.rotateRight();
 230                     }
 231                     setColor(parent[x],  BLACK);
 232                     setColor(parent[parent[x]], RED);
 233                     if (parent[parent[x]] != null)
 234                         parent[parent[x]].rotateLeft();
 235                 }
 236             }
 237         }
 238         root.set(BLACK);
 239     }
 240
 241     // From CLR
 242     void fixAfterDeletion() {
 243         Box x = this;
 244         while (x != root && color(x) == BLACK) {
 245             if (x == left(parent[x])) {
 246                 Box sib = right(parent[x]);
 247                 if (color(sib) == RED) {
 248                     setColor(sib, BLACK);
 249                     setColor(parent[x], RED);
 250                     parent[x].rotateLeft();
 251                     sib = right(parent[x]);
 252                 }
 253                 if (color(left(sib)) == BLACK && color(right(sib)) == BLACK) {
 254                     setColor(sib,  RED);
 255                     x = parent[x];
 256                 }
 257                 else {
 258                     if (color(right(sib)) == BLACK) {
 259                         setColor(left(sib), BLACK);
 260                         setColor(sib, RED);
 261                         sib.rotateRight();
 262                         sib = right(parent[x]);
 263                     }
 264                     setColor(sib, color(parent[x]));
 265                     setColor(parent[x], BLACK);
 266                     setColor(right(sib), BLACK);
 267                     parent[x].rotateLeft();
 268                     x = root;
 269                 }
 270             }
 271             else {
 272                 Box sib = left(parent[x]);
 273                 if (color(sib) == RED) {
 274                     setColor(sib, BLACK);
 275                     setColor(parent[x], RED);
 276                     parent[x].rotateRight();
 277                     sib = left(parent[x]);
 278                 }
 279                 if (color(right(sib)) == BLACK && color(left(sib)) == BLACK) {
 280                     setColor(sib,  RED);
 281                     x = parent[x];
 282                 }
 283                 else {
 284                     if (color(left(sib)) == BLACK) {
 285                         setColor(right(sib), BLACK);
 286                         setColor(sib, RED);
 287                         sib.rotateLeft();
 288                         sib = left(parent[x]);
 289                     }
 290                     setColor(sib, color(parent[x]));
 291                     setColor(parent[x], BLACK);
 292                     setColor(left(sib), BLACK);
 293                     parent[x].rotateRight();
 294                     x = root;
 295                 }
 296             }
 297         }
 298         setColor(x, BLACK);
 299     }
 300     */
 301 }