projects
/
org.ibex.core.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
move JS's Hashtable to JS.O
[org.ibex.core.git]
/
src
/
org
/
ibex
/
util
/
BalancedTree.java
diff --git
a/src/org/ibex/util/BalancedTree.java
b/src/org/ibex/util/BalancedTree.java
index
54e5a71
..
24c474d
100644
(file)
--- a/
src/org/ibex/util/BalancedTree.java
+++ b/
src/org/ibex/util/BalancedTree.java
@@
-25,8
+25,6
@@
public class BalancedTree {
private int cached_index = -1;
private int cached_slot = -1;
private int cached_index = -1;
private int cached_slot = -1;
- private FinalizationHelper fh;
-
// Public API //////////////////////////////////////////////////////////////////////////
/** the number of elements in the tree */
// Public API //////////////////////////////////////////////////////////////////////////
/** the number of elements in the tree */
@@
-47,7
+45,6
@@
public class BalancedTree {
if (root != 0) {
insert(index, arg, root, 0, false, false);
} else {
if (root != 0) {
insert(index, arg, root, 0, false, false);
} else {
- if(fh == null) fh = new FinalizationHelper(this);
root = arg;
left[arg] = right[arg] = parent[arg] = 0;
size[arg] = 1;
root = arg;
left[arg] = right[arg] = parent[arg] = 0;
size[arg] = 1;
@@
-267,7
+264,6
@@
public class BalancedTree {
int d = right[b];
int c = left[d];
if (d == 0) throw new Error("rotation error");
int d = right[b];
int c = left[d];
if (d == 0) throw new Error("rotation error");
- if(DEBUG) check();
left[d] = b;
right[b] = c;
left[d] = b;
right[b] = c;
@@
-280,9
+276,7
@@
public class BalancedTree {
else if (right[p] == b) right[p] = d;
else throw new Error("rotate called with invalid parent");
size[b] = 1 + sizeof(left[b]) + sizeof(right[b]);
else if (right[p] == b) right[p] = d;
else throw new Error("rotate called with invalid parent");
size[b] = 1 + sizeof(left[b]) + sizeof(right[b]);
- size[d] = 1 + sizeof(left[d]) + sizeof(right[d]);
-
- if(DEBUG) try { check(); } catch(Error e) { System.err.println("rotate: " + toTheLeft + "," + b + "," + p); throw e; }
+ size[d] = 1 + sizeof(left[d]) + sizeof(right[d]);
}
private void balance(int slot, int p) {
}
private void balance(int slot, int p) {
@@
-335,7
+329,6
@@
public class BalancedTree {
right[arg] = 0;
parent[arg] = p;
left[p] = arg;
right[arg] = 0;
parent[arg] = p;
left[p] = arg;
- if(DEBUG) check();
balance(arg, p);
// we take the place of a preexisting node
balance(arg, p);
// we take the place of a preexisting node
@@
-349,14
+342,12
@@
public class BalancedTree {
if(left[arg] != 0) parent[left[arg]] = arg;
if (slot == root) {
root = arg;
if(left[arg] != 0) parent[left[arg]] = arg;
if (slot == root) {
root = arg;
- if(DEBUG) check();
balance(slot, arg);
balance(arg, 0);
} else {
if (left[p] == slot) left[p] = arg;
else if (right[p] == slot) right[p] = arg;
else throw new Error("should never happen");
balance(slot, arg);
balance(arg, 0);
} else {
if (left[p] == slot) left[p] = arg;
else if (right[p] == slot) right[p] = arg;
else throw new Error("should never happen");
- if(DEBUG) check();
balance(slot, arg);
balance(arg, p);
}
balance(slot, arg);
balance(arg, p);
}
@@
-431,12
+422,8
@@
public class BalancedTree {
return slot;
}
}
return slot;
}
}
-
- static class FinalizationHelper {
- private BalancedTree bt;
- FinalizationHelper(BalancedTree bt) { this.bt = bt; }
- protected void finalize() { bt.clear(); }
- }
+
+ protected void finalize() { clear(); }
// Debugging ///////////////////////////////////////////////////////////////////////////
// Debugging ///////////////////////////////////////////////////////////////////////////
@@
-450,6
+437,12
@@
public class BalancedTree {
if(parent[root] != 0) throw new Error("parent of the root isn't 0");
if(left[0] != 0 || right[0] != 0 || size[0] != 0 || parent[0] != 0)
throw new Error("someone messed with [0]");
if(parent[root] != 0) throw new Error("parent of the root isn't 0");
if(left[0] != 0 || right[0] != 0 || size[0] != 0 || parent[0] != 0)
throw new Error("someone messed with [0]");
+
+ int c = 0;
+ int n = leftmost(root);
+ while(n != 0) { c++; n = next(n); }
+ if(c != size[root]) throw new Error("size[] mismatch");
+
if(root != 0) check(root);
} catch(Error e) {
printTree();
if(root != 0) check(root);
} catch(Error e) {
printTree();
@@
-481,13
+474,13
@@
public class BalancedTree {
if(node == 0) System.err.println("None");
else {
System.err.print("" + node + ": " + objects[node]);
if(node == 0) System.err.println("None");
else {
System.err.print("" + node + ": " + objects[node]);
- System.err.println(" Parent: " + parent[node]);
+ System.err.println(" Parent: " + parent[node] + " Size: " + size[node]);
printTree(left[node],indent+1,true);
printTree(right[node],indent+1,false);
}
}
printTree(left[node],indent+1,true);
printTree(right[node],indent+1,false);
}
}
- public static void main(String[] args) {
+ /*public static void main(String[] args) {
BalancedTree t = new BalancedTree();
for(int i=0;i<args.length;i++)
t.insertNode(i,args[i]);
BalancedTree t = new BalancedTree();
for(int i=0;i<args.length;i++)
t.insertNode(i,args[i]);
@@
-498,5
+491,5
@@
public class BalancedTree {
for(int n = t.rightmost(t.root); n != 0; n = t.prev(n)) {
System.err.println("Prev: " + n);
}
for(int n = t.rightmost(t.root); n != 0; n = t.prev(n)) {
System.err.println("Prev: " + n);
}
- }
+ }*/
}
}