public class SequencesComparator<T>
extends java.lang.Object
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.
EditScript
,
EditCommand
,
CommandVisitor
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 . |
Modifier and Type | Field and 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 and 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.
|
Modifier and Type | Method and 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. |
private final java.util.List<T> sequence1
private final java.util.List<T> sequence2
private final int[] vDown
private final int[] vUp
public SequencesComparator(java.util.List<T> sequence1, java.util.List<T> sequence2)
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.
sequence1
- first sequence to be comparedsequence2
- second sequence to be comparedpublic SequencesComparator(java.util.List<T> sequence1, java.util.List<T> sequence2, Equator<? super T> equator)
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.
sequence1
- first sequence to be comparedsequence2
- second sequence to be comparedequator
- the equator to use for testing object equalitypublic EditScript<T> getScript()
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.
private SequencesComparator.Snake buildSnake(int start, int diag, int end1, int end2)
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 comparedprivate SequencesComparator.Snake getMiddleSnake(int start1, int end1, int start2, int end2)
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.
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 comparedprivate void buildScript(int start1, int end1, int start2, int end2, EditScript<T> script)
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