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 // 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 /** a red-black tree of arbitrary objects */
  15 public class RedBlackTree {
  16
  17     private static final boolean RED = false;
  18     private static final boolean BLACK = true;
  19
  20     private static final int DELETE = 0;
  21     private static final int INSERT = 1;
  22
  23     // These arrays are indexed by "slot", a totally meaningless number
  24     // assigned to each object object[slot] has index index[slot] and
  25     // color color[slot].  Note that slot 0 is reserved as "null".
  26
  27     private Object[] objects;    ///< every object in the tree has an entry here; ordering is completely random
  28
  29     // FEATURE: use a bitmask?
  30     private boolean[] color;     ///< the color of each object
  31
  32     private int[] left;          ///< the slot of this object's left child
  33     private int[] right;         ///< the slot of this object's right child
  34     private int[] index;         ///< the index of each element; ie how many objects are "before" it in the logical ordering
  35
  36     private int root = 0;               ///< the slot of the root element
  37
  38
  39     //    parent             parent
  40     //      |                  |
  41     //      b                  d
  42     //     / \                / \
  43     //    a   d    < == >    b   e
  44     //       / \            / \
  45     //      c   e          a   c
  46     void rotate(boolean toTheLeft, int b, int parent) {
  47         int[] left = toTheLeft ? this.left : this.right;
  48         int[] right = toTheLeft ? this.right : this.left;
  49         if (b == 0) throw new Error("rotate called on the null slot");
  50         int d = right[b];
  51         if (d == 0) throw new Error("attempted to rotate a node with only one child in the wrong direction");
  52         int c = left[d];
  53         left[d] = b;
  54         right[b] = c;
  55         if (parent == 0)              root = d;
  56         else if (left[parent] == b)   left[parent] = d;
  57         else if (right[parent] == b)  right[parent] = d;
  58         else throw new Error("rotate called with invalid parent");
  59     }
  60
  61     /** seeks to the node specified by slot/idx and performs operation on it */
  62     private int seek(int slot, int idx, int cur, int operation, int parent, int grandparent, int greatgrandparent) {
  63
  64         int ret = 0;
  65         if (index[cur] > idx && left[cur] != 0) {
  66             ret = seek(slot, idx, left[cur], operation, cur, parent, grandparent);
  67             if (ret > 0) return ret - 1;
  68
  69         } else if (index[cur] < idx && right[cur] != 0) {
  70             ret = seek(slot, idx, right[cur], operation, cur, parent, grandparent);
  71             if (ret > 0) return ret - 1;
  72
  73         } else switch(operation) {
  74             case INSERT: (index[cur] > idx ? left : right)[cur] = slot; break;
  75             case DELETE: {
  76                 int swap = 0;
  77                 if (right[left[slot]] != 0)         swap = right[left[slot]];
  78                 else if (left[right[slot]] != 0)    swap = left[right[slot]];
  79                 else if (left[slot] != 0)           for(swap = left[slot]; right[swap] != 0;) swap = right[swap];
  80                 else if (right[slot] != 0)          for(swap = right[slot]; left[swap] != 0;) swap = left[swap];
  81                 else swap = slot;
  82                 //swapAndDelete(swap, slot);
  83             }
  84         }
  85
  86         // grandparent cannot be null since root is always BLACK
  87         if (parent == 0) { color[slot] = BLACK; return Integer.MAX_VALUE; }
  88
  89         switch(operation) {
  90             // FIXME check for nulls
  91             // FIXME only move up the tree when explicitly told to do so
  92             case DELETE: {
  93                 int[] left = slot == this.left[parent] ? this.left : this.right;
  94                 int[] right = slot == this.left[parent] ? this.right : this.left;
  95                 if (color[slot] == RED) { color[slot] = BLACK; return Integer.MAX_VALUE; }
  96                 int sib = right[parent];
  97                 if (color[sib] == RED) {
  98                     color[sib] = BLACK;
  99                     color[parent] = RED;
 100                     rotate(left == this.left, parent, grandparent);
 101                     parent = grandparent;
 102                     grandparent = greatgrandparent;
 103                     greatgrandparent = 0;
 104                     ret += 1;
 105                     sib = right[parent];
 106                 }
 107                 if (color[left[sib]] == BLACK && color[right[sib]] == BLACK) { color[sib] = RED; break; }
 108                 if (color[right[sib]] == BLACK) {
 109                     color[left[sib]] = BLACK;
 110                     color[sib] = RED;
 111                     rotate(left != this.left, sib, parent);
 112                     sib = right[parent];
 113                 }
 114                 color[sib] = color[parent];
 115                 color[parent] = BLACK;
 116                 color[right[sib]] = BLACK;
 117                 rotate(left == this.left, parent, grandparent);
 118                 ret += 1;
 119                 //x = root /* is this right? */;
 120             }
 121
 122             case INSERT: {
 123                 if (parent == 0 || color[parent] == BLACK) return Integer.MAX_VALUE;
 124                 int[] left = parent == this.left[grandparent] ? this.left : this.right;
 125                 int[] right = parent == this.left[grandparent] ? this.right : this.left;
 126                 if(color[right[grandparent]] == RED) {
 127                     color[parent] = BLACK;
 128                     color[right[grandparent]] = BLACK;
 129                     color[grandparent] = RED;
 130                     return 1;
 131                 } else {
 132                     if (slot == right[parent]) {
 133                         ret = 1;                                        // skip our parent
 134                         rotate(left == this.left, slot, parent);        // then make him our child
 135                         color[slot] = BLACK;                            // same as else block
 136                         color[grandparent] = RED;                       // same as else block
 137                         rotate(left == this.left, parent, grandparent); // same as else block
 138                     } else {
 139                         color[parent] = BLACK;
 140                         color[grandparent] = RED;
 141                         rotate(left != this.left, grandparent, greatgrandparent);
 142                     }
 143                 }
 144             }
 145         }
 146         return ret;
 147     }
 148
 149
 150 }