static SMSRD SMS()

in src/dotnet/APIView/APIView/DIff/Diff.cs [266:386]


        static SMSRD SMS<T>(DiffData<T> dataA, int lowerA, int upperA, DiffData<T> dataB, int lowerB, int upperB, int[] downVector, int[] upVector) where T: IEquatable<T>
        {
            SMSRD ret;
            int MAX = dataA.Length + dataB.Length + 1;

            int downK = lowerA - lowerB;
            // the k-line to start the forward search
            int upK = upperA - upperB;
            // the k-line to start the reverse search
            int delta = (upperA - lowerA) - (upperB - lowerB);
            bool oddDelta = (delta & 1) != 0;

            // The vectors in the publication accepts negative indexes. the vectors implemented here are 0-based
            // and are access using a specific offset: UpOffset UpVector and DownOffset for DownVektor
            int downOffset = MAX - downK;
            int upOffset = MAX - upK;

            int MaxD = ((upperA - lowerA + upperB - lowerB) / 2) + 1;

            // Debug.Write(2, "SMS", String.Format("Search the box: A[{0}-{1}] to B[{2}-{3}]", LowerA, UpperA, LowerB, UpperB));

            // init vectors
            downVector[downOffset + downK + 1] = lowerA;
            upVector[upOffset + upK - 1] = upperA;

            for (int D = 0; D <= MaxD; D++)
            {

                // Extend the forward path.
                for (int k = downK - D; k <= downK + D; k += 2)
                {
                    // Debug.Write(0, "SMS", "extend forward path " + k.ToString());

                    // find the only or better starting point
                    int x, y;
                    if (k == downK - D)
                    {
                        x = downVector[downOffset + k + 1];
                        // down
                    }
                    else
                    {
                        x = downVector[downOffset + k - 1] + 1;
                        // a step to the right
                        if (k < downK + D && downVector[downOffset + k + 1] >= x)
                            x = downVector[downOffset + k + 1];
                        // down
                    }
                    y = x - k;

                    // find the end of the furthest reaching forward D-path in diagonal k.
                    while (x < upperA && y < upperB && dataA.Data[x].Equals(dataB.Data[y]))
                    {
                        x++;
                        y++;
                    }
                    downVector[downOffset + k] = x;

                    // overlap ?
                    if (oddDelta && upK - D < k && k < upK + D)
                    {
                        if (upVector[upOffset + k] <= downVector[downOffset + k])
                        {
                            ret.x = downVector[downOffset + k];
                            ret.y = downVector[downOffset + k] - k;
                            return (ret);
                        }
                        // if
                    }
                    // if
                }
                // for k
                // Extend the reverse path.
                for (int k = upK - D; k <= upK + D; k += 2)
                {
                    // Debug.Write(0, "SMS", "extend reverse path " + k.ToString());

                    // find the only or better starting point
                    int x, y;
                    if (k == upK + D)
                    {
                        x = upVector[upOffset + k - 1];
                        // up
                    }
                    else
                    {
                        x = upVector[upOffset + k + 1] - 1;
                        // left
                        if (k > upK - D && upVector[upOffset + k - 1] < x)
                            x = upVector[upOffset + k - 1];
                        // up
                    }
                    // if
                    y = x - k;

                    while (x > lowerA && y > lowerB && dataA.Data[x - 1].Equals(dataB.Data[y - 1]))
                    {
                        x--;
                        y--;
                        // diagonal
                    }
                    upVector[upOffset + k] = x;

                    // overlap ?
                    if (!oddDelta && downK - D <= k && k <= downK + D)
                    {
                        if (upVector[upOffset + k] <= downVector[downOffset + k])
                        {
                            ret.x = downVector[downOffset + k];
                            ret.y = downVector[downOffset + k] - k;
                            return (ret);
                        }
                        // if
                    }
                    // if
                }
                // for k
            }
            // for D
            throw new ApplicationException("the algorithm should never come here.");
        }