Subversion-Projekte lars-tiefland.laravel_shop

Revision

Revision 148 | Details | Vergleich mit vorheriger | Letzte Änderung | Log anzeigen | RSS feed

Revision Autor Zeilennr. Zeile
148 lars 1 
<?php declare(strict_types=1);
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 
namespace SebastianBergmann\Diff;
11 
 
12 
use function array_fill;
13 
use function array_merge;
14 
use function array_reverse;
15 
use function array_slice;
16 
use function count;
17 
use function in_array;
18 
use function max;
19 
 
20 
final class MemoryEfficientLongestCommonSubsequenceCalculator implements LongestCommonSubsequenceCalculator
21 
{
22 
    /**
23 
     * {@inheritdoc}
24 
     */
25 
    public function calculate(array $from, array $to): array
26 
    {
27 
        $cFrom = count($from);
28 
        $cTo   = count($to);
29 
 
30 
        if ($cFrom === 0) {
31 
            return [];
32 
        }
33 
 
34 
        if ($cFrom === 1) {
35 
            if (in_array($from[0], $to, true)) {
36 
                return [$from[0]];
37 
            }
38 
 
39 
            return [];
40 
        }
41 
 
42 
        $i         = (int) ($cFrom / 2);
43 
        $fromStart = array_slice($from, 0, $i);
44 
        $fromEnd   = array_slice($from, $i);
45 
        $llB       = $this->length($fromStart, $to);
46 
        $llE       = $this->length(array_reverse($fromEnd), array_reverse($to));
47 
        $jMax      = 0;
48 
        $max       = 0;
49 
 
50 
        for ($j = 0; $j <= $cTo; $j++) {
51 
            $m = $llB[$j] + $llE[$cTo - $j];
52 
 
53 
            if ($m >= $max) {
54 
                $max  = $m;
55 
                $jMax = $j;
56 
            }
57 
        }
58 
 
59 
        $toStart = array_slice($to, 0, $jMax);
60 
        $toEnd   = array_slice($to, $jMax);
61 
 
62 
        return array_merge(
63 
            $this->calculate($fromStart, $toStart),
64 
            $this->calculate($fromEnd, $toEnd)
65 
        );
66 
    }
67 
 
68 
    private function length(array $from, array $to): array
69 
    {
70 
        $current = array_fill(0, count($to) + 1, 0);
71 
        $cFrom   = count($from);
72 
        $cTo     = count($to);
73 
 
74 
        for ($i = 0; $i < $cFrom; $i++) {
75 
            $prev = $current;
76 
 
77 
            for ($j = 0; $j < $cTo; $j++) {
78 
                if ($from[$i] === $to[$j]) {
79 
                    $current[$j + 1] = $prev[$j] + 1;
80 
                } else {
1663 lars 81 
                    // don't use max() to avoid function call overhead
82 
                    if ($current[$j] > $prev[$j + 1]) {
83 
                        $current[$j + 1] = $current[$j];
84 
                    } else {
85 
                        $current[$j + 1] = $prev[$j + 1];
86 
                    }
148 lars 87 
                }
88 
            }
89 
        }
90 
 
91 
        return $current;
92 
    }
93 
}