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