2003/11/27 05:05:10

darcs-hash:20040130074211-2ba56-ddadde43a90f07f7f09f5ebba09c21311b8d98a8.gz

diff --git a/src/org/xwt/js/JS.java b/src/org/xwt/js/JS.java
index 3632250..957b9ad 100644 (file)
--- 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 (file)
--- 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;