Change to the linux kernel coding style
[wmaker-crm.git] / WINGs / bagtree.c
Commit [+]AuthorDateLineData
6672180d kojima2000-03-28 02:30:13 +00001
6672180d kojima2000-03-28 02:30:13 +00002#include <stdlib.h>
3#include <string.h>
4
5#include "WUtil.h"
6
6672180d kojima2000-03-28 02:30:13 +00007typedef struct W_Node {
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +02008 struct W_Node *parent;
9 struct W_Node *left;
10 struct W_Node *right;
11 int color;
595d2b06 dan2000-09-15 04:57:31 +000012
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +020013 void *data;
14 int index;
6672180d kojima2000-03-28 02:30:13 +000015} W_Node;
16
595d2b06 dan2000-09-15 04:57:31 +000017typedef struct W_Bag {
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020018 W_Node *root;
595d2b06 dan2000-09-15 04:57:31 +000019
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020020 W_Node *nil; /* sentinel */
595d2b06 dan2000-09-15 04:57:31 +000021
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020022 int count;
6672180d kojima2000-03-28 02:30:13 +000023
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020024 void (*destructor) (void *item);
595d2b06 dan2000-09-15 04:57:31 +000025} W_Bag;
6672180d kojima2000-03-28 02:30:13 +000026
6672180d kojima2000-03-28 02:30:13 +000027#define IS_LEFT(node) (node == node->parent->left)
28#define IS_RIGHT(node) (node == node->parent->right)
29
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020030static void leftRotate(W_Bag * tree, W_Node * node)
6672180d kojima2000-03-28 02:30:13 +000031{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020032 W_Node *node2;
595d2b06 dan2000-09-15 04:57:31 +000033
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +020034 node2 = node->right;
35 node->right = node2->left;
6672180d kojima2000-03-28 02:30:13 +000036
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020037 node2->left->parent = node;
6672180d kojima2000-03-28 02:30:13 +000038
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020039 node2->parent = node->parent;
6672180d kojima2000-03-28 02:30:13 +000040
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +020041 if (node->parent == tree->nil) {
42 tree->root = node2;
43 } else {
44 if (IS_LEFT(node)) {
45 node->parent->left = node2;
46 } else {
47 node->parent->right = node2;
48 }
49 }
50 node2->left = node;
51 node->parent = node2;
6672180d kojima2000-03-28 02:30:13 +000052}
53
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020054static void rightRotate(W_Bag * tree, W_Node * node)
6672180d kojima2000-03-28 02:30:13 +000055{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020056 W_Node *node2;
595d2b06 dan2000-09-15 04:57:31 +000057
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +020058 node2 = node->left;
59 node->left = node2->right;
595d2b06 dan2000-09-15 04:57:31 +000060
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +020061 node2->right->parent = node;
595d2b06 dan2000-09-15 04:57:31 +000062
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +020063 node2->parent = node->parent;
64
65 if (node->parent == tree->nil) {
66 tree->root = node2;
67 } else {
68 if (IS_LEFT(node)) {
69 node->parent->left = node2;
70 } else {
71 node->parent->right = node2;
72 }
73 }
74 node2->right = node;
75 node->parent = node2;
76}
77
78static void treeInsert(W_Bag * tree, W_Node * node)
79{
80 W_Node *y = tree->nil;
81 W_Node *x = tree->root;
82
83 while (x != tree->nil) {
84 y = x;
85 if (node->index <= x->index)
86 x = x->left;
87 else
88 x = x->right;
89 }
90 node->parent = y;
91 if (y == tree->nil)
92 tree->root = node;
93 else if (node->index <= y->index)
94 y->left = node;
95 else
96 y->right = node;
97}
98
99static void rbTreeInsert(W_Bag * tree, W_Node * node)
100{
101 W_Node *y;
102
103 treeInsert(tree, node);
104
105 node->color = 'R';
106
107 while (node != tree->root && node->parent->color == 'R') {
108 if (IS_LEFT(node->parent)) {
109 y = node->parent->parent->right;
110
111 if (y->color == 'R') {
112
113 node->parent->color = 'B';
114 y->color = 'B';
115 node->parent->parent->color = 'R';
116 node = node->parent->parent;
117
118 } else {
119 if (IS_RIGHT(node)) {
120 node = node->parent;
121 leftRotate(tree, node);
122 }
123 node->parent->color = 'B';
124 node->parent->parent->color = 'R';
125 rightRotate(tree, node->parent->parent);
126 }
127 } else {
128 y = node->parent->parent->left;
129
130 if (y->color == 'R') {
131
132 node->parent->color = 'B';
133 y->color = 'B';
134 node->parent->parent->color = 'R';
135 node = node->parent->parent;
136
137 } else {
138 if (IS_LEFT(node)) {
139 node = node->parent;
140 rightRotate(tree, node);
141 }
142 node->parent->color = 'B';
143 node->parent->parent->color = 'R';
144 leftRotate(tree, node->parent->parent);
145 }
146 }
147 }
148 tree->root->color = 'B';
149}
150
151static void rbDeleteFixup(W_Bag * tree, W_Node * node)
152{
153 W_Node *w;
154
155 while (node != tree->root && node->color == 'B') {
156 if (IS_LEFT(node)) {
157 w = node->parent->right;
158 if (w->color == 'R') {
159 w->color = 'B';
160 node->parent->color = 'R';
161 leftRotate(tree, node->parent);
162 w = node->parent->right;
163 }
164 if (w->left->color == 'B' && w->right->color == 'B') {
165 w->color = 'R';
166 node = node->parent;
167 } else {
168 if (w->right->color == 'B') {
169 w->left->color = 'B';
170 w->color = 'R';
171 rightRotate(tree, w);
172 w = node->parent->right;
173 }
174 w->color = node->parent->color;
175 node->parent->color = 'B';
176 w->right->color = 'B';
177 leftRotate(tree, node->parent);
178 node = tree->root;
179 }
180 } else {
181 w = node->parent->left;
182 if (w->color == 'R') {
183 w->color = 'B';
184 node->parent->color = 'R';
185 rightRotate(tree, node->parent);
186 w = node->parent->left;
187 }
188 if (w->left->color == 'B' && w->right->color == 'B') {
189 w->color = 'R';
190 node = node->parent;
191 } else {
192 if (w->left->color == 'B') {
193 w->right->color = 'B';
194 w->color = 'R';
195 leftRotate(tree, w);
196 w = node->parent->left;
197 }
198 w->color = node->parent->color;
199 node->parent->color = 'B';
200 w->left->color = 'B';
201 rightRotate(tree, node->parent);
202 node = tree->root;
203 }
204 }
205 }
206 node->color = 'B';
207
208}
209
210static W_Node *treeMinimum(W_Node * node, W_Node * nil)
211{
212 while (node->left != nil)
213 node = node->left;
214 return node;
215}
216
217static W_Node *treeMaximum(W_Node * node, W_Node * nil)
218{
219 while (node->right != nil)
220 node = node->right;
221 return node;
222}
223
224static W_Node *treeSuccessor(W_Node * node, W_Node * nil)
225{
226 W_Node *y;
227
228 if (node->right != nil) {
229 return treeMinimum(node->right, nil);
230 }
231 y = node->parent;
232 while (y != nil && node == y->right) {
233 node = y;
234 y = y->parent;
235 }
236 return y;
237}
238
239static W_Node *treePredecessor(W_Node * node, W_Node * nil)
240{
241 W_Node *y;
242
243 if (node->left != nil) {
244 return treeMaximum(node->left, nil);
245 }
246 y = node->parent;
247 while (y != nil && node == y->left) {
248 node = y;
249 y = y->parent;
250 }
251 return y;
252}
253
254static W_Node *rbTreeDelete(W_Bag * tree, W_Node * node)
255{
256 W_Node *nil = tree->nil;
257 W_Node *x, *y;
258
259 if (node->left == nil || node->right == nil) {
260 y = node;
261 } else {
262 y = treeSuccessor(node, nil);
263 }
264
265 if (y->left != nil) {
266 x = y->left;
267 } else {
268 x = y->right;
269 }
270
271 x->parent = y->parent;
272
273 if (y->parent == nil) {
274 tree->root = x;
275 } else {
276 if (IS_LEFT(y)) {
277 y->parent->left = x;
278 } else {
279 y->parent->right = x;
280 }
281 }
282 if (y != node) {
283 node->index = y->index;
284 node->data = y->data;
285 }
286 if (y->color == 'B') {
287 rbDeleteFixup(tree, x);
288 }
6672180d kojima2000-03-28 02:30:13 +0000289
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200290 return y;
6672180d kojima2000-03-28 02:30:13 +0000291}
292
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200293static W_Node *treeSearch(W_Node * root, W_Node * nil, int index)
6672180d kojima2000-03-28 02:30:13 +0000294{
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200295 if (root == nil || root->index == index) {
296 return root;
297 }
595d2b06 dan2000-09-15 04:57:31 +0000298
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200299 if (index < root->index) {
300 return treeSearch(root->left, nil, index);
301 } else {
302 return treeSearch(root->right, nil, index);
303 }
6672180d kojima2000-03-28 02:30:13 +0000304}
305
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200306static W_Node *treeFind(W_Node * root, W_Node * nil, void *data)
6672180d kojima2000-03-28 02:30:13 +0000307{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200308 W_Node *tmp;
595d2b06 dan2000-09-15 04:57:31 +0000309
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200310 if (root == nil || root->data == data)
311 return root;
595d2b06 dan2000-09-15 04:57:31 +0000312
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200313 tmp = treeFind(root->left, nil, data);
314 if (tmp != nil)
315 return tmp;
595d2b06 dan2000-09-15 04:57:31 +0000316
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200317 tmp = treeFind(root->right, nil, data);
595d2b06 dan2000-09-15 04:57:31 +0000318
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200319 return tmp;
6672180d kojima2000-03-28 02:30:13 +0000320}
321
6672180d kojima2000-03-28 02:30:13 +0000322#if 0
323static char buf[512];
324
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200325static void printNodes(W_Node * node, W_Node * nil, int depth)
6672180d kojima2000-03-28 02:30:13 +0000326{
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200327 if (node == nil) {
328 return;
329 }
595d2b06 dan2000-09-15 04:57:31 +0000330
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200331 printNodes(node->left, nil, depth + 1);
6672180d kojima2000-03-28 02:30:13 +0000332
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200333 memset(buf, ' ', depth * 2);
334 buf[depth * 2] = 0;
335 if (IS_LEFT(node))
336 printf("%s/(%2i\n", buf, node->index);
337 else
338 printf("%s\\(%2i\n", buf, node->index);
6672180d kojima2000-03-28 02:30:13 +0000339
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200340 printNodes(node->right, nil, depth + 1);
6672180d kojima2000-03-28 02:30:13 +0000341}
342
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200343void PrintTree(WMBag * bag)
6672180d kojima2000-03-28 02:30:13 +0000344{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200345 W_TreeBag *tree = (W_TreeBag *) bag->data;
595d2b06 dan2000-09-15 04:57:31 +0000346
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200347 printNodes(tree->root, tree->nil, 0);
6672180d kojima2000-03-28 02:30:13 +0000348}
349#endif
350
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200351WMBag *WMCreateTreeBag(void)
6672180d kojima2000-03-28 02:30:13 +0000352{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200353 return WMCreateTreeBagWithDestructor(NULL);
6672180d kojima2000-03-28 02:30:13 +0000354}
355
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200356WMBag *WMCreateTreeBagWithDestructor(WMFreeDataProc * destructor)
6672180d kojima2000-03-28 02:30:13 +0000357{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200358 WMBag *bag;
595d2b06 dan2000-09-15 04:57:31 +0000359
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200360 bag = wmalloc(sizeof(WMBag));
6672180d kojima2000-03-28 02:30:13 +0000361
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200362 memset(bag, 0, sizeof(WMBag));
595d2b06 dan2000-09-15 04:57:31 +0000363
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200364 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;
6672180d kojima2000-03-28 02:30:13 +0000368
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200369 bag->root = bag->nil;
6672180d kojima2000-03-28 02:30:13 +0000370
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200371 bag->destructor = destructor;
595d2b06 dan2000-09-15 04:57:31 +0000372
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200373 return bag;
6672180d kojima2000-03-28 02:30:13 +0000374}
375
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200376int WMGetBagItemCount(WMBag * self)
6672180d kojima2000-03-28 02:30:13 +0000377{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200378 return self->count;
6672180d kojima2000-03-28 02:30:13 +0000379}
380
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200381void WMAppendBag(WMBag * self, WMBag * bag)
6672180d kojima2000-03-28 02:30:13 +0000382{
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200383 WMBagIterator ptr;
384 void *data;
595d2b06 dan2000-09-15 04:57:31 +0000385
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200386 for (data = WMBagFirst(bag, &ptr); data != NULL; data = WMBagNext(bag, &ptr)) {
387 WMPutInBag(self, data);
388 }
6672180d kojima2000-03-28 02:30:13 +0000389}
390
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200391void WMPutInBag(WMBag * self, void *item)
6672180d kojima2000-03-28 02:30:13 +0000392{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200393 W_Node *ptr;
595d2b06 dan2000-09-15 04:57:31 +0000394
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200395 ptr = wmalloc(sizeof(W_Node));
595d2b06 dan2000-09-15 04:57:31 +0000396
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200397 ptr->data = item;
398 ptr->index = self->count;
399 ptr->left = self->nil;
400 ptr->right = self->nil;
401 ptr->parent = self->nil;
595d2b06 dan2000-09-15 04:57:31 +0000402
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200403 rbTreeInsert(self, ptr);
595d2b06 dan2000-09-15 04:57:31 +0000404
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200405 self->count++;
6672180d kojima2000-03-28 02:30:13 +0000406}
407
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200408void WMInsertInBag(WMBag * self, int index, void *item)
6672180d kojima2000-03-28 02:30:13 +0000409{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200410 W_Node *ptr;
6672180d kojima2000-03-28 02:30:13 +0000411
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200412 ptr = wmalloc(sizeof(W_Node));
595d2b06 dan2000-09-15 04:57:31 +0000413
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200414 ptr->data = item;
415 ptr->index = index;
416 ptr->left = self->nil;
417 ptr->right = self->nil;
418 ptr->parent = self->nil;
595d2b06 dan2000-09-15 04:57:31 +0000419
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200420 rbTreeInsert(self, ptr);
595d2b06 dan2000-09-15 04:57:31 +0000421
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200422 while ((ptr = treeSuccessor(ptr, self->nil)) != self->nil) {
423 ptr->index++;
424 }
595d2b06 dan2000-09-15 04:57:31 +0000425
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200426 self->count++;
6672180d kojima2000-03-28 02:30:13 +0000427}
428
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200429int WMRemoveFromBag(WMBag * self, void *item)
6672180d kojima2000-03-28 02:30:13 +0000430{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200431 W_Node *ptr = treeFind(self->root, self->nil, item);
595d2b06 dan2000-09-15 04:57:31 +0000432
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200433 if (ptr != self->nil) {
434 W_Node *tmp;
595d2b06 dan2000-09-15 04:57:31 +0000435
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200436 self->count--;
595d2b06 dan2000-09-15 04:57:31 +0000437
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200438 tmp = treeSuccessor(ptr, self->nil);
439 while (tmp != self->nil) {
440 tmp->index--;
441 tmp = treeSuccessor(tmp, self->nil);
442 }
9e45e85d kojima2000-03-29 02:17:39 +0000443
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200444 ptr = rbTreeDelete(self, ptr);
445 if (self->destructor)
446 self->destructor(ptr->data);
447 wfree(ptr);
595d2b06 dan2000-09-15 04:57:31 +0000448
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200449 return 1;
450 } else {
451 return 0;
452 }
9e45e85d kojima2000-03-29 02:17:39 +0000453}
454
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200455int WMEraseFromBag(WMBag * self, int index)
9e45e85d kojima2000-03-29 02:17:39 +0000456{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200457 W_Node *ptr = treeSearch(self->root, self->nil, index);
595d2b06 dan2000-09-15 04:57:31 +0000458
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200459 if (ptr != self->nil) {
6672180d kojima2000-03-28 02:30:13 +0000460
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200461 self->count--;
e29fce43 kojima2000-07-10 22:37:39 +0000462
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200463 ptr = rbTreeDelete(self, ptr);
464 if (self->destructor)
465 self->destructor(ptr->data);
466 wfree(ptr);
595d2b06 dan2000-09-15 04:57:31 +0000467
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200468 wassertrv(self->count == 0 || self->root->index >= 0, 1);
595d2b06 dan2000-09-15 04:57:31 +0000469
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200470 return 1;
471 } else {
472 return 0;
473 }
6672180d kojima2000-03-28 02:30:13 +0000474}
475
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200476int WMDeleteFromBag(WMBag * self, int index)
6672180d kojima2000-03-28 02:30:13 +0000477{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200478 W_Node *ptr = treeSearch(self->root, self->nil, index);
595d2b06 dan2000-09-15 04:57:31 +0000479
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200480 if (ptr != self->nil) {
481 W_Node *tmp;
595d2b06 dan2000-09-15 04:57:31 +0000482
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200483 self->count--;
e29fce43 kojima2000-07-10 22:37:39 +0000484
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200485 tmp = treeSuccessor(ptr, self->nil);
486 while (tmp != self->nil) {
487 tmp->index--;
488 tmp = treeSuccessor(tmp, self->nil);
489 }
e29fce43 kojima2000-07-10 22:37:39 +0000490
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200491 ptr = rbTreeDelete(self, ptr);
492 if (self->destructor)
493 self->destructor(ptr->data);
494 wfree(ptr);
6672180d kojima2000-03-28 02:30:13 +0000495
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200496 wassertrv(self->count == 0 || self->root->index >= 0, 1);
595d2b06 dan2000-09-15 04:57:31 +0000497
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200498 return 1;
499 } else {
500 return 0;
501 }
6672180d kojima2000-03-28 02:30:13 +0000502}
503
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200504void *WMGetFromBag(WMBag * self, int index)
595d2b06 dan2000-09-15 04:57:31 +0000505{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200506 W_Node *node;
9e45e85d kojima2000-03-29 02:17:39 +0000507
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200508 node = treeSearch(self->root, self->nil, index);
509 if (node != self->nil)
510 return node->data;
511 else
512 return NULL;
6672180d kojima2000-03-28 02:30:13 +0000513}
514
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200515int WMGetFirstInBag(WMBag * self, void *item)
6672180d kojima2000-03-28 02:30:13 +0000516{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200517 W_Node *node;
595d2b06 dan2000-09-15 04:57:31 +0000518
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200519 node = treeFind(self->root, self->nil, item);
520 if (node != self->nil)
521 return node->index;
522 else
523 return WBNotFound;
6672180d kojima2000-03-28 02:30:13 +0000524}
525
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200526static int treeCount(W_Node * root, W_Node * nil, void *item)
6672180d kojima2000-03-28 02:30:13 +0000527{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200528 int count = 0;
595d2b06 dan2000-09-15 04:57:31 +0000529
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200530 if (root == nil)
531 return 0;
595d2b06 dan2000-09-15 04:57:31 +0000532
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200533 if (root->data == item)
534 count++;
6672180d kojima2000-03-28 02:30:13 +0000535
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200536 if (root->left != nil)
537 count += treeCount(root->left, nil, item);
595d2b06 dan2000-09-15 04:57:31 +0000538
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200539 if (root->right != nil)
540 count += treeCount(root->right, nil, item);
6672180d kojima2000-03-28 02:30:13 +0000541
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200542 return count;
6672180d kojima2000-03-28 02:30:13 +0000543}
544
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200545int WMCountInBag(WMBag * self, void *item)
595d2b06 dan2000-09-15 04:57:31 +0000546{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200547 return treeCount(self->root, self->nil, item);
6672180d kojima2000-03-28 02:30:13 +0000548}
549
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200550void *WMReplaceInBag(WMBag * self, int index, void *item)
6672180d kojima2000-03-28 02:30:13 +0000551{
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200552 W_Node *ptr = treeSearch(self->root, self->nil, index);
553 void *old = NULL;
6672180d kojima2000-03-28 02:30:13 +0000554
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200555 if (item == NULL) {
556 self->count--;
557 ptr = rbTreeDelete(self, ptr);
558 if (self->destructor)
559 self->destructor(ptr->data);
560 wfree(ptr);
561 } else if (ptr != self->nil) {
562 old = ptr->data;
563 ptr->data = item;
564 } else {
565 W_Node *ptr;
9e45e85d kojima2000-03-29 02:17:39 +0000566
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200567 ptr = wmalloc(sizeof(W_Node));
9e45e85d kojima2000-03-29 02:17:39 +0000568
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200569 ptr->data = item;
570 ptr->index = index;
571 ptr->left = self->nil;
572 ptr->right = self->nil;
573 ptr->parent = self->nil;
9e45e85d kojima2000-03-29 02:17:39 +0000574
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200575 rbTreeInsert(self, ptr);
9e45e85d kojima2000-03-29 02:17:39 +0000576
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200577 self->count++;
578 }
595d2b06 dan2000-09-15 04:57:31 +0000579
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200580 return old;
6672180d kojima2000-03-28 02:30:13 +0000581}
582
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200583void WMSortBag(WMBag * self, WMCompareDataProc * comparer)
6672180d kojima2000-03-28 02:30:13 +0000584{
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200585 void **items;
586 W_Node *tmp;
587 int i;
7bb187a3 kojima2000-03-29 19:01:31 +0000588
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200589 if (self->count == 0)
590 return;
7bb187a3 kojima2000-03-29 19:01:31 +0000591
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200592 items = wmalloc(sizeof(void *) * self->count);
593 i = 0;
595d2b06 dan2000-09-15 04:57:31 +0000594
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200595 tmp = treeMinimum(self->root, self->nil);
596 while (tmp != self->nil) {
597 items[i++] = tmp->data;
598 tmp = treeSuccessor(tmp, self->nil);
599 }
7bb187a3 kojima2000-03-29 19:01:31 +0000600
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200601 qsort(&items[0], self->count, sizeof(void *), comparer);
595d2b06 dan2000-09-15 04:57:31 +0000602
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200603 i = 0;
604 tmp = treeMinimum(self->root, self->nil);
605 while (tmp != self->nil) {
606 tmp->index = i;
607 tmp->data = items[i++];
608 tmp = treeSuccessor(tmp, self->nil);
609 }
595d2b06 dan2000-09-15 04:57:31 +0000610
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200611 wfree(items);
6672180d kojima2000-03-28 02:30:13 +0000612}
613
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200614static void deleteTree(WMBag * self, W_Node * node)
6672180d kojima2000-03-28 02:30:13 +0000615{
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200616 if (node == self->nil)
617 return;
595d2b06 dan2000-09-15 04:57:31 +0000618
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200619 deleteTree(self, node->left);
595d2b06 dan2000-09-15 04:57:31 +0000620
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200621 if (self->destructor)
622 self->destructor(node->data);
595d2b06 dan2000-09-15 04:57:31 +0000623
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200624 deleteTree(self, node->right);
595d2b06 dan2000-09-15 04:57:31 +0000625
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200626 wfree(node);
6672180d kojima2000-03-28 02:30:13 +0000627}
628
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200629void WMEmptyBag(WMBag * self)
6672180d kojima2000-03-28 02:30:13 +0000630{
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200631 deleteTree(self, self->root);
632 self->root = self->nil;
633 self->count = 0;
6672180d kojima2000-03-28 02:30:13 +0000634}
635
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200636void WMFreeBag(WMBag * self)
6672180d kojima2000-03-28 02:30:13 +0000637{
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200638 WMEmptyBag(self);
639 wfree(self->nil);
640 wfree(self);
6672180d kojima2000-03-28 02:30:13 +0000641}
642
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200643static void mapTree(W_Bag * tree, W_Node * node, void (*function) (void *, void *), void *data)
6672180d kojima2000-03-28 02:30:13 +0000644{
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200645 if (node == tree->nil)
646 return;
595d2b06 dan2000-09-15 04:57:31 +0000647
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200648 mapTree(tree, node->left, function, data);
6672180d kojima2000-03-28 02:30:13 +0000649
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200650 (*function) (node->data, data);
6672180d kojima2000-03-28 02:30:13 +0000651
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200652 mapTree(tree, node->right, function, data);
6672180d kojima2000-03-28 02:30:13 +0000653}
654
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200655void WMMapBag(WMBag * self, void (*function) (void *, void *), void *data)
6672180d kojima2000-03-28 02:30:13 +0000656{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200657 mapTree(self, self->root, function, data);
6672180d kojima2000-03-28 02:30:13 +0000658}
659
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200660static int findInTree(W_Bag * tree, W_Node * node, WMMatchDataProc * function, void *cdata)
6672180d kojima2000-03-28 02:30:13 +0000661{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200662 int index;
595d2b06 dan2000-09-15 04:57:31 +0000663
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200664 if (node == tree->nil)
665 return WBNotFound;
595d2b06 dan2000-09-15 04:57:31 +0000666
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200667 index = findInTree(tree, node->left, function, cdata);
668 if (index != WBNotFound)
669 return index;
6672180d kojima2000-03-28 02:30:13 +0000670
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200671 if ((*function) (node->data, cdata)) {
672 return node->index;
673 }
6672180d kojima2000-03-28 02:30:13 +0000674
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200675 return findInTree(tree, node->right, function, cdata);
6672180d kojima2000-03-28 02:30:13 +0000676}
677
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200678int WMFindInBag(WMBag * self, WMMatchDataProc * match, void *cdata)
6672180d kojima2000-03-28 02:30:13 +0000679{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200680 return findInTree(self, self->root, match, cdata);
6672180d kojima2000-03-28 02:30:13 +0000681}
682
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200683void *WMBagFirst(WMBag * self, WMBagIterator * ptr)
6672180d kojima2000-03-28 02:30:13 +0000684{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200685 W_Node *node;
595d2b06 dan2000-09-15 04:57:31 +0000686
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200687 node = treeMinimum(self->root, self->nil);
595d2b06 dan2000-09-15 04:57:31 +0000688
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200689 if (node == self->nil) {
690 *ptr = NULL;
691 return NULL;
692 } else {
693 *ptr = node;
694 return node->data;
695 }
6672180d kojima2000-03-28 02:30:13 +0000696}
697
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200698void *WMBagLast(WMBag * self, WMBagIterator * ptr)
6672180d kojima2000-03-28 02:30:13 +0000699{
700
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200701 W_Node *node;
595d2b06 dan2000-09-15 04:57:31 +0000702
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200703 node = treeMaximum(self->root, self->nil);
595d2b06 dan2000-09-15 04:57:31 +0000704
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200705 if (node == self->nil) {
706 *ptr = NULL;
707 return NULL;
708 } else {
709 *ptr = node;
710 return node->data;
711 }
6672180d kojima2000-03-28 02:30:13 +0000712}
713
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200714void *WMBagNext(WMBag * self, WMBagIterator * ptr)
6672180d kojima2000-03-28 02:30:13 +0000715{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200716 W_Node *node;
595d2b06 dan2000-09-15 04:57:31 +0000717
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200718 if (*ptr == NULL)
719 return NULL;
595d2b06 dan2000-09-15 04:57:31 +0000720
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200721 node = treeSuccessor(*ptr, self->nil);
595d2b06 dan2000-09-15 04:57:31 +0000722
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200723 if (node == self->nil) {
724 *ptr = NULL;
725 return NULL;
726 } else {
727 *ptr = node;
728 return node->data;
729 }
6672180d kojima2000-03-28 02:30:13 +0000730}
731
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200732void *WMBagPrevious(WMBag * self, WMBagIterator * ptr)
6672180d kojima2000-03-28 02:30:13 +0000733{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200734 W_Node *node;
595d2b06 dan2000-09-15 04:57:31 +0000735
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200736 if (*ptr == NULL)
737 return NULL;
595d2b06 dan2000-09-15 04:57:31 +0000738
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200739 node = treePredecessor(*ptr, self->nil);
595d2b06 dan2000-09-15 04:57:31 +0000740
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200741 if (node == self->nil) {
742 *ptr = NULL;
743 return NULL;
744 } else {
745 *ptr = node;
746 return node->data;
747 }
6672180d kojima2000-03-28 02:30:13 +0000748}
749
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200750void *WMBagIteratorAtIndex(WMBag * self, int index, WMBagIterator * ptr)
6672180d kojima2000-03-28 02:30:13 +0000751{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200752 W_Node *node;
595d2b06 dan2000-09-15 04:57:31 +0000753
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200754 node = treeSearch(self->root, self->nil, index);
595d2b06 dan2000-09-15 04:57:31 +0000755
688a56e8
CM
Carlos R. Mafra2009-08-20 00:59:40 +0200756 if (node == self->nil) {
757 *ptr = NULL;
758 return NULL;
759 } else {
760 *ptr = node;
761 return node->data;
762 }
6672180d kojima2000-03-28 02:30:13 +0000763}
764
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200765int WMBagIndexForIterator(WMBag * bag, WMBagIterator ptr)
6672180d kojima2000-03-28 02:30:13 +0000766{
688a56e8 Carlos R. Mafra2009-08-20 00:59:40 +0200767 return ((W_Node *) ptr)->index;
6672180d kojima2000-03-28 02:30:13 +0000768}