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: