SN\DaisyDiff\RangeDifferencer\OldDifferencer::findDifferences()

Complexity

Conditions	22
Paths	192

Size

Total Lines	99
Code Lines	46

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	44
CRAP Score	22

Importance

Changes

0

<?php
    public static function findDifferences(RangeComparatorInterface $left, RangeComparatorInterface $right): array
    {
        // Assert that both RangeComparatorInterface are of the same class.
        \assert(\get_class($right) === \get_class($left));

        $rightSize = $right->getRangeCount();
        $leftSize = $left->getRangeCount();

        // Differences matrix:
        // Only the last d of each diagonal is stored, i.e., $lastDiagonal[$k] = row of d
        $diagLen = (int) (2 * \max($rightSize, $leftSize));
        $maxDiagonal = $diagLen;

        /** @var int[] The row containing the last d */
        $lastDiagonal = \array_fill(0, $diagLen + 1, 0);

        // On diagonal $k ($lastDiagonal[$k] = $row
        $origin = (int) ($diagLen / 2);

        // Script corresponding to $d[$k]
        /** @var LinkedRangeDifference[] $script */
        $script = \array_fill(0, $diagLen + 1, null);
        $row = 0;

        // Find common prefix.
        for (;$row < $rightSize && $row < $leftSize && self::rangesEqual($right, $row, $left, $row);) {
            $row++;
        }

        $lastDiagonal[$origin] = $row;
        $script[$origin] = null;

        $lower = ($row === $rightSize) ? $origin + 1 : $origin - 1;
        $upper = ($row === $leftSize) ? $origin - 1 : $origin + 1;

        if ($lower > $upper) {
            return [];
        }

        // For each value of the edit distance.
        for ($d = 1; $d <= $maxDiagonal; $d++) {
            // $d is the current edit distance.

            if ($right->skipRangeComparison($d, $maxDiagonal, $left)) {
                // This condition always returns false, so the following code is never executed.
                // It should be something we already found.
                return []; // @codeCoverageIgnore
            }

            // For each relevant diagonal (-d, -d+2, ... d-2, d)
            for ($k = $lower; $k <= $upper; $k += 2) {
                // $k is the current diagonal.
                if ($k === $origin - $d || $k !== $origin + $d && $lastDiagonal[$k + 1] >= $lastDiagonal[$k - 1]) {
                    // Move down.
                    $row = $lastDiagonal[$k + 1] + 1;
                    $edit = new LinkedRangeDifference($script[$k + 1], LinkedRangeDifference::DELETE);
                } else {
                    // Move right.
                    $row = $lastDiagonal[$k - 1];
                    $edit = new LinkedRangeDifference($script[$k - 1], LinkedRangeDifference::INSERT);
                }

                $col = $row + $k - $origin;

                $edit->setRightStart($row);
                $edit->setLeftStart($col);

                \assert($k >= 0 && $k <= $maxDiagonal);
                $script[$k] = $edit;

                // Slide down the diagonal as far as possible.
                while ($row < $rightSize && $col < $leftSize && self::rangesEqual($right, $row, $left, $col)) {
                    $row++;
                    $col++;
                }

                // Unreasonable value for diagonal index.
                \assert($k >= 0 && $k <= $maxDiagonal);
                $lastDiagonal[$k] = $row;

                if ($row === $rightSize && $col === $leftSize) {
                    return self::createRangeDifferences($script[$k]);
                }

                if ($row === $rightSize) {
                    $lower = $k + 2;
                }

                if ($col === $leftSize) {
                    $upper = $k - 2;
                }
            }

            $lower--;
            $upper++;
        }

        // Too many differences.
        throw new \RuntimeException(); // @codeCoverageIgnore
    }