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