Mercurial > hg > isophonics-drupal-site
annotate vendor/sebastian/diff/src/TimeEfficientLongestCommonSubsequenceCalculator.php @ 19:fa3358dc1485 tip
Add ndrum files
author | Chris Cannam |
---|---|
date | Wed, 28 Aug 2019 13:14:47 +0100 |
parents | 1fec387a4317 |
children |
rev | line source |
---|---|
Chris@14 | 1 <?php declare(strict_types=1); |
Chris@14 | 2 /* |
Chris@14 | 3 * This file is part of sebastian/diff. |
Chris@14 | 4 * |
Chris@14 | 5 * (c) Sebastian Bergmann <sebastian@phpunit.de> |
Chris@14 | 6 * |
Chris@14 | 7 * For the full copyright and license information, please view the LICENSE |
Chris@14 | 8 * file that was distributed with this source code. |
Chris@14 | 9 */ |
Chris@14 | 10 |
Chris@14 | 11 namespace SebastianBergmann\Diff; |
Chris@14 | 12 |
Chris@14 | 13 final class TimeEfficientLongestCommonSubsequenceCalculator implements LongestCommonSubsequenceCalculator |
Chris@14 | 14 { |
Chris@14 | 15 /** |
Chris@14 | 16 * {@inheritdoc} |
Chris@14 | 17 */ |
Chris@14 | 18 public function calculate(array $from, array $to): array |
Chris@14 | 19 { |
Chris@14 | 20 $common = []; |
Chris@14 | 21 $fromLength = \count($from); |
Chris@14 | 22 $toLength = \count($to); |
Chris@14 | 23 $width = $fromLength + 1; |
Chris@14 | 24 $matrix = new \SplFixedArray($width * ($toLength + 1)); |
Chris@14 | 25 |
Chris@14 | 26 for ($i = 0; $i <= $fromLength; ++$i) { |
Chris@14 | 27 $matrix[$i] = 0; |
Chris@14 | 28 } |
Chris@14 | 29 |
Chris@14 | 30 for ($j = 0; $j <= $toLength; ++$j) { |
Chris@14 | 31 $matrix[$j * $width] = 0; |
Chris@14 | 32 } |
Chris@14 | 33 |
Chris@14 | 34 for ($i = 1; $i <= $fromLength; ++$i) { |
Chris@14 | 35 for ($j = 1; $j <= $toLength; ++$j) { |
Chris@14 | 36 $o = ($j * $width) + $i; |
Chris@14 | 37 $matrix[$o] = \max( |
Chris@14 | 38 $matrix[$o - 1], |
Chris@14 | 39 $matrix[$o - $width], |
Chris@14 | 40 $from[$i - 1] === $to[$j - 1] ? $matrix[$o - $width - 1] + 1 : 0 |
Chris@14 | 41 ); |
Chris@14 | 42 } |
Chris@14 | 43 } |
Chris@14 | 44 |
Chris@14 | 45 $i = $fromLength; |
Chris@14 | 46 $j = $toLength; |
Chris@14 | 47 |
Chris@14 | 48 while ($i > 0 && $j > 0) { |
Chris@14 | 49 if ($from[$i - 1] === $to[$j - 1]) { |
Chris@14 | 50 $common[] = $from[$i - 1]; |
Chris@14 | 51 --$i; |
Chris@14 | 52 --$j; |
Chris@14 | 53 } else { |
Chris@14 | 54 $o = ($j * $width) + $i; |
Chris@14 | 55 |
Chris@14 | 56 if ($matrix[$o - $width] > $matrix[$o - 1]) { |
Chris@14 | 57 --$j; |
Chris@14 | 58 } else { |
Chris@14 | 59 --$i; |
Chris@14 | 60 } |
Chris@14 | 61 } |
Chris@14 | 62 } |
Chris@14 | 63 |
Chris@14 | 64 return \array_reverse($common); |
Chris@14 | 65 } |
Chris@14 | 66 } |