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

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

Definition at line 60 of file WikiDiff3.php.

References $powLimit, and $tooLong.

Member Function Documentation

WikiDiff3::diff	(		$from,
			$to
	)

Definition at line 65 of file WikiDiff3.php.

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

Referenced by diff_range().

WikiDiff3::diff_range	(		$from_lines,
			$to_lines
	)

Definition at line 190 of file WikiDiff3.php.

References diff(), and n.

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

private

Definition at line 269 of file WikiDiff3.php.

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

Referenced by lcs_rec().

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

staticprivate

Definition at line 493 of file WikiDiff3.php.

References $limit.

WikiDiff3::getLcsLength

(

)

Returns

mixed

Definition at line 575 of file WikiDiff3.php.

References $length.

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

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.

Referenced by getLcsLength().

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().

---

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

• includes/diff/WikiDiff3.php