test.c - wavlTree - wavl tree: weak AVL Tree

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:
	wavlTree wavl tree: weak AVL Tree
	git clone https://noulin.net/git/wavlTree.git
	Log \| Files \| Refs \| README \| LICENSE