*/
$max = min( $this->m, $this->n );
for ( $forwardBound = 0; $forwardBound < $max
- && $this->from[$forwardBound] === $this->to[$forwardBound];
- ++$forwardBound ) {
+ && $this->from[$forwardBound] === $this->to[$forwardBound];
+ ++$forwardBound
+ ) {
$this->removed[$forwardBound] = $this->added[$forwardBound] = false;
}
$backBoundL2 = $this->n - 1;
while ( $backBoundL1 >= $forwardBound && $backBoundL2 >= $forwardBound
- && $this->from[$backBoundL1] === $this->to[$backBoundL2] ) {
+ && $this->from[$backBoundL1] === $this->to[$backBoundL2]
+ ) {
$this->removed[$backBoundL1--] = $this->added[$backBoundL2--] = false;
}
$snake = array( 0, 0, 0 );
$this->length = $forwardBound + $this->m - $backBoundL1 - 1
- + $this->lcs_rec( $forwardBound, $backBoundL1,
- $forwardBound, $backBoundL2, $V, $snake );
+ + $this->lcs_rec(
+ $forwardBound,
+ $backBoundL1,
+ $forwardBound,
+ $backBoundL2,
+ $V,
+ $snake
+ );
}
$this->m = $m;
while ( $xi < $this->m || $yi < $this->n ) {
// Matching "snake".
while ( $xi < $this->m && $yi < $this->n
- && !$this->removed[$xi]
- && !$this->added[$yi] ) {
+ && !$this->removed[$xi]
+ && !$this->added[$yi]
+ ) {
++$xi;
++$yi;
}
}
if ( $xi > $xstart || $yi > $ystart ) {
- $ranges[] = new RangeDifference( $xstart, $xi,
- $ystart, $yi );
+ $ranges[] = new RangeDifference( $xstart, $xi, $ystart, $yi );
}
}
+
return $ranges;
}
}
$d = $this->find_middle_snake( $bottoml1, $topl1, $bottoml2,
- $topl2, $V, $snake );
+ $topl2, $V, $snake );
// need to store these so we don't lose them when they're
// overwritten by the recursion
if ( $d > 1 ) {
return $len
+ $this->lcs_rec( $bottoml1, $startx - 1, $bottoml2,
- $starty - 1, $V, $snake )
+ $starty - 1, $V, $snake )
+ $this->lcs_rec( $startx + $len, $topl1, $starty + $len,
- $topl2, $V, $snake );
+ $topl2, $V, $snake );
} elseif ( $d == 1 ) {
/*
* In this case the sequences differ by exactly 1 line. We have
$this->removed[$bottoml1 + $i] =
$this->added[$bottoml2 + $i] = false;
}
+
return $max + $len;
}
+
return $len;
}
$snake0 = &$snake[0];
$snake1 = &$snake[1];
$snake2 = &$snake[2];
- $bottoml1_min_1 = $bottoml1 -1;
- $bottoml2_min_1 = $bottoml2 -1;
+ $bottoml1_min_1 = $bottoml1 - 1;
+ $bottoml2_min_1 = $bottoml2 - 1;
$N = $topl1 - $bottoml1_min_1;
$M = $topl2 - $bottoml2_min_1;
$delta = $N - $M;
// compute forward furthest reaching paths
for ( $k = $start_diag; $k <= $end_diag; $k += 2 ) {
if ( $k == -$d || ( $k < $d
- && $V0[$limit_min_1 + $k] < $V0[$limit_plus_1 + $k] ) ) {
+ && $V0[$limit_min_1 + $k] < $V0[$limit_plus_1 + $k] )
+ ) {
$x = $V0[$limit_plus_1 + $k];
} else {
$x = $V0[$limit_min_1 + $k] + 1;
++$absx;
++$absy;
}
- $x = $absx -$bottoml1;
+ $x = $absx - $bottoml1;
- $snake2 = $absx -$snake0;
+ $snake2 = $absx - $snake0;
$V0[$limit + $k] = $x;
if ( $k >= $delta - $d + 1 && $k <= $delta + $d - 1
- && $x >= $V1[$limit + $k - $delta] ) {
+ && $x >= $V1[$limit + $k - $delta]
+ ) {
return 2 * $d - 1;
}
// compute backward furthest reaching paths
for ( $k = $start_diag; $k <= $end_diag; $k += 2 ) {
if ( $k == $d
- || ( $k != -$d && $V1[$limit_min_1 + $k] < $V1[$limit_plus_1 + $k] ) ) {
+ || ( $k != -$d && $V1[$limit_min_1 + $k] < $V1[$limit_plus_1 + $k] )
+ ) {
$x = $V1[$limit_min_1 + $k];
} else {
$x = $V1[$limit_plus_1 + $k] - 1;
$snake2 = 0;
while ( $x > 0 && $y > 0
- && $from[$x + $bottoml1_min_1] === $to[$y + $bottoml2_min_1] ) {
+ && $from[$x + $bottoml1_min_1] === $to[$y + $bottoml2_min_1]
+ ) {
--$x;
--$y;
++$snake2;
// compute forward furthest reaching paths
for ( $k = $start_diag; $k <= $end_diag; $k += 2 ) {
if ( $k == -$d
- || ( $k < $d && $V0[$limit_min_1 + $k] < $V0[$limit_plus_1 + $k] ) ) {
+ || ( $k < $d && $V0[$limit_min_1 + $k] < $V0[$limit_plus_1 + $k] )
+ ) {
$x = $V0[$limit_plus_1 + $k];
} else {
$x = $V0[$limit_min_1 + $k] + 1;
++$absx;
++$absy;
}
- $x = $absx -$bottoml1;
- $snake2 = $absx -$snake0;
+ $x = $absx - $bottoml1;
+ $snake2 = $absx - $snake0;
$V0[$limit + $k] = $x;
// check to see if we can cut down the diagonal range
if ( $x >= $N && $end_forward > $k - 1 ) {
$end_forward = $k - 1;
- } elseif ( $absy -$bottoml2 >= $M ) {
+ } elseif ( $absy - $bottoml2 >= $M ) {
$start_forward = $k + 1;
$value_to_add_forward = 0;
}
// compute backward furthest reaching paths
for ( $k = $start_diag; $k <= $end_diag; $k += 2 ) {
if ( $k == $d
- || ( $k != -$d && $V1[$limit_min_1 + $k] < $V1[$limit_plus_1 + $k] ) ) {
+ || ( $k != -$d && $V1[$limit_min_1 + $k] < $V1[$limit_plus_1 + $k] )
+ ) {
$x = $V1[$limit_min_1 + $k];
} else {
$x = $V1[$limit_plus_1 + $k] - 1;
$snake2 = 0;
while ( $x > 0 && $y > 0
- && $from[$x + $bottoml1_min_1] === $to[$y + $bottoml2_min_1] ) {
+ && $from[$x + $bottoml1_min_1] === $to[$y + $bottoml2_min_1]
+ ) {
--$x;
--$y;
++$snake2;
$V1[$limit + $k] = $x;
if ( $k >= -$delta - $d && $k <= $d - $delta
- && $x <= $V0[$limit + $k + $delta] ) {
+ && $x <= $V0[$limit + $k + $delta]
+ ) {
$snake0 = $bottoml1 + $x;
$snake1 = $bottoml2 + $y;
+
return 2 * $d;
}
$snake2 = 0;
wfDebug( "Computing the LCS is too expensive. Using a heuristic.\n" );
$this->heuristicUsed = true;
+
return 5; /*
* HACK: since we didn't really finish the LCS computation
* we don't really know the length of the SES. We don't do
public function getLcsLength() {
if ( $this->heuristicUsed && !$this->lcsLengthCorrectedForHeuristic ) {
$this->lcsLengthCorrectedForHeuristic = true;
- $this->length = $this->m -array_sum( $this->added );
+ $this->length = $this->m - array_sum( $this->added );
}
+
return $this->length;
}
*/
class RangeDifference {
+ /** @var int */
public $leftstart;
+
+ /** @var int */
public $leftend;
+
+ /** @var int */
public $leftlength;
+ /** @var int */
public $rightstart;
+
+ /** @var int */
public $rightend;
+
+ /** @var int */
public $rightlength;
function __construct( $leftstart, $leftend, $rightstart, $rightend ) {
$this->rightend = $rightend;
$this->rightlength = $rightend - $rightstart;
}
+
}
dépôts / lhc / web / wiklou.git / blobdiff