2
\$\begingroup\$

(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.

\$\endgroup\$
2
  • \$\begingroup\$ In your previous iteration, it has been noted in the answers using i and j as parameters for buildDiff is unreadable. Yet it seems you still use them here. Did you disagree with that part of the answer? \$\endgroup\$
    – Mast
    Aug 25 at 17:18
  • \$\begingroup\$ You have a point. It just didn’t reach my attention. \$\endgroup\$
    – coderodde
    Aug 26 at 8:28

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.