/**
 * This software is released as part of the Pumpernickel project.
 * 
 * All com.pump resources in the Pumpernickel project are distributed under the
 * MIT License:
 * https://github.com/mickleness/pumpernickel/raw/master/License.txt
 * 
 * More information about the Pumpernickel project is available here:
 * https://mickleness.github.io/pumpernickel/
 */
package com.pump.text;

import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.TreeSet;

/**
 * This object can diff two Strings together to find the minimal amount of
 * changes between the two.
 * <p>
 * Note this is only intended for small strings, and depending on the similarity
 * and length of the Strings: this can be very expensive. Because it is
 * expensive: this object caches all requested diffs for cheap retrieval. So
 * periodically you may want to replace your {@code TextDiff} object to avoid
 * store large sets of Strings and diffs in memory.
 * <p>
 * This class can best be described by examples, so let's consider how this
 * diffs the two strings: "antigravity" and "gravity field". The simplest result
 * this identifies is: "[anti]gravity{ field}". A visualization of this result
 * resembles:
 * <p>
 * <img src=
 * "data:image/png;base64, "
 * alt="[anti]gravity{ field}">
 * <p>
 * You can either follow the red arrows (branch A, using square brackets) to
 * create the first String, or you can follow the blue arrows (branch B, using
 * curly brackets) to create the second String.
 * <p>
 * Each of these columns is a different type of {@link TextDiff.DiffSegment}
 * object:
 * <ul>
 * <li>{@link TextDiff.SharedSegment}: clusters of letters that belong to both
 * of the Strings/branches. In the example above this is the middle column.</li>
 * <li>{@link TextDiff.SplitSegment}: clusters of letters that belong
 * exclusively to branch A or B. In the example above this is the leftmost and
 * rightmost column.</li>
 * </ul>
 * <p>
 * <p>
 * One of the reasons that calculating these diffs is so expensive is that there
 * may be several unusual ways to process this data. For example, this is
 * another solution to the example above: "[an]{gravi}t[igrav]{y f}i[ty]{eld}":
 * <p>
 * <img src=
 * "data:image/png;base64, "
 * alt="[an]{gravi}t[igrav]{y f}i[ty]{eld}">
 * <p>
 * There are actually 38 solutions for this example. There are 74 solutions for
 * diffing "agri department" against "agriculture dept". But in both cases:
 * there is exactly one solution that is considered the simplest, so other
 * solutions are discarded.
 * <p>
 * Each solution is represented as a single {@code DiffSegment} object. A
 * {@code DiffSegment} is actually a linked list, and you can traverse the
 * {@code next()} and {@code previous()} methods to walk the list from beginning
 * to end.
 */
public class TextDiff {

	/** A designation of which branch (A or B) you're interested in examining. */
	public static enum Branch {
		/**
		 * The first possible way to read a DiffSegment graph. This is denoted
		 * with square brackets.
		 */
		A,
		/**
		 * The second possible way to read a DiffSegment graph. This is denoted
		 * with curly brackets.
		 */
		B;

		/**
		 * Returns the opposite branch.
		 * 
		 * @return the opposite branch.
		 */
		public Branch opposite() {
			for (Branch b : Branch.values()) {
				if (b != this) {
					return b;
				}
			}
			throw new RuntimeException("Unexpected condition");
		}
	};

	/**
	 * This represents a segment of a diff solution.
	 * <p>
	 * This abstract class has two subclasses: the {@code SharedSegment} is a
	 * String that is shared between both branch A and B, and the {code
	 * SplitSegment} is two Strings that deviate depending on which branch
	 * you're following.
	 * <p>
	 * This is illustrated in the {@link TextDiff} javadoc with diagrams. Each
	 * column in those diagrams is a DiffSegment object.
	 * <p>
	 * This object is a node in a linked list. Originally you are given the head
	 * of the list as the complete solution, and you can call {@code next()} to
	 * traverse to the tail of this list.
	 * <p>
	 * If this is put into a sorted data structure, these segments are sorted by
	 * complexity (with the least complex graph sorted first).
	 */
	public abstract static class DiffSegment implements Comparable<DiffSegment> {

		protected DiffSegment next;
		protected DiffSegment prev;
		protected int complexity = -1;

		/**
		 * Return the next node in this list, or null if this is the tail node.
		 * 
		 * @return the next node in this list, or null if this is the tail node.
		 */
		public DiffSegment next() {
			return next;
		}

		/**
		 * Return the previous node in this list, or null if this is the head
		 * node.
		 * 
		 * @return the previous node in this list, or null if this is the head
		 *         node.
		 */
		public DiffSegment previous() {
			return prev;
		}

		/**
		 * Return the sum of the length of all {@code SharedSegments}.
		 * 
		 * @return the sum of the length of all {@code SharedSegments}.
		 */
		public int getSharedCharCount() {
			int sum = 0;
			DiffSegment t = this;
			while (t != null) {
				if (t instanceof SharedSegment) {
					sum += ((SharedSegment) t).text.length();
				}
				t = t.next;
			}
			return sum;
		}

		/**
		 * Return -1 if this graph is less complex than the argument.
		 * 
		 * @return -1 if this graph is less complex than the argument.
		 */
		@Override
		public int compareTo(DiffSegment o) {
			int myComplexity = getComplexity();
			int otherComplexity = o.getComplexity();
			if (myComplexity < otherComplexity) {
				return -1;
			} else if (myComplexity > otherComplexity) {
				return 1;
			}
			// it doesn't matter what we do here, as long as its
			// consistent. My first draft just used:
			// toString().compareTo(o.toString())
			// this worked, but was several times slower than the
			// approach below that helps cut the comparison short
			// much sooner.
			int type1 = this instanceof SharedSegment ? 1 : 0;
			int type2 = o instanceof SharedSegment ? 1 : 0;
			if (type1 == 1 && type2 == 0) {
				return -1;
			} else if (type1 == 0 && type2 == 1) {
				return 1;
			} else if (type1 == 1 && type2 == 1) {
				SharedSegment s1 = (SharedSegment) this;
				SharedSegment s2 = (SharedSegment) o;
				int k = s1.text.compareTo(s2.text);
				if (k != 0) {
					return k;
				}
			} else if (type1 == 0 && type2 == 0) {
				SplitSegment s1 = (SplitSegment) this;
				SplitSegment s2 = (SplitSegment) o;
				int k = s1.textA.compareTo(s2.textA);
				if (k != 0) {
					return k;
				}
				k = s1.textB.compareTo(s2.textB);
				if (k != 0) {
					return k;
				}
			}

			if (next == null && o.next == null) {
				return 0;
			} else if (next == null) {
				return -1;
			} else if (o.next == null) {
				return 1;
			} else {
				return next.compareTo(o.next);
			}
		}

		/**
		 * Clone this node and all its subsequent nodes.
		 */
		public DiffSegment clone() {
			return clone(false);
		}

		/**
		 * Clone this node and all its subsequent nodes.
		 * 
		 * @param swapBranches
		 *            if true then branch A and B should swap as we clone this
		 *            node.
		 */
		public abstract DiffSegment clone(boolean swapBranches);

		/**
		 * Return the text of this node.
		 * 
		 * @param branch
		 *            the branch of this node to consider. For a
		 *            {@code SharedSegment} this argument is ignored, but for a
		 *            {@code SplitSegment} this argument controls which String
		 *            is returned.
		 * @param appendSubsequentNodes
		 *            if true then this appends all subsequent nodes. This is
		 *            useful if just want the whole String of a branch. If you
		 *            need to study individual pieces more carefully then you
		 *            may want to pass false here.
		 * @return the text of this node. This returns the raw text with no
		 *         quotations or square/curly brackets.
		 */
		public abstract String getText(Branch branch,
				boolean appendSubsequentNodes);

		/**
		 * Return the tail of this linked list.
		 * 
		 * @return the tail of this linked list.
		 */
		public DiffSegment getTail() {
			DiffSegment t = this;
			while (t.next != null) {
				t = t.next;
			}
			return t;
		}

		/**
		 * Clone this node and append one character to both branches.
		 * 
		 * @param ch
		 *            the character to append.
		 * @return the new node that represents this node + the argument.
		 */
		public DiffSegment append(char ch) {
			DiffSegment clone = clone();
			DiffSegment tail = clone.getTail();
			if (tail instanceof SharedSegment) {
				SharedSegment oldTail = (SharedSegment) tail;
				SharedSegment newTail = new SharedSegment(oldTail.text + ch);

				DiffSegment nextToLast = oldTail.prev;
				if (nextToLast != null) {
					nextToLast.next = newTail;
					newTail.prev = nextToLast;
				} else {
					clone = newTail;
				}
			} else {
				SharedSegment newTail = new SharedSegment(ch);
				tail.next = newTail;
				newTail.prev = tail.next;
			}
			return clone;
		}

		/**
		 * Clone this node and append the two Strings provided to each
		 * respective branch.
		 * <p>
		 * Warning: some splits are considered "unnecessary", and are rejected.
		 * When an unnecessary split is detected this method returns null. For
		 * example the diff "[h]{h}ello" is rejected, because when the first
		 * characters of a split are the same: we have a redundant/unnecessary
		 * split.
		 * 
		 * @param strA
		 *            the String to append to branch A.
		 * @param strB
		 *            the String to append to branch B.
		 * @return the new node that represents this node + the arguments or
		 *         null if this split is not allowed.
		 */
		public DiffSegment append(String strA, String strB) {
			identifyRedundantOp: {
				DiffSegment origTail = getTail();
				if (origTail instanceof SplitSegment) {
					SplitSegment tail = (SplitSegment) origTail;
					char chA, chB;
					if (tail.textA.length() == 0 && strA.length() > 0) {
						chA = strA.charAt(0);
					} else if (tail.textA.length() > 0) {
						chA = tail.textA.charAt(0);
					} else {
						break identifyRedundantOp;
					}
					if (tail.textB.length() == 0 && strB.length() > 0) {
						chB = strB.charAt(0);
					} else if (tail.textB.length() > 0) {
						chB = tail.textB.charAt(0);
					} else {
						break identifyRedundantOp;
					}
					if (chA == chB) {
						return null;
					}
				}
			}

			DiffSegment clone = clone();
			DiffSegment tail = clone.getTail();
			if (tail instanceof SplitSegment) {
				SplitSegment oldTail = (SplitSegment) tail;
				SplitSegment newTail = new SplitSegment(oldTail.textA + strA,
						oldTail.textB + strB);

				DiffSegment nextToLast = oldTail.prev;
				if (nextToLast != null) {
					nextToLast.next = newTail;
					newTail.prev = nextToLast;
				} else {
					clone = newTail;
				}
			} else {
				SplitSegment newTail = new SplitSegment(strA, strB);
				tail.next = newTail;
				newTail.prev = tail.next;
			}
			return clone;
		}

		/**
		 * Return the complexity of this segment. Lower values are considered
		 * simpler and therefore "better" when pruning solutions.
		 * 
		 * @return the complexity of this segment.
		 */
		public int getComplexity() {
			if (complexity == -1) {
				complexity = calculateComplexity();
			}
			return complexity;
		}

		protected abstract int calculateComplexity();

		/**
		 * Return true if branch x is a subset of the opposite branch.
		 * <p>
		 * For example if string A is "underwater" and string B is "water", then
		 * the diff of these will be "[under]water". So calling
		 * {@code myDiff.isSubset(Branch.B)} will return true, because the B
		 * branch ("water") is a subset of the A branch ("underwater").
		 * <p>
		 * However if string A is "underwater" and string B is "watered", then
		 * the diff will be "[under]water{ed}". Here calling
		 * {@code isSubset(..)} for either branch returns false, because neither
		 * is a subset of the other.
		 * <p>
		 * The examples above are trivial because they cluster all the words
		 * together, but the utility of this method has to do with
		 * abbreviations. For example given the strings "association" and
		 * "assn": the second branch is considered a subset of the first, even
		 * though the diff resembles "ass[ociatio]n".
		 * <p>
		 * As a word of caution: this is helpful at identifying abbreviations,
		 * but it can also be misleading. For example "ne" is a subset of
		 * "northeast" (as expected), but "ne" is <i>also</i> a subset of
		 * "northwest". Similarly "intl" is a subset of "international", but it
		 * is also a subset of "intelligence". And "cm" is a subset of
		 * "centimeter", but it also a subset of "camp".
		 * 
		 * @param x
		 *            the branch that might be a subset of the opposite branch.
		 * @return true if the argument branch is a subset of the opposite
		 *         branch.
		 */
		public boolean isSubset(Branch x) {
			DiffSegment t = this;
			int droppedCharCount = 0;
			while (t != null) {
				if (t instanceof SplitSegment) {
					SplitSegment s = (SplitSegment) t;
					String text = s.getText(x, false);
					if (text.equals("")) {
						droppedCharCount += s.getText(x.opposite(), false)
								.length();
					} else {
						return false;
					}
				}
				t = t.next;
			}
			return droppedCharCount > 0;
		}

		/**
		 * Return true if this graph contains a split where one of the words is
		 * in the argument provided.
		 * 
		 * @param values
		 *            a collection of Strings to check against.
		 * @return true if this graph contains a split that contains text from
		 *         the argument.
		 */
		public boolean containsSplit(Collection<String> values) {
			DiffSegment t = this;
			while (t != null) {
				if (t instanceof SplitSegment) {
					SplitSegment s = (SplitSegment) t;
					if (values.contains(s.textA) || values.contains(s.textB)) {
						return true;
					}
				}
				t = t.next;
			}
			return false;
		}
	}

	/** This segment represents the same text for both branches. */
	public static class SharedSegment extends DiffSegment {

		/** The text this segment represents. */
		public final String text;

		private SharedSegment(char ch) {
			this(Character.toString(ch));
		}

		@Override
		public int hashCode() {
			return text.hashCode();
		}

		@Override
		protected int calculateComplexity() {
			int c = text.length();
			if (next != null) {
				c += next.getComplexity();
			}
			return c;
		}

		@Override
		public boolean equals(Object obj) {
			if (!(obj instanceof SharedSegment)) {
				return false;
			}
			SharedSegment other = (SharedSegment) obj;
			if (!text.equals(other.text)) {
				return false;
			} else if (next != null && other.next != null) {
				return next.equals(other.next);
			} else if (next != null || other.next != null) {
				return false;
			}
			return true;
		}

		private SharedSegment(String text) {
			if (text == null)
				throw new NullPointerException();
			this.text = text;
		}

		@Override
		public String getText(Branch branch, boolean appendSubsequentNodes) {
			String returnValue = text;
			if (appendSubsequentNodes && next != null) {
				returnValue += next.getText(branch, appendSubsequentNodes);
			}
			return returnValue;
		}

		@Override
		public String toString() {
			String returnValue = text;
			if (next != null) {
				returnValue += next.toString();
			}
			return returnValue;
		}

		@Override
		public SharedSegment clone(boolean swapBranches) {
			SharedSegment clone = new SharedSegment(text);
			if (next != null) {
				clone.next = next.clone(swapBranches);
				clone.next.prev = clone;
			}
			return clone;
		}
	}

	/**
	 * This segment represents two unique Strings depending on whether you're
	 * reading branch A or B.
	 */
	public static class SplitSegment extends DiffSegment {

		/** The text that should be applied to branch A. */
		public final String textA;

		/** The text that should be applied to branch B. */
		public final String textB;

		private SplitSegment(String textA, String textB) {
			if (textA == null)
				throw new NullPointerException();
			if (textB == null)
				throw new NullPointerException();
			if (textA.length() == 0 && textB.length() == 0)
				throw new IllegalArgumentException(
						"At least one branch must have text.");
			this.textA = textA;
			this.textB = textB;

		}

		@Override
		protected int calculateComplexity() {
			int c = textA.length() + textB.length() + 1;
			if (next != null) {
				c += next.getComplexity();
			}
			return c;
		}

		@Override
		public int hashCode() {
			return textA.hashCode() ^ textB.hashCode();
		}

		@Override
		public boolean equals(Object obj) {
			if (!(obj instanceof SplitSegment)) {
				return false;
			}
			SplitSegment other = (SplitSegment) obj;
			if (!textA.equals(other.textA)) {
				return false;
			} else if (!textB.equals(other.textB)) {
				return false;
			} else if (next != null && other.next != null) {
				return next.equals(other.next);
			} else if (next != null || other.next != null) {
				return false;
			}
			return true;
		}

		@Override
		public SplitSegment clone(boolean swapBranches) {
			SplitSegment clone;
			if (swapBranches) {
				clone = new SplitSegment(textB, textA);
			} else {
				clone = new SplitSegment(textA, textB);
			}
			if (next != null) {
				clone.next = next.clone(swapBranches);
				clone.next.prev = clone;
			}
			return clone;
		}

		@Override
		public String getText(Branch branch, boolean appendSubsequentNodes) {
			if (branch == null)
				throw new NullPointerException();

			String returnValue;
			if (branch == Branch.A) {
				returnValue = textA;
			} else {
				returnValue = textB;
			}
			if (appendSubsequentNodes && next != null) {
				returnValue += next.getText(branch, appendSubsequentNodes);
			}
			return returnValue;
		}

		@Override
		public String toString() {
			String returnValue;
			if (textA.length() == 0 && textB.length() == 0) {
				// weird, but let's not make a stink here
				returnValue = "";
			} else if (textA.length() == 0) {
				returnValue = "{" + textB + "}";
			} else if (textB.length() == 0) {
				returnValue = "[" + textA + "]";
			} else {
				returnValue = "[" + textA + "]{" + textB + "}";
			}
			if (next != null) {
				returnValue += next.toString();
			}
			return returnValue;
		}
	}

	static class Key {
		final String strA, strB;
		final boolean includeAllSolutions;

		Key(String strA, String strB, boolean includeAllSolutions) {
			this.strA = strA;
			this.strB = strB;
			this.includeAllSolutions = includeAllSolutions;
		}

		@Override
		public int hashCode() {
			return strA.hashCode() + strB.hashCode()
					+ (includeAllSolutions ? 1 : 0);
		}

		@Override
		public boolean equals(Object obj) {
			if (!(obj instanceof Key)) {
				return false;
			}
			Key other = (Key) obj;
			return strA.equals(other.strA) && strB.equals(other.strB)
					&& includeAllSolutions == other.includeAllSolutions;
		}

		@Override
		public String toString() {
			return "\"" + strA + "\" \"" + strB + "\" includeAllSolutions="
					+ includeAllSolutions;
		}
	}

	protected Map<Key, Collection<DiffSegment>> cachedResults = new HashMap<>();

	public TextDiff() {
	}

	/**
	 * Return the simplest graphs explaining the diff between strA and strB.
	 * <p>
	 * If this query is already cached, then that cached value is immediately
	 * returned. Otherwise this method calculates the diff and caches the
	 * results in this object for future retrieval.
	 * 
	 * @param strA
	 *            the first String/branch to compare.
	 * @param strB
	 *            the second String/branch to compare.
	 * @return the simplest graphs explaining the diff between strA and strB.
	 */
	public DiffSegment[] getSolutions(String strA, String strB) {
		return getSolutions(strA, strB, false);
	}

	/**
	 * Return the graphs explaining the diff between strA and strB.
	 * <p>
	 * If this query is already cached, then that cached value is immediately
	 * returned. Otherwise this method calculates the diff and caches the
	 * results in this object for future retrieval.
	 * 
	 * @param strA
	 *            the first String/branch to compare.
	 * @param strB
	 *            the second String/branch to compare.
	 * @param includeAllSolutions
	 *            if true then this includes ALL solutions, including overly
	 *            complex solutions. If false (which is recommended) then this
	 *            method only includes the simplest solutions. If all solutions
	 *            are included: this query can be several times slower.
	 * @return the graphs explaining the diff between strA and strB.
	 */
	public DiffSegment[] getSolutions(String strA, String strB,
			boolean includeAllSolutions) {
		boolean reverse = strA.compareTo(strB) > 0;
		String tA, tB;
		if (reverse) {
			tA = strB;
			tB = strA;
		} else {
			tA = strA;
			tB = strB;
		}
		Key key = new Key(tA, tB, includeAllSolutions);
		Collection<DiffSegment> solutions = cachedResults.get(key);
		if (solutions == null) {
			solutions = includeAllSolutions ? new TreeSet<DiffSegment>()
					: new HashSet<DiffSegment>();
			calculateSolutions(solutions, null, key, 0, 0, new Complexity());
			cachedResults.put(key, solutions);
		}

		DiffSegment[] returnValue = new DiffSegment[solutions.size()];
		if (reverse) {
			int a = 0;
			for (DiffSegment s : solutions) {
				returnValue[a] = s.clone(true);
				a++;
			}
		} else {
			solutions.toArray(returnValue);
		}
		return returnValue;
	}

	/**
	 * Return one of the simplest graphs explaining the diff between strA and
	 * strB.
	 * <p>
	 * If this query is already cached, then that cached value is immediately
	 * returned. Otherwise this method calculates the diff and caches the
	 * results in this object for future retrieval.
	 * 
	 * @param strA
	 *            the first String/branch to compare.
	 * @param strB
	 *            the second String/branch to compare.
	 * @return one of the simplest graphs explaining the diff between strA and
	 *         strB.
	 */
	public DiffSegment getSolution(String strA, String strB) {
		boolean reverse = strA.compareTo(strB) > 0;
		String tA, tB;
		if (reverse) {
			tA = strB;
			tB = strA;
		} else {
			tA = strA;
			tB = strB;
		}
		Key key = new Key(tA, tB, false);
		Collection<DiffSegment> solutions = cachedResults.get(key);
		if (solutions == null) {
			solutions = new HashSet<>();
			calculateSolutions(solutions, null, key, 0, 0, new Complexity());
			cachedResults.put(key, solutions);
		}

		DiffSegment returnValue = solutions.iterator().next();
		if (reverse) {
			returnValue = returnValue.clone(true);
		}

		return returnValue;
	}

	/**
	 * This is a trivial wrapper for an int value representing the minimum
	 * complexity of a query.
	 */
	private static class Complexity {
		public int value = Integer.MAX_VALUE;
	}

	/**
	 * This searches for ways to diff strA and strB, and when a solution is
	 * found this calls
	 * {@link #processSolution(Collection,DiffSegment,Key,Complexity)}.
	 * 
	 * @param results
	 *            the object to store results in
	 * @param path
	 *            the base (starting) path to append data to.
	 * @param key
	 *            the key (which includes strA and strB) that describes this
	 *            query.
	 * @param indexA
	 *            the index of strA to begin reading.
	 * @param indexB
	 *            the index of strB to begin reading.
	 * @param minComplexity
	 *            a wrapper for the minimum complexity detected during this
	 *            scan. If we don't have to return all solutions then as branch
	 *            attempts pass this complexity they immediately abort.
	 */
	private void calculateSolutions(Collection<DiffSegment> results,
			DiffSegment path, Key key, int indexA, int indexB,
			Complexity minComplexity) {

		if ((!key.includeAllSolutions) && path != null
				&& path.getComplexity() > minComplexity.value)
			return;

		if (key.strA.length() - indexA == 0 && key.strB.length() - indexB == 0) {
			processSolution(results, path, key, minComplexity);
		} else if (key.strA.length() - indexA == 0
				|| key.strB.length() - indexB == 0) {
			String remainingA = key.strA.subSequence(indexA, key.strA.length())
					.toString();
			String remainingB = key.strB.subSequence(indexB, key.strB.length())
					.toString();
			if (path == null) {
				processSolution(results, new SplitSegment(remainingA,
						remainingB), key, minComplexity);
			} else {
				DiffSegment copy = path.append(remainingA, remainingB);
				if (copy != null)
					processSolution(results, copy, key, minComplexity);
			}
		} else {
			char ch1 = key.strA.charAt(indexA);
			char ch2 = key.strB.charAt(indexB);
			// great! create a special branch with this shared character:
			if (ch1 == ch2) {
				DiffSegment newPath;
				if (path == null) {
					newPath = new SharedSegment(ch1);
				} else {
					newPath = path.append(ch1);
				}

				calculateSolutions(results, newPath, key, indexA + 1,
						indexB + 1, minComplexity);
			}

			// take ch1 and create a special branch:
			{
				DiffSegment newPath;
				if (path == null) {
					newPath = new SplitSegment(Character.toString(ch1), "");
				} else {
					newPath = path.append(Character.toString(ch1), "");
				}
				if (newPath != null) {
					calculateSolutions(results, newPath, key, indexA + 1,
							indexB, minComplexity);
				}
			}

			// take ch2 and create a special branch:
			{
				DiffSegment newPath;
				if (path == null) {
					newPath = new SplitSegment("", Character.toString(ch2));
				} else {
					newPath = path.append("", Character.toString(ch2));
				}
				if (newPath != null) {
					calculateSolutions(results, newPath, key, indexA,
							indexB + 1, minComplexity);
				}
			}
		}
	}

	/**
	 * This chooses to record the results in the collection provided or discard
	 * it.
	 * <p>
	 * If includeAllSolutions is true, then this solution is always recorded.
	 * Otherwise this solution is only recorded if the complexity is the lowest
	 * complexity yet detected.
	 * 
	 * @param results
	 *            the collection to store the solution in if this method decides
	 *            to keep it.
	 * @param solution
	 *            the new solution to process.
	 * @param key
	 *            the key describing the query being made.
	 */
	protected void processSolution(Collection<DiffSegment> results,
			DiffSegment solution, Key key, Complexity minComplexity) {
		boolean isValid = true;
		DiffSegment tail = solution.getTail();
		if (tail instanceof SplitSegment) {
			SplitSegment tailSplit = (SplitSegment) tail;

			if (tailSplit.textA.length() > 0 && tailSplit.textB.length() > 0) {
				char chA = tailSplit.textA.charAt(tailSplit.textA.length() - 1);
				char chB = tailSplit.textB.charAt(tailSplit.textB.length() - 1);
				if (chA == chB) {
					isValid = false;
				}
			}
		}
		if (!isValid)
			return;

		int complexity = solution.getComplexity();
		if (key.includeAllSolutions) {
			results.add(solution);
		} else {
			if ((!key.includeAllSolutions) && complexity < minComplexity.value) {
				results.clear();
				minComplexity.value = complexity;
			}
			if (complexity == minComplexity.value) {
				results.add(solution);
			}
		}
	}

	/**
	 * Return true if the smaller phrase is a subset of the bigger phrase. For
	 * example "cm" is a subset of "centimeter" and "camp".
	 * 
	 * @param smallerPhrase
	 *            the smaller of the two phrases (the one that might be an
	 *            abbreviation)
	 * @param biggerPhrase
	 *            the larger of the two phrases
	 * @return the first solution that diffs these two phrases with the first as
	 *         a subset as the second.
	 */
	public DiffSegment getSubset(String smallerPhrase, String biggerPhrase) {
		DiffSegment[] array = getSolutions(smallerPhrase, biggerPhrase);
		for (DiffSegment s : array) {
			if (s.isSubset(Branch.A))
				return s;
		}
		return null;
	}
}