--- /dev/null
+#ifndef diagbox_h\r
+#define diagbox_h\r
+\r
+struct DiagBox;\r
+\r
+void GetDiagBox(unsigned LA, unsigned LB, unsigned DiagLo, unsigned DiagHi, DiagBox &Box);\r
+void GetDiagRange(unsigned LA, unsigned LB, unsigned d,\r
+ unsigned &mini, unsigned &minj, unsigned &maxi, unsigned &maxj);\r
+void GetDiagLoHi(unsigned LA, unsigned LB, const char *Path,\r
+ unsigned &dlo, unsigned &dhi);\r
+\r
+struct DiagBox\r
+ {\r
+ DiagBox()\r
+ {\r
+ }\r
+\r
+ DiagBox(unsigned LA_, unsigned LB_, unsigned DiagLo, unsigned DiagHi)\r
+ {\r
+ //GetDiagBox(LA, LB, DiagLo, DiagHi, *this);\r
+ //Validate();\r
+ Init(LA_, LB_, DiagLo, DiagHi);\r
+ }\r
+\r
+ void Init(unsigned LA_, unsigned LB_, unsigned DiagLo, unsigned DiagHi)\r
+ {\r
+ GetDiagBox(LA_, LB_, DiagLo, DiagHi, *this);\r
+ Validate();\r
+ }\r
+\r
+ unsigned LA;\r
+ unsigned LB;\r
+\r
+ unsigned dlo;\r
+ unsigned dhi;\r
+\r
+ unsigned dlo_mini;\r
+ unsigned dlo_minj;\r
+\r
+ unsigned dlo_maxi;\r
+ unsigned dlo_maxj;\r
+\r
+ unsigned dhi_mini;\r
+ unsigned dhi_minj;\r
+\r
+ unsigned dhi_maxi;\r
+ unsigned dhi_maxj;\r
+\r
+ unsigned GetDiag(unsigned i, unsigned j) const\r
+ {\r
+ return LA - i + j;\r
+ }\r
+\r
+// i, j are positions 0..LA-1, 0..LB-1.\r
+ bool InBox(unsigned i, unsigned j) const\r
+ {\r
+ unsigned d = GetDiag(i, j);\r
+ return d >= dlo && d <= dhi;\r
+ }\r
+\r
+/***\r
+i, j are 0-based prefix lengths 0..LA, 0..LB.\r
+\r
+A full path is in the box iff all match pairs are in the box.\r
+\r
+A partial path that aligns a prefix of A to a prefix of B as\r
+in D.P.) is in the box iff it is is the prefix of at least\r
+one full path that is in the box.\r
+\r
+A D.P. matrix entry X[i][j] is in the box iff there is at\r
+least one full path aligning the first i letters of A and\r
+the first j letters of B ending in a column of type X, i.e.\r
+if there exists a partial path in the box that ends in X.\r
+\r
+Assume terminals appear in all paths, and DI/ID forbidden.\r
+\r
+Intuitively seems that by these definitions D is in box iff\r
+DM or MD is in box, I is in box iff IM or MI is in box.\r
+Don't have proof..\r
+***/\r
+ bool InBoxDPM(unsigned i, unsigned j) const\r
+ {\r
+ // Special case for M[0][0]\r
+ if (i == 0 && j == 0)\r
+ return true;\r
+ if (i == 0 || j == 0)\r
+ return false;\r
+ unsigned d = GetDiag(i-1, j-1);\r
+ return d >= dlo && d <= dhi;\r
+ }\r
+\r
+ bool InBoxDPD(unsigned i, unsigned j) const\r
+ {\r
+ bool MD = i == 0 ? false : InBoxDPM(i-1, j);\r
+ bool DM = (i == LA || j == LB) ? false : InBoxDPM(i+1, j+1);\r
+ return MD || DM;\r
+ }\r
+\r
+ bool InBoxDPI(unsigned i, unsigned j) const\r
+ {\r
+ bool MI = j == 0 ? false : InBoxDPM(i, j-1);\r
+ bool IM = (i == LA || j == LB) ? false : InBoxDPM(i+1, j+1);\r
+ return MI || IM;\r
+ }\r
+\r
+ // d = LA - i + j = 1 .. LA+LB-1\r
+ void Validate() const\r
+ {\r
+ asserta(dlo <= dhi);\r
+ asserta(dlo >= GetDiag(LA-1, 0));\r
+ asserta(dhi <= GetDiag(0, LB-1));\r
+\r
+ asserta(GetDiag(dlo_mini, dlo_minj) == dlo);\r
+ asserta(GetDiag(dlo_maxi, dlo_maxj) == dlo);\r
+ asserta(GetDiag(dhi_mini, dhi_minj) == dhi);\r
+ asserta(GetDiag(dhi_maxi, dhi_maxj) == dhi);\r
+\r
+ asserta(dlo_mini >= dhi_mini);\r
+ asserta(dlo_minj <= dhi_minj);\r
+ asserta(dlo_maxi >= dhi_maxi);\r
+ asserta(dlo_maxj <= dhi_maxj);\r
+ }\r
+\r
+ unsigned GetMini() const\r
+ {\r
+ return dhi_mini;\r
+ }\r
+\r
+ unsigned GetMaxi() const\r
+ {\r
+ return dlo_maxi;\r
+ }\r
+\r
+ unsigned GetMinj() const\r
+ {\r
+ return dlo_minj;\r
+ }\r
+\r
+ unsigned GetMaxj() const\r
+ {\r
+ return dhi_maxj;\r
+ }\r
+/***\r
+ i = 0..LA-1\r
+ j = 0..LB-1\r
+ d = LA - i + j = 1 .. LA+LB-1\r
+ j = d - LA + i\r
+ i = LA - d + j\r
+***/\r
+ void GetRange_j(unsigned i, unsigned &Startj, unsigned &Endj) const\r
+ {\r
+ // j = d - LA + i\r
+ if (dlo + i >= LA)\r
+ Startj = dlo + i - LA;\r
+ else\r
+ Startj = 0;\r
+\r
+ if (Startj >= LB)\r
+ Startj = LB - 1;\r
+\r
+ if (dhi + i + 1 >= LA)\r
+ Endj = dhi + i + 1 - LA;\r
+ else\r
+ Endj = 0;\r
+\r
+ if (Endj > LB)\r
+ Endj = LB;\r
+\r
+ asserta(Endj >= Startj);\r
+ }\r
+\r
+ void LogMe() const\r
+ {\r
+ 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
+ LA, LB,\r
+ dlo,\r
+ dlo_mini, dlo_minj,\r
+ dlo_maxi, dlo_maxj,\r
+ dhi,\r
+ dhi_mini, dhi_minj,\r
+ dhi_maxi, dhi_maxj,\r
+ GetMini(), GetMaxi(),\r
+ GetMinj(), GetMaxj());\r
+ }\r
+ };\r
+\r
+typedef const char *(*NWDIAG)(const byte *A, unsigned LA, const byte *B, unsigned LB,
+ unsigned DiagLo, unsigned DiagHi, bool LeftTerm, bool RightTerm);
+
+const char *NWBandWrap(NWDIAG NW, const byte *A, unsigned LA, const byte *B, unsigned LB,
+ unsigned DiagLo, unsigned DiagHi, bool LeftTerm, bool RightTerm);
+\r
+#endif // diagbox_h\r
projects / mothur.git / blobdiff