source: branches/stable/NALIGNER/ali_pathmap.cxx

Last change on this file was 16766, checked in by westram, 8 years ago
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 9.6 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    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
24ALI_PATHMAP::~ALI_PATHMAP() {
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
36void 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,
45                       sizeof(ALI_TARRAY < ali_pathmap_up_pointer > *));
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
61void 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
92void ALI_PATHMAP::optimize(unsigned long x) {
93    // optimize the pathmap (the dynamic field with up_pointers)
94    unsigned long   l, counter;
95    ALI_TARRAY < ali_pathmap_up_pointer > *(*buffer)[];
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
125void ALI_PATHMAP::print() {
126    ali_pathmap_up_pointer up;
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
185ALI_TARRAY<ali_pathmap_up_pointer> *array1, *array2;
186
187void 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
223void 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
238void 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
272main() {
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------------------------------------------------------------ */
Note: See TracBrowser for help on using the repository browser.