It is guaranteed that the comparisons will always be done as o1.equals(o2) where o1 belongs to the first sequence and o2 belongs to the second sequence. This can be important if subclassing is used for some elements in the first sequence and the equals method is specialized.

Comparison can be seen from two points of view: either as giving the smallest modification allowing to transform the first sequence into the second one, or as giving the longest sequence which is a subsequence of both initial sequences. The equals method is used to compare objects, so any object can be put into sequences. Modifications include deleting, inserting or keeping one object, starting from the beginning of the first sequence.

This class implements the comparison algorithm, which is the very efficient algorithm from Eugene W. Myers An O(ND) Difference Algorithm and Its Variations. This algorithm produces the shortest possible edit script containing all the commands needed to transform the first sequence into the second one.

This code has been adapted from Apache Commons Collections 4.0.

Nested and Inner Type Summary

Modifier and Type	Class and Description
private static class	StringsComparator.Snake Holds the end part of a path under construction in a `StringsComparator`.

Field Summary

Modifier and Type	Field and Description
private final String	left First character sequence.
private final String	right Second character sequence.
private final int[]	vDown Temporary array.
private final int[]	vUp Temporary array.

Constructor Summary

Access	Constructor and Description
public	StringsComparator(final String first character sequence to be compared. left, final String second character sequence to be compared. right) Constructs a new instance of StringsComparator.

Method Summary

Modifier and Type	Method and Description
private void	buildScript(final int the begin of the first sequence to be compared. start1, final int the end of the first sequence to be compared. end1, final int the begin of the second sequence to be compared. start2, final int the end of the second sequence to be compared. end2, final EditScript<Character> the edited script. script) Builds an edit script.
private StringsComparator.Snake	Returns: The snake built. buildSnake(final int the value of the start of the snake. start, final int the value of the diagonal of the snake. diag, final int the value of the end of the first sequence to be compared. end1, final int the value of the end of the second sequence to be compared. end2) Builds a snake.
private StringsComparator.Snake	Returns: The middle snake. getMiddleSnake(final int the begin of the first sequence to be compared. start1, final int the end of the first sequence to be compared. end1, final int the begin of the second sequence to be compared. start2, final int the end of the second sequence to be compared. end2) Gets the middle snake corresponding to two subsequences of the main sequences.
public EditScript<Character>	Returns: The edit script resulting from the comparison of the two sequences. getScript() Gets the `EditScript` object.

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

left	back to summary
private final String left First character sequence.

right	back to summary
private final String right Second character sequence.

vDown	back to summary
private final int[] vDown Temporary array.

vUp	back to summary
private final int[] vUp Temporary array.

Constructor Detail

StringsComparator back to summary

StringsComparator	back to summary
public StringsComparator(final String left, final String right) Constructs a new instance of StringsComparator. It is guaranteed that the comparisons will always be done as `o1.equals(o2)` where `o1` belongs to the first sequence and `o2` belongs to the second sequence. This can be important if subclassing is used for some elements in the first sequence and the `equals` method is specialized. Parameters left:String first character sequence to be compared. right:String second character sequence to be compared.

public StringsComparator(final String left, final String right)

Constructs a new instance of StringsComparator.

It is guaranteed that the comparisons will always be done as o1.equals(o2) where o1 belongs to the first sequence and o2 belongs to the second sequence. This can be important if subclassing is used for some elements in the first sequence and the equals method is specialized.

Parameters

left:String: first character sequence to be compared.
right:String: second character sequence to be compared.

Method Detail

buildScript	back to summary
private void buildScript(final int start1, final int end1, final int start2, final int end2, final EditScript<Character> script) Builds an edit script. Parameters start1:int the begin of the first sequence to be compared. end1:int the end of the first sequence to be compared. start2:int the begin of the second sequence to be compared. end2:int the end of the second sequence to be compared. script:EditScript<Character> the edited script.

buildScript

back to summary

private void buildScript(final int start1, final int end1, final int start2, final int end2, final EditScript<Character> script)

Builds an edit script.

Parameters

start1:int: the begin of the first sequence to be compared.
end1:int: the end of the first sequence to be compared.
start2:int: the begin of the second sequence to be compared.
end2:int: the end of the second sequence to be compared.
script:EditScript<Character>: the edited script.

buildSnake	back to summary
private StringsComparator.Snake buildSnake(final int start, final int diag, final int end1, final int end2) Builds a snake. Parameters start:int the value of the start of the snake. diag:int the value of the diagonal of the snake. end1:int the value of the end of the first sequence to be compared. end2:int the value of the end of the second sequence to be compared. Returns:StringsComparator.Snake The snake built.

buildSnake

back to summary

private StringsComparator.Snake buildSnake(final int start, final int diag, final int end1, final int end2)

Builds a snake.

Parameters

start:int: the value of the start of the snake.
diag:int: the value of the diagonal of the snake.
end1:int: the value of the end of the first sequence to be compared.
end2:int: the value of the end of the second sequence to be compared.

Returns:StringsComparator.Snake

The snake built.

getMiddleSnake	back to summary
private StringsComparator.Snake getMiddleSnake(final int start1, final int end1, final int start2, final int end2) Gets the middle snake corresponding to two subsequences of the main sequences. The snake is found using the MYERS Algorithm (this algorithms has also been implemented in the GNU diff program). This algorithm is explained in Eugene Myers article: An O(ND) Difference Algorithm and Its Variations. Parameters start1:int the begin of the first sequence to be compared. end1:int the end of the first sequence to be compared. start2:int the begin of the second sequence to be compared. end2:int the end of the second sequence to be compared. Returns:StringsComparator.Snake The middle snake.

getMiddleSnake

back to summary

private StringsComparator.Snake getMiddleSnake(final int start1, final int end1, final int start2, final int end2)

Gets the middle snake corresponding to two subsequences of the main sequences.

The snake is found using the MYERS Algorithm (this algorithms has also been implemented in the GNU diff program). This algorithm is explained in Eugene Myers article: An O(ND) Difference Algorithm and Its Variations.

Parameters

start1:int: the begin of the first sequence to be compared.
end1:int: the end of the first sequence to be compared.
start2:int: the begin of the second sequence to be compared.
end2:int: the end of the second sequence to be compared.

Returns:StringsComparator.Snake

The middle snake.

getScript back to summary

getScript	back to summary
public EditScript<Character> getScript() Gets the `EditScript` object. It is guaranteed that the objects embedded in the `insert commands` come from the second sequence and that the objects embedded in either the `delete commands` or `keep commands` come from the first sequence. This can be important if subclassing is used for some elements in the first sequence and the `equals` method is specialized. Returns:EditScript<Character> The edit script resulting from the comparison of the two sequences.

public EditScript<Character> getScript()

Gets the EditScript object.

It is guaranteed that the objects embedded in the insert commands come from the second sequence and that the objects embedded in either the delete commands or keep commands come from the first sequence. This can be important if subclassing is used for some elements in the first sequence and the equals method is specialized.

Returns:EditScript<Character>: The edit script resulting from the comparison of the two sequences.

org.apache.commons.text.diff back to summary

private final Class StringsComparator.Snake

Class Inheritance

extends Object

java.lang.Object
org.apache.commons.text.diff.StringsComparator.Snake

Holds the end part of a path under construction in a StringsComparator.

Field Summary

Modifier and Type	Field and Description
private final int	diag Diagonal number.
private final int	end End index.
private final int	start Start index.

Constructor Summary

Access	Constructor and Description
pack-priv	Snake(final int start index of the snake. start, final int end index of the snake. end, final int diagonal number. diag) Constructs a new instance of Snake with specified indices.

Method Summary

Modifier and Type	Method and Description
public int	Returns: diagonal number of the snake. getDiag() Gets the diagonal number of the snake.
public int	Returns: end index of the snake. getEnd() Gets the end index of the snake.
public int	Returns: start index of the snake. getStart() Gets the start index of the snake.

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

diag	back to summary
private final int diag Diagonal number.

end	back to summary
private final int end End index.

start	back to summary
private final int start Start index.

Constructor Detail

Snake	back to summary
pack-priv Snake(final int start, final int end, final int diag) Constructs a new instance of Snake with specified indices. Parameters start:int start index of the snake. end:int end index of the snake. diag:int diagonal number.

Snake

back to summary

pack-priv Snake(final int start, final int end, final int diag)

Constructs a new instance of Snake with specified indices.

Parameters

start:int: start index of the snake.
end:int: end index of the snake.
diag:int: diagonal number.

Method Detail

getDiag	back to summary
public int getDiag() Gets the diagonal number of the snake. Returns:int diagonal number of the snake.

getDiag

back to summary

public int getDiag()

Gets the diagonal number of the snake.

Returns:int: diagonal number of the snake.

getEnd	back to summary
public int getEnd() Gets the end index of the snake. Returns:int end index of the snake.

getEnd

back to summary

public int getEnd()

Gets the end index of the snake.

Returns:int: end index of the snake.

getStart	back to summary
public int getStart() Gets the start index of the snake. Returns:int start index of the snake.

getStart

back to summary

public int getStart()

Gets the start index of the snake.

Returns:int: start index of the snake.

public Class StringsComparator

Nested and Inner Type Summary

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

private final Class StringsComparator.Snake

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail