Chris@0: <?php
Chris@0: /*
Chris@0:  * This file is part of the Diff package.
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@0:         $cFrom = count($from);
Chris@0:         $cTo   = count($to);
Chris@0: 
Chris@0:         if ($cFrom == 0) {
Chris@0:             return array();
Chris@0:         } elseif ($cFrom == 1) {
Chris@0:             if (in_array($from[0], $to)) {
Chris@0:                 return array($from[0]);
Chris@0:             } else {
Chris@0:                 return array();
Chris@0:             }
Chris@0:         } else {
Chris@0:             $i         = intval($cFrom / 2);
Chris@0:             $fromStart = array_slice($from, 0, $i);
Chris@0:             $fromEnd   = array_slice($from, $i);
Chris@0:             $llB       = $this->length($fromStart, $to);
Chris@0:             $llE       = $this->length(array_reverse($fromEnd), array_reverse($to));
Chris@0:             $jMax      = 0;
Chris@0:             $max       = 0;
Chris@0: 
Chris@0:             for ($j = 0; $j <= $cTo; $j++) {
Chris@0:                 $m = $llB[$j] + $llE[$cTo - $j];
Chris@0: 
Chris@0:                 if ($m >= $max) {
Chris@0:                     $max  = $m;
Chris@0:                     $jMax = $j;
Chris@0:                 }
Chris@0:             }
Chris@0: 
Chris@0:             $toStart = array_slice($to, 0, $jMax);
Chris@0:             $toEnd   = array_slice($to, $jMax);
Chris@0: 
Chris@0:             return array_merge(
Chris@0:                 $this->calculate($fromStart, $toStart),
Chris@0:                 $this->calculate($fromEnd, $toEnd)
Chris@0:             );
Chris@0:         }
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@0:         $current = array_fill(0, count($to) + 1, 0);
Chris@0:         $cFrom   = count($from);
Chris@0:         $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@0:                 if ($from[$i] == $to[$j]) {
Chris@0:                     $current[$j + 1] = $prev[$j] + 1;
Chris@0:                 } else {
Chris@0:                     $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: }