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=615db24c1ef43fe9e96ca81ba1c4b79ce67ae2bb;hb=3591b88b94a6bb378af3d4abe6eb5233ce583104;hp=0000000000000000000000000000000000000000;hpb=de378041d5ca2aca1a2b5a31ef15ae90a86c977f;p=org.ibex.core.git diff --git a/src/org/ibex/util/BalancedTree.java b/src/org/ibex/util/BalancedTree.java new file mode 100644 index 0000000..615db24 --- /dev/null +++ b/src/org/ibex/util/BalancedTree.java @@ -0,0 +1,395 @@ +// 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 + +/** 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() { return root == 0 ? 0 : size[root]; } + + /** 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(); + 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 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; + 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 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 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 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 = 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; + 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; + } + + /** 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 ///////////////////////////////////////////////////////////////////////// + + 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]); } + + + // 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; + 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 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; + 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; + left[arg] = slot; + 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 { + 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; + } + } + + // 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