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