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