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