Wikimedia\Diff\DiffEngine 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=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

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.

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

Author

Guy Van den Broeck, Geoffrey T. Dairiki, Tim Starling

Definition at line 48 of file DiffEngine.php.

Constructor & Destructor Documentation

__construct()

Wikimedia\Diff\DiffEngine::__construct	(		$tooLong = 2_000_000,
			$powLimit = 1.45 )

Parameters

int	$tooLong
float	$powLimit

Definition at line 88 of file DiffEngine.php.

Member Function Documentation

diff()

Wikimedia\Diff\DiffEngine::diff	(		$from_lines,
			$to_lines )

Performs diff.

Parameters

string[]	$from_lines
string[]	$to_lines

Exceptions

ComplexityException

Returns

DiffOp[]

Definition at line 102 of file DiffEngine.php.

References Wikimedia\Diff\DiffEngine\diffInternal().

diffInternal()

Wikimedia\Diff\DiffEngine::diffInternal ( array $from, array $to )

protected

Parameters

string[]	$from
string[]	$to

Exceptions

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

getLcsLength()

Wikimedia\Diff\DiffEngine::getLcsLength

(

)

Returns

int

Definition at line 804 of file DiffEngine.php.

References Wikimedia\Diff\DiffEngine\$length.

setBailoutComplexity()

Wikimedia\Diff\DiffEngine::setBailoutComplexity

(

$value

)

Sets the complexity (in comparison operations) that can't be exceeded.

Parameters

int

$value

Definition at line 159 of file DiffEngine.php.

Referenced by Wikimedia\Diff\Diff\__construct().

Member Data Documentation

$added

array Wikimedia\Diff\DiffEngine::$added

Definition at line 80 of file DiffEngine.php.

Referenced by Wikimedia\Diff\DiffEngine\diffInternal().

$bailoutComplexity

int Wikimedia\Diff\DiffEngine::$bailoutComplexity = 0

protected

Definition at line 66 of file DiffEngine.php.

$heuristicUsed

bool Wikimedia\Diff\DiffEngine::$heuristicUsed

Definition at line 82 of file DiffEngine.php.

$length

int Wikimedia\Diff\DiffEngine::$length

Definition at line 76 of file DiffEngine.php.

Referenced by Wikimedia\Diff\DiffEngine\getLcsLength().

$removed

array Wikimedia\Diff\DiffEngine::$removed

Definition at line 78 of file DiffEngine.php.

Referenced by Wikimedia\Diff\DiffEngine\diffInternal().

---

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

• includes/libs/Diff/DiffEngine.php