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 aso1.equals(o2)
whereo1
belongs to the first sequence ando2
belongs to the second sequence. This can be important if subclassing is used for some elements in the first sequence and theequals
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 thecommands
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 aSequencesComparator
.
-
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
All Methods Instance Methods Concrete Methods 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 theEditScript
object.
-
-
-
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)
whereo1
belongs to the first sequence ando2
belongs to the second sequence. This can be important if subclassing is used for some elements in the first sequence and theequals
method is specialized.- Parameters:
sequence1
- first sequence to be comparedsequence2
- 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)
whereo1
belongs to the first sequence ando2
belongs to the second sequence.- Parameters:
sequence1
- first sequence to be comparedsequence2
- second sequence to be comparedequator
- the equator to use for testing object equality
-
-
Method Detail
-
getScript
public EditScript<T> getScript()
Get theEditScript
object.It is guaranteed that the objects embedded in the
insert commands
come from the second sequence and that the objects embedded in either thedelete commands
orkeep commands
come from the first sequence. This can be important if subclassing is used for some elements in the first sequence and theequals
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 snakediag
- the value of the diagonal of the snakeend1
- the value of the end of the first sequence to be comparedend2
- 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 comparedend1
- the end of the first sequence to be comparedstart2
- the begin of the second sequence to be comparedend2
- 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 comparedend1
- the end of the first sequence to be comparedstart2
- the begin of the second sequence to be comparedend2
- the end of the second sequence to be comparedscript
- the edited script
-
-