// Copyright 2003 Adam Megacz, see the COPYING file for licensing [GPL]
package org.xwt.util;
+// Implemented from http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/red_black.html
+
+// 1. Every node is either red or black.
+// 2. Every leaf node is black; if a red node has no right or left child,
+// pretend that an imaginary (sentinel) black node is there.
+// 3. If a node is red, then both its children are black.
+// 4. Every simple path from a node to a descendant leaf contains the
+// same number of black nodes.
+
+
/** a red-black tree of arbitrary objects */
public class RedBlackTree {
- private static boolean RED = false;
- private static boolean BLACK = true;
+ private static final boolean RED = false;
+ private static final boolean BLACK = true;
+
+ private static final int DELETE = 0;
+ private static final int INSERT = 1;
// These arrays are indexed by "slot", a totally meaningless number
// assigned to each object object[slot] has index index[slot] and
// color color[slot]. Note that slot 0 is reserved as "null".
- /** every object in the tree has an entry here; ordering is completely random */
- private Object[] objects;
-
- /** the color of each object */
- private boolean[] color;
-
- /** the slot of this object's parent */
- private int[] parent;
-
- /** the slot of this object's left child */
- private int[] left;
-
- /** the slot of this object's right child */
- private int[] right;
-
- /** the index of each element; ie how many objects are "before" it in the logical ordering */
- private int[] index;
-
- /** the slot of the root element */
- private int root = 0;
-
- /** returns the slot of the newly-inserted object */
- /*
- public int insertBefore(int slot, Object newObject) { left = cell; cell.parent = this; cell.fixAfterInsertion(); }
- public int insertAfterMe(int slot, Object newObject) { right = cell; cell.parent = this; cell.fixAfterInsertion(); }
-
- private void setColor(int slot, boolean c) { if (objects[slot] != null) color[slot] = c; }
-
- // FIXME: we can drop all this since all the 0th elements are the defaults, right?
- private boolean color(int slot) { return objects[slot] == null ? BLACK : color[slot]; }
- private int left(int slot) { return objects[slot] == null ? 0 : left[slot]; }
- private int right(int slot) { return objects[slot] == null ? 0 : right[slot]; }
-
- public void remove(int slot) { remove(slot, index[slot], root); }
-
- private void seek(int slot, int idx, int cur, int operation) {
- if (index[cur] > idx) {
- remove(slot, idx, left[cur], operation);
- } else if (index[cur] < idx) {
- remove(slot, idx, right[cur], operation);
- } else {
- switch(operation) {
- case REMOVE:
- case INSERT:
- }
- }
+ private Object[] objects; ///< every object in the tree has an entry here; ordering is completely random
+
+ // FEATURE: use a bitmask?
+ private boolean[] color; ///< the color of each object
+
+ private int[] left; ///< the slot of this object's left child
+ private int[] right; ///< the slot of this object's right child
+ private int[] index; ///< the index of each element; ie how many objects are "before" it in the logical ordering
+
+ private int root = 0; ///< the slot of the root element
+
+
+ // parent parent
+ // | |
+ // b d
+ // / \ / \
+ // a d < == > b e
+ // / \ / \
+ // c e a c
+ void rotate(boolean toTheLeft, int b, int parent) {
+ int[] left = toTheLeft ? this.left : this.right;
+ int[] right = toTheLeft ? this.right : this.left;
+ if (b == 0) throw new Error("rotate called on the null slot");
+ int d = right[b];
+ if (d == 0) throw new Error("attempted to rotate a node with only one child in the wrong direction");
+ int c = left[d];
+ left[d] = b;
+ right[b] = c;
+ if (parent == 0) root = d;
+ else if (left[parent] == b) left[parent] = d;
+ else if (right[parent] == b) right[parent] = d;
+ else throw new Error("rotate called with invalid parent");
}
- public void removeNode() {
-
- // handle case where we are only node
- if (left == null && right == null && parent == null) return;
-
- // if strictly internal, swap places with a successor
- if (left != null && right != null) swapPosition(this, nextSibling());
-
- // Start fixup at replacement node (normally a child).
- // But if no children, fake it by using self
- if (left == null && right == null) {
-
- if (test(BLACK)) fixAfterDeletion();
-
- // Unlink (Couldn't before since fixAfterDeletion needs parent ptr)
-
- if (parent != null) {
- if (this == parent.left)
- parent.left = null;
- else if (this == parent.right)
- parent.right = null;
- parent = null;
- }
-
- } else {
- Box replacement = left;
- if (replacement == null) replacement = right;
-
- // link replacement to parent
- replacement.parent = parent;
-
- if (parent == null) root = replacement;
- else if (this == parent.left) parent.left = replacement;
- else parent.right = replacement;
-
- left = null;
- right = null;
- parent = null;
-
- // fix replacement
- if (test(BLACK)) replacement.fixAfterDeletion();
-
- }
- }
-
- // Swap the linkages of two nodes in a tree.
- void swapPosition(Box x, Box y) {
-
- // Too messy. TODO: find sequence of assigments that are always OK
-
- Box px = x.parent;
- boolean xpl = px != null && x == px.left;
- Box lx = x.left;
- Box rx = x.right;
-
- Box py = y.parent;
- boolean ypl = py != null && y == py.left;
- Box ly = y.left;
- Box ry = y.right;
-
- if (x == py) {
- y.parent = px;
- if (px != null) if (xpl) px.left = y; else px.right = y;
- x.parent = y;
- if (ypl) {
- y.left = x;
- y.right = rx; if (rx != null) rx.parent = y;
- }
- else {
- y.right = x;
- y.left = lx; if (lx != null) lx.parent = y;
+ /** seeks to the node specified by slot/idx and performs operation on it */
+ private int seek(int slot, int idx, int cur, int operation, int parent, int grandparent, int greatgrandparent) {
+
+ int ret = 0;
+ if (index[cur] > idx && left[cur] != 0) {
+ ret = seek(slot, idx, left[cur], operation, cur, parent, grandparent);
+ if (ret > 0) return ret - 1;
+
+ } else if (index[cur] < idx && right[cur] != 0) {
+ ret = seek(slot, idx, right[cur], operation, cur, parent, grandparent);
+ if (ret > 0) return ret - 1;
+
+ } else switch(operation) {
+ case INSERT: (index[cur] > idx ? left : right)[cur] = slot; break;
+ case DELETE: {
+ int swap = 0;
+ if (right[left[slot]] != 0) swap = right[left[slot]];
+ else if (left[right[slot]] != 0) swap = left[right[slot]];
+ else if (left[slot] != 0) for(swap = left[slot]; right[swap] != 0;) swap = right[swap];
+ else if (right[slot] != 0) for(swap = right[slot]; left[swap] != 0;) swap = left[swap];
+ else swap = slot;
+ //swapAndDelete(swap, slot);
}
- x.left = ly; if (ly != null) ly.parent = x;
- x.right = ry; if (ry != null) ry.parent = x;
-
- } else if (y == px) {
- x.parent = py;
- if (py != null) if (ypl) py.left = x; else py.right = x;
- y.parent = x;
- if (xpl) {
- x.left = y;
- x.right = ry; if (ry != null) ry.parent = x;
- }
- else {
- x.right = y;
- x.left = ly; if (ly != null) ly.parent = x;
- }
- y.left = lx; if (lx != null) lx.parent = y;
- y.right = rx; if (rx != null) rx.parent = y;
-
- } else {
- x.parent = py; if (py != null) if (ypl) py.left = x; else py.right = x;
- x.left = ly; if (ly != null) ly.parent = x;
- x.right = ry; if (ry != null) ry.parent = x;
-
- y.parent = px; if (px != null) if (xpl) px.left = y; else px.right = y;
- y.left = lx; if (lx != null) lx.parent = y;
- y.right = rx; if (rx != null) rx.parent = y;
}
- boolean c = x.test(BLACK);
- if (y.test(BLACK)) x.set(BLACK); else x.clear(BLACK);
- if (c) y.set(BLACK); else y.clear(BLACK);
-
- if (root == x) root = y;
- else if (root == y) root = x;
- }
-
- void rotateLeft() {
- Box r = right;
- right = r.left;
- if (r.left != null) r.left.parent = this;
- r.parent = parent;
- if (parent == null) root = r;
- else if (parent.left == this) parent.left = r;
- else parent.right = r;
- r.left = this;
- parent = r;
- }
-
- void rotateRight() {
- Box l = left;
- left = l.right;
- if (l.right != null) l.right.parent = this;
- l.parent = parent;
- if (parent == null) root = l;
- else if (parent.right == this) parent.right = l;
- else parent.left = l;
- l.right = this;
- parent = l;
- }
-
- void fixAfterInsertion() {
- clear(BLACK);
- Box x = this;
-
- while (x != null && x != root && !x.parent.test(BLACK)) {
- if (parent[x] == left(parent[parent[x]])) {
- Box y = right(parent[parent[x]]);
- if (color(y) == RED) {
- setColor(parent[x], BLACK);
- setColor(y, BLACK);
- setColor(parent[parent[x]], RED);
- x = parent[parent[x]];
+ // grandparent cannot be null since root is always BLACK
+ if (parent == 0) { color[slot] = BLACK; return Integer.MAX_VALUE; }
+
+ switch(operation) {
+ // FIXME check for nulls
+ // FIXME only move up the tree when explicitly told to do so
+ case DELETE: {
+ int[] left = slot == this.left[parent] ? this.left : this.right;
+ int[] right = slot == this.left[parent] ? this.right : this.left;
+ if (color[slot] == RED) { color[slot] = BLACK; return Integer.MAX_VALUE; }
+ int sib = right[parent];
+ if (color[sib] == RED) {
+ color[sib] = BLACK;
+ color[parent] = RED;
+ rotate(left == this.left, parent, grandparent);
+ parent = grandparent;
+ grandparent = greatgrandparent;
+ greatgrandparent = 0;
+ ret += 1;
+ sib = right[parent];
}
- else {
- if (x == right(parent[x])) {
- x = parent[x];
- x.rotateLeft();
- }
- setColor(parent[x], BLACK);
- setColor(parent[parent[x]], RED);
- if (parent[parent[x]] != null)
- parent[parent[x]].rotateRight();
+ if (color[left[sib]] == BLACK && color[right[sib]] == BLACK) { color[sib] = RED; break; }
+ if (color[right[sib]] == BLACK) {
+ color[left[sib]] = BLACK;
+ color[sib] = RED;
+ rotate(left != this.left, sib, parent);
+ sib = right[parent];
}
+ color[sib] = color[parent];
+ color[parent] = BLACK;
+ color[right[sib]] = BLACK;
+ rotate(left == this.left, parent, grandparent);
+ ret += 1;
+ //x = root /* is this right? */;
}
- else {
- Box y = left(parent[parent[x]]);
- if (color(y) == RED) {
- setColor(parent[x], BLACK);
- setColor(y, BLACK);
- setColor(parent[parent[x]], RED);
- x = parent[parent[x]];
- }
- else {
- if (x == left(parent[x])) {
- x = parent[x];
- x.rotateRight();
- }
- setColor(parent[x], BLACK);
- setColor(parent[parent[x]], RED);
- if (parent[parent[x]] != null)
- parent[parent[x]].rotateLeft();
- }
- }
- }
- root.set(BLACK);
- }
- // From CLR
- void fixAfterDeletion() {
- Box x = this;
- while (x != root && color(x) == BLACK) {
- if (x == left(parent[x])) {
- Box sib = right(parent[x]);
- if (color(sib) == RED) {
- setColor(sib, BLACK);
- setColor(parent[x], RED);
- parent[x].rotateLeft();
- sib = right(parent[x]);
- }
- if (color(left(sib)) == BLACK && color(right(sib)) == BLACK) {
- setColor(sib, RED);
- x = parent[x];
- }
- else {
- if (color(right(sib)) == BLACK) {
- setColor(left(sib), BLACK);
- setColor(sib, RED);
- sib.rotateRight();
- sib = right(parent[x]);
+ case INSERT: {
+ if (parent == 0 || color[parent] == BLACK) return Integer.MAX_VALUE;
+ int[] left = parent == this.left[grandparent] ? this.left : this.right;
+ int[] right = parent == this.left[grandparent] ? this.right : this.left;
+ if(color[right[grandparent]] == RED) {
+ color[parent] = BLACK;
+ color[right[grandparent]] = BLACK;
+ color[grandparent] = RED;
+ return 1;
+ } else {
+ if (slot == right[parent]) {
+ ret = 1; // skip our parent
+ rotate(left == this.left, slot, parent); // then make him our child
+ color[slot] = BLACK; // same as else block
+ color[grandparent] = RED; // same as else block
+ rotate(left == this.left, parent, grandparent); // same as else block
+ } else {
+ color[parent] = BLACK;
+ color[grandparent] = RED;
+ rotate(left != this.left, grandparent, greatgrandparent);
}
- setColor(sib, color(parent[x]));
- setColor(parent[x], BLACK);
- setColor(right(sib), BLACK);
- parent[x].rotateLeft();
- x = root;
- }
- }
- else {
- Box sib = left(parent[x]);
- if (color(sib) == RED) {
- setColor(sib, BLACK);
- setColor(parent[x], RED);
- parent[x].rotateRight();
- sib = left(parent[x]);
- }
- if (color(right(sib)) == BLACK && color(left(sib)) == BLACK) {
- setColor(sib, RED);
- x = parent[x];
- }
- else {
- if (color(left(sib)) == BLACK) {
- setColor(right(sib), BLACK);
- setColor(sib, RED);
- sib.rotateLeft();
- sib = left(parent[x]);
- }
- setColor(sib, color(parent[x]));
- setColor(parent[x], BLACK);
- setColor(left(sib), BLACK);
- parent[x].rotateRight();
- x = root;
}
}
}
- setColor(x, BLACK);
+ return ret;
}
- */
+
+
}
projects / org.ibex.core.git / commitdiff