GRASS Programmer's Manual  6.4.1(2011)
cell_stats.c
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     /* 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 }
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Defines