← Back to branch summary

~ubuntu-branches/ubuntu/vivid/grass/vivid-proposed

« back to all changes in this revision

Viewing changes to imagery/i.segment/regtree.c

  • Committer: Package Import Robot
  • Author(s): Bas Couwenberg
  • Date: 2015-02-20 23:12:08 UTC
  • mfrom: (8.2.6 experimental)
  • Revision ID: package-import@ubuntu.com-20150220231208-1u6qvqm84v430b10
Tags: 7.0.0-1~exp1
* New upstream release.
* Update python-ctypes-ternary.patch to use if/else instead of and/or.
* Drop check4dev patch, rely on upstream check.
* Add build dependency on libpq-dev to grass-dev for libpq-fe.h.
* Drop patches applied upstream, refresh remaining patches.
* Update symlinks for images switched from jpg to png.

Show diffs side-by-side

added added

removed removed

Lines of Context:
imagery/i.segment/regtree.c
 
1
/*!
 
2
 * \file rbtree.c
 
3
 *
 
4
 * \brief binary search tree 
 
5
 *
 
6
 * Generic balanced binary search tree (Red Black Tree) implementation
 
7
 *
 
8
 * (C) 2009 by the GRASS Development Team
 
9
 *
 
10
 * This program is free software under the GNU General Public License
 
11
 * (>=v2).  Read the file COPYING that comes with GRASS for details.
 
12
 *
 
13
 * \author Original author Julienne Walker 2003, 2008
 
14
 *         GRASS implementation Markus Metz, 2009
 
15
 */
 
16
 
 
17
/* balanced binary search tree implementation
 
18
 * 
 
19
 * this one is a Red Black Tree, no parent pointers, no threads
 
20
 * The core code comes from Julienne Walker's tutorials on binary search trees
 
21
 * original license: public domain
 
22
 * http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx
 
23
 * some ideas come from libavl (GPL >= 2)
 
24
 *
 
25
 * Red Black Trees are used to maintain a data structure with
 
26
 * search, insertion and deletion in O(log N) time
 
27
 */
 
28
 
 
29
#include <assert.h>
 
30
#include <stdlib.h>
 
31
#include <string.h>
 
32
#include <grass/gis.h>
 
33
#include <grass/glocale.h>
 
34
#include "regtree.h"
 
35
 
 
36
/* internal functions */
 
37
static struct RG_NODE *rgtree_single(struct RG_NODE *, int);
 
38
static struct RG_NODE *rgtree_double(struct RG_NODE *, int);
 
39
static struct reg_stats *rgtree_first(struct RG_TRAV *);
 
40
static struct reg_stats *rgtree_next(struct RG_TRAV *);
 
41
static struct RG_NODE *rgtree_make_node(size_t, struct reg_stats *);
 
42
static int is_red(struct RG_NODE *);
 
43
 
 
44
 
 
45
int compare_regstat(struct reg_stats *a, struct reg_stats *b)
 
46
{
 
47
    return (a->id - b->id);
 
48
}
 
49
 
 
50
 
 
51
/* create new tree and initialize
 
52
 * returns pointer to new tree, NULL for memory allocation error
 
53
 */
 
54
struct RG_TREE *rgtree_create(int nbands, size_t rb_datasize)
 
55
{
 
56
    struct RG_TREE *tree = (struct RG_TREE *)malloc(sizeof(struct RG_TREE));
 
57
 
 
58
    if (tree == NULL) {
 
59
        G_warning("RB tree: Out of memory!");
 
60
        return NULL;
 
61
    }
 
62
 
 
63
    tree->datasize = rb_datasize;
 
64
    tree->cmp = compare_regstat;
 
65
    tree->count = 0;
 
66
    tree->nbands = nbands;
 
67
    tree->root = NULL;
 
68
 
 
69
    return tree;
 
70
}
 
71
 
 
72
/* add an item to a tree
 
73
 * non-recursive top-down insertion
 
74
 * the algorithm does not allow duplicates and also does not warn about a duplicate
 
75
 * returns 1 on success, 0 on failure
 
76
 */
 
77
int rgtree_insert(struct RG_TREE *tree, struct reg_stats *data)
 
78
{
 
79
    assert(tree && data);
 
80
 
 
81
    if (tree->root == NULL) {
 
82
        /* create a new root node for tree */
 
83
        tree->root = rgtree_make_node(tree->datasize, data);
 
84
        if (tree->root == NULL)
 
85
            return 0;
 
86
    }
 
87
    else {
 
88
        struct RG_NODE head = { 0, {0, 0}, {0, 0, 0, 0} };      /* False tree root */
 
89
        struct RG_NODE *g, *t;  /* Grandparent & parent */
 
90
        struct RG_NODE *p, *q;  /* Iterator & parent */
 
91
        int dir = 0, last = 0;
 
92
 
 
93
        /* Set up helpers */
 
94
        t = &head;
 
95
        g = p = NULL;
 
96
        q = t->link[1] = tree->root;
 
97
 
 
98
        /* Search down the tree */
 
99
        for (;;) {
 
100
            if (q == NULL) {
 
101
                /* Insert new node at the bottom */
 
102
                p->link[dir] = q = rgtree_make_node(tree->datasize, data);
 
103
                if (q == NULL)
 
104
                    return 0;
 
105
            }
 
106
            else if (is_red(q->link[0]) && is_red(q->link[1])) {
 
107
                /* Color flip */
 
108
                q->red = 1;
 
109
                q->link[0]->red = 0;
 
110
                q->link[1]->red = 0;
 
111
            }
 
112
 
 
113
            /* Fix red violation */
 
114
            if (is_red(q) && is_red(p)) {
 
115
                int dir2 = t->link[1] == g;
 
116
 
 
117
                if (q == p->link[last])
 
118
                    t->link[dir2] = rgtree_single(g, !last);
 
119
                else
 
120
                    t->link[dir2] = rgtree_double(g, !last);
 
121
            }
 
122
 
 
123
            last = dir;
 
124
            dir = tree->cmp(&(q->data), data);
 
125
 
 
126
            /* Stop if found. This check also disallows duplicates in the tree */
 
127
            if (dir == 0)
 
128
                break;
 
129
 
 
130
            dir = dir < 0;
 
131
 
 
132
            /* Move the helpers down */
 
133
            if (g != NULL)
 
134
                t = g;
 
135
 
 
136
            g = p, p = q;
 
137
            q = q->link[dir];
 
138
        }
 
139
 
 
140
        /* Update root */
 
141
        tree->root = head.link[1];
 
142
    }
 
143
 
 
144
    /* Make root black */
 
145
    tree->root->red = 0;
 
146
 
 
147
    tree->count++;
 
148
 
 
149
    return 1;
 
150
}
 
151
 
 
152
/* remove an item from a tree that matches given data
 
153
 * non-recursive top-down removal
 
154
 * returns 1 on successful removal
 
155
 * returns 0 if data item was not found
 
156
 */
 
157
int rgtree_remove(struct RG_TREE *tree, struct reg_stats *data)
 
158
{
 
159
    struct RG_NODE head = { 0, {0, 0}, {0, 0, 0, 0} };  /* False tree root */
 
160
    struct RG_NODE *q, *p, *g;  /* Helpers */
 
161
    struct RG_NODE *f = NULL;   /* Found item */
 
162
    int dir = 1, removed = 0;
 
163
 
 
164
    assert(tree && data);
 
165
 
 
166
    if (tree->root == NULL) {
 
167
        return 0;               /* empty tree, nothing to remove */
 
168
    }
 
169
 
 
170
    /* Set up helpers */
 
171
    q = &head;
 
172
    g = p = NULL;
 
173
    q->link[1] = tree->root;
 
174
 
 
175
    /* Search and push a red down */
 
176
    while (q->link[dir] != NULL) {
 
177
        int last = dir;
 
178
 
 
179
        /* Update helpers */
 
180
        g = p, p = q;
 
181
        q = q->link[dir];
 
182
        dir = tree->cmp(&(q->data), data);
 
183
 
 
184
        /* Save found node */
 
185
        if (dir == 0)
 
186
            f = q;
 
187
 
 
188
        dir = dir < 0;
 
189
 
 
190
        /* Push the red node down */
 
191
        if (!is_red(q) && !is_red(q->link[dir])) {
 
192
            if (is_red(q->link[!dir]))
 
193
                p = p->link[last] = rgtree_single(q, dir);
 
194
            else if (!is_red(q->link[!dir])) {
 
195
                struct RG_NODE *s = p->link[!last];
 
196
 
 
197
                if (s != NULL) {
 
198
                    if (!is_red(s->link[!last]) && !is_red(s->link[last])) {
 
199
                        /* Color flip */
 
200
                        p->red = 0;
 
201
                        s->red = 1;
 
202
                        q->red = 1;
 
203
                    }
 
204
                    else {
 
205
                        int dir2 = g->link[1] == p;
 
206
 
 
207
                        if (is_red(s->link[last]))
 
208
                            g->link[dir2] = rgtree_double(p, last);
 
209
                        else if (is_red(s->link[!last]))
 
210
                            g->link[dir2] = rgtree_single(p, last);
 
211
 
 
212
                        /* Ensure correct coloring */
 
213
                        q->red = g->link[dir2]->red = 1;
 
214
                        g->link[dir2]->link[0]->red = 0;
 
215
                        g->link[dir2]->link[1]->red = 0;
 
216
                    }
 
217
                }
 
218
            }
 
219
        }
 
220
    }
 
221
 
 
222
    /* Replace and remove if found */
 
223
    if (f != NULL) {
 
224
        if (f != q) {
 
225
            f->data.id = q->data.id;
 
226
            f->data.count = q->data.count;
 
227
            memcpy(f->data.sum, q->data.sum, tree->datasize);
 
228
            memcpy(f->data.mean, q->data.mean, tree->datasize);
 
229
            /* unused:
 
230
            memcpy(f->data.min, q->data.min, tree->datasize);
 
231
            memcpy(f->data.max, q->data.max, tree->datasize);
 
232
            */
 
233
        }
 
234
        p->link[p->link[1] == q] = q->link[q->link[0] == NULL];
 
235
        
 
236
        free(q->data.sum);
 
237
        free(q->data.mean);
 
238
        /* unused:
 
239
        free(q->data.min);
 
240
        free(q->data.max);
 
241
        */
 
242
        free(q);
 
243
        q = NULL;
 
244
        tree->count--;
 
245
        removed = 1;
 
246
    }
 
247
    else
 
248
        G_debug(2, "RB tree: data not found in search tree");
 
249
 
 
250
    /* Update root and make it black */
 
251
    tree->root = head.link[1];
 
252
    if (tree->root != NULL)
 
253
        tree->root->red = 0;
 
254
 
 
255
    return removed;
 
256
}
 
257
 
 
258
/* find data item in tree
 
259
 * returns pointer to data item if found else NULL
 
260
 */
 
261
struct reg_stats *rgtree_find(struct RG_TREE *tree, struct reg_stats *data)
 
262
{
 
263
    struct RG_NODE *curr_node = tree->root;
 
264
    int cmp;
 
265
 
 
266
    assert(tree && data);
 
267
 
 
268
    while (curr_node != NULL) {
 
269
        cmp = tree->cmp(&(curr_node->data), data);
 
270
        if (cmp == 0)
 
271
            return &curr_node->data;    /* found */
 
272
 
 
273
        curr_node = curr_node->link[cmp < 0];
 
274
    }
 
275
    return NULL;
 
276
}
 
277
 
 
278
/* initialize tree traversal
 
279
 * (re-)sets trav structure
 
280
 * returns 0
 
281
 */
 
282
int rgtree_init_trav(struct RG_TRAV *trav, struct RG_TREE *tree)
 
283
{
 
284
    assert(trav && tree);
 
285
 
 
286
    trav->tree = tree;
 
287
    trav->curr_node = tree->root;
 
288
    trav->first = 1;
 
289
    trav->top = 0;
 
290
 
 
291
    return 0;
 
292
}
 
293
 
 
294
/* traverse the tree in ascending order
 
295
 * useful to get all items in the tree non-recursively
 
296
 * struct RG_TRAV *trav needs to be initialized first
 
297
 * returns pointer to data, NULL when finished
 
298
 */
 
299
struct reg_stats *rgtree_traverse(struct RG_TRAV *trav)
 
300
{
 
301
    assert(trav);
 
302
 
 
303
    if (trav->curr_node == NULL) {
 
304
        if (trav->first)
 
305
            G_debug(1, "RB tree: empty tree");
 
306
        else
 
307
            G_debug(1, "RB tree: finished traversing");
 
308
 
 
309
        return NULL;
 
310
    }
 
311
 
 
312
    if (!trav->first)
 
313
        return rgtree_next(trav);
 
314
    else {
 
315
        trav->first = 0;
 
316
        return rgtree_first(trav);
 
317
    }
 
318
}
 
319
 
 
320
/* find start point to traverse the tree in ascending order
 
321
 * useful to get a selection of items in the tree
 
322
 * magnitudes faster than traversing the whole tree
 
323
 * may return first item that's smaller or first item that's larger
 
324
 * struct RG_TRAV *trav needs to be initialized first
 
325
 * returns pointer to data, NULL when finished
 
326
 */
 
327
struct reg_stats *rgtree_traverse_start(struct RG_TRAV *trav, struct reg_stats *data)
 
328
{
 
329
    int dir = 0;
 
330
 
 
331
    assert(trav && data);
 
332
 
 
333
    if (trav->curr_node == NULL) {
 
334
        if (trav->first)
 
335
            G_warning("RB tree: empty tree");
 
336
        else
 
337
            G_warning("RB tree: finished traversing");
 
338
 
 
339
        return NULL;
 
340
    }
 
341
 
 
342
    if (!trav->first)
 
343
        return rgtree_next(trav);
 
344
 
 
345
    /* else first time, get start node */
 
346
 
 
347
    trav->first = 0;
 
348
    trav->top = 0;
 
349
 
 
350
    while (trav->curr_node != NULL) {
 
351
        dir = trav->tree->cmp(&(trav->curr_node->data), data);
 
352
        /* exact match, great! */
 
353
        if (dir == 0)
 
354
            return &(trav->curr_node->data);
 
355
        else {
 
356
            dir = dir < 0;
 
357
            /* end of branch, also reached if
 
358
             * smallest item is larger than search template or
 
359
             * largest item is smaller than search template */
 
360
            if (trav->curr_node->link[dir] == NULL)
 
361
                return &(trav->curr_node->data);
 
362
 
 
363
            trav->up[trav->top++] = trav->curr_node;
 
364
            trav->curr_node = trav->curr_node->link[dir];
 
365
        }
 
366
    }
 
367
 
 
368
    return NULL;                /* should not happen */
 
369
}
 
370
 
 
371
/* two functions needed to fully traverse the tree: initialize and continue
 
372
 * useful to get all items in the tree non-recursively
 
373
 * this one here uses a stack
 
374
 * parent pointers or threads would also be possible
 
375
 * but these would need to be added to RG_NODE
 
376
 * -> more memory needed for standard operations
 
377
 */
 
378
 
 
379
/* start traversing the tree
 
380
 * returns pointer to smallest data item
 
381
 */
 
382
static struct reg_stats *rgtree_first(struct RG_TRAV *trav)
 
383
{
 
384
    /* get smallest item */
 
385
    while (trav->curr_node->link[0] != NULL) {
 
386
        trav->up[trav->top++] = trav->curr_node;
 
387
        trav->curr_node = trav->curr_node->link[0];
 
388
    }
 
389
 
 
390
    return &(trav->curr_node->data);    /* return smallest item */
 
391
}
 
392
 
 
393
/* continue traversing the tree in ascending order
 
394
 * returns pointer to data item, NULL when finished
 
395
 */
 
396
static struct reg_stats *rgtree_next(struct RG_TRAV *trav)
 
397
{
 
398
    if (trav->curr_node->link[1] != NULL) {
 
399
        /* something on the right side: larger item */
 
400
        trav->up[trav->top++] = trav->curr_node;
 
401
        trav->curr_node = trav->curr_node->link[1];
 
402
 
 
403
        /* go down, find smallest item in this branch */
 
404
        while (trav->curr_node->link[0] != NULL) {
 
405
            trav->up[trav->top++] = trav->curr_node;
 
406
            trav->curr_node = trav->curr_node->link[0];
 
407
        }
 
408
    }
 
409
    else {
 
410
        /* at smallest item in this branch, go back up */
 
411
        struct RG_NODE *last;
 
412
 
 
413
        do {
 
414
            if (trav->top == 0) {
 
415
                trav->curr_node = NULL;
 
416
                break;
 
417
            }
 
418
            last = trav->curr_node;
 
419
            trav->curr_node = trav->up[--trav->top];
 
420
        } while (last == trav->curr_node->link[1]);
 
421
    }
 
422
 
 
423
    if (trav->curr_node != NULL) {
 
424
        return &(trav->curr_node->data);
 
425
    }
 
426
    else
 
427
        return NULL;            /* finished traversing */
 
428
}
 
429
 
 
430
/* destroy the tree */
 
431
void rgtree_destroy(struct RG_TREE *tree)
 
432
{
 
433
    struct RG_NODE *it;
 
434
    struct RG_NODE *save = tree->root;
 
435
 
 
436
    /*
 
437
    Rotate away the left links so that
 
438
    we can treat this like the destruction
 
439
    of a linked list
 
440
    */
 
441
    while((it = save) != NULL) {
 
442
        if (it->link[0] == NULL) {
 
443
            /* No left links, just kill the node and move on */
 
444
            save = it->link[1];
 
445
            free(it->data.sum);
 
446
            free(it->data.mean);
 
447
            free(it);
 
448
            it = NULL;
 
449
        }
 
450
        else {
 
451
            /* Rotate away the left link and check again */
 
452
            save = it->link[0];
 
453
            it->link[0] = save->link[1];
 
454
            save->link[1] = it;
 
455
        }
 
456
    }
 
457
    free(tree);
 
458
    tree = NULL;
 
459
    
 
460
    return;
 
461
}
 
462
 
 
463
/* used for debugging: check for errors in tree structure */
 
464
int rgtree_debug(struct RG_TREE *tree, struct RG_NODE *root)
 
465
{
 
466
    int lh, rh;
 
467
 
 
468
    if (root == NULL)
 
469
        return 1;
 
470
    else {
 
471
        struct RG_NODE *ln = root->link[0];
 
472
        struct RG_NODE *rn = root->link[1];
 
473
        int lcmp = 0, rcmp = 0;
 
474
 
 
475
        /* Consecutive red links */
 
476
        if (is_red(root)) {
 
477
            if (is_red(ln) || is_red(rn)) {
 
478
                G_warning("Red Black Tree debugging: Red violation");
 
479
                return 0;
 
480
            }
 
481
        }
 
482
 
 
483
        lh = rgtree_debug(tree, ln);
 
484
        rh = rgtree_debug(tree, rn);
 
485
 
 
486
        if (ln) {
 
487
            lcmp = tree->cmp(&(ln->data), &(root->data));
 
488
        }
 
489
 
 
490
        if (rn) {
 
491
            rcmp = tree->cmp(&(rn->data), &(root->data));
 
492
        }
 
493
 
 
494
        /* Invalid binary search tree:
 
495
         * left node >= parent or right node <= parent */
 
496
        if ((ln != NULL && lcmp > -1)
 
497
            || (rn != NULL && rcmp < 1)) {
 
498
            G_warning("Red Black Tree debugging: Binary tree violation");
 
499
            return 0;
 
500
        }
 
501
 
 
502
        /* Black height mismatch */
 
503
        if (lh != 0 && rh != 0 && lh != rh) {
 
504
            G_warning("Red Black Tree debugging: Black violation");
 
505
            return 0;
 
506
        }
 
507
 
 
508
        /* Only count black links */
 
509
        if (lh != 0 && rh != 0)
 
510
            return is_red(root) ? lh : lh + 1;
 
511
        else
 
512
            return 0;
 
513
    }
 
514
}
 
515
 
 
516
/*******************************************************
 
517
 *                                                     *
 
518
 *  internal functions for Red Black Tree maintenance  *
 
519
 *                                                     *
 
520
 *******************************************************/
 
521
 
 
522
/* add a new node to the tree */
 
523
static struct RG_NODE *rgtree_make_node(size_t datasize, struct reg_stats *data)
 
524
{
 
525
    struct RG_NODE *new_node = (struct RG_NODE *)malloc(sizeof(*new_node));
 
526
 
 
527
    if (new_node == NULL)
 
528
        G_fatal_error("RB Search Tree: Out of memory!");
 
529
 
 
530
    if ((new_node->data.sum = malloc(datasize)) == NULL)
 
531
        G_fatal_error("RB Search Tree: Out of memory!");
 
532
    if ((new_node->data.mean = malloc(datasize)) == NULL)
 
533
        G_fatal_error("RB Search Tree: Out of memory!");
 
534
    /* unused:
 
535
    if ((new_node->data.min = malloc(datasize)) == NULL)
 
536
        G_fatal_error("RB Search Tree: Out of memory!");
 
537
    if ((new_node->data.max = malloc(datasize)) == NULL)
 
538
        G_fatal_error("RB Search Tree: Out of memory!");
 
539
    */
 
540
 
 
541
 
 
542
    new_node->data.id = data->id;
 
543
    new_node->data.count = data->count;
 
544
    memcpy(new_node->data.sum, data->sum, datasize);
 
545
    memcpy(new_node->data.mean, data->mean, datasize);
 
546
    /* unused
 
547
    memcpy(new_node->data.min, data->min, datasize);
 
548
    memcpy(new_node->data.max, data->max, datasize);
 
549
    */
 
550
 
 
551
    new_node->red = 1;          /* 1 is red, 0 is black */
 
552
    new_node->link[0] = NULL;
 
553
    new_node->link[1] = NULL;
 
554
 
 
555
    return new_node;
 
556
}
 
557
 
 
558
/* check for red violation */
 
559
static int is_red(struct RG_NODE *root)
 
560
{
 
561
    if (root)
 
562
        return root->red == 1;
 
563
 
 
564
    return 0;
 
565
}
 
566
 
 
567
/* single rotation */
 
568
static struct RG_NODE *rgtree_single(struct RG_NODE *root, int dir)
 
569
{
 
570
    struct RG_NODE *newroot = root->link[!dir];
 
571
 
 
572
    root->link[!dir] = newroot->link[dir];
 
573
    newroot->link[dir] = root;
 
574
 
 
575
    root->red = 1;
 
576
    newroot->red = 0;
 
577
 
 
578
    return newroot;
 
579
}
 
580
 
 
581
/* double rotation */
 
582
static struct RG_NODE *rgtree_double(struct RG_NODE *root, int dir)
 
583
{
 
584
    root->link[!dir] = rgtree_single(root->link[!dir], !dir);
 
585
    return rgtree_single(root, dir);
 
586
}