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; }
/** 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
// 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;
}
}