1
|
|
|
<?php |
2
|
|
|
|
3
|
|
|
namespace Fisharebest\Tests\Algorithm; |
4
|
|
|
|
5
|
|
|
use Fisharebest\Algorithm\MyersDiff; |
6
|
|
|
|
7
|
|
|
/** |
8
|
|
|
* @author Greg Roach <[email protected]> |
9
|
|
|
* @copyright (c) 2021 Greg Roach <[email protected]> |
10
|
|
|
* @license GPL-3.0+ |
11
|
|
|
* |
12
|
|
|
* This program is free software: you can redistribute it and/or modify |
13
|
|
|
* it under the terms of the GNU General Public License as published by |
14
|
|
|
* the Free Software Foundation, either version 3 of the License, or |
15
|
|
|
* (at your option) any later version. |
16
|
|
|
* This program is distributed in the hope that it will be useful, |
17
|
|
|
* but WITHOUT ANY WARRANTY; without even the implied warranty of |
18
|
|
|
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
19
|
|
|
* GNU General Public License for more details. |
20
|
|
|
* You should have received a copy of the GNU General Public License |
21
|
|
|
* along with this program. If not, see <https://www.gnu.org/licenses>. |
22
|
|
|
*/ |
23
|
|
|
class MyersDiffTest extends BaseTestCase |
24
|
|
|
{ |
25
|
|
|
/** |
26
|
|
|
* Test empty sequences. |
27
|
|
|
* |
28
|
|
|
* @return void |
29
|
|
|
*/ |
30
|
|
|
public function testBothEmpty() |
31
|
|
|
{ |
32
|
|
|
$algorithm = new MyersDiff(); |
33
|
|
|
$x = array(); |
34
|
|
|
$y = array(); |
35
|
|
|
$diff = array(); |
36
|
|
|
|
37
|
|
|
$this->assertSame($diff, $algorithm->calculate($x, $y)); |
38
|
|
|
} |
39
|
|
|
|
40
|
|
|
/** |
41
|
|
|
* Test one empty sequence. |
42
|
|
|
* |
43
|
|
|
* @return void |
44
|
|
|
*/ |
45
|
|
|
public function testFirstEmpty() |
46
|
|
|
{ |
47
|
|
|
$algorithm = new MyersDiff(); |
48
|
|
|
$x = array(); |
49
|
|
|
$y = array('a', 'b', 'c'); |
50
|
|
|
$diff = array( |
51
|
|
|
array('a', MyersDiff::INSERT), |
52
|
|
|
array('b', MyersDiff::INSERT), |
53
|
|
|
array('c', MyersDiff::INSERT), |
54
|
|
|
); |
55
|
|
|
|
56
|
|
|
$this->assertSame($diff, $algorithm->calculate($x, $y)); |
57
|
|
|
} |
58
|
|
|
|
59
|
|
|
/** |
60
|
|
|
* Test one empty sequence. |
61
|
|
|
* |
62
|
|
|
* @return void |
63
|
|
|
*/ |
64
|
|
|
public function testSecondEmpty() |
65
|
|
|
{ |
66
|
|
|
$algorithm = new MyersDiff(); |
67
|
|
|
$x = array('a', 'b', 'c'); |
68
|
|
|
$y = array(); |
69
|
|
|
$diff = array( |
70
|
|
|
array('a', MyersDiff::DELETE), |
71
|
|
|
array('b', MyersDiff::DELETE), |
72
|
|
|
array('c', MyersDiff::DELETE), |
73
|
|
|
); |
74
|
|
|
|
75
|
|
|
$this->assertSame($diff, $algorithm->calculate($x, $y)); |
76
|
|
|
} |
77
|
|
|
|
78
|
|
|
/** |
79
|
|
|
* Test identical sequences containing one token. |
80
|
|
|
* |
81
|
|
|
* @return void |
82
|
|
|
*/ |
83
|
|
|
public function testIdenticalOne() |
84
|
|
|
{ |
85
|
|
|
$algorithm = new MyersDiff(); |
86
|
|
|
$x = array('a'); |
87
|
|
|
$y = array('a'); |
88
|
|
|
$diff = array( |
89
|
|
|
array('a', MyersDiff::KEEP), |
90
|
|
|
); |
91
|
|
|
|
92
|
|
|
$this->assertSame($diff, $algorithm->calculate($x, $y)); |
93
|
|
|
} |
94
|
|
|
|
95
|
|
|
/** |
96
|
|
|
* Test identical sequences containing two tokens. |
97
|
|
|
* |
98
|
|
|
* @return void |
99
|
|
|
*/ |
100
|
|
|
public function testIdenticalTwo() |
101
|
|
|
{ |
102
|
|
|
$algorithm = new MyersDiff(); |
103
|
|
|
$x = array('a', 'b'); |
104
|
|
|
$y = array('a', 'b'); |
105
|
|
|
$diff = array( |
106
|
|
|
array('a', MyersDiff::KEEP), |
107
|
|
|
array('b', MyersDiff::KEEP), |
108
|
|
|
); |
109
|
|
|
|
110
|
|
|
$this->assertSame($diff, $algorithm->calculate($x, $y)); |
111
|
|
|
} |
112
|
|
|
|
113
|
|
|
/** |
114
|
|
|
* Test identical sequences containing three tokens. |
115
|
|
|
* |
116
|
|
|
* @return void |
117
|
|
|
*/ |
118
|
|
|
public function testIdenticalThree() |
119
|
|
|
{ |
120
|
|
|
$algorithm = new MyersDiff(); |
121
|
|
|
$x = array('a', 'b', 'c'); |
122
|
|
|
$y = array('a', 'b', 'c'); |
123
|
|
|
$diff = array( |
124
|
|
|
array('a', MyersDiff::KEEP), |
125
|
|
|
array('b', MyersDiff::KEEP), |
126
|
|
|
array('c', MyersDiff::KEEP), |
127
|
|
|
); |
128
|
|
|
|
129
|
|
|
$this->assertSame($diff, $algorithm->calculate($x, $y)); |
130
|
|
|
} |
131
|
|
|
|
132
|
|
|
/** |
133
|
|
|
* Test different strings containing one token. |
134
|
|
|
* |
135
|
|
|
* @return void |
136
|
|
|
*/ |
137
|
|
|
public function testSingleDifferentONe() |
138
|
|
|
{ |
139
|
|
|
$algorithm = new MyersDiff(); |
140
|
|
|
$x = array('a'); |
141
|
|
|
$y = array('x'); |
142
|
|
|
$diff = array( |
143
|
|
|
array('a', MyersDiff::DELETE), |
144
|
|
|
array('x', MyersDiff::INSERT), |
145
|
|
|
); |
146
|
|
|
|
147
|
|
|
$this->assertSame($diff, $algorithm->calculate($x, $y)); |
148
|
|
|
} |
149
|
|
|
|
150
|
|
|
/** |
151
|
|
|
* Test different strings containing two token. |
152
|
|
|
* |
153
|
|
|
* @return void |
154
|
|
|
*/ |
155
|
|
|
public function testSingleDifferentTwo() |
156
|
|
|
{ |
157
|
|
|
$algorithm = new MyersDiff(); |
158
|
|
|
$x = array('a', 'b'); |
159
|
|
|
$y = array('x', 'y'); |
160
|
|
|
$diff = array( |
161
|
|
|
array('a', MyersDiff::DELETE), |
162
|
|
|
array('b', MyersDiff::DELETE), |
163
|
|
|
array('x', MyersDiff::INSERT), |
164
|
|
|
array('y', MyersDiff::INSERT), |
165
|
|
|
); |
166
|
|
|
|
167
|
|
|
$this->assertSame($diff, $algorithm->calculate($x, $y)); |
168
|
|
|
} |
169
|
|
|
|
170
|
|
|
/** |
171
|
|
|
* Test different strings containing three token. |
172
|
|
|
* |
173
|
|
|
* @return void |
174
|
|
|
*/ |
175
|
|
|
public function testSingleDifferentThree() |
176
|
|
|
{ |
177
|
|
|
$algorithm = new MyersDiff(); |
178
|
|
|
$x = array('a', 'b', 'c'); |
179
|
|
|
$y = array('x', 'y', 'z'); |
180
|
|
|
$diff = array( |
181
|
|
|
array('a', MyersDiff::DELETE), |
182
|
|
|
array('b', MyersDiff::DELETE), |
183
|
|
|
array('c', MyersDiff::DELETE), |
184
|
|
|
array('x', MyersDiff::INSERT), |
185
|
|
|
array('y', MyersDiff::INSERT), |
186
|
|
|
array('z', MyersDiff::INSERT), |
187
|
|
|
); |
188
|
|
|
|
189
|
|
|
$this->assertSame($diff, $algorithm->calculate($x, $y)); |
190
|
|
|
} |
191
|
|
|
|
192
|
|
|
/** |
193
|
|
|
* Test two non-empty sequences. |
194
|
|
|
* |
195
|
|
|
* @return void |
196
|
|
|
*/ |
197
|
|
|
public function testBothNonEmpty() |
198
|
|
|
{ |
199
|
|
|
$algorithm = new MyersDiff(); |
200
|
|
|
$x = array('a', 'b', 'c', 'a', 'b', 'b', 'a'); |
201
|
|
|
$y = array('c', 'b', 'a', 'b', 'a', 'c'); |
202
|
|
|
$diff = array( |
203
|
|
|
array('a', MyersDiff::DELETE), |
204
|
|
|
array('b', MyersDiff::DELETE), |
205
|
|
|
array('c', MyersDiff::KEEP), |
206
|
|
|
array('b', MyersDiff::INSERT), |
207
|
|
|
array('a', MyersDiff::KEEP), |
208
|
|
|
array('b', MyersDiff::KEEP), |
209
|
|
|
array('b', MyersDiff::DELETE), |
210
|
|
|
array('a', MyersDiff::KEEP), |
211
|
|
|
array('c', MyersDiff::INSERT), |
212
|
|
|
); |
213
|
|
|
|
214
|
|
|
$this->assertSame($diff, $algorithm->calculate($x, $y)); |
215
|
|
|
} |
216
|
|
|
|
217
|
|
|
/** |
218
|
|
|
* Test delete-before-insert. Delete/insert gives the same |
219
|
|
|
* result as insert/delete. Our algorithm consistently |
220
|
|
|
* deletes first. |
221
|
|
|
* |
222
|
|
|
* void |
223
|
|
|
*/ |
224
|
|
|
public function testDeleteBeforeInsert() |
225
|
|
|
{ |
226
|
|
|
$algorithm = new MyersDiff(); |
227
|
|
|
$x = array('a', 'b', 'c'); |
228
|
|
|
$y = array('a', 'd', 'c'); |
229
|
|
|
$diff = array( |
230
|
|
|
array('a', MyersDiff::KEEP), |
231
|
|
|
array('b', MyersDiff::DELETE), |
232
|
|
|
array('d', MyersDiff::INSERT), |
233
|
|
|
array('c', MyersDiff::KEEP), |
234
|
|
|
); |
235
|
|
|
|
236
|
|
|
$this->assertSame($diff, $algorithm->calculate($x, $y)); |
237
|
|
|
} |
238
|
|
|
|
239
|
|
|
/** |
240
|
|
|
* Test custom token comparison. |
241
|
|
|
* |
242
|
|
|
* @return void |
243
|
|
|
*/ |
244
|
|
|
public function testCustomCompare() |
245
|
|
|
{ |
246
|
|
|
$algorithm = new MyersDiff(); |
247
|
|
|
$ignorecase = static function ($x, $y) { return strtolower($x) === strtolower($y); }; |
248
|
|
|
$x = array('a', 'b', 'c'); |
249
|
|
|
$y = array('A', 'B', 'C'); |
250
|
|
|
$diff = array( |
251
|
|
|
array('a', MyersDiff::KEEP), |
252
|
|
|
array('b', MyersDiff::KEEP), |
253
|
|
|
array('c', MyersDiff::KEEP), |
254
|
|
|
); |
255
|
|
|
|
256
|
|
|
$this->assertSame($diff, $algorithm->calculate($x, $y, $ignorecase)); |
257
|
|
|
} |
258
|
|
|
} |
259
|
|
|
|