X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=src%2Forg%2Fxwt%2Futil%2FBalancedTree.java;h=5e15b3efcf77e1fcaa5450c3972285b7fc1db570;hb=de378041d5ca2aca1a2b5a31ef15ae90a86c977f;hp=77091a07357f1cfbf0716944504d2f4b698bbd47;hpb=a4790e9810a6504f9b33bd9b3bbd39d1d1f26b9c;p=org.ibex.core.git diff --git a/src/org/xwt/util/BalancedTree.java b/src/org/xwt/util/BalancedTree.java index 77091a07..5e15b3e 100644 --- a/src/org/xwt/util/BalancedTree.java +++ b/src/org/xwt/util/BalancedTree.java @@ -1,167 +1,395 @@ -// Copyright 2003 Adam Megacz, see the COPYING file for licensing [GPL] +// Copyright (C) 2003 Adam Megacz all rights reserved. +// +// You may modify, copy, and redistribute this code under the terms of +// the GNU Library Public License version 2.1, with the exception of +// the portion of clause 6a after the semicolon (aka the "obnoxious +// relink clause") + package org.xwt.util; -// Implemented from http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/red_black.html +// FEATURE: private void intersection() { } +// FEATURE: private void union() { } +// FEATURE: private void subset() { } +// FEATURE: grow if we run out of slots + +/** a weight-balanced tree with fake leaves */ +public class BalancedTree { + + + // Instance Variables /////////////////////////////////////////////////////////////////// + + private int root = 0; ///< the slot of the root element + + private int cached_index = -1; + private int cached_slot = -1; + + // Public API ////////////////////////////////////////////////////////////////////////// + + /** the number of elements in the tree */ + public final int treeSize() { return root == 0 ? 0 : size[root]; } + + /** clamps index to [0..treeSize()] and inserts object o *before* the specified index */ + public final synchronized void insertNode(int index, Object o) { + if(o == null) throw new Error("can't insert nulls in the balanced tree"); + cached_slot = cached_index = -1; + if (index < 0) index = 0; + if (index > treeSize()) index = treeSize(); + int arg = allocateSlot(o); + if (root != 0) { + insert(index, arg, root, 0, false, false); + } else { + root = arg; + left[arg] = right[arg] = parent[arg] = 0; + size[arg] = 1; + } + } + + /** clamps index to [0..treeSize()-1] and replaces the object at that index with object o */ + public final synchronized void replaceNode(int index, Object o) { + if(o == null) throw new Error("can't insert nulls in the balanced tree"); + cached_slot = cached_index = -1; + if(root == 0) throw new Error("called replaceNode() on an empty tree"); + if (index < 0) index = 0; + if (index >= treeSize()) index = treeSize() - 1; + int arg = allocateSlot(o); + insert(index, arg, root, 0, true, false); + } + + /** returns the index of o; runs in O((log n)^2) time unless cache hit */ + public final synchronized int indexNode(Object o) { + if(o == null) return -1; + if (cached_slot != -1 && objects[cached_slot] == o) return cached_index; + + int slot = getSlot(o); + if(slot == -1) return -1; + + int index = 0; + while(true) { + // everything to the left is before us so add that to the index + index += sizeof(left[slot]); + // we are before anything on the right + while(left[parent[slot]] == slot) slot = parent[slot]; + // we end of the first node who isn't on the left, go to the node that has as its child + slot = parent[slot]; + // if we just processed the root we're done + if(slot == 0) break; + // count the node we're currently on towards the index + index++; + } + return index; + } + + /** returns the object at index; runs in O(log n) time unless cache hit */ + public final synchronized Object getNode(int index) { + if (index == cached_index) return objects[cached_slot]; + + if (cached_index != -1) { + int distance = Math.abs(index - cached_index); + // if the in-order distance between the cached node and the + // target node is less than log(n), it's probably faster to + // search directly. + if ((distance < 16) && ((2 << distance) < treeSize())) { + while(cached_index > index) { cached_slot = prev(cached_slot); cached_index--; } + while(cached_index < index) { cached_slot = next(cached_slot); cached_index++; } + return objects[cached_slot]; + } + } + /* + cached_index = index; + cached_slot = get(index, root); + return objects[cached_slot]; + */ + return objects[get(index, root)]; + } -// 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. + /** deletes the object at index, returning the deleted object */ + public final synchronized Object deleteNode(int index) { + cached_slot = cached_index = -1; + // FIXME: left[], right[], size[], and parent[] aren't getting cleared properly somewhere in here where a node had two children + int del = delete(index, root, 0); + left[del] = right[del] = size[del] = parent[del] = 0; + Object ret = objects[del]; + objects[del] = null; + return ret; + } + + public final synchronized void clear() { + if(root == 0) return; + int i = leftmost(root); + do { + int next = next(i); + objects[i] = null; + left[i] = right[i] = size[i] = parent[i] = 0; + i = next; + } while(i != 0); + root = 0; + } + + protected void finalize() { clear(); } -// FIXME: ability to ask for n^th node; requires a descendant count + // Node Data ///////////////////////////////////////////////////////////////////////// -/** a red-black tree of arbitrary objects */ -public class RedBlackTree { + private final static int NUM_SLOTS = 64 * 1024; + // FEATURE: GROW - private final static int MAX_SLOT_DISTANCE = 32; - private static final boolean RED = false; - private static final boolean BLACK = true; + /** + * Every object inserted into *any* tree gets a "slot" in this + * array. The slot is determined by hashcode modulo the length of + * the array, with quadradic probing to resolve collisions. NOTE + * that the "slot" of a node is NOT the same as its index. + * Furthermore, if an object is inserted into multiple trees, that + * object will have multiple slots. + */ + private static Object[] objects = new Object[NUM_SLOTS]; - private static final int DELETE = 0; - private static final int INSERT = 1; + /// These two arrays hold the left and right children of each + /// slot; in other words, left[x] is the *slot* of the left child + /// of the node in slot x. + /// + /// If x has no left child, then left[x] is -1 multiplied by the + /// slot of the node that precedes x; if x is the first node, then + /// left[x] is 0. The right[] array works the same way. + /// + private static int[] left = new int[NUM_SLOTS]; + private static int[] right = new int[NUM_SLOTS]; + + /// The parent of this node (0 if it is the root node) + private static int[] parent = new int[NUM_SLOTS]; - // 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". + ///< the number of descendants of this node *including the node itself* + private static int[] size = new int[NUM_SLOTS]; - // 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 + // Slot Management ////////////////////////////////////////////////////////////////////// - private int freeslot = 0; + /** if alloc == false returns the slot holding object o. if alloc is true returns a new slot for obejct o */ + private int getSlot(Object o, boolean alloc) { + // we XOR with our own hashcode so that we don't get tons of + // collisions when a single Object is inserted into multiple + // trees + int dest = Math.abs(o.hashCode() ^ this.hashCode()) % objects.length; + Object search = alloc ? null : o; + int odest = dest; + boolean plus = true; + int tries = 1; + while (objects[dest] != search || !(alloc || root(dest) == root)) { + if (dest == 0) dest++; + dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % objects.length); + if (plus) tries++; + plus = !plus; + // FEATURE: GROW - if(tries > MAX_SLOT_DISTANCE) return -1; + } + return dest; + } - 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]); } + /** returns the slots holding object o */ + private int getSlot(Object o) { return getSlot(o,false); } + + /** allocates a new slot holding object o*/ + private int allocateSlot(Object o) { + int slot = getSlot(o, true); + // FEATURE: GROW - if(slot == -1) throw new Error("out of slots"); + objects[slot] = o; + return slot; + } - // parent parent + + + // Helpers ///////////////////////////////////////////////////////////////////////// + + private final int leftmost(int slot) { return left[slot] <= 0 ? slot : leftmost(left[slot]); } + private final int rightmost(int slot) { return right[slot] <= 0 ? slot : rightmost(right[slot]); } + private final int next(int slot) { return right[slot] <= 0 ? -1 * right[slot] : leftmost(right[slot]); } + private final int prev(int slot) { return left[slot] <= 0 ? -1 * left[slot] : rightmost(left[slot]); } + private final int sizeof(int slot) { return slot <= 0 ? 0 : size[slot]; } + private final int root(int slot) { return parent[slot] == 0 ? slot : root(parent[slot]); } + + + // Rotation and Balancing ///////////////////////////////////////////////////////////// + + // p p // | | // 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; + // FIXME might be doing too much work here + private void rotate(boolean toTheLeft, int b, int p) { + int[] left = toTheLeft ? BalancedTree.left : BalancedTree.right; + int[] right = toTheLeft ? BalancedTree.right : BalancedTree.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]; + if (d <= 0) throw new Error("rotation error"); 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; + if(size[b] <= 3) // b is now a leaf + right[b] = -d; + else + right[b] = c; + parent[b] = d; + parent[d] = p; + if(c > 0) parent[c] = b; + if (p == 0) root = d; + else if (left[p] == b) left[p] = d; + else if (right[p] == b) right[p] = d; else throw new Error("rotate called with invalid parent"); + size[b] = 1 + sizeof(left[b]) + sizeof(right[b]); + size[d] = 1 + sizeof(left[d]) + sizeof(right[d]); } - 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]]; + private void balance(int slot, int p) { + if (slot <= 0) return; + size[slot] = 1 + sizeof(left[slot]) + sizeof(right[slot]); + if (sizeof(left[slot]) - 1 > 2 * sizeof(right[slot])) rotate(false, slot, p); + else if (sizeof(left[slot]) * 2 < sizeof(right[slot]) - 1) rotate(true, slot, p); } - // FIXME: maintain fakeptrs - // private void intersection() { } - // private void union() { } - // private void subset() { } + // Insert ///////////////////////////////////////////////////////////////////////// + + private void insert(int index, int arg, int slot, int p, boolean replace, boolean wentLeft) { + int diff = slot <= 0 ? 0 : index - sizeof(left[slot]); + if (slot > 0 && diff != 0) { + if (diff < 0) insert(index, arg, left[slot], slot, replace, true); + else insert(index - sizeof(left[slot]) - 1, arg, right[slot], slot, replace, false); + balance(slot, p); + return; + } - private void insert(int idx, int arg, int slot, int parent) { + if (size[arg] != 0) throw new Error("double insertion"); - int diff = idx - size[left[slot]]; - if (slot == 0 || diff == 0) { - if (size[arg] != 0) throw new Error("double insertion"); + // we are replacing an existing node + if (replace) { + if (diff != 0) throw new Error("this should never happen"); // since we already clamped the index + if (p == 0) root = arg; + else if (left[p] == slot) left[p] = arg; + else if (right[p] == slot) right[p] = arg; + left[arg] = left[slot]; + right[arg] = right[slot]; + size[arg] = size[slot]; + parent[arg] = parent[slot]; + if(left[slot] > 0) parent[left[slot]] = arg; + if(right[slot] > 0) parent[right[slot]] = arg; + objects[slot] = null; + left[slot] = right[slot] = size[slot] = parent[slot] = 0; + + // we become the child of a former leaf + } else if (slot <= 0) { + int[] left = wentLeft ? BalancedTree.left : BalancedTree.right; + int[] right = wentLeft ? BalancedTree.right : BalancedTree.left; + left[arg] = slot; + left[p] = arg; + right[arg] = -1 * p; + parent[arg] = p; + balance(arg, p); + // we take the place of a preexisting node + } else { left[arg] = left[slot]; // steal slot's left subtree - left[slot] = 0; + left[slot] = -1 * arg; 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; + parent[arg] = parent[slot]; + parent[slot] = arg; + if (slot == root) { + root = arg; + balance(slot, arg); + balance(arg, 0); + } else { + if (left[p] == slot) left[p] = arg; + else if (right[p] == slot) right[p] = arg; + else throw new Error("should never happen"); + balance(slot, arg); + balance(arg, p); + } } - - 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]]; + // Retrieval ////////////////////////////////////////////////////////////////////// + + private int get(int index, int slot) { + int diff = index - sizeof(left[slot]); if (diff > 0) return get(diff - 1, right[slot]); - else if (diff < 0) return get(idx, left[slot]); + else if (diff < 0) return get(index, 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); + + // Deletion ////////////////////////////////////////////////////////////////////// + + private int delete(int index, int slot, int p) { + int diff = index - sizeof(left[slot]); + if (diff < 0) { + int ret = delete(index, left[slot], slot); + balance(slot, p); return ret; } else if (diff > 0) { int ret = delete(diff - 1, right[slot], slot); - balance(slot, parent); + balance(slot, p); return ret; + // we found the node to delete } 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]; + + // fast path: it has no children + if (left[slot] <= 0 && right[slot] <= 0) { + if (p == 0) root = 0; + else { + int[] side = left[p] == slot ? left : right; + side[p] = side[slot]; // fix parent's pointer } - if (parent == 0) root = replacement; - else (left[parent] == slot ? left : right)[parent] = replacement; - left[slot] = 0; - right[slot] = 0; - balance(replacement, parent); + + // fast path: it has no left child, so we replace it with its right child + } else if (left[slot] <= 0) { + if (p == 0) root = right[slot]; + else (left[p] == slot ? left : right)[p] = right[slot]; // fix parent's pointer + parent[right[slot]] = p; + left[leftmost(right[slot])] = left[slot]; // fix our successor-leaf's fake right ptr + balance(right[slot], p); + + // fast path; it has no right child, so we replace it with its left child + } else if (right[slot] <= 0) { + if (p == 0) root = left[slot]; + else (left[p] == slot ? left : right)[p] = left[slot]; // fix parent's pointer + parent[left[slot]] = p; + right[rightmost(left[slot])] = right[slot]; // fix our successor-leaf's fake right ptr + balance(left[slot], p); + + // node to be deleted has two children, so we replace it with its left child's rightmost descendant + } else { + int left_childs_rightmost = delete(sizeof(left[slot]) - 1, left[slot], slot); + left[left_childs_rightmost] = left[slot]; + right[left_childs_rightmost] = right[slot]; + if(left[slot] > 0) parent[left[slot]] = left_childs_rightmost; + if(right[slot] > 0) parent[right[slot]] = left_childs_rightmost; + parent[left_childs_rightmost] = parent[slot]; + if (p == 0) root = left_childs_rightmost; + else (left[p] == slot ? left : right)[p] = left_childs_rightmost; // fix parent's pointer + balance(left_childs_rightmost, p); } + return slot; } } + // Debugging /////////////////////////////////////////////////////////////////////////// + + public void printTree() { + if(root == 0) System.err.println("Tree is empty"); + else printTree(root,0,false); + } + private void printTree(int node,int indent,boolean l) { + for(int i=0;i