1package tests.persistent.map;
2
3import java.util.Iterator;
4import java.util.Random;
5
6import ds.persistent.map.BinaryTree;
7import ds.util.KV;
8import ds.util.K;
9
10import static ds.util.K.mkK;
11import static ds.util.V.mkV;
12import static ds.util.KV.mkPair;
13
14import tests.util.Args;
15
16public class BinaryTreeRandom {
17
18 public static void main(String [] args) {
19 int noOfElems = Args.getInt(args, 0, 1023);
20
21 new Main(noOfElems)
22 .run();
23 }
24
25 private static
26 class Main
27 extends tests.persistent.map.util.MainBinaryTree {
28
29 final Random r;
30
31 Main(int n1) {
32 super(n1);
33 r = new Random(42);
34 }
35
36 protected void buildTree() {
37 buildTreeSimple();
38 buildTreeSmart();
39 }
40
41 protected void buildTreeSimple() {
42 startTime("building binary search tree by inserting " +
43 n +
44 " random integers\n" +
45 "(simple version by stepwise insertion)");
46 for (int i = 0; i < n; ++i) {
47 int k = r.nextInt();
48 t = t.insert(mkK(k), mkV(i));
49 }
50 stopTime();
51 }
52
53 protected void buildTreeSmart() {
54 startTime("building binary search tree by inserting " +
55 n +
56 " random integers\n" +
57 "(with iterator)");
58
59 Iterator<KV> elems
60 = new ds.util.Iterator<KV>() {
61 int i = 0;
62 public boolean hasNext() {
63 return
64 i < n;
65 }
66 public KV next() {
67 int k = r.nextInt();
68 ++i;
69 return
70 mkPair(mkK(k), mkV(i));
71 }
72 };
73 t = BinaryTree.fromIterator(elems);
74
75 stopTime();
76 }
77
78 protected void removeAll() {
79 startTime("removing all elements by stepwise removing the root element");
80
81 for (int i = t.size(); i > 0; --i) {
82 K k = t.findRoot().fst;
83 t = t.remove(k);
84 }
85 stopTime();
86 }
87 }
88}
Algorithmen & Datenstrukturen mit Java: tests.persistent.map.BinaryTreeRandom
