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 (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) return 1;
00077
00078 node = s->node;
00079
00080
00081 if ((N = s->N) == 0)
00082 {
00083 cat = *cell++;
00084 while(G_is_c_null_value(&cat))
00085 {
00086 s->null_data_count++;
00087 cat = *cell++;
00088 n--;
00089 }
00090 if(n>0)
00091 {
00092 N = 1;
00093 if (cat < 0)
00094 {
00095 idx = -((-cat) >> SHIFT) - 1;
00096 offset = cat + ((-idx) << SHIFT) - 1;
00097 }
00098 else
00099 {
00100 idx = cat >> SHIFT;
00101 offset = cat - (idx << SHIFT);
00102 }
00103 fflush(stderr);
00104 init_node (&node[1], idx, offset);
00105 node[1].right = 0;
00106 n--;
00107 }
00108 }
00109 while (n-- > 0)
00110 {
00111 cat = *cell++;
00112 if(G_is_c_null_value(&cat))
00113 {
00114 s->null_data_count++;
00115 continue;
00116 }
00117 if (cat < 0)
00118 {
00119 idx = -((-cat) >> SHIFT) - 1;
00120 offset = cat + ((-idx) << SHIFT) - 1;
00121 }
00122 else
00123 {
00124 idx = cat >> SHIFT;
00125 offset = cat - (idx << SHIFT);
00126 }
00127
00128 q = 1;
00129 while (q > 0)
00130 {
00131 pnode = &node[p = q];
00132 if (pnode->idx == idx)
00133 {
00134 pnode->count[offset]++;
00135 break;
00136 }
00137 if (pnode->idx > idx)
00138 q = pnode->left;
00139 else
00140 q = pnode->right;
00141 }
00142 if (q > 0)
00143 continue;
00144
00145
00146 N++;
00147
00148
00149 if (N >= s->tlen)
00150 {
00151 node = (NODE *) G_realloc ((char *) node, sizeof(NODE) * (s->tlen += INCR));
00152 pnode = &node[p];
00153 }
00154
00155
00156 init_node (new_node = &node[N], idx, offset);
00157
00158 if (pnode->idx > idx)
00159 {
00160 new_node->right = -p;
00161 pnode->left = N;
00162 }
00163 else
00164 {
00165 new_node->right = pnode->right;
00166 pnode->right = N;
00167 }
00168 }
00169 s->N = N;
00170 s->node = node;
00171
00172 return 0;
00173 }
00174
00175 static int init_node(NODE *node,int idx,int offset)
00176 {
00177 register long *count;
00178 register int i;
00179
00180 count = node->count = (long *) G_calloc (i = NCATS, sizeof(long));
00181 while(i--)
00182 *count++ = 0;
00183 node->idx = idx;
00184 node->count[offset] = 1;
00185 node->left = 0;
00186
00187 return 0;
00188 }
00189
00190
00215 int G_find_cell_stat (
00216 CELL cat,
00217 long *count,
00218 struct Cell_stats *s)
00219 {
00220 register int q;
00221 register int idx;
00222 int offset;
00223
00224 *count = 0;
00225 if(G_is_c_null_value(&cat))
00226 {
00227 *count = s->null_data_count;
00228 return (*count != 0);
00229 }
00230
00231 if (s->N <= 0)
00232 return 0;
00233
00234
00235
00236
00237
00238
00239
00240
00241
00242
00243
00244
00245
00246 if (cat < 0)
00247 {
00248 idx = -((-cat) >> SHIFT) - 1;
00249 offset = cat + ((-idx) << SHIFT) - 1;
00250 }
00251 else
00252 {
00253 idx = cat >> SHIFT;
00254 offset = cat - (idx << SHIFT);
00255 }
00256
00257 q = 1;
00258 while (q > 0)
00259 {
00260 if (s->node[q].idx == idx)
00261 {
00262 *count = s->node[q].count[offset];
00263 return (*count != 0);
00264 }
00265 if (s->node[q].idx > idx)
00266 q = s->node[q].left;
00267 else
00268 q = s->node[q].right;
00269 }
00270 return 0;
00271 }
00272
00273
00284 int G_rewind_cell_stats (struct Cell_stats *s)
00285 {
00286 int q;
00287
00288 if (s->N <= 0)
00289 return 1;
00290
00291 s->curp = 1;
00292 while ((q = s->node[s->curp].left))
00293 s->curp = q;
00294 s->curoffset = -1;
00295
00296 return 0;
00297 }
00298
00299 static int next_node (struct Cell_stats *s)
00300 {
00301 int q;
00302
00303
00304 s->curp = s->node[s->curp].right;
00305
00306 if (s->curp == 0)
00307 return 0;
00308
00309 if (s->curp < 0)
00310 {
00311 s->curp = -(s->curp) ;
00312 return 1;
00313 }
00314
00315 while ((q = s->node[s->curp].left))
00316 s->curp = q;
00317
00318 return 1;
00319 }
00320
00321
00358 int G_next_cell_stat (
00359 CELL *cat,
00360 long *count,
00361 struct Cell_stats *s)
00362 {
00363 int idx;
00364
00365
00366
00367
00368
00369
00370
00371
00372
00373
00374
00375
00376 if (s->N <= 0)
00377 return 0;
00378 for(;;)
00379 {
00380 s->curoffset++;
00381 if (s->curoffset >= NCATS)
00382 {
00383 if(!next_node(s))
00384 return 0;
00385 s->curoffset = -1;
00386 continue;
00387 }
00388 if ((*count = s->node[s->curp].count[s->curoffset]))
00389 {
00390 idx = s->node[s->curp].idx;
00391
00392
00393
00394
00395
00396
00397
00398 if (idx < 0)
00399 *cat = -((-idx)<<SHIFT) + s->curoffset+1;
00400 else
00401 *cat = (idx<<SHIFT) + s->curoffset;
00402
00403 return 1;
00404 }
00405 }
00406 }
00407
00408
00422 int G_get_stats_for_null_value (long *count, struct Cell_stats *s)
00423 {
00424 *count = s->null_data_count;
00425 return 1;
00426 }
00427
00428
00439 int G_free_cell_stats (struct Cell_stats *s)
00440 {
00441 int i;
00442
00443 for (i = 1; i <= s->N; i++)
00444 G_free (s->node[i].count);
00445 G_free (s->node);
00446
00447 return 0;
00448 }