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*,void*), void *data);
  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                 rightRotate(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                     leftRotate(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                 rightRotate(tree, node->parent);
 268                 node = tree->root;
 269             }
 270         }
 271     }
 272     node->color = 'B';
 273
 274 }
 275
 276
 277 static W_Node *treeMinimum(W_Node *node, W_Node *nil)
 278 {
 279     while (node->left != nil)
 280         node = node->left;
 281     return node;
 282 }
 283
 284
 285 static W_Node *treeMaximum(W_Node *node, W_Node *nil)
 286 {
 287     while (node->right != nil)
 288         node = node->right;
 289     return node;
 290 }
 291
 292
 293 static W_Node *treeSuccessor(W_Node *node, W_Node *nil)
 294 {
 295     W_Node *y;
 296
 297     if (node->right != nil) {
 298         return treeMinimum(node->right, nil);
 299     }
 300     y = node->parent;
 301     while (y != nil && node == y->right) {
 302         node = y;
 303         y = y->parent;
 304     }
 305     return y;
 306 }
 307
 308
 309 static W_Node *treePredecessor(W_Node *node, W_Node *nil)
 310 {
 311     W_Node *y;
 312
 313     if (node->left != nil) {
 314         return treeMaximum(node->left, nil);
 315     }
 316     y = node->parent;
 317     while (y != nil && node == y->left) {
 318         node = y;
 319         y = y->parent;
 320     }
 321     return y;
 322 }
 323
 324
 325 static W_Node *rbTreeDelete(W_TreeBag *tree, W_Node *node)
 326 {
 327     W_Node *nil = tree->nil;
 328     W_Node *x, *y;
 329
 330     if (node->left == nil || node->right == nil) {
 331         y = node;
 332     } else {
 333         y = treeSuccessor(node, nil);
 334     }
 335
 336     if (y->left != nil) {
 337         x = y->left;
 338     } else {
 339         x = y->right;
 340     }
 341
 342     x->parent = y->parent;
 343
 344     if (y->parent == nil) {
 345         tree->root = x;
 346     } else {
 347         if (IS_LEFT(y)) {
 348             y->parent->left = x;
 349         } else {
 350             y->parent->right = x;
 351         }
 352     }
 353     if (y != node) {
 354         node->index = y->index;
 355         node->data = y->data;
 356     }
 357     if (y->color == 'B') {
 358         rbDeleteFixup(tree, x);
 359     }
 360
 361     return y;
 362 }
 363
 364
 365
 366 static W_Node *treeSearch(W_Node *root, W_Node *nil, int index)
 367 {
 368     if (root == nil || root->index == index) {
 369         return root;
 370     }
 371
 372     if (index < root->index) {
 373         return treeSearch(root->left, nil, index);
 374     } else {
 375         return treeSearch(root->right, nil, index);
 376     }
 377 }
 378
 379
 380 static W_Node *treeFind(W_Node *root, W_Node *nil, void *data)
 381 {
 382     W_Node *tmp;
 383
 384     if (root == nil || root->data == data)
 385         return root;
 386
 387     tmp = treeFind(root->left, nil, data);
 388     if (tmp != nil)
 389         return tmp;
 390
 391     tmp = treeFind(root->right, nil, data);
 392
 393     return tmp;
 394 }
 395
 396
 397
 398
 399
 400 #if 0
 401 static char buf[512];
 402
 403 static void printNodes(W_Node *node, W_Node *nil, int depth)
 404 {
 405     if (node == nil) {
 406         return;
 407     }
 408
 409     printNodes(node->left, nil, depth+1);
 410
 411     memset(buf, ' ', depth*2);
 412     buf[depth*2] = 0;
 413     if (IS_LEFT(node))
 414         printf("%s/(%2i\n", buf, node->index);
 415     else
 416         printf("%s\\(%2i\n", buf, node->index);
 417
 418     printNodes(node->right, nil, depth+1);
 419 }
 420
 421
 422 void PrintTree(WMBag *bag)
 423 {
 424     W_TreeBag *tree = (W_TreeBag*)bag->data;
 425
 426     printNodes(tree->root, tree->nil, 0);
 427 }
 428 #endif
 429
 430
 431
 432
 433 #define SELF ((W_TreeBag*)self->data)
 434
 435 WMBag *WMCreateTreeBag(void)
 436 {
 437     return WMCreateTreeBagWithDestructor(NULL);
 438 }
 439
 440
 441 WMBag *WMCreateTreeBagWithDestructor(void (*destructor)(void*))
 442 {
 443     WMBag *bag;
 444     W_TreeBag *tree;
 445
 446     bag = wmalloc(sizeof(WMBag));
 447
 448     bag->data = tree = wmalloc(sizeof(W_TreeBag));
 449     memset(tree, 0, sizeof(W_TreeBag));
 450
 451     tree->nil = wmalloc(sizeof(W_Node));
 452     memset(tree->nil, 0, sizeof(W_Node));
 453     tree->nil->left = tree->nil->right = tree->nil->parent = tree->nil;
 454     tree->nil->index = WBNotFound;
 455
 456     tree->root = tree->nil;
 457
 458     bag->destructor = destructor;
 459
 460     bag->func = bagFunctions;
 461
 462     return bag;
 463 }
 464
 465
 466 static int getItemCount(WMBag *self)
 467 {
 468     return SELF->count;
 469 }
 470
 471
 472 static int appendBag(WMBag *self, WMBag *bag)
 473 {
 474     WMBagIterator ptr;
 475     void *data;
 476
 477     for (data = first(bag, &ptr); data != NULL; data = next(bag, &ptr)) {
 478         if (!putInBag(self, data))
 479             return 0;
 480     }
 481
 482     return 1;
 483 }
 484
 485 extern WMBag *bla;
 486
 487 static int putInBag(WMBag *self, void *item)
 488 {
 489     W_Node *ptr;
 490
 491
 492     ptr = wmalloc(sizeof(W_Node));
 493
 494     ptr->data = item;
 495     ptr->index = SELF->count;
 496     ptr->left = SELF->nil;
 497     ptr->right = SELF->nil;
 498     ptr->parent = SELF->nil;
 499
 500     rbTreeInsert(SELF, ptr);
 501
 502     SELF->count++;
 503
 504     return 1;
 505 }
 506
 507
 508 static int insertInBag(WMBag *self, int index, void *item)
 509 {
 510     W_Node *ptr;
 511
 512     ptr = wmalloc(sizeof(W_Node));
 513
 514     ptr->data = item;
 515     ptr->index = index;
 516     ptr->left = SELF->nil;
 517     ptr->right = SELF->nil;
 518     ptr->parent = SELF->nil;
 519
 520     rbTreeInsert(SELF, ptr);
 521
 522     while ((ptr = treeSuccessor(ptr, SELF->nil)) != SELF->nil) {
 523         ptr->index++;
 524     }
 525
 526
 527     SELF->count++;
 528
 529     return 1;
 530 }
 531
 532
 533
 534 static int removeFromBag(WMBag *self, void *item)
 535 {
 536     W_Node *ptr = treeFind(SELF->root, SELF->nil, item);
 537
 538     if (ptr != SELF->nil) {
 539         W_Node *tmp;
 540
 541         SELF->count--;
 542
 543         tmp = treeSuccessor(ptr, SELF->nil);
 544         while (tmp != SELF->nil) {
 545             tmp->index--;
 546             tmp = treeSuccessor(tmp, SELF->nil);
 547         }
 548
 549         ptr = rbTreeDelete(SELF, ptr);
 550         if (self->destructor)
 551             self->destructor(ptr->data);
 552         free(ptr);
 553
 554         return 1;
 555     } else {
 556         return 0;
 557     }
 558 }
 559
 560
 561
 562 static int eraseFromBag(WMBag *self, int index)
 563 {
 564     W_Node *ptr = treeSearch(SELF->root, SELF->nil, index);
 565
 566     if (ptr != SELF->nil) {
 567
 568         SELF->count--;
 569
 570         ptr = rbTreeDelete(SELF, ptr);
 571         if (self->destructor)
 572             self->destructor(ptr->data);
 573         free(ptr);
 574
 575         wassertrv(SELF->count == 0||SELF->root->index >= 0, 1);
 576
 577         return 1;
 578     } else {
 579         return 0;
 580     }
 581 }
 582
 583
 584 static int deleteFromBag(WMBag *self, int index)
 585 {
 586     W_Node *ptr = treeSearch(SELF->root, SELF->nil, index);
 587
 588     if (ptr != SELF->nil) {
 589         W_Node *tmp;
 590
 591         SELF->count--;
 592
 593         tmp = treeSuccessor(ptr, SELF->nil);
 594         while (tmp != SELF->nil) {
 595             tmp->index--;
 596             tmp = treeSuccessor(tmp, SELF->nil);
 597         }
 598
 599         ptr = rbTreeDelete(SELF, ptr);
 600         if (self->destructor)
 601             self->destructor(ptr->data);
 602         free(ptr);
 603
 604         wassertrv(SELF->count == 0||SELF->root->index >= 0, 1);
 605
 606         return 1;
 607     } else {
 608         return 0;
 609     }
 610 }
 611
 612
 613 static void *getFromBag(WMBag *self, int index)
 614 {
 615     W_Node *node;
 616
 617     node = treeSearch(SELF->root, SELF->nil, index);
 618     if (node != SELF->nil)
 619         return node->data;
 620     else
 621         return NULL;
 622 }
 623
 624
 625
 626 static int firstInBag(WMBag *self, void *item)
 627 {
 628     W_Node *node;
 629
 630     node = treeFind(SELF->root, SELF->nil, item);
 631     if (node != SELF->nil)
 632         return node->index;
 633     else
 634         return WBNotFound;
 635 }
 636
 637
 638
 639 static int treeCount(W_Node *root, W_Node *nil, void *item)
 640 {
 641     int count = 0;
 642
 643     if (root == nil)
 644         return 0;
 645
 646     if (root->data == item)
 647         count++;
 648
 649     if (root->left != nil)
 650         count += treeCount(root->left, nil, item);
 651
 652     if (root->right != nil)
 653         count += treeCount(root->right, nil, item);
 654
 655     return count;
 656 }
 657
 658
 659
 660 static int countInBag(WMBag *self, void *item)
 661 {
 662     return treeCount(SELF->root, SELF->nil, item);
 663 }
 664
 665
 666 static void *replaceInBag(WMBag *self, int index, void *item)
 667 {
 668     W_Node *ptr = treeSearch(SELF->root, SELF->nil, index);
 669     void *old = NULL;
 670
 671     if (item == NULL) {
 672         SELF->count--;
 673         ptr = rbTreeDelete(SELF, ptr);
 674         if (self->destructor)
 675             self->destructor(ptr->data);
 676         free(ptr);
 677     } else if (ptr != SELF->nil) {
 678         old = ptr->data;
 679         ptr->data = item;
 680     } else {
 681         W_Node *ptr;
 682
 683         ptr = wmalloc(sizeof(W_Node));
 684
 685         ptr->data = item;
 686         ptr->index = index;
 687         ptr->left = SELF->nil;
 688         ptr->right = SELF->nil;
 689         ptr->parent = SELF->nil;
 690
 691         rbTreeInsert(SELF, ptr);
 692
 693         SELF->count++;
 694     }
 695
 696     return old;
 697 }
 698
 699
 700
 701
 702 static int sortBag(WMBag *self, int (*comparer)(const void*, const void*))
 703 {
 704     void **items;
 705     W_Node *tmp;
 706     int i;
 707
 708     if (SELF->count == 0)
 709         return 1;
 710
 711     items = wmalloc(sizeof(void*)*SELF->count);
 712     i = 0;
 713
 714     tmp = treeMinimum(SELF->root, SELF->nil);
 715     while (tmp != SELF->nil) {
 716         items[i++] = tmp->data;
 717         tmp = treeSuccessor(tmp, SELF->nil);
 718     }
 719
 720     qsort(&items[0], SELF->count, sizeof(void*), comparer);
 721
 722     i = 0;
 723     tmp = treeMinimum(SELF->root, SELF->nil);
 724     while (tmp != SELF->nil) {
 725         tmp->index = i;
 726         tmp->data = items[i++];
 727         tmp = treeSuccessor(tmp, SELF->nil);
 728     }
 729
 730     wfree(items);
 731
 732     return 1;
 733 }
 734
 735
 736
 737
 738 static void deleteTree(WMBag *self, W_Node *node)
 739 {
 740     if (node == SELF->nil)
 741         return;
 742
 743     deleteTree(self, node->left);
 744
 745     if (self->destructor)
 746         self->destructor(node->data);
 747
 748     deleteTree(self, node->right);
 749
 750     free(node);
 751 }
 752
 753
 754 static void emptyBag(WMBag *self)
 755 {
 756     deleteTree(self, SELF->root);
 757     SELF->root = SELF->nil;
 758     SELF->count = 0;
 759 }
 760
 761
 762 static void freeBag(WMBag *self)
 763 {
 764     emptyBag(self);
 765
 766     free(SELF->nil);
 767     free(self->data);
 768
 769     free(self);
 770 }
 771
 772
 773
 774 static void mapTree(W_TreeBag *tree, W_Node *node,
 775                     void (*function)(void*, void*), void *data)
 776 {
 777     if (node == tree->nil)
 778         return;
 779
 780     mapTree(tree, node->left, function, data);
 781
 782     (*function)(node->data, data);
 783
 784     mapTree(tree, node->right, function, data);
 785 }
 786
 787
 788 static void mapBag(WMBag *self, void (*function)(void*, void*), void *data)
 789 {
 790     mapTree(SELF, SELF->root, function, data);
 791 }
 792
 793
 794
 795 static int findInTree(W_TreeBag *tree, W_Node *node,
 796                       int (*function)(void*,void*), void *cdata)
 797 {
 798     int index;
 799
 800     if (node == tree->nil)
 801         return WBNotFound;
 802
 803     index = findInTree(tree, node->left, function, cdata);
 804     if (index != WBNotFound)
 805         return index;
 806
 807     if ((*function)(node->data, cdata)) {
 808         return node->index;
 809     }
 810
 811     return findInTree(tree, node->right, function, cdata);
 812 }
 813
 814
 815 static int findInBag(WMBag *self, int (*match)(void*,void*), void *cdata)
 816 {
 817     return findInTree(SELF, SELF->root, match, cdata);
 818 }
 819
 820
 821
 822
 823 static void *first(WMBag *self, WMBagIterator *ptr)
 824 {
 825     W_Node *node;
 826
 827     node = treeMinimum(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 *last(WMBag *self, WMBagIterator *ptr)
 843 {
 844
 845     W_Node *node;
 846
 847     node = treeMaximum(SELF->root, SELF->nil);
 848
 849     if (node == SELF->nil) {
 850         *ptr = NULL;
 851
 852         return NULL;
 853     } else {
 854         *ptr = node;
 855
 856         return node->data;
 857     }
 858 }
 859
 860
 861
 862 static void *next(WMBag *self, WMBagIterator *ptr)
 863 {
 864     W_Node *node;
 865
 866     if (*ptr == NULL)
 867         return NULL;
 868
 869     node = treeSuccessor(*ptr, SELF->nil);
 870
 871     if (node == SELF->nil) {
 872         *ptr = NULL;
 873
 874         return NULL;
 875     } else {
 876         *ptr = node;
 877
 878         return node->data;
 879     }
 880 }
 881
 882
 883
 884 static void *previous(WMBag *self, WMBagIterator *ptr)
 885 {
 886     W_Node *node;
 887
 888     if (*ptr == NULL)
 889         return NULL;
 890
 891     node = treePredecessor(*ptr, SELF->nil);
 892
 893
 894     if (node == SELF->nil) {
 895         *ptr = NULL;
 896
 897         return NULL;
 898     } else {
 899         *ptr = node;
 900
 901         return node->data;
 902     }
 903 }
 904
 905
 906
 907 static void *iteratorAtIndex(WMBag *self, int index, WMBagIterator *ptr)
 908 {
 909     W_Node *node;
 910
 911     node = treeSearch(SELF->root, SELF->nil, index);
 912
 913     if (node == SELF->nil) {
 914         *ptr = NULL;
 915         return NULL;
 916     } else {
 917         *ptr = node;
 918         return node->data;
 919     }
 920 }
 921
 922
 923 static int indexForIterator(WMBag *bag, WMBagIterator ptr)
 924 {
 925     return ((W_Node*)ptr)->index;
 926 }
 927