1<?php 2/* 3 * This file is part of sebastian/diff. 4 * 5 * (c) Sebastian Bergmann <sebastian@phpunit.de> 6 * 7 * For the full copyright and license information, please view the LICENSE 8 * file that was distributed with this source code. 9 */ 10 11namespace SebastianBergmann\Diff\LCS; 12 13/** 14 * Memory-efficient implementation of longest common subsequence calculation. 15 */ 16class MemoryEfficientImplementation implements LongestCommonSubsequence 17{ 18 /** 19 * Calculates the longest common subsequence of two arrays. 20 * 21 * @param array $from 22 * @param array $to 23 * 24 * @return array 25 */ 26 public function calculate(array $from, array $to) 27 { 28 $cFrom = \count($from); 29 $cTo = \count($to); 30 31 if ($cFrom === 0) { 32 return array(); 33 } 34 35 if ($cFrom === 1) { 36 if (\in_array($from[0], $to, true)) { 37 return array($from[0]); 38 } 39 40 return array(); 41 } 42 43 $i = (int) ($cFrom / 2); 44 $fromStart = \array_slice($from, 0, $i); 45 $fromEnd = \array_slice($from, $i); 46 $llB = $this->length($fromStart, $to); 47 $llE = $this->length(\array_reverse($fromEnd), \array_reverse($to)); 48 $jMax = 0; 49 $max = 0; 50 51 for ($j = 0; $j <= $cTo; $j++) { 52 $m = $llB[$j] + $llE[$cTo - $j]; 53 54 if ($m >= $max) { 55 $max = $m; 56 $jMax = $j; 57 } 58 } 59 60 $toStart = \array_slice($to, 0, $jMax); 61 $toEnd = \array_slice($to, $jMax); 62 63 return \array_merge( 64 $this->calculate($fromStart, $toStart), 65 $this->calculate($fromEnd, $toEnd) 66 ); 67 } 68 69 /** 70 * @param array $from 71 * @param array $to 72 * 73 * @return array 74 */ 75 private function length(array $from, array $to) 76 { 77 $current = \array_fill(0, \count($to) + 1, 0); 78 $cFrom = \count($from); 79 $cTo = \count($to); 80 81 for ($i = 0; $i < $cFrom; $i++) { 82 $prev = $current; 83 84 for ($j = 0; $j < $cTo; $j++) { 85 if ($from[$i] === $to[$j]) { 86 $current[$j + 1] = $prev[$j] + 1; 87 } else { 88 $current[$j + 1] = \max($current[$j], $prev[$j + 1]); 89 } 90 } 91 } 92 93 return $current; 94 } 95} 96