Skip to content
This repository was archived by the owner on Oct 21, 2020. It is now read-only.

Commit cb8e8bf

Browse files
wumpzwumpz
committed
removed inheritance for pathnode
1 parent a41c680 commit cb8e8bf

File tree

7 files changed

+98
-149
lines changed

7 files changed

+98
-149
lines changed

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

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -38,7 +38,9 @@ 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 Patch<T> diff(T[] original, T[] revised) throws DiffException;
41+
public default Patch<T> diff(T[] original, T[] revised) throws DiffException {
42+
return diff(Arrays.asList(original), Arrays.asList(revised));
43+
}
4244

4345
/**
4446
* Computes the difference between the original sequence and the revised sequence and returns it

‎src/main/java/difflib/algorithm/myers/DiffNode.java

Lines changed: 0 additions & 62 deletions
This file was deleted.

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

Lines changed: 6 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -74,16 +74,6 @@ public MyersDiff(final Equalizer<T> equalizer) {
7474
this.equalizer = equalizer;
7575
}
7676

77-
/**
78-
* {@inheritDoc}
79-
*
80-
* @return Returns an empty diff if get the error while procession the difference.
81-
*/
82-
@Override
83-
public Patch<T> diff(final T[] original, final T[] revised) throws DiffException {
84-
return diff(Arrays.asList(original), Arrays.asList(revised));
85-
}
86-
8777
/**
8878
* {@inheritDoc}
8979
*
@@ -93,7 +83,7 @@ public Patch<T> diff(final T[] original, final T[] revised) throws DiffException
9383
public Patch<T> diff(final List<T> original, final List<T> revised) throws DiffException {
9484
Objects.requireNonNull(original, "original list must not be null");
9585
Objects.requireNonNull(revised, "revised list must not be null");
96-
86+
9787
PathNode path = buildPath(original, revised);
9888
return buildRevision(path, original, revised);
9989
}
@@ -121,7 +111,7 @@ private PathNode buildPath(final List<T> orig, final List<T> rev)
121111
final int middle = size / 2;
122112
final PathNode diagonal[] = new PathNode[size];
123113

124-
diagonal[middle + 1] = new Snake(0, -1, null);
114+
diagonal[middle + 1] = new PathNode(0, -1, true, null);
125115
for (int d = 0; d < MAX; d++) {
126116
for (int k = -d; k <= d; k += 2) {
127117
final int kmiddle = middle + k;
@@ -142,17 +132,15 @@ private PathNode buildPath(final List<T> orig, final List<T> rev)
142132

143133
int j = i - k;
144134

145-
PathNode node = new DiffNode(i, j, prev);
135+
PathNode node = new PathNode(i, j, false, prev);
146136

147-
// orig and rev are zero-based
148-
// but the algorithm is one-based
149-
// that's why there's no +1 when indexing the sequences
150137
while (i < N && j < M && equalizer.equals(orig.get(i), rev.get(j))) {
151138
i++;
152139
j++;
153140
}
154-
if (i > node.i) {
155-
node = new Snake(i, j, node);
141+
142+
if (i != node.i) {
143+
node = new PathNode(i, j, true, node);
156144
}
157145

158146
diagonal[kmiddle] = node;
@@ -162,7 +150,6 @@ private PathNode buildPath(final List<T> orig, final List<T> rev)
162150
}
163151
}
164152
diagonal[middle + d - 1] = null;
165-
166153
}
167154
// According to Myers, this cannot happen
168155
throw new DifferentiationFailedException("could not find a diff path");

‎src/main/java/difflib/algorithm/myers/PathNode.java

Lines changed: 14 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -22,13 +22,13 @@
2222
/**
2323
* A node in a diffpath.
2424
*
25-
* @author <a href="mailto:juanco@suigeneris.org">Juanco Anez</a>
25+
* @author <a href="mailto:juanco@suigeneris.org">Juanco Anez</a>
2626
*
2727
* @see DiffNode
2828
* @see Snake
2929
*
3030
*/
31-
public abstract class PathNode {
31+
public final class PathNode {
3232

3333
/**
3434
* Position in the original sequence.
@@ -43,25 +43,29 @@ public abstract class PathNode {
4343
*/
4444
public final PathNode prev;
4545

46+
public final boolean snake;
47+
4648
/**
4749
* Concatenates a new path node with an existing diffpath.
4850
*
4951
* @param i The position in the original sequence for the new node.
5052
* @param j The position in the revised sequence for the new node.
5153
* @param prev The previous node in the path.
5254
*/
53-
public PathNode(int i, int j, PathNode prev) {
55+
public PathNode(int i, int j, boolean snake, PathNode prev) {
5456
this.i = i;
5557
this.j = j;
56-
this.prev = prev;
58+
if (snake) {
59+
this.prev = prev;
60+
} else {
61+
this.prev = (prev == null ? null : prev.previousSnake());
62+
}
63+
this.snake = snake;
5764
}
5865

59-
/**
60-
* Is this node a {@link Snake Snake node}?
61-
*
62-
* @return true if this is a {@link Snake Snake node}
63-
*/
64-
public abstract boolean isSnake();
66+
public boolean isSnake() {
67+
return snake;
68+
}
6569

6670
/**
6771
* Is this a bootstrap node?

‎src/main/java/difflib/algorithm/myers/Snake.java

Lines changed: 0 additions & 56 deletions
This file was deleted.

‎src/test/java/difflib/DiffUtilsTest.java

Lines changed: 9 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -145,11 +145,19 @@ public void testPossibleDiffHangOnLargeDatasetDnaumenkoIssue26() throws IOExcept
145145
assertEquals(1, patch.getDeltas().size());
146146
}
147147

148-
private static List<String> readStringListFromInputStream(InputStream is) throws IOException {
148+
public static List<String> readStringListFromInputStream(InputStream is) throws IOException {
149149
try (BufferedReader reader = new BufferedReader(
150150
new InputStreamReader(is, Charset.forName(StandardCharsets.UTF_8.name())))) {
151151

152152
return reader.lines().collect(toList());
153153
}
154154
}
155+
156+
@Test
157+
public void testDiffMyersExample1() throws DiffException {
158+
final Patch<String> patch = DiffUtils.diff(Arrays.asList("A","B","C","A","B","B","A"), Arrays.asList("C","B","A","B","A","C"));
159+
assertNotNull(patch);
160+
assertEquals(4, patch.getDeltas().size());
161+
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());
162+
}
155163
}

‎src/test/java/difflib/algorithm/myers/MyersDiffTest.java

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
/*
2+
* Copyright 2017 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 difflib.algorithm.myers;
17+
18+
import difflib.DiffUtils;
19+
import difflib.algorithm.DiffException;
20+
import difflib.patch.Patch;
21+
import java.util.Arrays;
22+
import org.junit.After;
23+
import org.junit.AfterClass;
24+
import org.junit.Before;
25+
import org.junit.BeforeClass;
26+
import org.junit.Test;
27+
import static org.junit.Assert.*;
28+
29+
/**
30+
*
31+
* @author tw
32+
*/
33+
public class MyersDiffTest {
34+
35+
public MyersDiffTest() {
36+
}
37+
38+
@BeforeClass
39+
public static void setUpClass() {
40+
}
41+
42+
@AfterClass
43+
public static void tearDownClass() {
44+
}
45+
46+
@Before
47+
public void setUp() {
48+
}
49+
50+
@After
51+
public void tearDown() {
52+
}
53+
54+
55+
56+
@Test
57+
public void testDiffMyersExample1Forward() throws DiffException {
58+
final Patch<String> patch = new MyersDiff<String>().diff(
59+
Arrays.asList("A","B","C","A","B","B","A"),
60+
Arrays.asList("C","B","A","B","A","C"));
61+
assertNotNull(patch);
62+
assertEquals(4, patch.getDeltas().size());
63+
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());
64+
}
65+
66+
}

0 commit comments

Comments
 (0)