Collaboration diagram for org.buildmlearn.toolkit.utilities.diff_match_patch:

Classes
class	Diff

class	LinesToCharsResult

enum	Operation

class	Patch

Public Member Functions
LinkedList< Diff >	diff_main (String text1, String text2)

LinkedList< Diff >	diff_main (String text1, String text2, boolean checklines)

LinkedList< Diff >	diff_WordMode (String text1, String text2)

int	diff_commonPrefix (String text1, String text2)

int	diff_commonSuffix (String text1, String text2)

void	diff_cleanupSemantic (LinkedList< Diff > diffs)

void	diff_cleanupSemanticLossless (LinkedList< Diff > diffs)

void	diff_cleanupEfficiency (LinkedList< Diff > diffs)

void	diff_cleanupMerge (LinkedList< Diff > diffs)

int	diff_xIndex (LinkedList< Diff > diffs, int loc)

String[]	diff_prettyHtml (LinkedList< Diff > diffs)

String	diff_text1 (LinkedList< Diff > diffs)

String	diff_text2 (LinkedList< Diff > diffs)

int	diff_levenshtein (LinkedList< Diff > diffs)

String	diff_toDelta (LinkedList< Diff > diffs)

LinkedList< Diff >	diff_fromDelta (String text1, String delta) throws IllegalArgumentException

int	match_main (String text, String pattern, int loc)

LinkedList< Patch >	patch_make (String text1, String text2)

LinkedList< Patch >	patch_make (LinkedList< Diff > diffs)

LinkedList< Patch >	patch_make (String text1, String text2, LinkedList< Diff > diffs)

LinkedList< Patch >	patch_make (String text1, LinkedList< Diff > diffs)

LinkedList< Patch >	patch_deepCopy (LinkedList< Patch > patches)

Object[]	patch_apply (LinkedList< Patch > patches, String text)

String	patch_addPadding (LinkedList< Patch > patches)

void	patch_splitMax (LinkedList< Patch > patches)

String	patch_toText (List< Patch > patches)

List< Patch >	patch_fromText (String textline) throws IllegalArgumentException

Public Attributes
float	Diff_Timeout = 1.0f

short	Diff_EditCost = 4

float	Match_Threshold = 0.5f

int	Match_Distance = 1000

float	Patch_DeleteThreshold = 0.5f

short	Patch_Margin = 4

Protected Member Functions
LinkedList< Diff >	diff_bisect (String text1, String text2, long deadline)

LinesToCharsResult	diff_linesToChars (String text1, String text2)

LinesToCharsResult	diff_wordsToChars (String text1, String text2)

void	diff_charsToLines (LinkedList< Diff > diffs, List< String > lineArray)

int	diff_commonOverlap (String text1, String text2)

String[]	diff_halfMatch (String text1, String text2)

int	match_bitap (String text, String pattern, int loc)

Map< Character, Integer >	match_alphabet (String pattern)

void	patch_addContext (Patch patch, String text)

Private Member Functions
LinkedList< Diff >	diff_main (String text1, String text2, boolean checklines, long deadline)

LinkedList< Diff >	diff_compute (String text1, String text2, boolean checklines, long deadline)

LinkedList< Diff >	diff_lineMode (String text1, String text2, long deadline)

LinkedList< Diff >	diff_bisectSplit (String text1, String text2, int x, int y, long deadline)

String	diff_linesToCharsMunge (String text, List< String > lineArray, Map< String, Integer > lineHash)

String	diff_wordsToCharsMunge (String text, List< String > lineArray, Map< String, Integer > lineHash)

String[]	diff_halfMatchI (String longtext, String shorttext, int i)

int	diff_cleanupSemanticScore (String one, String two)

double	match_bitapScore (int e, int x, int loc, String pattern)

Static Private Member Functions
static String	unescapeForEncodeUriCompatability (String str)

Private Attributes
short	Match_MaxBits = 32

Pattern	BLANKLINEEND = Pattern.compile("\\n\\r?\\n\\Z", Pattern.DOTALL)

Pattern	BLANKLINESTART = Pattern.compile("\\A\\r?\\n\\r?\\n", Pattern.DOTALL)

Detailed Description

Class containing the diff, match and patch methods. Also contains the behaviour settings.

Member Function Documentation

LinkedList<Diff> org.buildmlearn.toolkit.utilities.diff_match_patch.diff_bisect	(	String	text1,
		String	text2,
		long	deadline
	)

protected

Find the 'middle snake' of a diff, split the problem in two and return the recursively constructed diff. See Myers 1986 paper: An O(ND) Difference Algorithm and Its Variations.

Parameters

text1	Old string to be diffed.
text2	New string to be diffed.
deadline	Time at which to bail if not yet complete.

Returns: LinkedList of Diff objects.

LinkedList<Diff> org.buildmlearn.toolkit.utilities.diff_match_patch.diff_bisectSplit	(	String	text1,
		String	text2,
		int	x,
		int	y,
		long	deadline
	)

private

Given the location of the 'middle snake', split the diff in two parts and recurse.

Parameters

text1	Old string to be diffed.
text2	New string to be diffed.
x	Index of split point in text1.
y	Index of split point in text2.
deadline	Time at which to bail if not yet complete.

Returns: LinkedList of Diff objects.

void org.buildmlearn.toolkit.utilities.diff_match_patch.diff_charsToLines	(	LinkedList< Diff >	diffs,
		List< String >	lineArray
	)

protected

Rehydrate the text in a diff from a string of line hashes to real lines of text.

Parameters

diffs	LinkedList of Diff objects.
lineArray	List of unique strings.

void org.buildmlearn.toolkit.utilities.diff_match_patch.diff_cleanupEfficiency ( LinkedList< Diff > diffs )

Reduce the number of edits by eliminating operationally trivial equalities.

Parameters

diffs LinkedList of Diff objects.

void org.buildmlearn.toolkit.utilities.diff_match_patch.diff_cleanupMerge ( LinkedList< Diff > diffs )

Reorder and merge like edit sections. Merge equalities. Any edit section can move as long as it doesn't cross an equality.

Parameters

diffs LinkedList of Diff objects.

void org.buildmlearn.toolkit.utilities.diff_match_patch.diff_cleanupSemantic ( LinkedList< Diff > diffs )

Reduce the number of edits by eliminating semantically trivial equalities.

Parameters

diffs LinkedList of Diff objects.

void org.buildmlearn.toolkit.utilities.diff_match_patch.diff_cleanupSemanticLossless ( LinkedList< Diff > diffs )

Look for single edits surrounded on both sides by equalities which can be shifted sideways to align the edit to a word boundary. e.g: The c<ins>at c</ins>ame. -> The <ins>cat </ins>came.

Parameters

diffs LinkedList of Diff objects.

int org.buildmlearn.toolkit.utilities.diff_match_patch.diff_cleanupSemanticScore	(	String	one,
		String	two
	)

private

Given two strings, compute a score representing whether the internal boundary falls on logical boundaries. Scores range from 6 (best) to 0 (worst).

Parameters

one	First string.
two	Second string.

Returns: The score.

int org.buildmlearn.toolkit.utilities.diff_match_patch.diff_commonOverlap	(	String	text1,
		String	text2
	)

protected

Determine if the suffix of one string is the prefix of another.

Parameters

text1	First string.
text2	Second string.

Returns: The number of characters common to the end of the first string and the start of the second string.

int org.buildmlearn.toolkit.utilities.diff_match_patch.diff_commonPrefix	(	String	text1,
		String	text2
	)

Determine the common prefix of two strings

Parameters

text1	First string.
text2	Second string.

Returns: The number of characters common to the start of each string.

int org.buildmlearn.toolkit.utilities.diff_match_patch.diff_commonSuffix	(	String	text1,
		String	text2
	)

Determine the common suffix of two strings

Parameters

text1	First string.
text2	Second string.

Returns: The number of characters common to the end of each string.

LinkedList<Diff> org.buildmlearn.toolkit.utilities.diff_match_patch.diff_compute	(	String	text1,
		String	text2,
		boolean	checklines,
		long	deadline
	)

private

Find the differences between two texts. Assumes that the texts do not have any common prefix or suffix.

Parameters

text1	Old string to be diffed.
text2	New string to be diffed.
checklines	Speedup flag. If false, then don't run a line-level diff first to identify the changed areas. If true, then run a faster slightly less optimal diff.
deadline	Time when the diff should be complete by.

Returns: Linked List of Diff objects.

LinkedList<Diff> org.buildmlearn.toolkit.utilities.diff_match_patch.diff_fromDelta	(	String	text1,
		String	delta
	)		throws IllegalArgumentException

Given the original text1, and an encoded string which describes the operations required to transform text1 into text2, compute the full diff.

Parameters

text1	Source string for the diff.
delta	Delta text.

Returns: Array of Diff objects or null if invalid.

Exceptions

IllegalArgumentException If invalid input.

String [] org.buildmlearn.toolkit.utilities.diff_match_patch.diff_halfMatch	(	String	text1,
		String	text2
	)

protected

Do the two texts share a substring which is at least half the length of the longer text? This speedup can produce non-minimal diffs.

Parameters

text1	First string.
text2	Second string.

Returns: Five element String array, containing the prefix of text1, the suffix of text1, the prefix of text2, the suffix of text2 and the common middle. Or null if there was no match.

String [] org.buildmlearn.toolkit.utilities.diff_match_patch.diff_halfMatchI	(	String	longtext,
		String	shorttext,
		int	i
	)

private

Does a substring of shorttext exist within longtext such that the substring is at least half the length of longtext?

Parameters

longtext	Longer string.
shorttext	Shorter string.
i	Start index of quarter length substring within longtext.

Returns: Five element String array, containing the prefix of longtext, the suffix of longtext, the prefix of shorttext, the suffix of shorttext and the common middle. Or null if there was no match.

int org.buildmlearn.toolkit.utilities.diff_match_patch.diff_levenshtein ( LinkedList< Diff > diffs )

Compute the Levenshtein distance; the number of inserted, deleted or substituted characters.

Parameters

diffs LinkedList of Diff objects.

Returns: Number of changes.

LinkedList<Diff> org.buildmlearn.toolkit.utilities.diff_match_patch.diff_lineMode	(	String	text1,
		String	text2,
		long	deadline
	)

private

Do a quick line-level diff on both strings, then rediff the parts for greater accuracy. This speedup can produce non-minimal diffs.

Parameters

text1	Old string to be diffed.
text2	New string to be diffed.
deadline	Time when the diff should be complete by.

Returns: Linked List of Diff objects.

LinesToCharsResult org.buildmlearn.toolkit.utilities.diff_match_patch.diff_linesToChars	(	String	text1,
		String	text2
	)

protected

Split two texts into a list of strings. Reduce the texts to a string of hashes where each Unicode character represents one line.

Parameters

text1	First string.
text2	Second string.

Returns: An object containing the encoded text1, the encoded text2 and the List of unique strings. The zeroth element of the List of unique strings is intentionally blank.

String org.buildmlearn.toolkit.utilities.diff_match_patch.diff_linesToCharsMunge	(	String	text,
		List< String >	lineArray,
		Map< String, Integer >	lineHash
	)

private

Split a text into a list of strings. Reduce the texts to a string of hashes where each Unicode character represents one line.

Parameters

text	String to encode.
lineArray	List of unique strings.
lineHash	Map of strings to indices.

Returns: Encoded string.

LinkedList<Diff> org.buildmlearn.toolkit.utilities.diff_match_patch.diff_main	(	String	text1,
		String	text2
	)

Find the differences between two texts. Run a faster, slightly less optimal diff. This method allows the 'checklines' of diff_main() to be optional. Most of the time checklines is wanted, so default to true.

Parameters

text1	Old string to be diffed.
text2	New string to be diffed.

Returns: Linked List of Diff objects.

LinkedList<Diff> org.buildmlearn.toolkit.utilities.diff_match_patch.diff_main	(	String	text1,
		String	text2,
		boolean	checklines
	)

Find the differences between two texts.

Parameters

text1	Old string to be diffed.
text2	New string to be diffed.
checklines	Speedup flag. If false, then don't run a line-level diff first to identify the changed areas. If true, then run a faster slightly less optimal diff.

Returns: Linked List of Diff objects.

LinkedList<Diff> org.buildmlearn.toolkit.utilities.diff_match_patch.diff_main	(	String	text1,
		String	text2,
		boolean	checklines,
		long	deadline
	)

private

Find the differences between two texts. Simplifies the problem by stripping any common prefix or suffix off the texts before diffing.

Parameters

text1	Old string to be diffed.
text2	New string to be diffed.
checklines	Speedup flag. If false, then don't run a line-level diff first to identify the changed areas. If true, then run a faster slightly less optimal diff.
deadline	Time when the diff should be complete by. Used internally for recursive calls. Users should set DiffTimeout instead.

Returns: Linked List of Diff objects.

String [] org.buildmlearn.toolkit.utilities.diff_match_patch.diff_prettyHtml ( LinkedList< Diff > diffs )

Convert a Diff list into a pretty HTML report.

Parameters

diffs LinkedList of Diff objects.

Returns: HTML representation. + number of equal words in an array where first element is HTML representation and second is number of Equal words.

String org.buildmlearn.toolkit.utilities.diff_match_patch.diff_text1 ( LinkedList< Diff > diffs )

Compute and return the source text (all equalities and deletions).

Parameters

diffs LinkedList of Diff objects.

Returns: Source text.

String org.buildmlearn.toolkit.utilities.diff_match_patch.diff_text2 ( LinkedList< Diff > diffs )

Compute and return the destination text (all equalities and insertions).

Parameters

diffs LinkedList of Diff objects.

Returns: Destination text.

String org.buildmlearn.toolkit.utilities.diff_match_patch.diff_toDelta ( LinkedList< Diff > diffs )

Crush the diff into an encoded string which describes the operations required to transform text1 into text2. E.g. =3-2+ing -> Keep 3 chars, delete 2 chars, insert 'ing'. Operations are tab-separated. Inserted text is escaped using xx notation.

Parameters

diffs Array of Diff objects.

Returns: Delta text.

LinkedList<Diff> org.buildmlearn.toolkit.utilities.diff_match_patch.diff_WordMode	(	String	text1,
		String	text2
	)

LinesToCharsResult org.buildmlearn.toolkit.utilities.diff_match_patch.diff_wordsToChars	(	String	text1,
		String	text2
	)

protected

Split two texts into a list of strings. Reduce the texts to a string of hashes where each Unicode character represents one word.

Parameters

text1	First string.
text2	Second string.

Returns: An object containing the encoded text1, the encoded text2 and the List of unique strings. The zeroth element of the List of unique strings is intentionally blank.

String org.buildmlearn.toolkit.utilities.diff_match_patch.diff_wordsToCharsMunge	(	String	text,
		List< String >	lineArray,
		Map< String, Integer >	lineHash
	)

private

Split a text into a list of strings. Reduce the texts to a string of hashes where each Unicode character represents one word.

Parameters

text	String to encode.
lineArray	List of unique strings.
lineHash	Map of strings to indices.

Returns: Encoded string.

int org.buildmlearn.toolkit.utilities.diff_match_patch.diff_xIndex	(	LinkedList< Diff >	diffs,
		int	loc
	)

loc is a location in text1, compute and return the equivalent location in text2. e.g. "The cat" vs "The big cat", 1->1, 5->8

Parameters

diffs	LinkedList of Diff objects.
loc	Location within text1.

Returns: Location within text2.

Map<Character, Integer> org.buildmlearn.toolkit.utilities.diff_match_patch.match_alphabet ( String pattern )

protected

Initialise the alphabet for the Bitap algorithm.

Parameters

pattern The text to encode.

Returns: Hash of character locations.

int org.buildmlearn.toolkit.utilities.diff_match_patch.match_bitap	(	String	text,
		String	pattern,
		int	loc
	)

protected

Locate the best instance of 'pattern' in 'text' near 'loc' using the Bitap algorithm. Returns -1 if no match found.

Parameters

text	The text to search.
pattern	The pattern to search for.
loc	The location to search around.

Returns: Best match index or -1.

double org.buildmlearn.toolkit.utilities.diff_match_patch.match_bitapScore	(	int	e,
		int	x,
		int	loc,
		String	pattern
	)

private

Compute and return the score for a match with e errors and x location.

Parameters

e	Number of errors in match.
x	Location of match.
loc	Expected location of match.
pattern	Pattern being sought.

Returns: Overall score for match (0.0 = good, 1.0 = bad).

int org.buildmlearn.toolkit.utilities.diff_match_patch.match_main	(	String	text,
		String	pattern,
		int	loc
	)

Locate the best instance of 'pattern' in 'text' near 'loc'. Returns -1 if no match found.

Parameters

text	The text to search.
pattern	The pattern to search for.
loc	The location to search around.

Returns: Best match index or -1.

void org.buildmlearn.toolkit.utilities.diff_match_patch.patch_addContext	(	Patch	patch,
		String	text
	)

protected

Increase the context until it is unique, but don't let the pattern expand beyond Match_MaxBits.

Parameters

patch	The patch to grow.
text	Source text.

String org.buildmlearn.toolkit.utilities.diff_match_patch.patch_addPadding ( LinkedList< Patch > patches )

Add some padding on text start and end so that edges can match something. Intended to be called only from within patch_apply.

Parameters

patches Array of Patch objects.

Returns: The padding string added to each side.

Object [] org.buildmlearn.toolkit.utilities.diff_match_patch.patch_apply	(	LinkedList< Patch >	patches,
		String	text
	)

Merge a set of patches onto the text. Return a patched text, as well as an array of true/false values indicating which patches were applied.

Parameters

patches	Array of Patch objects
text	Old text.

Returns: Two element Object array, containing the new text and an array of boolean values.

LinkedList<Patch> org.buildmlearn.toolkit.utilities.diff_match_patch.patch_deepCopy ( LinkedList< Patch > patches )

Given an array of patches, return another array that is identical.

Parameters

patches Array of Patch objects.

Returns: Array of Patch objects.

List<Patch> org.buildmlearn.toolkit.utilities.diff_match_patch.patch_fromText ( String textline ) throws IllegalArgumentException

Parse a textual representation of patches and return a List of Patch objects.

Parameters

textline Text representation of patches.

Returns: List of Patch objects.

Exceptions

IllegalArgumentException If invalid input.

LinkedList<Patch> org.buildmlearn.toolkit.utilities.diff_match_patch.patch_make	(	String	text1,
		String	text2
	)

Compute a list of patches to turn text1 into text2. A set of diffs will be computed.

Parameters

text1	Old text.
text2	New text.

Returns: LinkedList of Patch objects.

LinkedList<Patch> org.buildmlearn.toolkit.utilities.diff_match_patch.patch_make ( LinkedList< Diff > diffs )

Compute a list of patches to turn text1 into text2. text1 will be derived from the provided diffs.

Parameters

diffs Array of Diff objects for text1 to text2.

Returns: LinkedList of Patch objects.

LinkedList<Patch> org.buildmlearn.toolkit.utilities.diff_match_patch.patch_make	(	String	text1,
		String	text2,
		LinkedList< Diff >	diffs
	)

Compute a list of patches to turn text1 into text2. text2 is ignored, diffs are the delta between text1 and text2.

Parameters

text1	Old text
text2	Ignored.
diffs	Array of Diff objects for text1 to text2.

Returns: LinkedList of Patch objects.

Deprecated:: Prefer patch_make(String text1, LinkedList<Diff> diffs).

LinkedList<Patch> org.buildmlearn.toolkit.utilities.diff_match_patch.patch_make	(	String	text1,
		LinkedList< Diff >	diffs
	)

Compute a list of patches to turn text1 into text2. text2 is not provided, diffs are the delta between text1 and text2.

Parameters

text1	Old text.
diffs	Array of Diff objects for text1 to text2.

Returns: LinkedList of Patch objects.

void org.buildmlearn.toolkit.utilities.diff_match_patch.patch_splitMax ( LinkedList< Patch > patches )

Look through the patches and break up any which are longer than the maximum limit of the match algorithm. Intended to be called only from within patch_apply.

Parameters

patches LinkedList of Patch objects.

String org.buildmlearn.toolkit.utilities.diff_match_patch.patch_toText ( List< Patch > patches )

Take a list of patches and return a textual representation.

Parameters

patches List of Patch objects.

Returns: Text representation of patches.

static String org.buildmlearn.toolkit.utilities.diff_match_patch.unescapeForEncodeUriCompatability ( String str )

staticprivate

Unescape selected chars for compatability with JavaScript's encodeURI. In speed critical applications this could be dropped since the receiving application will certainly decode these fine. Note that this function is case-sensitive. Thus "%3f" would not be unescaped. But this is ok because it is only called with the output of URLEncoder.encode which returns uppercase hex.

Example: "%3F" -> "?", "%24" -> "$", etc.

Parameters

str	The string to escape.

Returns: The escaped string.

Member Data Documentation

Pattern org.buildmlearn.toolkit.utilities.diff_match_patch.BLANKLINEEND = Pattern.compile("\\n\\r?\\n\\Z", Pattern.DOTALL)

private

Pattern org.buildmlearn.toolkit.utilities.diff_match_patch.BLANKLINESTART = Pattern.compile("\\A\\r?\\n\\r?\\n", Pattern.DOTALL)

private

short org.buildmlearn.toolkit.utilities.diff_match_patch.Diff_EditCost = 4

Cost of an empty edit operation in terms of edit characters.

float org.buildmlearn.toolkit.utilities.diff_match_patch.Diff_Timeout = 1.0f

Number of seconds to map a diff before giving up (0 for infinity).

int org.buildmlearn.toolkit.utilities.diff_match_patch.Match_Distance = 1000

How far to search for a match (0 = exact location, 1000+ = broad match). A match this many characters away from the expected location will add 1.0 to the score (0.0 is a perfect match).

short org.buildmlearn.toolkit.utilities.diff_match_patch.Match_MaxBits = 32

private

The number of bits in an int.

float org.buildmlearn.toolkit.utilities.diff_match_patch.Match_Threshold = 0.5f

At what point is no match declared (0.0 = perfection, 1.0 = very loose).

float org.buildmlearn.toolkit.utilities.diff_match_patch.Patch_DeleteThreshold = 0.5f

When deleting a large block of text (over ~64 characters), how close do the contents have to be to match the expected contents. (0.0 = perfection, 1.0 = very loose). Note that Match_Threshold controls how closely the end points of a delete need to match.

short org.buildmlearn.toolkit.utilities.diff_match_patch.Patch_Margin = 4

Chunk size for context length.

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

source-code/app/src/main/java/org/buildmlearn/toolkit/utilities/diff_match_patch.java

Classes

Public Member Functions

Public Attributes

Protected Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Function Documentation

Member Data Documentation