From a88b93becb603643cb2fa323499f27e80a22700b Mon Sep 17 00:00:00 2001 From: brian Date: Fri, 30 Jan 2004 07:43:53 +0000 Subject: [PATCH] 2003/12/30 21:30:01 darcs-hash:20040130074353-aa32f-2eeb898d092ce58262ee7c5e3ca05d2b4103c4a7.gz --- src/org/xwt/util/BalancedTree.java | 214 ++++++++++++++++++++++++------------ 1 file changed, 143 insertions(+), 71 deletions(-) diff --git a/src/org/xwt/util/BalancedTree.java b/src/org/xwt/util/BalancedTree.java index 175ae33..0775ebe 100644 --- a/src/org/xwt/util/BalancedTree.java +++ b/src/org/xwt/util/BalancedTree.java @@ -11,7 +11,6 @@ package org.xwt.util; // FEATURE: private void union() { } // FEATURE: private void subset() { } // FEATURE: grow if we run out of slots -// FEATURE: finalizer /** a weight-balanced tree with fake leaves */ public class BalancedTree { @@ -31,6 +30,7 @@ public class BalancedTree { /** 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(); @@ -39,34 +39,44 @@ public class BalancedTree { insert(index, arg, root, 0, false, false); } else { root = arg; - left[arg] = 0; - right[arg] = 0; - size[root] = 1; + 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; + 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 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, 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 - return size(left[slot]) + (parent <= 0 ? 0 : indexNode(objects[parent])) + 1; + 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 += size(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 */ @@ -95,17 +105,33 @@ public class BalancedTree { /** 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] = 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 = 64 * 1024; + // FEATURE: GROW - private final static int MAX_SLOT_DISTANCE = 32; /** * Every object inserted into *any* tree gets a "slot" in this @@ -127,35 +153,43 @@ public class BalancedTree { /// 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]; ///< the number of descendants of this node *including the node itself* private static int[] size = new int[NUM_SLOTS]; // Slot Management ////////////////////////////////////////////////////////////////////// - - /** 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; + + /** 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; } @@ -169,11 +203,12 @@ public class BalancedTree { 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 root(int slot) { return parent[slot] == 0 ? slot : root(parent[slot]); } // Rotation and Balancing ///////////////////////////////////////////////////////////// - // parent parent + // p p // | | // b d // / \ / \ @@ -181,77 +216,92 @@ public class BalancedTree { // / \ / \ // c e a c // FIXME might be doing too much work here - private void rotate(boolean toTheLeft, int b, int parent) { + 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; - 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 + size(left[b]) + size(right[b]); size[d] = 1 + size(left[d]) + size(right[d]); } - private void balance(int slot, int parent) { + private void balance(int slot, int p) { if (slot <= 0) return; size[slot] = 1 + size(left[slot]) + size(right[slot]); - 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); + if (size(left[slot]) - 1 > 2 * size(right[slot])) rotate(false, slot, p); + else if (size(left[slot]) * 2 < size(right[slot]) - 1) rotate(true, slot, p); } // Insert ///////////////////////////////////////////////////////////////////////// - private void insert(int index, int arg, int slot, int parent, boolean replace, boolean wentLeft) { + private void insert(int index, int arg, int slot, int p, boolean replace, boolean wentLeft) { int diff = slot <= 0 ? 0 : index - size(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); + balance(slot, p); return; } if (size[arg] != 0) throw new Error("double insertion"); + // we are replacing an existing node if (replace) { - if (diff == 0) { - objects[slot] = objects[arg]; - objects[arg] = null; - left[arg] = right[arg] = size[arg] = 0; - } else { - // since we already clamped the index - throw new Error("this should never happen"); - } - } - + 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 + parent[arg] = parent[slot]; + parent[slot] = arg; if (slot == root) { root = arg; balance(slot, arg); balance(arg, 0); } else { - (left[parent] == slot ? left : right)[parent] = arg; + 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, parent); + balance(arg, p); } } } @@ -269,16 +319,16 @@ public class BalancedTree { // Deletion ////////////////////////////////////////////////////////////////////// - private int delete(int index, int slot, int parent) { + private int delete(int index, int slot, int p) { int diff = index - size(left[slot]); if (diff < 0) { int ret = delete(index, left[slot], slot); - balance(slot, parent); + 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 @@ -286,38 +336,60 @@ public class BalancedTree { // fast path: it has no children if (left[slot] <= 0 && right[slot] <= 0) { - if (parent == 0) root = 0; + if (p == 0) root = 0; else { - int[] side = left[parent] == slot ? left : right; - side[parent] = side[slot]; // fix parent's pointer + int[] side = left[p] == slot ? left : right; + side[p] = side[slot]; // fix parent's pointer } // fast path: it has no left child, so we replace it with its right child } else if (left[slot] <= 0) { - if (parent == 0) root = right[slot]; - else (left[parent] == slot ? left : right)[parent] = right[slot]; // fix parent's pointer - if (right[slot] > 0) left[leftmost(right[slot])] = left[slot]; // fix our successor-leaf's fake right ptr - balance(right[slot], parent); + 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 (parent == 0) root = left[slot]; - else (left[parent] == slot ? left : right)[parent] = left[slot]; // fix parent's pointer - if (left[slot] > 0) right[rightmost(left[slot])] = right[slot]; // fix our successor-leaf's fake right ptr - balance(left[slot], parent); + 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(size(left[slot]) - 1, left[slot], slot); left[left_childs_rightmost] = left[slot]; right[left_childs_rightmost] = right[slot]; - if (parent == 0) root = left_childs_rightmost; - else (left[parent] == slot ? left : right)[parent] = left_childs_rightmost; // fix parent's pointer - balance(left_childs_rightmost, parent); + 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