1 files changed, 460 insertions, 0 deletions
diff --git a/bundles/org.eclipse.compare/compare/org/eclipse/compare/rangedifferencer/RangeDifferencer.java b/bundles/org.eclipse.compare/compare/org/eclipse/compare/rangedifferencer/RangeDifferencer.java
new file mode 100644
index 000000000..9056493f6
--- /dev/null
+++ b/bundles/org.eclipse.compare/compare/org/eclipse/compare/rangedifferencer/RangeDifferencer.java
@@ -0,0 +1,460 @@
+/*
+ * Licensed Materials - Property of IBM,
+ * WebSphere Studio Workbench
+ * (c) Copyright IBM Corp 2000, 2001
+ */
+package org.eclipse.compare.rangedifferencer;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import org.eclipse.jface.util.Assert;
+
+/**
+ * For finding the differences between two or three <code>IRangeComparator</code>s.
+ * <p>
+ * To use the differencer, clients provide an <code>IRangeComparator</code>
+ * that breaks their input data into a sequence of comparable entities. The differencer
+ * returns the differences among these sequences as an array of <code>RangeDifference</code> objects
+ * (<code>findDifferences</code> methods).
+ * Every <code>RangeDifference</code> represents a single kind of difference
+ * and the corresponding ranges of the underlying comparable entities in the
+ * left, right, and optionally ancestor sides.
+ * <p>
+ * Alternatively, the <code>findRanges</code> methods not only return objects for
+ * the differing ranges but for non-differing ranges too.
+ * <p>
+ * The algorithm used is an objectified version of one described in:
+ * <it>A File Comparison Program,</it> by Webb Miller and Eugene W. Myers, 
+ * Software Practice and Experience, Vol. 15, Nov. 1985.
+ *
+ * @see IRangeComparator
+ * @see RangeDifference
+ */
+public final class RangeDifferencer {
+	
+	private static final RangeDifference[] EMPTY_RESULT= new RangeDifference[0];
+	
+	/* (non Javadoc)
+	 * Non instantiatiable!
+	 */
+	private RangeDifferencer() { 
+	}
+	
+	/**
+	 * Finds the differences between two <code>IRangeComparator</code>s.
+	 * The differences are returned as a list of <code>RangeDifference</code>s.
+	 * If no differences are detected an empty list is returned.
+	 * 
+	 * @param left the left range comparator
+	 * @param right the right range comparator
+	 * @return an array of range differences, or an empty array if no differences were found
+	 */
+	public static RangeDifference[] findDifferences(IRangeComparator left, IRangeComparator right) {
+
+		// assert that both IRangeComparators are of the same class
+		Assert.isTrue(right.getClass().equals(left.getClass()));
+
+		int rightSize= right.getRangeCount();
+		int leftSize= left.getRangeCount();
+		//
+		// Differences matrix:
+		// only the last d of each diagonal is stored, i.e., lastDiagonal[k] = row of d    
+		//
+		int diagLen= 2 * Math.max(rightSize, leftSize); // bound on the size of edit script
+		int maxDiagonal= diagLen;
+		int lastDiagonal[]= new int[diagLen + 1]; // the row containing the last d
+		// on diagonal k (lastDiagonal[k] = row)
+		int origin= diagLen / 2; // origin of diagonal 0
+
+		// script corresponding to d[k] 
+		LinkedRangeDifference script[]= new LinkedRangeDifference[diagLen + 1];
+		int row, col;
+
+		// find common prefix
+		for (row= 0; row < rightSize && row < leftSize && rangesEqual(right, row, left, row) == true; ++row);
+
+		lastDiagonal[origin]= row;
+		script[origin]= null;
+		int lower= (row == rightSize) ? origin + 1 : origin - 1;
+		int upper= (row == leftSize) ? origin - 1 : origin + 1;
+
+		if (lower > upper)
+			return EMPTY_RESULT;
+
+		// for each value of the edit distance
+		for (int d= 1; d <= maxDiagonal; ++d) { // d is the current edit distance
+
+			if (right.skipRangeComparison(d, maxDiagonal, left))
+				return EMPTY_RESULT; // should be something we already found
+
+			// for each relevant diagonal (-d, -d+2 ..., d-2, d)
+			for (int k= lower; k <= upper; k += 2) { // k is the current diagonal
+				LinkedRangeDifference edit;
+
+				if (k == origin - d || k != origin + d && lastDiagonal[k + 1] >= lastDiagonal[k - 1]) {
+					//
+					// move down
+					//
+					row= lastDiagonal[k + 1] + 1;
+					edit= new LinkedRangeDifference(script[k + 1], LinkedRangeDifference.DELETE);
+				} else {
+					//
+					// move right
+					//
+					row= lastDiagonal[k - 1];
+					edit= new LinkedRangeDifference(script[k - 1], LinkedRangeDifference.INSERT);
+				}
+				col= row + k - origin;
+				edit.fRightStart= row;
+				edit.fLeftStart= col;
+				Assert.isTrue(k >= 0 && k <= maxDiagonal, "Indices out of range");
+				script[k]= edit;
+
+				// slide down the diagonal as far as possible 
+				while (row < rightSize && col < leftSize && rangesEqual(right, row, left, col) == true) {
+					++row;
+					++col;
+				}
+
+				Assert.isTrue(k >= 0 && k <= maxDiagonal, "unreasonable value for diagonal index");
+				lastDiagonal[k]= row;
+
+				if (row == rightSize && col == leftSize) {
+					//showScript(script[k], right, left);
+					return createDifferencesRanges(script[k]);
+				}
+				if (row == rightSize)
+					lower= k + 2;
+				if (col == leftSize)
+					upper= k - 2;
+			}
+			--lower;
+			++upper;
+		}
+		// too many differences
+		Assert.isTrue(false);
+		return null;
+	}
+
+	/**
+	 * Finds the differences among three <code>IRangeComparator</code>s.
+	 * The differences are returned as a list of <code>RangeDifference</code>s.
+	 * If no differences are detected an empty list is returned.
+	 * If the ancestor range comparator is <code>null</code>, a two-way
+	 * comparison is performed.
+	 * 
+	 * @param ancestor the ancestor range comparator or <code>null</code>
+	 * @param left the left range comparator
+	 * @param right the right range comparator
+	 * @return an array of range differences, or an empty array if no differences were found
+	 */
+	public static RangeDifference[] findDifferences(IRangeComparator ancestor, IRangeComparator left, IRangeComparator right) {
+
+		if (ancestor == null)
+			return findDifferences(left, right);
+
+		RangeDifference[] leftAncestorScript= null;
+		RangeDifference[] rightAncestorScript= findDifferences(ancestor, right);
+		if (rightAncestorScript != null)
+			leftAncestorScript= findDifferences(ancestor, left);
+		if (rightAncestorScript == null || leftAncestorScript == null)
+			return null;
+
+		DifferencesIterator myIter= new DifferencesIterator(rightAncestorScript);
+		DifferencesIterator yourIter= new DifferencesIterator(leftAncestorScript);
+
+		List diff3= new ArrayList();
+		diff3.add(new RangeDifference(RangeDifference.ERROR)); // add a sentinel
+
+		int changeRangeStart= 0;
+		int changeRangeEnd= 0;
+		//
+		// Combine the two two-way edit scripts into one
+		//
+		while (myIter.fDifference != null || yourIter.fDifference != null) {
+
+			DifferencesIterator startThread;
+			myIter.removeAll();
+			yourIter.removeAll();
+			//
+			// take the next diff that is closer to the start
+			//
+			if (myIter.fDifference == null)
+				startThread= yourIter;
+			else if (yourIter.fDifference == null)
+				startThread= myIter;
+			else { // not at end of both scripts take the lowest range
+				if (myIter.fDifference.fLeftStart <= yourIter.fDifference.fLeftStart) // 2 -> common (Ancestor) change range
+					startThread= myIter;
+				else
+					startThread= yourIter;
+			}
+			changeRangeStart= startThread.fDifference.fLeftStart;
+			changeRangeEnd= startThread.fDifference.leftEnd();
+
+			startThread.next();
+			//
+			// check for overlapping changes with other thread
+			// merge overlapping changes with this range
+			//
+			DifferencesIterator other= startThread.other(myIter, yourIter);
+			while (other.fDifference != null && other.fDifference.fLeftStart <= changeRangeEnd) {
+				int newMax= other.fDifference.leftEnd();
+				other.next();
+				if (newMax >= changeRangeEnd) {
+					changeRangeEnd= newMax;
+					other= other.other(myIter, yourIter);
+				}
+			}
+			diff3.add(createRangeDifference3(myIter, yourIter, diff3, right, left, changeRangeStart, changeRangeEnd));
+		}
+
+		// remove sentinel
+		diff3.remove(0);
+		return (RangeDifference[]) diff3.toArray(EMPTY_RESULT);
+	}
+
+	/**
+	 * Finds the differences among two <code>IRangeComparator</code>s.
+	 * In contrast to <code>findDifferences</code>, the result
+	 * contains <code>RangeDifference</code> elements for non-differing ranges too.
+	 * 
+	 * @param left the left range comparator
+	 * @param right the right range comparator
+	 * @return an array of range differences
+	 */
+	public static RangeDifference[] findRanges(IRangeComparator left, IRangeComparator right) {
+		RangeDifference[] in= findDifferences(left, right);
+		List out= new ArrayList();
+
+		RangeDifference rd;
+
+		int mstart= 0;
+		int ystart= 0;
+
+		for (int i= 0; i < in.length; i++) {
+			RangeDifference es= in[i];
+
+			rd= new RangeDifference(RangeDifference.NOCHANGE, mstart, es.rightStart() - mstart, ystart, es.leftStart() - ystart);
+			if (rd.maxLength() != 0)
+				out.add(rd);
+
+			out.add(es);
+
+			mstart= es.rightEnd();
+			ystart= es.leftEnd();
+		}
+		rd= new RangeDifference(RangeDifference.NOCHANGE, mstart, right.getRangeCount() - mstart, ystart, left.getRangeCount() - ystart);
+		if (rd.maxLength() > 0)
+			out.add(rd);
+
+		return (RangeDifference[]) out.toArray(EMPTY_RESULT);
+	}
+
+	/**
+	 * Finds the differences among three <code>IRangeComparator</code>s.
+	 * In contrast to <code>findDifferences</code>, the result
+	 * contains <code>RangeDifference</code> elements for non-differing ranges too.
+	 * If the ancestor range comparator is <code>null</code>, a two-way
+	 * comparison is performed.
+	 * 
+	 * @param ancestor the ancestor range comparator or <code>null</code>
+	 * @param left the left range comparator
+	 * @param right the right range comparator
+	 * @return an array of range differences
+	 */
+	public static RangeDifference[] findRanges(IRangeComparator ancestor, IRangeComparator left, IRangeComparator right) {
+
+		if (ancestor == null)
+			return findRanges(left, right);
+
+		RangeDifference[] in= findDifferences(ancestor, left, right);
+		List out= new ArrayList();
+
+		RangeDifference rd;
+
+		int mstart= 0;
+		int ystart= 0;
+		int astart= 0;
+
+		for (int i= 0; i < in.length; i++) {
+			RangeDifference es= (RangeDifference) in[i];
+
+			rd= new RangeDifference(RangeDifference.NOCHANGE, mstart, es.rightStart() - mstart, ystart, es.leftStart() - ystart, astart, es.ancestorStart() - astart);
+			if (rd.maxLength() > 0)
+				out.add(rd);
+
+			out.add(es);
+
+			mstart= es.rightEnd();
+			ystart= es.leftEnd();
+			astart= es.ancestorEnd();
+		}
+		rd= new RangeDifference(RangeDifference.NOCHANGE, mstart, right.getRangeCount() - mstart, ystart, left.getRangeCount() - ystart, astart, ancestor.getRangeCount() - astart);
+		if (rd.maxLength() > 0)
+			out.add(rd);
+
+		return (RangeDifference[]) out.toArray(EMPTY_RESULT);
+	}
+
+	//---- private methods
+
+	/**
+	 * Creates a Vector of DifferencesRanges out of the LinkedRangeDifference.
+	 * It coalesces adjacent changes.
+	 * In addition, indices are changed such that the ranges are 1) open, i.e,
+	 * the end of the range is not included, and 2) are zero based.
+	 */
+	private static RangeDifference[] createDifferencesRanges(LinkedRangeDifference start) {
+
+		LinkedRangeDifference ep= reverseDifferences(start);
+		ArrayList result= new ArrayList();
+		RangeDifference es= null;
+
+		while (ep != null) {
+			es= new RangeDifference(RangeDifference.CHANGE);
+
+			if (ep.isInsert()) {
+				es.fRightStart= ep.fRightStart + 1;
+				es.fLeftStart= ep.fLeftStart;
+				RangeDifference b= ep;
+				do {
+					ep= ep.getNext();
+					es.fLeftLength++;
+				} while (ep != null && ep.isInsert() && ep.fRightStart == b.fRightStart);
+			} else {
+				es.fRightStart= ep.fRightStart;
+				es.fLeftStart= ep.fLeftStart;
+
+				RangeDifference a= ep;
+				//
+				// deleted lines
+				//
+				do {
+					a= ep;
+					ep= ep.getNext();
+					es.fRightLength++;
+				} while (ep != null && ep.isDelete() && ep.fRightStart == a.fRightStart + 1);
+
+				boolean change= (ep != null && ep.isInsert() && ep.fRightStart == a.fRightStart);
+
+				if (change) {
+					RangeDifference b= ep;
+					//
+					// replacement lines
+					//
+					do {
+						ep= ep.getNext();
+						es.fLeftLength++;
+					} while (ep != null && ep.isInsert() && ep.fRightStart == b.fRightStart);
+				} else {
+					es.fLeftLength= 0;
+				}
+				es.fLeftStart++; // meaning of range changes from "insert after", to "replace with"
+
+			}
+			//
+			// the script commands are 1 based, subtract one to make them zero based
+			//
+			es.fRightStart--;
+			es.fLeftStart--;
+			result.add(es);
+		}
+		return (RangeDifference[]) result.toArray(EMPTY_RESULT);
+	}
+
+	/**
+	 * Creates a <code>RangeDifference3</code> given the
+	 * state of two DifferenceIterators.
+	 */
+	private static RangeDifference createRangeDifference3(
+		DifferencesIterator myIter, 
+		DifferencesIterator yourIter, 
+		List diff3, 
+		IRangeComparator right, 
+		IRangeComparator left, 
+		int changeRangeStart, 
+		int changeRangeEnd) {
+
+		int rightStart, rightEnd;
+		int leftStart, leftEnd;
+		int kind= RangeDifference.ERROR;
+		RangeDifference last= (RangeDifference) diff3.get(diff3.size() - 1);
+
+		Assert.isTrue((myIter.getCount() != 0 || yourIter.getCount() != 0), "at least one range array must be non-empty");
+		//
+		// find corresponding lines to fChangeRangeStart/End in right and left
+		//
+		if (myIter.getCount() == 0) { // only left changed
+			rightStart= changeRangeStart - last.ancestorEnd() + last.rightEnd();
+			rightEnd= changeRangeEnd - last.ancestorEnd() + last.rightEnd();
+			kind= RangeDifference.LEFT;
+		} else {
+			RangeDifference f= (RangeDifference) myIter.fRange.get(0);
+			RangeDifference l= (RangeDifference) myIter.fRange.get(myIter.fRange.size() - 1);
+			rightStart= changeRangeStart - f.fLeftStart + f.fRightStart;
+			rightEnd= changeRangeEnd - l.leftEnd() + l.rightEnd();
+		}
+
+		if (yourIter.getCount() == 0) { // only right changed
+			leftStart= changeRangeStart - last.ancestorEnd() + last.leftEnd();
+			leftEnd= changeRangeEnd - last.ancestorEnd() + last.leftEnd();
+			kind= RangeDifference.RIGHT;
+		} else {
+			RangeDifference f= (RangeDifference) yourIter.fRange.get(0);
+			RangeDifference l= (RangeDifference) yourIter.fRange.get(yourIter.fRange.size() - 1);
+			leftStart= changeRangeStart - f.fLeftStart + f.fRightStart;
+			leftEnd= changeRangeEnd - l.leftEnd() + l.rightEnd();
+		}
+
+		if (kind == RangeDifference.ERROR) { // overlapping change (conflict) -> compare the changed ranges
+			if (rangeSpansEqual(right, rightStart, rightEnd - rightStart, left, leftStart, leftEnd - leftStart))
+				kind= RangeDifference.ANCESTOR;
+			else
+				kind= RangeDifference.CONFLICT;
+		}
+		return new RangeDifference(kind, rightStart, rightEnd - rightStart, leftStart, leftEnd - leftStart, changeRangeStart, changeRangeEnd - changeRangeStart);
+	}
+
+	/**
+	 * Tests if two ranges are equal
+	 */
+	private static boolean rangesEqual(IRangeComparator a, int ai, IRangeComparator b, int bi) {
+		return a.rangesEqual(ai, b, bi);
+	}
+
+	/**
+	 * Tests whether <code>right</code> and <code>left</left> changed in the same way
+	 */
+	private static boolean rangeSpansEqual(IRangeComparator right, int rightStart, int rightLen, IRangeComparator left, int leftStart, int leftLen) {
+		if (rightLen == leftLen) {
+			int i= 0;
+			for (i= 0; i < rightLen; i++) {
+				if (!rangesEqual(right, rightStart + i, left, leftStart + i))
+					break;
+			}
+			if (i == rightLen)
+				return true;
+		}
+		return false;
+	}
+
+	/**
+	 * Reverses the range differences
+	 */
+	private static LinkedRangeDifference reverseDifferences(LinkedRangeDifference start) {
+		LinkedRangeDifference ep, behind, ahead;
+
+		ahead= start;
+		ep= null;
+		while (ahead != null) {
+			behind= ep;
+			ep= ahead;
+			ahead= ahead.getNext();
+			ep.setNext(behind);
+		}
+		return ep;
+	}
+}
+