Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitc765616

Browse files
committed
attached logging to new meyer diff algorithm
1 parent24c3df1 commitc765616

File tree

6 files changed

+133
-51
lines changed

6 files changed

+133
-51
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
packagecom.github.difflib;
1717

18+
importcom.github.difflib.algorithm.DiffAlgorithmFactory;
1819
importcom.github.difflib.algorithm.DiffAlgorithmI;
1920
importcom.github.difflib.algorithm.DiffAlgorithmListener;
20-
importcom.github.difflib.algorithm.myers.MyersDiff;
21+
importcom.github.difflib.algorithm.myers.MeyersDiff;
2122
importcom.github.difflib.patch.AbstractDelta;
2223
importcom.github.difflib.patch.Patch;
2324
importcom.github.difflib.patch.PatchFailedException;
@@ -34,26 +35,35 @@
3435
publicfinalclassDiffUtils {
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+
staticDiffAlgorithmFactoryDEFAULT_DIFF =MeyersDiff.factory();
41+
42+
publicstaticvoidwithDefaultDiffAlgorithmFactory(DiffAlgorithmFactoryfactory) {
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
publicstatic <T>Patch<T>diff(List<T>original,List<T>revised,DiffAlgorithmListenerprogress) {
48-
returnDiffUtils.diff(original,revised,newMyersDiff<>(),progress);
58+
returnDiffUtils.diff(original,revised,DEFAULT_DIFF.create(),progress);
4959
}
5060

5161
publicstatic <T>Patch<T>diff(List<T>original,List<T>revised) {
52-
returnDiffUtils.diff(original,revised,newMyersDiff<>(),null);
62+
returnDiffUtils.diff(original,revised,DEFAULT_DIFF.create(),null);
5363
}
54-
64+
5565
publicstatic <T>Patch<T>diff(List<T>original,List<T>revised,booleanincludeEqualParts) {
56-
returnDiffUtils.diff(original,revised,newMyersDiff<>(),null,includeEqualParts);
66+
returnDiffUtils.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 diffalgorithm
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
publicstatic <T>Patch<T>diff(List<T>source,List<T>target,
8293
BiPredicate<T,T>equalizer) {
8394
if (equalizer !=null) {
8495
returnDiffUtils.diff(source,target,
85-
newMyersDiff<>(equalizer));
96+
DEFAULT_DIFF.create(equalizer));
8697
}
87-
returnDiffUtils.diff(source,target,newMyersDiff<>());
98+
returnDiffUtils.diff(source,target,newMeyersDiff<>());
8899
}
89100

90101
publicstatic <T>Patch<T>diff(List<T>original,List<T>revised,
91102
DiffAlgorithmI<T>algorithm,DiffAlgorithmListenerprogress) {
92103
returndiff(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 diffalgorithm
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
publicstatic <T>Patch<T>diff(List<T>original,List<T>revised,
108-
DiffAlgorithmI<T>algorithm,DiffAlgorithmListenerprogress,
119+
DiffAlgorithmI<T>algorithm,DiffAlgorithmListenerprogress,
109120
booleanincludeEqualParts) {
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 diffalgorithm
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
publicstatic <T>Patch<T>diff(List<T>original,List<T>revised,DiffAlgorithmI<T>algorithm) {
128139
returndiff(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 outof texts lists of characters, like DiffRowGenerator
145+
*does and merges those changes at the endtogether again.
135146
*
136147
* @param original
137148
* @param revised
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+
packagecom.github.difflib.algorithm;
17+
18+
importjava.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+
publicinterfaceDiffAlgorithmFactory {
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: 29 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,7 @@
1616
packagecom.github.difflib.algorithm.myers;
1717

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

2829
/**
29-
* A clean-room implementation of EugeneMyers greedy differencing algorithm.
30+
* A clean-room implementation of EugeneMeyers greedy differencing algorithm.
3031
*/
31-
publicfinalclassMyersDiff<T>implementsDiffAlgorithmI<T> {
32+
publicfinalclassMeyersDiff<T>implementsDiffAlgorithmI<T> {
3233

3334
privatefinalBiPredicate<T,T>equalizer;
3435

35-
publicMyersDiff() {
36+
publicMeyersDiff() {
3637
equalizer =Object::equals;
3738
}
3839

39-
publicMyersDiff(finalBiPredicate<T,T>equalizer) {
40+
publicMeyersDiff(finalBiPredicate<T,T>equalizer) {
4041
Objects.requireNonNull(equalizer,"equalizer must not be null");
4142
this.equalizer =equalizer;
4243
}
@@ -63,8 +64,9 @@ public List<Change> computeDiff(final List<T> source, final List<T> target, Diff
6364
}
6465

6566
/**
66-
* Computes the minimum diffpath that expresses de differences between the original and revised
67-
* 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.
6870
*
6971
* @param orig The original sequence.
7072
* @param rev The revised sequence.
@@ -138,8 +140,8 @@ private PathNode buildPath(final List<T> orig, final List<T> rev, DiffAlgorithmL
138140
* @param orig The original sequence.
139141
* @param rev The revised sequence.
140142
* @return A {@link Patch} script corresponding to the path.
141-
* @throws DifferentiationFailedException if a {@link Patch} could not be built from the given
142-
* path.
143+
* @throws DifferentiationFailedException if a {@link Patch} could not be
144+
*built from the givenpath.
143145
*/
144146
privateList<Change>buildRevision(PathNodeactualPath,List<T>orig,List<T>rev) {
145147
Objects.requireNonNull(actualPath,"path is null");
@@ -176,4 +178,23 @@ private List<Change> buildRevision(PathNode actualPath, List<T> orig, List<T> re
176178
}
177179
returnchanges;
178180
}
181+
182+
/**
183+
* Factory to create instances of this specific diff algorithm.
184+
*/
185+
publicstaticDiffAlgorithmFactoryfactory() {
186+
returnnewDiffAlgorithmFactory() {
187+
@Override
188+
public <T>DiffAlgorithmI<T>
189+
create() {
190+
returnnewMeyersDiff<T>();
191+
}
192+
193+
@Override
194+
public <T>DiffAlgorithmI<T>
195+
create(BiPredicate <T,T >equalizer) {
196+
returnnewMeyersDiff<T>(equalizer);
197+
}
198+
};
199+
}
179200
}

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

Lines changed: 28 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -23,6 +23,7 @@
2323
importjava.util.List;
2424
importjava.util.Objects;
2525
importjava.util.function.BiPredicate;
26+
importjava.util.function.Consumer;
2627

2728
/**
2829
*
@@ -43,13 +44,33 @@ public MeyersDiffWithLinearSpace(final BiPredicate<T, T> equalizer) {
4344

4445
@Override
4546
publicList<Change>computeDiff(List<T>source,List<T>target,DiffAlgorithmListenerprogress) {
47+
Objects.requireNonNull(source,"source list must not be null");
48+
Objects.requireNonNull(target,"target list must not be null");
49+
50+
if (progress !=null) {
51+
progress.diffStart();
52+
}
53+
4654
DiffDatadata =newDiffData(source,target);
47-
//shouldn't it be source.size() - 1?
48-
buildScript(data,0,source.size(),0,target.size());
55+
56+
intmaxIdx =source.size() +target.size();
57+
58+
buildScript(data,0,source.size(),0,target.size(),idx -> {
59+
if (progress !=null) {
60+
progress.diffStep(idx,maxIdx);
61+
}
62+
});
63+
64+
if (progress !=null) {
65+
progress.diffEnd();
66+
}
4967
returndata.script;
5068
}
5169

52-
privatevoidbuildScript(DiffDatadata,intstart1,intend1,intstart2,intend2) {
70+
privatevoidbuildScript(DiffDatadata,intstart1,intend1,intstart2,intend2,Consumer<Integer>progress) {
71+
if (progress !=null) {
72+
progress.accept(start1);
73+
}
5374
finalSnakemiddle =getMiddleSnake(data,start1,end1,start2,end2);
5475
if (middle ==null
5576
||middle.start ==end1 &&middle.diag ==end1 -end2
@@ -86,8 +107,8 @@ private void buildScript(DiffData data, int start1, int end1, int start2, int en
86107
}
87108
}
88109
}else {
89-
buildScript(data,start1,middle.start,start2,middle.start -middle.diag);
90-
buildScript(data,middle.end,end1,middle.end -middle.diag,end2);
110+
buildScript(data,start1,middle.start,start2,middle.start -middle.diag,progress);
111+
buildScript(data,middle.end,end1,middle.end -middle.diag,end2,progress);
91112
}
92113
}
93114

@@ -169,7 +190,7 @@ private Snake buildSnake(DiffData data, final int start, final int diag, final i
169190
returnnewSnake(start,end,diag);
170191
}
171192

172-
classDiffData {
193+
privateclassDiffData {
173194

174195
finalintsize;
175196
finalint[]vDown;
@@ -188,7 +209,7 @@ public DiffData(List<T> source, List<T> target) {
188209
}
189210
}
190211

191-
classSnake {
212+
privateclassSnake {
192213

193214
finalintstart;
194215
finalintend;

‎java-diff-utils/src/test/java/com/github/difflib/algorithm/myers/MeyersDiffWithLinearSpaceTest.java‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -39,8 +39,8 @@ public void testDiffMyersExample1Forward() {
3939
finalPatch<String>patch =Patch.generate(original,revised,newMeyersDiffWithLinearSpace<String>().computeDiff(original,revised,null));
4040
assertNotNull(patch);
4141
System.out.println(patch);
42-
assertEquals(4,patch.getDeltas().size());
43-
assertEquals("Patch{deltas=[[DeleteDelta, position: 0, lines: [A, B]], [InsertDelta, position:3, lines: [B]], [DeleteDelta, position: 5, lines: [B]], [InsertDelta, position: 7, lines: [C]]]}",patch.toString());
42+
assertEquals(5,patch.getDeltas().size());
43+
assertEquals("Patch{deltas=[[InsertDelta, position: 0, lines: [C]], [DeleteDelta, position: 0, lines: [A]], [DeleteDelta, position:2, lines: [C]], [DeleteDelta, position: 5, lines: [B]], [InsertDelta, position: 7, lines: [C]]]}",patch.toString());
4444
}
4545

4646
@Test
@@ -68,8 +68,8 @@ public void diffEnd() {
6868
}));
6969
assertNotNull(patch);
7070
System.out.println(patch);
71-
assertEquals(4,patch.getDeltas().size());
72-
assertEquals("Patch{deltas=[[DeleteDelta, position: 0, lines: [A, B]], [InsertDelta, position:3, lines: [B]], [DeleteDelta, position: 5, lines: [B]], [InsertDelta, position: 7, lines: [C]]]}",patch.toString());
71+
assertEquals(5,patch.getDeltas().size());
72+
assertEquals("Patch{deltas=[[InsertDelta, position: 0, lines: [C]], [DeleteDelta, position: 0, lines: [A]], [DeleteDelta, position:2, lines: [C]], [DeleteDelta, position: 5, lines: [B]], [InsertDelta, position: 7, lines: [C]]]}",patch.toString());
7373
System.out.println(logdata);
7474
assertEquals(8,logdata.size());
7575
}

‎java-diff-utils/src/test/java/com/github/difflib/algorithm/myers/MyersDiffTest.java‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -34,7 +34,7 @@ public class MyersDiffTest {
3434
publicvoidtestDiffMyersExample1Forward() {
3535
List<String>original =Arrays.asList("A","B","C","A","B","B","A");
3636
List<String>revised =Arrays.asList("C","B","A","B","A","C");
37-
finalPatch<String>patch =Patch.generate(original,revised,newMyersDiff<String>().computeDiff(original,revised,null));
37+
finalPatch<String>patch =Patch.generate(original,revised,newMeyersDiff<String>().computeDiff(original,revised,null));
3838
assertNotNull(patch);
3939
assertEquals(4,patch.getDeltas().size());
4040
assertEquals("Patch{deltas=[[DeleteDelta, position: 0, lines: [A, B]], [InsertDelta, position: 3, lines: [B]], [DeleteDelta, position: 5, lines: [B]], [InsertDelta, position: 7, lines: [C]]]}",patch.toString());
@@ -47,7 +47,7 @@ public void testDiffMyersExample1ForwardWithListener() {
4747

4848
List<String>logdata =newArrayList<>();
4949
finalPatch<String>patch =Patch.generate(original,revised,
50-
newMyersDiff<String>().computeDiff(original,revised,newDiffAlgorithmListener() {
50+
newMeyersDiff<String>().computeDiff(original,revised,newDiffAlgorithmListener() {
5151
@Override
5252
publicvoiddiffStart() {
5353
logdata.add("start");

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp