From 1ece8d661a27c6ca5f94ef291db1eaa9885885d1 Mon Sep 17 00:00:00 2001 From: megacz Date: Fri, 30 Jan 2004 07:42:11 +0000 Subject: [PATCH] 2003/11/27 05:05:10 darcs-hash:20040130074211-2ba56-ddadde43a90f07f7f09f5ebba09c21311b8d98a8.gz --- src/org/xwt/js/JS.java | 2 +- src/org/xwt/util/BalancedTree.java | 48 +++++++++++++++++++----------------- 2 files changed, 27 insertions(+), 23 deletions(-) diff --git a/src/org/xwt/js/JS.java b/src/org/xwt/js/JS.java index 3632250..957b9ad 100644 --- a/src/org/xwt/js/JS.java +++ b/src/org/xwt/js/JS.java @@ -7,7 +7,7 @@ import java.io.*; import java.util.*; /** The minimum set of functionality required for objects which are manipulated by JavaScript */ -public class JS { +public class JS extends org.xwt.util.BalancedTree { // Static Interpreter Control Methods /////////////////////////////////////////////////////////////// diff --git a/src/org/xwt/util/BalancedTree.java b/src/org/xwt/util/BalancedTree.java index 734636f..99ec34f 100644 --- a/src/org/xwt/util/BalancedTree.java +++ b/src/org/xwt/util/BalancedTree.java @@ -18,47 +18,48 @@ public class BalancedTree { // Public API ////////////////////////////////////////////////////////////////////////// /** the number of elements in the tree */ - public int size() { return root == 0 ? 0 : size[root]; } + public final int treeSize() { return root == 0 ? 0 : size[root]; } - /** clamps index to [0..size()] and inserts object o *before* the specified index */ - public void insert(int index, Object o) { + /** clamps index to [0..treeSize()] and inserts object o *before* the specified index */ + public final void insertNode(int index, Object o) { if (index < 0) index = 0; - if (index > size()) index = size(); + if (index > treeSize()) index = treeSize(); int arg = allocateSlot(o); - if (root != 0) { insert(index, arg, root, 0, false); return; } + if (root != 0) { insert(index, arg, root, 0, false, false); return; } root = arg; left[arg] = 0; right[arg] = 0; + size[root] = 1; } - /** clamps index to [0..size()-1] and replaces the object at that index with object o */ - public void replace(int index, Object o) { + /** clamps index to [0..treeSize()-1] and replaces the object at that index with object o */ + public final void replaceNode(int index, Object o) { if (index < 0) index = 0; - if (index > size()) index = size() - 1; + if (index > treeSize()) index = treeSize() - 1; int arg = allocateSlot(o); - if (root != 0) { insert(index, arg, root, 0, true); return; } + if (root != 0) { insert(index, arg, root, 0, true, false); return; } root = arg; left[arg] = 0; right[arg] = 0; } /** returns the index of o; runs in O((log n)^2) time */ - public int index(Object o) { + public final int indexNode(Object o) { 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]) + index(objects[parent]) + 1; + else return size(left[slot]) + indexNode(objects[parent]) + 1; } /** returns the object at index; runs in O(log n) time */ - public Object get(int index) { + public final Object getNode(int index) { return objects[get(index, root)]; } /** deletes the object at index, returning the deleted object */ - public Object delete(int index) { + public final Object deleteNode(int index) { return delete(index, root, 0); } @@ -91,6 +92,7 @@ public class BalancedTree { boolean plus = true; int tries = 1; while (objects[dest] != o) { + if (dest == 0) dest++; dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % objects.length); if (plus) tries++; plus = !plus; @@ -144,8 +146,10 @@ public class BalancedTree { } private void balance(int slot, int parent) { + /* 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]); } @@ -153,11 +157,11 @@ public class BalancedTree { // Insert ///////////////////////////////////////////////////////////////////////// - private void insert(int index, int arg, int slot, int parent, boolean replace) { + private void insert(int index, int arg, int slot, int parent, boolean replace, boolean wentLeft) { int diff = slot <= 0 ? 0 : index - size(left[slot]); - if (slot >= 0 && diff != 0) { - if (diff <= 0) insert(index, arg, left[slot], slot, replace); - else insert(index - size(left[slot]) - 1, arg, right[slot], slot, replace); + if (slot > 0 && diff != 0) { + if (diff < 0) insert(index, arg, left[slot], slot, replace, true); + else insert(index - size(left[slot]) - 1, arg, right[slot], slot, replace, false); balance(slot, parent); return; } @@ -166,17 +170,17 @@ public class BalancedTree { // we become the child of a former leaf if (slot <= 0) { - int[] left = BalancedTree.left[parent] == slot ? BalancedTree.left : BalancedTree.right; - int[] right = BalancedTree.left[parent] == slot ? BalancedTree.right : BalancedTree.left; + int[] left = wentLeft ? BalancedTree.left : BalancedTree.right; + int[] right = wentLeft ? BalancedTree.right : BalancedTree.left; left[arg] = slot; - right[arg] = parent; left[parent] = arg; + right[arg] = -1 * parent; balance(arg, parent); - // we become the child of a preexisting node + // we take the place of a preexisting node } else { left[arg] = left[slot]; // steal slot's left subtree - left[slot] = arg; + left[slot] = -1 * arg; right[arg] = slot; // make slot our right subtree if (slot == root) root = arg; (left[parent] == slot ? left : right)[parent] = arg; -- 1.7.10.4