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

List of all members.

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 excution 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, $m, $n, $removed, $to, lcs_rec(), n, and wfDebug().

Referenced by diff_range().

Here is the call graph for this function:

Here is the caller graph for this function:

WikiDiff3::diff_range	(	$	from_lines,
		$	to_lines
	)

Definition at line 182 of file WikiDiff3.php.

References diff(), and n.

Here is the call graph for this function:

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

Definition at line 258 of file WikiDiff3.php.

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

Referenced by lcs_rec().

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 472 of file WikiDiff3.php.

References $limit.

Referenced by find_middle_snake().

Here is the caller graph for this function:

WikiDiff3::getLcsLength

(

)

Returns:

mixed

Definition at line 555 of file WikiDiff3.php.

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

Definition at line 216 of file WikiDiff3.php.

References find_middle_snake().

Referenced by diff().

Here is the call graph for this function:

Here is the caller graph for this function:

---

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.

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