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 * Time-efficient implementation of longest common subsequence calculation.
15 */
16class TimeEfficientImplementation 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        $common     = array();
29        $fromLength = \count($from);
30        $toLength   = \count($to);
31        $width      = $fromLength + 1;
32        $matrix     = new \SplFixedArray($width * ($toLength + 1));
33
34        for ($i = 0; $i <= $fromLength; ++$i) {
35            $matrix[$i] = 0;
36        }
37
38        for ($j = 0; $j <= $toLength; ++$j) {
39            $matrix[$j * $width] = 0;
40        }
41
42        for ($i = 1; $i <= $fromLength; ++$i) {
43            for ($j = 1; $j <= $toLength; ++$j) {
44                $o          = ($j * $width) + $i;
45                $matrix[$o] = \max(
46                    $matrix[$o - 1],
47                    $matrix[$o - $width],
48                    $from[$i - 1] === $to[$j - 1] ? $matrix[$o - $width - 1] + 1 : 0
49                );
50            }
51        }
52
53        $i = $fromLength;
54        $j = $toLength;
55
56        while ($i > 0 && $j > 0) {
57            if ($from[$i - 1] === $to[$j - 1]) {
58                $common[] = $from[$i - 1];
59                --$i;
60                --$j;
61            } else {
62                $o = ($j * $width) + $i;
63
64                if ($matrix[$o - $width] > $matrix[$o - 1]) {
65                    --$j;
66                } else {
67                    --$i;
68                }
69            }
70        }
71
72        return \array_reverse($common);
73    }
74}
75