diagbox.h

   1 //uchime by Robert C. Edgar http://drive5.com/uchime This code is donated to the public domain.\r
   2 \r
   3 #ifndef diagbox_h\r
   4 #define diagbox_h\r
   5 \r
   6 struct DiagBox;\r
   7 \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
  13 \r
  14 struct DiagBox\r
  15         {\r
  16         DiagBox()\r
  17                 {\r
  18                 }\r
  19 \r
  20         DiagBox(unsigned LA_, unsigned LB_, unsigned DiagLo, unsigned DiagHi)\r
  21                 {\r
  22                 //GetDiagBox(LA, LB, DiagLo, DiagHi, *this);\r
  23                 //Validate();\r
  24                 Init(LA_, LB_, DiagLo, DiagHi);\r
  25                 }\r
  26 \r
  27         void Init(unsigned LA_, unsigned LB_, unsigned DiagLo, unsigned DiagHi)\r
  28                 {\r
  29                 GetDiagBox(LA_, LB_, DiagLo, DiagHi, *this);\r
  30                 Validate();\r
  31                 }\r
  32 \r
  33         unsigned LA;\r
  34         unsigned LB;\r
  35 \r
  36         unsigned dlo;\r
  37         unsigned dhi;\r
  38 \r
  39         unsigned dlo_mini;\r
  40         unsigned dlo_minj;\r
  41 \r
  42         unsigned dlo_maxi;\r
  43         unsigned dlo_maxj;\r
  44 \r
  45         unsigned dhi_mini;\r
  46         unsigned dhi_minj;\r
  47 \r
  48         unsigned dhi_maxi;\r
  49         unsigned dhi_maxj;\r
  50 \r
  51         unsigned GetDiag(unsigned i, unsigned j) const\r
  52                 {\r
  53                 return LA - i + j;\r
  54                 }\r
  55 \r
  56 // i, j are positions 0..LA-1, 0..LB-1.\r
  57         bool InBox(unsigned i, unsigned j) const\r
  58                 {\r
  59                 unsigned d = GetDiag(i, j);\r
  60                 return d >= dlo && d <= dhi;\r
  61                 }\r
  62 \r
  63 /***\r
  64 i, j are 0-based prefix lengths 0..LA, 0..LB.\r
  65 \r
  66 A full path is in the box iff all match pairs are in the box.\r
  67 \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
  71 \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
  76 \r
  77 Assume terminals appear in all paths, and DI/ID forbidden.\r
  78 \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
  81 Don't have proof..\r
  82 ***/\r
  83         bool InBoxDPM(unsigned i, unsigned j) const\r
  84                 {\r
  85         // Special case for M[0][0]\r
  86                 if (i == 0 && j == 0)\r
  87                         return true;\r
  88                 if (i == 0 || j == 0)\r
  89                         return false;\r
  90                 unsigned d = GetDiag(i-1, j-1);\r
  91                 return d >= dlo && d <= dhi;\r
  92                 }\r
  93 \r
  94         bool InBoxDPD(unsigned i, unsigned j) const\r
  95                 {\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
  98                 return MD || DM;\r
  99                 }\r
 100 \r
 101         bool InBoxDPI(unsigned i, unsigned j) const\r
 102                 {\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
 105                 return MI || IM;\r
 106                 }\r
 107 \r
 108         // d = LA - i + j = 1 .. LA+LB-1\r
 109         void Validate() const\r
 110                 {\r
 111                 asserta(dlo <= dhi);\r
 112                 asserta(dlo >= GetDiag(LA-1, 0));\r
 113                 asserta(dhi <= GetDiag(0, LB-1));\r
 114 \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
 119 \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
 124                 }\r
 125 \r
 126         unsigned GetMini() const\r
 127                 {\r
 128                 return dhi_mini;\r
 129                 }\r
 130 \r
 131         unsigned GetMaxi() const\r
 132                 {\r
 133                 return dlo_maxi;\r
 134                 }\r
 135 \r
 136         unsigned GetMinj() const\r
 137                 {\r
 138                 return dlo_minj;\r
 139                 }\r
 140 \r
 141         unsigned GetMaxj() const\r
 142                 {\r
 143                 return dhi_maxj;\r
 144                 }\r
 145 /***\r
 146         i = 0..LA-1\r
 147         j = 0..LB-1\r
 148         d = LA - i + j = 1 .. LA+LB-1\r
 149         j = d - LA + i\r
 150         i = LA - d + j\r
 151 ***/\r
 152         void GetRange_j(unsigned i, unsigned &Startj, unsigned &Endj) const\r
 153                 {\r
 154         // j = d - LA + i\r
 155                 if (dlo + i >= LA)\r
 156                         Startj = dlo + i - LA;\r
 157                 else\r
 158                         Startj = 0;\r
 159 \r
 160                 if (Startj >= LB)\r
 161                         Startj = LB - 1;\r
 162 \r
 163                 if (dhi + i + 1 >= LA)\r
 164                         Endj = dhi + i + 1 - LA;\r
 165                 else\r
 166                         Endj = 0;\r
 167 \r
 168                 if (Endj > LB)\r
 169                         Endj = LB;\r
 170 \r
 171                 asserta(Endj >= Startj);\r
 172                 }\r
 173 \r
 174         void LogMe() const\r
 175                 {\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
 177                   LA, LB,\r
 178                   dlo,\r
 179                   dlo_mini, dlo_minj,\r
 180                   dlo_maxi, dlo_maxj,\r
 181                   dhi,\r
 182                   dhi_mini, dhi_minj,\r
 183                   dhi_maxi, dhi_maxj,\r
 184                   GetMini(), GetMaxi(),\r
 185                   GetMinj(), GetMaxj());\r
 186                 }\r
 187         };\r
 188 \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
 191 \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
 194 \r
 195 #endif // diagbox_h\r