changeset 1807:ffa28e2155bb

add line_diff
author Franklin Schmidt <fschmidt@gmail.com>
date Sun, 12 May 2024 15:25:29 -0600
parents 3b7a8f1cc887
children 69623c62aa34
files src/goodjava/util/LineDiff.java src/luan/modules/String.luan src/luan/modules/StringLuan.java
diffstat 3 files changed, 102 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
diff -r 3b7a8f1cc887 -r ffa28e2155bb src/goodjava/util/LineDiff.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/goodjava/util/LineDiff.java	Sun May 12 15:25:29 2024 -0600
@@ -0,0 +1,90 @@
+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 int line;
+		public final String text;
+
+		private Diff(char operation,int line,String text) {
+			this.operation = operation;
+			this.line = line;
+			this.text = text;
+		}
+	}
+
+	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, iOld+1, oldLines[iOld] ) );
+				iOld++;
+			} else {
+ 				diffs.add( new Diff( INSERT, iOld+1, newLines[iNew] ) );
+				iNew++;
+			}
+		}
+
+		// dump out one remainder of one string if the other is exhausted
+		while( iOld < nOld ) {
+			diffs.add( new Diff( DELETE, iOld+1, oldLines[iOld] ) );
+			iOld++;
+		}
+		while( iNew < nNew ) {
+			diffs.add( new Diff( INSERT, nOld+1, newLines[iNew] ) );
+			iNew++;
+		}
+
+		return diffs;
+	}
+}
diff -r 3b7a8f1cc887 -r ffa28e2155bb src/luan/modules/String.luan
--- a/src/luan/modules/String.luan	Thu May 09 20:39:53 2024 -0600
+++ b/src/luan/modules/String.luan	Sun May 12 15:25:29 2024 -0600
@@ -12,6 +12,7 @@
 String.ends_with = StringLuan.ends_with
 String.find = StringLuan.find
 String.format = StringLuan.format
+String.line_diff = StringLuan.line_diff
 String.lower = StringLuan.lower
 String.regex = Boot.regex
 String.regex_quote = Pattern.quote
diff -r 3b7a8f1cc887 -r ffa28e2155bb src/luan/modules/StringLuan.java
--- a/src/luan/modules/StringLuan.java	Thu May 09 20:39:53 2024 -0600
+++ b/src/luan/modules/StringLuan.java	Sun May 12 15:25:29 2024 -0600
@@ -2,7 +2,9 @@
 
 import java.security.NoSuchAlgorithmException;
 import java.util.Arrays;
+import java.util.List;
 import goodjava.util.GoodUtils;
+import goodjava.util.LineDiff;
 import luan.Luan;
 import luan.LuanTable;
 import luan.LuanFunction;
@@ -156,4 +158,13 @@
 		return GoodUtils.replace(s,target,replacement);
 	}
 
+	public static String line_diff(String oldStr,String newStr) {
+		List<LineDiff.Diff> diffs = LineDiff.diff(oldStr,newStr);
+		StringBuilder sb = new StringBuilder();
+		for( LineDiff.Diff diff : diffs ) {
+			sb.append(diff.operation).append(' ').append(diff.line).append(" - ").append(diff.text).append('\n');
+		}
+		return sb.toString();
+	}
+
 }