1 2 /**************************************************************************** 3 * 4 * MODULE: r.describe 5 * 6 * AUTHOR(S): Michael Shapiro - CERL 7 * 8 * PURPOSE: Prints terse list of category values found in a raster 9 * map layer. 10 * 11 * COPYRIGHT: (C) 2006 by the GRASS Development Team 12 * 13 * This program is free software under the GNU General Public 14 * License (>=v2). Read the file COPYING that comes with GRASS 15 * for details. 16 * 17 ***************************************************************************/ 18 19 #include <grass/gis.h> 20 #include <grass/raster.h> 21 22 #define INCR 10 23 #define NCATS 100 24 25 typedef struct 26 { 27 int idx; 28 char cat[NCATS]; 29 int left; 30 int right; 31 } NODE; 32 33 static NODE *tree = 0; /* tree of values */ 34 static int tlen; /* allocated tree size */ 35 static int N; /* number of actual nodes in tree */ 36 37 plant_tree(void)38int plant_tree(void) 39 { 40 N = 0; 41 if (!tree) { 42 tlen = INCR; 43 tree = (NODE *) G_malloc(tlen * sizeof(NODE)); 44 } 45 46 return 0; 47 } 48 add_node_to_tree(register CELL cat)49int add_node_to_tree(register CELL cat) 50 { 51 register int p, q; 52 int idx, offset; 53 54 if (cat < 0) { 55 idx = -(-cat / NCATS) - 1; 56 offset = cat - idx * NCATS - 1; 57 } 58 else { 59 idx = cat / NCATS; 60 offset = cat - idx * NCATS; 61 } 62 if (offset < 0 || offset >= NCATS) 63 G_warning("cat %ld got offset %d - shouldn't happen", (long)cat, 64 offset); 65 /* first node is special case */ 66 if (N == 0) { 67 N = 1; 68 G_zero(tree[N].cat, sizeof(tree[N].cat)); 69 tree[N].idx = idx; 70 tree[N].cat[offset] = 1; 71 tree[N].left = 0; 72 tree[N].right = 0; 73 74 return 0; 75 } 76 77 q = 1; 78 while (q > 0) { 79 p = q; 80 if (tree[q].idx == idx) { 81 tree[q].cat[offset] = 1; 82 83 return 0; /* found */ 84 } 85 if (tree[q].idx > idx) 86 q = tree[q].left; /* go left */ 87 else 88 q = tree[q].right; /* go right */ 89 } 90 91 /* new node */ 92 N++; 93 94 /* grow the tree? */ 95 if (N >= tlen) 96 tree = (NODE *) G_realloc(tree, sizeof(NODE) * (tlen += INCR)); 97 98 /* add node to tree */ 99 G_zero(tree[N].cat, sizeof(tree[N].cat)); 100 tree[N].idx = idx; 101 tree[N].cat[offset] = 1; 102 tree[N].left = 0; 103 104 if (tree[p].idx > idx) { 105 tree[N].right = -p; /* create thread */ 106 tree[p].left = N; /* insert left */ 107 } 108 else { 109 tree[N].right = tree[p].right; /* copy right link/thread */ 110 tree[p].right = N; /* add right */ 111 } 112 113 return 0; 114 } 115 116 static int curp; 117 118 #ifdef COMMENT_OUT 119 static int curoffset; 120 #endif 121 first_node(void)122int first_node(void) 123 { 124 int q; 125 126 /* start at root and go all the way to the left */ 127 curp = 1; 128 while ((q = tree[curp].left)) 129 curp = q; 130 131 return 0; 132 } 133 next_node(void)134int next_node(void) 135 { 136 int q; 137 138 /* go to the right */ 139 curp = tree[curp].right; 140 141 if (curp == 0) /* no more */ 142 return 0; 143 144 if (curp < 0) { /* thread. stop here */ 145 curp = -curp; 146 return 1; 147 } 148 149 while ((q = tree[curp].left)) /* now go all the way left */ 150 curp = q; 151 152 return 1; 153 } 154 155 #ifdef COMMENT_OUT first_cat(CELL * cat)156int first_cat(CELL * cat) 157 { 158 first_node(); 159 curoffset = -1; 160 161 return next_cat(cat); 162 } 163 next_cat(CELL * cat)164int next_cat(CELL * cat) 165 { 166 int idx; 167 168 for (;;) { 169 curoffset++; 170 if (curoffset >= NCATS) { 171 if (!next_node()) 172 return 0; 173 curoffset = -1; 174 continue; 175 } 176 if (tree[curp].cat[curoffset]) { 177 idx = tree[curp].idx; 178 179 if (idx < 0) 180 *cat = idx * NCATS + curoffset + 1; 181 else 182 *cat = idx * NCATS + curoffset; 183 184 return 1; 185 } 186 } 187 188 return 0; 189 } 190 #endif 191