11 typedef struct W_Node
{
12 struct W_Node
*parent
;
22 typedef struct W_TreeBag
{
25 W_Node
*nil
; /* sentinel */
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*,void*), void *data
);
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
= {
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
)
94 node
->right
= node2
->left
;
96 node2
->left
->parent
= node
;
98 node2
->parent
= node
->parent
;
100 if (node
->parent
== tree
->nil
) {
104 node
->parent
->left
= node2
;
106 node
->parent
->right
= node2
;
110 node
->parent
= node2
;
115 static void rightRotate(W_TreeBag
*tree
, W_Node
*node
)
120 node
->left
= node2
->right
;
122 node2
->right
->parent
= node
;
124 node2
->parent
= node
->parent
;
126 if (node
->parent
== tree
->nil
) {
130 node
->parent
->left
= node2
;
132 node
->parent
->right
= node2
;
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
) {
148 if (node
->index
<= x
->index
)
156 else if (node
->index
<= y
->index
)
163 static void rbTreeInsert(W_TreeBag
*tree
, W_Node
*node
)
167 treeInsert(tree
, node
);
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';
179 node
->parent
->parent
->color
= 'R';
180 node
= node
->parent
->parent
;
183 if (IS_RIGHT(node
)) {
185 leftRotate(tree
, node
);
187 node
->parent
->color
= 'B';
188 node
->parent
->parent
->color
= 'R';
189 rightRotate(tree
, node
->parent
->parent
);
192 y
= node
->parent
->parent
->left
;
194 if (y
->color
== 'R') {
196 node
->parent
->color
= 'B';
198 node
->parent
->parent
->color
= 'R';
199 node
= node
->parent
->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
)
221 while (node
!= tree
->root
&& node
->color
== 'B') {
223 w
= node
->parent
->right
;
224 if (w
->color
== 'R') {
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') {
234 if (w
->right
->color
== 'B') {
235 w
->left
->color
= 'B';
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
);
247 w
= node
->parent
->left
;
248 if (w
->color
== 'R') {
250 node
->parent
->color
= 'R';
251 rightRotate(tree
, node
->parent
);
252 w
= node
->parent
->left
;
254 if (w
->left
->color
== 'B' && w
->right
->color
== 'B') {
258 if (w
->left
->color
== 'B') {
259 w
->right
->color
= 'B';
262 w
= node
->parent
->left
;
264 w
->color
= node
->parent
->color
;
265 node
->parent
->color
= 'B';
266 w
->left
->color
= 'B';
267 rightRotate(tree
, node
->parent
);
277 static W_Node
*treeMinimum(W_Node
*node
, W_Node
*nil
)
279 while (node
->left
!= nil
)
285 static W_Node
*treeMaximum(W_Node
*node
, W_Node
*nil
)
287 while (node
->right
!= nil
)
293 static W_Node
*treeSuccessor(W_Node
*node
, W_Node
*nil
)
297 if (node
->right
!= nil
) {
298 return treeMinimum(node
->right
, nil
);
301 while (y
!= nil
&& node
== y
->right
) {
309 static W_Node
*treePredecessor(W_Node
*node
, W_Node
*nil
)
313 if (node
->left
!= nil
) {
314 return treeMaximum(node
->left
, nil
);
317 while (y
!= nil
&& node
== y
->left
) {
325 static W_Node
*rbTreeDelete(W_TreeBag
*tree
, W_Node
*node
)
327 W_Node
*nil
= tree
->nil
;
330 if (node
->left
== nil
|| node
->right
== nil
) {
333 y
= treeSuccessor(node
, nil
);
336 if (y
->left
!= nil
) {
342 x
->parent
= y
->parent
;
344 if (y
->parent
== nil
) {
350 y
->parent
->right
= x
;
354 node
->index
= y
->index
;
355 node
->data
= y
->data
;
357 if (y
->color
== 'B') {
358 rbDeleteFixup(tree
, x
);
366 static W_Node
*treeSearch(W_Node
*root
, W_Node
*nil
, int index
)
368 if (root
== nil
|| root
->index
== index
) {
372 if (index
< root
->index
) {
373 return treeSearch(root
->left
, nil
, index
);
375 return treeSearch(root
->right
, nil
, index
);
380 static W_Node
*treeFind(W_Node
*root
, W_Node
*nil
, void *data
)
384 if (root
== nil
|| root
->data
== data
)
387 tmp
= treeFind(root
->left
, nil
, data
);
391 tmp
= treeFind(root
->right
, nil
, data
);
401 static char buf
[512];
403 static void printNodes(W_Node
*node
, W_Node
*nil
, int depth
)
409 printNodes(node
->left
, nil
, depth
+1);
411 memset(buf
, ' ', depth
*2);
414 printf("%s/(%2i\n", buf
, node
->index
);
416 printf("%s\\(%2i\n", buf
, node
->index
);
418 printNodes(node
->right
, nil
, depth
+1);
422 void PrintTree(WMBag
*bag
)
424 W_TreeBag
*tree
= (W_TreeBag
*)bag
->data
;
426 printNodes(tree
->root
, tree
->nil
, 0);
433 #define SELF ((W_TreeBag*)self->data)
435 WMBag
*WMCreateTreeBag(void)
437 return WMCreateTreeBagWithDestructor(NULL
);
441 WMBag
*WMCreateTreeBagWithDestructor(void (*destructor
)(void*))
446 bag
= wmalloc(sizeof(WMBag
));
448 bag
->data
= tree
= wmalloc(sizeof(W_TreeBag
));
449 memset(tree
, 0, sizeof(W_TreeBag
));
451 tree
->nil
= wmalloc(sizeof(W_Node
));
452 memset(tree
->nil
, 0, sizeof(W_Node
));
453 tree
->nil
->left
= tree
->nil
->right
= tree
->nil
->parent
= tree
->nil
;
454 tree
->nil
->index
= WBNotFound
;
456 tree
->root
= tree
->nil
;
458 bag
->destructor
= destructor
;
460 bag
->func
= bagFunctions
;
466 static int getItemCount(WMBag
*self
)
472 static int appendBag(WMBag
*self
, WMBag
*bag
)
477 for (data
= first(bag
, &ptr
); data
!= NULL
; data
= next(bag
, &ptr
)) {
478 if (!putInBag(self
, data
))
487 static int putInBag(WMBag
*self
, void *item
)
492 ptr
= wmalloc(sizeof(W_Node
));
495 ptr
->index
= SELF
->count
;
496 ptr
->left
= SELF
->nil
;
497 ptr
->right
= SELF
->nil
;
498 ptr
->parent
= SELF
->nil
;
500 rbTreeInsert(SELF
, ptr
);
508 static int insertInBag(WMBag
*self
, int index
, void *item
)
512 ptr
= wmalloc(sizeof(W_Node
));
516 ptr
->left
= SELF
->nil
;
517 ptr
->right
= SELF
->nil
;
518 ptr
->parent
= SELF
->nil
;
520 rbTreeInsert(SELF
, ptr
);
522 while ((ptr
= treeSuccessor(ptr
, SELF
->nil
)) != SELF
->nil
) {
534 static int removeFromBag(WMBag
*self
, void *item
)
536 W_Node
*ptr
= treeFind(SELF
->root
, SELF
->nil
, item
);
538 if (ptr
!= SELF
->nil
) {
543 tmp
= treeSuccessor(ptr
, SELF
->nil
);
544 while (tmp
!= SELF
->nil
) {
546 tmp
= treeSuccessor(tmp
, SELF
->nil
);
549 ptr
= rbTreeDelete(SELF
, ptr
);
550 if (self
->destructor
)
551 self
->destructor(ptr
->data
);
562 static int eraseFromBag(WMBag
*self
, int index
)
564 W_Node
*ptr
= treeSearch(SELF
->root
, SELF
->nil
, index
);
566 if (ptr
!= SELF
->nil
) {
570 ptr
= rbTreeDelete(SELF
, ptr
);
571 if (self
->destructor
)
572 self
->destructor(ptr
->data
);
575 wassertrv(SELF
->count
== 0||SELF
->root
->index
>= 0, 1);
584 static int deleteFromBag(WMBag
*self
, int index
)
586 W_Node
*ptr
= treeSearch(SELF
->root
, SELF
->nil
, index
);
588 if (ptr
!= SELF
->nil
) {
593 tmp
= treeSuccessor(ptr
, SELF
->nil
);
594 while (tmp
!= SELF
->nil
) {
596 tmp
= treeSuccessor(tmp
, SELF
->nil
);
599 ptr
= rbTreeDelete(SELF
, ptr
);
600 if (self
->destructor
)
601 self
->destructor(ptr
->data
);
604 wassertrv(SELF
->count
== 0||SELF
->root
->index
>= 0, 1);
613 static void *getFromBag(WMBag
*self
, int index
)
617 node
= treeSearch(SELF
->root
, SELF
->nil
, index
);
618 if (node
!= SELF
->nil
)
626 static int firstInBag(WMBag
*self
, void *item
)
630 node
= treeFind(SELF
->root
, SELF
->nil
, item
);
631 if (node
!= SELF
->nil
)
639 static int treeCount(W_Node
*root
, W_Node
*nil
, void *item
)
646 if (root
->data
== item
)
649 if (root
->left
!= nil
)
650 count
+= treeCount(root
->left
, nil
, item
);
652 if (root
->right
!= nil
)
653 count
+= treeCount(root
->right
, nil
, item
);
660 static int countInBag(WMBag
*self
, void *item
)
662 return treeCount(SELF
->root
, SELF
->nil
, item
);
666 static void *replaceInBag(WMBag
*self
, int index
, void *item
)
668 W_Node
*ptr
= treeSearch(SELF
->root
, SELF
->nil
, index
);
673 ptr
= rbTreeDelete(SELF
, ptr
);
674 if (self
->destructor
)
675 self
->destructor(ptr
->data
);
677 } else if (ptr
!= SELF
->nil
) {
683 ptr
= wmalloc(sizeof(W_Node
));
687 ptr
->left
= SELF
->nil
;
688 ptr
->right
= SELF
->nil
;
689 ptr
->parent
= SELF
->nil
;
691 rbTreeInsert(SELF
, ptr
);
702 static int sortBag(WMBag
*self
, int (*comparer
)(const void*, const void*))
708 if (SELF
->count
== 0)
711 items
= wmalloc(sizeof(void*)*SELF
->count
);
714 tmp
= treeMinimum(SELF
->root
, SELF
->nil
);
715 while (tmp
!= SELF
->nil
) {
716 items
[i
++] = tmp
->data
;
717 tmp
= treeSuccessor(tmp
, SELF
->nil
);
720 qsort(&items
[0], SELF
->count
, sizeof(void*), comparer
);
723 tmp
= treeMinimum(SELF
->root
, SELF
->nil
);
724 while (tmp
!= SELF
->nil
) {
726 tmp
->data
= items
[i
++];
727 tmp
= treeSuccessor(tmp
, SELF
->nil
);
738 static void deleteTree(WMBag
*self
, W_Node
*node
)
740 if (node
== SELF
->nil
)
743 deleteTree(self
, node
->left
);
745 if (self
->destructor
)
746 self
->destructor(node
->data
);
748 deleteTree(self
, node
->right
);
754 static void emptyBag(WMBag
*self
)
756 deleteTree(self
, SELF
->root
);
757 SELF
->root
= SELF
->nil
;
762 static void freeBag(WMBag
*self
)
774 static void mapTree(W_TreeBag
*tree
, W_Node
*node
,
775 void (*function
)(void*, void*), void *data
)
777 if (node
== tree
->nil
)
780 mapTree(tree
, node
->left
, function
, data
);
782 (*function
)(node
->data
, data
);
784 mapTree(tree
, node
->right
, function
, data
);
788 static void mapBag(WMBag
*self
, void (*function
)(void*, void*), void *data
)
790 mapTree(SELF
, SELF
->root
, function
, data
);
795 static int findInTree(W_TreeBag
*tree
, W_Node
*node
,
796 int (*function
)(void*,void*), void *cdata
)
800 if (node
== tree
->nil
)
803 index
= findInTree(tree
, node
->left
, function
, cdata
);
804 if (index
!= WBNotFound
)
807 if ((*function
)(node
->data
, cdata
)) {
811 return findInTree(tree
, node
->right
, function
, cdata
);
815 static int findInBag(WMBag
*self
, int (*match
)(void*,void*), void *cdata
)
817 return findInTree(SELF
, SELF
->root
, match
, cdata
);
823 static void *first(WMBag
*self
, WMBagIterator
*ptr
)
827 node
= treeMinimum(SELF
->root
, SELF
->nil
);
829 if (node
== SELF
->nil
) {
842 static void *last(WMBag
*self
, WMBagIterator
*ptr
)
847 node
= treeMaximum(SELF
->root
, SELF
->nil
);
849 if (node
== SELF
->nil
) {
862 static void *next(WMBag
*self
, WMBagIterator
*ptr
)
869 node
= treeSuccessor(*ptr
, SELF
->nil
);
871 if (node
== SELF
->nil
) {
884 static void *previous(WMBag
*self
, WMBagIterator
*ptr
)
891 node
= treePredecessor(*ptr
, SELF
->nil
);
894 if (node
== SELF
->nil
) {
907 static void *iteratorAtIndex(WMBag
*self
, int index
, WMBagIterator
*ptr
)
911 node
= treeSearch(SELF
->root
, SELF
->nil
, index
);
913 if (node
== SELF
->nil
) {
923 static int indexForIterator(WMBag
*bag
, WMBagIterator ptr
)
925 return ((W_Node
*)ptr
)->index
;