MediaWiki  1.23.12
WikiDiff3 Class Reference

This diff implementation is mainly lifted from the LCS algorithm of the Eclipse project which in turn is based on Myers' "An O(ND) difference algorithm and its variations" (http://citeseer.ist.psu.edu/myers86ond.html) with range compression (see Wu et al. More...

## Public Member Functions

__construct ( \$tooLong=2000000, \$powLimit=1.45)

diff (\$from, \$to)

diff_range ( \$from_lines, \$to_lines)

getLcsLength ()

\$heuristicUsed

\$length

\$removed

## Private Member Functions

find_middle_snake ( \$bottoml1, \$topl1, \$bottoml2, \$topl2, &\$V, &\$snake)

lcs_rec ( \$bottoml1, \$topl1, \$bottoml2, \$topl2, &\$V, &\$snake)

## Static Private Member Functions

static findMostProgress ( \$M, \$N, \$limit, \$V)

## Private Attributes

\$from

\$lcsLengthCorrectedForHeuristic = false

\$m

\$maxDifferences

\$n

\$powLimit

\$to

\$tooLong

## Detailed Description

This diff implementation is mainly lifted from the LCS algorithm of the Eclipse project which in turn is based on Myers' "An O(ND) difference algorithm and its variations" (http://citeseer.ist.psu.edu/myers86ond.html) with range compression (see Wu et al.

's "An O(NP) Sequence Comparison Algorithm").

This implementation supports an upper bound on the execution time.

Complexity: O((M + N)D) worst case time, O(M + N + D^2) expected time, O(M + N) space

Definition at line 39 of file WikiDiff3.php.

## ◆ __construct()

 WikiDiff3::__construct ( \$tooLong = `2000000`, \$powLimit = `1.45` )

Definition at line 60 of file WikiDiff3.php.

References \$powLimit, and \$tooLong.

## ◆ diff()

 WikiDiff3::diff ( \$from, \$to )

Definition at line 65 of file WikiDiff3.php.

References \$added, \$from, \$m, \$n, \$removed, \$to, array(), as, from, lcs_rec(), n, and wfDebug().

Referenced by diff_range().

## ◆ diff_range()

 WikiDiff3::diff_range ( \$from_lines, \$to_lines )

Definition at line 190 of file WikiDiff3.php.

References array(), diff(), and n.

## ◆ find_middle_snake()

 WikiDiff3::find_middle_snake ( \$bottoml1, \$topl1, \$bottoml2, \$topl2, & \$V, & \$snake )
private

Definition at line 269 of file WikiDiff3.php.

References \$from, \$limit, \$to, findMostProgress(), and wfDebug().

Referenced by lcs_rec().

## ◆ findMostProgress()

 static WikiDiff3::findMostProgress ( \$M, \$N, \$limit, \$V )
staticprivate

Definition at line 493 of file WikiDiff3.php.

References \$limit, and array().

Referenced by find_middle_snake().

## ◆ getLcsLength()

 WikiDiff3::getLcsLength ( )
Returns
mixed

Definition at line 575 of file WikiDiff3.php.

References \$length.

## ◆ lcs_rec()

 WikiDiff3::lcs_rec ( \$bottoml1, \$topl1, \$bottoml2, \$topl2, & \$V, & \$snake )
private

Definition at line 225 of file WikiDiff3.php.

References find_middle_snake().

Referenced by diff().

## Member Data Documentation

Definition at line 57 of file WikiDiff3.php.

Referenced by diff().

## ◆ \$from

 WikiDiff3::\$from
private

Definition at line 42 of file WikiDiff3.php.

Referenced by diff(), and find_middle_snake().

## ◆ \$heuristicUsed

 WikiDiff3::\$heuristicUsed

Definition at line 58 of file WikiDiff3.php.

## ◆ \$lcsLengthCorrectedForHeuristic

 WikiDiff3::\$lcsLengthCorrectedForHeuristic = false
private

Definition at line 52 of file WikiDiff3.php.

## ◆ \$length

 WikiDiff3::\$length

Definition at line 55 of file WikiDiff3.php.

Referenced by getLcsLength().

## ◆ \$m

 WikiDiff3::\$m
private

Definition at line 44 of file WikiDiff3.php.

Referenced by diff().

## ◆ \$maxDifferences

 WikiDiff3::\$maxDifferences
private

Definition at line 51 of file WikiDiff3.php.

## ◆ \$n

 WikiDiff3::\$n
private

Definition at line 45 of file WikiDiff3.php.

Referenced by diff().

## ◆ \$powLimit

 WikiDiff3::\$powLimit
private

Definition at line 48 of file WikiDiff3.php.

Referenced by __construct().

## ◆ \$removed

 WikiDiff3::\$removed

Definition at line 56 of file WikiDiff3.php.

Referenced by diff().

## ◆ \$to

 WikiDiff3::\$to
private

Definition at line 43 of file WikiDiff3.php.

Referenced by diff(), and find_middle_snake().

## ◆ \$tooLong

 WikiDiff3::\$tooLong
private

Definition at line 47 of file WikiDiff3.php.

Referenced by __construct().

The documentation for this class was generated from the following file: