11 typedef struct W_Node
{
12 struct W_Node
*parent
;
22 typedef struct W_Bag
{
25 W_Node
*nil
; /* sentinel */
29 void (*destructor
)(void *item
);
34 static int getItemCount(WMBag
*self
);
35 static int appendBag(WMBag
*self
, WMBag
*bag
);
36 static int putInBag(WMBag
*self
, void *item
);
37 static int insertInBag(WMBag
*self
, int index
, void *item
);
38 static int removeFromBag(WMBag
*bag
, void *item
);
39 static int eraseFromBag(WMBag
*bag
, int index
);
40 static int deleteFromBag(WMBag
*bag
, int index
);
41 static void *getFromBag(WMBag
*bag
, int index
);
42 static int countInBag(WMBag
*bag
, void *item
);
43 static int firstInBag(WMBag
*bag
, void *item
);
44 static void *replaceInBag(WMBag
*bag
, int index
, void *item
);
45 static int sortBag(WMBag
*bag
, int (*comparer
)(const void*, const void*));
46 static void emptyBag(WMBag
*bag
);
47 static void freeBag(WMBag
*bag
);
48 static void mapBag(WMBag
*bag
, void (*function
)(void*, void*), void *data
);
49 static int findInBag(WMBag
*bag
, int (*match
)(void*,void*), void *data
);
50 static void *first(WMBag
*bag
, WMBagIterator
*ptr
);
51 static void *last(WMBag
*bag
, WMBagIterator
*ptr
);
52 static void *next(WMBag
*bag
, WMBagIterator
*ptr
);
53 static void *previous(WMBag
*bag
, WMBagIterator
*ptr
);
54 static void *iteratorAtIndex(WMBag
*bag
, int index
, WMBagIterator
*ptr
);
55 static int indexForIterator(WMBag
*bag
, WMBagIterator ptr
);
59 #define IS_LEFT(node) (node == node->parent->left)
60 #define IS_RIGHT(node) (node == node->parent->right)
65 leftRotate(W_Bag
*tree
, W_Node
*node
)
70 node
->right
= node2
->left
;
72 node2
->left
->parent
= node
;
74 node2
->parent
= node
->parent
;
76 if (node
->parent
== tree
->nil
) {
80 node
->parent
->left
= node2
;
82 node
->parent
->right
= node2
;
92 rightRotate(W_Bag
*tree
, W_Node
*node
)
97 node
->left
= node2
->right
;
99 node2
->right
->parent
= node
;
101 node2
->parent
= node
->parent
;
103 if (node
->parent
== tree
->nil
) {
107 node
->parent
->left
= node2
;
109 node
->parent
->right
= node2
;
113 node
->parent
= node2
;
118 treeInsert(W_Bag
*tree
, W_Node
*node
)
120 W_Node
*y
= tree
->nil
;
121 W_Node
*x
= tree
->root
;
123 while (x
!= tree
->nil
) {
125 if (node
->index
<= x
->index
)
133 else if (node
->index
<= y
->index
)
141 rbTreeInsert(W_Bag
*tree
, W_Node
*node
)
145 treeInsert(tree
, node
);
149 while (node
!= tree
->root
&& node
->parent
->color
== 'R') {
150 if (IS_LEFT(node
->parent
)) {
151 y
= node
->parent
->parent
->right
;
153 if (y
->color
== 'R') {
155 node
->parent
->color
= 'B';
157 node
->parent
->parent
->color
= 'R';
158 node
= node
->parent
->parent
;
161 if (IS_RIGHT(node
)) {
163 leftRotate(tree
, node
);
165 node
->parent
->color
= 'B';
166 node
->parent
->parent
->color
= 'R';
167 rightRotate(tree
, node
->parent
->parent
);
170 y
= node
->parent
->parent
->left
;
172 if (y
->color
== 'R') {
174 node
->parent
->color
= 'B';
176 node
->parent
->parent
->color
= 'R';
177 node
= node
->parent
->parent
;
182 rightRotate(tree
, node
);
184 node
->parent
->color
= 'B';
185 node
->parent
->parent
->color
= 'R';
186 leftRotate(tree
, node
->parent
->parent
);
190 tree
->root
->color
= 'B';
195 rbDeleteFixup(W_Bag
*tree
, W_Node
*node
)
199 while (node
!= tree
->root
&& node
->color
== 'B') {
201 w
= node
->parent
->right
;
202 if (w
->color
== 'R') {
204 node
->parent
->color
= 'R';
205 leftRotate(tree
, node
->parent
);
206 w
= node
->parent
->right
;
208 if (w
->left
->color
== 'B' && w
->right
->color
== 'B') {
212 if (w
->right
->color
== 'B') {
213 w
->left
->color
= 'B';
215 rightRotate(tree
, w
);
216 w
= node
->parent
->right
;
218 w
->color
= node
->parent
->color
;
219 node
->parent
->color
= 'B';
220 w
->right
->color
= 'B';
221 leftRotate(tree
, node
->parent
);
225 w
= node
->parent
->left
;
226 if (w
->color
== 'R') {
228 node
->parent
->color
= 'R';
229 rightRotate(tree
, node
->parent
);
230 w
= node
->parent
->left
;
232 if (w
->left
->color
== 'B' && w
->right
->color
== 'B') {
236 if (w
->left
->color
== 'B') {
237 w
->right
->color
= 'B';
240 w
= node
->parent
->left
;
242 w
->color
= node
->parent
->color
;
243 node
->parent
->color
= 'B';
244 w
->left
->color
= 'B';
245 rightRotate(tree
, node
->parent
);
256 treeMinimum(W_Node
*node
, W_Node
*nil
)
258 while (node
->left
!= nil
)
265 treeMaximum(W_Node
*node
, W_Node
*nil
)
267 while (node
->right
!= nil
)
274 treeSuccessor(W_Node
*node
, W_Node
*nil
)
278 if (node
->right
!= nil
) {
279 return treeMinimum(node
->right
, nil
);
282 while (y
!= nil
&& node
== y
->right
) {
291 treePredecessor(W_Node
*node
, W_Node
*nil
)
295 if (node
->left
!= nil
) {
296 return treeMaximum(node
->left
, nil
);
299 while (y
!= nil
&& node
== y
->left
) {
308 rbTreeDelete(W_Bag
*tree
, W_Node
*node
)
310 W_Node
*nil
= tree
->nil
;
313 if (node
->left
== nil
|| node
->right
== nil
) {
316 y
= treeSuccessor(node
, nil
);
319 if (y
->left
!= nil
) {
325 x
->parent
= y
->parent
;
327 if (y
->parent
== nil
) {
333 y
->parent
->right
= x
;
337 node
->index
= y
->index
;
338 node
->data
= y
->data
;
340 if (y
->color
== 'B') {
341 rbDeleteFixup(tree
, x
);
349 treeSearch(W_Node
*root
, W_Node
*nil
, int index
)
351 if (root
== nil
|| root
->index
== index
) {
355 if (index
< root
->index
) {
356 return treeSearch(root
->left
, nil
, index
);
358 return treeSearch(root
->right
, nil
, index
);
364 treeFind(W_Node
*root
, W_Node
*nil
, void *data
)
368 if (root
== nil
|| root
->data
== data
)
371 tmp
= treeFind(root
->left
, nil
, data
);
375 tmp
= treeFind(root
->right
, nil
, data
);
383 static char buf
[512];
385 static void printNodes(W_Node
*node
, W_Node
*nil
, int depth
)
391 printNodes(node
->left
, nil
, depth
+1);
393 memset(buf
, ' ', depth
*2);
396 printf("%s/(%2i\n", buf
, node
->index
);
398 printf("%s\\(%2i\n", buf
, node
->index
);
400 printNodes(node
->right
, nil
, depth
+1);
404 void PrintTree(WMBag
*bag
)
406 W_TreeBag
*tree
= (W_TreeBag
*)bag
->data
;
408 printNodes(tree
->root
, tree
->nil
, 0);
413 //#define SELF ((W_TreeBag*)self->data)
416 WMCreateTreeBag(void)
418 return WMCreateTreeBagWithDestructor(NULL
);
423 WMCreateTreeBagWithDestructor(void (*destructor
)(void*))
427 bag
= wmalloc(sizeof(WMBag
));
429 memset(bag
, 0, sizeof(WMBag
));
431 bag
->nil
= wmalloc(sizeof(W_Node
));
432 memset(bag
->nil
, 0, sizeof(W_Node
));
433 bag
->nil
->left
= bag
->nil
->right
= bag
->nil
->parent
= bag
->nil
;
434 bag
->nil
->index
= WBNotFound
;
436 bag
->root
= bag
->nil
;
438 bag
->destructor
= destructor
;
445 WMGetBagItemCount(WMBag
*self
)
452 WMAppendBag(WMBag
*self
, WMBag
*bag
)
457 for (data
= WMBagFirst(bag
, &ptr
); data
!= NULL
; data
= WMBagNext(bag
, &ptr
)) {
458 if (!WMPutInBag(self
, data
))
468 WMPutInBag(WMBag
*self
, void *item
)
473 ptr
= wmalloc(sizeof(W_Node
));
476 ptr
->index
= self
->count
;
477 ptr
->left
= self
->nil
;
478 ptr
->right
= self
->nil
;
479 ptr
->parent
= self
->nil
;
481 rbTreeInsert(self
, ptr
);
490 WMInsertInBag(WMBag
*self
, int index
, void *item
)
494 ptr
= wmalloc(sizeof(W_Node
));
498 ptr
->left
= self
->nil
;
499 ptr
->right
= self
->nil
;
500 ptr
->parent
= self
->nil
;
502 rbTreeInsert(self
, ptr
);
504 while ((ptr
= treeSuccessor(ptr
, self
->nil
)) != self
->nil
) {
516 WMRemoveFromBag(WMBag
*self
, void *item
)
518 W_Node
*ptr
= treeFind(self
->root
, self
->nil
, item
);
520 if (ptr
!= self
->nil
) {
525 tmp
= treeSuccessor(ptr
, self
->nil
);
526 while (tmp
!= self
->nil
) {
528 tmp
= treeSuccessor(tmp
, self
->nil
);
531 ptr
= rbTreeDelete(self
, ptr
);
532 if (self
->destructor
)
533 self
->destructor(ptr
->data
);
544 WMEraseFromBag(WMBag
*self
, int index
)
546 W_Node
*ptr
= treeSearch(self
->root
, self
->nil
, index
);
548 if (ptr
!= self
->nil
) {
552 ptr
= rbTreeDelete(self
, ptr
);
553 if (self
->destructor
)
554 self
->destructor(ptr
->data
);
557 wassertrv(self
->count
== 0||self
->root
->index
>= 0, 1);
567 WMDeleteFromBag(WMBag
*self
, int index
)
569 W_Node
*ptr
= treeSearch(self
->root
, self
->nil
, index
);
571 if (ptr
!= self
->nil
) {
576 tmp
= treeSuccessor(ptr
, self
->nil
);
577 while (tmp
!= self
->nil
) {
579 tmp
= treeSuccessor(tmp
, self
->nil
);
582 ptr
= rbTreeDelete(self
, ptr
);
583 if (self
->destructor
)
584 self
->destructor(ptr
->data
);
587 wassertrv(self
->count
== 0||self
->root
->index
>= 0, 1);
597 WMGetFromBag(WMBag
*self
, int index
)
601 node
= treeSearch(self
->root
, self
->nil
, index
);
602 if (node
!= self
->nil
)
610 WMGetFirstInBag(WMBag
*self
, void *item
)
614 node
= treeFind(self
->root
, self
->nil
, item
);
615 if (node
!= self
->nil
)
624 treeCount(W_Node
*root
, W_Node
*nil
, void *item
)
631 if (root
->data
== item
)
634 if (root
->left
!= nil
)
635 count
+= treeCount(root
->left
, nil
, item
);
637 if (root
->right
!= nil
)
638 count
+= treeCount(root
->right
, nil
, item
);
646 WMCountInBag(WMBag
*self
, void *item
)
648 return treeCount(self
->root
, self
->nil
, item
);
653 WMReplaceInBag(WMBag
*self
, int index
, void *item
)
655 W_Node
*ptr
= treeSearch(self
->root
, self
->nil
, index
);
660 ptr
= rbTreeDelete(self
, ptr
);
661 if (self
->destructor
)
662 self
->destructor(ptr
->data
);
664 } else if (ptr
!= self
->nil
) {
670 ptr
= wmalloc(sizeof(W_Node
));
674 ptr
->left
= self
->nil
;
675 ptr
->right
= self
->nil
;
676 ptr
->parent
= self
->nil
;
678 rbTreeInsert(self
, ptr
);
688 WMSortBag(WMBag
*self
, int (*comparer
)(const void*, const void*))
694 if (self
->count
== 0)
697 items
= wmalloc(sizeof(void*)*self
->count
);
700 tmp
= treeMinimum(self
->root
, self
->nil
);
701 while (tmp
!= self
->nil
) {
702 items
[i
++] = tmp
->data
;
703 tmp
= treeSuccessor(tmp
, self
->nil
);
706 qsort(&items
[0], self
->count
, sizeof(void*), comparer
);
709 tmp
= treeMinimum(self
->root
, self
->nil
);
710 while (tmp
!= self
->nil
) {
712 tmp
->data
= items
[i
++];
713 tmp
= treeSuccessor(tmp
, self
->nil
);
723 deleteTree(WMBag
*self
, W_Node
*node
)
725 if (node
== self
->nil
)
728 deleteTree(self
, node
->left
);
730 if (self
->destructor
)
731 self
->destructor(node
->data
);
733 deleteTree(self
, node
->right
);
740 WMEmptyBag(WMBag
*self
)
742 deleteTree(self
, self
->root
);
743 self
->root
= self
->nil
;
749 WMFreeBag(WMBag
*self
)
760 mapTree(W_Bag
*tree
, W_Node
*node
, void (*function
)(void*, void*), void *data
)
762 if (node
== tree
->nil
)
765 mapTree(tree
, node
->left
, function
, data
);
767 (*function
)(node
->data
, data
);
769 mapTree(tree
, node
->right
, function
, data
);
774 WMMapBag(WMBag
*self
, void (*function
)(void*, void*), void *data
)
776 mapTree(self
, self
->root
, function
, data
);
782 findInTree(W_Bag
*tree
, W_Node
*node
, int (*function
)(void*,void*), void *cdata
)
786 if (node
== tree
->nil
)
789 index
= findInTree(tree
, node
->left
, function
, cdata
);
790 if (index
!= WBNotFound
)
793 if ((*function
)(node
->data
, cdata
)) {
797 return findInTree(tree
, node
->right
, function
, cdata
);
802 WMFindInBag(WMBag
*self
, int (*match
)(void*,void*), void *cdata
)
804 return findInTree(self
, self
->root
, match
, cdata
);
809 WMBagFirst(WMBag
*self
, WMBagIterator
*ptr
)
813 node
= treeMinimum(self
->root
, self
->nil
);
815 if (node
== self
->nil
) {
828 WMBagLast(WMBag
*self
, WMBagIterator
*ptr
)
833 node
= treeMaximum(self
->root
, self
->nil
);
835 if (node
== self
->nil
) {
848 WMBagNext(WMBag
*self
, WMBagIterator
*ptr
)
855 node
= treeSuccessor(*ptr
, self
->nil
);
857 if (node
== self
->nil
) {
870 WMBagPrevious(WMBag
*self
, WMBagIterator
*ptr
)
877 node
= treePredecessor(*ptr
, self
->nil
);
879 if (node
== self
->nil
) {
892 WMBagIteratorAtIndex(WMBag
*self
, int index
, WMBagIterator
*ptr
)
896 node
= treeSearch(self
->root
, self
->nil
, index
);
898 if (node
== self
->nil
) {
909 WMBagIndexForIterator(WMBag
*bag
, WMBagIterator ptr
)
911 return ((W_Node
*)ptr
)->index
;