annotate src/goodjava/util/LineDiff.java @ 1821:d28f5ed56454

fix stringify empty list
author Franklin Schmidt <fschmidt@gmail.com>
date Tue, 09 Jul 2024 07:17:41 -0600
parents 90187946d1a4
children
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 String text;
1809
Franklin Schmidt <fschmidt@gmail.com>
parents: 1808
diff changeset
17 public final int lineOld;
Franklin Schmidt <fschmidt@gmail.com>
parents: 1808
diff changeset
18 public final int lineNew;
1807
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
19
1809
Franklin Schmidt <fschmidt@gmail.com>
parents: 1808
diff changeset
20 private Diff(char operation,String line,int iOld,int iNew) {
1807
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
21 this.operation = operation;
1809
Franklin Schmidt <fschmidt@gmail.com>
parents: 1808
diff changeset
22 this.text = line;
Franklin Schmidt <fschmidt@gmail.com>
parents: 1808
diff changeset
23 this.lineOld = iOld + 1;
Franklin Schmidt <fschmidt@gmail.com>
parents: 1808
diff changeset
24 this.lineNew = iNew + 1;
1807
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 }
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
27
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
28 public static String[] stringToLines(String s) {
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
29 List<String> list = new ArrayList<String>();
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
30 BufferedReader br = new BufferedReader(new StringReader(s));
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
31 String line;
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
32 try {
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
33 while( (line = br.readLine()) != null ) {
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
34 list.add(line);
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
35 }
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
36 } catch(IOException e) {
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
37 throw new RuntimeException(e);
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 return list.toArray(new String[list.size()]);
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
40 }
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
41
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
42 public static List<Diff> diff(String oldStr,String newStr) {
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
43 return diff( stringToLines(oldStr), stringToLines(newStr) );
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
44 }
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
45
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
46 // https://introcs.cs.princeton.edu/java/23recursion/Diff.java.html
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
47 public static List<Diff> diff(String[] oldLines,String[] newLines) {
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
48 List<Diff> diffs = new ArrayList<Diff>();
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
49
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
50 int nOld = oldLines.length;
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
51 int nNew = newLines.length;
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
52
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
53 // 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
54 int[][] opt = new int[nOld+1][nNew+1];
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
55
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
56 // compute length of LCS and all subproblems via dynamic programming
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
57 for (int iOld = nOld-1; iOld >= 0; iOld--) {
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
58 for (int iNew = nNew-1; iNew >= 0; iNew--) {
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
59 if (oldLines[iOld].equals(newLines[iNew]))
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
60 opt[iOld][iNew] = opt[iOld+1][iNew+1] + 1;
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
61 else
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
62 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
63 }
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
64 }
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
65
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
66 int iOld = 0, iNew = 0;
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
67 while (iOld < nOld && iNew < nNew) {
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
68 if (oldLines[iOld].equals(newLines[iNew])) {
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
69 iOld++;
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
70 iNew++;
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
71 } else if (opt[iOld+1][iNew] >= opt[iOld][iNew+1]) {
1809
Franklin Schmidt <fschmidt@gmail.com>
parents: 1808
diff changeset
72 diffs.add( new Diff( DELETE, oldLines[iOld], iOld, iNew ) );
Franklin Schmidt <fschmidt@gmail.com>
parents: 1808
diff changeset
73 iOld++;
1807
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
74 } else {
1809
Franklin Schmidt <fschmidt@gmail.com>
parents: 1808
diff changeset
75 diffs.add( new Diff( INSERT, newLines[iNew], iOld, iNew ) );
Franklin Schmidt <fschmidt@gmail.com>
parents: 1808
diff changeset
76 iNew++;
1807
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 }
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
79
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
80 // dump out one remainder of one string if the other is exhausted
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
81 while( iOld < nOld ) {
1809
Franklin Schmidt <fschmidt@gmail.com>
parents: 1808
diff changeset
82 diffs.add( new Diff( DELETE, oldLines[iOld], iOld, iNew ) );
Franklin Schmidt <fschmidt@gmail.com>
parents: 1808
diff changeset
83 iOld++;
1807
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
84 }
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
85 while( iNew < nNew ) {
1809
Franklin Schmidt <fschmidt@gmail.com>
parents: 1808
diff changeset
86 diffs.add( new Diff( INSERT, newLines[iNew], iOld, iNew ) );
Franklin Schmidt <fschmidt@gmail.com>
parents: 1808
diff changeset
87 iNew++;
1807
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
88 }
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 return diffs;
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
91 }
ffa28e2155bb add line_diff
Franklin Schmidt <fschmidt@gmail.com>
parents:
diff changeset
92 }