1package tests.persistent.map.util;
2
3import ds.persistent.map.BinaryTree;
4import ds.util.KV;
5
6import static ds.persistent.map.BinaryTree.empty;
7
8public abstract class MainBinaryTree
9 extends tests.util.Main {
10
11 protected BinaryTree t;
12 protected final int n;
13
14 protected MainBinaryTree(int n1) {
15 t = (BinaryTree)empty();
16 n = n1;
17 }
18
19 protected abstract void buildTree();
20 protected abstract void removeAll();
21
22 protected void balanceTree() {
23 startTime("balance tree");
24 t = t.balance();
25 stopTime();
26 }
27
28 protected void lookupAll(int times) {
29 startTime("looking up all elements in tree " + times + " times");
30
31 boolean found = true;
32 for (int j = 0; j < times; ++j)
33 for (KV p : t) {
34 found &= (t.lookup(p.fst) == p.snd);
35 }
36 stopTime();
37 }
38
39 protected void traverse(int times) {
40 startTime("traversing all elements in tree " + times + " times");
41
42 int res = 0;
43 for (int j = 0; j < times; ++j)
44 for (KV p : t) {
45 res += p.fst.key;
46 }
47 stopTime();
48 }
49
50 protected void stats() {
51 if ( n < 10 )
52 msg("t = " + t);
53 msg("t.inv() = " + t.inv());
54 msg("t.size() = " + t.size());
55 msg("t.depth() = " + t.depth());
56 msg("t.minDepth() = " + t.minDepth());
57 msg("t.balanced() = " + t.balanced());
58 msg("");
59 }
60
61 protected void memStats() {
62 msg(t.objStats());
63 msg("");
64 }
65
66 protected void classStats() {
67 msg(BinaryTree.stats());
68 }
69
70 public void run() {
71 nl();
72 buildTree();
73 stats();
74 memStats();
75 traverse(20);
76 lookupAll(20);
77 balanceTree();
78 lookupAll(20);
79 stats();
80 removeAll();
81 stats();
82 classStats();
83 }
84}
Algorithmen & Datenstrukturen mit Java: tests.persistent.map.util.MainBinaryTree
