1 #ifndef diagbox_h 2 #define diagbox_h 3 4 struct DiagBox; 5 6 void GetDiagBox(unsigned LA, unsigned LB, unsigned DiagLo, unsigned DiagHi, DiagBox &Box); 7 void GetDiagRange(unsigned LA, unsigned LB, unsigned d, 8 unsigned &mini, unsigned &minj, unsigned &maxi, unsigned &maxj); 9 void GetDiagLoHi(unsigned LA, unsigned LB, const char *Path, 10 unsigned &dlo, unsigned &dhi); 11 12 struct DiagBox 13 { DiagBoxDiagBox14 DiagBox() 15 { 16 } 17 DiagBoxDiagBox18 DiagBox(unsigned LA_, unsigned LB_, unsigned DiagLo, unsigned DiagHi) 19 { 20 //GetDiagBox(LA, LB, DiagLo, DiagHi, *this); 21 //Validate(); 22 Init(LA_, LB_, DiagLo, DiagHi); 23 } 24 InitDiagBox25 void Init(unsigned LA_, unsigned LB_, unsigned DiagLo, unsigned DiagHi) 26 { 27 GetDiagBox(LA_, LB_, DiagLo, DiagHi, *this); 28 Validate(); 29 } 30 31 unsigned LA; 32 unsigned LB; 33 34 unsigned dlo; 35 unsigned dhi; 36 37 unsigned dlo_mini; 38 unsigned dlo_minj; 39 40 unsigned dlo_maxi; 41 unsigned dlo_maxj; 42 43 unsigned dhi_mini; 44 unsigned dhi_minj; 45 46 unsigned dhi_maxi; 47 unsigned dhi_maxj; 48 GetDiagDiagBox49 unsigned GetDiag(unsigned i, unsigned j) const 50 { 51 return LA - i + j; 52 } 53 54 // i, j are positions 0..LA-1, 0..LB-1. InBoxDiagBox55 bool InBox(unsigned i, unsigned j) const 56 { 57 unsigned d = GetDiag(i, j); 58 return d >= dlo && d <= dhi; 59 } 60 61 /*** 62 i, j are 0-based prefix lengths 0..LA, 0..LB. 63 64 A full path is in the box iff all match pairs are in the box. 65 66 A partial path that aligns a prefix of A to a prefix of B as 67 in D.P.) is in the box iff it is is the prefix of at least 68 one full path that is in the box. 69 70 A D.P. matrix entry X[i][j] is in the box iff there is at 71 least one full path aligning the first i letters of A and 72 the first j letters of B ending in a column of type X, i.e. 73 if there exists a partial path in the box that ends in X. 74 75 Assume terminals appear in all paths, and DI/ID forbidden. 76 77 Intuitively seems that by these definitions D is in box iff 78 DM or MD is in box, I is in box iff IM or MI is in box. 79 Don't have proof.. 80 ***/ InBoxDPMDiagBox81 bool InBoxDPM(unsigned i, unsigned j) const 82 { 83 // Special case for M[0][0] 84 if (i == 0 && j == 0) 85 return true; 86 if (i == 0 || j == 0) 87 return false; 88 unsigned d = GetDiag(i-1, j-1); 89 return d >= dlo && d <= dhi; 90 } 91 InBoxDPDDiagBox92 bool InBoxDPD(unsigned i, unsigned j) const 93 { 94 bool MD = i == 0 ? false : InBoxDPM(i-1, j); 95 bool DM = (i == LA || j == LB) ? false : InBoxDPM(i+1, j+1); 96 return MD || DM; 97 } 98 InBoxDPIDiagBox99 bool InBoxDPI(unsigned i, unsigned j) const 100 { 101 bool MI = j == 0 ? false : InBoxDPM(i, j-1); 102 bool IM = (i == LA || j == LB) ? false : InBoxDPM(i+1, j+1); 103 return MI || IM; 104 } 105 106 // d = LA - i + j = 1 .. LA+LB-1 ValidateDiagBox107 void Validate() const 108 { 109 asserta(dlo <= dhi); 110 asserta(dlo >= GetDiag(LA-1, 0)); 111 asserta(dhi <= GetDiag(0, LB-1)); 112 113 asserta(GetDiag(dlo_mini, dlo_minj) == dlo); 114 asserta(GetDiag(dlo_maxi, dlo_maxj) == dlo); 115 asserta(GetDiag(dhi_mini, dhi_minj) == dhi); 116 asserta(GetDiag(dhi_maxi, dhi_maxj) == dhi); 117 118 asserta(dlo_mini >= dhi_mini); 119 asserta(dlo_minj <= dhi_minj); 120 asserta(dlo_maxi >= dhi_maxi); 121 asserta(dlo_maxj <= dhi_maxj); 122 } 123 GetMiniDiagBox124 unsigned GetMini() const 125 { 126 return dhi_mini; 127 } 128 GetMaxiDiagBox129 unsigned GetMaxi() const 130 { 131 return dlo_maxi; 132 } 133 GetMinjDiagBox134 unsigned GetMinj() const 135 { 136 return dlo_minj; 137 } 138 GetMaxjDiagBox139 unsigned GetMaxj() const 140 { 141 return dhi_maxj; 142 } 143 /*** 144 i = 0..LA-1 145 j = 0..LB-1 146 d = LA - i + j = 1 .. LA+LB-1 147 j = d - LA + i 148 i = LA - d + j 149 ***/ GetRange_jDiagBox150 void GetRange_j(unsigned i, unsigned &Startj, unsigned &Endj) const 151 { 152 // j = d - LA + i 153 if (dlo + i >= LA) 154 Startj = dlo + i - LA; 155 else 156 Startj = 0; 157 158 if (Startj >= LB) 159 Startj = LB - 1; 160 161 if (dhi + i + 1 >= LA) 162 Endj = dhi + i + 1 - LA; 163 else 164 Endj = 0; 165 166 if (Endj > LB) 167 Endj = LB; 168 169 asserta(Endj >= Startj); 170 } 171 LogMeDiagBox172 void LogMe() const 173 { 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", 175 LA, LB, 176 dlo, 177 dlo_mini, dlo_minj, 178 dlo_maxi, dlo_maxj, 179 dhi, 180 dhi_mini, dhi_minj, 181 dhi_maxi, dhi_maxj, 182 GetMini(), GetMaxi(), 183 GetMinj(), GetMaxj()); 184 } 185 }; 186 187 typedef const char *(*NWDIAG)(const byte *A, unsigned LA, const byte *B, unsigned LB, 188 unsigned DiagLo, unsigned DiagHi, bool LeftTerm, bool RightTerm); 189 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); 192 193 #endif // diagbox_h 194