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  }
151