Skip to content

Commit 2b02951

Browse files
wumpzwumpz
committed
Merge introduce-optimized-meyers-algorithm
2 parents 89ce301 + 894b8ba commit 2b02951

16 files changed

+876
-73
lines changed

‎java-diff-utils/src/main/java/com/github/difflib/DiffUtils.java

Lines changed: 41 additions & 30 deletions
Original file line numberDiff line numberDiff line change
@@ -15,9 +15,10 @@
1515
*/
1616
package com.github.difflib;
1717

18+
import com.github.difflib.algorithm.DiffAlgorithmFactory;
1819
import com.github.difflib.algorithm.DiffAlgorithmI;
1920
import com.github.difflib.algorithm.DiffAlgorithmListener;
20-
import com.github.difflib.algorithm.myers.MyersDiff;
21+
import com.github.difflib.algorithm.myers.MeyersDiff;
2122
import com.github.difflib.patch.AbstractDelta;
2223
import com.github.difflib.patch.Patch;
2324
import com.github.difflib.patch.PatchFailedException;
@@ -34,26 +35,35 @@
3435
public final class DiffUtils {
3536

3637
/**
37-
* Computes the difference between the original and revised list of elements with default diff
38-
* algorithm
38+
* This factory generates the DEFAULT_DIFF algorithm for all these routines.
39+
*/
40+
static DiffAlgorithmFactory DEFAULT_DIFF = MeyersDiff.factory();
41+
42+
public static void withDefaultDiffAlgorithmFactory(DiffAlgorithmFactory factory) {
43+
DEFAULT_DIFF = factory;
44+
}
45+
46+
/**
47+
* Computes the difference between the original and revised list of elements
48+
* with default diff algorithm
3949
*
4050
* @param <T> types to be diffed
4151
* @param original The original text. Must not be {@code null}.
4252
* @param revised The revised text. Must not be {@code null}.
4353
* @param progress progress listener
44-
* @return The patch describing the difference between the original and revised sequences. Never
45-
* {@code null}.
54+
* @return The patch describing the difference between the original and
55+
* revised sequences. Never {@code null}.
4656
*/
4757
public static <T> Patch<T> diff(List<T> original, List<T> revised, DiffAlgorithmListener progress) {
48-
return DiffUtils.diff(original, revised, new MyersDiff<>(), progress);
58+
return DiffUtils.diff(original, revised, DEFAULT_DIFF.create(), progress);
4959
}
5060

5161
public static <T> Patch<T> diff(List<T> original, List<T> revised) {
52-
return DiffUtils.diff(original, revised, new MyersDiff<>(), null);
62+
return DiffUtils.diff(original, revised, DEFAULT_DIFF.create(), null);
5363
}
54-
64+
5565
public static <T> Patch<T> diff(List<T> original, List<T> revised, boolean includeEqualParts) {
56-
return DiffUtils.diff(original, revised, new MyersDiff<>(), null, includeEqualParts);
66+
return DiffUtils.diff(original, revised, DEFAULT_DIFF.create(), null, includeEqualParts);
5767
}
5868

5969
/**
@@ -67,45 +77,46 @@ public static Patch<String> diff(String sourceText, String targetText,
6777
}
6878

6979
/**
70-
* Computes the difference between the original and revised list of elements with default diff
71-
* algorithm
80+
* Computes the difference between the original and revised list of elements
81+
* with default diff algorithm
7282
*
7383
* @param source The original text. Must not be {@code null}.
7484
* @param target The revised text. Must not be {@code null}.
7585
*
76-
* @param equalizer the equalizer object to replace the default compare algorithm
77-
* (Object.equals). If {@code null} the default equalizer of the default algorithm is used..
78-
* @return The patch describing the difference between the original and revised sequences. Never
79-
* {@code null}.
86+
* @param equalizer the equalizer object to replace the default compare
87+
* algorithm (Object.equals). If {@code null} the default equalizer of the
88+
* default algorithm is used..
89+
* @return The patch describing the difference between the original and
90+
* revised sequences. Never {@code null}.
8091
*/
8192
public static <T> Patch<T> diff(List<T> source, List<T> target,
8293
BiPredicate<T, T> equalizer) {
8394
if (equalizer != null) {
8495
return DiffUtils.diff(source, target,
85-
new MyersDiff<>(equalizer));
96+
DEFAULT_DIFF.create(equalizer));
8697
}
87-
return DiffUtils.diff(source, target, new MyersDiff<>());
98+
return DiffUtils.diff(source, target, new MeyersDiff<>());
8899
}
89100

90101
public static <T> Patch<T> diff(List<T> original, List<T> revised,
91102
DiffAlgorithmI<T> algorithm, DiffAlgorithmListener progress) {
92103
return diff(original, revised, algorithm, progress, false);
93104
}
94-
105+
95106
/**
96-
* Computes the difference between the original and revised list of elements with default diff
97-
* algorithm
107+
* Computes the difference between the original and revised list of elements
108+
* with default diff algorithm
98109
*
99110
* @param original The original text. Must not be {@code null}.
100111
* @param revised The revised text. Must not be {@code null}.
101112
* @param algorithm The diff algorithm. Must not be {@code null}.
102113
* @param progress The diff algorithm listener.
103114
* @param includeEqualParts Include equal data parts into the patch.
104-
* @return The patch describing the difference between the original and revised sequences. Never
105-
* {@code null}.
115+
* @return The patch describing the difference between the original and
116+
* revised sequences. Never {@code null}.
106117
*/
107118
public static <T> Patch<T> diff(List<T> original, List<T> revised,
108-
DiffAlgorithmI<T> algorithm, DiffAlgorithmListener progress,
119+
DiffAlgorithmI<T> algorithm, DiffAlgorithmListener progress,
109120
boolean includeEqualParts) {
110121
Objects.requireNonNull(original, "original must not be null");
111122
Objects.requireNonNull(revised, "revised must not be null");
@@ -115,23 +126,23 @@ public static <T> Patch<T> diff(List<T> original, List<T> revised,
115126
}
116127

117128
/**
118-
* Computes the difference between the original and revised list of elements with default diff
119-
* algorithm
129+
* Computes the difference between the original and revised list of elements
130+
* with default diff algorithm
120131
*
121132
* @param original The original text. Must not be {@code null}.
122133
* @param revised The revised text. Must not be {@code null}.
123134
* @param algorithm The diff algorithm. Must not be {@code null}.
124-
* @return The patch describing the difference between the original and revised sequences. Never
125-
* {@code null}.
135+
* @return The patch describing the difference between the original and
136+
* revised sequences. Never {@code null}.
126137
*/
127138
public static <T> Patch<T> diff(List<T> original, List<T> revised, DiffAlgorithmI<T> algorithm) {
128139
return diff(original, revised, algorithm, null);
129140
}
130141

131142
/**
132-
* Computes the difference between the given texts inline. This one uses the "trick" to make out
133-
* of texts lists of characters, like DiffRowGenerator does and merges those changes at the end
134-
* together again.
143+
* Computes the difference between the given texts inline. This one uses the
144+
* "trick" to make out of texts lists of characters, like DiffRowGenerator
145+
* does and merges those changes at the end together again.
135146
*
136147
* @param original
137148
* @param revised

‎java-diff-utils/src/main/java/com/github/difflib/algorithm/Change.java

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -36,4 +36,12 @@ public Change(DeltaType deltaType, int startOriginal, int endOriginal, int start
3636
this.startRevised = startRevised;
3737
this.endRevised = endRevised;
3838
}
39+
40+
public Change withEndOriginal(int endOriginal) {
41+
return new Change(deltaType, startOriginal, endOriginal, startRevised, endRevised);
42+
}
43+
44+
public Change withEndRevised(int endRevised) {
45+
return new Change(deltaType, startOriginal, endOriginal, startRevised, endRevised);
46+
}
3947
}

‎java-diff-utils/src/main/java/com/github/difflib/algorithm/DiffAlgorithmFactory.java

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
/*
2+
* Copyright 2021 java-diff-utils.
3+
*
4+
* Licensed under the Apache License, Version 2.0 (the "License");
5+
* you may not use this file except in compliance with the License.
6+
* You may obtain a copy of the License at
7+
*
8+
* http://www.apache.org/licenses/LICENSE-2.0
9+
*
10+
* Unless required by applicable law or agreed to in writing, software
11+
* distributed under the License is distributed on an "AS IS" BASIS,
12+
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13+
* See the License for the specific language governing permissions and
14+
* limitations under the License.
15+
*/
16+
package com.github.difflib.algorithm;
17+
18+
import java.util.function.BiPredicate;
19+
20+
/**
21+
* Tool to create new instances of a diff algorithm. This one is only needed at the moment to
22+
* set DiffUtils default diff algorithm.
23+
* @author tw
24+
*/
25+
public interface DiffAlgorithmFactory {
26+
<T> DiffAlgorithmI<T> create();
27+
28+
<T> DiffAlgorithmI<T> create(BiPredicate<T, T> equalizer);
29+
}

‎java-diff-utils/src/main/java/com/github/difflib/algorithm/myers/MyersDiff.java renamed to ‎java-diff-utils/src/main/java/com/github/difflib/algorithm/myers/MeyersDiff.java

Lines changed: 30 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,7 @@
1616
package com.github.difflib.algorithm.myers;
1717

1818
import com.github.difflib.algorithm.Change;
19+
import com.github.difflib.algorithm.DiffAlgorithmFactory;
1920
import com.github.difflib.algorithm.DiffAlgorithmI;
2021
import com.github.difflib.algorithm.DiffAlgorithmListener;
2122
import com.github.difflib.patch.DeltaType;
@@ -26,18 +27,17 @@
2627
import java.util.function.BiPredicate;
2728

2829
/**
29-
* A clean-room implementation of Eugene Myers greedy differencing algorithm.
30+
* A clean-room implementation of Eugene Meyers greedy differencing algorithm.
3031
*/
31-
public final class MyersDiff<T> implements DiffAlgorithmI<T> {
32+
public final class MeyersDiff<T> implements DiffAlgorithmI<T> {
3233

33-
private final BiPredicate<T, T> DEFAULT_EQUALIZER = Object::equals;
3434
private final BiPredicate<T, T> equalizer;
3535

36-
public MyersDiff() {
37-
equalizer = DEFAULT_EQUALIZER;
36+
public MeyersDiff() {
37+
equalizer = Object::equals;
3838
}
3939

40-
public MyersDiff(final BiPredicate<T, T> equalizer) {
40+
public MeyersDiff(final BiPredicate<T, T> equalizer) {
4141
Objects.requireNonNull(equalizer, "equalizer must not be null");
4242
this.equalizer = equalizer;
4343
}
@@ -64,8 +64,9 @@ public List<Change> computeDiff(final List<T> source, final List<T> target, Diff
6464
}
6565

6666
/**
67-
* Computes the minimum diffpath that expresses de differences between the original and revised
68-
* sequences, according to Gene Myers differencing algorithm.
67+
* Computes the minimum diffpath that expresses de differences between the
68+
* original and revised sequences, according to Gene Myers differencing
69+
* algorithm.
6970
*
7071
* @param orig The original sequence.
7172
* @param rev The revised sequence.
@@ -139,8 +140,8 @@ private PathNode buildPath(final List<T> orig, final List<T> rev, DiffAlgorithmL
139140
* @param orig The original sequence.
140141
* @param rev The revised sequence.
141142
* @return A {@link Patch} script corresponding to the path.
142-
* @throws DifferentiationFailedException if a {@link Patch} could not be built from the given
143-
* path.
143+
* @throws DifferentiationFailedException if a {@link Patch} could not be
144+
* built from the given path.
144145
*/
145146
private List<Change> buildRevision(PathNode actualPath, List<T> orig, List<T> rev) {
146147
Objects.requireNonNull(actualPath, "path is null");
@@ -177,4 +178,23 @@ private List<Change> buildRevision(PathNode actualPath, List<T> orig, List<T> re
177178
}
178179
return changes;
179180
}
181+
182+
/**
183+
* Factory to create instances of this specific diff algorithm.
184+
*/
185+
public static DiffAlgorithmFactory factory() {
186+
return new DiffAlgorithmFactory() {
187+
@Override
188+
public <T> DiffAlgorithmI<T>
189+
create() {
190+
return new MeyersDiff<T>();
191+
}
192+
193+
@Override
194+
public <T> DiffAlgorithmI<T>
195+
create(BiPredicate < T, T > equalizer) {
196+
return new MeyersDiff<T>(equalizer);
197+
}
198+
};
199+
}
180200
}

0 commit comments

Comments
 (0)