Skip to content

Commit d12b13d

Browse files
wumpzwumpz
committed
fixes #21 
1 parent c8f0624 commit d12b13d

9 files changed

Lines changed: 195 additions & 24 deletions

File tree

‎README.md‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -3,8 +3,6 @@
33
## Status ##
44
[![Build Status](https://travis-ci.org/wumpz/java-diff-utils.svg?branch=master)](https://travis-ci.org/wumpz/java-diff-utils) [![Codacy Badge](https://api.codacy.com/project/badge/Grade/7eba77f10bed4c2a8d08ac8dc8da4a86)](https://www.codacy.com/app/wumpz/java-diff-utils?utm_source=github.com&utm_medium=referral&utm_content=wumpz/java-diff-utils&utm_campaign=Badge_Grade)
55

6-
**After a while using it, at least for me, this one seems to be feature complete. If someone finds bugs or has improvement ideas, please file an issue. I wonder why that this project is a zero issue project.**
7-
86

97
## Intro ##
108
Diff Utils library is an OpenSource library for performing the comparison operations between texts: computing diffs, applying patches, generating unified diffs or parsing them, generating diff output for easy future displaying (like side-by-side view) and so on.
@@ -54,6 +52,8 @@ But it can easily replaced by any other which is better for handing your texts.
5452

5553
### Changelog ###
5654
* Version 2.3-SNAPSHOT
55+
* Introduced a process listener to diff algorithms. For long running
56+
diffs one could implement some progress information.
5757
* Version 2.2
5858
* released at maven central
5959
* included checkstyle source code conventions

‎src/main/java/com/github/difflib/DiffUtils.java‎

Lines changed: 26 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -20,6 +20,7 @@
2020
package com.github.difflib;
2121

2222
import com.github.difflib.algorithm.DiffAlgorithm;
23+
import com.github.difflib.algorithm.DiffAlgorithmListener;
2324
import com.github.difflib.algorithm.DiffException;
2425
import com.github.difflib.algorithm.myers.MyersDiff;
2526
import com.github.difflib.patch.Delta;
@@ -37,7 +38,6 @@
3738
* Implements the difference and patching engine
3839
*
3940
* @author <a href="dm.naumenko@gmail.com">Dmitry Naumenko</a>
40-
* @version 0.4.1
4141
*/
4242
public final class DiffUtils {
4343

@@ -46,17 +46,23 @@ public final class DiffUtils {
4646
*
4747
* @param original The original text. Must not be {@code null}.
4848
* @param revised The revised text. Must not be {@code null}.
49+
* @param progress progress listener
4950
* @return The patch describing the difference between the original and revised sequences. Never {@code null}.
51+
* @throws com.github.difflib.algorithm.DiffException
5052
*/
53+
public static <T> Patch<T> diff(List<T> original, List<T> revised, DiffAlgorithmListener progress) throws DiffException {
54+
return DiffUtils.diff(original, revised, new MyersDiff<>(), progress);
55+
}
56+
5157
public static <T> Patch<T> diff(List<T> original, List<T> revised) throws DiffException {
52-
return DiffUtils.diff(original, revised, new MyersDiff<>());
58+
return DiffUtils.diff(original, revised, new MyersDiff<>(), null);
5359
}
5460

5561
/**
5662
* Computes the difference between the original and revised text.
5763
*/
58-
public static Patch<String> diff(String originalText, String revisedText) throws DiffException {
59-
return DiffUtils.diff(Arrays.asList(originalText.split("\n")), Arrays.asList(revisedText.split("\n")));
64+
public static Patch<String> diff(String originalText, String revisedText, DiffAlgorithmListener progress) throws DiffException {
65+
return DiffUtils.diff(Arrays.asList(originalText.split("\n")), Arrays.asList(revisedText.split("\n")), progress);
6066
}
6167

6268
/**
@@ -84,16 +90,30 @@ public static <T> Patch<T> diff(List<T> original, List<T> revised,
8490
* @param original The original text. Must not be {@code null}.
8591
* @param revised The revised text. Must not be {@code null}.
8692
* @param algorithm The diff algorithm. Must not be {@code null}.
93+
* @param progress The diff algorithm listener.
8794
* @return The patch describing the difference between the original and revised sequences. Never {@code null}.
8895
*/
8996
public static <T> Patch<T> diff(List<T> original, List<T> revised,
90-
DiffAlgorithm<T> algorithm) throws DiffException {
97+
DiffAlgorithm<T> algorithm, DiffAlgorithmListener progress) throws DiffException {
9198
Objects.requireNonNull(original, "original must not be null");
9299
Objects.requireNonNull(revised, "revised must not be null");
93100
Objects.requireNonNull(algorithm, "algorithm must not be null");
94101

95-
return Patch.generate(original, revised, algorithm.diff(original, revised));
102+
return Patch.generate(original, revised, algorithm.diff(original, revised, progress));
96103
}
104+
105+
/**
106+
* Computes the difference between the original and revised list of elements with default diff algorithm
107+
*
108+
* @param original The original text. Must not be {@code null}.
109+
* @param revised The revised text. Must not be {@code null}.
110+
* @param algorithm The diff algorithm. Must not be {@code null}.
111+
* @return The patch describing the difference between the original and revised sequences. Never {@code null}.
112+
*/
113+
public static <T> Patch<T> diff(List<T> original, List<T> revised,
114+
DiffAlgorithm<T> algorithm) throws DiffException {
115+
return diff(original, revised, algorithm, null);
116+
}
97117

98118
/**
99119
* Computes the difference between the given texts inline. This one uses the "trick" to make out of texts lists of

‎src/main/java/com/github/difflib/algorithm/DiffAlgorithm.java‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -38,8 +38,8 @@ public interface DiffAlgorithm<T> {
3838
* @param revised The revised sequence. Must not be {@code null}.
3939
* @return The patch representing the diff of the given sequences. Never {@code null}.
4040
*/
41-
public default List<Change> diff(T[] original, T[] revised) throws DiffException {
42-
return diff(Arrays.asList(original), Arrays.asList(revised));
41+
default List<Change> diff(T[] original, T[] revised, DiffAlgorithmListener progress) throws DiffException {
42+
return diff(Arrays.asList(original), Arrays.asList(revised), progress);
4343
}
4444

4545
/**
@@ -50,5 +50,5 @@ public default List<Change> diff(T[] original, T[] revised) throws DiffException
5050
* @param revised The revised sequence. Must not be {@code null}.
5151
* @return The patch representing the diff of the given sequences. Never {@code null}.
5252
*/
53-
public List<Change> diff(List<T> original, List<T> revised) throws DiffException;
53+
List<Change> diff(List<T> original, List<T> revised, DiffAlgorithmListener progress) throws DiffException;
5454
}

‎src/main/java/com/github/difflib/algorithm/DiffAlgorithmListener.java‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
/*
2+
* Copyright 2018 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+
/**
19+
*
20+
* @author Tobias Warneke (t.warneke@gmx.net)
21+
*/
22+
public interface DiffAlgorithmListener {
23+
void diffStart();
24+
25+
/**
26+
* This is a step within the diff algorithm. Due to different implementations the value
27+
* is not strict incrementing to the max and is not garantee to reach the max. It could
28+
* stop before.
29+
* @param value
30+
* @param max
31+
*/
32+
void diffStep(int value, int max);
33+
void diffEnd();
34+
}

‎src/main/java/com/github/difflib/algorithm/jgit/HistogramDiff.java‎

Lines changed: 20 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -17,6 +17,7 @@
1717

1818
import com.github.difflib.algorithm.Change;
1919
import com.github.difflib.algorithm.DiffAlgorithm;
20+
import com.github.difflib.algorithm.DiffAlgorithmListener;
2021
import com.github.difflib.algorithm.DiffException;
2122
import com.github.difflib.patch.DeltaType;
2223
import java.util.ArrayList;
@@ -28,18 +29,22 @@
2829
import org.eclipse.jgit.diff.SequenceComparator;
2930

3031
/**
31-
* HistorgramDiff using JGit - Library. This one is much more performant than the orginal Myers implementation.
32+
* HistorgramDiff using JGit - Library. This one is much more performant than the orginal Myers
33+
* implementation.
3234
*
3335
* @author toben
3436
*/
3537
public class HistogramDiff<T> implements DiffAlgorithm<T> {
3638

3739
@Override
38-
public List<Change> diff(List<T> original, List<T> revised) throws DiffException {
40+
public List<Change> diff(List<T> original, List<T> revised, DiffAlgorithmListener progress) throws DiffException {
3941
Objects.requireNonNull(original, "original list must not be null");
4042
Objects.requireNonNull(revised, "revised list must not be null");
43+
if (progress != null) {
44+
progress.diffStart();
45+
}
4146
EditList diffList = new EditList();
42-
diffList.addAll(new org.eclipse.jgit.diff.HistogramDiff().diff(new DataListComparator<>(), new DataList<>(original), new DataList<>(revised)));
47+
diffList.addAll(new org.eclipse.jgit.diff.HistogramDiff().diff(new DataListComparator<>(progress), new DataList<>(original), new DataList<>(revised)));
4348
List<Change> patch = new ArrayList<>();
4449
for (Edit edit : diffList) {
4550
DeltaType type = DeltaType.EQUAL;
@@ -56,14 +61,26 @@ public List<Change> diff(List<T> original, List<T> revised) throws DiffException
5661
}
5762
patch.add(new Change(type, edit.getBeginA(), edit.getEndA(), edit.getBeginB(), edit.getEndB()));
5863
}
64+
if (progress != null) {
65+
progress.diffEnd();
66+
}
5967
return patch;
6068
}
6169
}
6270

6371
class DataListComparator<T> extends SequenceComparator<DataList<T>> {
6472

73+
private final DiffAlgorithmListener progress;
74+
75+
public DataListComparator(DiffAlgorithmListener progress) {
76+
this.progress = progress;
77+
}
78+
6579
@Override
6680
public boolean equals(DataList<T> original, int orgIdx, DataList<T> revised, int revIdx) {
81+
if (progress != null) {
82+
progress.diffStep(orgIdx + revIdx, original.size() + revised.size());
83+
}
6784
return original.data.get(orgIdx).equals(revised.data.get(revIdx));
6885
}
6986

‎src/main/java/com/github/difflib/algorithm/myers/MyersDiff.java‎

Lines changed: 19 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -21,6 +21,7 @@
2121

2222
import com.github.difflib.algorithm.Change;
2323
import com.github.difflib.algorithm.DiffAlgorithm;
24+
import com.github.difflib.algorithm.DiffAlgorithmListener;
2425
import com.github.difflib.algorithm.DiffException;
2526
import com.github.difflib.algorithm.DifferentiationFailedException;
2627
import com.github.difflib.patch.DeltaType;
@@ -53,24 +54,31 @@ public MyersDiff(final BiPredicate<T, T> equalizer) {
5354
* Return empty diff if get the error while procession the difference.
5455
*/
5556
@Override
56-
public List<Change> diff(final List<T> original, final List<T> revised) throws DiffException {
57+
public List<Change> diff(final List<T> original, final List<T> revised, DiffAlgorithmListener progress) throws DiffException {
5758
Objects.requireNonNull(original, "original list must not be null");
5859
Objects.requireNonNull(revised, "revised list must not be null");
5960

60-
PathNode path = buildPath(original, revised);
61-
return buildRevision(path, original, revised);
61+
if (progress != null) {
62+
progress.diffStart();
63+
}
64+
PathNode path = buildPath(original, revised, progress);
65+
List<Change> result = buildRevision(path, original, revised);
66+
if (progress != null) {
67+
progress.diffEnd();
68+
}
69+
return result;
6270
}
6371

6472
/**
65-
* Computes the minimum diffpath that expresses de differences between the original and revised sequences, according
66-
* to Gene Myers differencing algorithm.
73+
* Computes the minimum diffpath that expresses de differences between the original and revised
74+
* sequences, according to Gene Myers differencing algorithm.
6775
*
6876
* @param orig The original sequence.
6977
* @param rev The revised sequence.
7078
* @return A minimum {@link PathNode Path} accross the differences graph.
7179
* @throws DifferentiationFailedException if a diff path could not be found.
7280
*/
73-
private PathNode buildPath(final List<T> orig, final List<T> rev)
81+
private PathNode buildPath(final List<T> orig, final List<T> rev, DiffAlgorithmListener progress)
7482
throws DifferentiationFailedException {
7583
Objects.requireNonNull(orig, "original sequence is null");
7684
Objects.requireNonNull(rev, "revised sequence is null");
@@ -86,6 +94,9 @@ private PathNode buildPath(final List<T> orig, final List<T> rev)
8694

8795
diagonal[middle + 1] = new PathNode(0, -1, true, true, null);
8896
for (int d = 0; d < MAX; d++) {
97+
if (progress != null) {
98+
progress.diffStep(d, MAX);
99+
}
89100
for (int k = -d; k <= d; k += 2) {
90101
final int kmiddle = middle + k;
91102
final int kplus = kmiddle + 1;
@@ -135,7 +146,8 @@ private PathNode buildPath(final List<T> orig, final List<T> rev)
135146
* @param orig The original sequence.
136147
* @param rev The revised sequence.
137148
* @return A {@link Patch} script corresponding to the path.
138-
* @throws DifferentiationFailedException if a {@link Patch} could not be built from the given path.
149+
* @throws DifferentiationFailedException if a {@link Patch} could not be built from the given
150+
* path.
139151
*/
140152
private List<Change> buildRevision(PathNode actualPath, List<T> orig, List<T> rev) {
141153
Objects.requireNonNull(actualPath, "path is null");

‎src/test/java/com/github/difflib/algorithm/jgit/HistogramDiffTest.java‎

Lines changed: 37 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -15,9 +15,11 @@
1515
*/
1616
package com.github.difflib.algorithm.jgit;
1717

18+
import com.github.difflib.algorithm.DiffAlgorithmListener;
1819
import com.github.difflib.algorithm.DiffException;
1920
import com.github.difflib.patch.Patch;
2021
import com.github.difflib.patch.PatchFailedException;
22+
import java.util.ArrayList;
2123
import java.util.Arrays;
2224
import java.util.List;
2325
import org.junit.After;
@@ -59,7 +61,7 @@ public void tearDown() {
5961
public void testDiff() throws DiffException, PatchFailedException {
6062
List<String> orgList = Arrays.asList("A", "B", "C", "A", "B", "B", "A");
6163
List<String> revList = Arrays.asList("C", "B", "A", "B", "A", "C");
62-
final Patch<String> patch = Patch.generate(orgList, revList, new HistogramDiff().diff(orgList, revList));
64+
final Patch<String> patch = Patch.generate(orgList, revList, new HistogramDiff().diff(orgList, revList, null));
6365
System.out.println(patch);
6466
assertNotNull(patch);
6567
assertEquals(3, patch.getDeltas().size());
@@ -68,4 +70,38 @@ public void testDiff() throws DiffException, PatchFailedException {
6870
List<String> patched = patch.applyTo(orgList);
6971
assertEquals(revList, patched);
7072
}
73+
74+
@Test
75+
public void testDiffWithListener() throws DiffException, PatchFailedException {
76+
List<String> orgList = Arrays.asList("A", "B", "C", "A", "B", "B", "A");
77+
List<String> revList = Arrays.asList("C", "B", "A", "B", "A", "C");
78+
79+
List<String> logdata = new ArrayList<>();
80+
final Patch<String> patch = Patch.generate(orgList, revList, new HistogramDiff().diff(orgList, revList, new DiffAlgorithmListener() {
81+
@Override
82+
public void diffStart() {
83+
logdata.add("start");
84+
}
85+
86+
@Override
87+
public void diffStep(int value, int max) {
88+
logdata.add(value + " - " + max);
89+
}
90+
91+
@Override
92+
public void diffEnd() {
93+
logdata.add("end");
94+
}
95+
}));
96+
System.out.println(patch);
97+
assertNotNull(patch);
98+
assertEquals(3, patch.getDeltas().size());
99+
assertEquals("Patch{deltas=[[DeleteDelta, position: 0, lines: [A, B]], [DeleteDelta, position: 3, lines: [A, B]], [InsertDelta, position: 7, lines: [B, A, C]]]}", patch.toString());
100+
101+
List<String> patched = patch.applyTo(orgList);
102+
assertEquals(revList, patched);
103+
104+
System.out.println(logdata);
105+
assertEquals(17, logdata.size());
106+
}
71107
}

‎src/test/java/com/github/difflib/algorithm/jgit/LRHistogramDiffTest.java‎

Lines changed: 21 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -17,10 +17,12 @@
1717

1818
import static com.github.difflib.DiffUtilsTest.readStringListFromInputStream;
1919
import com.github.difflib.TestConstants;
20+
import com.github.difflib.algorithm.DiffAlgorithmListener;
2021
import com.github.difflib.algorithm.DiffException;
2122
import com.github.difflib.patch.Patch;
2223
import com.github.difflib.patch.PatchFailedException;
2324
import java.io.IOException;
25+
import java.util.ArrayList;
2426
import java.util.List;
2527
import java.util.zip.ZipFile;
2628
import org.junit.After;
@@ -61,12 +63,30 @@ public void testPossibleDiffHangOnLargeDatasetDnaumenkoIssue26() throws IOExcept
6163
List<String> original = readStringListFromInputStream(zip.getInputStream(zip.getEntry("ta")));
6264
List<String> revised = readStringListFromInputStream(zip.getInputStream(zip.getEntry("tb")));
6365

64-
Patch<String> patch = Patch.generate(original, revised, new HistogramDiff().diff(original, revised));
66+
List<String> logdata = new ArrayList<>();
67+
Patch<String> patch = Patch.generate(original, revised, new HistogramDiff().diff(original, revised, new DiffAlgorithmListener() {
68+
@Override
69+
public void diffStart() {
70+
logdata.add("start");
71+
}
72+
73+
@Override
74+
public void diffStep(int value, int max) {
75+
logdata.add(value + " - " + max);
76+
}
77+
78+
@Override
79+
public void diffEnd() {
80+
logdata.add("end");
81+
}
82+
}));
6583

6684
assertEquals(34, patch.getDeltas().size());
6785

6886
List<String> created = patch.applyTo(original);
6987
assertArrayEquals(revised.toArray(), created.toArray());
88+
89+
assertEquals(50, logdata.size());
7090
}
7191

7292
}

0 commit comments

Comments
 (0)