GRASS GIS 7 Programmer's Manual  7.9.dev(2021)-e5379bbd7
cell_stats.c
Go to the documentation of this file.
1 /*!
2  * \file lib/raster/cell_stats.c
3  *
4  * \brief Raster Library - Raster cell statistics
5  *
6  * (C) 2001-2009 GRASS Development Team
7  *
8  * This program is free software under the GNU General Public License
9  * (>=v2). Read the file COPYING that comes with GRASS for details.
10  *
11  * \author Original author CERL
12  */
13 
14 #include <stdlib.h>
15 
16 #include <grass/gis.h>
17 #include <grass/raster.h>
18 
19 #define INCR 10
20 #define SHIFT 6
21 
22 static const int NCATS = 1 << SHIFT;
23 
24 #define NODE struct Cell_stats_node
25 
26 static int next_node(struct Cell_stats *);
27 static void init_node(NODE *, int, int);
28 
29 /*!
30  * \brief Initialize cell stats
31  *
32  * This routine, which must be called first, initializes the
33  * Cell_stats structure.
34  *
35  * Set the count for NULL-values to zero.
36  *
37  * \param s pointer to Cell_stats structure
38  */
40 {
41  s->N = 0;
42  s->tlen = INCR;
43  s->node = (NODE *) G_malloc(s->tlen * sizeof(NODE));
44  s->null_data_count = 0;
45 }
46 
47 /*!
48  * \brief Add data to cell stats
49  *
50  * The <i>n</i> CELL values in the <i>data</i> array are inserted (and
51  * counted) in the Cell_stats structure.
52  *
53  * Look for NULLs and update the NULL-value count.
54  *
55  * \param cell raster values
56  * \param n number of values
57  * \param s pointer to Cell_stats structure which holds cell stats info
58  *
59  * \return 1 on failure
60  * \return 0 on success
61  */
62 int Rast_update_cell_stats(const CELL * cell, int n, struct Cell_stats *s)
63 {
64  CELL cat;
65  int p, q;
66  int idx, offset;
67  int N;
68  NODE *node, *pnode;
69  NODE *new_node;
70 
71  if (n <= 0)
72  return 1;
73 
74  node = s->node;
75 
76  /* first non-null node is special case */
77  if ((N = s->N) == 0) {
78  cat = *cell++;
79  while (Rast_is_c_null_value(&cat)) {
80  s->null_data_count++;
81  cat = *cell++;
82  n--;
83  }
84  if (n > 0) { /* if there are some non-null cells */
85  N = 1;
86  if (cat < 0) {
87  idx = -((-cat) >> SHIFT) - 1;
88  offset = cat + ((-idx) << SHIFT) - 1;
89  }
90  else {
91  idx = cat >> SHIFT;
92  offset = cat - (idx << SHIFT);
93  }
94  fflush(stderr);
95  init_node(&node[1], idx, offset);
96  node[1].right = 0;
97  n--;
98  }
99  }
100  while (n-- > 0) {
101  cat = *cell++;
102  if (Rast_is_c_null_value(&cat)) {
103  s->null_data_count++;
104  continue;
105  }
106  if (cat < 0) {
107  idx = -((-cat) >> SHIFT) - 1;
108  offset = cat + ((-idx) << SHIFT) - 1;
109  }
110  else {
111  idx = cat >> SHIFT;
112  offset = cat - (idx << SHIFT);
113  }
114 
115  q = 1;
116  while (q > 0) {
117  pnode = &node[p = q];
118  if (pnode->idx == idx) {
119  pnode->count[offset]++;
120  break;
121  }
122  if (pnode->idx > idx)
123  q = pnode->left; /* go left */
124  else
125  q = pnode->right; /* go right */
126  }
127  if (q > 0)
128  continue; /* found */
129 
130  /* new node */
131  N++;
132 
133  /* grow the tree? */
134  if (N >= s->tlen) {
135  node =
136  (NODE *) G_realloc((char *)node,
137  sizeof(NODE) * (s->tlen += INCR));
138  pnode = &node[p]; /* realloc moves node, must reassign pnode */
139  }
140 
141  /* add node to tree */
142  init_node(new_node = &node[N], idx, offset);
143 
144  if (pnode->idx > idx) {
145  new_node->right = -p; /* create thread */
146  pnode->left = N; /* insert left */
147  }
148  else {
149  new_node->right = pnode->right; /* copy right link/thread */
150  pnode->right = N; /* add right */
151  }
152  } /* while n-- > 0 */
153  s->N = N;
154  s->node = node;
155 
156  return 0;
157 }
158 
159 static void init_node(NODE * node, int idx, int offset)
160 {
161  long *count;
162  int i;
163 
164  count = node->count = (long *)G_calloc(i = NCATS, sizeof(long));
165  while (i--)
166  *count++ = 0;
167  node->idx = idx;
168  node->count[offset] = 1;
169  node->left = 0;
170 }
171 
172 
173 /*!
174  * \brief Random query of cell stats
175  *
176  * This routine allows a random query of the Cell_stats structure. The
177  * \p count associated with the raster value \p cat is
178  * set. The routine returns 1 if \p cat was found in the
179  * structure, 0 otherwise.
180  *
181  * Allow finding the count for the NULL-value.
182  *
183  * \param cat raster value
184  * \param[out] count count
185  * \param s pointer to Cell_stats structure which holds cell stats info
186  *
187  * \return 1 if found
188  * \return 0 if not found
189  */
190 int Rast_find_cell_stat(CELL cat, long *count, const struct Cell_stats *s)
191 {
192  int q;
193  int idx;
194  int offset;
195 
196  *count = 0;
197  if (Rast_is_c_null_value(&cat)) {
198  *count = s->null_data_count;
199  return (*count != 0);
200  }
201 
202  if (s->N <= 0)
203  return 0;
204 
205  /*
206  if (cat < 0)
207  {
208  idx = -(-cat/NCATS) - 1;
209  offset = cat - idx*NCATS - 1;
210  }
211  else
212  {
213  idx = cat/NCATS;
214  offset = cat - idx*NCATS;
215  }
216  */
217  if (cat < 0) {
218  idx = -((-cat) >> SHIFT) - 1;
219  offset = cat + ((-idx) << SHIFT) - 1;
220  }
221  else {
222  idx = cat >> SHIFT;
223  offset = cat - (idx << SHIFT);
224  }
225 
226  q = 1;
227  while (q > 0) {
228  if (s->node[q].idx == idx) {
229  *count = s->node[q].count[offset];
230  return (*count != 0);
231  }
232  if (s->node[q].idx > idx)
233  q = s->node[q].left; /* go left */
234  else
235  q = s->node[q].right; /* go right */
236  }
237  return 0;
238 }
239 
240 /*!
241  * \brief Reset/rewind cell stats
242  *
243  * The structure <i>s</i> is rewound (i.e., positioned at the first
244  * raster category) so that sorted sequential retrieval can begin.
245  *
246  * \param s pointer to Cell_stats structure which holds cell stats info
247  *
248  * \return 0
249  */
251 {
252  int q;
253 
254  if (s->N <= 0)
255  return 1;
256  /* start at root and go all the way to the left */
257  s->curp = 1;
258  while ((q = s->node[s->curp].left))
259  s->curp = q;
260  s->curoffset = -1;
261 
262  return 0;
263 }
264 
265 static int next_node(struct Cell_stats *s)
266 {
267  int q;
268 
269  /* go to the right */
270  s->curp = s->node[s->curp].right;
271 
272  if (s->curp == 0) /* no more */
273  return 0;
274 
275  if (s->curp < 0) { /* thread. stop here */
276  s->curp = -(s->curp);
277  return 1;
278  }
279 
280  while ((q = s->node[s->curp].left)) /* now go all the way left */
281  s->curp = q;
282 
283  return 1;
284 }
285 
286 /*!
287  * \brief Retrieve sorted cell stats
288  *
289  * Retrieves the next <i>cat, count</i> combination from the
290  * structure. Returns 0 if there are no more items, non-zero if there
291  * are more. For example:
292  *
293  \code
294  struct Cell_stats s;
295  CELL cat;
296  long count;
297 
298  // updating <b>s</b> occurs here
299 
300  Rast_rewind_cell_stats(&s);
301  while (Rast_next_cell_stat(&cat,&count,&s)
302  fprintf(stdout, "%ld %ld\n", (long) cat, count);
303  \endcode
304  *
305  * Do not return a record for the NULL-value
306  *
307  * \param cat raster value
308  * \param[out] count
309  * \param s pointer to Cell_stats structure which holds cell stats info
310  *
311  * \return 0 if there are no more items
312  * \return non-zero if there are more
313  */
314 int Rast_next_cell_stat(CELL * cat, long *count, struct Cell_stats *s)
315 {
316  int idx;
317 
318  /* first time report stats for null */
319  /* decided not to return stats for null in this function
320  static int null_reported = 0;
321  if(!null_reported && s->null_data_count > 0)
322  {
323  *count = s->null_data_count;
324  Rast_set_c_null_value(&cat,1);
325  null_reported = 1;
326  return 1;
327  }
328  */
329  if (s->N <= 0)
330  return 0;
331  for (;;) {
332  s->curoffset++;
333  if (s->curoffset >= NCATS) {
334  if (!next_node(s))
335  return 0;
336  s->curoffset = -1;
337  continue;
338  }
339  if ((*count = s->node[s->curp].count[s->curoffset])) {
340  idx = s->node[s->curp].idx;
341 
342  /*
343  if (idx < 0)
344  *cat = idx*NCATS + s->curoffset+1;
345  else
346  *cat = idx*NCATS + s->curoffset;
347  */
348  if (idx < 0)
349  *cat = -((-idx) << SHIFT) + s->curoffset + 1;
350  else
351  *cat = (idx << SHIFT) + s->curoffset;
352 
353  return 1;
354  }
355  }
356 }
357 
358 
359 /*!
360  * \brief Get number of null values.
361  *
362  * Get a number of null values from stats structure.
363  *
364  * Note: when reporting values which appear in a map using
365  * Rast_next_cell_stats(), to get stats for null, call
366  * Rast_get_stats_for_null_value() first, since Rast_next_cell_stats() does
367  * not report stats for null.
368  *
369  * \param count count
370  * \param s pointer to Cell_stats structure which holds cell stats info
371  */
372 void Rast_get_stats_for_null_value(long *count, const struct Cell_stats *s)
373 {
374  *count = s->null_data_count;
375 }
376 
377 /*!
378  * \brief Free cell stats structure
379  *
380  * The memory associated with structure <i>s</i> is freed. This
381  * routine may be called any time after calling Rast_init_cell_stats().
382  *
383  * \param s pointer to Cell_stats structure
384  */
386 {
387  int i;
388 
389  for (i = 1; i <= s->N; i++)
390  G_free(s->node[i].count);
391  G_free(s->node);
392 }
#define G_malloc(n)
Definition: defs/gis.h:112
real i
Definition: la.h:56
long null_data_count
Definition: raster.h:203
void Rast_init_cell_stats(struct Cell_stats *s)
Initialize cell stats.
Definition: cell_stats.c:39
int N
Definition: raster.h:201
int curp
Definition: raster.h:202
void G_free(void *)
Free allocated memory.
Definition: gis/alloc.c:149
int count
#define N
Definition: e_intersect.c:923
int Rast_rewind_cell_stats(struct Cell_stats *s)
Reset/rewind cell stats.
Definition: cell_stats.c:250
#define G_calloc(m, n)
Definition: defs/gis.h:113
#define SHIFT
Definition: cell_stats.c:20
void Rast_free_cell_stats(struct Cell_stats *s)
Free cell stats structure.
Definition: cell_stats.c:385
#define INCR
Definition: cell_stats.c:19
#define NODE
Definition: cell_stats.c:24
int Rast_update_cell_stats(const CELL *cell, int n, struct Cell_stats *s)
Add data to cell stats.
Definition: cell_stats.c:62
int Rast_find_cell_stat(CELL cat, long *count, const struct Cell_stats *s)
Random query of cell stats.
Definition: cell_stats.c:190
int Rast_next_cell_stat(CELL *cat, long *count, struct Cell_stats *s)
Retrieve sorted cell stats.
Definition: cell_stats.c:314
void Rast_get_stats_for_null_value(long *count, const struct Cell_stats *s)
Get number of null values.
Definition: cell_stats.c:372
int CELL
Definition: gis.h:602
#define G_realloc(p, n)
Definition: defs/gis.h:114
int curoffset
Definition: raster.h:204
struct Cell_stats::Cell_stats_node * node
int tlen
Definition: raster.h:200
#define Rast_is_c_null_value(cellVal)
Definition: defs/raster.h:416