WINGs/bagtree.c

   1
   2
   3
   4
   5 #include <stdlib.h>
   6 #include <string.h>
   7
   8 #include "WUtil.h"
   9
  10
  11 typedef struct W_Node {
  12     struct W_Node *parent;
  13     struct W_Node *left;
  14     struct W_Node *right;
  15     int color;
  16
  17     void *data;
  18     int index;
  19 } W_Node;
  20
  21
  22 typedef struct W_TreeBag {
  23     W_Node *root;
  24
  25     W_Node *nil;                       /* sentinel */
  26
  27     int count;
  28 } W_TreeBag;
  29
  30
  31
  32 static int getItemCount(WMBag *self);
  33 static int appendBag(WMBag *self, WMBag *bag);
  34 static int putInBag(WMBag *self, void *item);
  35 static int insertInBag(WMBag *self, int index, void *item);
  36 static int removeFromBag(WMBag *bag, void *item);
  37 static int deleteFromBag(WMBag *bag, int index);
  38 static void *getFromBag(WMBag *bag, int index);
  39 static int countInBag(WMBag *bag, void *item);
  40 static int firstInBag(WMBag *bag, void *item);
  41 static void *replaceInBag(WMBag *bag, int index, void *item);
  42 static int sortBag(WMBag *bag, int (*comparer)(const void*, const void*));
  43 static void emptyBag(WMBag *bag);
  44 static void freeBag(WMBag *bag);
  45 static void mapBag(WMBag *bag, void (*function)(void*, void*), void *data);
  46 static int findInBag(WMBag *bag, int (*match)(void*));;
  47 static void *first(WMBag *bag, WMBagIterator *ptr);
  48 static void *last(WMBag *bag, WMBagIterator *ptr);
  49 static void *next(WMBag *bag, WMBagIterator *ptr);
  50 static void *previous(WMBag *bag, WMBagIterator *ptr);
  51 static void *iteratorAtIndex(WMBag *bag, int index, WMBagIterator *ptr);
  52 static int indexForIterator(WMBag *bag, WMBagIterator ptr);
  53
  54
  55 static W_BagFunctions bagFunctions = {
  56     getItemCount,
  57         appendBag,
  58         putInBag,
  59         insertInBag,
  60         removeFromBag,
  61         deleteFromBag,
  62         getFromBag,
  63         firstInBag,
  64         countInBag,
  65         replaceInBag,
  66         sortBag,
  67         emptyBag,
  68         freeBag,
  69         mapBag,
  70         findInBag,
  71         first,
  72         last,
  73         next,
  74         previous,
  75         iteratorAtIndex,
  76         indexForIterator
  77 };
  78
  79
  80
  81
  82 #define IS_LEFT(node) (node == node->parent->left)
  83 #define IS_RIGHT(node) (node == node->parent->right)
  84
  85
  86
  87 static void leftRotate(W_TreeBag *tree, W_Node *node)
  88 {
  89     W_Node *node2;
  90
  91     node2 = node->right;
  92     node->right = node2->left;
  93
  94     node2->left->parent = node;
  95
  96     node2->parent = node->parent;
  97
  98     if (node->parent == tree->nil) {
  99         tree->root = node2;
 100     } else {
 101         if (IS_LEFT(node)) {
 102             node->parent->left = node2;
 103         } else {
 104             node->parent->right = node2;
 105         }
 106     }
 107     node2->left = node;
 108     node->parent = node2;
 109 }
 110
 111
 112
 113 static void rightRotate(W_TreeBag *tree, W_Node *node)
 114 {
 115     W_Node *node2;
 116
 117     node2 = node->left;
 118     node->left = node2->right;
 119
 120     node2->right->parent = node;
 121
 122     node2->parent = node->parent;
 123
 124     if (node->parent == tree->nil) {
 125         tree->root = node2;
 126     } else {
 127         if (IS_LEFT(node)) {
 128             node->parent->left = node2;
 129         } else {
 130             node->parent->right = node2;
 131         }
 132     }
 133     node2->right = node;
 134     node->parent = node2;
 135 }
 136
 137
 138
 139 static void treeInsert(W_TreeBag *tree, W_Node *node)
 140 {
 141     W_Node *y = tree->nil;
 142     W_Node *x = tree->root;
 143
 144     while (x != tree->nil) {
 145         y = x;
 146         if (node->index < x->index)
 147             x = x->left;
 148         else
 149             x = x->right;
 150     }
 151     node->parent = y;
 152     if (y == tree->nil)
 153         tree->root = node;
 154     else if (node->index < y->index)
 155         y->left = node;
 156     else
 157         y->right = node;
 158 }
 159
 160
 161 static void rbTreeInsert(W_TreeBag *tree, W_Node *node)
 162 {
 163     W_Node *y;
 164
 165     treeInsert(tree, node);
 166
 167     node->color = 'R';
 168
 169     while (node != tree->root && node->parent->color == 'R') {
 170         if (IS_LEFT(node->parent)) {
 171             y = node->parent->parent->right;
 172
 173             if (y->color == 'R') {
 174
 175                 node->parent->color = 'B';
 176                 y->color = 'B';
 177                 node->parent->parent->color = 'R';
 178                 node = node->parent->parent;
 179
 180             } else {
 181                 if (IS_RIGHT(node)) {
 182                     node = node->parent;
 183                     leftRotate(tree, node);
 184                 }
 185                 node->parent->color = 'B';
 186                 node->parent->parent->color = 'R';
 187                 rightRotate(tree, node->parent->parent);
 188             }
 189         } else {
 190             y = node->parent->parent->left;
 191
 192             if (y->color == 'R') {
 193
 194                 node->parent->color = 'B';
 195                 y->color = 'B';
 196                 node->parent->parent->color = 'R';
 197                 node = node->parent->parent;
 198
 199             } else {
 200                 if (IS_LEFT(node)) {
 201                     node = node->parent;
 202                     rightRotate(tree, node);
 203                 }
 204                 node->parent->color = 'B';
 205                 node->parent->parent->color = 'R';
 206                 leftRotate(tree, node->parent->parent);
 207             }
 208         }
 209     }
 210     tree->root->color = 'B';
 211 }
 212
 213
 214
 215 static void rbDeleteFixup(W_TreeBag *tree, W_Node *node)
 216 {
 217     W_Node *w;
 218
 219     while (node != tree->root && node->color == 'B') {
 220         if (IS_LEFT(node)) {
 221             w = node->parent->right;
 222             if (w->color == 'R') {
 223                 w->color = 'B';
 224                 node->parent->color = 'R';
 225                 leftRotate(tree, node->parent);
 226                 w = node->parent->right;
 227             }
 228             if (w->left->color == 'B' && w->right->color == 'B') {
 229                 w->color = 'R';
 230                 node = node->parent;
 231             } else {
 232                 if (w->right->color == 'B') {
 233                     w->left->color = 'B';
 234                     w->color = 'R';
 235                     rightRotate(tree, w);
 236                     w = node->parent->right;
 237                 }
 238                 w->color = node->parent->color;
 239                 node->parent->color = 'B';
 240                 w->right->color = 'B';
 241                 leftRotate(tree, node->parent);
 242                 node = tree->root;
 243             }
 244         } else {
 245             w = node->parent->left;
 246             if (w->color == 'R') {
 247                 w->color = 'B';
 248                 node->parent->color = 'R';
 249                 leftRotate(tree, node->parent);
 250                 w = node->parent->left;
 251             }
 252             if (w->left->color == 'B' && w->right->color == 'B') {
 253                 w->color = 'R';
 254                 node = node->parent;
 255             } else {
 256                 if (w->left->color == 'B') {
 257                     w->right->color = 'B';
 258                     w->color = 'R';
 259                     rightRotate(tree, w);
 260                     w = node->parent->left;
 261                 }
 262                 w->color = node->parent->color;
 263                 node->parent->color = 'B';
 264                 w->left->color = 'B';
 265                 leftRotate(tree, node->parent);
 266                 node = tree->root;
 267             }
 268         }
 269     }
 270     node->color = 'B';
 271 }
 272
 273
 274 static W_Node *treeMinimum(W_Node *node, W_Node *nil)
 275 {
 276     while (node->left != nil)
 277         node = node->left;
 278     return node;
 279 }
 280
 281
 282 static W_Node *treeMaximum(W_Node *node, W_Node *nil)
 283 {
 284     while (node->right != nil)
 285         node = node->right;
 286     return node;
 287 }
 288
 289
 290 static W_Node *treeSuccessor(W_Node *node, W_Node *nil)
 291 {
 292     W_Node *y;
 293
 294     if (node->right != nil) {
 295         return treeMinimum(node->right, nil);
 296     }
 297     y = node->parent;
 298     while (y != nil && node == y->right) {
 299         node = y;
 300         y = y->parent;
 301     }
 302     return y;
 303 }
 304
 305
 306 static W_Node *treePredecessor(W_Node *node, W_Node *nil)
 307 {
 308     W_Node *y;
 309
 310     if (node->left != nil) {
 311         return treeMaximum(node->left, nil);
 312     }
 313     y = node->parent;
 314     while (y != nil && node == y->left) {
 315         node = y;
 316         y = y->parent;
 317     }
 318     return y;
 319 }
 320
 321
 322 static W_Node *rbTreeDelete(W_TreeBag *tree, W_Node *node)
 323 {
 324     W_Node *nil = tree->nil;
 325     W_Node *x, *y;
 326
 327     if (node->left == nil || node->right == nil) {
 328         y = node;
 329     } else {
 330         y = treeSuccessor(node, nil);
 331     }
 332
 333     if (y->left != nil) {
 334         x = y->left;
 335     } else {
 336         x = y->right;
 337     }
 338
 339     x->parent = y->parent;
 340
 341     if (y->parent == nil) {
 342         tree->root = x;
 343     } else {
 344         if (IS_LEFT(y)) {
 345             y->parent->left = x;
 346         } else {
 347             y->parent->right = x;
 348         }
 349     }
 350     if (y != node) {
 351         node->index = y->index;
 352         node->data = y->data;
 353     }
 354     if (y->color == 'B') {
 355         rbDeleteFixup(tree, x);
 356     }
 357
 358     return y;
 359 }
 360
 361
 362
 363 static W_Node *treeSearch(W_Node *root, W_Node *nil, int index)
 364 {
 365     if (root == nil || root->index == index) {
 366         return root;
 367     }
 368
 369     if (index < root->index) {
 370         return treeSearch(root->left, nil, index);
 371     } else {
 372         return treeSearch(root->right, nil, index);
 373     }
 374 }
 375
 376
 377 static W_Node *treeFind(W_Node *root, W_Node *nil, void *data)
 378 {
 379     W_Node *tmp;
 380
 381     if (root == nil || root->data == data)
 382         return root;
 383
 384     tmp = treeFind(root->left, nil, data);
 385     if (tmp != nil)
 386         return tmp;
 387
 388     tmp = treeFind(root->right, nil, data);
 389
 390     return tmp;
 391 }
 392
 393
 394
 395
 396
 397 #if 0
 398 static char buf[512];
 399
 400 static void printNodes(W_Node *node, W_Node *nil, int depth)
 401 {
 402     if (node == nil) {
 403         return;
 404     }
 405
 406     printNodes(node->left, nil, depth+1);
 407
 408     memset(buf, ' ', depth*2);
 409     buf[depth*2] = 0;
 410     if (IS_LEFT(node))
 411         printf("%s/(%2i\n", buf, node->index);
 412     else
 413         printf("%s\\(%2i\n", buf, node->index);
 414
 415     printNodes(node->right, nil, depth+1);
 416 }
 417
 418
 419 void PrintTree(WMBag *bag)
 420 {
 421     W_TreeBag *tree = (W_TreeBag*)bag->data;
 422
 423     printNodes(tree->root, tree->nil, 0);
 424 }
 425 #endif
 426
 427
 428
 429
 430 #define SELF ((W_TreeBag*)self->data)
 431
 432 WMBag *WMCreateTreeBag(void)
 433 {
 434     return WMCreateTreeBagWithDestructor(NULL);
 435 }
 436
 437
 438 WMBag *WMCreateTreeBagWithDestructor(void (*destructor)(void*))
 439 {
 440     WMBag *bag;
 441     W_TreeBag *tree;
 442
 443     bag = wmalloc(sizeof(WMBag));
 444
 445     bag->data = tree = wmalloc(sizeof(W_TreeBag));
 446     memset(tree, 0, sizeof(W_TreeBag));
 447
 448     tree->nil = wmalloc(sizeof(W_Node));
 449     memset(tree->nil, 0, sizeof(W_Node));
 450     tree->nil->left = tree->nil->right = tree->nil->parent = tree->nil;
 451     tree->nil->index = WBNotFound;
 452
 453     tree->root = tree->nil;
 454
 455     bag->destructor = destructor;
 456
 457     bag->func = bagFunctions;
 458
 459     return bag;
 460 }
 461
 462
 463 static int getItemCount(WMBag *self)
 464 {
 465     return SELF->count;
 466 }
 467
 468
 469 static int appendBag(WMBag *self, WMBag *bag)
 470 {
 471     WMBagIterator ptr;
 472     void *data;
 473
 474     for (data = first(bag, &ptr); data != NULL; data = next(bag, &ptr)) {
 475         if (!putInBag(self, data))
 476             return 0;
 477     }
 478
 479     return 1;
 480 }
 481
 482
 483 static int putInBag(WMBag *self, void *item)
 484 {
 485     W_Node *ptr;
 486
 487     ptr = wmalloc(sizeof(W_Node));
 488
 489     ptr->data = item;
 490     ptr->index = SELF->count;
 491     ptr->left = SELF->nil;
 492     ptr->right = SELF->nil;
 493     ptr->parent = SELF->nil;
 494
 495     rbTreeInsert(SELF, ptr);
 496
 497     SELF->count++;
 498
 499     return 1;
 500 }
 501
 502
 503 static int insertInBag(WMBag *self, int index, void *item)
 504 {
 505     W_Node *ptr;
 506
 507     ptr = wmalloc(sizeof(W_Node));
 508
 509     ptr->data = item;
 510     ptr->index = index;
 511     ptr->left = SELF->nil;
 512     ptr->right = SELF->nil;
 513     ptr->parent = SELF->nil;
 514
 515     rbTreeInsert(SELF, ptr);
 516
 517     while ((ptr = treeSuccessor(ptr, SELF->nil))) {
 518         ptr->index++;
 519     }
 520
 521
 522     SELF->count++;
 523
 524     return 1;
 525 }
 526
 527
 528
 529 static int removeFromBag(WMBag *self, void *item)
 530 {
 531     W_Node *ptr = treeFind(SELF->root, SELF->nil, item);
 532
 533     if (ptr != SELF->nil) {
 534
 535         SELF->count--;
 536
 537         ptr = rbTreeDelete(SELF, ptr);
 538         free(ptr);
 539
 540         return 1;
 541     } else {
 542         return 0;
 543     }
 544 }
 545
 546
 547 static int deleteFromBag(WMBag *self, int index)
 548 {
 549     W_Node *ptr = treeSearch(SELF->root, SELF->nil, index);
 550
 551     if (ptr != SELF->nil) {
 552
 553         SELF->count--;
 554
 555         ptr = rbTreeDelete(SELF, ptr);
 556         free(ptr);
 557
 558         return 1;
 559     } else {
 560         return 0;
 561     }
 562 }
 563
 564
 565 static void *getFromBag(WMBag *self, int index)
 566 {
 567     W_Node *node;
 568
 569     if (SELF->count>0)
 570     assert(SELF->root != SELF->nil);
 571
 572     node = treeSearch(SELF->root, SELF->nil, index);
 573     if (node != SELF->nil)
 574         return node->data;
 575     else
 576         return NULL;
 577 }
 578
 579
 580
 581 static int firstInBag(WMBag *self, void *item)
 582 {
 583     W_Node *node;
 584
 585     node = treeFind(SELF->root, SELF->nil, item);
 586     if (node != SELF->nil)
 587         return node->index;
 588     else
 589         return WBNotFound;
 590 }
 591
 592
 593
 594 static int treeCount(W_Node *root, W_Node *nil, void *item)
 595 {
 596     int count = 0;
 597
 598     if (root == nil)
 599         return 0;
 600
 601     if (root->data == item)
 602         count++;
 603
 604     if (root->left != nil)
 605         count += treeCount(root->left, nil, item);
 606
 607     if (root->right != nil)
 608         count += treeCount(root->right, nil, item);
 609
 610     return count;
 611 }
 612
 613
 614
 615 static int countInBag(WMBag *self, void *item)
 616 {
 617     return treeCount(SELF->root, SELF->nil, item);
 618 }
 619
 620
 621 static void *replaceInBag(WMBag *self, int index, void *item)
 622 {
 623     W_Node *ptr = treeSearch(SELF->root, SELF->nil, index);
 624     void *old = NULL;
 625
 626     if (item == NULL) {
 627         SELF->count--;
 628
 629         ptr = rbTreeDelete(SELF, ptr);
 630         free(ptr);
 631     } else if (ptr != SELF->nil) {
 632         old = ptr->data;
 633         ptr->data = item;
 634     } else {
 635         insertInBag(self, index, item);
 636     }
 637
 638     return old;
 639 }
 640
 641
 642
 643 static int sortBag(WMBag *self, int (*comparer)(const void*, const void*))
 644 {
 645     assert(0&&"not implemented");
 646
 647     return 0;
 648 }
 649
 650
 651
 652
 653 static void deleteTree(WMBag *self, W_Node *node)
 654 {
 655     if (node == SELF->nil)
 656         return;
 657
 658     deleteTree(self, node->left);
 659
 660     if (self->destructor)
 661         self->destructor(node->data);
 662
 663     deleteTree(self, node->right);
 664
 665     free(node);
 666 }
 667
 668
 669 static void emptyBag(WMBag *self)
 670 {
 671     deleteTree(self, SELF->root);
 672     SELF->root = SELF->nil;
 673     SELF->count = 0;
 674 }
 675
 676
 677 static void freeBag(WMBag *self)
 678 {
 679     emptyBag(self);
 680
 681     free(self);
 682 }
 683
 684
 685
 686 static void mapTree(W_TreeBag *tree, W_Node *node,
 687                     void (*function)(void*, void*), void *data)
 688 {
 689     if (node == tree->nil)
 690         return;
 691
 692     mapTree(tree, node->left, function, data);
 693
 694     (*function)(node->data, data);
 695
 696     mapTree(tree, node->right, function, data);
 697 }
 698
 699
 700 static void mapBag(WMBag *self, void (*function)(void*, void*), void *data)
 701 {
 702     mapTree(SELF, SELF->root, function, data);
 703 }
 704
 705
 706
 707 static int findInTree(W_TreeBag *tree, W_Node *node, int (*function)(void*))
 708 {
 709     int index;
 710
 711     if (node == tree->nil)
 712         return WBNotFound;
 713
 714     index = findInTree(tree, node->left, function);
 715     if (index != WBNotFound)
 716         return index;
 717
 718     if ((*function)(node->data)) {
 719         return node->index;
 720     }
 721
 722     return findInTree(tree, node->right, function);
 723 }
 724
 725
 726 static int findInBag(WMBag *self, int (*match)(void*))
 727 {
 728     return findInTree(SELF, SELF->root, match);
 729 }
 730
 731
 732
 733
 734 static void *first(WMBag *self, WMBagIterator *ptr)
 735 {
 736     W_Node *node;
 737
 738     node = treeMinimum(SELF->root, SELF->nil);
 739
 740     if (node == SELF->nil) {
 741         *ptr = NULL;
 742
 743         return NULL;
 744     } else {
 745         *ptr = node;
 746
 747         return node->data;
 748     }
 749 }
 750
 751
 752
 753 static void *last(WMBag *self, WMBagIterator *ptr)
 754 {
 755
 756     W_Node *node;
 757
 758     node = treeMaximum(SELF->root, SELF->nil);
 759
 760     if (node == SELF->nil) {
 761         *ptr = NULL;
 762
 763         return NULL;
 764     } else {
 765         *ptr = node;
 766
 767         return node->data;
 768     }
 769 }
 770
 771
 772
 773 static void *next(WMBag *self, WMBagIterator *ptr)
 774 {
 775     W_Node *node;
 776
 777     if (*ptr == NULL)
 778         return NULL;
 779
 780     node = treeSuccessor(*ptr, SELF->nil);
 781
 782     if (node == SELF->nil) {
 783         *ptr = NULL;
 784
 785         return NULL;
 786     } else {
 787         *ptr = node;
 788
 789         return node->data;
 790     }
 791 }
 792
 793
 794
 795 static void *previous(WMBag *self, WMBagIterator *ptr)
 796 {
 797     W_Node *node;
 798
 799     if (*ptr == NULL)
 800         return NULL;
 801
 802     node = treePredecessor(*ptr, SELF->nil);
 803
 804
 805     if (node == SELF->nil) {
 806         *ptr = NULL;
 807
 808         return NULL;
 809     } else {
 810         *ptr = node;
 811
 812         return node->data;
 813     }
 814 }
 815
 816
 817
 818 static void *iteratorAtIndex(WMBag *self, int index, WMBagIterator *ptr)
 819 {
 820     W_Node *node;
 821
 822     node = treeSearch(SELF->root, SELF->nil, index);
 823
 824     if (node == SELF->nil) {
 825         *ptr = NULL;
 826         return NULL;
 827     } else {
 828         *ptr = node;
 829         return node->data;
 830     }
 831 }
 832
 833
 834 static int indexForIterator(WMBag *bag, WMBagIterator ptr)
 835 {
 836     return ((W_Node*)ptr)->index;
 837 }
 838