ARB
ali_pathmap.cxx
Go to the documentation of this file.
1 // =============================================================== //
2 // //
3 // File : ali_pathmap.cxx //
4 // Purpose : //
5 // //
6 // Institute of Microbiology (Technical University Munich) //
7 // http://www.arb-home.de/ //
8 // //
9 // =============================================================== //
10 
11 #include "ali_pathmap.hxx"
12 
13 ALI_PATHMAP::ALI_PATHMAP(unsigned long w, unsigned long h) {
14  width = w;
15  height = h;
16  height_real = (h / 2) + 1;
17 
18  pathmap = (unsigned char **) CALLOC((unsigned int) (height_real * w), sizeof(unsigned char));
19  up_pointers = (ALI_TARRAY < ali_pathmap_up_pointer > ****) CALLOC((unsigned int) w, sizeof(ALI_TARRAY < ali_pathmap_up_pointer > *));
20  optimized = (unsigned char **) CALLOC((unsigned int) ((w / 8) + 1), sizeof(unsigned char));
21  ali_out_of_memory_if(!pathmap || !up_pointers || !optimized);
22 }
23 
25  free(pathmap);
26  if (up_pointers) {
27  for (unsigned long l = 0; l < width; l++)
28  if ((*up_pointers)[l])
29  free((*up_pointers)[l]);
30  free(up_pointers);
31  }
32  free(optimized);
33 }
34 
35 
36 void ALI_PATHMAP::set(unsigned long x, unsigned long y, unsigned char val, ALI_TARRAY < ali_pathmap_up_pointer > *up_pointer) {
37  // Set a value in the pathmap
38  if (x >= width || y >= height)
39  ali_fatal_error("Out of range", "ALI_PATHMAP::set()");
40 
41  if (val & ALI_LUP) {
42  if (!(*up_pointers)[x]) {
43  (*up_pointers)[x] = (ALI_TARRAY < ali_pathmap_up_pointer > **)
44  CALLOC((unsigned int) height,
46  ali_out_of_memory_if(!(*up_pointers)[x]);
47  (*optimized)[x / 8] &= (unsigned char) ~(0x01 << (7 - (x % 8)));
48  }
49  if ((*optimized)[x / 8] & (0x01 << (7 - (x % 8))))
50  ali_fatal_error("Try to change optimized value", "ALI_PATHMAP::set()");
51 
52  (*up_pointers)[x][y] = up_pointer;
53  }
54  if (y & 0x01)
55  val &= 0x0f;
56  else
57  val <<= 4;
58  (*pathmap)[x * height_real + (y >> 1)] |= val;
59 }
60 
61 void ALI_PATHMAP::get(unsigned long x, unsigned long y, unsigned char *val, ALI_TARRAY < ali_pathmap_up_pointer > **up_pointer) {
62  // Get a value from the pathmap
63 
64  *up_pointer = NULp;
65  if (x >= width || y >= height) {
66  ali_fatal_error("Out of range", "ALI_PATHMAP::get()");
67  }
68  if (y & 0x01)
69  *val = (*pathmap)[x * height_real + (y >> 1)] & 0x0f;
70  else
71  *val = (*pathmap)[x * height_real + (y >> 1)] >> 4;
72 
73  if (*val & ALI_LUP) {
74  if ((*optimized)[x / 8] & (0x01 << (7 - (x % 8)))) {
75  unsigned long l;
76  unsigned long counter;
77  for (l = 0, counter = 0; l < y / 2; l++) {
78  if ((*pathmap)[x * height_real + l] & ALI_LUP)
79  counter++;
80  if (((*pathmap)[x * height_real + l] >> 4) & ALI_LUP)
81  counter++;
82  }
83  if (y & 0x01 && ((*pathmap)[x * height_real + l] >> 4) & ALI_LUP)
84  counter++;
85  *up_pointer = (*up_pointers)[x][counter];
86  } else
87  *up_pointer = (*up_pointers)[x][y];
88  }
89 }
90 
91 
92 void ALI_PATHMAP::optimize(unsigned long x) {
93  // optimize the pathmap (the dynamic field with up_pointers)
94  unsigned long l, counter;
96 
97  if (!(*up_pointers)[x] || (*optimized)[x / 8] & (0x01 << (7 - (x % 8))))
98  return;
99 
100  for (l = 0, counter = 0; l < height; l++)
101  if ((*up_pointers)[x][l])
102  counter++;
103 
104  if (counter == 0) {
105  free((*up_pointers)[x]);
106  (*up_pointers)[x] = NULp;
107  return;
108  }
109  (*optimized)[x / 8] |= (unsigned char) (0x01 << (7 - (x % 8)));
110 
111  buffer = (ALI_TARRAY < ali_pathmap_up_pointer > *(*)[])
112  CALLOC((unsigned int) counter + 1, sizeof(ALI_TARRAY < ali_pathmap_up_pointer > *));
113  ali_out_of_memory_if(!buffer);
114 
115  for (l = 0, counter = 0; l < height; l++)
116  if ((*up_pointers)[x][l])
117  (*buffer)[counter++] = (*up_pointers)[x][l];
118  (*buffer)[counter] = NULp;
119 
120  free((*up_pointers)[x]);
121  (*up_pointers)[x] = (ALI_TARRAY < ali_pathmap_up_pointer > **) buffer;
122 }
123 
124 
127  unsigned long x, y, i;
128  unsigned char val;
129 
130  printf("PATH_MATRIX:\n");
131  for (y = 0; y < height; y++) {
132  for (x = 0; x < width; x++) {
133  if (y & 0x01)
134  val = (*pathmap)[x * height_real + y / 2] & 0x0f;
135  else
136  val = (*pathmap)[x * height_real + y / 2] >> 4;
137  printf("%d ", val);
138  }
139  printf("\n");
140  }
141 
142  printf("UP_POINTERS:\n");
143  for (x = 0; x < width; x++) {
144  if ((*up_pointers)[x]) {
145  printf("%3ld : ", x);
146  if ((*optimized)[x / 8] & 0x01 << (7 - (x % 8))) {
147  for (y = 0; (*up_pointers)[x][y]; y++) {
148  printf("(");
149  for (i = 0; i < (*up_pointers)[x][y]->size(); i++) {
150  up = (*up_pointers)[x][y]->get(i);
151  printf("%ld:%d ", up.start, up.operation);
152  }
153  printf(") ");
154  }
155  }
156  else {
157  for (y = 0; y < height; y++) {
158  printf("(");
159  if ((*up_pointers)[x][y]) {
160  for (i = 0; i < (*up_pointers)[x][y]->size(); i++) {
161  up = (*up_pointers)[x][y]->get(i);
162  printf("%ld:%d ", up.start, up.operation);
163  }
164  }
165  printf(") ");
166  }
167  }
168  printf("\n");
169  }
170  }
171 }
172 
173 
174 
175 
176 
177 
178 /* ------------------------------------------------------------
179  *
180  * TEST PART
181  *
182 
183 #include "ali_tarray.hxx"
184 
185 ALI_TARRAY<ali_pathmap_up_pointer> *array1, *array2;
186 
187 void init_pathmap(ALI_PATHMAP *pmap) {
188 
189  pmap->set(0,0,ALI_LEFT);
190  pmap->set(0,1,ALI_DIAG);
191  pmap->set(0,2,ALI_UP);
192  pmap->set(0,3,ALI_LUP,array1);
193  pmap->set(0,4,ALI_LEFT);
194  pmap->set(0,5,ALI_DIAG);
195  pmap->set(0,6,ALI_UP);
196  pmap->set(0,7,ALI_LUP,array2);
197 
198 
199  pmap->set(1,0,ALI_LEFT|ALI_DIAG);
200  pmap->set(1,1,ALI_LEFT|ALI_UP);
201  pmap->set(1,2,ALI_LEFT|ALI_LUP,array2);
202  pmap->set(1,3,ALI_LEFT|ALI_DIAG);
203  pmap->set(1,4,ALI_LEFT|ALI_UP);
204  pmap->set(1,5,ALI_LEFT|ALI_LUP,array1);
205 
206  pmap->set(30,23,ALI_LEFT);
207  pmap->set(30,24,ALI_DIAG);
208  pmap->set(30,25,ALI_UP);
209  pmap->set(30,26,ALI_LUP,array1);
210  pmap->set(30,27,ALI_LEFT);
211  pmap->set(30,28,ALI_DIAG);
212  pmap->set(30,29,ALI_UP);
213  pmap->set(30,30,ALI_LUP,array2);
214 
215  pmap->set(29,25,ALI_LEFT|ALI_DIAG);
216  pmap->set(29,26,ALI_LEFT|ALI_UP);
217  pmap->set(29,27,ALI_LEFT|ALI_LUP,array2);
218  pmap->set(29,28,ALI_LEFT|ALI_DIAG);
219  pmap->set(29,29,ALI_LEFT|ALI_UP);
220  pmap->set(29,30,ALI_LEFT|ALI_LUP,array1);
221 }
222 
223 void print_array(ALI_TARRAY<ali_pathmap_up_pointer> *array) {
224  unsigned long l;
225  ali_pathmap_up_pointer up;
226 
227  if (array == 0)
228  return;
229 
230  printf("<");
231  for (l = 0; l < array->size(); l++) {
232  up = array->get(l);
233  printf("%d:%d ",up.start,up.operation);
234  }
235  printf(">");
236 }
237 
238 void check_pathmap(ALI_PATHMAP *pmap) {
239  unsigned long l;
240 
241  unsigned char val;
242  ALI_TARRAY<ali_pathmap_up_pointer> *array_of_pointer;
243 
244  printf("******************\n");
245  for (l = 0; l < 8; l++) {
246  pmap->get(0,l,&val,&array_of_pointer);
247  printf("(0,%d) %d ",l,val);
248  print_array(array_of_pointer);
249  printf("\n");
250  }
251  for (l = 0; l < 6; l++) {
252  pmap->get(1,l,&val,&array_of_pointer);
253  printf("(1,%d) %d ",l,val);
254  print_array(array_of_pointer);
255  printf("\n");
256  }
257  for (l = 23; l < 31; l++) {
258  pmap->get(29,l,&val,&array_of_pointer);
259  printf("(29,%d) %d ",l,val);
260  print_array(array_of_pointer);
261  printf("\n");
262  }
263  for (l = 25; l < 31; l++) {
264  pmap->get(30,l,&val,&array_of_pointer);
265  printf("(30,%d) %d ",l,val);
266  print_array(array_of_pointer);
267  printf("\n");
268  }
269 }
270 
271 
272 main() {
273  ali_pathmap_up_pointer up;
274  ALI_PATHMAP *pmap;
275 
276  array1 = new ALI_TARRAY<ali_pathmap_up_pointer>(3);
277  up.start = 1; up.operation = ALI_LEFT;
278  array1->set(0,up);
279  up.start = 3; up.operation = ALI_DIAG;
280  array1->set(1,up);
281  up.start = 5; up.operation = ALI_LEFT;
282  array1->set(2,up);
283  array2 = new ALI_TARRAY<ali_pathmap_up_pointer>(4);
284  up.start = 2; up.operation = ALI_DIAG;
285  array2->set(0,up);
286  up.start = 4; up.operation = ALI_LEFT;
287  array2->set(1,up);
288  up.start = 8; up.operation = ALI_DIAG;
289  array2->set(2,up);
290  up.start = 16; up.operation = ALI_LEFT;
291  array2->set(3,up);
292 
293  pmap = new ALI_PATHMAP(31,31);
294 
295  init_pathmap(pmap);
296  pmap->print();
297  check_pathmap(pmap);
298  pmap->optimize(0);
299  pmap->optimize(1);
300  pmap->optimize(30);
301  pmap->optimize(29);
302  pmap->print();
303  check_pathmap(pmap);
304 }
305 
306 ------------------------------------------------------------ */
void ali_out_of_memory_if(bool cond)
Definition: ali_misc.hxx:52
static char * y[maxsp+1]
void get(unsigned long x, unsigned long y, unsigned char *val, ALI_TARRAY< ali_pathmap_up_pointer > **up_pointer)
Definition: ali_pathmap.cxx:61
void set(unsigned long x, unsigned long y, unsigned char val, ALI_TARRAY< ali_pathmap_up_pointer > *up_pointer=NULp)
Definition: ali_pathmap.cxx:36
ALI_PATHMAP(unsigned long width, unsigned long height)
Definition: ali_pathmap.cxx:13
void * CALLOC(long i, long j)
Definition: ali_misc.hxx:56
unsigned char operation
Definition: ali_pathmap.hxx:27
void optimize(unsigned long x)
Definition: ali_pathmap.cxx:92
void ali_fatal_error(const char *message, const char *func)
Definition: ali_main.cxx:85
#define NULp
Definition: cxxforward.h:97
#define ALI_LUP
Definition: ali_pathmap.hxx:22