source: branches/port5/ALIV3/a3_ptree1.cxx

Last change on this file was 5438, checked in by westram, 17 years ago
  • char array indices
  • ambiguous elses
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 13.0 KB
Line 
1// -----------------------------------------------------------------------------
2//  Include-Dateien
3// -----------------------------------------------------------------------------
4
5#include <iostream>
6#include <cstdlib>
7
8#include "a3_basen.h"
9#include "a3_ptree.hxx"
10
11#include <inline.h>
12
13using std::cout;
14using std::hex;
15using std::dec;
16
17// -----------------------------------------------------------------------------
18static void CountAppearances ( str  seq,
19                               int *pos,
20                               int  num,
21                               int  off,
22                               int *anz )
23// -----------------------------------------------------------------------------
24{
25    if (!num)
26    {
27        int base;
28       
29        while ((base = *seq++) != 0)
30        {
31            int index = BIndex[base];
32
33            if ((index >= 0) &&
34                (index < BASENPUR)) anz[index]++;
35        }
36    }
37    else
38    {
39        while (num--)
40        {
41            int base = seq[pos[num] + off];
42           
43            if (base == 0) anz[BASEN] = 1;
44            else           anz[BIndex[base]]++;
45        }
46    }
47}
48
49// -----------------------------------------------------------------------------
50    static void FindAppearances ( int *list,
51                                  int  base,
52                                  int  anz,
53                                  str  seq,
54                                  int *pos,
55                                  int  num,
56                                  int  off )
57// -----------------------------------------------------------------------------
58{
59    int next  = 0,
60        count = 0;
61
62    if (!num)
63    {
64        num = strlen(seq);
65
66        while ((count < num) && (next < anz))
67        {
68            if (BIndex[safeCharIndex(seq[count])] == base) list[next++] = count;
69               
70            count++;
71        }
72    }
73    else
74        while ((count < num) && (next < anz))
75        {
76            if (base == BASEN)
77            {
78                if (!seq[pos[count]+ off]) list[next++] = pos[count];
79            }
80            else
81            {
82                if (BIndex[safeCharIndex(seq[pos[count]+ off])] == base) list[next++] = pos[count];
83            }
84
85            count++;
86        }
87}
88
89// -----------------------------------------------------------------------------
90//  Konstruktor zum Erstellen eines Positionsbaumes aus einer Sequenz
91// -----------------------------------------------------------------------------
92    PtNode::PtNode ( str  seq,
93                     int *pos,
94                     int  num,
95                     int  rec )
96// -----------------------------------------------------------------------------
97{
98    if (!seq) mask = (Mask)0, position = NULL, next = NULL;
99    else
100    {
101        int anz[BASEN + 1],
102            base;
103
104        mask     = (Mask)0;
105        position = NULL;
106        next     = NULL;
107       
108        memset(anz,0,(BASEN + 1) * sizeof(int));
109       
110        CountAppearances(seq,pos,num,rec,anz);
111
112        if (anz[ADENIN] > 0) {
113            if (anz[ADENIN] > 1)    mask = (Mask)(mask | N_ADENIN);
114            else                    mask = (Mask)(mask | P_ADENIN);
115        }
116        if (anz[CYTOSIN] > 0) {
117            if (anz[CYTOSIN] > 1)   mask = (Mask)(mask | N_CYTOSIN);
118            else                    mask = (Mask)(mask | P_CYTOSIN);
119        }
120        if (anz[GUANIN] > 0) {
121            if (anz[GUANIN] > 1)    mask = (Mask)(mask | N_GUANIN);
122            else                    mask = (Mask)(mask | P_GUANIN);
123        }
124        if (anz[URACIL] > 0) {
125            if (anz[URACIL] > 1)    mask = (Mask)(mask | N_URACIL);
126            else                    mask = (Mask)(mask | P_URACIL);
127        }
128        if (anz[ONE] > 0) {
129            if (anz[ONE] > 1)       mask = (Mask)(mask | N_ONE);
130            else                    mask = (Mask)(mask | P_ONE);
131        }
132        if (anz[ANY] > 0) {
133            if (anz[ANY] > 1)       mask = (Mask)(mask | N_ANY);
134            else                    mask = (Mask)(mask | P_ANY);
135        }
136        if (anz[BASEN])             mask = (Mask)(mask | P_FINISH);
137       
138        {
139            int panz = NumOfPos(),
140                nanz = NumOfNext();
141
142            if (panz) position = new int     [panz];
143            if (nanz) next     = new PtNode* [nanz];
144        }
145
146        for (base = 0;base < (BASEN + 1);base++)
147        {
148            switch (anz[base])
149            {
150                case 0:     break;
151                case 1:
152                {
153                    int  list,
154                         which = base;
155                    Mask tmp = P_ADENIN;
156                   
157                    while (which--) tmp = (Mask)(tmp * 2);
158                   
159                    FindAppearances(&list,base,1,seq,pos,num,rec);
160
161                    position[IndexOfPos(tmp)] = list;
162
163                    break;
164                }
165                default:
166                {
167                    int    *list  = new int [anz[base]],
168                            which = base,
169                            index;
170                    Mask    tmp   = N_ADENIN;
171                    PtNode *ptn;
172                       
173                    while (which--) tmp = (Mask)( tmp * 2);
174                       
175                    FindAppearances(list,base,anz[base],seq,pos,num,rec);
176
177                    index = IndexOfNext(tmp);
178                    ptn   = new PtNode(seq,list,anz[base],rec + 1);
179                    next[index] = ptn;
180
181                    delete list;
182                   
183                    break;
184                }
185            }
186        }
187    }
188}
189
190// -----------------------------------------------------------------------------
191//  Kopierkonstruktor
192// -----------------------------------------------------------------------------
193    PtNode::PtNode ( PtNode &node )
194// -----------------------------------------------------------------------------
195{
196    cout << "\nKopierkonstruktor(PtNode)\n";
197   
198    mask = node.mask;
199   
200    if (position)
201    {
202        int anz = node.NumOfPos();
203       
204        position = new int [anz];
205
206        memcpy(position,node.position,anz * sizeof(int));
207    }
208   
209    if (next)
210    {
211        int anz = node.NumOfNext();
212       
213        next = new PtNode* [anz];
214       
215        while (anz--)
216            if (node.next[anz]) next[anz] = new PtNode(*node.next[anz]);
217            else                next[anz] = NULL;
218    }
219}
220
221// -----------------------------------------------------------------------------
222//  Destruktor
223// -----------------------------------------------------------------------------
224    PtNode::~PtNode ( void )
225// -----------------------------------------------------------------------------
226{
227    if (position) delete position;
228   
229    if (next)
230    {
231        int anz = NumOfNext();
232       
233        while (anz--) if (next[anz]) delete next[anz];
234       
235        delete next;
236    }
237}
238
239// -----------------------------------------------------------------------------
240//  Anzahl der vorhandenen Positionen
241// -----------------------------------------------------------------------------
242    int PtNode::NumOfPos ( void )
243// -----------------------------------------------------------------------------
244{
245    int anz  = 0,
246        test = P_ADENIN;
247       
248    while (test <= P_FINISH)
249    {
250        if (mask & test) anz++;
251           
252        test *= 2;
253    }
254
255    return anz;
256}
257
258// -----------------------------------------------------------------------------
259//  Positionsindex einer Base
260// -----------------------------------------------------------------------------
261    int PtNode::IndexOfPos ( Mask base )
262// -----------------------------------------------------------------------------
263{
264    int index = INVALID;
265   
266    if ((base <= P_FINISH) && (mask & base))
267    {
268        int test = P_ADENIN;
269       
270        index = 0;
271       
272        while (test <= base)
273        {
274            if (mask & test) index++;
275           
276            test *= 2;
277        }
278
279        index--;
280    }
281
282    return index;
283}
284
285// -----------------------------------------------------------------------------
286//  Anzahl der vorhandenen Verzweigungen
287// -----------------------------------------------------------------------------
288    int PtNode::NumOfNext ( void )
289// -----------------------------------------------------------------------------
290{
291    int anz  = 0,
292        test = N_ADENIN;
293       
294    while (test < (N_ANY * 2))
295    {
296        if (mask & test) anz++;
297           
298        test *= 2;
299    }
300
301    return anz;
302}
303
304// -----------------------------------------------------------------------------
305//  Verzweigungsindex einer Base
306// -----------------------------------------------------------------------------
307    int PtNode::IndexOfNext ( Mask base )
308// -----------------------------------------------------------------------------
309{
310    int index = INVALID;
311   
312    if ((base >= N_ADENIN) && (base <= N_ANY) && (mask & base))
313    {
314        int test = N_ADENIN;
315       
316        index = 0;
317       
318        while (test <= base)
319        {
320            if (mask & test) index++;
321           
322            test *= 2;
323        }
324
325        index--;
326    }
327
328    return index;
329}
330
331// -----------------------------------------------------------------------------
332//  Ausgabefunktion fuer ein Knoten eines Positionsbaumes
333// -----------------------------------------------------------------------------
334    void PtNode::Dump ( void )
335// -----------------------------------------------------------------------------
336{
337    cout << "\nnode: " << this;
338    cout << "\nmask = 0x" << hex << mask << "\n";
339   
340    if (position)
341    {
342        int anz = NumOfPos(),
343            pos = 0;
344       
345        cout << "position[" << dec << anz << "] =";
346       
347        while (pos < anz) cout << " " << position[pos++];
348
349        cout << "\n";
350    }
351
352    if (next)
353    {
354        int anz = NumOfNext(),
355            pos = 0;
356       
357        cout << "next[" << dec << anz << "]:";
358       
359        while (pos < anz) cout << " " << next[pos++];
360
361        cout << "\n";
362
363        pos = 0;
364       
365        while (pos < anz) next[pos++]->Dump();
366    }
367}
368
369// -----------------------------------------------------------------------------
370//  Ausgabefunktion fuer einen Positionsbaum
371// -----------------------------------------------------------------------------
372    void PtNode::Show ( int  rec,
373                        int *where )
374// -----------------------------------------------------------------------------
375{
376    int  panz   = NumOfPos(),
377         nanz   = NumOfNext();
378    str  prefix = new char [rec * 3];
379
380    prefix[0] = 0;
381   
382    if (rec)
383    {
384        int count = 0;
385       
386        prefix[0] = 0;
387       
388        while (count < rec)
389            if (where[count++]) strcat(prefix,"|  ");
390            else                strcat(prefix,"   ");
391    }
392   
393    if (panz)
394    {
395        Base base  = ADENIN;
396        Mask which = P_ADENIN;
397       
398        while (which <= P_FINISH)
399        {
400            int index = IndexOfPos(which);
401
402            if ((index != INVALID) && (index < panz))
403            {
404                if (base == BASEN)
405                {
406                    if (!nanz && (index == (panz - 1)))
407                        cout << prefix << "\\- # " << position[index] << "\n";
408                    else
409                        cout << prefix << "|- # " << position[index] << "\n";
410                }
411                else
412                {
413                    if (!nanz && (index == (panz - 1)))
414                        cout << prefix << "\\- " << (char)BCharacter[base],
415                        cout << " " << position[index] << "\n";
416                    else
417                        cout << prefix << "|- " << (char)BCharacter[base],
418                        cout << " " << position[index] << "\n";
419                }
420            }
421           
422            which = (Mask)(which * 2);
423            base  = (Base)(base  + 1);
424        }
425    }
426
427    if (nanz)
428    {
429        Base  base     = ADENIN;
430        Mask  which    = N_ADENIN;
431        int  *wherenew = new int [rec + 1];
432
433        memcpy(wherenew,where,rec * sizeof(int));
434
435        while (which <= N_ANY)
436        {
437            int index = IndexOfNext(which);
438
439            if ((index != INVALID) && (index < nanz))
440            {
441                if (base == BASEN)
442                {
443                    if (index == (nanz - 1))
444                        cout << prefix << "\\- #\n",
445                        wherenew[rec] = 0;
446                    else
447                        cout << prefix << "|- #\n",
448                        wherenew[rec] = 1;
449                }
450                else
451                {
452                    if (index == (nanz - 1))
453                        cout << prefix << "\\- " << (char)BCharacter[base] << "\n",
454                        wherenew[rec] = 0;
455                    else
456                        cout << prefix << "|- " << (char)BCharacter[base] << "\n",
457                        wherenew[rec] = 1;
458                }
459               
460                next[index]->Show(rec + 1,wherenew);
461            }
462           
463            which = (Mask)(which * 2);
464            base  = (Base)(base  + 1);
465        }
466
467        delete wherenew;
468    }
469
470    delete prefix;
471}
Note: See TracBrowser for help on using the repository browser.