This class allows to compare two objects sequences.

The two sequences can hold any object type, as only the equals method is used to compare the elements of the sequences. 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.

Nested and Inner Type Summary

Modifier and Type	Class and Description
private static class	SequencesComparator.Snake This class is a simple placeholder to hold the end part of a path under construction in a `SequencesComparator`.

Field Summary

Modifier and Type	Field and Description
private final Equator<? super T>	equator The equator used for testing object equality.
private final List<T>	sequence1 First sequence.
private final List<T>	sequence2 Second sequence.
private final int[]	vDown Temporary variables.
private final int[]	vUp

Constructor Summary

Access	Constructor and Description
public	SequencesComparator(final List<T> first sequence to be compared sequence1, final List<T> second sequence to be compared sequence2) Simple constructor.
public	SequencesComparator(final List<T> first sequence to be compared sequence1, final List<T> second sequence to be compared sequence2, final Equator<? super T> the equator to use for testing object equality equator) Simple constructor.

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<T> the edited script script) Build an edit script.
private SequencesComparator.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) Build a snake.
private SequencesComparator.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) Get the middle snake corresponding to two subsequences of the main sequences.
public EditScript<T>	Returns: the edit script resulting from the comparison of the two sequences getScript() Get the `EditScript` object.

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

Field Detail

equator	back to summary
private final Equator<? super T> equator The equator used for testing object equality.

sequence1	back to summary
private final List<T> sequence1 First sequence.

sequence2	back to summary
private final List<T> sequence2 Second sequence.

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

vUp	back to summary
private final int[] vUp

Constructor Detail

SequencesComparator back to summary

SequencesComparator	back to summary
public SequencesComparator(final List<T> sequence1, final List<T> sequence2) Simple constructor. Creates a new instance of SequencesComparator using a `DefaultEquator`. 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 sequence1:List<T> first sequence to be compared sequence2:List<T> second sequence to be compared

public SequencesComparator(final List<T> sequence1, final List<T> sequence2)

Simple constructor.

Creates a new instance of SequencesComparator using a DefaultEquator.

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

sequence1:List<T>: first sequence to be compared
sequence2:List<T>: second sequence to be compared

SequencesComparator back to summary

SequencesComparator	back to summary
public SequencesComparator(final List<T> sequence1, final List<T> sequence2, final Equator<? super T> equator) Simple constructor. Creates a new instance of SequencesComparator with a custom `Equator`. It is guaranteed that the comparisons will always be done as `Equator.equate(o1, o2)` where `o1` belongs to the first sequence and `o2` belongs to the second sequence. Parameters sequence1:List<T> first sequence to be compared sequence2:List<T> second sequence to be compared equator:Equator<? super T> the equator to use for testing object equality

public SequencesComparator(final List<T> sequence1, final List<T> sequence2, final Equator<? super T> equator)

Simple constructor.

Creates a new instance of SequencesComparator with a custom Equator.

It is guaranteed that the comparisons will always be done as Equator.equate(o1, o2) where o1 belongs to the first sequence and o2 belongs to the second sequence.

Parameters

sequence1:List<T>: first sequence to be compared
sequence2:List<T>: second sequence to be compared
equator:Equator<? super T>: the equator to use for testing object equality

Method Detail

buildScript	back to summary
private void buildScript(final int start1, final int end1, final int start2, final int end2, final EditScript<T> script) Build 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<T> the edited script

buildScript

back to summary

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

Build 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<T>: the edited script

buildSnake	back to summary
private SequencesComparator.Snake buildSnake(final int start, final int diag, final int end1, final int end2) Build 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:SequencesComparator.Snake the snake built

buildSnake

back to summary

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

Build 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:SequencesComparator.Snake

the snake built

getMiddleSnake	back to summary
private SequencesComparator.Snake getMiddleSnake(final int start1, final int end1, final int start2, final int end2) Get 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:SequencesComparator.Snake the middle snake

getMiddleSnake

back to summary

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

Get 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:SequencesComparator.Snake

the middle snake

getScript back to summary

getScript	back to summary
public EditScript<T> getScript() Get 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<T> the edit script resulting from the comparison of the two sequences

public EditScript<T> getScript()

Get 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<T>: the edit script resulting from the comparison of the two sequences

org.apache.commons.collections4.sequence back to summary

private Class SequencesComparator.Snake

Class Inheritance

extends Object

java.lang.Object
org.apache.commons.collections4.sequence.SequencesComparator.Snake

This class is a simple placeholder to hold the end part of a path under construction in a SequencesComparator.

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
public	Snake(final int start index of the snake start, final int end index of the snake end, final int diagonal number diag) Simple constructor.

Method Summary

Modifier and Type	Method and Description
public int	Returns: diagonal number of the snake getDiag() Get the diagonal number of the snake.
public int	Returns: end index of the snake getEnd() Get the end index of the snake.
public int	Returns: start index of the snake getStart() Get 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
public Snake(final int start, final int end, final int diag) Simple constructor. Creates 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

public Snake(final int start, final int end, final int diag)

Simple constructor. Creates 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() Get the diagonal number of the snake. Returns:int diagonal number of the snake

getDiag

back to summary

public int getDiag()

Get the diagonal number of the snake.

Returns:int: diagonal number of the snake

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

getEnd

back to summary

public int getEnd()

Get the end index of the snake.

Returns:int: end index of the snake

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

getStart

back to summary

public int getStart()

Get the start index of the snake.

Returns:int: start index of the snake

public Class SequencesComparator<T>

Nested and Inner Type Summary

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

private Class SequencesComparator.Snake

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail