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