tree

Log

Files

Refs

README

LICENSE

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: