MediaWiki  1.23.2
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 ()
 

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
 

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

Author
Guy Van den Broeck

Definition at line 39 of file WikiDiff3.php.

Constructor & Destructor Documentation

◆ __construct()

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

Definition at line 60 of file WikiDiff3.php.

References $powLimit, and $tooLong.

Member Function Documentation

◆ 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

◆ $added

WikiDiff3::$added

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: