From 962334c1b6f5cbce360343b6863e902b007233df Mon Sep 17 00:00:00 2001 From: adam Date: Thu, 23 Sep 2004 04:40:28 +0000 Subject: [PATCH] imported Brian's updated version of BalancedTree darcs-hash:20040923044028-5007d-89bf532d2f555596259b3c33a29a16d1af386715.gz --- src/org/ibex/util/BalancedTree.java | 233 +++++++++++++++++++++++++++++++---- 1 file changed, 206 insertions(+), 27 deletions(-) diff --git a/src/org/ibex/util/BalancedTree.java b/src/org/ibex/util/BalancedTree.java index 82226c2..ee36a81 100644 --- a/src/org/ibex/util/BalancedTree.java +++ b/src/org/ibex/util/BalancedTree.java @@ -12,9 +12,11 @@ package org.ibex.util; // FEATURE: private void subset() { } // FEATURE: grow if we run out of slots +// FEATURE: Add the cached_index stuff back in + /** a weight-balanced tree with fake leaves */ public class BalancedTree { - + private static final boolean DEBUG = true; // Instance Variables /////////////////////////////////////////////////////////////////// @@ -22,6 +24,8 @@ public class BalancedTree { private int cached_index = -1; private int cached_slot = -1; + + private FinalizationHelper fh; // Public API ////////////////////////////////////////////////////////////////////////// @@ -35,6 +39,7 @@ public class BalancedTree { /** clamps index to [0..treeSize()] and inserts object o *before* the specified index */ public final void insertNode(int index, Object o) { synchronized(BalancedTree.class) { + if(DEBUG) leafCheck(); if(o == null) throw new Error("can't insert nulls in the balanced tree"); cached_slot = cached_index = -1; if (index < 0) index = 0; @@ -43,16 +48,20 @@ public class BalancedTree { if (root != 0) { insert(index, arg, root, 0, false, false); } else { + if(fh == null) fh = new FinalizationHelper(this); root = arg; left[arg] = right[arg] = parent[arg] = 0; size[arg] = 1; } + if(DEBUG) check(); + if(DEBUG) leafCheck(); } } /** clamps index to [0..treeSize()-1] and replaces the object at that index with object o */ public final void replaceNode(int index, Object o) { synchronized(BalancedTree.class) { + if(DEBUG) leafCheck(); 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"); @@ -60,6 +69,8 @@ public class BalancedTree { if (index >= treeSize()) index = treeSize() - 1; int arg = allocateSlot(o); insert(index, arg, root, 0, true, false); + if(DEBUG) check(); + if(DEBUG) leafCheck(); } } @@ -92,6 +103,7 @@ public class BalancedTree { /** returns the object at index; runs in O(log n) time unless cache hit */ public final Object getNode(int index) { synchronized(BalancedTree.class) { + if(DEBUG) leafCheck(); if (index == cached_index) return objects[cached_slot]; if (cached_index != -1) { @@ -117,12 +129,15 @@ public class BalancedTree { /** deletes the object at index, returning the deleted object */ public final Object deleteNode(int index) { synchronized(BalancedTree.class) { + if(DEBUG) leafCheck(); 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; + if(DEBUG) check(); + if(DEBUG) leafCheck(); return ret; } } @@ -139,10 +154,8 @@ public class BalancedTree { } while(i != 0); root = 0; } + if(DEBUG) check(); } - - protected void finalize() { clear(); } - // Node Data ///////////////////////////////////////////////////////////////////////// @@ -215,13 +228,35 @@ public class BalancedTree { // Helpers ///////////////////////////////////////////////////////////////////////// + // FEATURE: These might be faster if they aren't recursive 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]); } + private int next(int node) { + if(right[node] > 0) { + node = right[node]; + while(left[node] > 0) node = left[node]; + return node; + } else { + int p = parent[node]; + while(right[p] == node) { node = p; p = parent[node]; }; + return p; + } + } + + private int prev(int node) { + if(left[node] > 0) { + node = left[node]; + while(right[node] > 0) node = right[node]; + return node; + } else { + int p = parent[node]; + while(left[p] == node) { node = p; p = parent[node]; } + return p; + } + } // Rotation and Balancing ///////////////////////////////////////////////////////////// @@ -238,19 +273,20 @@ public class BalancedTree { int[] right = toTheLeft ? BalancedTree.right : BalancedTree.left; int d = right[b]; int c = left[d]; - if (d <= 0) throw new Error("rotation error"); + if (d == 0) throw new Error("rotation error"); left[d] = b; - right[b] = c <= 0 ? -d : c; + right[b] = c; parent[b] = d; parent[d] = p; - if(c > 0) parent[c] = b; + 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]); + size[d] = 1 + sizeof(left[d]) + sizeof(right[d]); } private void balance(int slot, int p) { @@ -265,8 +301,8 @@ public class BalancedTree { // 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) { + 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); @@ -275,38 +311,45 @@ public class BalancedTree { if (size[arg] != 0) throw new Error("double insertion"); + if(DEBUG) check(); + // 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; + else throw new Error("should never happen"); 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; + 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; - + if(DEBUG) check(); + // we become the child of a former leaf - } else if (slot <= 0) { + } else if (slot == 0) { int[] left = wentLeft ? BalancedTree.left : BalancedTree.right; int[] right = wentLeft ? BalancedTree.right : BalancedTree.left; + // FEATURE: Might be doing too much work here left[arg] = slot; - left[p] = arg; - right[arg] = -1 * p; + right[arg] = 0; parent[arg] = p; + left[p] = arg; balance(arg, p); // we take the place of a preexisting node } else { + if(DEBUG) check(); left[arg] = left[slot]; // steal slot's left subtree - left[slot] = -1 * arg; + left[slot] = 0; right[arg] = slot; // make slot our right subtree parent[arg] = parent[slot]; parent[slot] = arg; + if(left[arg] != 0) parent[left[arg]] = arg; if (slot == root) { root = arg; balance(slot, arg); @@ -350,7 +393,7 @@ public class BalancedTree { } else { // fast path: it has no children - if (left[slot] <= 0 && right[slot] <= 0) { + if (left[slot] == 0 && right[slot] == 0) { if (p == 0) root = 0; else { int[] side = left[p] == slot ? left : right; @@ -358,7 +401,7 @@ public class BalancedTree { } // fast path: it has no left child, so we replace it with its right child - } else if (left[slot] <= 0) { + } 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; @@ -366,7 +409,7 @@ public class BalancedTree { balance(right[slot], p); // fast path; it has no right child, so we replace it with its left child - } else if (right[slot] <= 0) { + } 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; @@ -378,8 +421,8 @@ public class BalancedTree { 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; + 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 @@ -389,22 +432,158 @@ public class BalancedTree { return slot; } } + + static class FinalizationHelper { + private BalancedTree bt; + FinalizationHelper(BalancedTree bt) { this.bt = bt; } + protected void finalize() { bt.clear(); } + } // Debugging /////////////////////////////////////////////////////////////////////////// + public void check() { check(false); } + public void check(boolean expensive) { + if(expensive) System.err.println("--> Running expensive balanced tree checks"); + try { + if(expensive) + for(int i=0;i 0) { + if(parent[left[node]] != node) throw new Error("parent node mismatch on left child of " + node); + check(left[node]); + } + if(right[node] > 0) { + if(parent[right[node]] != node) throw new Error("parent node mismatch on right child of " + node); + check(right[node]); + } + } + 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 0) { + for (int i = 0;i 0) { + System.err.println("forward: " + backward.length); + for (int i = 0;i 0) { + System.err.println("backward: " + backward.length); + for (int i = backward.length-1;i>=0;i--) { + System.err.println(backward[i]); + } + } + } + + public int[] getLeavesForward() { + int[] leaves = new int[size[root]]; + if (size[root] > 0) { + leaves[0] = leftmost(root); + for (int i=1;i < leaves.length;i++) { + leaves[i] = next(leaves[i-1]); + } + } + return leaves; + } + + public int[] getLeavesBackward() { + int[] leaves = new int[size[root]]; + if (size[root] > 0) { + leaves[0] = rightmost(root); + for (int i=1;i < leaves.length;i++) { + leaves[i] = prev(leaves[i-1]); + } + } + return leaves; + } + + public void validateTree() { + if(root == 0) System.err.println("Tree is empty"); + else validateTree(root,0,false); + System.err.println(""); + } + private void validateTree(int node,int indent,boolean l) { + if(node < 0) {} + else if(node == 0) {} + else { + System.err.println((l?"Prev: " : "Next: ") + -node); + validateTree(left[node],indent+1,true); + validateTree(right[node],indent+1,false); + } + } + } -- 1.7.10.4