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