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
 362         memset(bag, 0, sizeof(WMBag));
 363
 364         bag->nil = wmalloc(sizeof(W_Node));
 365         memset(bag->nil, 0, sizeof(W_Node));
 366         bag->nil->left = bag->nil->right = bag->nil->parent = bag->nil;
 367         bag->nil->index = WBNotFound;
 368
 369         bag->root = bag->nil;
 370
 371         bag->destructor = destructor;
 372
 373         return bag;
 374 }
 375
 376 int WMGetBagItemCount(WMBag * self)
 377 {
 378         return self->count;
 379 }
 380
 381 void WMAppendBag(WMBag * self, WMBag * bag)
 382 {
 383         WMBagIterator ptr;
 384         void *data;
 385
 386         for (data = WMBagFirst(bag, &ptr); data != NULL; data = WMBagNext(bag, &ptr)) {
 387                 WMPutInBag(self, data);
 388         }
 389 }
 390
 391 void WMPutInBag(WMBag * self, void *item)
 392 {
 393         W_Node *ptr;
 394
 395         ptr = wmalloc(sizeof(W_Node));
 396
 397         ptr->data = item;
 398         ptr->index = self->count;
 399         ptr->left = self->nil;
 400         ptr->right = self->nil;
 401         ptr->parent = self->nil;
 402
 403         rbTreeInsert(self, ptr);
 404
 405         self->count++;
 406 }
 407
 408 void WMInsertInBag(WMBag * self, int index, void *item)
 409 {
 410         W_Node *ptr;
 411
 412         ptr = wmalloc(sizeof(W_Node));
 413
 414         ptr->data = item;
 415         ptr->index = index;
 416         ptr->left = self->nil;
 417         ptr->right = self->nil;
 418         ptr->parent = self->nil;
 419
 420         rbTreeInsert(self, ptr);
 421
 422         while ((ptr = treeSuccessor(ptr, self->nil)) != self->nil) {
 423                 ptr->index++;
 424         }
 425
 426         self->count++;
 427 }
 428
 429 int WMRemoveFromBag(WMBag * self, void *item)
 430 {
 431         W_Node *ptr = treeFind(self->root, self->nil, item);
 432
 433         if (ptr != self->nil) {
 434                 W_Node *tmp;
 435
 436                 self->count--;
 437
 438                 tmp = treeSuccessor(ptr, self->nil);
 439                 while (tmp != self->nil) {
 440                         tmp->index--;
 441                         tmp = treeSuccessor(tmp, self->nil);
 442                 }
 443
 444                 ptr = rbTreeDelete(self, ptr);
 445                 if (self->destructor)
 446                         self->destructor(ptr->data);
 447                 wfree(ptr);
 448
 449                 return 1;
 450         } else {
 451                 return 0;
 452         }
 453 }
 454
 455 int WMEraseFromBag(WMBag * self, int index)
 456 {
 457         W_Node *ptr = treeSearch(self->root, self->nil, index);
 458
 459         if (ptr != self->nil) {
 460
 461                 self->count--;
 462
 463                 ptr = rbTreeDelete(self, ptr);
 464                 if (self->destructor)
 465                         self->destructor(ptr->data);
 466                 wfree(ptr);
 467
 468                 wassertrv(self->count == 0 || self->root->index >= 0, 1);
 469
 470                 return 1;
 471         } else {
 472                 return 0;
 473         }
 474 }
 475
 476 int WMDeleteFromBag(WMBag * self, int index)
 477 {
 478         W_Node *ptr = treeSearch(self->root, self->nil, index);
 479
 480         if (ptr != self->nil) {
 481                 W_Node *tmp;
 482
 483                 self->count--;
 484
 485                 tmp = treeSuccessor(ptr, self->nil);
 486                 while (tmp != self->nil) {
 487                         tmp->index--;
 488                         tmp = treeSuccessor(tmp, self->nil);
 489                 }
 490
 491                 ptr = rbTreeDelete(self, ptr);
 492                 if (self->destructor)
 493                         self->destructor(ptr->data);
 494                 wfree(ptr);
 495
 496                 wassertrv(self->count == 0 || self->root->index >= 0, 1);
 497
 498                 return 1;
 499         } else {
 500                 return 0;
 501         }
 502 }
 503
 504 void *WMGetFromBag(WMBag * self, int index)
 505 {
 506         W_Node *node;
 507
 508         node = treeSearch(self->root, self->nil, index);
 509         if (node != self->nil)
 510                 return node->data;
 511         else
 512                 return NULL;
 513 }
 514
 515 int WMGetFirstInBag(WMBag * self, void *item)
 516 {
 517         W_Node *node;
 518
 519         node = treeFind(self->root, self->nil, item);
 520         if (node != self->nil)
 521                 return node->index;
 522         else
 523                 return WBNotFound;
 524 }
 525
 526 static int treeCount(W_Node * root, W_Node * nil, void *item)
 527 {
 528         int count = 0;
 529
 530         if (root == nil)
 531                 return 0;
 532
 533         if (root->data == item)
 534                 count++;
 535
 536         if (root->left != nil)
 537                 count += treeCount(root->left, nil, item);
 538
 539         if (root->right != nil)
 540                 count += treeCount(root->right, nil, item);
 541
 542         return count;
 543 }
 544
 545 int WMCountInBag(WMBag * self, void *item)
 546 {
 547         return treeCount(self->root, self->nil, item);
 548 }
 549
 550 void *WMReplaceInBag(WMBag * self, int index, void *item)
 551 {
 552         W_Node *ptr = treeSearch(self->root, self->nil, index);
 553         void *old = NULL;
 554
 555         if (item == NULL) {
 556                 self->count--;
 557                 ptr = rbTreeDelete(self, ptr);
 558                 if (self->destructor)
 559                         self->destructor(ptr->data);
 560                 wfree(ptr);
 561         } else if (ptr != self->nil) {
 562                 old = ptr->data;
 563                 ptr->data = item;
 564         } else {
 565                 W_Node *ptr;
 566
 567                 ptr = wmalloc(sizeof(W_Node));
 568
 569                 ptr->data = item;
 570                 ptr->index = index;
 571                 ptr->left = self->nil;
 572                 ptr->right = self->nil;
 573                 ptr->parent = self->nil;
 574
 575                 rbTreeInsert(self, ptr);
 576
 577                 self->count++;
 578         }
 579
 580         return old;
 581 }
 582
 583 void WMSortBag(WMBag * self, WMCompareDataProc * comparer)
 584 {
 585         void **items;
 586         W_Node *tmp;
 587         int i;
 588
 589         if (self->count == 0)
 590                 return;
 591
 592         items = wmalloc(sizeof(void *) * self->count);
 593         i = 0;
 594
 595         tmp = treeMinimum(self->root, self->nil);
 596         while (tmp != self->nil) {
 597                 items[i++] = tmp->data;
 598                 tmp = treeSuccessor(tmp, self->nil);
 599         }
 600
 601         qsort(&items[0], self->count, sizeof(void *), comparer);
 602
 603         i = 0;
 604         tmp = treeMinimum(self->root, self->nil);
 605         while (tmp != self->nil) {
 606                 tmp->index = i;
 607                 tmp->data = items[i++];
 608                 tmp = treeSuccessor(tmp, self->nil);
 609         }
 610
 611         wfree(items);
 612 }
 613
 614 static void deleteTree(WMBag * self, W_Node * node)
 615 {
 616         if (node == self->nil)
 617                 return;
 618
 619         deleteTree(self, node->left);
 620
 621         if (self->destructor)
 622                 self->destructor(node->data);
 623
 624         deleteTree(self, node->right);
 625
 626         wfree(node);
 627 }
 628
 629 void WMEmptyBag(WMBag * self)
 630 {
 631         deleteTree(self, self->root);
 632         self->root = self->nil;
 633         self->count = 0;
 634 }
 635
 636 void WMFreeBag(WMBag * self)
 637 {
 638         WMEmptyBag(self);
 639         wfree(self->nil);
 640         wfree(self);
 641 }
 642
 643 static void mapTree(W_Bag * tree, W_Node * node, void (*function) (void *, void *), void *data)
 644 {
 645         if (node == tree->nil)
 646                 return;
 647
 648         mapTree(tree, node->left, function, data);
 649
 650         (*function) (node->data, data);
 651
 652         mapTree(tree, node->right, function, data);
 653 }
 654
 655 void WMMapBag(WMBag * self, void (*function) (void *, void *), void *data)
 656 {
 657         mapTree(self, self->root, function, data);
 658 }
 659
 660 static int findInTree(W_Bag * tree, W_Node * node, WMMatchDataProc * function, void *cdata)
 661 {
 662         int index;
 663
 664         if (node == tree->nil)
 665                 return WBNotFound;
 666
 667         index = findInTree(tree, node->left, function, cdata);
 668         if (index != WBNotFound)
 669                 return index;
 670
 671         if ((*function) (node->data, cdata)) {
 672                 return node->index;
 673         }
 674
 675         return findInTree(tree, node->right, function, cdata);
 676 }
 677
 678 int WMFindInBag(WMBag * self, WMMatchDataProc * match, void *cdata)
 679 {
 680         return findInTree(self, self->root, match, cdata);
 681 }
 682
 683 void *WMBagFirst(WMBag * self, WMBagIterator * ptr)
 684 {
 685         W_Node *node;
 686
 687         node = treeMinimum(self->root, self->nil);
 688
 689         if (node == self->nil) {
 690                 *ptr = NULL;
 691                 return NULL;
 692         } else {
 693                 *ptr = node;
 694                 return node->data;
 695         }
 696 }
 697
 698 void *WMBagLast(WMBag * self, WMBagIterator * ptr)
 699 {
 700
 701         W_Node *node;
 702
 703         node = treeMaximum(self->root, self->nil);
 704
 705         if (node == self->nil) {
 706                 *ptr = NULL;
 707                 return NULL;
 708         } else {
 709                 *ptr = node;
 710                 return node->data;
 711         }
 712 }
 713
 714 void *WMBagNext(WMBag * self, WMBagIterator * ptr)
 715 {
 716         W_Node *node;
 717
 718         if (*ptr == NULL)
 719                 return NULL;
 720
 721         node = treeSuccessor(*ptr, self->nil);
 722
 723         if (node == self->nil) {
 724                 *ptr = NULL;
 725                 return NULL;
 726         } else {
 727                 *ptr = node;
 728                 return node->data;
 729         }
 730 }
 731
 732 void *WMBagPrevious(WMBag * self, WMBagIterator * ptr)
 733 {
 734         W_Node *node;
 735
 736         if (*ptr == NULL)
 737                 return NULL;
 738
 739         node = treePredecessor(*ptr, self->nil);
 740
 741         if (node == self->nil) {
 742                 *ptr = NULL;
 743                 return NULL;
 744         } else {
 745                 *ptr = node;
 746                 return node->data;
 747         }
 748 }
 749
 750 void *WMBagIteratorAtIndex(WMBag * self, int index, WMBagIterator * ptr)
 751 {
 752         W_Node *node;
 753
 754         node = treeSearch(self->root, self->nil, index);
 755
 756         if (node == self->nil) {
 757                 *ptr = NULL;
 758                 return NULL;
 759         } else {
 760                 *ptr = node;
 761                 return node->data;
 762         }
 763 }
 764
 765 int WMBagIndexForIterator(WMBag * bag, WMBagIterator ptr)
 766 {
 767         return ((W_Node *) ptr)->index;
 768 }