Exception
1 year ago
Output
1 year ago
Chunk.php
1 year ago
Diff.php
1 year ago
Differ.php
1 year ago
Line.php
1 year ago
LongestCommonSubsequenceCalculator.php
1 year ago
MemoryEfficientLongestCommonSubsequenceCalculator.php
1 year ago
Parser.php
1 year ago
TimeEfficientLongestCommonSubsequenceCalculator.php
1 year ago
TimeEfficientLongestCommonSubsequenceCalculator.php
83 lines
| 1 | <?php declare(strict_types=1); |
| 2 | /* |
| 3 | * This file is part of sebastian/diff. |
| 4 | * |
| 5 | * (c) Sebastian Bergmann <sebastian@phpunit.de> |
| 6 | * |
| 7 | * For the full copyright and license information, please view the LICENSE |
| 8 | * file that was distributed with this source code. |
| 9 | */ |
| 10 | namespace SebastianBergmann\Diff; |
| 11 | |
| 12 | use function array_reverse; |
| 13 | use function count; |
| 14 | use function max; |
| 15 | use SplFixedArray; |
| 16 | |
| 17 | final class TimeEfficientLongestCommonSubsequenceCalculator implements LongestCommonSubsequenceCalculator |
| 18 | { |
| 19 | /** |
| 20 | * {@inheritdoc} |
| 21 | */ |
| 22 | public function calculate(array $from, array $to): array |
| 23 | { |
| 24 | $common = []; |
| 25 | $fromLength = count($from); |
| 26 | $toLength = count($to); |
| 27 | $width = $fromLength + 1; |
| 28 | $matrix = new SplFixedArray($width * ($toLength + 1)); |
| 29 | |
| 30 | for ($i = 0; $i <= $fromLength; ++$i) { |
| 31 | $matrix[$i] = 0; |
| 32 | } |
| 33 | |
| 34 | for ($j = 0; $j <= $toLength; ++$j) { |
| 35 | $matrix[$j * $width] = 0; |
| 36 | } |
| 37 | |
| 38 | for ($i = 1; $i <= $fromLength; ++$i) { |
| 39 | for ($j = 1; $j <= $toLength; ++$j) { |
| 40 | $o = ($j * $width) + $i; |
| 41 | |
| 42 | // don't use max() to avoid function call overhead |
| 43 | $firstOrLast = $from[$i - 1] === $to[$j - 1] ? $matrix[$o - $width - 1] + 1 : 0; |
| 44 | |
| 45 | if ($matrix[$o - 1] > $matrix[$o - $width]) { |
| 46 | if ($firstOrLast > $matrix[$o - 1]) { |
| 47 | $matrix[$o] = $firstOrLast; |
| 48 | } else { |
| 49 | $matrix[$o] = $matrix[$o - 1]; |
| 50 | } |
| 51 | } else { |
| 52 | if ($firstOrLast > $matrix[$o - $width]) { |
| 53 | $matrix[$o] = $firstOrLast; |
| 54 | } else { |
| 55 | $matrix[$o] = $matrix[$o - $width]; |
| 56 | } |
| 57 | } |
| 58 | } |
| 59 | } |
| 60 | |
| 61 | $i = $fromLength; |
| 62 | $j = $toLength; |
| 63 | |
| 64 | while ($i > 0 && $j > 0) { |
| 65 | if ($from[$i - 1] === $to[$j - 1]) { |
| 66 | $common[] = $from[$i - 1]; |
| 67 | --$i; |
| 68 | --$j; |
| 69 | } else { |
| 70 | $o = ($j * $width) + $i; |
| 71 | |
| 72 | if ($matrix[$o - $width] > $matrix[$o - 1]) { |
| 73 | --$j; |
| 74 | } else { |
| 75 | --$i; |
| 76 | } |
| 77 | } |
| 78 | } |
| 79 | |
| 80 | return array_reverse($common); |
| 81 | } |
| 82 | } |
| 83 |