From a4790e9810a6504f9b33bd9b3bbd39d1d1f26b9c Mon Sep 17 00:00:00 2001 From: megacz Date: Fri, 30 Jan 2004 07:42:08 +0000 Subject: [PATCH] 2003/11/26 21:59:13 darcs-hash:20040130074208-2ba56-ad57cb45277eb6dd6a57cfee364bb5c678fbafe7.gz --- src/org/xwt/util/BalancedTree.java | 167 ++++++++++++++++++++++++++++++++++++ src/org/xwt/util/RedBlackTree.java | 150 -------------------------------- 2 files changed, 167 insertions(+), 150 deletions(-) create mode 100644 src/org/xwt/util/BalancedTree.java delete mode 100644 src/org/xwt/util/RedBlackTree.java diff --git a/src/org/xwt/util/BalancedTree.java b/src/org/xwt/util/BalancedTree.java new file mode 100644 index 0000000..77091a07 --- /dev/null +++ b/src/org/xwt/util/BalancedTree.java @@ -0,0 +1,167 @@ +// 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. + + +// FIXME: ability to ask for n^th node; requires a descendant count + +/** a red-black tree of arbitrary objects */ +public class RedBlackTree { + + 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". + + // FEATURE: use a bitmask? + private int[] left; ///< if positive: left child's slot; if negative: predecessor's slot + private int[] right; ///< if positive: right child's slot; if negative: successor's slot + private int[] size; ///< the number of descendants of this node *including the node itself* + private Object[] objects; ///< every object in the tree has an entry here; ordering is completely random + + private int root = 0; ///< the slot of the root element + + private int freeslot = 0; + + private int leftmost(int slot) { return left[slot] <= 0 ? slot : leftmost(left[slot]); } + private int rightmost(int slot) { return right[slot] <= 0 ? slot : rightmost(right[slot]); } + private int next(int slot) { return right[slot] <= 0 ? -1 * right[slot] : leftmost(right[slot]); } + private int prev(int slot) { return left[slot] <= 0 ? -1 * left[slot] : rightmost(left[slot]); } + + // parent parent + // | | + // b d + // / \ / \ + // a d < == > b e + // / \ / \ + // c e a c + void rotate(boolean toTheLeft, int b, int parent) { + if (b == 0) throw new Error("rotate called on the null slot"); + int[] left = toTheLeft ? this.left : this.right; + int[] right = toTheLeft ? this.right : this.left; + 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; + size[b] -= size[d]; + int csize = c <= 0 ? 0 : size[c] + 1; + size[b] += csize; + size[d] -= csize; + size[d] += size[b]; + 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 balance(int slot, int parent) { + if (slot == 0) return; + if (size[left[slot]] > 2 * size[right[slot]]) { + rotate(false, slot, parent); + } else if (size[left[slot]] * 2 < size[right[slot]]) { + rotate(true, slot, parent); + } + size[slot] = 1 + size[left[slot]] + size[right[slot]]; + } + + // FIXME: maintain fakeptrs + + + // private void intersection() { } + // private void union() { } + // private void subset() { } + + private void insert(int idx, int arg, int slot, int parent) { + + int diff = idx - size[left[slot]]; + if (slot == 0 || diff == 0) { + if (size[arg] != 0) throw new Error("double insertion"); + + left[arg] = left[slot]; // steal slot's left subtree + left[slot] = 0; + right[arg] = slot; // make slot our right subtree + + // FIXME: if slot == 0 we can't use it to figure out which end of parent we belong on + if (parent == 0) root = arg; + else (left[parent] == slot ? left : right)[parent] = arg; + + balance(slot, arg); + balance(arg, slot); + return; + } + + if (diff < 0) insert(idx, arg, left[slot], slot); + else insert(idx - size[left[slot]] - 1, arg, right[slot], slot); + balance(slot, parent); + } + + private int indexOf(int slot) { + int parent = -1 * left[leftmost(slot)]; + if (parent == 0) return size[left[slot]]; // we are on the far left edge + else return size[left[slot]] + indexOf(parent) + 1; // all nodes after parent and before us are in our left subtree + } + + private int get(int idx, int slot) { + int diff = idx - size[left[slot]]; + if (diff > 0) return get(diff - 1, right[slot]); + else if (diff < 0) return get(idx, left[slot]); + else return slot; + } + + // return slot that was deleted + private int delete(int idx, int slot, int parent) { + int diff = idx - size[left[slot]]; + if (slot == 0) return 0; + else if (diff < 0) { + int ret = delete(idx, left[slot], slot); + balance(slot, parent); + return ret; + + } else if (diff > 0) { + int ret = delete(diff - 1, right[slot], slot); + balance(slot, parent); + return ret; + + } else { + size[slot] = 0; + if (left[slot] == 0) { + if (parent == 0) root = right[slot]; + else (left[parent] == slot ? left : right)[parent] = right[slot]; + right[slot] = 0; + balance(slot, parent); + } else if (right[slot] == 0) { + if (parent == 0) root = left[slot]; + else (left[parent] == slot ? left : right)[parent] = left[slot]; + left[slot] = 0; + balance(slot, parent); + } else { + int replacement = delete(idx - 1, slot, parent); + if (replacement != 0) { + left[replacement] = left[slot]; + right[replacement] = right[slot]; + } + if (parent == 0) root = replacement; + else (left[parent] == slot ? left : right)[parent] = replacement; + left[slot] = 0; + right[slot] = 0; + balance(replacement, parent); + } + return slot; + } + } + +} diff --git a/src/org/xwt/util/RedBlackTree.java b/src/org/xwt/util/RedBlackTree.java deleted file mode 100644 index ce034eb..0000000 --- a/src/org/xwt/util/RedBlackTree.java +++ /dev/null @@ -1,150 +0,0 @@ -// 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 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". - - 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"); - } - - /** 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); - } - } - - // 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]; - } - 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? */; - } - - 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); - } - } - } - } - return ret; - } - - -} -- 1.7.10.4