public abstract class DiffAlgorithm
extends java.lang.Object
Sequence
s to create an
EditList
of changes.
An algorithm's diff
method must be callable from concurrent threads
without data collisions. This permits some algorithms to use a singleton
pattern, with concurrent invocations using the same singleton. Other
algorithms may support parameterization, in which case the caller can create
a unique instance per thread.
Modifier and Type | Class and Description |
---|---|
static class |
DiffAlgorithm.SupportedAlgorithm
Supported diff algorithm
|
Constructor and Description |
---|
DiffAlgorithm() |
Modifier and Type | Method and Description |
---|---|
private static <S extends Sequence> |
coverEdit(S a,
S b) |
<S extends Sequence> |
diff(SequenceComparator<? super S> cmp,
S a,
S b)
Compare two sequences and identify a list of edits between them.
|
abstract <S extends Sequence> |
diffNonCommon(SequenceComparator<? super S> cmp,
S a,
S b)
Compare two sequences and identify a list of edits between them.
|
static DiffAlgorithm |
getAlgorithm(DiffAlgorithm.SupportedAlgorithm alg)
Get diff algorithm
|
private static <S extends Sequence> |
normalize(SequenceComparator<? super S> cmp,
EditList e,
S a,
S b)
Reorganize an
EditList for better diff consistency. |
public static DiffAlgorithm getAlgorithm(DiffAlgorithm.SupportedAlgorithm alg)
alg
- the diff algorithm for which an implementation should be
returnedpublic <S extends Sequence> EditList diff(SequenceComparator<? super S> cmp, S a, S b)
cmp
- the comparator supplying the element equivalence function.a
- the first (also known as old or pre-image) sequence. Edits
returned by this algorithm will reference indexes using the
'A' side: Edit.getBeginA()
,
Edit.getEndA()
.b
- the second (also known as new or post-image) sequence. Edits
returned by this algorithm will reference indexes using the
'B' side: Edit.getBeginB()
,
Edit.getEndB()
.cmp
's rules. The
result list is never null.private static <S extends Sequence> EditList normalize(SequenceComparator<? super S> cmp, EditList e, S a, S b)
EditList
for better diff consistency.
DiffAlgorithms
may return Edit.Type.INSERT
or
Edit.Type.DELETE
edits that can be "shifted". For
example, the deleted section
-a -b -c a b ccan be shifted down by 1, 2 or 3 locations.
To avoid later merge issues, we shift such edits to a
consistent location. normalize
uses a simple strategy of
shifting such edits to their latest possible location.
This strategy may not always produce an aesthetically pleasing diff. For instance, it works well with
function1 { ... } +function2 { + ... +} + function3 { ... }but less so for
# # comment1 # function1() { } # +# comment3 +# +function3() { +} + +# # comment2 # function2() { }More sophisticated strategies are possible, say by calculating a suitable "aesthetic cost" for each possible position and using the lowest cost, but
normalize
just shifts edits
to the end as much as possible.S
- type of sequence being compared.cmp
- the comparator supplying the element equivalence function.e
- a modifiable edit list comparing the provided sequences.a
- the first (also known as old or pre-image) sequence.b
- the second (also known as new or post-image) sequence.public abstract <S extends Sequence> EditList diffNonCommon(SequenceComparator<? super S> cmp, S a, S b)
diff(SequenceComparator, Sequence, Sequence)
method, which invokes this method using
Subsequence
s.cmp
- the comparator supplying the element equivalence function.a
- the first (also known as old or pre-image) sequence. Edits
returned by this algorithm will reference indexes using the
'A' side: Edit.getBeginA()
,
Edit.getEndA()
.b
- the second (also known as new or post-image) sequence. Edits
returned by this algorithm will reference indexes using the
'B' side: Edit.getBeginB()
,
Edit.getEndB()
.