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

Commit8bb4a9a

Browse files
committed
first implementation of meyers diff with linear space
1 parent3d5343c commit8bb4a9a

File tree

9 files changed

+514
-4
lines changed

9 files changed

+514
-4
lines changed
Lines changed: 195 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,195 @@
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.myers;
17+
18+
importcom.github.difflib.algorithm.Change;
19+
importcom.github.difflib.algorithm.DiffAlgorithmI;
20+
importcom.github.difflib.algorithm.DiffAlgorithmListener;
21+
importcom.github.difflib.patch.DeltaType;
22+
importjava.util.ArrayList;
23+
importjava.util.List;
24+
importjava.util.Objects;
25+
importjava.util.function.BiPredicate;
26+
27+
/**
28+
*
29+
* @author tw
30+
*/
31+
publicclassMeyersDiffWithLinearSpace<T>implementsDiffAlgorithmI<T> {
32+
33+
privatefinalBiPredicate<T,T>equalizer;
34+
35+
publicMeyersDiffWithLinearSpace() {
36+
equalizer =Object::equals;
37+
}
38+
39+
publicMeyersDiffWithLinearSpace(finalBiPredicate<T,T>equalizer) {
40+
Objects.requireNonNull(equalizer,"equalizer must not be null");
41+
this.equalizer =equalizer;
42+
}
43+
44+
@Override
45+
publicList<Change>computeDiff(List<T>source,List<T>target,DiffAlgorithmListenerprogress) {
46+
DiffDatadata =newDiffData(source,target);
47+
//shouldn't it be source.size() - 1?
48+
buildScript(data,0,source.size(),0,target.size());
49+
returndata.script;
50+
}
51+
52+
privatevoidbuildScript(DiffDatadata,intstart1,intend1,intstart2,intend2) {
53+
finalSnakemiddle =getMiddleSnake(data,start1,end1,start2,end2);
54+
if (middle ==null
55+
||middle.start ==end1 &&middle.diag ==end1 -end2
56+
||middle.end ==start1 &&middle.diag ==start1 -start2) {
57+
inti =start1;
58+
intj =start2;
59+
while (i <end1 ||j <end2) {
60+
if (i <end1 &&j <end2 &&equalizer.test(data.source.get(i),data.target.get(j))) {
61+
//script.append(new KeepCommand<>(left.charAt(i)));
62+
++i;
63+
++j;
64+
}else {
65+
//TODO: compress these commands.
66+
if (end1 -start1 >end2 -start2) {
67+
//script.append(new DeleteCommand<>(left.charAt(i)));
68+
data.script.add(newChange(DeltaType.DELETE,i,i +1,j,j));
69+
++i;
70+
}else {
71+
//script.append(new InsertCommand<>(right.charAt(j)));
72+
data.script.add(newChange(DeltaType.INSERT,i,i,j,j +1));
73+
++j;
74+
}
75+
}
76+
}
77+
}else {
78+
buildScript(data,start1,middle.start,start2,middle.start -middle.diag);
79+
// for (int i = middle.getStart(); i < middle.getEnd(); ++i) {
80+
// script.append(new KeepCommand<>(left.charAt(i)));
81+
// }
82+
buildScript(data,middle.end,end1,middle.end -middle.diag,end2);
83+
}
84+
}
85+
86+
privateSnakegetMiddleSnake(DiffDatadata,intstart1,intend1,intstart2,intend2) {
87+
finalintm =end1 -start1;
88+
finalintn =end2 -start2;
89+
if (m ==0 ||n ==0) {
90+
returnnull;
91+
}
92+
93+
finalintdelta =m -n;
94+
finalintsum =n +m;
95+
finalintoffset = (sum %2 ==0 ?sum :sum +1) /2;
96+
data.vDown[1 +offset] =start1;
97+
data.vUp[1 +offset] =end1 +1;
98+
99+
for (intd =0;d <=offset; ++d) {
100+
// Down
101+
for (intk = -d;k <=d;k +=2) {
102+
// First step
103+
104+
finalinti =k +offset;
105+
if (k == -d ||k !=d &&data.vDown[i -1] <data.vDown[i +1]) {
106+
data.vDown[i] =data.vDown[i +1];
107+
}else {
108+
data.vDown[i] =data.vDown[i -1] +1;
109+
}
110+
111+
intx =data.vDown[i];
112+
inty =x -start1 +start2 -k;
113+
114+
while (x <end1 &&y <end2 &&equalizer.test(data.source.get(x),data.target.get(y))) {
115+
data.vDown[i] = ++x;
116+
++y;
117+
}
118+
// Second step
119+
if (delta %2 !=0 &&delta -d <=k &&k <=delta +d) {
120+
if (data.vUp[i -delta] <=data.vDown[i]) {
121+
returnbuildSnake(data,data.vUp[i -delta],k +start1 -start2,end1,end2);
122+
}
123+
}
124+
}
125+
126+
// Up
127+
for (intk =delta -d;k <=delta +d;k +=2) {
128+
// First step
129+
finalinti =k +offset -delta;
130+
if (k ==delta -d
131+
||k !=delta +d &&data.vUp[i +1] <=data.vUp[i -1]) {
132+
data.vUp[i] =data.vUp[i +1] -1;
133+
}else {
134+
data.vUp[i] =data.vUp[i -1];
135+
}
136+
137+
intx =data.vUp[i] -1;
138+
inty =x -start1 +start2 -k;
139+
while (x >=start1 &&y >=start2 &&equalizer.test(data.source.get(x),data.target.get(y))) {
140+
data.vUp[i] =x--;
141+
y--;
142+
}
143+
// Second step
144+
if (delta %2 ==0 && -d <=k &&k <=d) {
145+
if (data.vUp[i] <=data.vDown[i +delta]) {
146+
returnbuildSnake(data,data.vUp[i],k +start1 -start2,end1,end2);
147+
}
148+
}
149+
}
150+
}
151+
152+
// According to Myers, this cannot happen
153+
thrownewIllegalStateException("could not find a diff path");
154+
}
155+
156+
privateSnakebuildSnake(DiffDatadata,finalintstart,finalintdiag,finalintend1,finalintend2) {
157+
intend =start;
158+
while (end -diag <end2 &&end <end1 &&equalizer.test(data.source.get(end),data.target.get(end -diag))) {
159+
++end;
160+
}
161+
returnnewSnake(start,end,diag);
162+
}
163+
164+
classDiffData {
165+
166+
finalintsize;
167+
finalint[]vDown;
168+
finalint[]vUp;
169+
finalList<Change>script;
170+
finalList<T>source;
171+
finalList<T>target;
172+
173+
publicDiffData(List<T>source,List<T>target) {
174+
this.source =source;
175+
this.target =target;
176+
size =source.size() +target.size() +2;
177+
vDown =newint[size];
178+
vUp =newint[size];
179+
script =newArrayList<>();
180+
}
181+
}
182+
183+
classSnake {
184+
185+
finalintstart;
186+
finalintend;
187+
finalintdiag;
188+
189+
publicSnake(finalintstart,finalintend,finalintdiag) {
190+
this.start =start;
191+
this.end =end;
192+
this.diag =diag;
193+
}
194+
}
195+
}

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

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -30,11 +30,10 @@
3030
*/
3131
publicfinalclassMyersDiff<T>implementsDiffAlgorithmI<T> {
3232

33-
privatefinalBiPredicate<T,T>DEFAULT_EQUALIZER =Object::equals;
3433
privatefinalBiPredicate<T,T>equalizer;
3534

3635
publicMyersDiff() {
37-
equalizer =DEFAULT_EQUALIZER;
36+
equalizer =Object::equals;
3837
}
3938

4039
publicMyersDiff(finalBiPredicate<T,T>equalizer) {
Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,73 @@
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.myers;
17+
18+
importcom.github.difflib.algorithm.DiffAlgorithmListener;
19+
importcom.github.difflib.patch.Patch;
20+
importjava.util.ArrayList;
21+
importjava.util.Arrays;
22+
importjava.util.List;
23+
importorg.junit.jupiter.api.Test;
24+
importstaticorg.junit.jupiter.api.Assertions.*;
25+
26+
/**
27+
*
28+
* @author tw
29+
*/
30+
publicclassMeyersDiffWithLinearSpaceTest {
31+
32+
@Test
33+
publicvoidtestDiffMyersExample1Forward() {
34+
List<String>original =Arrays.asList("A","B","C","A","B","B","A");
35+
List<String>revised =Arrays.asList("C","B","A","B","A","C");
36+
finalPatch<String>patch =Patch.generate(original,revised,newMeyersDiffWithLinearSpace<String>().computeDiff(original,revised,null));
37+
assertNotNull(patch);
38+
System.out.println(patch);
39+
assertEquals(4,patch.getDeltas().size());
40+
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());
41+
}
42+
43+
@Test
44+
publicvoidtestDiffMyersExample1ForwardWithListener() {
45+
List<String>original =Arrays.asList("A","B","C","A","B","B","A");
46+
List<String>revised =Arrays.asList("C","B","A","B","A","C");
47+
48+
List<String>logdata =newArrayList<>();
49+
finalPatch<String>patch =Patch.generate(original,revised,
50+
newMeyersDiffWithLinearSpace<String>().computeDiff(original,revised,newDiffAlgorithmListener() {
51+
@Override
52+
publicvoiddiffStart() {
53+
logdata.add("start");
54+
}
55+
56+
@Override
57+
publicvoiddiffStep(intvalue,intmax) {
58+
logdata.add(value +" - " +max);
59+
}
60+
61+
@Override
62+
publicvoiddiffEnd() {
63+
logdata.add("end");
64+
}
65+
}));
66+
assertNotNull(patch);
67+
System.out.println(patch);
68+
assertEquals(4,patch.getDeltas().size());
69+
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());
70+
System.out.println(logdata);
71+
assertEquals(8,logdata.size());
72+
}
73+
}

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

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -69,5 +69,4 @@ public void diffEnd() {
6969
System.out.println(logdata);
7070
assertEquals(8,logdata.size());
7171
}
72-
7372
}
Lines changed: 104 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,104 @@
1+
packagecom.github.difflib.algorithm.myers;
2+
3+
importcom.github.difflib.patch.*;
4+
importstaticorg.junit.jupiter.api.Assertions.assertEquals;
5+
importstaticorg.junit.jupiter.api.Assertions.fail;
6+
7+
importjava.io.ByteArrayInputStream;
8+
importjava.io.ByteArrayOutputStream;
9+
importjava.io.IOException;
10+
importjava.io.ObjectInputStream;
11+
importjava.io.ObjectOutputStream;
12+
importjava.util.Arrays;
13+
importjava.util.List;
14+
15+
importorg.junit.jupiter.api.Test;
16+
17+
importcom.github.difflib.DiffUtils;
18+
19+
publicclassWithMeyersDiffWithLinearSpacePatchTest {
20+
21+
@Test
22+
publicvoidtestPatch_Insert() {
23+
finalList<String>insertTest_from =Arrays.asList("hhh");
24+
finalList<String>insertTest_to =Arrays.asList("hhh","jjj","kkk","lll");
25+
26+
finalPatch<String>patch =DiffUtils.diff(insertTest_from,insertTest_to,newMeyersDiffWithLinearSpace<String>());
27+
try {
28+
assertEquals(insertTest_to,DiffUtils.patch(insertTest_from,patch));
29+
}catch (PatchFailedExceptione) {
30+
fail(e.getMessage());
31+
}
32+
}
33+
34+
@Test
35+
publicvoidtestPatch_Delete() {
36+
finalList<String>deleteTest_from =Arrays.asList("ddd","fff","ggg","hhh");
37+
finalList<String>deleteTest_to =Arrays.asList("ggg");
38+
39+
finalPatch<String>patch =DiffUtils.diff(deleteTest_from,deleteTest_to,newMeyersDiffWithLinearSpace<String>());
40+
try {
41+
assertEquals(deleteTest_to,DiffUtils.patch(deleteTest_from,patch));
42+
}catch (PatchFailedExceptione) {
43+
fail(e.getMessage());
44+
}
45+
}
46+
47+
@Test
48+
publicvoidtestPatch_Change() {
49+
finalList<String>changeTest_from =Arrays.asList("aaa","bbb","ccc","ddd");
50+
finalList<String>changeTest_to =Arrays.asList("aaa","bxb","cxc","ddd");
51+
52+
finalPatch<String>patch =DiffUtils.diff(changeTest_from,changeTest_to,newMeyersDiffWithLinearSpace<String>());
53+
try {
54+
assertEquals(changeTest_to,DiffUtils.patch(changeTest_from,patch));
55+
}catch (PatchFailedExceptione) {
56+
fail(e.getMessage());
57+
}
58+
}
59+
60+
@Test
61+
publicvoidtestPatch_Serializable()throwsIOException,ClassNotFoundException {
62+
finalList<String>changeTest_from =Arrays.asList("aaa","bbb","ccc","ddd");
63+
finalList<String>changeTest_to =Arrays.asList("aaa","bxb","cxc","ddd");
64+
65+
finalPatch<String>patch =DiffUtils.diff(changeTest_from,changeTest_to,newMeyersDiffWithLinearSpace<String>());
66+
ByteArrayOutputStreambaos =newByteArrayOutputStream();
67+
ObjectOutputStreamout =newObjectOutputStream(baos);
68+
out.writeObject(patch);
69+
out.close();
70+
ByteArrayInputStreambais =newByteArrayInputStream(baos.toByteArray());
71+
ObjectInputStreamin =newObjectInputStream(bais);
72+
Patch<String>result = (Patch<String>)in.readObject();
73+
in.close();
74+
75+
try {
76+
assertEquals(changeTest_to,DiffUtils.patch(changeTest_from,result));
77+
}catch (PatchFailedExceptione) {
78+
fail(e.getMessage());
79+
}
80+
81+
}
82+
83+
@Test
84+
publicvoidtestPatch_Change_withExceptionProcessor() {
85+
finalList<String>changeTest_from =Arrays.asList("aaa","bbb","ccc","ddd");
86+
finalList<String>changeTest_to =Arrays.asList("aaa","bxb","cxc","ddd");
87+
88+
finalPatch<String>patch =DiffUtils.diff(changeTest_from,changeTest_to,newMeyersDiffWithLinearSpace<String>());
89+
90+
changeTest_from.set(2,"CDC");
91+
92+
patch.withConflictOutput(Patch.CONFLICT_PRODUCES_MERGE_CONFLICT);
93+
94+
try {
95+
List<String>data =DiffUtils.patch(changeTest_from,patch);
96+
assertEquals(9,data.size());
97+
98+
assertEquals(Arrays.asList("aaa","<<<<<< HEAD","bbb","CDC","======","bbb","ccc",">>>>>>> PATCH","ddd"),data);
99+
100+
}catch (PatchFailedExceptione) {
101+
fail(e.getMessage());
102+
}
103+
}
104+
}

0 commit comments

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