Package org.apache.commons.collections4.sequence

Class SequencesComparator<T>

java.lang.Object

org.apache.commons.collections4.sequence.SequencesComparator<T>

public class SequencesComparator<T>
extends java.lang.Object

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.

Since:

4.0

See Also:

EditScript, EditCommand, CommandVisitor

Nested Class Summary

Nested Classes

Modifier and Type	Class	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

Fields

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

Constructor Summary

Constructors

Constructor	Description
SequencesComparator(java.util.List<T> sequence1, java.util.List<T> sequence2)	Simple constructor.
SequencesComparator(java.util.List<T> sequence1, java.util.List<T> sequence2, Equator<? super T> equator)	Simple constructor.

Method Summary

Modifier and Type	Method	Description
private void	buildScript(int start1, int end1, int start2, int end2, EditScript<T> script)	Build an edit script.
private SequencesComparator.Snake	buildSnake(int start, int diag, int end1, int end2)	Build a snake.
private SequencesComparator.Snake	getMiddleSnake(int start1, int end1, int start2, int end2)	Get the middle snake corresponding to two subsequences of the main sequences.
EditScript<T>	getScript()	Get the EditScript object.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

sequence1

private final java.util.List<T> sequence1

First sequence.

sequence2

private final java.util.List<T> sequence2

Second sequence.

equator

private final Equator<? super T> equator

The equator used for testing object equality.

vDown

private final int[] vDown

Temporary variables.

vUp

private final int[] vUp

Constructor Detail

SequencesComparator

public SequencesComparator(java.util.List<T> sequence1,
                           java.util.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 - first sequence to be compared

sequence2 - second sequence to be compared

SequencesComparator

public SequencesComparator(java.util.List<T> sequence1,
                           java.util.List<T> sequence2,
                           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 - first sequence to be compared

sequence2 - second sequence to be compared

equator - the equator to use for testing object equality

Method Detail

getScript

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:

the edit script resulting from the comparison of the two sequences

buildSnake

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

Build a snake.

Parameters:

start - the value of the start of the snake

diag - the value of the diagonal of the snake

end1 - the value of the end of the first sequence to be compared

end2 - the value of the end of the second sequence to be compared

Returns:

the snake built

getMiddleSnake

private SequencesComparator.Snake getMiddleSnake(int start1,
                                                 int end1,
                                                 int start2,
                                                 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 - the begin of the first sequence to be compared

end1 - the end of the first sequence to be compared

start2 - the begin of the second sequence to be compared

end2 - the end of the second sequence to be compared

Returns:

the middle snake

buildScript

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

Build an edit script.

Parameters:

start1 - the begin of the first sequence to be compared

end1 - the end of the first sequence to be compared

start2 - the begin of the second sequence to be compared

end2 - the end of the second sequence to be compared

script - the edited script