X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=src%2Forg%2Fxwt%2Futil%2FBalancedTree.java;h=e442db3b80007741fa16fe2f5e29cd260aadc111;hb=5a42fe8ca9bdfc070dbf860d10d3f288e87e9a41;hp=0ef3b38d1b9bd1958c9d78ea73bb314dd3908c35;hpb=4f0bf4330a75e521ac12262e4f7ea350c80d6eeb;p=org.ibex.core.git diff --git a/src/org/xwt/util/BalancedTree.java b/src/org/xwt/util/BalancedTree.java index 0ef3b38..e442db3 100644 --- a/src/org/xwt/util/BalancedTree.java +++ b/src/org/xwt/util/BalancedTree.java @@ -1,4 +1,10 @@ -// Copyright 2003 Adam Megacz, see the COPYING file for licensing [GPL] +// 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.xwt.util; // FEATURE: private void intersection() { } @@ -15,8 +21,8 @@ public class BalancedTree { private int root = 0; ///< the slot of the root element - private int cached_index = 0; - private int cached_slot = 0; + private int cached_index = -1; + private int cached_slot = -1; // Public API ////////////////////////////////////////////////////////////////////////// @@ -25,20 +31,23 @@ public class BalancedTree { /** clamps index to [0..treeSize()] and inserts object o *before* the specified index */ public final void insertNode(int index, Object o) { - cached_slot = cached_index = 0; + 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); return; } - root = arg; - left[arg] = 0; - right[arg] = 0; - size[root] = 1; + if (root != 0) { + insert(index, arg, root, 0, false, false); + } else { + root = arg; + left[arg] = 0; + right[arg] = 0; + size[root] = 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) { - cached_slot = cached_index = 0; + cached_slot = cached_index = -1; if (index < 0) index = 0; if (index > treeSize()) index = treeSize() - 1; int arg = allocateSlot(o); @@ -50,44 +59,53 @@ public class BalancedTree { /** returns the index of o; runs in O((log n)^2) time unless cache hit */ public final int indexNode(Object o) { - if (objects[cached_slot] == o) return cached_index; + 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 - else return size(left[slot]) + indexNode(objects[parent]) + 1; + return size(left[slot]) + indexNode(objects[parent]) + 1; } /** returns the object at index; runs in O(log n) time unless cache hit */ public final Object getNode(int index) { if (index == cached_index) return objects[cached_slot]; - 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 (cached_index != 0 && (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]; + 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) { - cached_slot = cached_index = 0; - return delete(index, root, 0); + cached_slot = cached_index = -1; + int del = delete(index, root, 0); + left[del] = right[del] = size[del] = 0; + Object ret = objects[del]; + objects[del] = null; + return ret; } // Node Data ///////////////////////////////////////////////////////////////////////// - private final static int NUM_SLOTS = 265 * 1024; + private final static int NUM_SLOTS = 64 * 1024; /** * Every object inserted into *any* tree gets a "slot" in this @@ -98,9 +116,20 @@ public class BalancedTree { * object will have multiple slots. */ private static Object[] objects = new Object[NUM_SLOTS]; - private static int[] left = new int[NUM_SLOTS]; ///< if positive: left child's slot; if negative: predecessor's slot - private static int[] right = new int[NUM_SLOTS]; ///< if positive: right child's slot; if negative: successor's slot - private static int[] size = new int[NUM_SLOTS]; ///< the number of descendants of this node *including the node itself* + + /// 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 number of descendants of this node *including the node itself* + private static int[] size = new int[NUM_SLOTS]; // Slot Management ////////////////////////////////////////////////////////////////////// @@ -157,6 +186,7 @@ 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"); left[d] = b; right[b] = c; if (parent == 0) root = d; @@ -164,15 +194,14 @@ public class BalancedTree { else if (right[parent] == b) right[parent] = d; else throw new Error("rotate called with invalid parent"); size[b] = 1 + size(left[b]) + size(right[b]); - balance(b, d); size[d] = 1 + size(left[d]) + size(right[d]); - balance(d, parent); } private void balance(int slot, int parent) { + 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); - size[slot] = 1 + size(left[slot]) + size(right[slot]); } @@ -190,6 +219,17 @@ public class BalancedTree { if (size[arg] != 0) throw new Error("double insertion"); + 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"); + } + } + // we become the child of a former leaf if (slot <= 0) { int[] left = wentLeft ? BalancedTree.left : BalancedTree.right; @@ -207,6 +247,7 @@ public class BalancedTree { if (slot == root) { root = arg; balance(slot, arg); + balance(arg, 0); } else { (left[parent] == slot ? left : right)[parent] = arg; balance(slot, arg); @@ -228,46 +269,54 @@ public class BalancedTree { // Deletion ////////////////////////////////////////////////////////////////////// - private Object delete(int index, int slot, int parent) { + private int delete(int index, int slot, int parent) { int diff = index - size(left[slot]); if (diff < 0) { - Object ret = delete(index, left[slot], slot); + int ret = delete(index, left[slot], slot); balance(slot, parent); return ret; } else if (diff > 0) { - Object ret = delete(diff - 1, right[slot], slot); + int ret = delete(diff - 1, right[slot], slot); balance(slot, parent); return ret; + // we found the node to delete } else { - if (left[slot] == 0) { + + // fast path: it has no children + if (left[slot] <= 0 && right[slot] <= 0) { + if (parent == 0) root = 0; + else { + int[] side = left[parent] == slot ? left : right; + side[parent] = 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]; - right[slot] = 0; - balance(slot, parent); - } else if (right[slot] == 0) { + 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); + + // 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]; - left[slot] = 0; - balance(slot, parent); + 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); + + // node to be deleted has two children, so we replace it with its left child's rightmost descendant } else { - Object replacement_object = delete(index - 1, slot, parent); - int replacement = allocateSlot(replacement_object); - if (replacement != 0) { - left[replacement] = left[slot]; - right[replacement] = right[slot]; - } - if (parent == 0) root = replacement; - else (left[parent] == slot ? left : right)[parent] = replacement; - left[slot] = 0; - right[slot] = 0; - balance(replacement, parent); + int left_childs_rightmost = delete(size(left[slot]) - 1, left[slot], slot); + left[left_childs_rightmost] = left[slot]; + left[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); } - Object ret = objects[slot]; - size[slot] = 0; - objects[slot] = null; - return ret; + + return slot; } }