MediaWiki master
|
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=2_000_000, $powLimit=1.45) | |
diff ( $from_lines, $to_lines) | |
Performs diff. | |
getLcsLength () | |
setBailoutComplexity ( $value) | |
Sets the complexity (in comparison operations) that can't be exceeded. | |
Public Attributes | |
array | $added |
bool | $heuristicUsed |
int | $length |
array | $removed |
Protected Member Functions | |
diffInternal (array $from, array $to) | |
Protected Attributes | |
int | $bailoutComplexity = 0 |
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.
Some ideas (and a bit of code) are from analyze.c, from GNU diffutils-2.7, which can be found at: ftp://gnudist.gnu.org/pub/gnu/diffutils/diffutils-2.7.tar.gz
Complexity: O((M + N)D) worst case time, O(M + N + D^2) expected time, O(M + N) space
Definition at line 48 of file DiffEngine.php.
Wikimedia\Diff\DiffEngine::__construct | ( | $tooLong = 2_000_000, | |
$powLimit = 1.45 ) |
int | $tooLong | |
float | $powLimit |
Definition at line 88 of file DiffEngine.php.
Wikimedia\Diff\DiffEngine::diff | ( | $from_lines, | |
$to_lines ) |
Performs diff.
string[] | $from_lines | |
string[] | $to_lines |
ComplexityException |
Definition at line 102 of file DiffEngine.php.
References Wikimedia\Diff\DiffEngine\diffInternal().
|
protected |
string[] | $from | |
string[] | $to |
ComplexityException |
Definition at line 303 of file DiffEngine.php.
References Wikimedia\Diff\DiffEngine\$added, and Wikimedia\Diff\DiffEngine\$removed.
Referenced by Wikimedia\Diff\DiffEngine\diff().
Wikimedia\Diff\DiffEngine::getLcsLength | ( | ) |
Definition at line 804 of file DiffEngine.php.
References Wikimedia\Diff\DiffEngine\$length.
Wikimedia\Diff\DiffEngine::setBailoutComplexity | ( | $value | ) |
Sets the complexity (in comparison operations) that can't be exceeded.
int | $value |
Definition at line 159 of file DiffEngine.php.
Referenced by Wikimedia\Diff\Diff\__construct().
array Wikimedia\Diff\DiffEngine::$added |
Definition at line 80 of file DiffEngine.php.
Referenced by Wikimedia\Diff\DiffEngine\diffInternal().
|
protected |
Definition at line 66 of file DiffEngine.php.
bool Wikimedia\Diff\DiffEngine::$heuristicUsed |
Definition at line 82 of file DiffEngine.php.
int Wikimedia\Diff\DiffEngine::$length |
Definition at line 76 of file DiffEngine.php.
Referenced by Wikimedia\Diff\DiffEngine\getLcsLength().
array Wikimedia\Diff\DiffEngine::$removed |
Definition at line 78 of file DiffEngine.php.
Referenced by Wikimedia\Diff\DiffEngine\diffInternal().