Chris@14: Chris@14: * Chris@14: * For the full copyright and license information, please view the LICENSE Chris@14: * file that was distributed with this source code. Chris@14: */ Chris@14: Chris@14: namespace SebastianBergmann\Diff; Chris@14: Chris@14: final class TimeEfficientLongestCommonSubsequenceCalculator implements LongestCommonSubsequenceCalculator Chris@14: { Chris@14: /** Chris@14: * {@inheritdoc} Chris@14: */ Chris@14: public function calculate(array $from, array $to): array Chris@14: { Chris@14: $common = []; Chris@14: $fromLength = \count($from); Chris@14: $toLength = \count($to); Chris@14: $width = $fromLength + 1; Chris@14: $matrix = new \SplFixedArray($width * ($toLength + 1)); Chris@14: Chris@14: for ($i = 0; $i <= $fromLength; ++$i) { Chris@14: $matrix[$i] = 0; Chris@14: } Chris@14: Chris@14: for ($j = 0; $j <= $toLength; ++$j) { Chris@14: $matrix[$j * $width] = 0; Chris@14: } Chris@14: Chris@14: for ($i = 1; $i <= $fromLength; ++$i) { Chris@14: for ($j = 1; $j <= $toLength; ++$j) { Chris@14: $o = ($j * $width) + $i; Chris@14: $matrix[$o] = \max( Chris@14: $matrix[$o - 1], Chris@14: $matrix[$o - $width], Chris@14: $from[$i - 1] === $to[$j - 1] ? $matrix[$o - $width - 1] + 1 : 0 Chris@14: ); Chris@14: } Chris@14: } Chris@14: Chris@14: $i = $fromLength; Chris@14: $j = $toLength; Chris@14: Chris@14: while ($i > 0 && $j > 0) { Chris@14: if ($from[$i - 1] === $to[$j - 1]) { Chris@14: $common[] = $from[$i - 1]; Chris@14: --$i; Chris@14: --$j; Chris@14: } else { Chris@14: $o = ($j * $width) + $i; Chris@14: Chris@14: if ($matrix[$o - $width] > $matrix[$o - 1]) { Chris@14: --$j; Chris@14: } else { Chris@14: --$i; Chris@14: } Chris@14: } Chris@14: } Chris@14: Chris@14: return \array_reverse($common); Chris@14: } Chris@14: }