2 #include "diaglist.h"
\r
5 #define MAX(x, y) ((x) > (y) ? (x) : (y))
\r
6 #define MIN(x, y) ((x) < (y) ? (x) : (y))
\r
8 void DiagList::Add(const Diag &d)
\r
10 if (m_uCount == MAX_DIAGS)
\r
11 Quit("DiagList::Add, overflow %u", m_uCount);
\r
12 m_Diags[m_uCount] = d;
\r
16 void DiagList::Add(unsigned uStartPosA, unsigned uStartPosB, unsigned uLength)
\r
19 d.m_uStartPosA = uStartPosA;
\r
20 d.m_uStartPosB = uStartPosB;
\r
21 d.m_uLength = uLength;
\r
25 const Diag &DiagList::Get(unsigned uIndex) const
\r
27 if (uIndex >= m_uCount)
\r
28 Quit("DiagList::Get(%u), count=%u", uIndex, m_uCount);
\r
29 return m_Diags[uIndex];
\r
32 void DiagList::LogMe() const
\r
34 Log("DiagList::LogMe, count=%u\n", m_uCount);
\r
35 Log(" n StartA StartB Length\n");
\r
36 Log("--- ------ ------ ------\n");
\r
37 for (unsigned n = 0; n < m_uCount; ++n)
\r
39 const Diag &d = m_Diags[n];
\r
40 Log("%3u %6u %6u %6u\n",
\r
41 n, d.m_uStartPosA, d.m_uStartPosB, d.m_uLength);
\r
45 void DiagList::FromPath(const PWPath &Path)
\r
49 const unsigned uEdgeCount = Path.GetEdgeCount();
\r
50 unsigned uLength = 0;
\r
51 unsigned uStartPosA;
\r
52 unsigned uStartPosB;
\r
53 for (unsigned uEdgeIndex = 0; uEdgeIndex < uEdgeCount; ++uEdgeIndex)
\r
55 const PWEdge &Edge = Path.GetEdge(uEdgeIndex);
\r
58 if (Edge.cType == 'M')
\r
62 uStartPosA = Edge.uPrefixLengthA - 1;
\r
63 uStartPosB = Edge.uPrefixLengthB - 1;
\r
69 if (uLength >= g_uMinDiagLength)
\r
70 Add(uStartPosA, uStartPosB, uLength);
\r
75 // Special case for last edge
\r
76 if (uLength >= g_uMinDiagLength)
\r
77 Add(uStartPosA, uStartPosB, uLength);
\r
80 bool DiagList::NonZeroIntersection(const Diag &d) const
\r
82 for (unsigned n = 0; n < m_uCount; ++n)
\r
84 const Diag &d2 = m_Diags[n];
\r
85 if (DiagOverlap(d, d2) > 0)
\r
91 // DialogOverlap returns the length of the overlapping
\r
92 // section of the two diagonals along the diagonals
\r
93 // themselves; in other words, the length of
\r
94 // the intersection of the two sets of cells in
\r
96 unsigned DiagOverlap(const Diag &d1, const Diag &d2)
\r
98 // Determine where the diagonals intersect the A
\r
99 // axis (extending them if required). If they
\r
100 // intersect at different points, they do not
\r
101 // overlap. Coordinates on a diagonal are
\r
102 // given by B = A + c where c is the value of
\r
103 // A at the intersection with the A axis.
\r
104 // Hence, c = B - A for any point on the diagonal.
\r
105 int c1 = (int) d1.m_uStartPosB - (int) d1.m_uStartPosA;
\r
106 int c2 = (int) d2.m_uStartPosB - (int) d2.m_uStartPosA;
\r
110 assert(DiagOverlapA(d1, d2) == DiagOverlapB(d1, d2));
\r
111 return DiagOverlapA(d1, d2);
\r
114 // DialogOverlapA returns the length of the overlapping
\r
115 // section of the projection of the two diagonals onto
\r
117 unsigned DiagOverlapA(const Diag &d1, const Diag &d2)
\r
119 unsigned uMaxStart = MAX(d1.m_uStartPosA, d2.m_uStartPosA);
\r
120 unsigned uMinEnd = MIN(d1.m_uStartPosA + d1.m_uLength - 1,
\r
121 d2.m_uStartPosA + d2.m_uLength - 1);
\r
123 int iLength = (int) uMinEnd - (int) uMaxStart + 1;
\r
126 return (unsigned) iLength;
\r
129 // DialogOverlapB returns the length of the overlapping
\r
130 // section of the projection of the two diagonals onto
\r
132 unsigned DiagOverlapB(const Diag &d1, const Diag &d2)
\r
134 unsigned uMaxStart = MAX(d1.m_uStartPosB, d2.m_uStartPosB);
\r
135 unsigned uMinEnd = MIN(d1.m_uStartPosB + d1.m_uLength - 1,
\r
136 d2.m_uStartPosB + d2.m_uLength - 1);
\r
138 int iLength = (int) uMinEnd - (int) uMaxStart + 1;
\r
141 return (unsigned) iLength;
\r
144 // Returns true if the two diagonals can be on the
\r
145 // same path through the DP matrix. If DiagCompatible
\r
146 // returns false, they cannot be in the same path
\r
147 // and hence "contradict" each other.
\r
148 bool DiagCompatible(const Diag &d1, const Diag &d2)
\r
150 if (DiagOverlap(d1, d2) > 0)
\r
152 return 0 == DiagOverlapA(d1, d2) && 0 == DiagOverlapB(d1, d2);
\r
155 // Returns the length of the "break" between two diagonals.
\r
156 unsigned DiagBreak(const Diag &d1, const Diag &d2)
\r
158 int c1 = (int) d1.m_uStartPosB - (int) d1.m_uStartPosA;
\r
159 int c2 = (int) d2.m_uStartPosB - (int) d2.m_uStartPosA;
\r
163 int iMaxStart = MAX(d1.m_uStartPosA, d2.m_uStartPosA);
\r
164 int iMinEnd = MIN(d1.m_uStartPosA + d1.m_uLength - 1,
\r
165 d2.m_uStartPosA + d1.m_uLength - 1);
\r
166 int iBreak = iMaxStart - iMinEnd - 1;
\r
169 return (unsigned) iBreak;
\r
172 // Merge diagonals that are continuations of each other with
\r
173 // short breaks of up to length g_uMaxDiagBreak.
\r
174 // In a sorted list of diagonals, we only have to check
\r
175 // consecutive entries.
\r
176 void MergeDiags(DiagList &DL)
\r
180 if (!DL.IsSorted())
\r
181 Quit("MergeDiags: !IsSorted");
\r
185 // Breaks must be with no offset (no gaps)
\r
186 const unsigned uCount = DL.GetCount();
\r
193 const Diag *ptrPrev = &DL.Get(0);
\r
194 for (unsigned i = 1; i < uCount; ++i)
\r
196 const Diag *ptrDiag = &DL.Get(i);
\r
197 unsigned uBreakLength = DiagBreak(*ptrPrev, *ptrDiag);
\r
198 if (uBreakLength <= g_uMaxDiagBreak)
\r
200 MergedDiag.m_uStartPosA = ptrPrev->m_uStartPosA;
\r
201 MergedDiag.m_uStartPosB = ptrPrev->m_uStartPosB;
\r
202 MergedDiag.m_uLength = ptrPrev->m_uLength + ptrDiag->m_uLength
\r
204 ptrPrev = &MergedDiag;
\r
208 NewList.Add(*ptrPrev);
\r
212 NewList.Add(*ptrPrev);
\r
216 void DiagList::DeleteIncompatible()
\r
218 assert(IsSorted());
\r
223 bool *bFlagForDeletion = new bool[m_uCount];
\r
224 for (unsigned i = 0; i < m_uCount; ++i)
\r
225 bFlagForDeletion[i] = false;
\r
227 for (unsigned i = 0; i < m_uCount; ++i)
\r
229 const Diag &di = m_Diags[i];
\r
230 for (unsigned j = i + 1; j < m_uCount; ++j)
\r
232 const Diag &dj = m_Diags[j];
\r
234 // Verify sorted correctly
\r
235 assert(di.m_uStartPosA <= dj.m_uStartPosA);
\r
237 // If two diagonals are incompatible and
\r
238 // one is is much longer than the other,
\r
239 // keep the longer one.
\r
240 if (!DiagCompatible(di, dj))
\r
242 if (di.m_uLength > dj.m_uLength*4)
\r
243 bFlagForDeletion[j] = true;
\r
244 else if (dj.m_uLength > di.m_uLength*4)
\r
245 bFlagForDeletion[i] = true;
\r
248 bFlagForDeletion[i] = true;
\r
249 bFlagForDeletion[j] = true;
\r
255 for (unsigned i = 0; i < m_uCount; ++i)
\r
257 const Diag &di = m_Diags[i];
\r
258 if (bFlagForDeletion[i])
\r
261 for (unsigned j = i + 1; j < m_uCount; ++j)
\r
263 const Diag &dj = m_Diags[j];
\r
264 if (bFlagForDeletion[j])
\r
267 // Verify sorted correctly
\r
268 assert(di.m_uStartPosA <= dj.m_uStartPosA);
\r
270 // If sort order in B different from sorted order in A,
\r
271 // either diags are incompatible or we detected a repeat
\r
273 if (di.m_uStartPosB >= dj.m_uStartPosB || !DiagCompatible(di, dj))
\r
275 bFlagForDeletion[i] = true;
\r
276 bFlagForDeletion[j] = true;
\r
281 unsigned uNewCount = 0;
\r
282 Diag *NewDiags = new Diag[m_uCount];
\r
283 for (unsigned i = 0; i < m_uCount; ++i)
\r
285 if (bFlagForDeletion[i])
\r
288 const Diag &d = m_Diags[i];
\r
289 NewDiags[uNewCount] = d;
\r
292 memcpy(m_Diags, NewDiags, uNewCount*sizeof(Diag));
\r
293 m_uCount = uNewCount;
\r
297 void DiagList::Copy(const DiagList &DL)
\r
300 unsigned uCount = DL.GetCount();
\r
301 for (unsigned i = 0; i < uCount; ++i)
\r
305 // Check if sorted in increasing order of m_uStartPosA
\r
306 bool DiagList::IsSorted() const
\r
309 unsigned uCount = GetCount();
\r
310 for (unsigned i = 1; i < uCount; ++i)
\r
311 if (m_Diags[i-1].m_uStartPosA > m_Diags[i].m_uStartPosA)
\r
316 // Sort in increasing order of m_uStartPosA
\r
317 // Dumb bubble sort, but don't care about speed
\r
318 // because don't get long lists.
\r
319 void DiagList::Sort()
\r
324 bool bContinue = true;
\r
328 for (unsigned i = 0; i < m_uCount - 1; ++i)
\r
330 if (m_Diags[i].m_uStartPosA > m_Diags[i+1].m_uStartPosA)
\r
332 Diag Tmp = m_Diags[i];
\r
333 m_Diags[i] = m_Diags[i+1];
\r
334 m_Diags[i+1] = Tmp;
\r
347 // d1.m_uStartPosA = 0;
\r
348 // d1.m_uStartPosB = 1;
\r
349 // d1.m_uLength = 32;
\r
351 // d2.m_uStartPosA = 55;
\r
352 // d2.m_uStartPosB = 70;
\r
353 // d2.m_uLength = 36;
\r
355 // d3.m_uStartPosA = 102;
\r
356 // d3.m_uStartPosB = 122;
\r
357 // d3.m_uLength = 50;
\r
364 // Log("Before DeleteIncompatible:\n");
\r
366 // DL.DeleteIncompatible();
\r
368 // Log("After DeleteIncompatible:\n");
\r
372 // Log("After Merge:\n");
\r
375 // DPRegionList RL;
\r
376 // DiagListToDPRegionList(DL, RL, 200, 200);
\r