1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
#include "muscle.h"
#include "pwpath.h"
#define TRACE 0
void DiffPaths(const PWPath &p1, const PWPath &p2, unsigned Edges1[],
unsigned *ptruDiffCount1, unsigned Edges2[], unsigned *ptruDiffCount2)
{
#if TRACE
Log("DiffPaths\n");
Log("p1=");
p1.LogMe();
Log("p2=");
p2.LogMe();
#endif
const unsigned uEdgeCount1 = p1.GetEdgeCount();
const unsigned uEdgeCount2 = p2.GetEdgeCount();
unsigned uDiffCount1 = 0;
unsigned uDiffCount2 = 0;
unsigned uEdgeIndex1 = 0;
unsigned uEdgeIndex2 = 0;
const PWEdge *Edge1 = &p1.GetEdge(uEdgeIndex1);
const PWEdge *Edge2 = &p2.GetEdge(uEdgeIndex2);
for (;;)
{
unsigned uEdgeIndexTop1 = uEdgeIndex1;
unsigned uEdgeIndexTop2 = uEdgeIndex2;
Edge1 = &p1.GetEdge(uEdgeIndex1);
Edge2 = &p2.GetEdge(uEdgeIndex2);
#if TRACE
Log("e1[%u] PLA%u PLB%u %c, e2[%u] PLA%u PLB %u %c DC1=%u DC2=%u\n",
uEdgeIndex1, Edge1->uPrefixLengthA, Edge1->uPrefixLengthB, Edge1->cType,
uEdgeIndex2, Edge2->uPrefixLengthA, Edge2->uPrefixLengthB, Edge2->cType,
uDiffCount1, uDiffCount2);
#endif
if (Edge1->uPrefixLengthA == Edge2->uPrefixLengthA &&
Edge1->uPrefixLengthB == Edge2->uPrefixLengthB)
{
if (!Edge1->Equal(*Edge2))
{
Edges1[uDiffCount1++] = uEdgeIndex1;
Edges2[uDiffCount2++] = uEdgeIndex2;
}
++uEdgeIndex1;
++uEdgeIndex2;
}
else if (Edge2->uPrefixLengthA < Edge1->uPrefixLengthA ||
Edge2->uPrefixLengthB < Edge1->uPrefixLengthB)
Edges2[uDiffCount2++] = uEdgeIndex2++;
else if (Edge1->uPrefixLengthA < Edge2->uPrefixLengthA ||
Edge1->uPrefixLengthB < Edge2->uPrefixLengthB)
Edges1[uDiffCount1++] = uEdgeIndex1++;
if (uEdgeCount1 == uEdgeIndex1)
{
while (uEdgeIndex2 < uEdgeCount2)
Edges2[uDiffCount2++] = uEdgeIndex2++;
goto Done;
}
if (uEdgeCount2 == uEdgeIndex2)
{
while (uEdgeIndex1 < uEdgeCount1)
Edges1[uDiffCount1++] = uEdgeIndex1++;
goto Done;
}
if (uEdgeIndex1 == uEdgeIndexTop1 && uEdgeIndex2 == uEdgeIndexTop2)
Quit("DiffPaths stuck");
}
Done:;
#if TRACE
Log("DiffCount1=%u (%u %u)\n", uDiffCount1, uEdgeCount1, uEdgeCount2);
Log("Diffs1=");
for (unsigned i = 0; i < uDiffCount1; ++i)
{
const PWEdge e = p1.GetEdge(Edges1[i]);
Log(" %u=%c%u.%u", Edges1[i], e.cType, e.uPrefixLengthA, e.uPrefixLengthB);
}
Log("\n");
Log("DiffCount2=%u\n", uDiffCount2);
Log("Diffs2=");
for (unsigned i = 0; i < uDiffCount2; ++i)
{
const PWEdge e = p2.GetEdge(Edges2[i]);
Log(" %u=%c%u.%u", Edges2[i], e.cType, e.uPrefixLengthA, e.uPrefixLengthB);
}
Log("\n");
#endif
*ptruDiffCount1 = uDiffCount1;
*ptruDiffCount2 = uDiffCount2;
}
void TestDiffPaths()
{
PWPath p1;
PWPath p2;
p1.AppendEdge('M', 1, 1);
p1.AppendEdge('M', 2, 2);
p1.AppendEdge('M', 3, 3);
p2.AppendEdge('M', 1, 1);
p2.AppendEdge('D', 2, 1);
p2.AppendEdge('I', 2, 2);
p2.AppendEdge('M', 3, 3);
unsigned Edges1[64];
unsigned Edges2[64];
unsigned uDiffCount1;
unsigned uDiffCount2;
DiffPaths(p1, p2, Edges1, &uDiffCount1, Edges2, &uDiffCount2);
}
|
