Mercurial Hosting > luan

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

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add line_diff
author Franklin Schmidt <fschmidt@gmail.com>
date Sun, 12 May 2024 15:25:29 -0600
parents
children 69623c62aa34
comparison
equal deleted inserted replaced
1806:3b7a8f1cc887 1807:ffa28e2155bb
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
19 private Diff(char operation,int line,String text) {
20 this.operation = operation;
21 this.line = line;
22 this.text = text;
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]) {
70 diffs.add( new Diff( DELETE, iOld+1, oldLines[iOld] ) );
71 iOld++;
72 } else {
73 diffs.add( new Diff( INSERT, iOld+1, newLines[iNew] ) );
74 iNew++;
75 }
76 }
77
78 // dump out one remainder of one string if the other is exhausted
79 while( iOld < nOld ) {
80 diffs.add( new Diff( DELETE, iOld+1, oldLines[iOld] ) );
81 iOld++;
82 }
83 while( iNew < nNew ) {
84 diffs.add( new Diff( INSERT, nOld+1, newLines[iNew] ) );
85 iNew++;
86 }
87
88 return diffs;
89 }
90 }