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