← Back to branch summary

~profzoom/ubuntu/quantal/wmaker/bug-1079925

« back to all changes in this revision

Viewing changes to WINGs/bagtree.c

  • Committer: Bazaar Package Importer
  • Author(s): Marcelo E. Magallon
  • Date: 2004-11-10 14:05:30 UTC
  • Revision ID: james.westby@ubuntu.com-20041110140530-qpd66b5lm38x7apk
Tags: upstream-0.91.0
Import upstream version 0.91.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
WINGs/bagtree.c
 
1
 
 
2
 
 
3
 
 
4
 
 
5
#include <stdlib.h>
 
6
#include <string.h>
 
7
 
 
8
#include "WUtil.h"
 
9
 
 
10
 
 
11
typedef struct W_Node {
 
12
    struct W_Node *parent;
 
13
    struct W_Node *left;
 
14
    struct W_Node *right;
 
15
    int color;
 
16
 
 
17
    void *data;
 
18
    int index;
 
19
} W_Node;
 
20
 
 
21
 
 
22
typedef struct W_Bag {
 
23
    W_Node *root;
 
24
 
 
25
    W_Node *nil;                       /* sentinel */
 
26
 
 
27
    int count;
 
28
 
 
29
    void (*destructor)(void *item);
 
30
} W_Bag;
 
31
 
 
32
 
 
33
 
 
34
#define IS_LEFT(node) (node == node->parent->left)
 
35
#define IS_RIGHT(node) (node == node->parent->right)
 
36
 
 
37
 
 
38
 
 
39
static void
 
40
leftRotate(W_Bag *tree, W_Node *node)
 
41
{
 
42
    W_Node *node2;
 
43
 
 
44
    node2 = node->right;
 
45
    node->right = node2->left;
 
46
 
 
47
    node2->left->parent = node;
 
48
 
 
49
    node2->parent = node->parent;
 
50
 
 
51
    if (node->parent == tree->nil) {
 
52
        tree->root = node2;
 
53
    } else {
 
54
        if (IS_LEFT(node)) {
 
55
            node->parent->left = node2;
 
56
        } else {
 
57
            node->parent->right = node2;
 
58
        }
 
59
    }
 
60
    node2->left = node;
 
61
    node->parent = node2;
 
62
}
 
63
 
 
64
 
 
65
 
 
66
static void
 
67
rightRotate(W_Bag *tree, W_Node *node)
 
68
{
 
69
    W_Node *node2;
 
70
 
 
71
    node2 = node->left;
 
72
    node->left = node2->right;
 
73
 
 
74
    node2->right->parent = node;
 
75
 
 
76
    node2->parent = node->parent;
 
77
 
 
78
    if (node->parent == tree->nil) {
 
79
        tree->root = node2;
 
80
    } else {
 
81
        if (IS_LEFT(node)) {
 
82
            node->parent->left = node2;
 
83
        } else {
 
84
            node->parent->right = node2;
 
85
        }
 
86
    }
 
87
    node2->right = node;
 
88
    node->parent = node2;
 
89
}
 
90
 
 
91
 
 
92
static void
 
93
treeInsert(W_Bag *tree, W_Node *node)
 
94
{
 
95
    W_Node *y = tree->nil;
 
96
    W_Node *x = tree->root;
 
97
 
 
98
    while (x != tree->nil) {
 
99
        y = x;
 
100
        if (node->index <= x->index)
 
101
            x = x->left;
 
102
        else
 
103
            x = x->right;
 
104
    }
 
105
    node->parent = y;
 
106
    if (y == tree->nil)
 
107
        tree->root = node;
 
108
    else if (node->index <= y->index)
 
109
        y->left = node;
 
110
    else
 
111
        y->right = node;
 
112
}
 
113
 
 
114
 
 
115
static void
 
116
rbTreeInsert(W_Bag *tree, W_Node *node)
 
117
{
 
118
    W_Node *y;
 
119
 
 
120
    treeInsert(tree, node);
 
121
 
 
122
    node->color = 'R';
 
123
 
 
124
    while (node != tree->root && node->parent->color == 'R') {
 
125
        if (IS_LEFT(node->parent)) {
 
126
            y = node->parent->parent->right;
 
127
 
 
128
            if (y->color == 'R') {
 
129
 
 
130
                node->parent->color = 'B';
 
131
                y->color = 'B';
 
132
                node->parent->parent->color = 'R';
 
133
                node = node->parent->parent;
 
134
 
 
135
            } else {
 
136
                if (IS_RIGHT(node)) {
 
137
                    node = node->parent;
 
138
                    leftRotate(tree, node);
 
139
                }
 
140
                node->parent->color = 'B';
 
141
                node->parent->parent->color = 'R';
 
142
                rightRotate(tree, node->parent->parent);
 
143
            }
 
144
        } else {
 
145
            y = node->parent->parent->left;
 
146
 
 
147
            if (y->color == 'R') {
 
148
 
 
149
                node->parent->color = 'B';
 
150
                y->color = 'B';
 
151
                node->parent->parent->color = 'R';
 
152
                node = node->parent->parent;
 
153
 
 
154
            } else {
 
155
                if (IS_LEFT(node)) {
 
156
                    node = node->parent;
 
157
                    rightRotate(tree, node);
 
158
                }
 
159
                node->parent->color = 'B';
 
160
                node->parent->parent->color = 'R';
 
161
                leftRotate(tree, node->parent->parent);
 
162
            }
 
163
        }
 
164
    }
 
165
    tree->root->color = 'B';
 
166
}
 
167
 
 
168
 
 
169
static void
 
170
rbDeleteFixup(W_Bag *tree, W_Node *node)
 
171
{
 
172
    W_Node *w;
 
173
 
 
174
    while (node != tree->root && node->color == 'B') {
 
175
        if (IS_LEFT(node)) {
 
176
            w = node->parent->right;
 
177
            if (w->color == 'R') {
 
178
                w->color = 'B';
 
179
                node->parent->color = 'R';
 
180
                leftRotate(tree, node->parent);
 
181
                w = node->parent->right;
 
182
            }
 
183
            if (w->left->color == 'B' && w->right->color == 'B') {
 
184
                w->color = 'R';
 
185
                node = node->parent;
 
186
            } else {
 
187
                if (w->right->color == 'B') {
 
188
                    w->left->color = 'B';
 
189
                    w->color = 'R';
 
190
                    rightRotate(tree, w);
 
191
                    w = node->parent->right;
 
192
                }
 
193
                w->color = node->parent->color;
 
194
                node->parent->color = 'B';
 
195
                w->right->color = 'B';
 
196
                leftRotate(tree, node->parent);
 
197
                node = tree->root;
 
198
            }
 
199
        } else {
 
200
            w = node->parent->left;
 
201
            if (w->color == 'R') {
 
202
                w->color = 'B';
 
203
                node->parent->color = 'R';
 
204
                rightRotate(tree, node->parent);
 
205
                w = node->parent->left;
 
206
            }
 
207
            if (w->left->color == 'B' && w->right->color == 'B') {
 
208
                w->color = 'R';
 
209
                node = node->parent;
 
210
            } else {
 
211
                if (w->left->color == 'B') {
 
212
                    w->right->color = 'B';
 
213
                    w->color = 'R';
 
214
                    leftRotate(tree, w);
 
215
                    w = node->parent->left;
 
216
                }
 
217
                w->color = node->parent->color;
 
218
                node->parent->color = 'B';
 
219
                w->left->color = 'B';
 
220
                rightRotate(tree, node->parent);
 
221
                node = tree->root;
 
222
            }
 
223
        }
 
224
    }
 
225
    node->color = 'B';
 
226
 
 
227
}
 
228
 
 
229
 
 
230
static W_Node*
 
231
treeMinimum(W_Node *node, W_Node *nil)
 
232
{
 
233
    while (node->left != nil)
 
234
        node = node->left;
 
235
    return node;
 
236
}
 
237
 
 
238
 
 
239
static W_Node*
 
240
treeMaximum(W_Node *node, W_Node *nil)
 
241
{
 
242
    while (node->right != nil)
 
243
        node = node->right;
 
244
    return node;
 
245
}
 
246
 
 
247
 
 
248
static W_Node*
 
249
treeSuccessor(W_Node *node, W_Node *nil)
 
250
{
 
251
    W_Node *y;
 
252
 
 
253
    if (node->right != nil) {
 
254
        return treeMinimum(node->right, nil);
 
255
    }
 
256
    y = node->parent;
 
257
    while (y != nil && node == y->right) {
 
258
        node = y;
 
259
        y = y->parent;
 
260
    }
 
261
    return y;
 
262
}
 
263
 
 
264
 
 
265
static W_Node*
 
266
treePredecessor(W_Node *node, W_Node *nil)
 
267
{
 
268
    W_Node *y;
 
269
 
 
270
    if (node->left != nil) {
 
271
        return treeMaximum(node->left, nil);
 
272
    }
 
273
    y = node->parent;
 
274
    while (y != nil && node == y->left) {
 
275
        node = y;
 
276
        y = y->parent;
 
277
    }
 
278
    return y;
 
279
}
 
280
 
 
281
 
 
282
static W_Node*
 
283
rbTreeDelete(W_Bag *tree, W_Node *node)
 
284
{
 
285
    W_Node *nil = tree->nil;
 
286
    W_Node *x, *y;
 
287
 
 
288
    if (node->left == nil || node->right == nil) {
 
289
        y = node;
 
290
    } else {
 
291
        y = treeSuccessor(node, nil);
 
292
    }
 
293
 
 
294
    if (y->left != nil) {
 
295
        x = y->left;
 
296
    } else {
 
297
        x = y->right;
 
298
    }
 
299
 
 
300
    x->parent = y->parent;
 
301
 
 
302
    if (y->parent == nil) {
 
303
        tree->root = x;
 
304
    } else {
 
305
        if (IS_LEFT(y)) {
 
306
            y->parent->left = x;
 
307
        } else {
 
308
            y->parent->right = x;
 
309
        }
 
310
    }
 
311
    if (y != node) {
 
312
        node->index = y->index;
 
313
        node->data = y->data;
 
314
    }
 
315
    if (y->color == 'B') {
 
316
        rbDeleteFixup(tree, x);
 
317
    }
 
318
 
 
319
    return y;
 
320
}
 
321
 
 
322
 
 
323
static W_Node*
 
324
treeSearch(W_Node *root, W_Node *nil, int index)
 
325
{
 
326
    if (root == nil || root->index == index) {
 
327
        return root;
 
328
    }
 
329
 
 
330
    if (index < root->index) {
 
331
        return treeSearch(root->left, nil, index);
 
332
    } else {
 
333
        return treeSearch(root->right, nil, index);
 
334
    }
 
335
}
 
336
 
 
337
 
 
338
static W_Node*
 
339
treeFind(W_Node *root, W_Node *nil, void *data)
 
340
{
 
341
    W_Node *tmp;
 
342
 
 
343
    if (root == nil || root->data == data)
 
344
        return root;
 
345
 
 
346
    tmp = treeFind(root->left, nil, data);
 
347
    if (tmp != nil)
 
348
        return tmp;
 
349
 
 
350
    tmp = treeFind(root->right, nil, data);
 
351
 
 
352
    return tmp;
 
353
}
 
354
 
 
355
 
 
356
 
 
357
#if 0
 
358
static char buf[512];
 
359
 
 
360
static void
 
361
printNodes(W_Node *node, W_Node *nil, int depth)
 
362
{
 
363
    if (node == nil) {
 
364
        return;
 
365
    }
 
366
 
 
367
    printNodes(node->left, nil, depth+1);
 
368
 
 
369
    memset(buf, ' ', depth*2);
 
370
    buf[depth*2] = 0;
 
371
    if (IS_LEFT(node))
 
372
        printf("%s/(%2i\n", buf, node->index);
 
373
    else
 
374
        printf("%s\\(%2i\n", buf, node->index);
 
375
 
 
376
    printNodes(node->right, nil, depth+1);
 
377
}
 
378
 
 
379
 
 
380
void
 
381
PrintTree(WMBag *bag)
 
382
{
 
383
    W_TreeBag *tree = (W_TreeBag*)bag->data;
 
384
 
 
385
    printNodes(tree->root, tree->nil, 0);
 
386
}
 
387
#endif
 
388
 
 
389
 
 
390
WMBag*
 
391
WMCreateTreeBag(void)
 
392
{
 
393
    return WMCreateTreeBagWithDestructor(NULL);
 
394
}
 
395
 
 
396
 
 
397
WMBag*
 
398
WMCreateTreeBagWithDestructor(WMFreeDataProc *destructor)
 
399
{
 
400
    WMBag *bag;
 
401
 
 
402
    bag = wmalloc(sizeof(WMBag));
 
403
 
 
404
    memset(bag, 0, sizeof(WMBag));
 
405
 
 
406
    bag->nil = wmalloc(sizeof(W_Node));
 
407
    memset(bag->nil, 0, sizeof(W_Node));
 
408
    bag->nil->left = bag->nil->right = bag->nil->parent = bag->nil;
 
409
    bag->nil->index = WBNotFound;
 
410
 
 
411
    bag->root = bag->nil;
 
412
 
 
413
    bag->destructor = destructor;
 
414
 
 
415
    return bag;
 
416
}
 
417
 
 
418
 
 
419
int
 
420
WMGetBagItemCount(WMBag *self)
 
421
{
 
422
    return self->count;
 
423
}
 
424
 
 
425
 
 
426
void
 
427
WMAppendBag(WMBag *self, WMBag *bag)
 
428
{
 
429
    WMBagIterator ptr;
 
430
    void *data;
 
431
 
 
432
    for (data = WMBagFirst(bag, &ptr); data != NULL; data = WMBagNext(bag, &ptr)) {
 
433
        WMPutInBag(self, data);
 
434
    }
 
435
}
 
436
 
 
437
 
 
438
void
 
439
WMPutInBag(WMBag *self, void *item)
 
440
{
 
441
    W_Node *ptr;
 
442
 
 
443
    ptr = wmalloc(sizeof(W_Node));
 
444
 
 
445
    ptr->data = item;
 
446
    ptr->index = self->count;
 
447
    ptr->left = self->nil;
 
448
    ptr->right = self->nil;
 
449
    ptr->parent = self->nil;
 
450
 
 
451
    rbTreeInsert(self, ptr);
 
452
 
 
453
    self->count++;
 
454
}
 
455
 
 
456
 
 
457
void
 
458
WMInsertInBag(WMBag *self, int index, void *item)
 
459
{
 
460
    W_Node *ptr;
 
461
 
 
462
    ptr = wmalloc(sizeof(W_Node));
 
463
 
 
464
    ptr->data = item;
 
465
    ptr->index = index;
 
466
    ptr->left = self->nil;
 
467
    ptr->right = self->nil;
 
468
    ptr->parent = self->nil;
 
469
 
 
470
    rbTreeInsert(self, ptr);
 
471
 
 
472
    while ((ptr = treeSuccessor(ptr, self->nil)) != self->nil) {
 
473
        ptr->index++;
 
474
    }
 
475
 
 
476
 
 
477
    self->count++;
 
478
}
 
479
 
 
480
 
 
481
int
 
482
WMRemoveFromBag(WMBag *self, void *item)
 
483
{
 
484
    W_Node *ptr = treeFind(self->root, self->nil, item);
 
485
 
 
486
    if (ptr != self->nil) {
 
487
        W_Node *tmp;
 
488
 
 
489
        self->count--;
 
490
 
 
491
        tmp = treeSuccessor(ptr, self->nil);
 
492
        while (tmp != self->nil) {
 
493
            tmp->index--;
 
494
            tmp = treeSuccessor(tmp, self->nil);
 
495
        }
 
496
 
 
497
        ptr = rbTreeDelete(self, ptr);
 
498
        if (self->destructor)
 
499
            self->destructor(ptr->data);
 
500
        wfree(ptr);
 
501
 
 
502
        return 1;
 
503
    } else {
 
504
        return 0;
 
505
    }
 
506
}
 
507
 
 
508
 
 
509
int
 
510
WMEraseFromBag(WMBag *self, int index)
 
511
{
 
512
    W_Node *ptr = treeSearch(self->root, self->nil, index);
 
513
 
 
514
    if (ptr != self->nil) {
 
515
 
 
516
        self->count--;
 
517
 
 
518
        ptr = rbTreeDelete(self, ptr);
 
519
        if (self->destructor)
 
520
            self->destructor(ptr->data);
 
521
        wfree(ptr);
 
522
 
 
523
        wassertrv(self->count == 0||self->root->index >= 0, 1);
 
524
 
 
525
        return 1;
 
526
    } else {
 
527
        return 0;
 
528
    }
 
529
}
 
530
 
 
531
 
 
532
int
 
533
WMDeleteFromBag(WMBag *self, int index)
 
534
{
 
535
    W_Node *ptr = treeSearch(self->root, self->nil, index);
 
536
 
 
537
    if (ptr != self->nil) {
 
538
        W_Node *tmp;
 
539
 
 
540
        self->count--;
 
541
 
 
542
        tmp = treeSuccessor(ptr, self->nil);
 
543
        while (tmp != self->nil) {
 
544
            tmp->index--;
 
545
            tmp = treeSuccessor(tmp, self->nil);
 
546
        }
 
547
 
 
548
        ptr = rbTreeDelete(self, ptr);
 
549
        if (self->destructor)
 
550
            self->destructor(ptr->data);
 
551
        wfree(ptr);
 
552
 
 
553
        wassertrv(self->count == 0||self->root->index >= 0, 1);
 
554
 
 
555
        return 1;
 
556
    } else {
 
557
        return 0;
 
558
    }
 
559
}
 
560
 
 
561
 
 
562
void*
 
563
WMGetFromBag(WMBag *self, int index)
 
564
{
 
565
    W_Node *node;
 
566
 
 
567
    node = treeSearch(self->root, self->nil, index);
 
568
    if (node != self->nil)
 
569
        return node->data;
 
570
    else
 
571
        return NULL;
 
572
}
 
573
 
 
574
 
 
575
int
 
576
WMGetFirstInBag(WMBag *self, void *item)
 
577
{
 
578
    W_Node *node;
 
579
 
 
580
    node = treeFind(self->root, self->nil, item);
 
581
    if (node != self->nil)
 
582
        return node->index;
 
583
    else
 
584
        return WBNotFound;
 
585
}
 
586
 
 
587
 
 
588
 
 
589
static int
 
590
treeCount(W_Node *root, W_Node *nil, void *item)
 
591
{
 
592
    int count = 0;
 
593
 
 
594
    if (root == nil)
 
595
        return 0;
 
596
 
 
597
    if (root->data == item)
 
598
        count++;
 
599
 
 
600
    if (root->left != nil)
 
601
        count += treeCount(root->left, nil, item);
 
602
 
 
603
    if (root->right != nil)
 
604
        count += treeCount(root->right, nil, item);
 
605
 
 
606
    return count;
 
607
}
 
608
 
 
609
 
 
610
 
 
611
int
 
612
WMCountInBag(WMBag *self, void *item)
 
613
{
 
614
    return treeCount(self->root, self->nil, item);
 
615
}
 
616
 
 
617
 
 
618
void*
 
619
WMReplaceInBag(WMBag *self, int index, void *item)
 
620
{
 
621
    W_Node *ptr = treeSearch(self->root, self->nil, index);
 
622
    void *old = NULL;
 
623
 
 
624
    if (item == NULL) {
 
625
        self->count--;
 
626
        ptr = rbTreeDelete(self, ptr);
 
627
        if (self->destructor)
 
628
            self->destructor(ptr->data);
 
629
        wfree(ptr);
 
630
    } else if (ptr != self->nil) {
 
631
        old = ptr->data;
 
632
        ptr->data = item;
 
633
    } else {
 
634
        W_Node *ptr;
 
635
 
 
636
        ptr = wmalloc(sizeof(W_Node));
 
637
 
 
638
        ptr->data = item;
 
639
        ptr->index = index;
 
640
        ptr->left = self->nil;
 
641
        ptr->right = self->nil;
 
642
        ptr->parent = self->nil;
 
643
 
 
644
        rbTreeInsert(self, ptr);
 
645
 
 
646
        self->count++;
 
647
    }
 
648
 
 
649
    return old;
 
650
}
 
651
 
 
652
 
 
653
void
 
654
WMSortBag(WMBag *self, WMCompareDataProc *comparer)
 
655
{
 
656
    void **items;
 
657
    W_Node *tmp;
 
658
    int i;
 
659
 
 
660
    if (self->count == 0)
 
661
        return;
 
662
 
 
663
    items = wmalloc(sizeof(void*)*self->count);
 
664
    i = 0;
 
665
 
 
666
    tmp = treeMinimum(self->root, self->nil);
 
667
    while (tmp != self->nil) {
 
668
        items[i++] = tmp->data;
 
669
        tmp = treeSuccessor(tmp, self->nil);
 
670
    }
 
671
 
 
672
    qsort(&items[0], self->count, sizeof(void*), comparer);
 
673
 
 
674
    i = 0;
 
675
    tmp = treeMinimum(self->root, self->nil);
 
676
    while (tmp != self->nil) {
 
677
        tmp->index = i;
 
678
        tmp->data = items[i++];
 
679
        tmp = treeSuccessor(tmp, self->nil);
 
680
    }
 
681
 
 
682
    wfree(items);
 
683
}
 
684
 
 
685
 
 
686
static void
 
687
deleteTree(WMBag *self, W_Node *node)
 
688
{
 
689
    if (node == self->nil)
 
690
        return;
 
691
 
 
692
    deleteTree(self, node->left);
 
693
 
 
694
    if (self->destructor)
 
695
        self->destructor(node->data);
 
696
 
 
697
    deleteTree(self, node->right);
 
698
 
 
699
    wfree(node);
 
700
}
 
701
 
 
702
 
 
703
void
 
704
WMEmptyBag(WMBag *self)
 
705
{
 
706
    deleteTree(self, self->root);
 
707
    self->root = self->nil;
 
708
    self->count = 0;
 
709
}
 
710
 
 
711
 
 
712
void
 
713
WMFreeBag(WMBag *self)
 
714
{
 
715
    WMEmptyBag(self);
 
716
    wfree(self->nil);
 
717
    wfree(self);
 
718
}
 
719
 
 
720
 
 
721
static void
 
722
mapTree(W_Bag *tree, W_Node *node, void (*function)(void*, void*), void *data)
 
723
{
 
724
    if (node == tree->nil)
 
725
        return;
 
726
 
 
727
    mapTree(tree, node->left, function, data);
 
728
 
 
729
    (*function)(node->data, data);
 
730
 
 
731
    mapTree(tree, node->right, function, data);
 
732
}
 
733
 
 
734
 
 
735
void
 
736
WMMapBag(WMBag *self, void (*function)(void*, void*), void *data)
 
737
{
 
738
    mapTree(self, self->root, function, data);
 
739
}
 
740
 
 
741
 
 
742
 
 
743
static int
 
744
findInTree(W_Bag *tree, W_Node *node, WMMatchDataProc *function, void *cdata)
 
745
{
 
746
    int index;
 
747
 
 
748
    if (node == tree->nil)
 
749
        return WBNotFound;
 
750
 
 
751
    index = findInTree(tree, node->left, function, cdata);
 
752
    if (index != WBNotFound)
 
753
        return index;
 
754
 
 
755
    if ((*function)(node->data, cdata)) {
 
756
        return node->index;
 
757
    }
 
758
 
 
759
    return findInTree(tree, node->right, function, cdata);
 
760
}
 
761
 
 
762
 
 
763
int
 
764
WMFindInBag(WMBag *self, WMMatchDataProc *match, void *cdata)
 
765
{
 
766
    return findInTree(self, self->root, match, cdata);
 
767
}
 
768
 
 
769
 
 
770
void*
 
771
WMBagFirst(WMBag *self, WMBagIterator *ptr)
 
772
{
 
773
    W_Node *node;
 
774
 
 
775
    node = treeMinimum(self->root, self->nil);
 
776
 
 
777
    if (node == self->nil) {
 
778
        *ptr = NULL;
 
779
        return NULL;
 
780
    } else {
 
781
        *ptr = node;
 
782
        return node->data;
 
783
    }
 
784
}
 
785
 
 
786
 
 
787
void*
 
788
WMBagLast(WMBag *self, WMBagIterator *ptr)
 
789
{
 
790
 
 
791
    W_Node *node;
 
792
 
 
793
    node = treeMaximum(self->root, self->nil);
 
794
 
 
795
    if (node == self->nil) {
 
796
        *ptr = NULL;
 
797
        return NULL;
 
798
    } else {
 
799
        *ptr = node;
 
800
        return node->data;
 
801
    }
 
802
}
 
803
 
 
804
 
 
805
void*
 
806
WMBagNext(WMBag *self, WMBagIterator *ptr)
 
807
{
 
808
    W_Node *node;
 
809
 
 
810
    if (*ptr == NULL)
 
811
        return NULL;
 
812
 
 
813
    node = treeSuccessor(*ptr, self->nil);
 
814
 
 
815
    if (node == self->nil) {
 
816
        *ptr = NULL;
 
817
        return NULL;
 
818
    } else {
 
819
        *ptr = node;
 
820
        return node->data;
 
821
    }
 
822
}
 
823
 
 
824
 
 
825
void*
 
826
WMBagPrevious(WMBag *self, WMBagIterator *ptr)
 
827
{
 
828
    W_Node *node;
 
829
 
 
830
    if (*ptr == NULL)
 
831
        return NULL;
 
832
 
 
833
    node = treePredecessor(*ptr, self->nil);
 
834
 
 
835
    if (node == self->nil) {
 
836
        *ptr = NULL;
 
837
        return NULL;
 
838
    } else {
 
839
        *ptr = node;
 
840
        return node->data;
 
841
    }
 
842
}
 
843
 
 
844
 
 
845
void*
 
846
WMBagIteratorAtIndex(WMBag *self, int index, WMBagIterator *ptr)
 
847
{
 
848
    W_Node *node;
 
849
 
 
850
    node = treeSearch(self->root, self->nil, index);
 
851
 
 
852
    if (node == self->nil) {
 
853
        *ptr = NULL;
 
854
        return NULL;
 
855
    } else {
 
856
        *ptr = node;
 
857
        return node->data;
 
858
    }
 
859
}
 
860
 
 
861
 
 
862
int
 
863
WMBagIndexForIterator(WMBag *bag, WMBagIterator ptr)
 
864
{
 
865
    return ((W_Node*)ptr)->index;
 
866
}
 
867
 
 
868