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 deleteFromBag(WMBag
*bag
, int index
);
38 static void *getFromBag(WMBag
*bag
, int index
);
39 static int countInBag(WMBag
*bag
, void *item
);
40 static int firstInBag(WMBag
*bag
, void *item
);
41 static void *replaceInBag(WMBag
*bag
, int index
, void *item
);
42 static int sortBag(WMBag
*bag
, int (*comparer
)(const void*, const void*));
43 static void emptyBag(WMBag
*bag
);
44 static void freeBag(WMBag
*bag
);
45 static void mapBag(WMBag
*bag
, void (*function
)(void*, void*), void *data
);
46 static int findInBag(WMBag
*bag
, int (*match
)(void*));;
47 static void *first(WMBag
*bag
, WMBagIterator
*ptr
);
48 static void *last(WMBag
*bag
, WMBagIterator
*ptr
);
49 static void *next(WMBag
*bag
, WMBagIterator
*ptr
);
50 static void *previous(WMBag
*bag
, WMBagIterator
*ptr
);
51 static void *iteratorAtIndex(WMBag
*bag
, int index
, WMBagIterator
*ptr
);
52 static int indexForIterator(WMBag
*bag
, WMBagIterator ptr
);
55 static W_BagFunctions bagFunctions
= {
82 #define IS_LEFT(node) (node == node->parent->left)
83 #define IS_RIGHT(node) (node == node->parent->right)
87 static void leftRotate(W_TreeBag
*tree
, W_Node
*node
)
92 node
->right
= node2
->left
;
94 node2
->left
->parent
= node
;
96 node2
->parent
= node
->parent
;
98 if (node
->parent
== tree
->nil
) {
102 node
->parent
->left
= node2
;
104 node
->parent
->right
= node2
;
108 node
->parent
= node2
;
113 static void rightRotate(W_TreeBag
*tree
, W_Node
*node
)
118 node
->left
= node2
->right
;
120 node2
->right
->parent
= node
;
122 node2
->parent
= node
->parent
;
124 if (node
->parent
== tree
->nil
) {
128 node
->parent
->left
= node2
;
130 node
->parent
->right
= node2
;
134 node
->parent
= node2
;
139 static void treeInsert(W_TreeBag
*tree
, W_Node
*node
)
141 W_Node
*y
= tree
->nil
;
142 W_Node
*x
= tree
->root
;
144 while (x
!= tree
->nil
) {
146 if (node
->index
< x
->index
)
154 else if (node
->index
< y
->index
)
161 static void rbTreeInsert(W_TreeBag
*tree
, W_Node
*node
)
165 treeInsert(tree
, node
);
169 while (node
!= tree
->root
&& node
->parent
->color
== 'R') {
170 if (IS_LEFT(node
->parent
)) {
171 y
= node
->parent
->parent
->right
;
173 if (y
->color
== 'R') {
175 node
->parent
->color
= 'B';
177 node
->parent
->parent
->color
= 'R';
178 node
= node
->parent
->parent
;
181 if (IS_RIGHT(node
)) {
183 leftRotate(tree
, node
);
185 node
->parent
->color
= 'B';
186 node
->parent
->parent
->color
= 'R';
187 rightRotate(tree
, node
->parent
->parent
);
190 y
= node
->parent
->parent
->left
;
192 if (y
->color
== 'R') {
194 node
->parent
->color
= 'B';
196 node
->parent
->parent
->color
= 'R';
197 node
= node
->parent
->parent
;
202 rightRotate(tree
, node
);
204 node
->parent
->color
= 'B';
205 node
->parent
->parent
->color
= 'R';
206 leftRotate(tree
, node
->parent
->parent
);
210 tree
->root
->color
= 'B';
215 static void rbDeleteFixup(W_TreeBag
*tree
, W_Node
*node
)
219 while (node
!= tree
->root
&& node
->color
== 'B') {
221 w
= node
->parent
->right
;
222 if (w
->color
== 'R') {
224 node
->parent
->color
= 'R';
225 leftRotate(tree
, node
->parent
);
226 w
= node
->parent
->right
;
228 if (w
->left
->color
== 'B' && w
->right
->color
== 'B') {
232 if (w
->right
->color
== 'B') {
233 w
->left
->color
= 'B';
235 rightRotate(tree
, w
);
236 w
= node
->parent
->right
;
238 w
->color
= node
->parent
->color
;
239 node
->parent
->color
= 'B';
240 w
->right
->color
= 'B';
241 leftRotate(tree
, node
->parent
);
245 w
= node
->parent
->left
;
246 if (w
->color
== 'R') {
248 node
->parent
->color
= 'R';
249 leftRotate(tree
, node
->parent
);
250 w
= node
->parent
->left
;
252 if (w
->left
->color
== 'B' && w
->right
->color
== 'B') {
256 if (w
->left
->color
== 'B') {
257 w
->right
->color
= 'B';
259 rightRotate(tree
, w
);
260 w
= node
->parent
->left
;
262 w
->color
= node
->parent
->color
;
263 node
->parent
->color
= 'B';
264 w
->left
->color
= 'B';
265 leftRotate(tree
, node
->parent
);
274 static W_Node
*treeMinimum(W_Node
*node
, W_Node
*nil
)
276 while (node
->left
!= nil
)
282 static W_Node
*treeMaximum(W_Node
*node
, W_Node
*nil
)
284 while (node
->right
!= nil
)
290 static W_Node
*treeSuccessor(W_Node
*node
, W_Node
*nil
)
294 if (node
->right
!= nil
) {
295 return treeMinimum(node
->right
, nil
);
298 while (y
!= nil
&& node
== y
->right
) {
306 static W_Node
*treePredecessor(W_Node
*node
, W_Node
*nil
)
310 if (node
->left
!= nil
) {
311 return treeMaximum(node
->left
, nil
);
314 while (y
!= nil
&& node
== y
->left
) {
322 static W_Node
*rbTreeDelete(W_TreeBag
*tree
, W_Node
*node
)
324 W_Node
*nil
= tree
->nil
;
327 if (node
->left
== nil
|| node
->right
== nil
) {
330 y
= treeSuccessor(node
, nil
);
333 if (y
->left
!= nil
) {
339 x
->parent
= y
->parent
;
341 if (y
->parent
== nil
) {
347 y
->parent
->right
= x
;
351 node
->index
= y
->index
;
352 node
->data
= y
->data
;
354 if (y
->color
== 'B') {
355 rbDeleteFixup(tree
, x
);
363 static W_Node
*treeSearch(W_Node
*root
, W_Node
*nil
, int index
)
365 if (root
== nil
|| root
->index
== index
) {
369 if (index
< root
->index
) {
370 return treeSearch(root
->left
, nil
, index
);
372 return treeSearch(root
->right
, nil
, index
);
377 static W_Node
*treeFind(W_Node
*root
, W_Node
*nil
, void *data
)
381 if (root
== nil
|| root
->data
== data
)
384 tmp
= treeFind(root
->left
, nil
, data
);
388 tmp
= treeFind(root
->right
, nil
, data
);
398 static char buf
[512];
400 static void printNodes(W_Node
*node
, W_Node
*nil
, int depth
)
406 printNodes(node
->left
, nil
, depth
+1);
408 memset(buf
, ' ', depth
*2);
411 printf("%s/(%2i\n", buf
, node
->index
);
413 printf("%s\\(%2i\n", buf
, node
->index
);
415 printNodes(node
->right
, nil
, depth
+1);
419 void PrintTree(WMBag
*bag
)
421 W_TreeBag
*tree
= (W_TreeBag
*)bag
->data
;
423 printNodes(tree
->root
, tree
->nil
, 0);
430 #define SELF ((W_TreeBag*)self->data)
432 WMBag
*WMCreateTreeBag(void)
434 return WMCreateTreeBagWithDestructor(NULL
);
438 WMBag
*WMCreateTreeBagWithDestructor(void (*destructor
)(void*))
443 bag
= wmalloc(sizeof(WMBag
));
445 bag
->data
= tree
= wmalloc(sizeof(W_TreeBag
));
446 memset(tree
, 0, sizeof(W_TreeBag
));
448 tree
->nil
= wmalloc(sizeof(W_Node
));
449 memset(tree
->nil
, 0, sizeof(W_Node
));
450 tree
->nil
->left
= tree
->nil
->right
= tree
->nil
->parent
= tree
->nil
;
451 tree
->nil
->index
= WBNotFound
;
453 tree
->root
= tree
->nil
;
455 bag
->destructor
= destructor
;
457 bag
->func
= bagFunctions
;
463 static int getItemCount(WMBag
*self
)
469 static int appendBag(WMBag
*self
, WMBag
*bag
)
474 for (data
= first(bag
, &ptr
); data
!= NULL
; data
= next(bag
, &ptr
)) {
475 if (!putInBag(self
, data
))
483 static int putInBag(WMBag
*self
, void *item
)
487 ptr
= wmalloc(sizeof(W_Node
));
490 ptr
->index
= SELF
->count
;
491 ptr
->left
= SELF
->nil
;
492 ptr
->right
= SELF
->nil
;
493 ptr
->parent
= SELF
->nil
;
495 rbTreeInsert(SELF
, ptr
);
503 static int insertInBag(WMBag
*self
, int index
, void *item
)
507 ptr
= wmalloc(sizeof(W_Node
));
511 ptr
->left
= SELF
->nil
;
512 ptr
->right
= SELF
->nil
;
513 ptr
->parent
= SELF
->nil
;
515 rbTreeInsert(SELF
, ptr
);
517 while ((ptr
= treeSuccessor(ptr
, SELF
->nil
))) {
529 static int removeFromBag(WMBag
*self
, void *item
)
531 W_Node
*ptr
= treeFind(SELF
->root
, SELF
->nil
, item
);
533 if (ptr
!= SELF
->nil
) {
537 ptr
= rbTreeDelete(SELF
, ptr
);
547 static int deleteFromBag(WMBag
*self
, int index
)
549 W_Node
*ptr
= treeSearch(SELF
->root
, SELF
->nil
, index
);
551 if (ptr
!= SELF
->nil
) {
555 ptr
= rbTreeDelete(SELF
, ptr
);
565 static void *getFromBag(WMBag
*self
, int index
)
570 assert(SELF
->root
!= SELF
->nil
);
572 node
= treeSearch(SELF
->root
, SELF
->nil
, index
);
573 if (node
!= SELF
->nil
)
581 static int firstInBag(WMBag
*self
, void *item
)
585 node
= treeFind(SELF
->root
, SELF
->nil
, item
);
586 if (node
!= SELF
->nil
)
594 static int treeCount(W_Node
*root
, W_Node
*nil
, void *item
)
601 if (root
->data
== item
)
604 if (root
->left
!= nil
)
605 count
+= treeCount(root
->left
, nil
, item
);
607 if (root
->right
!= nil
)
608 count
+= treeCount(root
->right
, nil
, item
);
615 static int countInBag(WMBag
*self
, void *item
)
617 return treeCount(SELF
->root
, SELF
->nil
, item
);
621 static void *replaceInBag(WMBag
*self
, int index
, void *item
)
623 W_Node
*ptr
= treeSearch(SELF
->root
, SELF
->nil
, index
);
629 ptr
= rbTreeDelete(SELF
, ptr
);
631 } else if (ptr
!= SELF
->nil
) {
635 insertInBag(self
, index
, item
);
643 static int sortBag(WMBag
*self
, int (*comparer
)(const void*, const void*))
645 assert(0&&"not implemented");
653 static void deleteTree(WMBag
*self
, W_Node
*node
)
655 if (node
== SELF
->nil
)
658 deleteTree(self
, node
->left
);
660 if (self
->destructor
)
661 self
->destructor(node
->data
);
663 deleteTree(self
, node
->right
);
669 static void emptyBag(WMBag
*self
)
671 deleteTree(self
, SELF
->root
);
672 SELF
->root
= SELF
->nil
;
677 static void freeBag(WMBag
*self
)
686 static void mapTree(W_TreeBag
*tree
, W_Node
*node
,
687 void (*function
)(void*, void*), void *data
)
689 if (node
== tree
->nil
)
692 mapTree(tree
, node
->left
, function
, data
);
694 (*function
)(node
->data
, data
);
696 mapTree(tree
, node
->right
, function
, data
);
700 static void mapBag(WMBag
*self
, void (*function
)(void*, void*), void *data
)
702 mapTree(SELF
, SELF
->root
, function
, data
);
707 static int findInTree(W_TreeBag
*tree
, W_Node
*node
, int (*function
)(void*))
711 if (node
== tree
->nil
)
714 index
= findInTree(tree
, node
->left
, function
);
715 if (index
!= WBNotFound
)
718 if ((*function
)(node
->data
)) {
722 return findInTree(tree
, node
->right
, function
);
726 static int findInBag(WMBag
*self
, int (*match
)(void*))
728 return findInTree(SELF
, SELF
->root
, match
);
734 static void *first(WMBag
*self
, WMBagIterator
*ptr
)
738 node
= treeMinimum(SELF
->root
, SELF
->nil
);
740 if (node
== SELF
->nil
) {
753 static void *last(WMBag
*self
, WMBagIterator
*ptr
)
758 node
= treeMaximum(SELF
->root
, SELF
->nil
);
760 if (node
== SELF
->nil
) {
773 static void *next(WMBag
*self
, WMBagIterator
*ptr
)
780 node
= treeSuccessor(*ptr
, SELF
->nil
);
782 if (node
== SELF
->nil
) {
795 static void *previous(WMBag
*self
, WMBagIterator
*ptr
)
802 node
= treePredecessor(*ptr
, SELF
->nil
);
805 if (node
== SELF
->nil
) {
818 static void *iteratorAtIndex(WMBag
*self
, int index
, WMBagIterator
*ptr
)
822 node
= treeSearch(SELF
->root
, SELF
->nil
, index
);
824 if (node
== SELF
->nil
) {
834 static int indexForIterator(WMBag
*bag
, WMBagIterator ptr
)
836 return ((W_Node
*)ptr
)->index
;