2
/****************************************************************************
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>
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
16
* COPYRIGHT: (C) 2006-2009 by the GRASS Development Team
18
* This program is free software under the GNU General Public
19
* License (>=v2). Read the file COPYING that comes with GRASS
22
***************************************************************************/
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
30
* inserts a new row-col with its distance value into the btree
33
* deletes (if possible) a row-col entry in the tree
36
* retrieves the entry with the smallest distance value
40
#include <grass/gis.h>
41
#include "local_proto.h"
44
#include <grass/glocale.h>
46
static struct cost *start_cell = NULL;
48
/* static int show(struct cost *); */
49
static int do_quit(double, int, int);
51
struct cost *insert(double min_cost, int row, int col)
53
struct cost *new_cell, *next_cell;
55
/* new_cell = (struct cost *)(G_malloc(sizeof(struct cost))); */
57
if (new_cell == NULL) {
58
G_message(_("NULL value computed (row %d, col %d)"),
61
new_cell->min_cost = min_cost;
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;
70
if (start_cell == NULL) {
71
start_cell = new_cell;
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;
81
new_cell->above = next_cell;
82
next_cell->lower = new_cell;
85
if (min_cost > next_cell->min_cost) {
86
if (next_cell->higher != NULL) {
87
next_cell = next_cell->higher;
90
new_cell->above = next_cell;
91
next_cell->higher = new_cell;
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;
107
struct cost *find(double min_cost, int row, int col)
109
struct cost *next_cell;
110
struct cost *next_tie_cell;
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);
120
if (next_cell->row == row && next_cell->col == col)
124
if (next_cell->lower != NULL) {
125
next_cell = next_cell->lower;
130
do_quit(min_cost, row, col); /* ??? */
133
if (next_cell->higher != NULL) {
134
next_cell = next_cell->higher;
139
do_quit(min_cost, row, col); /* ??? */
144
static int do_quit(double min_cost, int row, int col)
146
G_warning(_("Unable to find row %d, col %d: %f"),
152
struct cost *get_lowest(void)
154
struct cost *next_cell;
156
if (start_cell == NULL)
159
for (next_cell = start_cell;
160
next_cell->lower != NULL; next_cell = next_cell->lower) ;
162
/* Grab my first tie instead of me */
163
if (next_cell->nexttie != NULL)
164
next_cell = next_cell->nexttie;
166
if (next_cell->row == -1) {
168
fprintf(stderr, "Deleting %d\n", next_cell) ;
173
fprintf(stderr, "Deleted %d\n", next_cell) ;
176
return (get_lowest());
182
int delete(struct cost *delete_cell)
184
if (delete_cell == NULL) {
185
G_warning(_("Illegal delete request"));
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;
197
/* If I have a list of ties, link replace me with the first
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;
205
delete_cell->above->higher = delete_cell->nexttie;
208
delete_cell->nexttie->lower = delete_cell->lower;
209
if (delete_cell->lower != NULL)
210
delete_cell->lower->above = delete_cell->nexttie;
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;
235
if (delete_cell->higher == NULL) { /* 123456 */
236
if (delete_cell->lower == NULL) { /* 123 */
237
if (delete_cell->above == NULL) { /* 3 */
242
if (delete_cell->above->higher == delete_cell) { /* 1 */
243
delete_cell->above->higher = NULL;
248
delete_cell->above->lower = NULL;
255
if (delete_cell->above == NULL) { /* 6 */
256
start_cell = delete_cell->lower;
257
delete_cell->lower->above = NULL;
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;
268
delete_cell->above->lower = delete_cell->lower;
269
delete_cell->lower->above = delete_cell->above;
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;
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;
289
delete_cell->above->lower = delete_cell->higher;
290
delete_cell->higher->above = delete_cell->above;
296
* At this point we are left with 10,11,12 which can be expanded
300
* A O - B - O C ALL OTHERS
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;
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;
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;
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;
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;
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;
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.
365
delete_cell->row = -1;
371
if (start_cell == NULL) {
372
G_debug(1, "Nothing to show");
380
int show(struct cost *next)
382
struct cost *next_cell;
386
for (next_cell = next; next_cell != NULL; next_cell = next_cell->nexttie)
387
G_message("%p %d,%d,%f %p %p %p %p",
393
next_cell->lower, next_cell->higher, next_cell->above);
400
int check_all(char *str)
402
if (start_cell->above != NULL) {
403
G_fatal_error(_("Bad start cell"));
405
check(str, start_cell);
410
int check(char *str, struct cost *start)
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);
422
if (start->lower->above != start) {
423
G_warning(_("%s lower above pointer wrong"), str);
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);
435
if (start->higher->above != start) {
436
G_warning(_("%s higher above pointer wrong"), str);
441
check(str, start->lower);
442
check(str, start->higher);