From: megacz <megacz@xwt.org>
Date: Fri, 30 Jan 2004 07:42:14 +0000 (+0000)
Subject: 2003/11/28 03:06:56
X-Git-Tag: RC3~306
X-Git-Url: http://git.megacz.com/?p=org.ibex.core.git;a=commitdiff_plain;h=3d88386c55793510fc678df98af9c3fb3de7c091

2003/11/28 03:06:56

darcs-hash:20040130074214-2ba56-dcb4b5a96393370164ef015687b72765acf5e7dc.gz
---

diff --git a/src/org/xwt/js/JS.java b/src/org/xwt/js/JS.java
index 957b9ad..28622a3 100644
--- a/src/org/xwt/js/JS.java
+++ b/src/org/xwt/js/JS.java
@@ -114,12 +114,25 @@ public class JS extends org.xwt.util.BalancedTree {
     public static final Object T = Boolean.TRUE;
     public static final Object F = Boolean.FALSE;
 
-    public static final Number N(int i) { return new Integer(i); }
-    public static final Number N(long l) { return new Long(l); }
-    public static final Number N(double d) { return new Double(d); }
-    public static final Number N(String s) { return new Double(s); }
     public static final Boolean B(boolean b) { return b ? Boolean.TRUE : Boolean.FALSE; }
     public static final Boolean B(int i) { return i==0 ? Boolean.FALSE : Boolean.TRUE; }
+    public static final Number N(String s) { return s.indexOf('.') == -1 ? N(Integer.parseInt(s)) : new Double(s); }
+    public static final Number N(double d) { return (int)d == d ? N((int)d) : new Double(d); }
+    public static final Number N(long l) { return N((int)l); }
+
+    private static final Integer[] smallIntCache = new Integer[65535 / 4];
+    private static final Integer[] largeIntCache = new Integer[65535 / 4];
+    public static final Number N(int i) {
+        Integer ret = null;
+        if (i < smallIntCache.length) { ret = smallIntCache[i]; if (ret != null) return ret; }
+        else ret = largeIntCache[i % largeIntCache.length];
+        if (ret == null || ret.intValue() != i) {
+            ret = new Integer(i);
+            if (i < smallIntCache.length) smallIntCache[i] = ret;
+            else largeIntCache[i % largeIntCache.length] = ret;
+        }
+        return ret;
+    }
     
     private static Enumeration emptyEnumeration = new Enumeration() {
             public boolean hasMoreElements() { return false; }
diff --git a/src/org/xwt/util/BalancedTree.java b/src/org/xwt/util/BalancedTree.java
index 0ef3b38..5020547 100644
--- a/src/org/xwt/util/BalancedTree.java
+++ b/src/org/xwt/util/BalancedTree.java
@@ -80,14 +80,19 @@ public class BalancedTree {
 
     /** 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;
-        return delete(index, root, 0);
+        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
@@ -228,46 +233,43 @@ 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) {
-                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) {
-                if (parent == 0) root = left[slot];
-                else (left[parent] == slot ? left : right)[parent] = left[slot];
-                left[slot] = 0;
-                balance(slot, parent);
+
+            // 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
+                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
+                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];
+                (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;
         }
     }