source: tags/arb-6.0/NALIGNER/ali_pathmap.cxx

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