wavlTest.c (10309B)
1 #! /usr/bin/env sheepy
2 /* or direct path to sheepy: #! /usr/local/bin/sheepy */
3
4 /* Libsheepy documentation: http://spartatek.se/libsheepy/ */
5 #include "libsheepyObject.h"
6 #include "wavl.h"
7
8 int argc; char **argv;
9
10 /* enable/disable logging */
11 /* #undef pLog */
12 /* #define pLog(...) */
13
14 wavlDef(/* scope */, w /* wt wavl tree type and wNodet node type */, W /* function suffix: initW...*/, u32 /* keyType*/, u32 /* valueType */);
15
16 void freeKV(u32* /* keyType */ key, u32* /* valueType*/ value) {
17 }
18
19 #define FREEFUNC freeKV
20 #define CMPFUNC CMP
21
22 wavlFunctions(/* scope */, w /* wt wavl tree type*/, W /* function suffix: initW...*/, u32 /* keyType*/, u32 /* valueType */, -1 /* null key */, -1 /* null value */);
23
24 /* declare tree */
25 wt x;
26
27 #define assertEquals(A,B) do{\
28 var a = A;\
29 var b = B;\
30 if (a != b) {\
31 AT;\
32 logI(BLD RED"assert failed:"RST" %d != %d\n", a, b);\
33 }\
34 }while(0)
35
36 #define assertNull(p) do{\
37 if (p) {\
38 AT;\
39 logE(BLD RED"assert failed:"RST stringifyExpr(p) " not NULL\n");\
40 }\
41 }while(0)
42
43 #define assertTrue(c) do{\
44 if (!(c)) {\
45 AT;\
46 logE(BLD RED"assert failed: "RST stringifyExpr(c) " expected true\n");\
47 }\
48 }while(0)
49
50 void testTreeHeight() {
51 emptyW(&x);
52 addW(&x,2, 2);
53 assertEquals(0, heightW(&x));
54 addW(&x,3, 3);
55 assertEquals(1, heightW(&x));
56 addW(&x,1, 1);
57 addW(&x,0, 0);
58 assertEquals(2, heightW(&x));
59 }
60
61 void testInsertDoNothing() {
62 emptyW(&x);
63 addW(&x,2, 2);
64 addW(&x,3, 3);
65 assertEquals(0, x.rotations);
66 assertEquals(2, (int)x.root->value);
67 assertEquals(1, x.root->rank);
68
69 addW(&x,1, 1);
70 assertEquals(2, (int)x.root->value);
71
72 assertEquals(1, x.root->rank);
73 assertEquals(0, x.rotations);
74 }
75
76 void testInsert100() {
77 emptyW(&x);
78 for (int i=0; i<100; i++)
79 addW(&x,i, i);
80 assertEquals(100, x.count);
81 }
82
83 void testInsertMany() {
84 emptyW(&x);
85 int a[] = {477, 1193, 2130,398,1393,946,422,1381,1767,830,570,1085,741,598,1658,1801,487,1921,1918,258,135,975,1870};
86 for (int i=0; i < ARRAY_SIZE(a); i++)
87 addW(&x,a[i], a[i]);
88 assertEquals(1193, (int) x.root->value);
89 assertEquals(1767, (int) x.root->right->value);
90 assertEquals(1393, (int) x.root->right->left->value);
91 assertEquals(1921, (int) x.root->right->right->value);
92 assertEquals(1870, (int) x.root->right->right->left->value);
93 assertEquals(1801, (int) x.root->right->right->left->left->value);
94 assertEquals(2130, (int) x.root->right->right->right->value);
95 }
96
97 void testInsertOneLeftRotation() {
98 emptyW(&x);
99 addW(&x,1, 1);
100 addW(&x,2, 2);
101 addW(&x,3, 3);
102
103 assertEquals(1, x.root->rank);
104 assertEquals(2, (int) x.root->value);
105 assertEquals(0, x.root->right->rank);
106 }
107
108 void testInsertTwoLeftRotations() {
109 emptyW(&x);
110 addW(&x,1, 1);
111 addW(&x,2, 2);
112 addW(&x,3, 3);
113 addW(&x,4, 4);
114 addW(&x,5, 5);
115
116 assertEquals(2, x.root->rank);
117 assertEquals(2, (int) x.root->value);
118 assertEquals(2, x.rotations);
119 assertEquals(1, x.root->right->rank);
120 assertEquals(0, x.root->left->rank);
121 }
122
123 void testInsertThreeLeftRotations() {
124 emptyW(&x);
125 addW(&x,1, 1);
126 addW(&x,2, 2);
127 addW(&x,3, 3);
128 addW(&x,4, 4);
129 addW(&x,5, 5);
130 addW(&x,6, 6);
131
132 assertEquals(3, x.rotations);
133 assertEquals(4, (int) x.root->value);
134 assertEquals(2, x.root->rank);
135 assertTrue(x.root->right->rank == 1 && x.root->left->rank == 1);
136 }
137
138
139 void testInsertLeftRightRotation() {
140 emptyW(&x);
141 addW(&x,3, 3);
142 addW(&x,1, 1);
143 addW(&x,2, 2);
144
145 assertEquals(2, x.rotations);
146 assertEquals(2, (int) x.root->value);
147 assertEquals(1, x.root->rank);
148 }
149
150 void testInsertRightLeftRotation() {
151 emptyW(&x);
152 addW(&x,3, 3);
153 addW(&x,6, 6);
154 addW(&x,4, 4);
155
156 assertEquals(2, x.rotations);
157 assertEquals(4, (int) x.root->value);
158 assertEquals(1, x.root->rank);
159 }
160
161 void testInsertBuildFibonacciTree() {
162 emptyW(&x);
163 addW(&x,8, 8);
164 addW(&x,5, 5);
165 addW(&x,11, 11);
166 // 3,7,10,12
167 addW(&x,3, 3); addW(&x,7, 7); addW(&x,10, 10); addW(&x,12, 12);
168 // 2,4,6,9
169 addW(&x,2, 2); addW(&x,4, 4); addW(&x,6, 6); addW(&x,9, 9);
170 addW(&x,1, 1);
171 logI("Rotations: %d", x.rotations);
172 assertEquals(0, x.rotations);
173 }
174
175 void testInsertFibAfterDelete() {
176 emptyW(&x);
177 addW(&x,8, 8); // root
178 addW(&x,5, 5); addW(&x,11, 11);
179 // 3,7,10,12
180 addW(&x,3, 3); addW(&x,7, 7); addW(&x,10, 10); addW(&x,12, 12);
181 // 2,4,6,9
182 addW(&x,2, 2); addW(&x,4, 4); addW(&x,6, 6); addW(&x,9, 9);
183 addW(&x,1, 1);
184
185 delW(&x, 12);
186 //TODO
187 }
188
189 void testInsert6() {
190 emptyW(&x);
191 for (int i=0; i<6; i++)
192 addW(&x,i, i);
193 assertEquals(3, x.rotations);
194 assertEquals(3, (int) x.root->value);
195 // TODO x.inOrderTraversal(x.root);
196 }
197
198 void testInsertTwoRightRotations() {
199 emptyW(&x);
200 addW(&x,5, 5);
201 addW(&x,4, 4);
202 addW(&x,3, 3);
203 addW(&x,2, 4);
204 addW(&x,1, 1);
205
206 assertEquals(2, x.rotations);
207 assertEquals(2, x.root->rank);
208 assertEquals(4, (int) x.root->value);
209 assertEquals(0, x.root->right->rank);
210 assertEquals(1, x.root->left->rank);
211 }
212
213 void testDeleteNoRotationWAVL() {
214 emptyW(&x);
215 addW(&x,2, 2);
216 addW(&x,3, 3);
217 addW(&x,1, 1);
218 assertEquals(2, (int)x.root->value);
219
220 delW(&x,3);
221 assertEquals(1, x.root->rank);
222 assertEquals(0, x.rotations);
223
224 // remove root
225 delW(&x,2);
226 delW(&x,1);
227 assertEquals(0, x.count);
228 }
229
230 void testDeleteOneRightRotationWAVL() {
231 emptyW(&x);
232 addW(&x,10, 10);
233 addW(&x,8, 8); addW(&x,12, 12);
234 addW(&x,6, 6);
235
236 delW(&x,12);
237 /*
238 8
239 6 10
240 */
241 assertEquals(1, x.rotations);
242 assertEquals(2, x.root->rank); // created 2,2 node, non-leaf
243 assertEquals(0, x.root->right->rank);
244 assertEquals(0, x.root->left->rank);
245 assertEquals(8, (int) x.root->value);
246 }
247
248 void testDeleteOneRightRotationSiblingBalancedWAVL() {
249 emptyW(&x);
250 addW(&x,10, 10);
251 addW(&x,8, 8);addW(&x,12, 12);
252 addW(&x,6,6);addW(&x,9,9);
253
254 assertEquals(0, x.rotations);
255
256 delW(&x,12);
257 /* after
258 8
259 6 10
260 9
261 */
262 assertEquals(2, x.root->rank);
263 assertEquals(6, (int) x.root->left->value);
264 assertEquals(1, x.root->right->rank);
265 assertEquals(0, x.root->right->left->rank);
266 assertEquals(0, x.root->left->rank);
267 assertEquals(8, (int) x.root->value);
268 assertEquals(1, x.rotations);
269 }
270
271 void testDeleteOneLeftRightRotationWAVL() {
272 emptyW(&x);
273 addW(&x,10, 10);
274 addW(&x,8, 8);
275 addW(&x,12, 12);
276 addW(&x,9, 9);
277
278 delW(&x,12);
279 /*
280 9
281 8 10
282 */
283
284 assertEquals(0, x.root->right->rank);
285 assertEquals(0, x.root->left->rank);
286 assertEquals(2, x.root->rank); // created 2,2 node
287 assertEquals(9, (int) x.root->value);
288 assertEquals(2, x.rotations);
289 }
290
291 void testDelete5WAVL() {
292 emptyW(&x);
293 for (int i=0; i<6; i++)
294 addW(&x,i, i);
295
296 // 3(2)
297 // 1(1) 4(1)
298 // 0(0) 2(0) - 5(0)
299 //x.inOrderTraversal(x.root);
300
301 //logI("Rotations before remove: %d\n", x.rotations);
302
303 for (int i=0; i<5; i++) {
304 logI("Root: k %d v %d Deleting: %d\n", x.root->key, x.root->value, i);
305 delW(&x,i);
306 }
307
308 //logI("Rotations after remove: %d\n", x.rotations);
309 assertEquals(1, x.count);
310 assertEquals(0, x.root->rank);
311
312 delW(&x,5);
313 }
314
315 void testDeleteFibonacciTreeWAVL() {
316 emptyW(&x);
317 addW(&x,8, 8); // root
318 addW(&x,5, 5); addW(&x,11, 11);
319 // 3,7,10,12
320 addW(&x,3, 3); addW(&x,7, 7); addW(&x,10, 10); addW(&x,12, 12);
321 // 2,4,6,9
322 addW(&x,2, 2); addW(&x,4, 4); addW(&x,6, 6); addW(&x,9, 9);
323 addW(&x,1, 1);
324
325 // 8(4)
326 // 5(3) 11(2)
327 // 3(2) 7(1) 10(1) 12(0)
328 // 2(1) 4(0) 6(0) - 9(0) -
329 // 1(0) -
330
331 delW(&x, 12);
332
333 logI("Rotations after remove 12: %d\n", x.rotations);
334 logI("ROOT: k %d v %d\n", x.root->key, x.root->value);
335 assertEquals(1, x.rotations);
336 assertEquals(8, (int) x.root->value);
337 assertEquals(0, x.root->right->right->rank);
338 assertEquals(0, x.root->right->left->rank);
339 assertEquals(2, x.root->right->rank);
340 }
341
342 void testDeleteAlmostFibonacciTreeWAVL() {
343 emptyW(&x);
344 addW(&x,8, 8); // root
345 logVarG(getW(&x, 8));
346 addW(&x,5, 5); addW(&x,12, 12);
347 // 3,7,10,12
348 addW(&x,3, 3); addW(&x,7, 7); addW(&x,10, 10); addW(&x,13, 13);
349 // 2,4,6,9,11
350 addW(&x,2, 2); addW(&x,4, 4); addW(&x,6, 6); addW(&x,9, 9); addW(&x,11,11);
351 addW(&x,1, 1);
352
353 //x.inOrderTraversal(x.root);
354 //puts("\n");
355
356 delW(&x, 13);
357
358 // 8(4)
359 // 5(3) 12(2)
360 // 3(2) 7(1) 10(1) -
361 // 2(1) 4(0) 6(0) - 9(0) 11(0)
362 // 1(0) -
363 //x.inOrderTraversal(x.root);
364
365 /* int g[] = {8,5,12,3,7,10,13,2,4,6,9,11,1}; */
366 /* range(i, ARRAY_SIZE(g)) { */
367 /* var v = x.get(&x, g[i]); */
368 /* if (v == -1) { */
369 /* logI("key %d, "BLD YLW"not found"RST, g[i]); */
370 /* } */
371 /* else { */
372 /* logI("key %d, value %d", g[i], x.get(&x, g[i])); */
373 /* } */
374 /* } */
375
376 logI("Rotations after remove 13: %d\n", x.rotations);
377 logI("ROOT: k %d v %d\n", x.root->key, x.root->value);
378 assertEquals(1, x.rotations);
379 assertEquals(8, (int) x.root->value);
380 assertEquals(1, x.root->right->right->rank);
381 assertEquals(0, x.root->right->left->rank);
382 assertEquals(2, x.root->right->rank);
383 }
384
385 void testDeleteManyWAVL() {
386 emptyW(&x);
387 int a[] = {477,1193,2130,398,1393,946,422,1381,1767,830,570,1085,741,598,1658,1801,487,1921,1918,258,135,975,1870};
388 for (int i=0; i < ARRAY_SIZE(a); i++) {
389 logI("put: %d,\n", a[i]);
390 addW(&x,a[i], a[i]);
391 }
392 puts("\n");
393
394 for (int i=ARRAY_SIZE(a)-1; i > 0; i--) {
395 logI("Deleting: %d value: %d\n", i, a[i]);
396 delW(&x, a[i]);
397 }
398
399 // TODO x.inOrderTraversal(x.root);
400
401 assertEquals(477, (int) x.root->value);
402 assertEquals(0, x.root->rank);
403 assertNull(x.root->left);
404 assertNull(x.root->right);
405 }
406
407
408 int main(int ARGC, char** ARGV) {
409
410 argc = ARGC; argv = ARGV;
411
412 initLibsheepy(ARGV[0]);
413 setLogMode(LOG_FUNC);
414
415 initW(&x);
416
417 testDelete5WAVL();
418 testDeleteAlmostFibonacciTreeWAVL();
419 testDeleteFibonacciTreeWAVL();
420 testDeleteManyWAVL();
421 testDeleteNoRotationWAVL();
422 testDeleteOneLeftRightRotationWAVL();
423 testDeleteOneRightRotationSiblingBalancedWAVL();
424 testDeleteOneRightRotationWAVL();
425 testInsert100();
426 testInsert6();
427 testInsertBuildFibonacciTree();
428 testInsertDoNothing();
429 testInsertFibAfterDelete();
430 testInsertLeftRightRotation();
431 testInsertMany();
432 testInsertOneLeftRotation();
433 testInsertRightLeftRotation();
434 testInsertThreeLeftRotations();
435 testInsertTwoLeftRotations();
436 testInsertTwoRightRotations();
437 testTreeHeight();
438
439 freeW(&x);
440 }
441 // vim: set expandtab ts=2 sw=2: