(See the previous iteration here.)
After further revising my code, I have:
com.github.coderodde.diff.Diff.java:
package com.github.coderodde.diff;
import java.io.File;
import java.io.IOException;
import java.nio.file.Files;
import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
public class Diff {
public static final class Difference {
public enum Direction {
EQUAL,
INSERT,
DELETE,
}
private final Direction direction;
private final String line;
public Difference(Direction direction, String line) {
this.direction = direction;
this.line = line;
}
public Direction getDirection() {
return direction;
}
public String getLine() {
return line;
}
}
private static final String NL = System.lineSeparator();
private static final String HELP_MESSAGE =
"java -jar Diff.jar OLD_FILE NEW_FILE";
private final List<String> oldLines;
private final List<String> newLines;
private final int[][] matrix;
public Diff(List<String> oldSourceLines, List<String> newSourceLines) {
this.oldLines = Objects.requireNonNull(oldSourceLines);
this.newLines = Objects.requireNonNull(newSourceLines);
this.matrix = new int[oldSourceLines.size() + 1]
[newSourceLines.size() + 1];
}
public List<Difference> compute() {
computeLongestCommonSubsequenceMatrix();
return buildDiff();
}
public static void main(String[] args) {
if (args.length != 2) {
System.out.println(HELP_MESSAGE);
System.exit(0);
}
try {
List<String> oldLines = readFile(new File(args[0]));
List<String> newLines = readFile(new File(args[1]));
Diff diff = new Diff(oldLines, newLines);
System.out.println(combine(diff.compute()));
} catch (IOException ex) {
System.err.println("I/O failed: " + ex.getMessage());
System.exit(1);
}
}
private static String combine(List<Difference> differences) {
StringBuilder stringBuilder = new StringBuilder();
for (Difference difference : differences) {
switch (difference.getDirection()) {
case INSERT:
stringBuilder.append("+ ");
break;
case DELETE:
stringBuilder.append("- ");
break;
case EQUAL:
break;
default:
throw new IllegalStateException(
"Unknown enum: " + difference.getDirection());
}
stringBuilder.append(difference.getLine()).append(NL);
}
return stringBuilder.toString().trim();
}
// Reads all the file lines into a list and returns the list in question.
private static List<String> readFile(File file) throws IOException {
return Files.readAllLines(file.toPath());
}
// This algorithm solves the Longest Common Subsequence problem. The
// alphabet is not assumed to be a customary alphabet, but rather all
// possible strings over a simple alphabet.
private void computeLongestCommonSubsequenceMatrix() {
for (int i = 1; i <= oldLines.size(); ++i) {
for (int j = 1; j <= newLines.size(); ++j) {
if (oldLines.get(i - 1)
.equals(newLines.get(j - 1))) {
matrix[i][j] = matrix[i - 1][j - 1] + 1;
} else {
matrix[i][j] = Math.max(matrix[i - 1][j],
matrix[i][j - 1]);
}
}
}
}
// The entry point for the algorithm that reconstructs the LCS from the
// matrix.
private List<Difference> buildDiff() {
List<Difference> differences = new ArrayList<>();
buildDiff(differences,
oldLines.size() - 1,
newLines.size() - 1);
return differences;
}
// Reconstructs the diff content from the LCS matrix.
private void buildDiff(List<Difference> differences,
int i,
int j) {
if (i >= 0
&& j >= 0
&& oldLines.get(i).equals(newLines.get(j))) {
buildDiff(differences,
i - 1,
j - 1);
differences.add(
new Difference(
Difference.Direction.EQUAL,
oldLines.get(i)));
} else if (j > 0 && (i == 0 || matrix[i][j - 1] >= matrix[i - 1][j])) {
buildDiff(differences,
i,
j - 1);
differences.add(
new Difference(
Difference.Direction.INSERT,
newLines.get(j)));
} else if (i > 0 && (j == 0 || matrix[i][j - 1] < matrix[i - 1][j])) {
buildDiff(differences,
i - 1,
j);
differences.add(
new Difference(
Difference.Direction.DELETE,
oldLines.get(i)));
}
}
}
Critique request
As always, please tell me anything that comes to mind.
i
andj
as parameters forbuildDiff
is unreadable. Yet it seems you still use them here. Did you disagree with that part of the answer? \$\endgroup\$