7 typedef struct W_Node
{
17 typedef struct W_Bag
{
20 W_Node
*nil
; /* sentinel */
24 void (*destructor
) (void *item
);
27 #define IS_LEFT(node) (node == node->parent->left)
28 #define IS_RIGHT(node) (node == node->parent->right)
30 static void leftRotate(W_Bag
* tree
, W_Node
* node
)
35 node
->right
= node2
->left
;
37 node2
->left
->parent
= node
;
39 node2
->parent
= node
->parent
;
41 if (node
->parent
== tree
->nil
) {
45 node
->parent
->left
= node2
;
47 node
->parent
->right
= node2
;
54 static void rightRotate(W_Bag
* tree
, W_Node
* node
)
59 node
->left
= node2
->right
;
61 node2
->right
->parent
= node
;
63 node2
->parent
= node
->parent
;
65 if (node
->parent
== tree
->nil
) {
69 node
->parent
->left
= node2
;
71 node
->parent
->right
= node2
;
78 static void treeInsert(W_Bag
* tree
, W_Node
* node
)
80 W_Node
*y
= tree
->nil
;
81 W_Node
*x
= tree
->root
;
83 while (x
!= tree
->nil
) {
85 if (node
->index
<= x
->index
)
93 else if (node
->index
<= y
->index
)
99 static void rbTreeInsert(W_Bag
* tree
, W_Node
* node
)
103 treeInsert(tree
, node
);
107 while (node
!= tree
->root
&& node
->parent
->color
== 'R') {
108 if (IS_LEFT(node
->parent
)) {
109 y
= node
->parent
->parent
->right
;
111 if (y
->color
== 'R') {
113 node
->parent
->color
= 'B';
115 node
->parent
->parent
->color
= 'R';
116 node
= node
->parent
->parent
;
119 if (IS_RIGHT(node
)) {
121 leftRotate(tree
, node
);
123 node
->parent
->color
= 'B';
124 node
->parent
->parent
->color
= 'R';
125 rightRotate(tree
, node
->parent
->parent
);
128 y
= node
->parent
->parent
->left
;
130 if (y
->color
== 'R') {
132 node
->parent
->color
= 'B';
134 node
->parent
->parent
->color
= 'R';
135 node
= node
->parent
->parent
;
140 rightRotate(tree
, node
);
142 node
->parent
->color
= 'B';
143 node
->parent
->parent
->color
= 'R';
144 leftRotate(tree
, node
->parent
->parent
);
148 tree
->root
->color
= 'B';
151 static void rbDeleteFixup(W_Bag
* tree
, W_Node
* node
)
155 while (node
!= tree
->root
&& node
->color
== 'B') {
157 w
= node
->parent
->right
;
158 if (w
->color
== 'R') {
160 node
->parent
->color
= 'R';
161 leftRotate(tree
, node
->parent
);
162 w
= node
->parent
->right
;
164 if (w
->left
->color
== 'B' && w
->right
->color
== 'B') {
168 if (w
->right
->color
== 'B') {
169 w
->left
->color
= 'B';
171 rightRotate(tree
, w
);
172 w
= node
->parent
->right
;
174 w
->color
= node
->parent
->color
;
175 node
->parent
->color
= 'B';
176 w
->right
->color
= 'B';
177 leftRotate(tree
, node
->parent
);
181 w
= node
->parent
->left
;
182 if (w
->color
== 'R') {
184 node
->parent
->color
= 'R';
185 rightRotate(tree
, node
->parent
);
186 w
= node
->parent
->left
;
188 if (w
->left
->color
== 'B' && w
->right
->color
== 'B') {
192 if (w
->left
->color
== 'B') {
193 w
->right
->color
= 'B';
196 w
= node
->parent
->left
;
198 w
->color
= node
->parent
->color
;
199 node
->parent
->color
= 'B';
200 w
->left
->color
= 'B';
201 rightRotate(tree
, node
->parent
);
210 static W_Node
*treeMinimum(W_Node
* node
, W_Node
* nil
)
212 while (node
->left
!= nil
)
217 static W_Node
*treeMaximum(W_Node
* node
, W_Node
* nil
)
219 while (node
->right
!= nil
)
224 static W_Node
*treeSuccessor(W_Node
* node
, W_Node
* nil
)
228 if (node
->right
!= nil
) {
229 return treeMinimum(node
->right
, nil
);
232 while (y
!= nil
&& node
== y
->right
) {
239 static W_Node
*treePredecessor(W_Node
* node
, W_Node
* nil
)
243 if (node
->left
!= nil
) {
244 return treeMaximum(node
->left
, nil
);
247 while (y
!= nil
&& node
== y
->left
) {
254 static W_Node
*rbTreeDelete(W_Bag
* tree
, W_Node
* node
)
256 W_Node
*nil
= tree
->nil
;
259 if (node
->left
== nil
|| node
->right
== nil
) {
262 y
= treeSuccessor(node
, nil
);
265 if (y
->left
!= nil
) {
271 x
->parent
= y
->parent
;
273 if (y
->parent
== nil
) {
279 y
->parent
->right
= x
;
283 node
->index
= y
->index
;
284 node
->data
= y
->data
;
286 if (y
->color
== 'B') {
287 rbDeleteFixup(tree
, x
);
293 static W_Node
*treeSearch(W_Node
* root
, W_Node
* nil
, int index
)
295 if (root
== nil
|| root
->index
== index
) {
299 if (index
< root
->index
) {
300 return treeSearch(root
->left
, nil
, index
);
302 return treeSearch(root
->right
, nil
, index
);
306 static W_Node
*treeFind(W_Node
* root
, W_Node
* nil
, void *data
)
310 if (root
== nil
|| root
->data
== data
)
313 tmp
= treeFind(root
->left
, nil
, data
);
317 tmp
= treeFind(root
->right
, nil
, data
);
323 static char buf
[512];
325 static void printNodes(W_Node
* node
, W_Node
* nil
, int depth
)
331 printNodes(node
->left
, nil
, depth
+ 1);
333 memset(buf
, ' ', depth
* 2);
336 printf("%s/(%2i\n", buf
, node
->index
);
338 printf("%s\\(%2i\n", buf
, node
->index
);
340 printNodes(node
->right
, nil
, depth
+ 1);
343 void PrintTree(WMBag
* bag
)
345 W_TreeBag
*tree
= (W_TreeBag
*) bag
->data
;
347 printNodes(tree
->root
, tree
->nil
, 0);
351 WMBag
*WMCreateTreeBag(void)
353 return WMCreateTreeBagWithDestructor(NULL
);
356 WMBag
*WMCreateTreeBagWithDestructor(WMFreeDataProc
* destructor
)
360 bag
= wmalloc(sizeof(WMBag
));
362 memset(bag
, 0, sizeof(WMBag
));
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
;
369 bag
->root
= bag
->nil
;
371 bag
->destructor
= destructor
;
376 int WMGetBagItemCount(WMBag
* self
)
381 void WMAppendBag(WMBag
* self
, WMBag
* bag
)
386 for (data
= WMBagFirst(bag
, &ptr
); data
!= NULL
; data
= WMBagNext(bag
, &ptr
)) {
387 WMPutInBag(self
, data
);
391 void WMPutInBag(WMBag
* self
, void *item
)
395 ptr
= wmalloc(sizeof(W_Node
));
398 ptr
->index
= self
->count
;
399 ptr
->left
= self
->nil
;
400 ptr
->right
= self
->nil
;
401 ptr
->parent
= self
->nil
;
403 rbTreeInsert(self
, ptr
);
408 void WMInsertInBag(WMBag
* self
, int index
, void *item
)
412 ptr
= wmalloc(sizeof(W_Node
));
416 ptr
->left
= self
->nil
;
417 ptr
->right
= self
->nil
;
418 ptr
->parent
= self
->nil
;
420 rbTreeInsert(self
, ptr
);
422 while ((ptr
= treeSuccessor(ptr
, self
->nil
)) != self
->nil
) {
429 int WMRemoveFromBag(WMBag
* self
, void *item
)
431 W_Node
*ptr
= treeFind(self
->root
, self
->nil
, item
);
433 if (ptr
!= self
->nil
) {
438 tmp
= treeSuccessor(ptr
, self
->nil
);
439 while (tmp
!= self
->nil
) {
441 tmp
= treeSuccessor(tmp
, self
->nil
);
444 ptr
= rbTreeDelete(self
, ptr
);
445 if (self
->destructor
)
446 self
->destructor(ptr
->data
);
455 int WMEraseFromBag(WMBag
* self
, int index
)
457 W_Node
*ptr
= treeSearch(self
->root
, self
->nil
, index
);
459 if (ptr
!= self
->nil
) {
463 ptr
= rbTreeDelete(self
, ptr
);
464 if (self
->destructor
)
465 self
->destructor(ptr
->data
);
468 wassertrv(self
->count
== 0 || self
->root
->index
>= 0, 1);
476 int WMDeleteFromBag(WMBag
* self
, int index
)
478 W_Node
*ptr
= treeSearch(self
->root
, self
->nil
, index
);
480 if (ptr
!= self
->nil
) {
485 tmp
= treeSuccessor(ptr
, self
->nil
);
486 while (tmp
!= self
->nil
) {
488 tmp
= treeSuccessor(tmp
, self
->nil
);
491 ptr
= rbTreeDelete(self
, ptr
);
492 if (self
->destructor
)
493 self
->destructor(ptr
->data
);
496 wassertrv(self
->count
== 0 || self
->root
->index
>= 0, 1);
504 void *WMGetFromBag(WMBag
* self
, int index
)
508 node
= treeSearch(self
->root
, self
->nil
, index
);
509 if (node
!= self
->nil
)
515 int WMGetFirstInBag(WMBag
* self
, void *item
)
519 node
= treeFind(self
->root
, self
->nil
, item
);
520 if (node
!= self
->nil
)
526 static int treeCount(W_Node
* root
, W_Node
* nil
, void *item
)
533 if (root
->data
== item
)
536 if (root
->left
!= nil
)
537 count
+= treeCount(root
->left
, nil
, item
);
539 if (root
->right
!= nil
)
540 count
+= treeCount(root
->right
, nil
, item
);
545 int WMCountInBag(WMBag
* self
, void *item
)
547 return treeCount(self
->root
, self
->nil
, item
);
550 void *WMReplaceInBag(WMBag
* self
, int index
, void *item
)
552 W_Node
*ptr
= treeSearch(self
->root
, self
->nil
, index
);
557 ptr
= rbTreeDelete(self
, ptr
);
558 if (self
->destructor
)
559 self
->destructor(ptr
->data
);
561 } else if (ptr
!= self
->nil
) {
567 ptr
= wmalloc(sizeof(W_Node
));
571 ptr
->left
= self
->nil
;
572 ptr
->right
= self
->nil
;
573 ptr
->parent
= self
->nil
;
575 rbTreeInsert(self
, ptr
);
583 void WMSortBag(WMBag
* self
, WMCompareDataProc
* comparer
)
589 if (self
->count
== 0)
592 items
= wmalloc(sizeof(void *) * self
->count
);
595 tmp
= treeMinimum(self
->root
, self
->nil
);
596 while (tmp
!= self
->nil
) {
597 items
[i
++] = tmp
->data
;
598 tmp
= treeSuccessor(tmp
, self
->nil
);
601 qsort(&items
[0], self
->count
, sizeof(void *), comparer
);
604 tmp
= treeMinimum(self
->root
, self
->nil
);
605 while (tmp
!= self
->nil
) {
607 tmp
->data
= items
[i
++];
608 tmp
= treeSuccessor(tmp
, self
->nil
);
614 static void deleteTree(WMBag
* self
, W_Node
* node
)
616 if (node
== self
->nil
)
619 deleteTree(self
, node
->left
);
621 if (self
->destructor
)
622 self
->destructor(node
->data
);
624 deleteTree(self
, node
->right
);
629 void WMEmptyBag(WMBag
* self
)
631 deleteTree(self
, self
->root
);
632 self
->root
= self
->nil
;
636 void WMFreeBag(WMBag
* self
)
643 static void mapTree(W_Bag
* tree
, W_Node
* node
, void (*function
) (void *, void *), void *data
)
645 if (node
== tree
->nil
)
648 mapTree(tree
, node
->left
, function
, data
);
650 (*function
) (node
->data
, data
);
652 mapTree(tree
, node
->right
, function
, data
);
655 void WMMapBag(WMBag
* self
, void (*function
) (void *, void *), void *data
)
657 mapTree(self
, self
->root
, function
, data
);
660 static int findInTree(W_Bag
* tree
, W_Node
* node
, WMMatchDataProc
* function
, void *cdata
)
664 if (node
== tree
->nil
)
667 index
= findInTree(tree
, node
->left
, function
, cdata
);
668 if (index
!= WBNotFound
)
671 if ((*function
) (node
->data
, cdata
)) {
675 return findInTree(tree
, node
->right
, function
, cdata
);
678 int WMFindInBag(WMBag
* self
, WMMatchDataProc
* match
, void *cdata
)
680 return findInTree(self
, self
->root
, match
, cdata
);
683 void *WMBagFirst(WMBag
* self
, WMBagIterator
* ptr
)
687 node
= treeMinimum(self
->root
, self
->nil
);
689 if (node
== self
->nil
) {
698 void *WMBagLast(WMBag
* self
, WMBagIterator
* ptr
)
703 node
= treeMaximum(self
->root
, self
->nil
);
705 if (node
== self
->nil
) {
714 void *WMBagNext(WMBag
* self
, WMBagIterator
* ptr
)
721 node
= treeSuccessor(*ptr
, self
->nil
);
723 if (node
== self
->nil
) {
732 void *WMBagPrevious(WMBag
* self
, WMBagIterator
* ptr
)
739 node
= treePredecessor(*ptr
, self
->nil
);
741 if (node
== self
->nil
) {
750 void *WMBagIteratorAtIndex(WMBag
* self
, int index
, WMBagIterator
* ptr
)
754 node
= treeSearch(self
->root
, self
->nil
, index
);
756 if (node
== self
->nil
) {
765 int WMBagIndexForIterator(WMBag
* bag
, WMBagIterator ptr
)
767 return ((W_Node
*) ptr
)->index
;