2 /* Copyright (C) 2008 Guy Van den Broeck <guy@guyvdb.eu>
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
17 * or see http://www.gnu.org/
21 * This diff implementation is mainly lifted from the LCS algorithm of the Eclipse project which
22 * in turn is based on Myers' "An O(ND) difference algorithm and its variations"
23 * (http://citeseer.ist.psu.edu/myers86ond.html) with range compression (see Wu et al.'s
24 * "An O(NP) Sequence Comparison Algorithm").
26 * This implementation supports an upper bound on the excution time.
28 * Complexity: O((M + N)D) worst case time, O(M + N + D^2) expected time, O(M + N) space
30 * @author Guy Van den Broeck
45 private $maxDifferences;
46 private $lcsLengthCorrectedForHeuristic = false;
52 public $heuristicUsed;
54 function __construct($tooLong = 2000000, $powLimit = 1.45){
55 $this->tooLong
= $tooLong;
56 $this->powLimit
= $powLimit;
59 public function diff(/*array*/ $from, /*array*/ $to){
60 //remember initial lengths
64 $this->heuristicUsed
= FALSE;
67 $removed = $m>0?
array_fill(0,$m,true):array();
68 $added = $n>0?
array_fill(0,$n,true):array();
70 //reduce the complexity for the next step (intentionally done twice)
71 //remove common tokens at the start
73 while($i<$m && $i<$n && $from[$i]===$to[$i]){
74 $removed[$i] = $added[$i] = false;
75 unset($from[$i],$to[$i]);
79 //remove common tokens at the end
81 while($i+
$j<=$m && $i+
$j<=$n && $from[$m-$j]===$to[$n-$j]){
82 $removed[$m-$j] = $added[$n-$j] = false;
83 unset($from[$m-$j],$to[$n-$j]);
87 $this->from
= $newFromIndex = $this->to
= $newToIndex = array();
89 //remove tokens not in both sequences
90 $shared = array_fill_keys($from,false);
91 foreach($to as $index => $el){
92 if(array_key_exists($el,$shared)){
96 $newToIndex[] = $index;
99 foreach($from as $index => $el){
103 $newFromIndex[] = $index;
107 unset($shared, $from, $to);
109 $this->m
= sizeof($this->from
);
110 $this->n
= sizeof($this->to
);
112 $this->removed
= $this->m
>0?
array_fill(0,$this->m
,true):array();
113 $this->added
= $this->n
>0?
array_fill(0,$this->n
,true):array();
115 if ($this->m
== 0 ||
$this->n
== 0) {
118 $this->maxDifferences
= ceil(($this->m +
$this->n
) / 2.0);
119 if ($this->m
* $this->n
> $this->tooLong
) {
120 // limit complexity to D^POW_LIMIT for long sequences
121 $this->maxDifferences
= floor(pow($this->maxDifferences
, $this->powLimit
- 1.0));
122 wfDebug("Limiting max number of differences to $this->maxDifferences\n");
126 * The common prefixes and suffixes are always part of some LCS, include
127 * them now to reduce our search space
129 $max = min($this->m
, $this->n
);
130 for ($forwardBound = 0; $forwardBound < $max
131 && $this->from
[$forwardBound]===$this->to
[$forwardBound]; ++
$forwardBound) {
132 $this->removed
[$forwardBound] = $this->added
[$forwardBound] = false;
135 $backBoundL1 = $this->m
- 1;
136 $backBoundL2 = $this->n
- 1;
138 while ($backBoundL1 >= $forwardBound && $backBoundL2 >= $forwardBound
139 && $this->from
[$backBoundL1] === $this->to
[$backBoundL2]) {
140 $this->removed
[$backBoundL1--] = $this->added
[$backBoundL2--] = false;
143 $temp = array_fill(0,$this->m +
$this->n +
1, 0);
144 $V = array($temp,$temp);
145 $snake = array(0,0,0);
147 $this->length
= $forwardBound +
$this->m
- $backBoundL1 - 1
148 +
$this->lcs_rec($forwardBound, $backBoundL1, $forwardBound, $backBoundL2,
155 $this->length +
= $i+
$j-1;
157 foreach($this->removed
as $key => $removed_elem){
159 $removed[$newFromIndex[$key]] = false;
162 foreach($this->added
as $key => $added_elem){
164 $added[$newToIndex[$key]] = false;
167 $this->removed
= $removed;
168 $this->added
= $added;
171 function diff_range ($from_lines, $to_lines){
172 // Diff and store locally
173 $this->diff($from_lines, $to_lines);
174 unset($from_lines, $to_lines);
178 while ($xi < $this->m ||
$yi < $this->n
) {
180 while ( $xi < $this->m
&& $yi < $this->n
181 && !$this->removed
[$xi] && !$this->added
[$yi]) {
185 // Find deletes & adds.
187 while ($xi < $this->m
&& $this->removed
[$xi]){
192 while ($yi < $this->n
&& $this->added
[$yi]){
196 if ($xi>$xstart ||
$yi>$ystart){
197 $ranges[] = new RangeDifference($xstart,$xi,$ystart,$yi);
203 private function lcs_rec($bottoml1, $topl1, $bottoml2, $topl2, &$V, &$snake) {
204 // check that both sequences are non-empty
205 if ($bottoml1 > $topl1 ||
$bottoml2 > $topl2) {
209 $d = $this->find_middle_snake($bottoml1, $topl1, $bottoml2, $topl2, $V, $snake);
211 // need to store these so we don't lose them when they're overwritten by
217 // the middle snake is part of the LCS, store it
218 for ($i = 0; $i < $len; ++
$i) {
219 $this->removed
[$startx +
$i] = $this->added
[$starty +
$i] = false;
224 +
$this->lcs_rec($bottoml1, $startx - 1, $bottoml2, $starty - 1, $V, $snake)
225 +
$this->lcs_rec($startx +
$len, $topl1, $starty +
$len, $topl2, $V, $snake);
226 } else if ($d == 1) {
228 * In this case the sequences differ by exactly 1 line. We have
229 * already saved all the lines after the difference in the for loop
230 * above, now we need to save all the lines before the difference.
232 $max = min($startx - $bottoml1, $starty - $bottoml2);
233 for ($i = 0; $i < $max; ++
$i) {
234 $this->removed
[$bottoml1 +
$i] = $this->added
[$bottoml2 +
$i] = false;
241 private function find_middle_snake($bottoml1, $topl1, $bottoml2,$topl2, &$V, &$snake) {
242 $from = &$this->from
;
246 $snake0 = &$snake[0];
247 $snake1 = &$snake[1];
248 $snake2 = &$snake[2];
249 $bottoml1_min_1 = $bottoml1-1;
250 $bottoml2_min_1 = $bottoml2-1;
251 $N = $topl1 - $bottoml1_min_1;
252 $M = $topl2 - $bottoml2_min_1;
254 $maxabsx = $N+
$bottoml1;
255 $maxabsy = $M+
$bottoml2;
256 $limit = min($this->maxDifferences
, ceil(($N +
$M ) / 2)); // ceil((N+M)/2)
258 //value_to_add_forward: a 0 or 1 that we add to the start
260 // to make it odd/even
262 $value_to_add_forward = 1;
264 $value_to_add_forward = 0;
268 $value_to_add_backward = 1;
270 $value_to_add_backward = 0;
273 $start_forward = -$M;
275 $start_backward = -$N;
278 $limit_min_1 = $limit-1;
279 $limit_plus_1 = $limit+
1;
281 $V0[$limit_plus_1] = 0;
282 $V1[$limit_min_1] = $N;
283 $limit = min($this->maxDifferences
, ceil(($N +
$M ) / 2)); // ceil((N+M)/2)
285 if (($delta & 1) == 1) {
286 for ($d = 0; $d <= $limit; ++
$d) {
287 $start_diag = max($value_to_add_forward +
$start_forward, -$d);
288 $end_diag = min($end_forward, $d);
289 $value_to_add_forward = 1 - $value_to_add_forward;
291 // compute forward furthest reaching paths
292 for ($k = $start_diag; $k <= $end_diag; $k +
= 2) {
294 ||
($k < $d && $V0[$limit_min_1 +
$k] < $V0[$limit_plus_1 +
$k])) {
295 $x = $V0[$limit_plus_1 +
$k];
297 $x = $V0[$limit_min_1 +
$k] +
1;
300 $absx = $snake0 = $x +
$bottoml1;
301 $absy = $snake1 = $x - $k +
$bottoml2;
303 while ($absx < $maxabsx && $absy < $maxabsy && $from[$absx] === $to[$absy]) {
307 $x = $absx-$bottoml1;
309 $snake2 = $absx -$snake0;
310 $V0[$limit +
$k] = $x;
311 if ($k >= $delta - $d +
1 && $k <= $delta +
$d - 1
312 && $x >= $V1[$limit +
$k - $delta]) {
316 // check to see if we can cut down the diagonal range
317 if ($x >= $N && $end_forward > $k - 1) {
318 $end_forward = $k - 1;
319 } else if ($absy-$bottoml2 >= $M) {
320 $start_forward = $k +
1;
321 $value_to_add_forward = 0;
325 $start_diag = max($value_to_add_backward +
$start_backward, -$d);
326 $end_diag = min($end_backward, $d);
327 $value_to_add_backward = 1 - $value_to_add_backward;
329 // compute backward furthest reaching paths
330 for ($k = $start_diag; $k <= $end_diag; $k +
= 2) {
332 ||
($k != -$d && $V1[$limit_min_1 +
$k] < $V1[$limit_plus_1 +
$k])) {
333 $x = $V1[$limit_min_1 +
$k];
335 $x = $V1[$limit_plus_1 +
$k] - 1;
338 $y = $x - $k - $delta;
341 while ($x > 0 && $y > 0
342 && $from[$x +
$bottoml1_min_1] === $to[$y +
$bottoml2_min_1]) {
347 $V1[$limit +
$k] = $x;
349 // check to see if we can cut down our diagonal range
351 $start_backward = $k +
1;
352 $value_to_add_backward = 0;
353 } else if ($y <= 0 && $end_backward > $k - 1) {
354 $end_backward = $k - 1;
359 for ($d = 0; $d <= $limit; ++
$d) {
360 $start_diag = max($value_to_add_forward +
$start_forward, -$d);
361 $end_diag = min($end_forward, $d);
362 $value_to_add_forward = 1 - $value_to_add_forward;
364 // compute forward furthest reaching paths
365 for ($k = $start_diag; $k <= $end_diag; $k +
= 2) {
367 ||
($k < $d && $V0[$limit_min_1 +
$k] < $V0[$limit_plus_1 +
$k])) {
368 $x = $V0[$limit_plus_1 +
$k];
370 $x = $V0[$limit_min_1 +
$k] +
1;
373 $absx = $snake0 = $x +
$bottoml1;
374 $absy = $snake1 = $x - $k +
$bottoml2;
376 while ($absx < $maxabsx && $absy < $maxabsy && $from[$absx] === $to[$absy]) {
380 $x = $absx-$bottoml1;
381 $snake2 = $absx -$snake0;
382 $V0[$limit +
$k] = $x;
384 // check to see if we can cut down the diagonal range
385 if ($x >= $N && $end_forward > $k - 1) {
386 $end_forward = $k - 1;
387 } else if ($absy-$bottoml2 >= $M) {
388 $start_forward = $k +
1;
389 $value_to_add_forward = 0;
393 $start_diag = max($value_to_add_backward +
$start_backward, -$d);
394 $end_diag = min($end_backward, $d);
395 $value_to_add_backward = 1 - $value_to_add_backward;
397 // compute backward furthest reaching paths
398 for ($k = $start_diag; $k <= $end_diag; $k +
= 2) {
400 ||
($k != -$d && $V1[$limit_min_1 +
$k] < $V1[$limit_plus_1 +
$k])) {
401 $x = $V1[$limit_min_1 +
$k];
403 $x = $V1[$limit_plus_1 +
$k] - 1;
406 $y = $x - $k - $delta;
409 while ($x > 0 && $y > 0
410 && $from[$x +
$bottoml1_min_1] === $to[$y +
$bottoml2_min_1]) {
415 $V1[$limit +
$k] = $x;
417 if ($k >= -$delta - $d && $k <= $d - $delta
418 && $x <= $V0[$limit +
$k +
$delta]) {
419 $snake0 = $bottoml1 +
$x;
420 $snake1 = $bottoml2 +
$y;
424 // check to see if we can cut down our diagonal range
426 $start_backward = $k +
1;
427 $value_to_add_backward = 0;
428 } else if ($y <= 0 && $end_backward > $k - 1) {
429 $end_backward = $k - 1;
435 * computing the true LCS is too expensive, instead find the diagonal
436 * with the most progress and pretend a midle snake of length 0 occurs
440 $most_progress = self
::findMostProgress($M, $N, $limit, $V);
442 $snake0 = $bottoml1 +
$most_progress[0];
443 $snake1 = $bottoml2 +
$most_progress[1];
445 wfDebug('Computing the LCS is too expensive. Using a heuristic.\n');
446 $this->heuristicUsed
= true;
448 * HACK: since we didn't really finish the LCS computation
449 * we don't really know the length of the SES. We don't do
450 * anything with the result anyway, unless it's <=1. We know
451 * for a fact SES > 1 so 5 is as good a number as any to
456 private static function findMostProgress($M, $N, $limit, $V) {
459 if (($M & 1) == ($limit & 1)) {
460 $forward_start_diag = max(-$M, -$limit);
462 $forward_start_diag = max(1 - $M, -$limit);
465 $forward_end_diag = min($N, $limit);
467 if (($N & 1) == ($limit & 1)) {
468 $backward_start_diag = max(-$N, -$limit);
470 $backward_start_diag = max(1 - $N, -$limit);
473 $backward_end_diag = -min($M, $limit);
475 $temp = array(0,0,0);
478 $max_progress = array_fill(0,ceil(max($forward_end_diag
479 - $forward_start_diag, $backward_end_diag - $backward_start_diag) / 2), $temp);
480 $num_progress = 0; // the 1st entry is current, it is initialized
483 // first search the forward diagonals
484 for ($k = $forward_start_diag; $k <= $forward_end_diag; $k +
= 2) {
485 $x = $V[0][$limit +
$k];
487 if ($x > $N ||
$y > $M) {
492 if ($progress > $max_progress[0][2]) {
494 $max_progress[0][0] = $x;
495 $max_progress[0][1] = $y;
496 $max_progress[0][2] = $progress;
497 } else if ($progress == $max_progress[0][2]) {
499 $max_progress[$num_progress][0] = $x;
500 $max_progress[$num_progress][1] = $y;
501 $max_progress[$num_progress][2] = $progress;
505 $max_progress_forward = true; // initially the maximum
506 // progress is in the forward
509 // now search the backward diagonals
510 for ($k = $backward_start_diag; $k <= $backward_end_diag; $k +
= 2) {
511 $x = $V[1][$limit +
$k];
512 $y = $x - $k - $delta;
513 if ($x < 0 ||
$y < 0) {
517 $progress = $N - $x +
$M - $y;
518 if ($progress > $max_progress[0][2]) {
520 $max_progress_forward = false;
521 $max_progress[0][0] = $x;
522 $max_progress[0][1] = $y;
523 $max_progress[0][2] = $progress;
524 } else if ($progress == $max_progress[0][2] && !$max_progress_forward) {
526 $max_progress[$num_progress][0] = $x;
527 $max_progress[$num_progress][1] = $y;
528 $max_progress[$num_progress][2] = $progress;
532 // return the middle diagonal with maximal progress.
533 return $max_progress[floor($num_progress / 2)];
536 public function getLcsLength(){
537 if($this->heuristicUsed
&& !$this->lcsLengthCorrectedForHeuristic
){
538 $this->lcsLengthCorrectedForHeuristic
= true;
539 $this->length
= $this->m
-array_sum($this->added
);
541 return $this->length
;
547 * Alternative representation of a set of changes, by the index
548 * ranges that are changed.
550 class RangeDifference
{
560 function __construct($leftstart, $leftend, $rightstart, $rightend){
561 $this->leftstart
= $leftstart;
562 $this->leftend
= $leftend;
563 $this->leftlength
= $leftend-$leftstart;
564 $this->rightstart
= $rightstart;
565 $this->rightend
= $rightend;
566 $this->rightlength
= $rightend-$rightstart;