*** empty log message ***
[wmaker-crm.git] / WINGs / bagtree.c
blob7e45c0e3731a9e6eb21e296081c1267c1453821c
5 #include <stdlib.h>
6 #include <string.h>
8 #include "WUtil.h"
11 typedef struct W_Node {
12 struct W_Node *parent;
13 struct W_Node *left;
14 struct W_Node *right;
15 int color;
17 void *data;
18 int index;
19 } W_Node;
22 typedef struct W_TreeBag {
23 W_Node *root;
25 W_Node *nil; /* sentinel */
27 int count;
28 } W_TreeBag;
32 static int getItemCount(WMBag *self);
33 static int appendBag(WMBag *self, WMBag *bag);
34 static int putInBag(WMBag *self, void *item);
35 static int insertInBag(WMBag *self, int index, void *item);
36 static int removeFromBag(WMBag *bag, void *item);
37 static int eraseFromBag(WMBag *bag, int index);
38 static int deleteFromBag(WMBag *bag, int index);
39 static void *getFromBag(WMBag *bag, int index);
40 static int countInBag(WMBag *bag, void *item);
41 static int firstInBag(WMBag *bag, void *item);
42 static void *replaceInBag(WMBag *bag, int index, void *item);
43 static int sortBag(WMBag *bag, int (*comparer)(const void*, const void*));
44 static void emptyBag(WMBag *bag);
45 static void freeBag(WMBag *bag);
46 static void mapBag(WMBag *bag, void (*function)(void*, void*), void *data);
47 static int findInBag(WMBag *bag, int (*match)(void*));;
48 static void *first(WMBag *bag, WMBagIterator *ptr);
49 static void *last(WMBag *bag, WMBagIterator *ptr);
50 static void *next(WMBag *bag, WMBagIterator *ptr);
51 static void *previous(WMBag *bag, WMBagIterator *ptr);
52 static void *iteratorAtIndex(WMBag *bag, int index, WMBagIterator *ptr);
53 static int indexForIterator(WMBag *bag, WMBagIterator ptr);
56 static W_BagFunctions bagFunctions = {
57 getItemCount,
58 appendBag,
59 putInBag,
60 insertInBag,
61 removeFromBag,
62 eraseFromBag,
63 deleteFromBag,
64 getFromBag,
65 firstInBag,
66 countInBag,
67 replaceInBag,
68 sortBag,
69 emptyBag,
70 freeBag,
71 mapBag,
72 findInBag,
73 first,
74 last,
75 next,
76 previous,
77 iteratorAtIndex,
78 indexForIterator
84 #define IS_LEFT(node) (node == node->parent->left)
85 #define IS_RIGHT(node) (node == node->parent->right)
89 static void leftRotate(W_TreeBag *tree, W_Node *node)
91 W_Node *node2;
93 node2 = node->right;
94 node->right = node2->left;
96 node2->left->parent = node;
98 node2->parent = node->parent;
100 if (node->parent == tree->nil) {
101 tree->root = node2;
102 } else {
103 if (IS_LEFT(node)) {
104 node->parent->left = node2;
105 } else {
106 node->parent->right = node2;
109 node2->left = node;
110 node->parent = node2;
115 static void rightRotate(W_TreeBag *tree, W_Node *node)
117 W_Node *node2;
119 node2 = node->left;
120 node->left = node2->right;
122 node2->right->parent = node;
124 node2->parent = node->parent;
126 if (node->parent == tree->nil) {
127 tree->root = node2;
128 } else {
129 if (IS_LEFT(node)) {
130 node->parent->left = node2;
131 } else {
132 node->parent->right = node2;
135 node2->right = node;
136 node->parent = node2;
141 static void treeInsert(W_TreeBag *tree, W_Node *node)
143 W_Node *y = tree->nil;
144 W_Node *x = tree->root;
146 while (x != tree->nil) {
147 y = x;
148 if (node->index < x->index)
149 x = x->left;
150 else
151 x = x->right;
153 node->parent = y;
154 if (y == tree->nil)
155 tree->root = node;
156 else if (node->index < y->index)
157 y->left = node;
158 else
159 y->right = node;
163 static void rbTreeInsert(W_TreeBag *tree, W_Node *node)
165 W_Node *y;
167 treeInsert(tree, node);
169 node->color = 'R';
171 while (node != tree->root && node->parent->color == 'R') {
172 if (IS_LEFT(node->parent)) {
173 y = node->parent->parent->right;
175 if (y->color == 'R') {
177 node->parent->color = 'B';
178 y->color = 'B';
179 node->parent->parent->color = 'R';
180 node = node->parent->parent;
182 } else {
183 if (IS_RIGHT(node)) {
184 node = node->parent;
185 leftRotate(tree, node);
187 node->parent->color = 'B';
188 node->parent->parent->color = 'R';
189 rightRotate(tree, node->parent->parent);
191 } else {
192 y = node->parent->parent->left;
194 if (y->color == 'R') {
196 node->parent->color = 'B';
197 y->color = 'B';
198 node->parent->parent->color = 'R';
199 node = node->parent->parent;
201 } else {
202 if (IS_LEFT(node)) {
203 node = node->parent;
204 rightRotate(tree, node);
206 node->parent->color = 'B';
207 node->parent->parent->color = 'R';
208 leftRotate(tree, node->parent->parent);
212 tree->root->color = 'B';
217 static void rbDeleteFixup(W_TreeBag *tree, W_Node *node)
219 W_Node *w;
221 while (node != tree->root && node->color == 'B') {
222 if (IS_LEFT(node)) {
223 w = node->parent->right;
224 if (w->color == 'R') {
225 w->color = 'B';
226 node->parent->color = 'R';
227 leftRotate(tree, node->parent);
228 w = node->parent->right;
230 if (w->left->color == 'B' && w->right->color == 'B') {
231 w->color = 'R';
232 node = node->parent;
233 } else {
234 if (w->right->color == 'B') {
235 w->left->color = 'B';
236 w->color = 'R';
237 rightRotate(tree, w);
238 w = node->parent->right;
240 w->color = node->parent->color;
241 node->parent->color = 'B';
242 w->right->color = 'B';
243 leftRotate(tree, node->parent);
244 node = tree->root;
246 } else {
247 w = node->parent->left;
248 if (w->color == 'R') {
249 w->color = 'B';
250 node->parent->color = 'R';
251 leftRotate(tree, node->parent);
252 w = node->parent->left;
254 if (w->left->color == 'B' && w->right->color == 'B') {
255 w->color = 'R';
256 node = node->parent;
257 } else {
258 if (w->left->color == 'B') {
259 w->right->color = 'B';
260 w->color = 'R';
261 rightRotate(tree, w);
262 w = node->parent->left;
264 w->color = node->parent->color;
265 node->parent->color = 'B';
266 w->left->color = 'B';
267 leftRotate(tree, node->parent);
268 node = tree->root;
272 node->color = 'B';
276 static W_Node *treeMinimum(W_Node *node, W_Node *nil)
278 while (node->left != nil)
279 node = node->left;
280 return node;
284 static W_Node *treeMaximum(W_Node *node, W_Node *nil)
286 while (node->right != nil)
287 node = node->right;
288 return node;
292 static W_Node *treeSuccessor(W_Node *node, W_Node *nil)
294 W_Node *y;
296 if (node->right != nil) {
297 return treeMinimum(node->right, nil);
299 y = node->parent;
300 while (y != nil && node == y->right) {
301 node = y;
302 y = y->parent;
304 return y;
308 static W_Node *treePredecessor(W_Node *node, W_Node *nil)
310 W_Node *y;
312 if (node->left != nil) {
313 return treeMaximum(node->left, nil);
315 y = node->parent;
316 while (y != nil && node == y->left) {
317 node = y;
318 y = y->parent;
320 return y;
324 static W_Node *rbTreeDelete(W_TreeBag *tree, W_Node *node)
326 W_Node *nil = tree->nil;
327 W_Node *x, *y;
329 if (node->left == nil || node->right == nil) {
330 y = node;
331 } else {
332 y = treeSuccessor(node, nil);
335 if (y->left != nil) {
336 x = y->left;
337 } else {
338 x = y->right;
341 x->parent = y->parent;
343 if (y->parent == nil) {
344 tree->root = x;
345 } else {
346 if (IS_LEFT(y)) {
347 y->parent->left = x;
348 } else {
349 y->parent->right = x;
352 if (y != node) {
353 node->index = y->index;
354 node->data = y->data;
356 if (y->color == 'B') {
357 rbDeleteFixup(tree, x);
360 return y;
365 static W_Node *treeSearch(W_Node *root, W_Node *nil, int index)
367 if (root == nil || root->index == index) {
368 return root;
371 if (index < root->index) {
372 return treeSearch(root->left, nil, index);
373 } else {
374 return treeSearch(root->right, nil, index);
379 static W_Node *treeFind(W_Node *root, W_Node *nil, void *data)
381 W_Node *tmp;
383 if (root == nil || root->data == data)
384 return root;
386 tmp = treeFind(root->left, nil, data);
387 if (tmp != nil)
388 return tmp;
390 tmp = treeFind(root->right, nil, data);
392 return tmp;
399 #if 0
400 static char buf[512];
402 static void printNodes(W_Node *node, W_Node *nil, int depth)
404 if (node == nil) {
405 return;
408 printNodes(node->left, nil, depth+1);
410 memset(buf, ' ', depth*2);
411 buf[depth*2] = 0;
412 if (IS_LEFT(node))
413 printf("%s/(%2i\n", buf, node->index);
414 else
415 printf("%s\\(%2i\n", buf, node->index);
417 printNodes(node->right, nil, depth+1);
421 void PrintTree(WMBag *bag)
423 W_TreeBag *tree = (W_TreeBag*)bag->data;
425 printNodes(tree->root, tree->nil, 0);
427 #endif
432 #define SELF ((W_TreeBag*)self->data)
434 WMBag *WMCreateTreeBag(void)
436 return WMCreateTreeBagWithDestructor(NULL);
440 WMBag *WMCreateTreeBagWithDestructor(void (*destructor)(void*))
442 WMBag *bag;
443 W_TreeBag *tree;
445 bag = wmalloc(sizeof(WMBag));
447 bag->data = tree = wmalloc(sizeof(W_TreeBag));
448 memset(tree, 0, sizeof(W_TreeBag));
450 tree->nil = wmalloc(sizeof(W_Node));
451 memset(tree->nil, 0, sizeof(W_Node));
452 tree->nil->left = tree->nil->right = tree->nil->parent = tree->nil;
453 tree->nil->index = WBNotFound;
455 tree->root = tree->nil;
457 bag->destructor = destructor;
459 bag->func = bagFunctions;
461 return bag;
465 static int getItemCount(WMBag *self)
467 return SELF->count;
471 static int appendBag(WMBag *self, WMBag *bag)
473 WMBagIterator ptr;
474 void *data;
476 for (data = first(bag, &ptr); data != NULL; data = next(bag, &ptr)) {
477 if (!putInBag(self, data))
478 return 0;
481 return 1;
485 static int putInBag(WMBag *self, void *item)
487 W_Node *ptr;
489 ptr = wmalloc(sizeof(W_Node));
491 ptr->data = item;
492 ptr->index = SELF->count;
493 ptr->left = SELF->nil;
494 ptr->right = SELF->nil;
495 ptr->parent = SELF->nil;
497 rbTreeInsert(SELF, ptr);
499 SELF->count++;
501 return 1;
505 static int insertInBag(WMBag *self, int index, void *item)
507 W_Node *ptr;
509 ptr = wmalloc(sizeof(W_Node));
511 ptr->data = item;
512 ptr->index = index;
513 ptr->left = SELF->nil;
514 ptr->right = SELF->nil;
515 ptr->parent = SELF->nil;
517 rbTreeInsert(SELF, ptr);
519 while ((ptr = treeSuccessor(ptr, SELF->nil)) != SELF->nil) {
520 ptr->index++;
524 SELF->count++;
526 return 1;
531 static int removeFromBag(WMBag *self, void *item)
533 W_Node *ptr = treeFind(SELF->root, SELF->nil, item);
535 if (ptr != SELF->nil) {
536 W_Node *tmp;
538 SELF->count--;
540 tmp = treeSuccessor(ptr, SELF->nil);
541 while (tmp != SELF->nil) {
542 tmp->index--;
543 tmp = treeSuccessor(tmp, SELF->nil);
546 ptr = rbTreeDelete(SELF, ptr);
547 free(ptr);
549 return 1;
550 } else {
551 return 0;
557 static int eraseFromBag(WMBag *self, int index)
559 W_Node *ptr = treeSearch(SELF->root, SELF->nil, index);
561 if (ptr != SELF->nil) {
563 SELF->count--;
565 ptr = rbTreeDelete(SELF, ptr);
566 free(ptr);
568 return 1;
569 } else {
570 return 0;
575 static int deleteFromBag(WMBag *self, int index)
577 W_Node *ptr = treeSearch(SELF->root, SELF->nil, index);
579 if (ptr != SELF->nil) {
580 W_Node *tmp;
582 SELF->count--;
584 tmp = treeSuccessor(ptr, SELF->nil);
585 while (tmp != SELF->nil) {
586 tmp->index--;
587 tmp = treeSuccessor(tmp, SELF->nil);
590 ptr = rbTreeDelete(SELF, ptr);
591 free(ptr);
593 return 1;
594 } else {
595 return 0;
600 static void *getFromBag(WMBag *self, int index)
602 W_Node *node;
604 node = treeSearch(SELF->root, SELF->nil, index);
605 if (node != SELF->nil)
606 return node->data;
607 else
608 return NULL;
613 static int firstInBag(WMBag *self, void *item)
615 W_Node *node;
617 node = treeFind(SELF->root, SELF->nil, item);
618 if (node != SELF->nil)
619 return node->index;
620 else
621 return WBNotFound;
626 static int treeCount(W_Node *root, W_Node *nil, void *item)
628 int count = 0;
630 if (root == nil)
631 return 0;
633 if (root->data == item)
634 count++;
636 if (root->left != nil)
637 count += treeCount(root->left, nil, item);
639 if (root->right != nil)
640 count += treeCount(root->right, nil, item);
642 return count;
647 static int countInBag(WMBag *self, void *item)
649 return treeCount(SELF->root, SELF->nil, item);
653 static void *replaceInBag(WMBag *self, int index, void *item)
655 W_Node *ptr = treeSearch(SELF->root, SELF->nil, index);
656 void *old = NULL;
658 if (item == NULL) {
659 SELF->count--;
661 ptr = rbTreeDelete(SELF, ptr);
662 free(ptr);
663 } else if (ptr != SELF->nil) {
664 old = ptr->data;
665 ptr->data = item;
666 } else {
667 W_Node *ptr;
669 ptr = wmalloc(sizeof(W_Node));
671 ptr->data = item;
672 ptr->index = index;
673 ptr->left = SELF->nil;
674 ptr->right = SELF->nil;
675 ptr->parent = SELF->nil;
677 rbTreeInsert(SELF, ptr);
679 SELF->count++;
682 return old;
688 static int sortBag(WMBag *self, int (*comparer)(const void*, const void*))
690 void **items;
691 W_Node *tmp;
692 int i;
695 items = wmalloc(sizeof(void*)*SELF->count);
696 i = 0;
698 tmp = treeMinimum(SELF->root, SELF->nil);
699 while (tmp != SELF->nil) {
700 items[i++] = tmp->data;
701 tmp = treeSuccessor(tmp, SELF->nil);
704 qsort(&items[0], SELF->count, sizeof(void*), comparer);
706 i = 0;
707 tmp = treeMinimum(SELF->root, SELF->nil);
708 while (tmp != SELF->nil) {
709 tmp->index = i;
710 tmp->data = items[i++];
711 tmp = treeSuccessor(tmp, SELF->nil);
714 wfree(items);
716 return 1;
722 static void deleteTree(WMBag *self, W_Node *node)
724 if (node == SELF->nil)
725 return;
727 deleteTree(self, node->left);
729 if (self->destructor)
730 self->destructor(node->data);
732 deleteTree(self, node->right);
734 free(node);
738 static void emptyBag(WMBag *self)
740 deleteTree(self, SELF->root);
741 SELF->root = SELF->nil;
742 SELF->count = 0;
746 static void freeBag(WMBag *self)
748 emptyBag(self);
750 free(self);
755 static void mapTree(W_TreeBag *tree, W_Node *node,
756 void (*function)(void*, void*), void *data)
758 if (node == tree->nil)
759 return;
761 mapTree(tree, node->left, function, data);
763 (*function)(node->data, data);
765 mapTree(tree, node->right, function, data);
769 static void mapBag(WMBag *self, void (*function)(void*, void*), void *data)
771 mapTree(SELF, SELF->root, function, data);
776 static int findInTree(W_TreeBag *tree, W_Node *node, int (*function)(void*))
778 int index;
780 if (node == tree->nil)
781 return WBNotFound;
783 index = findInTree(tree, node->left, function);
784 if (index != WBNotFound)
785 return index;
787 if ((*function)(node->data)) {
788 return node->index;
791 return findInTree(tree, node->right, function);
795 static int findInBag(WMBag *self, int (*match)(void*))
797 return findInTree(SELF, SELF->root, match);
803 static void *first(WMBag *self, WMBagIterator *ptr)
805 W_Node *node;
807 node = treeMinimum(SELF->root, SELF->nil);
809 if (node == SELF->nil) {
810 *ptr = NULL;
812 return NULL;
813 } else {
814 *ptr = node;
816 return node->data;
822 static void *last(WMBag *self, WMBagIterator *ptr)
825 W_Node *node;
827 node = treeMaximum(SELF->root, SELF->nil);
829 if (node == SELF->nil) {
830 *ptr = NULL;
832 return NULL;
833 } else {
834 *ptr = node;
836 return node->data;
842 static void *next(WMBag *self, WMBagIterator *ptr)
844 W_Node *node;
846 if (*ptr == NULL)
847 return NULL;
849 node = treeSuccessor(*ptr, SELF->nil);
851 if (node == SELF->nil) {
852 *ptr = NULL;
854 return NULL;
855 } else {
856 *ptr = node;
858 return node->data;
864 static void *previous(WMBag *self, WMBagIterator *ptr)
866 W_Node *node;
868 if (*ptr == NULL)
869 return NULL;
871 node = treePredecessor(*ptr, SELF->nil);
874 if (node == SELF->nil) {
875 *ptr = NULL;
877 return NULL;
878 } else {
879 *ptr = node;
881 return node->data;
887 static void *iteratorAtIndex(WMBag *self, int index, WMBagIterator *ptr)
889 W_Node *node;
891 node = treeSearch(SELF->root, SELF->nil, index);
893 if (node == SELF->nil) {
894 *ptr = NULL;
895 return NULL;
896 } else {
897 *ptr = node;
898 return node->data;
903 static int indexForIterator(WMBag *bag, WMBagIterator ptr)
905 return ((W_Node*)ptr)->index;