comparison vendor/sebastian/diff/src/LCS/MemoryEfficientLongestCommonSubsequenceImplementation.php @ 0:4c8ae668cc8c

Initial import (non-working)
author Chris Cannam
date Wed, 29 Nov 2017 16:09:58 +0000
parents
children 7a779792577d
comparison
equal deleted inserted replaced
-1:000000000000 0:4c8ae668cc8c
1 <?php
2 /*
3 * This file is part of the Diff package.
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
11 namespace SebastianBergmann\Diff\LCS;
12
13 /**
14 * Memory-efficient implementation of longest common subsequence calculation.
15 */
16 class 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 } elseif ($cFrom == 1) {
34 if (in_array($from[0], $to)) {
35 return array($from[0]);
36 } else {
37 return array();
38 }
39 } else {
40 $i = intval($cFrom / 2);
41 $fromStart = array_slice($from, 0, $i);
42 $fromEnd = array_slice($from, $i);
43 $llB = $this->length($fromStart, $to);
44 $llE = $this->length(array_reverse($fromEnd), array_reverse($to));
45 $jMax = 0;
46 $max = 0;
47
48 for ($j = 0; $j <= $cTo; $j++) {
49 $m = $llB[$j] + $llE[$cTo - $j];
50
51 if ($m >= $max) {
52 $max = $m;
53 $jMax = $j;
54 }
55 }
56
57 $toStart = array_slice($to, 0, $jMax);
58 $toEnd = array_slice($to, $jMax);
59
60 return array_merge(
61 $this->calculate($fromStart, $toStart),
62 $this->calculate($fromEnd, $toEnd)
63 );
64 }
65 }
66
67 /**
68 * @param array $from
69 * @param array $to
70 *
71 * @return array
72 */
73 private function length(array $from, array $to)
74 {
75 $current = array_fill(0, count($to) + 1, 0);
76 $cFrom = count($from);
77 $cTo = count($to);
78
79 for ($i = 0; $i < $cFrom; $i++) {
80 $prev = $current;
81
82 for ($j = 0; $j < $cTo; $j++) {
83 if ($from[$i] == $to[$j]) {
84 $current[$j + 1] = $prev[$j] + 1;
85 } else {
86 $current[$j + 1] = max($current[$j], $prev[$j + 1]);
87 }
88 }
89 }
90
91 return $current;
92 }
93 }