← Back to branch summary

~ubuntu-branches/ubuntu/wily/grass/wily

« back to all changes in this revision

Viewing changes to raster/r.cost/btree.c

Tags: 7.0.0~rc1+ds1-1~exp1
http://bugs.debian.org/776349
* New upstream release candidate.
* Repack upstream tarball, remove precompiled Python objects.
* Add upstream metadata.
* Update gbp.conf and Vcs-Git URL to use the experimental branch.
* Update watch file for GRASS 7.0.
* Drop build dependencies for Tcl/Tk, add build dependencies:
  python-numpy, libnetcdf-dev, netcdf-bin, libblas-dev, liblapack-dev
* Update Vcs-Browser URL to use cgit instead of gitweb.
* Update paths to use grass70.
* Add configure options: --with-netcdf, --with-blas, --with-lapack,
  remove --with-tcltk-includes.
* Update patches for GRASS 7.
* Update copyright file, changes:
  - Update copyright years
  - Group files by license
  - Remove unused license sections
* Add patches for various typos.
* Fix desktop file with patch instead of d/rules.
* Use minimal dh rules.
* Bump Standards-Version to 3.9.6, no changes.
* Use dpkg-maintscript-helper to replace directories with symlinks.
  (closes: #776349)
* Update my email to use @debian.org address.

Show diffs side-by-side

added added

removed removed

Lines of Context:
raster/r.cost/btree.c
1
 
 
2
 
/****************************************************************************
3
 
 *
4
 
 * MODULE:       r.cost
5
 
 *
6
 
 * AUTHOR(S):    Antony Awaida - IESL - M.I.T.
7
 
 *               James Westervelt - CERL
8
 
 *               Pierre de Mouveaux <pmx audiovu com>
9
 
 *               Eric G. Miller <egm2 jps net>
10
 
 *
11
 
 * PURPOSE:      Outputs a raster map layer showing the cumulative cost
12
 
 *               of moving between different geographic locations on an
13
 
 *               input raster map layer whose cell category values
14
 
 *               represent cost.
15
 
 *
16
 
 * COPYRIGHT:    (C) 2006-2009 by the GRASS Development Team
17
 
 *
18
 
 *               This program is free software under the GNU General Public
19
 
 *               License (>=v2). Read the file COPYING that comes with GRASS
20
 
 *               for details.
21
 
 *
22
 
 ***************************************************************************/
23
 
 
24
 
/* These routines manage the list of grid-cell candidates for 
25
 
 * visiting to calculate distances to surrounding cells.
26
 
 * A binary tree (btree) approach is used.  Components are
27
 
 * sorted by distance.
28
 
 *
29
 
 * insert ()
30
 
 *   inserts a new row-col with its distance value into the btree
31
 
 *
32
 
 * delete()
33
 
 *   deletes (if possible) a row-col entry in the tree
34
 
 *
35
 
 * get_lowest()
36
 
 *   retrieves the entry with the smallest distance value
37
 
 */
38
 
 
39
 
 
40
 
#include <grass/gis.h>
41
 
#include "local_proto.h"
42
 
#include "memory.h"
43
 
#include <stdlib.h>
44
 
#include <grass/glocale.h>
45
 
 
46
 
static struct cost *start_cell = NULL;
47
 
 
48
 
/*  static int show(struct cost *); */
49
 
static int do_quit(double, int, int);
50
 
 
51
 
struct cost *insert(double min_cost, int row, int col)
52
 
{
53
 
    struct cost *new_cell, *next_cell;
54
 
 
55
 
    /*      new_cell = (struct cost *)(G_malloc(sizeof(struct cost))); */
56
 
    new_cell = get();
57
 
    if (new_cell == NULL) {
58
 
        G_message(_("NULL value computed (row %d, col %d)"),
59
 
                  row, col);
60
 
    }
61
 
    new_cell->min_cost = min_cost;
62
 
    new_cell->row = row;
63
 
    new_cell->col = col;
64
 
    new_cell->above = NULL;
65
 
    new_cell->higher = NULL;
66
 
    new_cell->lower = NULL;
67
 
    new_cell->nexttie = NULL;
68
 
    new_cell->previoustie = NULL;
69
 
 
70
 
    if (start_cell == NULL) {
71
 
        start_cell = new_cell;
72
 
        return (new_cell);
73
 
    }
74
 
 
75
 
    for (next_cell = start_cell;;) {
76
 
        if (min_cost < next_cell->min_cost) {
77
 
            if (next_cell->lower != NULL) {
78
 
                next_cell = next_cell->lower;
79
 
                continue;
80
 
            }
81
 
            new_cell->above = next_cell;
82
 
            next_cell->lower = new_cell;
83
 
            return (new_cell);
84
 
        }
85
 
        if (min_cost > next_cell->min_cost) {
86
 
            if (next_cell->higher != NULL) {
87
 
                next_cell = next_cell->higher;
88
 
                continue;
89
 
            }
90
 
            new_cell->above = next_cell;
91
 
            next_cell->higher = new_cell;
92
 
            return (new_cell);
93
 
        }
94
 
 
95
 
        /* If we find a value that is exactly equal to new value */
96
 
        new_cell->nexttie = next_cell->nexttie;
97
 
        next_cell->nexttie = new_cell;
98
 
        new_cell->previoustie = next_cell;
99
 
        if (new_cell->nexttie != NULL)
100
 
            new_cell->nexttie->previoustie = new_cell;
101
 
 
102
 
        return (new_cell);
103
 
    }
104
 
}
105
 
 
106
 
 
107
 
struct cost *find(double min_cost, int row, int col)
108
 
{
109
 
    struct cost *next_cell;
110
 
    struct cost *next_tie_cell;
111
 
 
112
 
    for (next_cell = start_cell;;) {
113
 
        if (min_cost <= next_cell->min_cost) {
114
 
            for (next_tie_cell = next_cell;
115
 
                 next_tie_cell != NULL;
116
 
                 next_tie_cell = next_tie_cell->nexttie)
117
 
                if (next_tie_cell->row == row && next_tie_cell->col == col)
118
 
                    return (next_tie_cell);
119
 
            /*
120
 
               if (next_cell->row == row && next_cell->col == col)
121
 
               return(next_cell) ;
122
 
             */
123
 
 
124
 
            if (next_cell->lower != NULL) {
125
 
                next_cell = next_cell->lower;
126
 
                continue;
127
 
            }
128
 
            G_debug(2, "1 ");
129
 
            return NULL;
130
 
            do_quit(min_cost, row, col); /* ??? */
131
 
        }
132
 
        else {
133
 
            if (next_cell->higher != NULL) {
134
 
                next_cell = next_cell->higher;
135
 
                continue;
136
 
            }
137
 
            G_debug(2, "2 ");
138
 
            return NULL;
139
 
            do_quit(min_cost, row, col); /* ??? */
140
 
        }
141
 
    }
142
 
}
143
 
 
144
 
static int do_quit(double min_cost, int row, int col)
145
 
{
146
 
    G_warning(_("Unable to find row %d, col %d: %f"),
147
 
              row, col, min_cost);
148
 
    show_all();
149
 
    exit(EXIT_FAILURE);
150
 
}
151
 
 
152
 
struct cost *get_lowest(void)
153
 
{
154
 
    struct cost *next_cell;
155
 
 
156
 
    if (start_cell == NULL)
157
 
        return (NULL);
158
 
 
159
 
    for (next_cell = start_cell;
160
 
         next_cell->lower != NULL; next_cell = next_cell->lower) ;
161
 
 
162
 
    /* Grab my first tie instead of me */
163
 
    if (next_cell->nexttie != NULL)
164
 
        next_cell = next_cell->nexttie;
165
 
 
166
 
    if (next_cell->row == -1) {
167
 
        /*
168
 
           fprintf(stderr, "Deleting %d\n", next_cell) ;
169
 
           show_all() ;
170
 
         */
171
 
        delete(next_cell);
172
 
        /*
173
 
           fprintf(stderr, "Deleted %d\n", next_cell) ;
174
 
           show_all() ;
175
 
         */
176
 
        return (get_lowest());
177
 
    }
178
 
 
179
 
    return (next_cell);
180
 
}
181
 
 
182
 
int delete(struct cost *delete_cell)
183
 
{
184
 
    if (delete_cell == NULL) {
185
 
        G_warning(_("Illegal delete request"));
186
 
        return 0;
187
 
    }
188
 
 
189
 
    /* Simple remove if I'm a one of the "ties" */
190
 
    if (delete_cell->previoustie != NULL) {
191
 
        delete_cell->previoustie->nexttie = delete_cell->nexttie;
192
 
        if (delete_cell->nexttie != NULL)
193
 
            delete_cell->nexttie->previoustie = delete_cell->previoustie;
194
 
        give(delete_cell);
195
 
        return 0;
196
 
    }
197
 
    /* If I have a list of ties, link replace me with the first
198
 
       in that list  */
199
 
    if (delete_cell->nexttie != NULL) {
200
 
        delete_cell->nexttie->above = delete_cell->above;
201
 
        if (delete_cell->above != NULL) {
202
 
            if (delete_cell->above->lower == delete_cell)
203
 
                delete_cell->above->lower = delete_cell->nexttie;
204
 
            else
205
 
                delete_cell->above->higher = delete_cell->nexttie;
206
 
        }
207
 
 
208
 
        delete_cell->nexttie->lower = delete_cell->lower;
209
 
        if (delete_cell->lower != NULL)
210
 
            delete_cell->lower->above = delete_cell->nexttie;
211
 
 
212
 
        delete_cell->nexttie->higher = delete_cell->higher;
213
 
        if (delete_cell->higher != NULL)
214
 
            delete_cell->higher->above = delete_cell->nexttie;
215
 
        if (start_cell == delete_cell)
216
 
            start_cell = delete_cell->nexttie;
217
 
        delete_cell->nexttie->previoustie = NULL;
218
 
 
219
 
        give(delete_cell);
220
 
        return (0);
221
 
    }
222
 
    /*
223
 
       \      \      \      \   
224
 
       1  X   4  X   7  X   10 X  
225
 
       N N    / N    N \    / \ 
226
 
 
227
 
       /      /      /      / 
228
 
       2  X   5  X   8  X   11 X  
229
 
       N N    / N    N \    / \
230
 
 
231
 
       N      N      N      N  
232
 
       3  X   6  X   9  X   12 X  
233
 
       N N    / N    N \    / \
234
 
     */
235
 
    if (delete_cell->higher == NULL) {  /* 123456       */
236
 
        if (delete_cell->lower == NULL) {       /* 123          */
237
 
            if (delete_cell->above == NULL) {   /*   3          */
238
 
                start_cell = NULL;
239
 
                give(delete_cell);
240
 
                return 0;
241
 
            }
242
 
            if (delete_cell->above->higher == delete_cell) {    /* 1            */
243
 
                delete_cell->above->higher = NULL;
244
 
                give(delete_cell);
245
 
                return 0;
246
 
            }
247
 
            else {              /*  2           */
248
 
                delete_cell->above->lower = NULL;
249
 
                give(delete_cell);
250
 
                return 0;
251
 
            }
252
 
        }
253
 
        else {                  /*    456       */
254
 
 
255
 
            if (delete_cell->above == NULL) {   /*      6       */
256
 
                start_cell = delete_cell->lower;
257
 
                delete_cell->lower->above = NULL;
258
 
                give(delete_cell);
259
 
                return 0;
260
 
            }
261
 
            if (delete_cell->above->higher == delete_cell) {    /*    4         */
262
 
                delete_cell->above->higher = delete_cell->lower;
263
 
                delete_cell->lower->above = delete_cell->above;
264
 
                give(delete_cell);
265
 
                return 0;
266
 
            }
267
 
            else {              /*     5        */
268
 
                delete_cell->above->lower = delete_cell->lower;
269
 
                delete_cell->lower->above = delete_cell->above;
270
 
                give(delete_cell);
271
 
                return 0;
272
 
            }
273
 
        }
274
 
    }
275
 
    if (delete_cell->lower == NULL) {   /*       789    */
276
 
        if (delete_cell->above == NULL) {       /*         9    */
277
 
            start_cell = delete_cell->higher;
278
 
            delete_cell->higher->above = NULL;
279
 
            give(delete_cell);
280
 
            return 0;
281
 
        }
282
 
        if (delete_cell->above->higher == delete_cell) {        /*       7      */
283
 
            delete_cell->above->higher = delete_cell->higher;
284
 
            delete_cell->higher->above = delete_cell->above;
285
 
            give(delete_cell);
286
 
            return 0;
287
 
        }
288
 
        else {                  /*        8     */
289
 
            delete_cell->above->lower = delete_cell->higher;
290
 
            delete_cell->higher->above = delete_cell->above;
291
 
            give(delete_cell);
292
 
            return 0;
293
 
        }
294
 
    }
295
 
    /*
296
 
     * At this point we are left with 10,11,12 which can be expanded
297
 
     *    \   
298
 
     *  10 X         X          X   
299
 
     *    / \       / \        / \  
300
 
     *          A  O   -   B  -   O     C ALL OTHERS
301
 
     *      /     / N            N \
302
 
     *  11 X  
303
 
     *    / \
304
 
     *
305
 
     *     N  
306
 
     *  12 X  
307
 
     *    / \
308
 
     */
309
 
 
310
 
    if (delete_cell->lower->higher == NULL) {   /* A */
311
 
        if (delete_cell == start_cell) {        /* 12A */
312
 
            delete_cell->lower->higher = delete_cell->higher;
313
 
            delete_cell->higher->above = delete_cell->lower;
314
 
            start_cell = delete_cell->lower;
315
 
            delete_cell->lower->above = NULL;
316
 
            give(delete_cell);
317
 
            return 0;
318
 
        }
319
 
        if (delete_cell->above->higher == delete_cell) {        /* 10A */
320
 
            delete_cell->lower->higher = delete_cell->higher;
321
 
            delete_cell->higher->above = delete_cell->lower;
322
 
            delete_cell->above->higher = delete_cell->lower;
323
 
            delete_cell->lower->above = delete_cell->above;
324
 
            give(delete_cell);
325
 
            return 0;
326
 
        }
327
 
        else {                  /* 11A */
328
 
            delete_cell->lower->higher = delete_cell->higher;
329
 
            delete_cell->higher->above = delete_cell->lower;
330
 
            delete_cell->above->lower = delete_cell->lower;
331
 
            delete_cell->lower->above = delete_cell->above;
332
 
            give(delete_cell);
333
 
            return 0;
334
 
        }
335
 
    }
336
 
    if (delete_cell->higher->lower == NULL) {   /* A */
337
 
        if (delete_cell == start_cell) {        /* 12B */
338
 
            delete_cell->higher->lower = delete_cell->lower;
339
 
            delete_cell->lower->above = delete_cell->higher;
340
 
            start_cell = delete_cell->higher;
341
 
            delete_cell->higher->above = NULL;
342
 
            give(delete_cell);
343
 
            return 0;
344
 
        }
345
 
        if (delete_cell->above->lower == delete_cell) { /* 11B */
346
 
            delete_cell->higher->lower = delete_cell->lower;
347
 
            delete_cell->lower->above = delete_cell->higher;
348
 
            delete_cell->above->lower = delete_cell->higher;
349
 
            delete_cell->higher->above = delete_cell->above;
350
 
            give(delete_cell);
351
 
            return 0;
352
 
        }
353
 
        else {                  /* 10B */
354
 
            delete_cell->higher->lower = delete_cell->lower;
355
 
            delete_cell->lower->above = delete_cell->higher;
356
 
            delete_cell->above->higher = delete_cell->higher;
357
 
            delete_cell->higher->above = delete_cell->above;
358
 
            give(delete_cell);
359
 
            return 0;
360
 
        }
361
 
    }
362
 
    /* If we get this far, the node cannot be safely removed.  Just leave
363
 
     * an internal mark noting that it is no longer good.
364
 
     */
365
 
    delete_cell->row = -1;
366
 
    return 0;
367
 
}
368
 
 
369
 
int show_all(void)
370
 
{
371
 
    if (start_cell == NULL) {
372
 
        G_debug(1, "Nothing to show");
373
 
        return 1;
374
 
    }
375
 
    show(start_cell);
376
 
 
377
 
    return 0;
378
 
}
379
 
 
380
 
int show(struct cost *next)
381
 
{
382
 
    struct cost *next_cell;
383
 
 
384
 
    if (next == NULL)
385
 
        return 0;
386
 
    for (next_cell = next; next_cell != NULL; next_cell = next_cell->nexttie)
387
 
        G_message("%p %d,%d,%f %p %p %p %p",
388
 
                  next_cell,
389
 
                  next_cell->row,
390
 
                  next_cell->col,
391
 
                  next_cell->min_cost,
392
 
                  next_cell->nexttie,
393
 
                  next_cell->lower, next_cell->higher, next_cell->above);
394
 
    show(next->lower);
395
 
    show(next->higher);
396
 
 
397
 
    return 0;
398
 
}
399
 
 
400
 
int check_all(char *str)
401
 
{
402
 
    if (start_cell->above != NULL) {
403
 
        G_fatal_error(_("Bad start cell"));
404
 
    }
405
 
    check(str, start_cell);
406
 
 
407
 
    return 0;
408
 
}
409
 
 
410
 
int check(char *str, struct cost *start)
411
 
{
412
 
    if (start == NULL)
413
 
        return 0;
414
 
 
415
 
    if (start->lower != NULL) {
416
 
        if (start->min_cost < start->lower->min_cost) {
417
 
            G_warning(_("%s %f-%f lower cost higher or equal"), str,
418
 
                      start->min_cost, start->lower->min_cost);
419
 
            show_all();
420
 
            exit(EXIT_FAILURE);
421
 
        }
422
 
        if (start->lower->above != start) {
423
 
            G_warning(_("%s lower above pointer wrong"), str);
424
 
            show_all();
425
 
            exit(EXIT_FAILURE);
426
 
        }
427
 
    }
428
 
    if (start->higher != NULL) {
429
 
        if (start->min_cost >= start->higher->min_cost) {
430
 
            G_warning(_("%s %f-%f higher cost lower"), str,
431
 
                      start->min_cost, start->higher->min_cost);
432
 
            show_all();
433
 
            exit(EXIT_FAILURE);
434
 
        }
435
 
        if (start->higher->above != start) {
436
 
            G_warning(_("%s higher above pointer wrong"), str);
437
 
            show_all();
438
 
            exit(EXIT_FAILURE);
439
 
        }
440
 
    }
441
 
    check(str, start->lower);
442
 
    check(str, start->higher);
443
 
 
444
 
    return 0;
445
 
}