Mercurial Hosting > luan
view src/goodjava/util/LineDiff.java @ 1832:d55c3eaf21d7 default tip
add jar
author | clarkton <ibraclarkton@gmail.com> |
---|---|
date | Wed, 11 Dec 2024 17:17:56 +0000 |
parents | 90187946d1a4 |
children |
line wrap: on
line source
package goodjava.util; import java.util.List; import java.util.ArrayList; import java.io.BufferedReader; import java.io.StringReader; import java.io.IOException; public final class LineDiff { public static final char DELETE = '<'; public static final char INSERT = '>'; public static class Diff { public final char operation; public final String text; public final int lineOld; public final int lineNew; private Diff(char operation,String line,int iOld,int iNew) { this.operation = operation; this.text = line; this.lineOld = iOld + 1; this.lineNew = iNew + 1; } } public static String[] stringToLines(String s) { List<String> list = new ArrayList<String>(); BufferedReader br = new BufferedReader(new StringReader(s)); String line; try { while( (line = br.readLine()) != null ) { list.add(line); } } catch(IOException e) { throw new RuntimeException(e); } return list.toArray(new String[list.size()]); } public static List<Diff> diff(String oldStr,String newStr) { return diff( stringToLines(oldStr), stringToLines(newStr) ); } // https://introcs.cs.princeton.edu/java/23recursion/Diff.java.html public static List<Diff> diff(String[] oldLines,String[] newLines) { List<Diff> diffs = new ArrayList<Diff>(); int nOld = oldLines.length; int nNew = newLines.length; // opt[iOld][iNew] = length of LCS of x[iOld..nOld] and y[iNew..nNew] int[][] opt = new int[nOld+1][nNew+1]; // compute length of LCS and all subproblems via dynamic programming for (int iOld = nOld-1; iOld >= 0; iOld--) { for (int iNew = nNew-1; iNew >= 0; iNew--) { if (oldLines[iOld].equals(newLines[iNew])) opt[iOld][iNew] = opt[iOld+1][iNew+1] + 1; else opt[iOld][iNew] = Math.max(opt[iOld+1][iNew], opt[iOld][iNew+1]); } } int iOld = 0, iNew = 0; while (iOld < nOld && iNew < nNew) { if (oldLines[iOld].equals(newLines[iNew])) { iOld++; iNew++; } else if (opt[iOld+1][iNew] >= opt[iOld][iNew+1]) { diffs.add( new Diff( DELETE, oldLines[iOld], iOld, iNew ) ); iOld++; } else { diffs.add( new Diff( INSERT, newLines[iNew], iOld, iNew ) ); iNew++; } } // dump out one remainder of one string if the other is exhausted while( iOld < nOld ) { diffs.add( new Diff( DELETE, oldLines[iOld], iOld, iNew ) ); iOld++; } while( iNew < nNew ) { diffs.add( new Diff( INSERT, newLines[iNew], iOld, iNew ) ); iNew++; } return diffs; } }