Algorithmen & Datenstrukturen mit Java: Test mit sortiertem Einfügen
| Algorithmen & Datenstrukturen mit Java: Test mit sortiertem Einfügen |
|
1package tests.persistent.map;
2
3import ds.persistent.map.RedBlackTree;
4import ds.util.KV;
5import ds.util.K;
6
7import static ds.util.K.mkK;
8import static ds.util.V.mkV;
9import static ds.util.KV.mkPair;
10
11import tests.util.Args;
12
13public class RedBlackWorstCase {
14
15 public static void main(String [] args) {
16 int noOfElems = Args.getInt(args, 0, 1023);
17
18 (new Main(noOfElems)).run();
19 }
20
21 private static
22 class Main
23 extends tests.util.Main {
24 RedBlackTree t;
25 final int n;
26
27 Main(int n1) {
28 t = RedBlackTree.empty();
29 n = n1;
30 }
31
32 void buildTree() {
33 startTime("building red-black tree by inserting " +
34 n +
35 " elements in ascending order (worst case)");
36 for (int i = 0; i < n; ++i) {
37 t = t.insert(mkK(i), mkV(i));
38 }
39 stopTime();
40 }
41
42 void deleteTree() {
43 startTime("deleting a red-black tree by removing " +
44 n +
45 " elements in ascending order");
46 for (int i = 0; i < n; ++i) {
47 // msg("" + i);
48 t = t.remove(mkK(i));
49 // msg("" + t);
50 }
51 stopTime();
52 }
53
54 void lookupAll(int times) {
55 startTime("looking up all elements in tree " + times + " times");
56
57 boolean found = true;
58 for (int j = 0; j < times; ++j)
59 for (KV p : t) {
60 found &= (t.lookup(p.fst) == p.snd);
61 }
62 stopTime();
63 }
64
65 void traverse(int times) {
66 startTime("traversing all elements in tree " + times + " times");
67
68 int res = 0;
69 for (int j = 0; j < times; ++j)
70 for (KV p : t) {
71 res += p.fst.key;
72 }
73 stopTime();
74 }
75
76 void stats() {
77 if ( n < 10 )
78 msg("t = " + t);
79 msg("t.size() = " + t.size());
80 msg("t.depth() = " + t.depth());
81 msg("t.minDepth() = " + t.minDepth());
82 msg("t.inv() = " + t.inv());
83 msg("");
84 }
85
86 void memStats() {
87 msg(t.objStats());
88 }
89
90 void classStats() {
91 msg(RedBlackTree.stats());
92 }
93
94 public void run() {
95 nl();
96 buildTree();
97 stats();
98 memStats();
99 classStats();
100 traverse(20);
101 lookupAll(20);
102 deleteTree();
103 stats();
104 classStats();
105 }
106 }
107}
|
| Letzte Änderung: 20.12.2017 | © Prof. Dr. Uwe Schmidt |
