annotate src/goodjava/util/LineDiff.java @ 1807:ffa28e2155bb

add line_diff
author Franklin Schmidt <fschmidt@gmail.com>
date Sun, 12 May 2024 15:25:29 -0600
parents
children 69623c62aa34
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
1807
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
1 package goodjava.util;
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
2
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
3 import java.util.List;
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
4 import java.util.ArrayList;
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
5 import java.io.BufferedReader;
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
6 import java.io.StringReader;
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
7 import java.io.IOException;
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
8
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
9
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
10 public final class LineDiff {
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
11 public static final char DELETE = '<';
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
12 public static final char INSERT = '>';
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
13
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
14 public static class Diff {
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
15 public final char operation;
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
16 public final int line;
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
17 public final String text;
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
18
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
19 private Diff(char operation,int line,String text) {
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
20 this.operation = operation;
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
21 this.line = line;
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
22 this.text = text;
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
23 }
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
24 }
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
25
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
26 public static String[] stringToLines(String s) {
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
27 List<String> list = new ArrayList<String>();
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
28 BufferedReader br = new BufferedReader(new StringReader(s));
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
29 String line;
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
30 try {
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
31 while( (line = br.readLine()) != null ) {
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
32 list.add(line);
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
33 }
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
34 } catch(IOException e) {
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
35 throw new RuntimeException(e);
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
36 }
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
37 return list.toArray(new String[list.size()]);
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
38 }
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
39
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
40 public static List<Diff> diff(String oldStr,String newStr) {
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
41 return diff( stringToLines(oldStr), stringToLines(newStr) );
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
42 }
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
43
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
44 // https://introcs.cs.princeton.edu/java/23recursion/Diff.java.html
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
45 public static List<Diff> diff(String[] oldLines,String[] newLines) {
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
46 List<Diff> diffs = new ArrayList<Diff>();
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
47
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
48 int nOld = oldLines.length;
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
49 int nNew = newLines.length;
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
50
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
51 // opt[iOld][iNew] = length of LCS of x[iOld..nOld] and y[iNew..nNew]
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
52 int[][] opt = new int[nOld+1][nNew+1];
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
53
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
54 // compute length of LCS and all subproblems via dynamic programming
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
55 for (int iOld = nOld-1; iOld >= 0; iOld--) {
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
56 for (int iNew = nNew-1; iNew >= 0; iNew--) {
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
57 if (oldLines[iOld].equals(newLines[iNew]))
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
58 opt[iOld][iNew] = opt[iOld+1][iNew+1] + 1;
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
59 else
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
60 opt[iOld][iNew] = Math.max(opt[iOld+1][iNew], opt[iOld][iNew+1]);
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
61 }
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
62 }
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
63
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
64 int iOld = 0, iNew = 0;
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
65 while (iOld < nOld && iNew < nNew) {
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
66 if (oldLines[iOld].equals(newLines[iNew])) {
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
67 iOld++;
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
68 iNew++;
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
69 } else if (opt[iOld+1][iNew] >= opt[iOld][iNew+1]) {
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
70 diffs.add( new Diff( DELETE, iOld+1, oldLines[iOld] ) );
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
71 iOld++;
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
72 } else {
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
73 diffs.add( new Diff( INSERT, iOld+1, newLines[iNew] ) );
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
74 iNew++;
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
75 }
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
76 }
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
77
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
78 // dump out one remainder of one string if the other is exhausted
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
79 while( iOld < nOld ) {
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
80 diffs.add( new Diff( DELETE, iOld+1, oldLines[iOld] ) );
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
81 iOld++;
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
82 }
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
83 while( iNew < nNew ) {
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
84 diffs.add( new Diff( INSERT, nOld+1, newLines[iNew] ) );
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
85 iNew++;
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
86 }
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
87
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
88 return diffs;
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
89 }
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
90 }