💾 Archived View for gmi.noulin.net › gitRepositories › wavlTree › file › test.c.gmi captured on 2023-01-29 at 11:35:54. Gemini links have been rewritten to link to archived content
-=-=-=-=-=-=-
test.c (14410B)
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 "wavlTree.h"
7 #include "wavlTreeNamespaceCleanup.h"
8
9 int argc; char **argv;
10
11 /* enable/disable logging */
12 /* #undef pLog */
13 /* #define pLog(...) */
14
15 wavlTreet x;
16
17 #define assertEquals(A,B) do{\
18 var a = A;\
19 var b = B;\
20 if (a != b) {\
21 AT;\
22 logI(BLD RED"assert failed:"RST" %d != %d\n", a, b);\
23 }\
24 }while(0)
25
26 #define assertNull(p) do{\
27 if (p) {\
28 AT;\
29 logE(BLD RED"assert failed:"RST stringifyExpr(p) " not NULL\n");\
30 }\
31 }while(0)
32
33 #define assertTrue(c) do{\
34 if (!(c)) {\
35 AT;\
36 logE(BLD RED"assert failed: "RST stringifyExpr(c) " expected true\n");\
37 }\
38 }while(0)
39
40 void testTreeHeight() {
41 x.clear(&x);
42 x.put(&x,2, 2);
43 assertEquals(0, x.treeHeight(&x));
44 x.put(&x,3, 3);
45 assertEquals(1, x.treeHeight(&x));
46 x.put(&x,1, 1);
47 x.put(&x,0, 0);
48 assertEquals(2, x.treeHeight(&x));
49 }
50
51 void testInsertDoNothing() {
52 x.clear(&x);
53 x.put(&x,2, 2);
54 x.put(&x,3, 3);
55 assertEquals(0, x.rotations);
56 assertEquals(2, (int)x.root->value);
57 assertEquals(1, x.root->rank);
58
59 x.put(&x,1, 1);
60 assertEquals(2, (int)x.root->value);
61
62 assertEquals(1, x.root->rank);
63 assertEquals(0, x.rotations);
64 }
65
66 void testInsert100() {
67 x.clear(&x);
68 for (int i=0; i<100; i++)
69 x.put(&x,i, i);
70 assertEquals(100, x.count);
71 }
72
73 void testInsertMany() {
74 x.clear(&x);
75 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};
76 for (int i=0; i < ARRAY_SIZE(a); i++)
77 x.put(&x,a[i], a[i]);
78 assertEquals(1193, (int) x.root->value);
79 assertEquals(1767, (int) x.root->right->value);
80 assertEquals(1393, (int) x.root->right->left->value);
81 assertEquals(1921, (int) x.root->right->right->value);
82 assertEquals(1870, (int) x.root->right->right->left->value);
83 assertEquals(1801, (int) x.root->right->right->left->left->value);
84 assertEquals(2130, (int) x.root->right->right->right->value);
85 }
86
87 void testDeleteMany() {
88 x.clear(&x);
89 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};
90 for (int i=0; i < ARRAY_SIZE(a);i++)
91 x.put(&x,a[i], a[i]);
92
93 //x.inOrderTraversal(x.root);
94
95 for (int i=ARRAY_SIZE(a)-1; i > 0; i--) {
96 logI("Deleting: %d value: %d", i, a[i]);
97 x.remove(&x, a[i]);
98 }
99
100 //x.inOrderTraversal(x.root);
101
102 assertEquals(477, (int) x.root->value);
103 assertEquals(0, x.root->rank); // error root rank is 2 should be 0
104 assertNull(x.root->left);
105 assertNull(x.root->right);
106 }
107
108 void testInsertOneLeftRotation() {
109 x.clear(&x);
110 x.put(&x,1, 1);
111 x.put(&x,2, 2);
112 x.put(&x,3, 3);
113
114 assertEquals(1, x.root->rank);
115 assertEquals(2, (int) x.root->value);
116 assertEquals(0, x.root->right->rank);
117 }
118
119 void testInsertTwoLeftRotations() {
120 x.clear(&x);
121 x.put(&x,1, 1);
122 x.put(&x,2, 2);
123 x.put(&x,3, 3);
124 x.put(&x,4, 4);
125 x.put(&x,5, 5);
126
127 assertEquals(2, x.root->rank);
128 assertEquals(2, (int) x.root->value);
129 assertEquals(2, x.rotations);
130 assertEquals(1, x.root->right->rank);
131 assertEquals(0, x.root->left->rank);
132 }
133
134 void testInsertThreeLeftRotations() {
135 x.clear(&x);
136 x.put(&x,1, 1);
137 x.put(&x,2, 2);
138 x.put(&x,3, 3);
139 x.put(&x,4, 4);
140 x.put(&x,5, 5);
141 x.put(&x,6, 6);
142
143 assertEquals(3, x.rotations);
144 assertEquals(4, (int) x.root->value);
145 assertEquals(2, x.root->rank);
146 assertTrue(x.root->right->rank == 1 && x.root->left->rank == 1);
147 }
148
149
150 void testInsertLeftRightRotation() {
151 x.clear(&x);
152 x.put(&x,3, 3);
153 x.put(&x,1, 1);
154 x.put(&x,2, 2);
155
156 assertEquals(2, x.rotations);
157 assertEquals(2, (int) x.root->value);
158 assertEquals(1, x.root->rank);
159 }
160
161 void testInsertRightLeftRotation() {
162 x.clear(&x);
163 x.put(&x,3, 3);
164 x.put(&x,6, 6);
165 x.put(&x,4, 4);
166
167 assertEquals(2, x.rotations);
168 assertEquals(4, (int) x.root->value);
169 assertEquals(1, x.root->rank);
170 }
171
172 void testInsertBuildFibonacciTree() {
173 x.clear(&x);
174 x.put(&x,8, 8);
175 x.put(&x,5, 5);
176 x.put(&x,11, 11);
177 // 3,7,10,12
178 x.put(&x,3, 3); x.put(&x,7, 7); x.put(&x,10, 10); x.put(&x,12, 12);
179 // 2,4,6,9
180 x.put(&x,2, 2); x.put(&x,4, 4); x.put(&x,6, 6); x.put(&x,9, 9);
181 x.put(&x,1, 1);
182 logI("Rotations: %d", x.rotations);
183 assertEquals(0, x.rotations);
184 }
185
186 void testInsertFibAfterDelete() {
187 x.clear(&x);
188 x.put(&x,8, 8); // root
189 x.put(&x,5, 5); x.put(&x,11, 11);
190 // 3,7,10,12
191 x.put(&x,3, 3); x.put(&x,7, 7); x.put(&x,10, 10); x.put(&x,12, 12);
192 // 2,4,6,9
193 x.put(&x,2, 2); x.put(&x,4, 4); x.put(&x,6, 6); x.put(&x,9, 9);
194 x.put(&x,1, 1);
195
196 x.remove(&x, 12);
197 //TODO
198 }
199
200 void testInsert6() {
201 x.clear(&x);
202 for (int i=0; i<6; i++)
203 x.put(&x,i, i);
204 assertEquals(3, x.rotations);
205 assertEquals(3, (int) x.root->value);
206 x.inOrderTraversal(x.root);
207 }
208
209 void testInsertTwoRightRotations() {
210 x.clear(&x);
211 x.put(&x,5, 5);
212 x.put(&x,4, 4);
213 x.put(&x,3, 3);
214 x.put(&x,2, 4);
215 x.put(&x,1, 1);
216
217 assertEquals(2, x.rotations);
218 assertEquals(2, x.root->rank);
219 assertEquals(4, (int) x.root->value);
220 assertEquals(0, x.root->right->rank);
221 assertEquals(1, x.root->left->rank);
222 }
223
224 void testDeleteNoRotation() {
225 x.clear(&x);
226 x.put(&x,2, 2);
227 x.put(&x,3, 3);
228 x.put(&x,1, 1);
229 assertEquals(2, (int)x.root->value);
230
231 // 2(1)
232 // 1(0) 3(0)
233 //x.inOrderTraversal(x.root);
234 //puts("");
235
236 x.remove(&x,3);
237
238 // 2(1)
239 // 1(0) -
240 //x.inOrderTraversal(x.root);
241
242 assertEquals(1, x.root->rank);
243 assertEquals(0, x.rotations);
244
245 // remove root
246 x.remove(&x,2);
247
248 //x.inOrderTraversal(x.root);
249
250 x.remove(&x,1);
251 assertEquals(0, x.count);
252 }
253
254 void testDeleteNoRotationWAVL() {
255 x.clear(&x);
256 x.deleteWAVL = true;
257 x.put(&x,2, 2);
258 x.put(&x,3, 3);
259 x.put(&x,1, 1);
260 assertEquals(2, (int)x.root->value);
261
262 x.remove(&x,3);
263 assertEquals(1, x.root->rank);
264 assertEquals(0, x.rotations);
265
266 // remove root
267 x.remove(&x,2);
268 x.remove(&x,1);
269 assertEquals(0, x.count);
270 }
271
272 void testDeleteNoRotationLeftTallDecrementRank() {
273 x.clear(&x);
274 x.put(&x,2, 2);
275 x.put(&x,3, 3);
276 x.put(&x,1, 1);
277 x.put(&x,0, 0);
278 assertEquals(2, (int)x.root->value);
279
280 x.remove(&x,0);
281 /*
282 2
283 1 3
284 */
285 assertEquals(1, x.root->rank); // error root rank is 2 should be 1
286 assertEquals(0, x.rotations);
287 }
288
289 void testDeleteOneRightRotation() {
290 x.clear(&x);
291 x.put(&x,10, 10);
292 x.put(&x,8, 8); x.put(&x,12, 12);
293 x.put(&x,6, 6);
294
295 x.remove(&x,12);
296 /*
297 8
298 6 10
299 */
300 assertEquals(1, x.rotations);
301 assertEquals(1, x.root->rank);
302 assertEquals(8, (int) x.root->value);
303 }
304
305 void testDeleteOneRightRotationWAVL() {
306 x.clear(&x);
307 x.deleteWAVL = true;
308 x.put(&x,10, 10);
309 x.put(&x,8, 8); x.put(&x,12, 12);
310 x.put(&x,6, 6);
311
312 x.remove(&x,12);
313 /*
314 8
315 6 10
316 */
317 assertEquals(1, x.rotations);
318 assertEquals(2, x.root->rank); // created 2,2 node, non-leaf
319 assertEquals(0, x.root->right->rank);
320 assertEquals(0, x.root->left->rank);
321 assertEquals(8, (int) x.root->value);
322 }
323
324 void testDeleteOneRightRotationSiblingBalanced() {
325 x.clear(&x);
326 x.put(&x,10, 10);
327 x.put(&x,8, 8);x.put(&x,12, 12);
328 x.put(&x,6,6);x.put(&x,9,9);
329
330 assertEquals(0, x.rotations);
331
332 x.remove(&x,12);
333 /* after
334 8
335 6 10
336 9
337 */
338 assertEquals(2, x.root->rank);
339 assertEquals(6, (int) x.root->left->value);
340 assertEquals(1, x.root->right->rank);
341 assertEquals(0, x.root->left->rank);
342 assertEquals(8, (int) x.root->value);
343 assertEquals(1, x.rotations);
344 }
345
346 void testDeleteOneRightRotationSiblingBalancedWAVL() {
347 x.clear(&x);
348 x.deleteWAVL = true;
349 x.put(&x,10, 10);
350 x.put(&x,8, 8);x.put(&x,12, 12);
351 x.put(&x,6,6);x.put(&x,9,9);
352
353 assertEquals(0, x.rotations);
354
355 x.remove(&x,12);
356 /* after
357 8
358 6 10
359 9
360 */
361 assertEquals(2, x.root->rank);
362 assertEquals(6, (int) x.root->left->value);
363 assertEquals(1, x.root->right->rank);
364 assertEquals(0, x.root->right->left->rank);
365 assertEquals(0, x.root->left->rank);
366 assertEquals(8, (int) x.root->value);
367 assertEquals(1, x.rotations);
368 }
369
370 void testDeleteOneLeftRightRotation() {
371 x.clear(&x);
372 x.put(&x,10, 10);
373 x.put(&x,8, 8);
374 x.put(&x,12, 12);
375 x.put(&x,9, 9);
376
377 x.remove(&x,12);
378 /*
379 9
380 8 10
381 */
382
383 assertEquals(0, x.root->right->rank);
384 assertEquals(0, x.root->left->rank);
385 assertEquals(1, x.root->rank);
386 assertEquals(9, (int) x.root->value);
387 assertEquals(2, x.rotations);
388 }
389
390 void testDeleteOneLeftRightRotationWAVL() {
391 x.clear(&x);
392 x.deleteWAVL = true;
393 x.put(&x,10, 10);
394 x.put(&x,8, 8);
395 x.put(&x,12, 12);
396 x.put(&x,9, 9);
397
398 x.remove(&x,12);
399 /*
400 9
401 8 10
402 */
403
404 assertEquals(0, x.root->right->rank);
405 assertEquals(0, x.root->left->rank);
406 assertEquals(2, x.root->rank); // created 2,2 node
407 assertEquals(9, (int) x.root->value);
408 assertEquals(2, x.rotations);
409 }
410
411 void testDelete5() {
412 x.clear(&x);
413 for (int i=0; i<6; i++)
414 x.put(&x,i, i);
415 for (int i=0; i<5; i++) {
416 logI("Root: k %d v %d Deleting: %d\n", x.root->key, x.root->value, i);
417 x.remove(&x,i);
418 }
419 assertEquals(1, x.count);
420 assertEquals(0, x.root->rank);
421 }
422
423 void testDelete5WAVL() {
424 x.clear(&x);
425 x.deleteWAVL = true;
426 for (int i=0; i<6; i++)
427 x.put(&x,i, i);
428
429 // 3(2)
430 // 1(1) 4(1)
431 // 0(0) 2(0) - 5(0)
432 //x.inOrderTraversal(x.root);
433
434 //logI("Rotations before remove: %d\n", x.rotations);
435
436 for (int i=0; i<5; i++) {
437 logI("Root: k %d v %d Deleting: %d\n", x.root->key, x.root->value, i);
438 x.remove(&x,i);
439 }
440
441 //logI("Rotations after remove: %d\n", x.rotations);
442 assertEquals(1, x.count);
443 assertEquals(0, x.root->rank);
444
445 x.remove(&x,5);
446 }
447
448 void testDeleteFibonacciTree() {
449 x.clear(&x);
450 x.put(&x,8, 8); // root
451 x.put(&x,5, 5); x.put(&x,11, 11);
452 // 3,7,10,12
453 x.put(&x,3, 3); x.put(&x,7, 7); x.put(&x,10, 10); x.put(&x,12, 12);
454 // 2,4,6,9
455 x.put(&x,2, 2); x.put(&x,4, 4); x.put(&x,6, 6); x.put(&x,9, 9);
456 x.put(&x,1, 1);
457 logI("Rotations before remove 12 from Fibonacci: %d\n", x.rotations);
458
459 // 8(4)
460 // 5(3) 11(2)
461 // 3(2) 7(1) 10(1) 12(0)
462 // 2(1) 4(0) 6(0) - 9(0) -
463 // 1(0) -
464 //x.inOrderTraversal(x.root);
465 //puts("\n");
466
467 x.remove(&x, 12);
468
469 // 8(4)
470 // 5(3) 11(2)
471 // 3(2) 7(1) 10(1) -
472 // 2(1) 4(0) 6(0) - 9(0) -
473 // 1(0) -
474 //x.inOrderTraversal(x.root);
475
476
477 logI("Rotations after remove 12: %d\n", x.rotations);
478 logI("ROOT: k %d v %d\n", x.root->key, x.root->value);
479 assertEquals(2, x.rotations);
480 assertEquals(5, (int) x.root->value);
481
482 x.remove(&x,4);
483
484 // 8(4)
485 // 5(3) 11(2)
486 // 3(2) 7(1) 10(1) -
487 // 2(1) - 6(0) - 9(0) -
488 // 1(0)
489 //x.inOrderTraversal(x.root);
490
491 assertEquals(2, (int) x.root->left->value);
492 assertEquals(1, x.root->left->rank);
493
494 }
495
496 void testDeleteFibonacciTreeWAVL() {
497 x.clear(&x);
498 x.deleteWAVL = true;
499 x.put(&x,8, 8); // root
500 x.put(&x,5, 5); x.put(&x,11, 11);
501 // 3,7,10,12
502 x.put(&x,3, 3); x.put(&x,7, 7); x.put(&x,10, 10); x.put(&x,12, 12);
503 // 2,4,6,9
504 x.put(&x,2, 2); x.put(&x,4, 4); x.put(&x,6, 6); x.put(&x,9, 9);
505 x.put(&x,1, 1);
506
507 // 8(4)
508 // 5(3) 11(2)
509 // 3(2) 7(1) 10(1) 12(0)
510 // 2(1) 4(0) 6(0) - 9(0) -
511 // 1(0) -
512
513 x.remove(&x, 12);
514
515 logI("Rotations after remove 12: %d\n", x.rotations);
516 logI("ROOT: k %d v %d\n", x.root->key, x.root->value);
517 assertEquals(1, x.rotations);
518 assertEquals(8, (int) x.root->value);
519 assertEquals(0, x.root->right->right->rank);
520 assertEquals(0, x.root->right->left->rank);
521 assertEquals(2, x.root->right->rank);
522 }
523
524 void testDeleteAlmostFibonacciTreeWAVL() {
525 x.clear(&x);
526 x.deleteWAVL = true;
527 x.put(&x,8, 8); // root
528 x.put(&x,5, 5); x.put(&x,12, 12);
529 // 3,7,10,12
530 x.put(&x,3, 3); x.put(&x,7, 7); x.put(&x,10, 10); x.put(&x,13, 13);
531 // 2,4,6,9,11
532 x.put(&x,2, 2); x.put(&x,4, 4); x.put(&x,6, 6); x.put(&x,9, 9); x.put(&x,11,11);
533 x.put(&x,1, 1);
534
535 //x.inOrderTraversal(x.root);
536 //puts("\n");
537
538 x.remove(&x, 13);
539
540 // 8(4)
541 // 5(3) 12(2)
542 // 3(2) 7(1) 10(1) -
543 // 2(1) 4(0) 6(0) - 9(0) 11(0)
544 // 1(0) -
545 //x.inOrderTraversal(x.root);
546
547 /* int g[] = {8,5,12,3,7,10,13,2,4,6,9,11,1}; */
548 /* range(i, ARRAY_SIZE(g)) { */
549 /* var v = x.get(&x, g[i]); */
550 /* if (v == -1) { */
551 /* logI("key %d, "BLD YLW"not found"RST, g[i]); */
552 /* } */
553 /* else { */
554 /* logI("key %d, value %d", g[i], x.get(&x, g[i])); */
555 /* } */
556 /* } */
557
558 logI("Rotations after remove 13: %d\n", x.rotations);
559 logI("ROOT: k %d v %d\n", x.root->key, x.root->value);
560 assertEquals(1, x.rotations);
561 assertEquals(8, (int) x.root->value);
562 assertEquals(1, x.root->right->right->rank);
563 assertEquals(0, x.root->right->left->rank);
564 assertEquals(2, x.root->right->rank);
565 }
566
567 void testDeleteManyWAVL() {
568 x.clear(&x);
569 x.deleteWAVL = true;
570 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};
571 for (int i=0; i < ARRAY_SIZE(a); i++) {
572 logI("put: %d,\n", a[i]);
573 x.put(&x,a[i], a[i]);
574 }
575 puts("\n");
576
577 for (int i=ARRAY_SIZE(a)-1; i > 0; i--) {
578 logI("Deleting: %d value: %d\n", i, a[i]);
579 x.remove(&x, a[i]);
580 }
581
582 x.inOrderTraversal(x.root);
583
584 assertEquals(477, (int) x.root->value);
585 assertEquals(0, x.root->rank);
586 assertNull(x.root->left);
587 assertNull(x.root->right);
588 }
589
590
591 int main(int ARGC, char** ARGV) {
592
593 argc = ARGC; argv = ARGV;
594
595 initLibsheepy(ARGV[0]);
596 setLogMode(LOG_FUNC);
597
598 wavlTreeinit(&x);
599
600 testDelete5();
601 testDelete5WAVL();
602 testDeleteAlmostFibonacciTreeWAVL();
603 testDeleteFibonacciTree();
604 testDeleteFibonacciTreeWAVL();
605 testDeleteMany();
606 testDeleteManyWAVL();
607 testDeleteNoRotation();
608 testDeleteNoRotationLeftTallDecrementRank();
609 testDeleteNoRotationWAVL();
610 testDeleteOneLeftRightRotation();
611 testDeleteOneLeftRightRotationWAVL();
612 testDeleteOneRightRotation();
613 testDeleteOneRightRotationSiblingBalanced();
614 testDeleteOneRightRotationSiblingBalancedWAVL();
615 testDeleteOneRightRotationWAVL();
616 testInsert100();
617 testInsert6();
618 testInsertBuildFibonacciTree();
619 testInsertDoNothing();
620 testInsertFibAfterDelete();
621 testInsertLeftRightRotation();
622 testInsertMany();
623 testInsertOneLeftRotation();
624 testInsertRightLeftRotation();
625 testInsertThreeLeftRotations();
626 testInsertTwoLeftRotations();
627 testInsertTwoRightRotations();
628 testTreeHeight();
629
630 x.clear(&x);
631 }
632 // vim: set expandtab ts=2 sw=2: