X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=src%2Forg%2Fibex%2Futil%2FBalancedTree.java;fp=src%2Forg%2Fibex%2Futil%2FBalancedTree.java;h=0000000000000000000000000000000000000000;hb=ac84b5a03467c0853c7275105712ece6c71be1f1;hp=dd993a0dc5e8984003da3e256b66c6c45a36c145;hpb=3f8aa5300e178e8975b0edc896a5a9d303e7bdf3;p=org.ibex.core.git diff --git a/src/org/ibex/util/BalancedTree.java b/src/org/ibex/util/BalancedTree.java deleted file mode 100644 index dd993a0..0000000 --- a/src/org/ibex/util/BalancedTree.java +++ /dev/null @@ -1,433 +0,0 @@ -// 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.ibex.util; - -// FEATURE: private void intersection() { } -// FEATURE: private void union() { } -// 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 */ - public final int treeSize() { - synchronized(BalancedTree.class) { - 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) { - synchronized(BalancedTree.class) { - 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 void replaceNode(int index, Object o) { - synchronized(BalancedTree.class) { - 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 int indexNode(Object o) { - synchronized(BalancedTree.class) { - 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 Object getNode(int index) { - synchronized(BalancedTree.class) { - 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) { - synchronized(BalancedTree.class) { - 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 void clear() { - synchronized(BalancedTree.class) { - 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; - } - } - - // 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 - * 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]; - - /// 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]; - - ///< the number of descendants of this node *including the node itself* - private static int[] size = new int[NUM_SLOTS]; - - - // 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; - if(dest == 0) dest=1; - while (objects[dest] != search || !(alloc || root(dest) == root)) { - dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % objects.length); - if (dest == 0) dest=1; - if (plus) tries++; - plus = !plus; - // FEATURE: GROW - if(tries > MAX_SLOT_DISTANCE) return -1; - } - return dest; - } - - /** 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; - } - - - - // 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 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 ///////////////////////////////////////////////////////////// - - // p p - // | | - // b d - // / \ / \ - // a d < == > b e - // / \ / \ - // c e a c - // 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; - - 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 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 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; - } - - 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; - 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; - 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; - // FEATURE: Might be doing too much work here - left[arg] = slot; - 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] = 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); - 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); - } - } - } - - - // 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(index, left[slot]); - else return slot; - } - - - // 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, p); - return ret; - - // we found the node to delete - } else { - - // 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 - } - - // 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; - } - } - - 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