WINGs/bagtree.c

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