6 void GetDiagBox(unsigned LA, unsigned LB, unsigned DiagLo, unsigned DiagHi, DiagBox &Box);
\r
7 void GetDiagRange(unsigned LA, unsigned LB, unsigned d,
\r
8 unsigned &mini, unsigned &minj, unsigned &maxi, unsigned &maxj);
\r
9 void GetDiagLoHi(unsigned LA, unsigned LB, const char *Path,
\r
10 unsigned &dlo, unsigned &dhi);
\r
18 DiagBox(unsigned LA_, unsigned LB_, unsigned DiagLo, unsigned DiagHi)
\r
20 //GetDiagBox(LA, LB, DiagLo, DiagHi, *this);
\r
22 Init(LA_, LB_, DiagLo, DiagHi);
\r
25 void Init(unsigned LA_, unsigned LB_, unsigned DiagLo, unsigned DiagHi)
\r
27 GetDiagBox(LA_, LB_, DiagLo, DiagHi, *this);
\r
49 unsigned GetDiag(unsigned i, unsigned j) const
\r
54 // i, j are positions 0..LA-1, 0..LB-1.
\r
55 bool InBox(unsigned i, unsigned j) const
\r
57 unsigned d = GetDiag(i, j);
\r
58 return d >= dlo && d <= dhi;
\r
62 i, j are 0-based prefix lengths 0..LA, 0..LB.
\r
64 A full path is in the box iff all match pairs are in the box.
\r
66 A partial path that aligns a prefix of A to a prefix of B as
\r
67 in D.P.) is in the box iff it is is the prefix of at least
\r
68 one full path that is in the box.
\r
70 A D.P. matrix entry X[i][j] is in the box iff there is at
\r
71 least one full path aligning the first i letters of A and
\r
72 the first j letters of B ending in a column of type X, i.e.
\r
73 if there exists a partial path in the box that ends in X.
\r
75 Assume terminals appear in all paths, and DI/ID forbidden.
\r
77 Intuitively seems that by these definitions D is in box iff
\r
78 DM or MD is in box, I is in box iff IM or MI is in box.
\r
81 bool InBoxDPM(unsigned i, unsigned j) const
\r
83 // Special case for M[0][0]
\r
84 if (i == 0 && j == 0)
\r
86 if (i == 0 || j == 0)
\r
88 unsigned d = GetDiag(i-1, j-1);
\r
89 return d >= dlo && d <= dhi;
\r
92 bool InBoxDPD(unsigned i, unsigned j) const
\r
94 bool MD = i == 0 ? false : InBoxDPM(i-1, j);
\r
95 bool DM = (i == LA || j == LB) ? false : InBoxDPM(i+1, j+1);
\r
99 bool InBoxDPI(unsigned i, unsigned j) const
\r
101 bool MI = j == 0 ? false : InBoxDPM(i, j-1);
\r
102 bool IM = (i == LA || j == LB) ? false : InBoxDPM(i+1, j+1);
\r
106 // d = LA - i + j = 1 .. LA+LB-1
\r
107 void Validate() const
\r
109 asserta(dlo <= dhi);
\r
110 asserta(dlo >= GetDiag(LA-1, 0));
\r
111 asserta(dhi <= GetDiag(0, LB-1));
\r
113 asserta(GetDiag(dlo_mini, dlo_minj) == dlo);
\r
114 asserta(GetDiag(dlo_maxi, dlo_maxj) == dlo);
\r
115 asserta(GetDiag(dhi_mini, dhi_minj) == dhi);
\r
116 asserta(GetDiag(dhi_maxi, dhi_maxj) == dhi);
\r
118 asserta(dlo_mini >= dhi_mini);
\r
119 asserta(dlo_minj <= dhi_minj);
\r
120 asserta(dlo_maxi >= dhi_maxi);
\r
121 asserta(dlo_maxj <= dhi_maxj);
\r
124 unsigned GetMini() const
\r
129 unsigned GetMaxi() const
\r
134 unsigned GetMinj() const
\r
139 unsigned GetMaxj() const
\r
146 d = LA - i + j = 1 .. LA+LB-1
\r
150 void GetRange_j(unsigned i, unsigned &Startj, unsigned &Endj) const
\r
154 Startj = dlo + i - LA;
\r
161 if (dhi + i + 1 >= LA)
\r
162 Endj = dhi + i + 1 - LA;
\r
169 asserta(Endj >= Startj);
\r
174 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
177 dlo_mini, dlo_minj,
\r
178 dlo_maxi, dlo_maxj,
\r
180 dhi_mini, dhi_minj,
\r
181 dhi_maxi, dhi_maxj,
\r
182 GetMini(), GetMaxi(),
\r
183 GetMinj(), GetMaxj());
\r
187 typedef const char *(*NWDIAG)(const byte *A, unsigned LA, const byte *B, unsigned LB,
188 unsigned DiagLo, unsigned DiagHi, bool LeftTerm, bool RightTerm);
190 const char *NWBandWrap(NWDIAG NW, const byte *A, unsigned LA, const byte *B, unsigned LB,
191 unsigned DiagLo, unsigned DiagHi, bool LeftTerm, bool RightTerm);
193 #endif // diagbox_h
\r