X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=src%2Forg%2Fxwt%2Futil%2FBalancedTree.java;h=5e15b3efcf77e1fcaa5450c3972285b7fc1db570;hb=de378041d5ca2aca1a2b5a31ef15ae90a86c977f;hp=99ec34f935ac781222a82bfc2744a568f2676312;hpb=1ece8d661a27c6ca5f94ef291db1eaa9885885d1;p=org.ibex.core.git diff --git a/src/org/xwt/util/BalancedTree.java b/src/org/xwt/util/BalancedTree.java index 99ec34f..5e15b3e 100644 --- a/src/org/xwt/util/BalancedTree.java +++ b/src/org/xwt/util/BalancedTree.java @@ -1,4 +1,10 @@ -// 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; // FEATURE: private void intersection() { } @@ -14,6 +20,8 @@ public class BalancedTree { private int root = 0; ///< the slot of the root element + private int cached_index = -1; + private int cached_slot = -1; // Public API ////////////////////////////////////////////////////////////////////////// @@ -21,52 +29,109 @@ public class BalancedTree { 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 void insertNode(int index, Object o) { + 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); return; } - root = arg; - left[arg] = 0; - right[arg] = 0; - size[root] = 1; + 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 void replaceNode(int index, 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; + if (index >= treeSize()) index = treeSize() - 1; int arg = allocateSlot(o); - if (root != 0) { insert(index, arg, root, 0, true, false); return; } - root = arg; - left[arg] = 0; - right[arg] = 0; + insert(index, arg, root, 0, true, false); } - /** returns the index of o; runs in O((log n)^2) time */ - public final int indexNode(Object o) { - int slot = getSlot(o, o.hashCode() ^ this.hashCode()); - int parent = -1 * left[leftmost(slot)]; - if (parent == 0) return size(left[slot]); // we are on the far left edge - - // all nodes after parent and before us are in our left subtree - else return size(left[slot]) + indexNode(objects[parent]) + 1; + /** 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 */ - public final Object getNode(int 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)]; } /** deletes the object at index, returning the deleted object */ - public final Object deleteNode(int index) { - return delete(index, root, 0); + 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(); } // Node Data ///////////////////////////////////////////////////////////////////////// - private final static int NUM_SLOTS = 265 * 1024; + private final static int NUM_SLOTS = 64 * 1024; + // FEATURE: GROW - private final static int MAX_SLOT_DISTANCE = 32; /** * Every object inserted into *any* tree gets a "slot" in this @@ -77,35 +142,54 @@ public class BalancedTree { * object will have multiple slots. */ private static Object[] objects = new Object[NUM_SLOTS]; - private static int[] left = new int[NUM_SLOTS]; ///< if positive: left child's slot; if negative: predecessor's slot - private static int[] right = new int[NUM_SLOTS]; ///< if positive: right child's slot; if negative: successor's slot - private static int[] size = new int[NUM_SLOTS]; ///< the number of descendants of this node *including the node itself* + /// 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]; - // Slot Management ////////////////////////////////////////////////////////////////////// + ///< the number of descendants of this node *including the node itself* + private static int[] size = new int[NUM_SLOTS]; - /** returns the slot holding object o; use null to allocate a new slot */ - private int getSlot(Object o, int hash) { - // FIXME: check for full table - int dest = Math.abs(hash) % objects.length; + + // Slot Management ////////////////////////////////////////////////////////////////////// + + /** 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] != o) { + 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; } - /** allocates a new 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) { - // 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 slot = getSlot(null, o.hashCode() ^ this.hashCode()); + int slot = getSlot(o, true); + // FEATURE: GROW - if(slot == -1) throw new Error("out of slots"); objects[slot] = o; return slot; } @@ -118,74 +202,107 @@ public class BalancedTree { 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 size(int slot) { return slot <= 0 ? 0 : size[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 ///////////////////////////////////////////////////////////// - // parent parent + // p p // | | // b d // / \ / \ // a d < == > b e // / \ / \ // c e a c - private void rotate(boolean toTheLeft, int b, int parent) { + // 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]; int c = left[d]; + if (d <= 0) throw new Error("rotation error"); left[d] = b; - right[b] = c; - size[b] = size(left[b]) + size(c); - size[d] = size[b] + size(right[d]); - 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]); } - private void balance(int slot, int parent) { - /* - if (size(left[slot]) - 1 > 2 * size(right[slot])) rotate(false, slot, parent); - else if (size(left[slot]) * 2 < size(right[slot]) - 1) 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); } // Insert ///////////////////////////////////////////////////////////////////////// - private void insert(int index, int arg, int slot, int parent, boolean replace, boolean wentLeft) { - int diff = slot <= 0 ? 0 : index - size(left[slot]); + 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 - size(left[slot]) - 1, arg, right[slot], slot, replace, false); - balance(slot, parent); + else insert(index - sizeof(left[slot]) - 1, arg, right[slot], slot, replace, false); + balance(slot, p); return; } 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 - if (slot <= 0) { + } else if (slot <= 0) { int[] left = wentLeft ? BalancedTree.left : BalancedTree.right; int[] right = wentLeft ? BalancedTree.right : BalancedTree.left; left[arg] = slot; - left[parent] = arg; - right[arg] = -1 * parent; - balance(arg, parent); + 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] = -1 * arg; right[arg] = slot; // make slot our right subtree - if (slot == root) root = arg; - (left[parent] == slot ? left : right)[parent] = arg; - balance(slot, arg); - balance(arg, parent); + 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); + } } } @@ -193,7 +310,7 @@ public class BalancedTree { // Retrieval ////////////////////////////////////////////////////////////////////// private int get(int index, int slot) { - int diff = index - size(left[slot]); + int diff = index - sizeof(left[slot]); if (diff > 0) return get(diff - 1, right[slot]); else if (diff < 0) return get(index, left[slot]); else return slot; @@ -202,47 +319,77 @@ public class BalancedTree { // Deletion ////////////////////////////////////////////////////////////////////// - private Object delete(int index, int slot, int parent) { - int diff = index - size(left[slot]); + private int delete(int index, int slot, int p) { + int diff = index - sizeof(left[slot]); if (diff < 0) { - Object ret = delete(index, left[slot], slot); - balance(slot, parent); + int ret = delete(index, left[slot], slot); + balance(slot, p); return ret; } else if (diff > 0) { - Object ret = delete(diff - 1, right[slot], slot); - balance(slot, parent); + int ret = delete(diff - 1, right[slot], slot); + balance(slot, p); return ret; + // we found the node to delete } else { - 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 { - Object replacement_object = delete(index - 1, slot, parent); - int replacement = allocateSlot(replacement_object); - 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); } - Object ret = objects[slot]; - size[slot] = 0; - objects[slot] = null; - return ret; + + 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