source: trunk/GDE/MUSCLE/src/bittraceback.cpp

Last change on this file was 10390, checked in by aboeckma, 12 years ago

added muscle sourcles amd makefile
File size: 3.3 KB
Line 
1#include "muscle.h"
2#include "pwpath.h"
3
4#define TRACE 0
5
6static char XlatEdgeType(char c)
7        {
8        if ('E' == c)
9                return 'D';
10        if ('J' == c)
11                return 'I';
12        return c;
13        }
14
15static const char *BitsToStr(char Bits)
16        {
17        static char Str[] = "xM xD xI";
18
19        switch (Bits & BIT_xM)
20                {
21        case BIT_MM:
22                Str[0] = 'M';
23                break;
24        case BIT_DM:
25                Str[0] = 'D';
26                break;
27        case BIT_IM:
28                Str[0] = 'I';
29                break;
30                }
31
32        switch (Bits & BIT_xD)
33                {
34        case BIT_MD:
35                Str[3] = 'M';
36                break;
37        case BIT_DD:
38                Str[3] = 'D';
39                break;
40                }
41
42        switch (Bits & BIT_xI)
43                {
44        case BIT_MI:
45                Str[6] = 'M';
46                break;
47        case BIT_II:
48                Str[6] = 'I';
49                break;
50                }
51
52        return Str;
53        }
54
55static inline char XChar(char Bits, char cType)
56        {
57        switch (cType)
58                {
59        case 'M':
60                {
61                switch (Bits & BIT_xM)
62                        {
63                case BIT_MM:
64                        return 'M';
65                case BIT_DM:
66                        return 'D';
67                case BIT_IM:
68                        return 'I';
69#if     DOUBLE_AFFINE
70                case BIT_EM:
71                        return 'E';
72                case BIT_JM:
73                        return 'J';
74#endif
75                        }
76                Quit("Huh!?");
77                return '?';
78                }
79        case 'D':
80                {
81                switch (Bits & BIT_xD)
82                        {
83                case BIT_MD:
84                        return 'M';
85                case BIT_DD:
86                        return 'D';
87                        }
88                Quit("Huh!?");
89                return '?';
90                }
91        case 'I':
92                {
93                switch (Bits & BIT_xI)
94                        {
95                case BIT_MI:
96                        return 'M';
97                case BIT_II:
98                        return 'I';
99                        }
100                Quit("Huh!?");
101                return '?';
102                }
103#if     DOUBLE_AFFINE
104        case 'E':
105                {
106                switch (Bits & BIT_xE)
107                        {
108                case BIT_ME:
109                        return 'M';
110                case BIT_EE:
111                        return 'E';
112                        }
113                Quit("Huh!?");
114                return '?';
115                }
116        case 'J':
117                {
118                switch (Bits & BIT_xJ)
119                        {
120                case BIT_MJ:
121                        return 'M';
122                case BIT_JJ:
123                        return 'J';
124                        }
125                Quit("Huh!?");
126                return '?';
127                }
128#endif
129        default:
130                Quit("Huh?");
131                return '?';
132                }
133        }
134
135void BitTraceBack(char **TraceBack, unsigned uLengthA, unsigned uLengthB,
136  char LastEdge, PWPath &Path)
137        {
138#if     TRACE
139        Log("BitTraceBack\n");
140#endif
141        Path.Clear();
142
143        PWEdge Edge;
144        Edge.uPrefixLengthA = uLengthA;
145        Edge.uPrefixLengthB = uLengthB;
146        char Bits = TraceBack[uLengthA][uLengthB];
147        Edge.cType = LastEdge;
148        for (;;)
149                {
150#if     TRACE
151                Log("Prepend %c%d.%d\n", Edge.cType, Edge.uPrefixLengthA, Edge.uPrefixLengthB);
152#endif
153                char cSave = Edge.cType;
154                Edge.cType = XlatEdgeType(cSave);
155                Path.PrependEdge(Edge);
156                Edge.cType = cSave;
157
158                unsigned PLA = Edge.uPrefixLengthA;
159                unsigned PLB = Edge.uPrefixLengthB;
160                char Bits = TraceBack[PLA][PLB];
161                char NextEdgeType = XChar(Bits, Edge.cType);
162#if     TRACE
163                Log("XChar(%s, %c) = %c\n", BitsToStr(Bits), Edge.cType, NextEdgeType);
164#endif
165                switch (Edge.cType)
166                        {
167                case 'M':
168                        {
169                        if (Edge.uPrefixLengthA == 0)
170                                Quit("BitTraceBack MA=0");
171                        if (Edge.uPrefixLengthB == 0)
172                                Quit("BitTraceBack MA=0");
173                        --(Edge.uPrefixLengthA);
174                        --(Edge.uPrefixLengthB);
175                        break;
176                        }
177                case 'D':
178                case 'E':
179                        {
180                        if (Edge.uPrefixLengthA == 0)
181                                Quit("BitTraceBack DA=0");
182                        --(Edge.uPrefixLengthA);
183                        break;
184                        }
185                case 'I':
186                case 'J':
187                        {
188                        if (Edge.uPrefixLengthB == 0)
189                                Quit("BitTraceBack IB=0");
190                        --(Edge.uPrefixLengthB);
191                        break;
192                        }
193                default:
194                        Quit("BitTraceBack: Invalid edge %c", Edge);
195                        }
196
197                if (0 == Edge.uPrefixLengthA && 0 == Edge.uPrefixLengthB)
198                        break;
199
200                Edge.cType = NextEdgeType;
201                }
202
203#if     TRACE
204        Path.LogMe();
205#endif
206        }
Note: See TracBrowser for help on using the repository browser.