← Back to branch summary

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

« back to all changes in this revision

Viewing changes to raster/r.cost/heap.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/heap.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
 *               min heap by Markus Metz
 
12
 *
 
13
 * PURPOSE:      Outputs a raster map layer showing the cumulative cost
 
14
 *               of moving between different geographic locations on an
 
15
 *               input raster map layer whose cell category values
 
16
 *               represent cost.
 
17
 *
 
18
 * COPYRIGHT:    (C) 2006-2009 by the GRASS Development Team
 
19
 *
 
20
 *               This program is free software under the GNU General Public
 
21
 *               License (>=v2). Read the file COPYING that comes with GRASS
 
22
 *               for details.
 
23
 *
 
24
 ***************************************************************************/
 
25
 
 
26
/* These routines manage the list of grid-cell candidates for 
 
27
 * visiting to calculate distances to surrounding cells.
 
28
 * A min-heap approach is used.  Components are
 
29
 * sorted first by distance then by the order in which they were added.
 
30
 *
 
31
 * insert ()
 
32
 *   inserts a new row-col with its distance value into the heap
 
33
 *
 
34
 * delete()
 
35
 *   deletes a row-col entry in the heap
 
36
 *
 
37
 * get_lowest()
 
38
 *   retrieves the entry with the smallest distance value
 
39
 */
 
40
 
 
41
 
 
42
#include <stdlib.h>
 
43
#include <grass/gis.h>
 
44
#include <grass/glocale.h>
 
45
#include "cost.h"
 
46
 
 
47
#define GET_PARENT(c) (((c) - 2) / 3 + 1)
 
48
#define GET_CHILD(p) (((p) * 3) - 1)
 
49
 
 
50
static long next_point = 0;
 
51
static long heap_size = 0;
 
52
static long heap_alloced = 0;
 
53
static struct cost **heap_index, *free_point;
 
54
 
 
55
int init_heap(void)
 
56
{
 
57
    next_point = 0;
 
58
    heap_size = 0;
 
59
    heap_alloced = 1000;
 
60
    heap_index = (struct cost **) G_malloc(heap_alloced * sizeof(struct cost *));
 
61
 
 
62
    free_point = NULL;
 
63
    
 
64
    return 0;
 
65
}
 
66
 
 
67
int free_heap(void)
 
68
{
 
69
    if (heap_alloced)
 
70
        G_free(heap_index);
 
71
 
 
72
    if (free_point)
 
73
        G_free(free_point);
 
74
 
 
75
    return 0;
 
76
}
 
77
 
 
78
/* compare two costs
 
79
 * return 1 if a < b else 0 */
 
80
int cmp_costs(struct cost *a, struct cost *b)
 
81
{
 
82
    if (a->min_cost < b->min_cost)
 
83
        return 1;
 
84
    else if (a->min_cost == b->min_cost) {
 
85
        if (a->age < b->age)
 
86
            return 1;
 
87
    }
 
88
 
 
89
    return 0;
 
90
}
 
91
 
 
92
long sift_up(long start, struct cost * child_pnt)
 
93
{
 
94
    register long parent, child;
 
95
 
 
96
    child = start;
 
97
 
 
98
    while (child > 1) {
 
99
        parent = GET_PARENT(child);
 
100
 
 
101
        /* child is smaller */
 
102
        if (cmp_costs(child_pnt, heap_index[parent])) {
 
103
            /* push parent point down */
 
104
            heap_index[child] = heap_index[parent];
 
105
            child = parent;
 
106
        }
 
107
        else
 
108
            /* no more sifting up, found new slot for child */
 
109
            break;
 
110
    }
 
111
 
 
112
    /* put point in new slot */
 
113
    if (child < start) {
 
114
        heap_index[child] = child_pnt;
 
115
    }
 
116
 
 
117
    return child;
 
118
}
 
119
 
 
120
struct cost *insert(double min_cost, int row, int col)
 
121
{
 
122
    struct cost *new_cell;
 
123
 
 
124
    if (free_point) {
 
125
        new_cell = free_point;
 
126
        free_point = NULL;
 
127
    }
 
128
    else
 
129
        new_cell = (struct cost *)(G_malloc(sizeof(struct cost)));
 
130
 
 
131
    new_cell->min_cost = min_cost;
 
132
    new_cell->age = next_point;
 
133
    new_cell->row = row;
 
134
    new_cell->col = col;
 
135
 
 
136
    next_point++;
 
137
    heap_size++;
 
138
    if (heap_size >= heap_alloced) {
 
139
        heap_alloced += 1000;
 
140
        heap_index = (struct cost **) G_realloc((void *)heap_index, heap_alloced * sizeof(struct cost *));
 
141
    }
 
142
 
 
143
    heap_index[heap_size] = new_cell;
 
144
    sift_up(heap_size, new_cell);
 
145
 
 
146
    return (new_cell);
 
147
}
 
148
 
 
149
struct cost *get_lowest(void)
 
150
{
 
151
    struct cost *next_cell;
 
152
    register long parent, child, childr, i;
 
153
 
 
154
    if (heap_size == 0)
 
155
        return NULL;
 
156
        
 
157
    next_cell = heap_index[1];
 
158
    heap_index[0] = next_cell;
 
159
 
 
160
    if (heap_size == 1) {
 
161
        heap_size--;
 
162
 
 
163
        heap_index[1] = NULL;
 
164
 
 
165
        return next_cell;
 
166
    }
 
167
 
 
168
    /* start with root */
 
169
    parent = 1;
 
170
 
 
171
    /* sift down: move hole back towards bottom of heap */
 
172
 
 
173
    while ((child = GET_CHILD(parent)) <= heap_size) {
 
174
        /* select smallest child */
 
175
        if (child < heap_size) {
 
176
            childr = child + 1;
 
177
            i = child + 3;
 
178
            while (childr < i && childr <= heap_size) {
 
179
                /* get smallest child */
 
180
                if (cmp_costs(heap_index[childr], heap_index[child])) {
 
181
                    child = childr;
 
182
                }
 
183
                childr++;
 
184
            }
 
185
        }
 
186
 
 
187
        /* move hole down */
 
188
        heap_index[parent] = heap_index[child];
 
189
        parent = child;
 
190
    }
 
191
 
 
192
    /* hole is in lowest layer, move to heap end */
 
193
    if (parent < heap_size) {
 
194
        heap_index[parent] = heap_index[heap_size];
 
195
 
 
196
        /* sift up last swapped point, only necessary if hole moved to heap end */
 
197
        sift_up(parent, heap_index[parent]);
 
198
    }
 
199
 
 
200
    /* the actual drop */
 
201
    heap_size--;
 
202
 
 
203
    return next_cell;
 
204
}
 
205
 
 
206
int delete(struct cost *delete_cell)
 
207
{
 
208
    if (free_point)
 
209
        G_free(delete_cell);
 
210
    else
 
211
        free_point = delete_cell;
 
212
 
 
213
    return 0;
 
214
}