2003/12/29 03:27:44

[org.ibex.core.git] / src / org / xwt / util / BalancedTree.java

diff --git a/src/org/xwt/util/BalancedTree.java b/src/org/xwt/util/BalancedTree.java
index e37e3f8..175ae33 100644 (file)
--- 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 <adam@xwt.org> 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() { }
@@ -24,20 +30,23 @@ 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) {
+    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) {
+    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;
@@ -49,7 +58,7 @@ public class BalancedTree {
     }
 
     /** returns the index of o; runs in O((log n)^2) time unless cache hit */
-    public final int indexNode(Object o) { 
+    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());
@@ -57,11 +66,11 @@ public class BalancedTree {
         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
-        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];
 
         if (cached_index != -1) {
@@ -75,14 +84,16 @@ public class BalancedTree {
                 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) {
+    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;
@@ -182,8 +193,8 @@ public class BalancedTree {
         else if (left[parent] == b)   left[parent] = d;
         else if (right[parent] == b)  right[parent] = d;
         else throw new Error("rotate called with invalid parent");
-        balance(b, d);
-        balance(d, parent);
+        size[b] = 1 + size(left[b]) + size(right[b]);
+        size[d] = 1 + size(left[d]) + size(right[d]);
     }
 
     private void balance(int slot, int parent) {
@@ -236,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);
@@ -298,7 +310,7 @@ 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];
+                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);