1 //uchime by Robert C. Edgar http://drive5.com/uchime This code is donated to the public domain.
\r
8 void GetDiagBox(unsigned LA, unsigned LB, unsigned DiagLo, unsigned DiagHi, DiagBox &Box);
\r
9 void GetDiagRange(unsigned LA, unsigned LB, unsigned d,
\r
10 unsigned &mini, unsigned &minj, unsigned &maxi, unsigned &maxj);
\r
11 void GetDiagLoHi(unsigned LA, unsigned LB, const char *Path,
\r
12 unsigned &dlo, unsigned &dhi);
\r
20 DiagBox(unsigned LA_, unsigned LB_, unsigned DiagLo, unsigned DiagHi)
\r
22 //GetDiagBox(LA, LB, DiagLo, DiagHi, *this);
\r
24 Init(LA_, LB_, DiagLo, DiagHi);
\r
27 void Init(unsigned LA_, unsigned LB_, unsigned DiagLo, unsigned DiagHi)
\r
29 GetDiagBox(LA_, LB_, DiagLo, DiagHi, *this);
\r
51 unsigned GetDiag(unsigned i, unsigned j) const
\r
56 // i, j are positions 0..LA-1, 0..LB-1.
\r
57 bool InBox(unsigned i, unsigned j) const
\r
59 unsigned d = GetDiag(i, j);
\r
60 return d >= dlo && d <= dhi;
\r
64 i, j are 0-based prefix lengths 0..LA, 0..LB.
\r
66 A full path is in the box iff all match pairs are in the box.
\r
68 A partial path that aligns a prefix of A to a prefix of B as
\r
69 in D.P.) is in the box iff it is is the prefix of at least
\r
70 one full path that is in the box.
\r
72 A D.P. matrix entry X[i][j] is in the box iff there is at
\r
73 least one full path aligning the first i letters of A and
\r
74 the first j letters of B ending in a column of type X, i.e.
\r
75 if there exists a partial path in the box that ends in X.
\r
77 Assume terminals appear in all paths, and DI/ID forbidden.
\r
79 Intuitively seems that by these definitions D is in box iff
\r
80 DM or MD is in box, I is in box iff IM or MI is in box.
\r
83 bool InBoxDPM(unsigned i, unsigned j) const
\r
85 // Special case for M[0][0]
\r
86 if (i == 0 && j == 0)
\r
88 if (i == 0 || j == 0)
\r
90 unsigned d = GetDiag(i-1, j-1);
\r
91 return d >= dlo && d <= dhi;
\r
94 bool InBoxDPD(unsigned i, unsigned j) const
\r
96 bool MD = i == 0 ? false : InBoxDPM(i-1, j);
\r
97 bool DM = (i == LA || j == LB) ? false : InBoxDPM(i+1, j+1);
\r
101 bool InBoxDPI(unsigned i, unsigned j) const
\r
103 bool MI = j == 0 ? false : InBoxDPM(i, j-1);
\r
104 bool IM = (i == LA || j == LB) ? false : InBoxDPM(i+1, j+1);
\r
108 // d = LA - i + j = 1 .. LA+LB-1
\r
109 void Validate() const
\r
111 asserta(dlo <= dhi);
\r
112 asserta(dlo >= GetDiag(LA-1, 0));
\r
113 asserta(dhi <= GetDiag(0, LB-1));
\r
115 asserta(GetDiag(dlo_mini, dlo_minj) == dlo);
\r
116 asserta(GetDiag(dlo_maxi, dlo_maxj) == dlo);
\r
117 asserta(GetDiag(dhi_mini, dhi_minj) == dhi);
\r
118 asserta(GetDiag(dhi_maxi, dhi_maxj) == dhi);
\r
120 asserta(dlo_mini >= dhi_mini);
\r
121 asserta(dlo_minj <= dhi_minj);
\r
122 asserta(dlo_maxi >= dhi_maxi);
\r
123 asserta(dlo_maxj <= dhi_maxj);
\r
126 unsigned GetMini() const
\r
131 unsigned GetMaxi() const
\r
136 unsigned GetMinj() const
\r
141 unsigned GetMaxj() const
\r
148 d = LA - i + j = 1 .. LA+LB-1
\r
152 void GetRange_j(unsigned i, unsigned &Startj, unsigned &Endj) const
\r
156 Startj = dlo + i - LA;
\r
163 if (dhi + i + 1 >= LA)
\r
164 Endj = dhi + i + 1 - LA;
\r
171 asserta(Endj >= Startj);
\r
176 Log("LA=%u LB=%d dlo(%u): (%u,%u)-(%u,%u) dhi(%u): (%u,%u)-(%u,%u) i=[%u-%u] j=[%u-%u]\n",
\r
179 dlo_mini, dlo_minj,
\r
180 dlo_maxi, dlo_maxj,
\r
182 dhi_mini, dhi_minj,
\r
183 dhi_maxi, dhi_maxj,
\r
184 GetMini(), GetMaxi(),
\r
185 GetMinj(), GetMaxj());
\r
189 typedef const char *(*NWDIAG)(const byte *A, unsigned LA, const byte *B, unsigned LB,
\r
190 unsigned DiagLo, unsigned DiagHi, bool LeftTerm, bool RightTerm);
\r
192 const char *NWBandWrap(NWDIAG NW, const byte *A, unsigned LA, const byte *B, unsigned LB,
\r
193 unsigned DiagLo, unsigned DiagHi, bool LeftTerm, bool RightTerm);
\r
195 #endif // diagbox_h
\r