source: branches/port5/ALIV3/a3_ptree2.cxx

Last change on this file was 5828, checked in by westram, 17 years ago
  • changed ulong→ULONG and uint→UINT (ulong/uint are missing under OSX)
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 19.0 KB
Line 
1// -----------------------------------------------------------------------------
2//  Include-Dateien
3// -----------------------------------------------------------------------------
4
5#include <iostream>
6#include <fstream>
7#include <cstdlib>
8
9#include "a3_basen.h"
10#include "a3_ptree.hxx"
11
12#include <inline.h>
13
14using std::cout;
15
16// -----------------------------------------------------------------------------
17static int int_compare ( const void *a,
18                         const void *b )
19// -----------------------------------------------------------------------------
20{
21    int result = 0,
22        diff   = *(int*)a - *(int*)b;
23   
24    if      (diff < 0) result = -1;
25    else if (diff > 0) result =  1;
26
27    return result;
28}
29
30// -----------------------------------------------------------------------------
31    static void SortIntArray ( int *array,
32                               int *anz )
33// -----------------------------------------------------------------------------
34{
35    qsort(array,*anz,sizeof(int),int_compare);
36
37    int source;
38    int dest = 1;
39    int lastelem = array[0];
40
41    for (source = 1; source < *anz; source++) {
42        if (array[source] != lastelem){
43            array[dest++] = lastelem = array[source];
44        }
45    }
46    *anz = dest;
47}
48
49// -----------------------------------------------------------------------------
50//  Liefert die Anzahl aller Positionen unterhalb eines bestimmten Knotens
51// -----------------------------------------------------------------------------
52    static int CountLeaves ( PtNode &node )
53// -----------------------------------------------------------------------------
54{
55    int panz = node.NumOfPos(),
56        nanz = node.NumOfNext();
57
58    while (nanz--) panz += CountLeaves(*node.next[nanz]);
59
60    return panz;
61}
62
63// -----------------------------------------------------------------------------
64//  Sucht alle Positionen unterhalb eines bestimmten Knotens
65// -----------------------------------------------------------------------------
66    static int GetLeaves ( PtNode &node,
67                           int    *field )
68// -----------------------------------------------------------------------------
69{
70    int panz  = node.NumOfPos(),
71        nanz  = node.NumOfNext(),
72        count = 0;
73
74    while (count < panz) {
75        field[count] = node.position[count];
76        count++;
77    }
78
79    while (nanz--) panz += GetLeaves(*node.next[nanz],&field[panz]);
80
81    return panz;
82}
83
84// -----------------------------------------------------------------------------
85//  Sucht alle Positionen unterhalb eines bestimmten Knotens
86// -----------------------------------------------------------------------------
87    static int *FindLeaves ( PtNode &node,
88                             int    *anz )
89// -----------------------------------------------------------------------------
90{
91    int *field = NULL;
92
93    if (((*anz = CountLeaves(node)) > 0) &&
94        ((field = new int [*anz])   != NULL)) GetLeaves(node,field);
95   
96    return field;
97}
98
99// -----------------------------------------------------------------------------
100//  Konstruktor zum Erzeugen einer leeren Instanz der Klasse Postree
101// -----------------------------------------------------------------------------
102    Postree::Postree ( void ) : sequence ()
103// -----------------------------------------------------------------------------
104{
105    topnode = NULL;
106}
107
108// -----------------------------------------------------------------------------
109//  Konstruktor zum Erzeugen einer Instanz der
110//  Klasse Postree aus einer vorgegebenen Sequenz
111// -----------------------------------------------------------------------------
112    Postree::Postree ( str seq2 ) : sequence ( seq2 )
113// -----------------------------------------------------------------------------
114{
115    str seq = sequence.Compressed();
116   
117    if (seq) topnode = new PtNode(seq,NULL,0,0), delete seq;
118}
119
120// -----------------------------------------------------------------------------
121//  Konstruktor zum Erzeugen einer Instanz der Klasse Postree aus einer
122//  zufaellig besetzten Instanz der Klasse Sequenz mit vorgebener Sequenzlaenge
123// -----------------------------------------------------------------------------
124    Postree::Postree ( UINT len ) : sequence ( len )
125// -----------------------------------------------------------------------------
126{
127    str seq = sequence.Compressed();
128   
129    if (seq) topnode = new PtNode(seq,NULL,0,0), delete seq;
130}
131
132// -----------------------------------------------------------------------------
133//  Konstruktor zum Erzeugen einer leeren Instanz der Klasse Postree
134//  aus einer Instanz der Klasse Sequenz aus ein vorgebener Datei mit
135//  vorgegebener Zeilennummer
136// -----------------------------------------------------------------------------
137    Postree::Postree ( str  file,
138                       UINT line ) : sequence ( file, line )
139// -----------------------------------------------------------------------------
140{
141    str seq = sequence.Compressed();
142   
143    if (seq) topnode = new PtNode(seq,NULL,0,0), delete seq;
144}
145
146// -----------------------------------------------------------------------------
147//  Kopierkonstruktor
148// -----------------------------------------------------------------------------
149    Postree::Postree ( Postree &postree ) : sequence ( postree.sequence )
150// -----------------------------------------------------------------------------
151{
152    cout << "\nKopierkonstruktor(Postree)\n";
153
154    if (!postree.topnode) topnode = NULL;
155    else                  topnode = new PtNode(*postree.topnode);
156}
157
158// -----------------------------------------------------------------------------
159//  Destruktor
160// -----------------------------------------------------------------------------
161    Postree::~Postree ( void )
162// -----------------------------------------------------------------------------
163{
164    if (topnode) delete topnode;
165}
166
167// -----------------------------------------------------------------------------
168//  Liefert Laenge der kompremierten Sequenz
169// -----------------------------------------------------------------------------
170    int Postree::SeqLen ( void )
171// -----------------------------------------------------------------------------
172{
173    return sequence.CompressedLen();
174}
175
176// -----------------------------------------------------------------------------
177//  Positionsbaum fuer neue Sequenz aufbauen
178// -----------------------------------------------------------------------------
179    void Postree::Set ( str seq )
180// -----------------------------------------------------------------------------
181{
182    if (seq && *seq)
183    {
184        str tmp;
185       
186        sequence.Set(seq);
187       
188        if (topnode) delete topnode, topnode = NULL;
189       
190        tmp = sequence.Compressed();
191       
192        if (tmp) topnode = new PtNode(tmp,NULL,0,0), delete tmp;
193    }
194}
195
196// -----------------------------------------------------------------------------
197//  Exakte Suche nach den Vorkommen einer Teilsequenz
198// -----------------------------------------------------------------------------
199    int Postree::Find ( str   seq,
200                        int **pos,
201                        int  *anz,
202                        int  *len,
203                        int   sort )
204// -----------------------------------------------------------------------------
205{
206    int result = INVALID;
207
208    *pos = NULL;
209    *anz = 0;
210    *len = 0;
211   
212    if (seq && *seq && pos && anz && len)
213    {
214        PtNode *node = topnode;
215       
216        result = 0;
217       
218        while (!result && *seq)
219        {
220            int base = BIndex[safeCharIndex(*seq++)];
221           
222            if ((base < ADENIN) ||
223                (base > URACIL)) result = INVALID;
224            else
225            {
226                Mask pmask = P_ADENIN,
227                     nmask = N_ADENIN;
228               
229                while (base--)
230                {
231                    pmask = (Mask)(pmask * 2);
232                    nmask = (Mask)(nmask * 2);
233                }
234               
235                if (node->mask & pmask) // Position gefunden
236                {
237                    (*len)++;
238
239                    *anz = 1;
240                    *pos = new int [1];
241                       
242                    if (!*pos) result = INVALID;    // Speicher
243                    else
244                    {
245                        *pos[0] = node->position[node->IndexOfPos(pmask)];
246                   
247                        if (*seq)   // Gesuchte Sequenz ist laenger als Baum tief
248                        {
249                            str org = sequence.Compressed();
250
251                            if (!org) result = INVALID; // Speicher
252                            else
253                            {
254                                str ptr = &org[*pos[0] + *len];
255                           
256                                while (*ptr && *seq && (*seq == *ptr))
257                                {
258                                    (*len)++;
259                                    seq++;
260                                    ptr++;
261                                }
262
263                                if (*seq && *ptr) result = 1;   // Unterschied
264                           
265                                delete org;
266                            }
267                        }
268                    }
269                }
270                else if (node->mask & nmask)    // Verzweigung existiert
271                {
272                    (*len)++;
273
274                    node = node->next[node->IndexOfNext(nmask)];
275                }
276                else    // Unterschied => alle Moeglichkeiten suchen
277                {
278                    result = 1;
279
280                    *pos = FindLeaves(*node,anz);
281                }
282            }
283        }
284
285        if (!result && !*seq && !*pos)  // Sequenz ist kuerzer als Baum tief
286        {
287            *pos = FindLeaves(*node,anz);
288
289            if (!*pos) result = INVALID;    // Speicher
290        }
291    }
292
293    if (sort && *pos && (*anz > 1)) SortIntArray(*pos,anz);
294   
295    return result;
296}
297
298// -----------------------------------------------------------------------------
299//  Suche nach den Vorkommen einer Teilsequenz mit bis zu einer Substitution
300// -----------------------------------------------------------------------------
301    int Postree::OneSubstitution ( str   seq,
302                                   int **pos,
303                                   int  *anz,
304                                   int  *len )
305// -----------------------------------------------------------------------------
306{
307    int  result  = INVALID,
308         seqlen  = strlen(seq),
309        *lpos    = NULL,
310         lanz    = 0,
311         llen    = 0,
312         res,
313         count;
314    str  search  = new char [seqlen + 1];
315       
316    for (count = 0;count < seqlen;count++)
317    {
318        int base;
319               
320        strcpy(search,seq);
321           
322        for (base = ADENIN;base <= URACIL;base++)
323        {
324            if (search[count] == BCharacter[base]) continue;
325
326            search[count] = BCharacter[base];
327
328            res = Find(search,&lpos,&lanz,&llen,0);
329
330            if (res >= 0)
331            {
332                if (llen > *len)
333                {
334                    if (*pos) delete *pos;
335
336                    *pos   = lpos;
337                    *len   = llen;
338                    *anz   = lanz;
339                    result = res;
340                }
341                else if (llen == *len)
342                {
343                    int *tmp = new int [*anz + lanz];
344                           
345                    if (*anz) memcpy(tmp,*pos,*anz * sizeof(int));
346
347                    memcpy(&tmp[*anz],lpos,lanz * sizeof(int));
348
349                    if (*pos) delete *pos;
350                           
351                    *pos    = tmp;
352                    *anz   += lanz;
353                    result  = res;
354                }
355            }
356
357            search[count] = seq[count];
358        }
359    }
360
361    delete search;
362
363    return result;
364}
365
366// -----------------------------------------------------------------------------
367//  Suche nach den Vorkommen einer Teilsequenz mit bis zu einer Deletion
368// -----------------------------------------------------------------------------
369    int Postree::OneDeletion ( str   seq,
370                               int **pos,
371                               int  *anz,
372                               int  *len )
373// -----------------------------------------------------------------------------
374{
375    int  result  = INVALID,
376         seqlen  = strlen(seq),
377        *lpos    = NULL,
378         lanz    = 0,
379         llen    = 0,
380         res,
381         count;
382    str  search  = new char [seqlen + 1];
383       
384    for (count = 0;count < seqlen;count++)
385    {
386        if (!count) *search = 0;
387        else         strncpy(search,seq,count), search[count] = 0;
388       
389        strcat(search,&seq[count + 1]);
390
391        res = Find(search,&lpos,&lanz,&llen,0);
392
393        if (res >= 0)
394        {
395            if (llen > *len)
396            {
397                if (*pos) delete *pos;
398
399                *pos   = lpos;
400                *len   = llen;
401                *anz   = lanz;
402                result = res;
403            }
404            else if (llen == *len)
405            {
406                int *tmp = new int [*anz + lanz];
407                           
408                if (*anz) memcpy(tmp,*pos,*anz * sizeof(int));
409               
410                memcpy(&tmp[*anz],lpos,lanz * sizeof(int));
411
412                if (*pos) delete *pos;
413                           
414                *pos    = tmp;
415                *anz   += lanz;
416                result  = res;
417            }
418        }
419    }
420
421    delete search;
422
423    return result;
424}
425
426// -----------------------------------------------------------------------------
427//  Suche nach den Vorkommen einer Teilsequenz mit bis zu einer Insertion
428// -----------------------------------------------------------------------------
429    int Postree::OneInsertion ( str   seq,
430                                int **pos,
431                                int  *anz,
432                                int  *len )
433// -----------------------------------------------------------------------------
434{
435    int  result  = INVALID,
436         seqlen  = strlen(seq),
437        *lpos    = NULL,
438         lanz    = 0,
439         llen    = 0,
440         res,
441         count;
442    str  search  = new char [seqlen + 2];
443       
444    for (count = 0;count <= seqlen;count++)
445    {
446        int base;
447
448        if (!count) search[0] = ' ',
449                    search[1] = 0;
450        else        strncpy(search,seq,count),
451                    search[count] = ' ',
452                    search[count + 1] = 0;
453       
454        strcat(search,&seq[count]);
455           
456        for (base = ADENIN;base <= URACIL;base++)
457        {
458            search[count] = BCharacter[base];
459
460            res = Find(search,&lpos,&lanz,&llen,0);
461
462            if (res >= 0)
463            {
464                if (llen > *len)
465                {
466                    if (*pos) delete *pos;
467
468                    *pos   = lpos;
469                    *len   = llen;
470                    *anz   = lanz;
471                    result = res;
472                }
473                else if (llen == *len)
474                {
475                    int *tmp = new int [*anz + lanz];
476                           
477                    if (*anz) memcpy(tmp,*pos,*anz * sizeof(int));
478
479                    memcpy(&tmp[*anz],lpos,lanz * sizeof(int));
480
481                    if (*pos) delete *pos;
482                           
483                    *pos    = tmp;
484                    *anz   += lanz;
485                    result  = res;
486                }
487            }
488
489            search[count] = seq[count];
490        }
491    }
492
493    delete search;
494
495    return result;
496}
497
498// -----------------------------------------------------------------------------
499//  Suche nach den Vorkommen einer Teilsequenz mit bis zu einem Fehler
500// -----------------------------------------------------------------------------
501    int Postree::OneMismatch ( str   seq,
502                               int **pos,
503                               int  *anz,
504                               int  *len )
505// -----------------------------------------------------------------------------
506{
507    int result = Find(seq,pos,anz,len,0);
508
509    if (result >= 0)
510    {
511        int *lpos[3] = { NULL, NULL, NULL },
512             lanz[3] = { 0, 0, 0 },
513             llen[3],
514             res [3] = { INVALID, INVALID, INVALID },
515             count;
516       
517        llen[0] = llen[2] = *len;
518        llen[1] = 0;
519        res[0] = OneSubstitution(seq,&lpos[0],&lanz[0],&llen[0]);
520        res[1] = OneDeletion    (seq,&lpos[1],&lanz[1],&llen[1]);
521        res[2] = OneInsertion   (seq,&lpos[2],&lanz[2],&llen[2]);
522
523        for (count = 0; count < 3;count++)
524        {
525            if (res[count] >= 0)
526            {
527                result = 1;
528               
529                if (llen[count] > *len)
530                {
531                    if (*pos) delete *pos;
532
533                    *pos   = lpos[count];
534                    *len   = llen[count];
535                    *anz   = lanz[count];
536                    result = res [count];
537
538                    lpos[count] = NULL;
539                }
540                else if (llen[count] == *len)
541                {
542                    int *tmp = new int [*anz + lanz[count]];
543                           
544                    if (*anz) memcpy(tmp,*pos,*anz * sizeof(int));
545
546                    memcpy(&tmp[*anz],lpos[count],lanz[count] * sizeof(int));
547
548                    if (*pos) delete *pos;
549                           
550                    *pos    = tmp;
551                    *anz   += lanz[count];
552                }
553            }
554
555            if (lpos[count]) delete lpos[count];
556        }
557
558        if (*pos && (*anz > 1)) SortIntArray(*pos,anz);
559    }
560
561    return result;
562}
563
564// -----------------------------------------------------------------------------
565//  Ausgabefunktion fur eine Instanz der Klasse Postree zu debug-Zwecken
566// -----------------------------------------------------------------------------
567    void Postree::Dump ( void )
568// -----------------------------------------------------------------------------
569{
570    cout << "\nsequence :\n";
571   
572    sequence.Dump();
573   
574    cout << "topnode :\n";
575   
576    if (topnode) topnode->Dump(), cout << "\n";
577}
578
579// -----------------------------------------------------------------------------
580//  Ausgabefunktion fur eine Instanz der Klasse Postree
581// -----------------------------------------------------------------------------
582    void Postree::Show ( int mode )
583// -----------------------------------------------------------------------------
584{
585    switch (mode)
586    {
587        case 0:     cout << "\npostree:\n\n";
588                    if (topnode) topnode->Show(0,NULL), cout << "\n";
589                    break;
590        case 1:
591        {
592            str seq = sequence.Compressed();
593           
594            cout << "\nsequence:\n\n";
595
596            if (seq)
597            {
598                cout << "Laenge: " << strlen(seq) << "\n";
599                cout << seq << "\n";
600                delete seq;
601            }
602           
603            break;
604        }
605        case 2:     cout << "\nsequence :\n";
606                    sequence.Dump();
607                    cout << "\npostree :\n\n";
608                    if (topnode) topnode->Show(0,NULL), cout << "\n";
609                    break;
610    }
611}
Note: See TracBrowser for help on using the repository browser.