5 #include <AD/trees/avl.h>
6 #include <AD/trees/splay.h>
7 #include <AD/trees/leftist.h>
8 #include <AD/trees/pagoda.h>
10 typedef const char * string
;
12 void print_tree (BinaryTree
<string
,string
>& tree
, Ix i
)
13 { if (i
== 0) { printf("."); return; }
14 printf("%s(",tree
.key(i
));
15 print_tree(tree
,tree
.left(i
));
17 print_tree(tree
,tree
.right(i
));
22 { AVLTree
<string
,string
> avl
;
23 SplayTree
<string
,string
> splay
;
24 LeftistTree
<string
,string
> leftist
;
25 Pagoda
<string
,string
> pagoda
;
27 static struct { string first
, last
; } authors
[] =
28 { { "Edgar", "Doctorow" },
30 { "Vladimir", "Nabokov" },
31 { "Pablo", "Neruda", },
32 { "William", "Faulkner", },
33 { "Ernest", "Hemingway" },
34 { "Gabriel", "Garcia Marquez" },
35 { "Isabel", "Allende" },
36 { "Thomas", "Pynchon" },
37 { "Kurt", "Vonnegurt" },
39 { "Norman", "Mailer" },
42 static struct { string first
, last
; } old_authors
[] =
43 { { "William", "Shakespear" },
45 { "Thomas", "Jefferson" }
48 int size
= sizeof(authors
)/sizeof(authors
[0]);
53 for (i
= 0; i
< sizeof(old_authors
)/sizeof(old_authors
[0]); i
++) {
54 avl
.insert(old_authors
[i
].first
, old_authors
[i
].last
);
55 assert(avl
.contains(old_authors
[i
].first
));
56 assert(avl
.avl_balanced());
57 splay
.insert(old_authors
[i
].first
, old_authors
[i
].last
);
58 assert(splay
.contains(old_authors
[i
].first
));
61 for (i
= 0; i
< size
; i
++) {
62 avl
.insert(authors
[i
].first
, authors
[i
].last
);
63 assert(avl
.contains(authors
[i
].first
));
64 assert(avl
.avl_balanced());
65 splay
.insert(authors
[i
].first
, authors
[i
].last
);
66 assert(splay
.contains(authors
[i
].first
));
69 printf( "AVL tree: size = %d\n", avl
.size());
70 for (count
= 0, ix
= avl
.first(); ix
; ix
= avl
.next(ix
), count
++)
71 printf("[%s %s] ", avl
.key(ix
), avl
.value(ix
));
73 assert(count
== size
);
75 for (count
= 0, ix
= avl
.last(); ix
; ix
= avl
.prev(ix
), count
++);
76 assert(count
== size
);
78 printf( "Splay tree: size = %d\n", splay
.size());
79 for (count
= 0, ix
= splay
.first(); ix
; ix
= splay
.next(ix
), count
++)
80 printf("[%s %s] ", splay
.key(ix
), splay
.value(ix
));
82 assert(count
== size
);
84 for (count
= 0, ix
= splay
.last(); ix
; ix
= splay
.prev(ix
), count
++);
85 assert(count
== size
);
87 for (i
= 0; i
< size
; i
++) {
88 assert(avl
.remove(authors
[i
].first
));
89 assert(avl
.lookup(authors
[i
].first
) == 0);
90 assert(avl
.avl_balanced());
91 for (count
= 0, ix
= avl
.first(); ix
; ix
= avl
.next(ix
), count
++);
92 assert(count
== size
- i
- 1);
93 for (count
= 0, ix
= avl
.last(); ix
; ix
= avl
.prev(ix
), count
++);
94 assert(count
== size
- i
- 1);
96 assert(avl
.size() == 0);
98 for (i
= 0; i
< size
; i
++) {
99 assert(splay
.remove(authors
[i
].first
));
100 assert(splay
.lookup(authors
[i
].first
) == 0);
101 for (count
= 0, ix
= splay
.first(); ix
; ix
= splay
.next(ix
), count
++);
102 assert(count
== size
- i
- 1);
103 for (count
= 0, ix
= splay
.last(); ix
; ix
= splay
.prev(ix
), count
++);
104 assert(count
== size
- i
- 1);
106 assert(splay
.size() == 0);
108 for (i
= 0; i
< size
; i
++)
109 leftist
.insert(authors
[i
].first
,authors
[i
].last
);
110 assert(leftist
.size() == size
);
112 for (i
= 0; i
< size
; i
++)
113 pagoda
.insert(authors
[i
].first
,authors
[i
].last
);
114 assert(pagoda
.size() == size
);
116 while (! leftist
.is_empty()) {
118 printf("[%s %s] ",leftist
.key(ix
),leftist
.value(ix
));
119 assert(leftist
.delete_min());
122 assert(leftist
.size() == 0);
124 while (! pagoda
.is_empty()) {
126 printf("[%s %s] ",pagoda
.key(ix
),pagoda
.value(ix
));
127 assert(pagoda
.delete_min());
130 assert(pagoda
.size() == 0);