GRASS Programmer's Manual
6.4.2(2012)
|
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 /* first non-null node is special case */ 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) { /* if there are some non-null cells */ 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; /* go left */ 00129 else 00130 q = pnode->right; /* go right */ 00131 } 00132 if (q > 0) 00133 continue; /* found */ 00134 00135 /* new node */ 00136 N++; 00137 00138 /* grow the tree? */ 00139 if (N >= s->tlen) { 00140 node = 00141 (NODE *) G_realloc((char *)node, 00142 sizeof(NODE) * (s->tlen += INCR)); 00143 pnode = &node[p]; /* realloc moves node, must reassign pnode */ 00144 } 00145 00146 /* add node to tree */ 00147 init_node(new_node = &node[N], idx, offset); 00148 00149 if (pnode->idx > idx) { 00150 new_node->right = -p; /* create thread */ 00151 pnode->left = N; /* insert left */ 00152 } 00153 else { 00154 new_node->right = pnode->right; /* copy right link/thread */ 00155 pnode->right = N; /* add right */ 00156 } 00157 } /* while n-- > 0 */ 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 if (cat < 0) 00221 { 00222 idx = -(-cat/NCATS) - 1; 00223 offset = cat - idx*NCATS - 1; 00224 } 00225 else 00226 { 00227 idx = cat/NCATS; 00228 offset = cat - idx*NCATS; 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; /* go left */ 00248 else 00249 q = s->node[q].right; /* go 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 /* start at root and go all the way to the left */ 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 /* go to the right */ 00285 s->curp = s->node[s->curp].right; 00286 00287 if (s->curp == 0) /* no more */ 00288 return 0; 00289 00290 if (s->curp < 0) { /* thread. stop here */ 00291 s->curp = -(s->curp); 00292 return 1; 00293 } 00294 00295 while ((q = s->node[s->curp].left)) /* now go all the way 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 /* first time report stats for null */ 00343 /* decided not to return stats for null in this function 00344 static int null_reported = 0; 00345 if(!null_reported && s->null_data_count > 0) 00346 { 00347 *count = s->null_data_count; 00348 G_set_c_null_value(&cat,1); 00349 null_reported = 1; 00350 return 1; 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 if (idx < 0) 00368 *cat = idx*NCATS + s->curoffset+1; 00369 else 00370 *cat = idx*NCATS + s->curoffset; 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 }