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;
	}
}