Chris@14: <?php declare(strict_types=1);
Chris@14: /*
Chris@14:  * This file is part of sebastian/diff.
Chris@14:  *
Chris@14:  * (c) Sebastian Bergmann <sebastian@phpunit.de>
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 MemoryEfficientLongestCommonSubsequenceCalculator 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:         $cFrom = \count($from);
Chris@14:         $cTo   = \count($to);
Chris@14: 
Chris@14:         if ($cFrom === 0) {
Chris@14:             return [];
Chris@14:         }
Chris@14: 
Chris@14:         if ($cFrom === 1) {
Chris@14:             if (\in_array($from[0], $to, true)) {
Chris@14:                 return [$from[0]];
Chris@14:             }
Chris@14: 
Chris@14:             return [];
Chris@14:         }
Chris@14: 
Chris@14:         $i         = (int) ($cFrom / 2);
Chris@14:         $fromStart = \array_slice($from, 0, $i);
Chris@14:         $fromEnd   = \array_slice($from, $i);
Chris@14:         $llB       = $this->length($fromStart, $to);
Chris@14:         $llE       = $this->length(\array_reverse($fromEnd), \array_reverse($to));
Chris@14:         $jMax      = 0;
Chris@14:         $max       = 0;
Chris@14: 
Chris@14:         for ($j = 0; $j <= $cTo; $j++) {
Chris@14:             $m = $llB[$j] + $llE[$cTo - $j];
Chris@14: 
Chris@14:             if ($m >= $max) {
Chris@14:                 $max  = $m;
Chris@14:                 $jMax = $j;
Chris@14:             }
Chris@14:         }
Chris@14: 
Chris@14:         $toStart = \array_slice($to, 0, $jMax);
Chris@14:         $toEnd   = \array_slice($to, $jMax);
Chris@14: 
Chris@14:         return \array_merge(
Chris@14:             $this->calculate($fromStart, $toStart),
Chris@14:             $this->calculate($fromEnd, $toEnd)
Chris@14:         );
Chris@14:     }
Chris@14: 
Chris@14:     private function length(array $from, array $to): array
Chris@14:     {
Chris@14:         $current = \array_fill(0, \count($to) + 1, 0);
Chris@14:         $cFrom   = \count($from);
Chris@14:         $cTo     = \count($to);
Chris@14: 
Chris@14:         for ($i = 0; $i < $cFrom; $i++) {
Chris@14:             $prev = $current;
Chris@14: 
Chris@14:             for ($j = 0; $j < $cTo; $j++) {
Chris@14:                 if ($from[$i] === $to[$j]) {
Chris@14:                     $current[$j + 1] = $prev[$j] + 1;
Chris@14:                 } else {
Chris@14:                     $current[$j + 1] = \max($current[$j], $prev[$j + 1]);
Chris@14:                 }
Chris@14:             }
Chris@14:         }
Chris@14: 
Chris@14:         return $current;
Chris@14:     }
Chris@14: }