binaries/src/muscle/diffpaths.cpp

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