package jp.ac.osaka_u.ist.sel.t_kanda.tkdiff;

import gnu.trove.iterator.TIntIterator;
import gnu.trove.list.TIntList;
import gnu.trove.list.array.TIntArrayList;
import gnu.trove.map.TIntIntMap;
import gnu.trove.map.TIntObjectMap;
import gnu.trove.map.hash.THashMap;
import gnu.trove.map.hash.TIntIntHashMap;
import gnu.trove.map.hash.TIntObjectHashMap;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;

/**
 * Compares two lists, returning a list of the additions, changes, and deletions
 * between them. A <code>Comparator</code> may be passed as an argument to the
 * constructor, and will thus be used. If not provided, the initial value in the
 * <code>a</code> ("from") list will be looked at to see if it supports the
 * <code>Comparable</code> interface. If so, its <code>equals</code> and
 * <code>compareTo</code> methods will be invoked on the instances in the "from"
 * and "to" lists; otherwise, for speed, hash codes from the objects will be
 * used instead for comparison.
 * 
 * <p>
 * The file FileDiff.java shows an example usage of this class, in an
 * application similar to the Unix "diff" program.
 * </p>
 */
public class JavaDiff {
	/**
	 * The source list, AKA the "from" values.
	 */
	protected List<String> a;

	/**
	 * The target list, AKA the "to" values.
	 */
	protected List<String> b;

	/**
	 * The list of differences, as <code>Difference</code> instances.
	 */
	protected List<Difference> diffs = new ArrayList<Difference>();

	/**
	 * The pending, uncommitted difference.
	 */
	private Difference pending;

	/**
	 * The thresholds.
	 */
	private Thresh thresh;

	/**
	 * Constructs the Diff object for the two lists, using the given comparator.
	 */
	public JavaDiff(List<String> a, List<String> b) {
		this.a = a;
		this.b = b;
		this.thresh = null;
	}

	/**
	 * Runs diff and returns the results.
	 */
	public List<Difference> diff() {
		traverseSequences();

		// add the last difference, if pending:
		if (pending != null) {
			diffs.add(pending);
		}

		return diffs;
	}

	/**
	 * Traverses the sequences, seeking the longest common subsequences,
	 * invoking the methods <code>finishedA</code>, <code>finishedB</code>,
	 * <code>onANotB</code>, and <code>onBNotA</code>.
	 */
	protected void traverseSequences() {
		Matches matches = getLongestCommonSubsequences();

		int lastA = a.size() - 1;
		int lastB = b.size() - 1;
		int bi = 0;
		int ai;

		int lastMatch = matches.lastMatch;

		for (ai = 0; ai <= lastMatch; ++ai) {
			
			if (!matches.matches.containsKey(ai)) {
				onANotB(ai, bi);
			} else {
				int bLine = matches.matches.get(ai);
				while (bi < bLine) {
					onBNotA(ai, bi++);
				}

				onMatch(ai, bi++);
			}
		}

		boolean calledFinishA = false;
		boolean calledFinishB = false;

		while (ai <= lastA || bi <= lastB) {

			// last A?
			if (ai == lastA + 1 && bi <= lastB) {
				if (!calledFinishA && callFinishedA()) {
					finishedA(lastA);
					calledFinishA = true;
				} else {
					while (bi <= lastB) {
						onBNotA(ai, bi++);
					}
				}
			}

			// last B?
			if (bi == lastB + 1 && ai <= lastA) {
				if (!calledFinishB && callFinishedB()) {
					finishedB(lastB);
					calledFinishB = true;
				} else {
					while (ai <= lastA) {
						onANotB(ai++, bi);
					}
				}
			}

			if (ai <= lastA) {
				onANotB(ai++, bi);
			}

			if (bi <= lastB) {
				onBNotA(ai, bi++);
			}
		}
	}

	/**
	 * Override and return true in order to have <code>finishedA</code> invoked
	 * at the last element in the <code>a</code> array.
	 */
	protected boolean callFinishedA() {
		return false;
	}

	/**
	 * Override and return true in order to have <code>finishedB</code> invoked
	 * at the last element in the <code>b</code> array.
	 */
	protected boolean callFinishedB() {
		return false;
	}

	/**
	 * Invoked at the last element in <code>a</code>, if
	 * <code>callFinishedA</code> returns true.
	 */
	protected void finishedA(int lastA) {
	}

	/**
	 * Invoked at the last element in <code>b</code>, if
	 * <code>callFinishedB</code> returns true.
	 */
	protected void finishedB(int lastB) {
	}

	/**
	 * Invoked for elements in <code>a</code> and not in <code>b</code>.
	 */
	protected void onANotB(int ai, int bi) {
		if (pending == null) {
			pending = new Difference(ai, ai, bi, -1);
		} else {
			pending.setDeleted(ai);
		}
	}

	/**
	 * Invoked for elements in <code>b</code> and not in <code>a</code>.
	 */
	protected void onBNotA(int ai, int bi) {
		if (pending == null) {
			pending = new Difference(ai, -1, bi, bi);
		} else {
			pending.setAdded(bi);
		}
	}

	/**
	 * Invoked for elements matching in <code>a</code> and <code>b</code>.
	 */
	protected void onMatch(int ai, int bi) {
		if (pending == null) {
			// no current pending
		} else {
			diffs.add(pending);
			pending = null;
		}
	}

	/**
	 * Compares the two objects, using the comparator provided with the
	 * constructor, if any.
	 */
	protected boolean equals(String x, String y) {
		return x.equals(y);
	}

	/**
	 * Returns an array of the longest common subsequences.
	 */
	public Matches getLongestCommonSubsequences() {
		int aStart = 0;
		int aEnd = a.size() - 1;

		int bStart = 0;
		int bEnd = b.size() - 1;

		Matches matches = new Matches();

		while (aStart <= aEnd && bStart <= bEnd && equals(a.get(aStart), b.get(bStart))) {
			matches.put(aStart++, bStart++);
		}

		while (aStart <= aEnd && bStart <= bEnd && equals(a.get(aEnd), b.get(bEnd))) {
			matches.put(aEnd--, bEnd--);
		}

		Map<String, TIntList> bMatches = new THashMap<>();

		for (int bi = bStart; bi <= bEnd; ++bi) {
			String element = b.get(bi);
			String key = element;
			TIntList positions = bMatches.get(key);

			if (positions == null) {
				positions = new TIntArrayList();
				bMatches.put(key, positions);
			}

			positions.insert(0, bi);
		}

		thresh = new Thresh();
		TIntObjectMap<DLink> links = new TIntObjectHashMap<>();

		for (int i = aStart; i <= aEnd; ++i) {
			String aElement = a.get(i);
			TIntList positions = bMatches.get(aElement);

			if (positions != null) {
				int k = 0;
				TIntIterator pit = positions.iterator();
				while (pit.hasNext()) {
					int j = pit.next();

					k = insert(j, k);

					if (k == Integer.MIN_VALUE) {
						// nothing
					} else {
						DLink value = k > 0 ? links.get(k - 1) : null;
						links.put(k, new DLink(value, i, j));
					}
				}
			}
		}

		if (thresh.tresh.size() > 0) {
			int ti = thresh.lastKey;
			DLink link = links.get(ti);
			while (link != null) {
				int x = link.l1;
				int y = link.l2;
				matches.put(x, y);
				link = link.d;
			}
		}

		return matches;
	}
	
	private class DLink{
		private DLink d;
		private int l1,l2;
		public DLink(DLink d, int i, int j){
			this.d = d;
			this.l1 = i;
			this.l2 = j;
		}
	}
	
	private class Matches{
		private TIntIntMap matches;
		private int lastMatch = 0;
		public Matches(){
			matches = new TIntIntHashMap();
		}
		public void put(int i, int j) {
			matches.put(i, j);
			lastMatch = Math.max(i, lastMatch);
		}
	}

	/**
	 * Returns whether the value in the map for the given index is greater than
	 * the given value.
	 */
	protected boolean isGreaterThan(int index, int val) {
		int lhs = thresh.get(index);
		return /*lhs != Integer.MIN_VALUE &&*/  val < lhs;
	}

	/**
	 * Returns whether the value in the map for the given index is less than the
	 * given value.
	 */
	protected boolean isLessThan(int index, int val) {
		int lhs = thresh.get(index);
		return lhs >= 0 && val > lhs;
	}

	/**
	 * Adds the given value to the "end" of the threshold map, that is, with the
	 * greatest index/key.
	 */
	protected void append(int value) {
		int addIdx;
		if (thresh.tresh.size() == 0) {
			addIdx = 0;
		} else {
			addIdx = thresh.lastKey + 1;
		}
		thresh.put(addIdx, value);
	}

	/**
	 * Inserts the given values into the threshold map.
	 */
	protected int insert(int j, int k) {
		if (k > 0 && isGreaterThan(k, j) && isLessThan(k - 1, j)) {
			thresh.put(k, j);
		} else {
			int high = -1;

			if (k > 0) {
				high = k;
			} else if (thresh.tresh.size() > 0) {
				high = thresh.lastKey;
			}

			// off the end?
			if (high == -1 || j > thresh.get(thresh.lastKey)) {
				append(j);
				k = high + 1;
			} else {
				// binary search for insertion point:
				int low = 0;

				while (low <= high) {
					int index = (high + low) / 2;
					int val = thresh.get(index);
					int cmp = Integer.compare(j,val);

					if (cmp == 0) {
						return Integer.MIN_VALUE;
					} else if (cmp > 0) {
						low = index + 1;
					} else {
						high = index - 1;
					}
				}

				thresh.put(low, j);
				k = low;
			}
		}

		return k;
	}
	
	private class Thresh{
		private TIntIntMap tresh;
		private int lastKey = Integer.MIN_VALUE;
		public Thresh(){
			tresh = new TIntIntHashMap();
		}
		public int get(int index) {
			return tresh.containsKey(index) ? tresh.get(index) : Integer.MIN_VALUE;
		}

		public int put(int key,int value) {
			lastKey = Math.max(key, lastKey);
			return tresh.put(key, value);
		}
	}
}
