source: trunk/GDE/MUSCLE/src/diffpaths.cpp

#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);
        }