X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=src%2Forg%2Fxwt%2Futil%2FBalancedTree.java;h=175ae33a3b10be5fd352427b9f098da11678b37b;hb=4ebc8fdd36b23d350924cc54b08fc74276249d0d;hp=502054772b93ee3c62c0a613303ef24186e54f9e;hpb=3d88386c55793510fc678df98af9c3fb3de7c091;p=org.ibex.core.git diff --git a/src/org/xwt/util/BalancedTree.java b/src/org/xwt/util/BalancedTree.java index 5020547..175ae33 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 ////////////////////////////////////////////////////////////////////////// @@ -24,21 +30,24 @@ public class BalancedTree { 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 void insertNode(int index, Object o) { - cached_slot = cached_index = 0; + public final synchronized void insertNode(int index, Object o) { + 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; + public final synchronized void replaceNode(int index, Object o) { + cached_slot = cached_index = -1; if (index < 0) index = 0; if (index > treeSize()) index = treeSize() - 1; int arg = allocateSlot(o); @@ -49,39 +58,43 @@ 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; + public final synchronized int indexNode(Object o) { + 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]) + (parent <= 0 ? 0 : indexNode(objects[parent])) + 1; } /** returns the object at index; runs in O(log n) time unless cache hit */ - public final Object getNode(int index) { + public final synchronized 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) { - // FIXME handle root deletion here - cached_slot = cached_index = 0; + public final synchronized Object deleteNode(int index) { + cached_slot = cached_index = -1; int del = delete(index, root, 0); left[del] = right[del] = size[del] = 0; Object ret = objects[del]; @@ -103,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 ////////////////////////////////////////////////////////////////////// @@ -162,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; @@ -169,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]); } @@ -195,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; @@ -212,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); @@ -248,15 +284,25 @@ public class BalancedTree { // we found the node to delete } else { + // 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 - if (left[slot] < 0) { - (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 left ptr + } else if (left[slot] <= 0) { + if (parent == 0) root = right[slot]; + 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) { - (left[parent] == slot ? left : right)[parent] = left[slot]; // fix parent's pointer + } else if (right[slot] <= 0) { + if (parent == 0) root = left[slot]; + 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); @@ -264,8 +310,9 @@ public class BalancedTree { } else { int left_childs_rightmost = delete(size(left[slot]) - 1, left[slot], slot); left[left_childs_rightmost] = left[slot]; - left[left_childs_rightmost] = right[slot]; - (left[parent] == slot ? left : right)[parent] = left_childs_rightmost; // fix parent's pointer + right[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); }