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 (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 /* first non-null node is special case */
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) /* if there are some non-null cells */
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;             /* go left */
00139             else
00140                 q = pnode->right;            /* go right */
00141         }
00142         if (q > 0)
00143             continue;                           /* found */
00144 
00145     /* new node */
00146         N++;
00147 
00148     /* grow the tree? */
00149         if (N >= s->tlen)
00150         {
00151             node = (NODE *) G_realloc ((char *) node, sizeof(NODE) * (s->tlen += INCR));
00152             pnode = &node[p]; /* realloc moves node, must reassign pnode */
00153         }
00154 
00155     /* add node to tree */
00156         init_node (new_node = &node[N], idx, offset);
00157 
00158         if (pnode->idx > idx)
00159         {
00160             new_node->right = -p;            /* create thread */
00161             pnode->left  = N;                /* insert left */
00162         }
00163         else
00164         {
00165             new_node->right = pnode->right; /* copy right link/thread */
00166             pnode->right = N;                /* add right */
00167         }
00168     } /* while n-- > 0 */
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     if (cat < 0)
00236     {
00237         idx = -(-cat/NCATS) - 1;
00238         offset = cat - idx*NCATS - 1;
00239     }
00240     else
00241     {
00242         idx = cat/NCATS;
00243         offset = cat - idx*NCATS;
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;             /* go left */
00267         else
00268             q = s->node[q].right;            /* go 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 /* start at root and go all the way to the left */
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 /* go to the right */
00304     s->curp = s->node[s->curp].right;
00305 
00306     if (s->curp == 0)          /* no more */
00307         return 0;
00308 
00309     if (s->curp < 0)           /* thread. stop here */
00310     {
00311         s->curp = -(s->curp) ;
00312         return 1;
00313     }
00314 
00315     while ((q = s->node[s->curp].left))   /* now go all the way 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     /* first time report stats for null */
00366     /* decided not to return stats for null in this function 
00367     static int null_reported = 0;
00368     if(!null_reported && s->null_data_count > 0)
00369     {
00370        *count = s->null_data_count;
00371        G_set_c_null_value(&cat,1);
00372        null_reported = 1;
00373        return 1;
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             if (idx < 0)
00394                 *cat = idx*NCATS + s->curoffset+1;
00395             else
00396                 *cat = idx*NCATS + s->curoffset;
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 }

Generated on Fri Nov 21 11:02:17 2008 for GRASS by  doxygen 1.5.1