X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=src%2Forg%2Fibex%2Futil%2FBalancedTree.java;h=dd993a0dc5e8984003da3e256b66c6c45a36c145;hb=8a6e58b0ea6c595a9bc89b72febf108ba5a66725;hp=82226c28e3e64f45860ef352c3cd84009eee8b10;hpb=b31b1260164bd52ace312a7b5d8b1a3d9e9ae3a9;p=org.ibex.core.git diff --git a/src/org/ibex/util/BalancedTree.java b/src/org/ibex/util/BalancedTree.java index 82226c2..dd993a0 100644 --- a/src/org/ibex/util/BalancedTree.java +++ b/src/org/ibex/util/BalancedTree.java @@ -12,17 +12,17 @@ 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 { - - // 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 */ @@ -140,9 +140,6 @@ public class BalancedTree { root = 0; } } - - protected void finalize() { clear(); } - // Node Data ///////////////////////////////////////////////////////////////////////// @@ -215,13 +212,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 +257,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 +285,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); @@ -281,32 +301,35 @@ public class BalancedTree { 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; - + // 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 { 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 +373,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 +381,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 +389,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 +401,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 @@ -390,19 +413,19 @@ public class BalancedTree { } } - // Debugging /////////////////////////////////////////////////////////////////////////// - + protected void finalize() { clear(); } + 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