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(WMFreeDataProc *destructor)
 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 void
 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         WMPutInBag(self, data);
 434     }
 435 }
 436
 437
 438 void
 439 WMPutInBag(WMBag *self, void *item)
 440 {
 441     W_Node *ptr;
 442
 443     ptr = wmalloc(sizeof(W_Node));
 444
 445     ptr->data = item;
 446     ptr->index = self->count;
 447     ptr->left = self->nil;
 448     ptr->right = self->nil;
 449     ptr->parent = self->nil;
 450
 451     rbTreeInsert(self, ptr);
 452
 453     self->count++;
 454 }
 455
 456
 457 void
 458 WMInsertInBag(WMBag *self, int index, void *item)
 459 {
 460     W_Node *ptr;
 461
 462     ptr = wmalloc(sizeof(W_Node));
 463
 464     ptr->data = item;
 465     ptr->index = index;
 466     ptr->left = self->nil;
 467     ptr->right = self->nil;
 468     ptr->parent = self->nil;
 469
 470     rbTreeInsert(self, ptr);
 471
 472     while ((ptr = treeSuccessor(ptr, self->nil)) != self->nil) {
 473         ptr->index++;
 474     }
 475
 476
 477     self->count++;
 478 }
 479
 480
 481 int
 482 WMRemoveFromBag(WMBag *self, void *item)
 483 {
 484     W_Node *ptr = treeFind(self->root, self->nil, item);
 485
 486     if (ptr != self->nil) {
 487         W_Node *tmp;
 488
 489         self->count--;
 490
 491         tmp = treeSuccessor(ptr, self->nil);
 492         while (tmp != self->nil) {
 493             tmp->index--;
 494             tmp = treeSuccessor(tmp, self->nil);
 495         }
 496
 497         ptr = rbTreeDelete(self, ptr);
 498         if (self->destructor)
 499             self->destructor(ptr->data);
 500         wfree(ptr);
 501
 502         return 1;
 503     } else {
 504         return 0;
 505     }
 506 }
 507
 508
 509 int
 510 WMEraseFromBag(WMBag *self, int index)
 511 {
 512     W_Node *ptr = treeSearch(self->root, self->nil, index);
 513
 514     if (ptr != self->nil) {
 515
 516         self->count--;
 517
 518         ptr = rbTreeDelete(self, ptr);
 519         if (self->destructor)
 520             self->destructor(ptr->data);
 521         wfree(ptr);
 522
 523         wassertrv(self->count == 0||self->root->index >= 0, 1);
 524
 525         return 1;
 526     } else {
 527         return 0;
 528     }
 529 }
 530
 531
 532 int
 533 WMDeleteFromBag(WMBag *self, int index)
 534 {
 535     W_Node *ptr = treeSearch(self->root, self->nil, index);
 536
 537     if (ptr != self->nil) {
 538         W_Node *tmp;
 539
 540         self->count--;
 541
 542         tmp = treeSuccessor(ptr, self->nil);
 543         while (tmp != self->nil) {
 544             tmp->index--;
 545             tmp = treeSuccessor(tmp, self->nil);
 546         }
 547
 548         ptr = rbTreeDelete(self, ptr);
 549         if (self->destructor)
 550             self->destructor(ptr->data);
 551         wfree(ptr);
 552
 553         wassertrv(self->count == 0||self->root->index >= 0, 1);
 554
 555         return 1;
 556     } else {
 557         return 0;
 558     }
 559 }
 560
 561
 562 void*
 563 WMGetFromBag(WMBag *self, int index)
 564 {
 565     W_Node *node;
 566
 567     node = treeSearch(self->root, self->nil, index);
 568     if (node != self->nil)
 569         return node->data;
 570     else
 571         return NULL;
 572 }
 573
 574
 575 int
 576 WMGetFirstInBag(WMBag *self, void *item)
 577 {
 578     W_Node *node;
 579
 580     node = treeFind(self->root, self->nil, item);
 581     if (node != self->nil)
 582         return node->index;
 583     else
 584         return WBNotFound;
 585 }
 586
 587
 588
 589 static int
 590 treeCount(W_Node *root, W_Node *nil, void *item)
 591 {
 592     int count = 0;
 593
 594     if (root == nil)
 595         return 0;
 596
 597     if (root->data == item)
 598         count++;
 599
 600     if (root->left != nil)
 601         count += treeCount(root->left, nil, item);
 602
 603     if (root->right != nil)
 604         count += treeCount(root->right, nil, item);
 605
 606     return count;
 607 }
 608
 609
 610
 611 int
 612 WMCountInBag(WMBag *self, void *item)
 613 {
 614     return treeCount(self->root, self->nil, item);
 615 }
 616
 617
 618 void*
 619 WMReplaceInBag(WMBag *self, int index, void *item)
 620 {
 621     W_Node *ptr = treeSearch(self->root, self->nil, index);
 622     void *old = NULL;
 623
 624     if (item == NULL) {
 625         self->count--;
 626         ptr = rbTreeDelete(self, ptr);
 627         if (self->destructor)
 628             self->destructor(ptr->data);
 629         wfree(ptr);
 630     } else if (ptr != self->nil) {
 631         old = ptr->data;
 632         ptr->data = item;
 633     } else {
 634         W_Node *ptr;
 635
 636         ptr = wmalloc(sizeof(W_Node));
 637
 638         ptr->data = item;
 639         ptr->index = index;
 640         ptr->left = self->nil;
 641         ptr->right = self->nil;
 642         ptr->parent = self->nil;
 643
 644         rbTreeInsert(self, ptr);
 645
 646         self->count++;
 647     }
 648
 649     return old;
 650 }
 651
 652
 653 void
 654 WMSortBag(WMBag *self, WMCompareDataProc *comparer)
 655 {
 656     void **items;
 657     W_Node *tmp;
 658     int i;
 659
 660     if (self->count == 0)
 661         return;
 662
 663     items = wmalloc(sizeof(void*)*self->count);
 664     i = 0;
 665
 666     tmp = treeMinimum(self->root, self->nil);
 667     while (tmp != self->nil) {
 668         items[i++] = tmp->data;
 669         tmp = treeSuccessor(tmp, self->nil);
 670     }
 671
 672     qsort(&items[0], self->count, sizeof(void*), comparer);
 673
 674     i = 0;
 675     tmp = treeMinimum(self->root, self->nil);
 676     while (tmp != self->nil) {
 677         tmp->index = i;
 678         tmp->data = items[i++];
 679         tmp = treeSuccessor(tmp, self->nil);
 680     }
 681
 682     wfree(items);
 683 }
 684
 685
 686 static void
 687 deleteTree(WMBag *self, W_Node *node)
 688 {
 689     if (node == self->nil)
 690         return;
 691
 692     deleteTree(self, node->left);
 693
 694     if (self->destructor)
 695         self->destructor(node->data);
 696
 697     deleteTree(self, node->right);
 698
 699     wfree(node);
 700 }
 701
 702
 703 void
 704 WMEmptyBag(WMBag *self)
 705 {
 706     deleteTree(self, self->root);
 707     self->root = self->nil;
 708     self->count = 0;
 709 }
 710
 711
 712 void
 713 WMFreeBag(WMBag *self)
 714 {
 715     WMEmptyBag(self);
 716     wfree(self->nil);
 717     wfree(self);
 718 }
 719
 720
 721 static void
 722 mapTree(W_Bag *tree, W_Node *node, void (*function)(void*, void*), void *data)
 723 {
 724     if (node == tree->nil)
 725         return;
 726
 727     mapTree(tree, node->left, function, data);
 728
 729     (*function)(node->data, data);
 730
 731     mapTree(tree, node->right, function, data);
 732 }
 733
 734
 735 void
 736 WMMapBag(WMBag *self, void (*function)(void*, void*), void *data)
 737 {
 738     mapTree(self, self->root, function, data);
 739 }
 740
 741
 742
 743 static int
 744 findInTree(W_Bag *tree, W_Node *node, WMMatchDataProc *function, void *cdata)
 745 {
 746     int index;
 747
 748     if (node == tree->nil)
 749         return WBNotFound;
 750
 751     index = findInTree(tree, node->left, function, cdata);
 752     if (index != WBNotFound)
 753         return index;
 754
 755     if ((*function)(node->data, cdata)) {
 756         return node->index;
 757     }
 758
 759     return findInTree(tree, node->right, function, cdata);
 760 }
 761
 762
 763 int
 764 WMFindInBag(WMBag *self, WMMatchDataProc *match, void *cdata)
 765 {
 766     return findInTree(self, self->root, match, cdata);
 767 }
 768
 769
 770 void*
 771 WMBagFirst(WMBag *self, WMBagIterator *ptr)
 772 {
 773     W_Node *node;
 774
 775     node = treeMinimum(self->root, self->nil);
 776
 777     if (node == self->nil) {
 778         *ptr = NULL;
 779         return NULL;
 780     } else {
 781         *ptr = node;
 782         return node->data;
 783     }
 784 }
 785
 786
 787 void*
 788 WMBagLast(WMBag *self, WMBagIterator *ptr)
 789 {
 790
 791     W_Node *node;
 792
 793     node = treeMaximum(self->root, self->nil);
 794
 795     if (node == self->nil) {
 796         *ptr = NULL;
 797         return NULL;
 798     } else {
 799         *ptr = node;
 800         return node->data;
 801     }
 802 }
 803
 804
 805 void*
 806 WMBagNext(WMBag *self, WMBagIterator *ptr)
 807 {
 808     W_Node *node;
 809
 810     if (*ptr == NULL)
 811         return NULL;
 812
 813     node = treeSuccessor(*ptr, self->nil);
 814
 815     if (node == self->nil) {
 816         *ptr = NULL;
 817         return NULL;
 818     } else {
 819         *ptr = node;
 820         return node->data;
 821     }
 822 }
 823
 824
 825 void*
 826 WMBagPrevious(WMBag *self, WMBagIterator *ptr)
 827 {
 828     W_Node *node;
 829
 830     if (*ptr == NULL)
 831         return NULL;
 832
 833     node = treePredecessor(*ptr, self->nil);
 834
 835     if (node == self->nil) {
 836         *ptr = NULL;
 837         return NULL;
 838     } else {
 839         *ptr = node;
 840         return node->data;
 841     }
 842 }
 843
 844
 845 void*
 846 WMBagIteratorAtIndex(WMBag *self, int index, WMBagIterator *ptr)
 847 {
 848     W_Node *node;
 849
 850     node = treeSearch(self->root, self->nil, index);
 851
 852     if (node == self->nil) {
 853         *ptr = NULL;
 854         return NULL;
 855     } else {
 856         *ptr = node;
 857         return node->data;
 858     }
 859 }
 860
 861
 862 int
 863 WMBagIndexForIterator(WMBag *bag, WMBagIterator ptr)
 864 {
 865     return ((W_Node*)ptr)->index;
 866 }
 867
 868