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
13use PHPUnit\Framework\TestCase;
14
15abstract class LongestCommonSubsequenceTest extends TestCase
16{
17    /**
18     * @var LongestCommonSubsequence
19     */
20    private $implementation;
21
22    /**
23     * @var string
24     */
25    private $memoryLimit;
26
27    /**
28     * @var int[]
29     */
30    private $stress_sizes = array(1, 2, 3, 100, 500, 1000, 2000);
31
32    protected function setUp()
33    {
34        $this->memoryLimit = \ini_get('memory_limit');
35        \ini_set('memory_limit', '256M');
36
37        $this->implementation = $this->createImplementation();
38    }
39
40    /**
41     * @return LongestCommonSubsequence
42     */
43    abstract protected function createImplementation();
44
45    protected function tearDown()
46    {
47        \ini_set('memory_limit', $this->memoryLimit);
48    }
49
50    public function testBothEmpty()
51    {
52        $from   = array();
53        $to     = array();
54        $common = $this->implementation->calculate($from, $to);
55
56        $this->assertEquals(array(), $common);
57    }
58
59    public function testIsStrictComparison()
60    {
61        $from = array(
62            false, 0, 0.0, '', null, array(),
63            true, 1, 1.0, 'foo', array('foo', 'bar'), array('foo' => 'bar')
64        );
65        $to     = $from;
66        $common = $this->implementation->calculate($from, $to);
67
68        $this->assertEquals($from, $common);
69
70        $to = array(
71            false, false, false, false, false, false,
72            true, true, true, true, true, true
73        );
74
75        $expected = array(
76            false,
77            true,
78        );
79
80        $common = $this->implementation->calculate($from, $to);
81
82        $this->assertEquals($expected, $common);
83    }
84
85    public function testEqualSequences()
86    {
87        foreach ($this->stress_sizes as $size) {
88            $range  = \range(1, $size);
89            $from   = $range;
90            $to     = $range;
91            $common = $this->implementation->calculate($from, $to);
92
93            $this->assertEquals($range, $common);
94        }
95    }
96
97    public function testDistinctSequences()
98    {
99        $from   = array('A');
100        $to     = array('B');
101        $common = $this->implementation->calculate($from, $to);
102        $this->assertEquals(array(), $common);
103
104        $from   = array('A', 'B', 'C');
105        $to     = array('D', 'E', 'F');
106        $common = $this->implementation->calculate($from, $to);
107        $this->assertEquals(array(), $common);
108
109        foreach ($this->stress_sizes as $size) {
110            $from   = \range(1, $size);
111            $to     = \range($size + 1, $size * 2);
112            $common = $this->implementation->calculate($from, $to);
113            $this->assertEquals(array(), $common);
114        }
115    }
116
117    public function testCommonSubsequence()
118    {
119        $from     = array('A',      'C',      'E', 'F', 'G');
120        $to       = array('A', 'B',      'D', 'E',           'H');
121        $expected = array('A',                'E');
122        $common   = $this->implementation->calculate($from, $to);
123        $this->assertEquals($expected, $common);
124
125        $from     = array('A',      'C',      'E', 'F', 'G');
126        $to       = array('B', 'C', 'D', 'E', 'F',      'H');
127        $expected = array('C',                'E', 'F');
128        $common   = $this->implementation->calculate($from, $to);
129        $this->assertEquals($expected, $common);
130
131        foreach ($this->stress_sizes as $size) {
132            $from     = $size < 2 ? array(1) : \range(1, $size + 1, 2);
133            $to       = $size < 3 ? array(1) : \range(1, $size + 1, 3);
134            $expected = $size < 6 ? array(1) : \range(1, $size + 1, 6);
135            $common   = $this->implementation->calculate($from, $to);
136
137            $this->assertEquals($expected, $common);
138        }
139    }
140
141    public function testSingleElementSubsequenceAtStart()
142    {
143        foreach ($this->stress_sizes as $size) {
144            $from   = \range(1, $size);
145            $to     = \array_slice($from, 0, 1);
146            $common = $this->implementation->calculate($from, $to);
147
148            $this->assertEquals($to, $common);
149        }
150    }
151
152    public function testSingleElementSubsequenceAtMiddle()
153    {
154        foreach ($this->stress_sizes as $size) {
155            $from   = \range(1, $size);
156            $to     = \array_slice($from, (int) $size / 2, 1);
157            $common = $this->implementation->calculate($from, $to);
158
159            $this->assertEquals($to, $common);
160        }
161    }
162
163    public function testSingleElementSubsequenceAtEnd()
164    {
165        foreach ($this->stress_sizes as $size) {
166            $from   = \range(1, $size);
167            $to     = \array_slice($from, $size - 1, 1);
168            $common = $this->implementation->calculate($from, $to);
169
170            $this->assertEquals($to, $common);
171        }
172    }
173
174    public function testReversedSequences()
175    {
176        $from     = array('A', 'B');
177        $to       = array('B', 'A');
178        $expected = array('A');
179        $common   = $this->implementation->calculate($from, $to);
180        $this->assertEquals($expected, $common);
181
182        foreach ($this->stress_sizes as $size) {
183            $from   = \range(1, $size);
184            $to     = \array_reverse($from);
185            $common = $this->implementation->calculate($from, $to);
186
187            $this->assertEquals(array(1), $common);
188        }
189    }
190
191    public function testStrictTypeCalculate()
192    {
193        $diff = $this->implementation->calculate(array('5'), array('05'));
194
195        $this->assertInternalType('array', $diff);
196        $this->assertCount(0, $diff);
197    }
198}
199