EVOLUTION-NINJA

Edit File: MemoryEfficientLongestCommonSubsequenceImplementation.php

<?php
/*
 * This file is part of the Diff package.
 *
 * (c) Sebastian Bergmann <sebastian@phpunit.de>
 *
 * For the full copyright and license information, please view the LICENSE
 * file that was distributed with this source code.
 */

namespace SebastianBergmann\Diff\LCS;

/**
 * Memory-efficient implementation of longest common subsequence calculation.
 */
class MemoryEfficientImplementation implements LongestCommonSubsequence
{
    /**
     * Calculates the longest common subsequence of two arrays.
     *
     * @param array $from
     * @param array $to
     *
     * @return array
     */
    public function calculate(array $from, array $to)
    {
        $cFrom = count($from);
        $cTo   = count($to);

if ($cFrom == 0) {
            return array();
        } elseif ($cFrom == 1) {
            if (in_array($from[0], $to)) {
                return array($from[0]);
            } else {
                return array();
            }
        } else {
            $i         = intval($cFrom / 2);
            $fromStart = array_slice($from, 0, $i);
            $fromEnd   = array_slice($from, $i);
            $llB       = $this->length($fromStart, $to);
            $llE       = $this->length(array_reverse($fromEnd), array_reverse($to));
            $jMax      = 0;
            $max       = 0;

for ($j = 0; $j <= $cTo; $j++) {
                $m = $llB[$j] + $llE[$cTo - $j];

if ($m >= $max) {
                    $max  = $m;
                    $jMax = $j;
                }
            }

$toStart = array_slice($to, 0, $jMax);
            $toEnd   = array_slice($to, $jMax);

return array_merge(
                $this->calculate($fromStart, $toStart),
                $this->calculate($fromEnd, $toEnd)
            );
        }
    }

/**
     * @param array $from
     * @param array $to
     *
     * @return array
     */
    private function length(array $from, array $to)
    {
        $current = array_fill(0, count($to) + 1, 0);
        $cFrom   = count($from);
        $cTo     = count($to);

for ($i = 0; $i < $cFrom; $i++) {
            $prev = $current;

for ($j = 0; $j < $cTo; $j++) {
                if ($from[$i] == $to[$j]) {
                    $current[$j + 1] = $prev[$j] + 1;
                } else {
                    $current[$j + 1] = max($current[$j], $prev[$j + 1]);
                }
            }
        }

return $current;
    }
}