Go to the documentation of this file.00001 #include <grass/gis.h>
00002 #include <stdlib.h>
00003
00004 #define INCR 10
00005 #define SHIFT 6
00006
00007 static int NCATS = 1 << SHIFT;
00008
00009 #define NODE struct Cell_stats_node
00010
00011 static int next_node(struct Cell_stats *);
00012 static int init_node(NODE *, int, int);
00013
00014
00034 int G_init_cell_stats(struct Cell_stats *s)
00035 {
00036 s->N = 0;
00037 s->tlen = INCR;
00038 s->node = (NODE *) G_malloc(s->tlen * sizeof(NODE));
00039 s->null_data_count = 0;
00040
00041 return 1;
00042 }
00043
00044
00067 int G_update_cell_stats(const CELL * cell, int n, struct Cell_stats *s)
00068 {
00069 CELL cat;
00070 register int p, q;
00071 int idx, offset;
00072 int N;
00073 register NODE *node, *pnode;
00074 register NODE *new_node;
00075
00076 if (n <= 0)
00077 return 1;
00078
00079 node = s->node;
00080
00081
00082 if ((N = s->N) == 0) {
00083 cat = *cell++;
00084 while (G_is_c_null_value(&cat)) {
00085 s->null_data_count++;
00086 cat = *cell++;
00087 n--;
00088 }
00089 if (n > 0) {
00090 N = 1;
00091 if (cat < 0) {
00092 idx = -((-cat) >> SHIFT) - 1;
00093 offset = cat + ((-idx) << SHIFT) - 1;
00094 }
00095 else {
00096 idx = cat >> SHIFT;
00097 offset = cat - (idx << SHIFT);
00098 }
00099 fflush(stderr);
00100 init_node(&node[1], idx, offset);
00101 node[1].right = 0;
00102 n--;
00103 }
00104 }
00105 while (n-- > 0) {
00106 cat = *cell++;
00107 if (G_is_c_null_value(&cat)) {
00108 s->null_data_count++;
00109 continue;
00110 }
00111 if (cat < 0) {
00112 idx = -((-cat) >> SHIFT) - 1;
00113 offset = cat + ((-idx) << SHIFT) - 1;
00114 }
00115 else {
00116 idx = cat >> SHIFT;
00117 offset = cat - (idx << SHIFT);
00118 }
00119
00120 q = 1;
00121 while (q > 0) {
00122 pnode = &node[p = q];
00123 if (pnode->idx == idx) {
00124 pnode->count[offset]++;
00125 break;
00126 }
00127 if (pnode->idx > idx)
00128 q = pnode->left;
00129 else
00130 q = pnode->right;
00131 }
00132 if (q > 0)
00133 continue;
00134
00135
00136 N++;
00137
00138
00139 if (N >= s->tlen) {
00140 node =
00141 (NODE *) G_realloc((char *)node,
00142 sizeof(NODE) * (s->tlen += INCR));
00143 pnode = &node[p];
00144 }
00145
00146
00147 init_node(new_node = &node[N], idx, offset);
00148
00149 if (pnode->idx > idx) {
00150 new_node->right = -p;
00151 pnode->left = N;
00152 }
00153 else {
00154 new_node->right = pnode->right;
00155 pnode->right = N;
00156 }
00157 }
00158 s->N = N;
00159 s->node = node;
00160
00161 return 0;
00162 }
00163
00164 static int init_node(NODE * node, int idx, int offset)
00165 {
00166 register long *count;
00167 register int i;
00168
00169 count = node->count = (long *)G_calloc(i = NCATS, sizeof(long));
00170 while (i--)
00171 *count++ = 0;
00172 node->idx = idx;
00173 node->count[offset] = 1;
00174 node->left = 0;
00175
00176 return 0;
00177 }
00178
00179
00204 int G_find_cell_stat(CELL cat, long *count, const struct Cell_stats *s)
00205 {
00206 register int q;
00207 register int idx;
00208 int offset;
00209
00210 *count = 0;
00211 if (G_is_c_null_value(&cat)) {
00212 *count = s->null_data_count;
00213 return (*count != 0);
00214 }
00215
00216 if (s->N <= 0)
00217 return 0;
00218
00219
00220
00221
00222
00223
00224
00225
00226
00227
00228
00229
00230
00231 if (cat < 0) {
00232 idx = -((-cat) >> SHIFT) - 1;
00233 offset = cat + ((-idx) << SHIFT) - 1;
00234 }
00235 else {
00236 idx = cat >> SHIFT;
00237 offset = cat - (idx << SHIFT);
00238 }
00239
00240 q = 1;
00241 while (q > 0) {
00242 if (s->node[q].idx == idx) {
00243 *count = s->node[q].count[offset];
00244 return (*count != 0);
00245 }
00246 if (s->node[q].idx > idx)
00247 q = s->node[q].left;
00248 else
00249 q = s->node[q].right;
00250 }
00251 return 0;
00252 }
00253
00254
00265 int G_rewind_cell_stats(struct Cell_stats *s)
00266 {
00267 int q;
00268
00269 if (s->N <= 0)
00270 return 1;
00271
00272 s->curp = 1;
00273 while ((q = s->node[s->curp].left))
00274 s->curp = q;
00275 s->curoffset = -1;
00276
00277 return 0;
00278 }
00279
00280 static int next_node(struct Cell_stats *s)
00281 {
00282 int q;
00283
00284
00285 s->curp = s->node[s->curp].right;
00286
00287 if (s->curp == 0)
00288 return 0;
00289
00290 if (s->curp < 0) {
00291 s->curp = -(s->curp);
00292 return 1;
00293 }
00294
00295 while ((q = s->node[s->curp].left))
00296 s->curp = q;
00297
00298 return 1;
00299 }
00300
00301
00338 int G_next_cell_stat(CELL * cat, long *count, struct Cell_stats *s)
00339 {
00340 int idx;
00341
00342
00343
00344
00345
00346
00347
00348
00349
00350
00351
00352
00353 if (s->N <= 0)
00354 return 0;
00355 for (;;) {
00356 s->curoffset++;
00357 if (s->curoffset >= NCATS) {
00358 if (!next_node(s))
00359 return 0;
00360 s->curoffset = -1;
00361 continue;
00362 }
00363 if ((*count = s->node[s->curp].count[s->curoffset])) {
00364 idx = s->node[s->curp].idx;
00365
00366
00367
00368
00369
00370
00371
00372 if (idx < 0)
00373 *cat = -((-idx) << SHIFT) + s->curoffset + 1;
00374 else
00375 *cat = (idx << SHIFT) + s->curoffset;
00376
00377 return 1;
00378 }
00379 }
00380 }
00381
00382
00396 int G_get_stats_for_null_value(long *count, const struct Cell_stats *s)
00397 {
00398 *count = s->null_data_count;
00399 return 1;
00400 }
00401
00402
00413 int G_free_cell_stats(struct Cell_stats *s)
00414 {
00415 int i;
00416
00417 for (i = 1; i <= s->N; i++)
00418 G_free(s->node[i].count);
00419 G_free(s->node);
00420
00421 return 0;
00422 }