Chris@2: <?php declare(strict_types=1);
Chris@2: /*
Chris@2:  * This file is part of sebastian/diff.
Chris@2:  *
Chris@2:  * (c) Sebastian Bergmann <sebastian@phpunit.de>
Chris@2:  *
Chris@2:  * For the full copyright and license information, please view the LICENSE
Chris@2:  * file that was distributed with this source code.
Chris@2:  */
Chris@2: 
Chris@2: namespace SebastianBergmann\Diff;
Chris@2: 
Chris@2: final class MemoryEfficientLongestCommonSubsequenceCalculator implements LongestCommonSubsequenceCalculator
Chris@2: {
Chris@2:     /**
Chris@2:      * {@inheritdoc}
Chris@2:      */
Chris@2:     public function calculate(array $from, array $to): array
Chris@2:     {
Chris@2:         $cFrom = \count($from);
Chris@2:         $cTo   = \count($to);
Chris@2: 
Chris@2:         if ($cFrom === 0) {
Chris@2:             return [];
Chris@2:         }
Chris@2: 
Chris@2:         if ($cFrom === 1) {
Chris@2:             if (\in_array($from[0], $to, true)) {
Chris@2:                 return [$from[0]];
Chris@2:             }
Chris@2: 
Chris@2:             return [];
Chris@2:         }
Chris@2: 
Chris@2:         $i         = (int) ($cFrom / 2);
Chris@2:         $fromStart = \array_slice($from, 0, $i);
Chris@2:         $fromEnd   = \array_slice($from, $i);
Chris@2:         $llB       = $this->length($fromStart, $to);
Chris@2:         $llE       = $this->length(\array_reverse($fromEnd), \array_reverse($to));
Chris@2:         $jMax      = 0;
Chris@2:         $max       = 0;
Chris@2: 
Chris@2:         for ($j = 0; $j <= $cTo; $j++) {
Chris@2:             $m = $llB[$j] + $llE[$cTo - $j];
Chris@2: 
Chris@2:             if ($m >= $max) {
Chris@2:                 $max  = $m;
Chris@2:                 $jMax = $j;
Chris@2:             }
Chris@2:         }
Chris@2: 
Chris@2:         $toStart = \array_slice($to, 0, $jMax);
Chris@2:         $toEnd   = \array_slice($to, $jMax);
Chris@2: 
Chris@2:         return \array_merge(
Chris@2:             $this->calculate($fromStart, $toStart),
Chris@2:             $this->calculate($fromEnd, $toEnd)
Chris@2:         );
Chris@2:     }
Chris@2: 
Chris@2:     private function length(array $from, array $to): array
Chris@2:     {
Chris@2:         $current = \array_fill(0, \count($to) + 1, 0);
Chris@2:         $cFrom   = \count($from);
Chris@2:         $cTo     = \count($to);
Chris@2: 
Chris@2:         for ($i = 0; $i < $cFrom; $i++) {
Chris@2:             $prev = $current;
Chris@2: 
Chris@2:             for ($j = 0; $j < $cTo; $j++) {
Chris@2:                 if ($from[$i] === $to[$j]) {
Chris@2:                     $current[$j + 1] = $prev[$j] + 1;
Chris@2:                 } else {
Chris@2:                     $current[$j + 1] = \max($current[$j], $prev[$j + 1]);
Chris@2:                 }
Chris@2:             }
Chris@2:         }
Chris@2: 
Chris@2:         return $current;
Chris@2:     }
Chris@2: }