MediaWiki
REL1_22
|
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 () | |
Public Attributes | |
$added | |
$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 |
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.
WikiDiff3::__construct | ( | $ | tooLong = 2000000 , |
$ | powLimit = 1.45 |
||
) |
Definition at line 60 of file WikiDiff3.php.
WikiDiff3::diff | ( | $ | from, |
$ | to | ||
) |
WikiDiff3::diff_range | ( | $ | from_lines, |
$ | to_lines | ||
) |
Definition at line 182 of file WikiDiff3.php.
WikiDiff3::find_middle_snake | ( | $ | bottoml1, |
$ | topl1, | ||
$ | bottoml2, | ||
$ | topl2, | ||
&$ | V, | ||
&$ | snake | ||
) | [private] |
Definition at line 258 of file WikiDiff3.php.
References $from, $limit, $to, findMostProgress(), from, and wfDebug().
Referenced by lcs_rec().
static WikiDiff3::findMostProgress | ( | $ | M, |
$ | N, | ||
$ | limit, | ||
$ | V | ||
) | [static, private] |
Definition at line 472 of file WikiDiff3.php.
References $limit, and array().
Referenced by find_middle_snake().
Definition at line 554 of file WikiDiff3.php.
WikiDiff3::lcs_rec | ( | $ | bottoml1, |
$ | topl1, | ||
$ | bottoml2, | ||
$ | topl2, | ||
&$ | V, | ||
&$ | snake | ||
) | [private] |
WikiDiff3::$added |
Definition at line 57 of file WikiDiff3.php.
Referenced by diff().
WikiDiff3::$from [private] |
Definition at line 42 of file WikiDiff3.php.
Referenced by diff(), and find_middle_snake().
WikiDiff3::$heuristicUsed |
Definition at line 58 of file WikiDiff3.php.
WikiDiff3::$lcsLengthCorrectedForHeuristic = false [private] |
Definition at line 52 of file WikiDiff3.php.
WikiDiff3::$length |
Definition at line 55 of file WikiDiff3.php.
WikiDiff3::$m [private] |
Definition at line 44 of file WikiDiff3.php.
Referenced by diff().
WikiDiff3::$maxDifferences [private] |
Definition at line 51 of file WikiDiff3.php.
WikiDiff3::$n [private] |
Definition at line 45 of file WikiDiff3.php.
Referenced by diff().
WikiDiff3::$powLimit [private] |
Definition at line 48 of file WikiDiff3.php.
Referenced by __construct().
WikiDiff3::$removed |
Definition at line 56 of file WikiDiff3.php.
Referenced by diff().
WikiDiff3::$to [private] |
Definition at line 43 of file WikiDiff3.php.
Referenced by diff(), and find_middle_snake().
WikiDiff3::$tooLong [private] |
Definition at line 47 of file WikiDiff3.php.
Referenced by __construct().