From 9643cac881861867d1356d45ae7262df32e23677 Mon Sep 17 00:00:00 2001 From: megacz Date: Fri, 30 Jan 2004 07:42:07 +0000 Subject: [PATCH] 2003/11/26 05:11:38 darcs-hash:20040130074207-2ba56-ffef7a5f2ce0be858e86e93cbfed03f0cfe42470.gz --- src/org/xwt/util/RedBlackTree.java | 399 +++++++++++------------------------- 1 file changed, 124 insertions(+), 275 deletions(-) diff --git a/src/org/xwt/util/RedBlackTree.java b/src/org/xwt/util/RedBlackTree.java index c848f64..ce034eb 100644 --- a/src/org/xwt/util/RedBlackTree.java +++ b/src/org/xwt/util/RedBlackTree.java @@ -1,301 +1,150 @@ // 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; } - */ + + } -- 1.7.10.4