[Jcommander-commit] plugins/org.jcommander.eclipsepatch.compare/compare/org/eclipse/compare/rangedif

SourceForge Headquarters 1320 Columbia Street Suite 310 San Diego, CA 92101 +1 (858) 422-6466

Update of /cvsroot/jcommander/plugins/org.jcommander.eclipsepatch.compare/compare/org/eclipse/compare/rangedifferencer
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv5127/compare/org/eclipse/compare/rangedifferencer

Added Files:
	RangeDifferencer.java LinkedRangeDifference.java 
	RangeDifference.java package.html DifferencesIterator.java 
	IRangeComparator.java 
Log Message:
org.eclipse.compare, extracted from the Eclipse CVS. Now independent of org.eclipse.ui.ide etc.

--- NEW FILE: IRangeComparator.java ---
/*******************************************************************************
 * Copyright (c) 2000, 2004 IBM Corporation and others.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     IBM Corporation - initial API and implementation
 *******************************************************************************/
package org.eclipse.compare.rangedifferencer;

/**
 * For breaking an object to compare into a sequence of comparable entities.
 * 
 * It is used by <code>RangeDifferencer</code> to find longest sequences of
 * matching and non-matching ranges.
 * 
 * For example, to compare two text documents and find longest common sequences
 * of matching and non-matching lines, the implementation must break the document
 * into lines. <code>getRangeCount</code> would return the number of lines in the 
 * document, and <code>rangesEqual</code> would compare a specified line given 
 * with one in another <code>IRangeComparator</code>.
 * 
 * 
 * Clients should implement this interface; there is no standard implementation.
 * 
 */
public interface IRangeComparator {

	/**
	 * Returns the number of comparable entities.
	 *
	 * @return the number of comparable entities 
	 */
	int getRangeCount();

	/**
	 * Returns whether the comparable entity given by the first index
	 * matches an entity specified by the other <code>IRangeComparator</code> and index.
	 *
	 * @param thisIndex the index of the comparable entity within this <code>IRangeComparator</code>
	 * @param other the IRangeComparator to compare this with
	 * @param otherIndex the index of the comparable entity within the other <code>IRangeComparator</code>
	 * @return <code>true</code> if the comparable entities are equal
	 */
	boolean rangesEqual(int thisIndex, IRangeComparator other, int otherIndex);

	/**
	 * Returns whether a comparison should be skipped because it would be too costly (or lengthy).
	 * 
	 * @param length a number on which to base the decision whether to return
	 * 	<code>true</code> or <code>false</code>
	 * @param maxLength another number on which to base the decision whether to return
	 *	<code>true</code> or <code>false</code>
	 * @param other the other <code>IRangeComparator</code> to compare with
	 * @return <code>true</code> to avoid a too lengthy range comparison
	 */
	boolean skipRangeComparison(int length, int maxLength, IRangeComparator other);
}

--- NEW FILE: RangeDifference.java ---
/*******************************************************************************
 * Copyright (c) 2000, 2004 IBM Corporation and others.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     IBM Corporation - initial API and implementation
 *******************************************************************************/
package org.eclipse.compare.rangedifferencer;

/**
 * Description of a change between two or three ranges of comparable entities.
 * 
 * <code>RangeDifference</code> objects are the elements of a compare result returned from
 * the <code>RangeDifferencer</code> <code>find* </code> methods.
 * Clients use these objects as they are returned from the differencer.
 * This class is not intended to be instantiated or subclassed.
 * 
 * Note: A range in the <code>RangeDifference</code> object is given as a start index
 * and length in terms of comparable entities. However, these entity indices and counts
 * are not necessarily character positions. For example, if an entity represents a line
 * in a document, the start index would be a line number and the count would be in lines.
 * 
 *
 * @see RangeDifferencer
 */
public class RangeDifference {

	/** Two-way change constant indicating no change. */
	public final static int NOCHANGE= 0;
	/** Two-way change constant indicating two-way change (same as <code>RIGHT</code>) */
	public final static int CHANGE= 2;

	/** Three-way change constant indicating a change in both right and left. */
	public final static int CONFLICT= 1;
	/** Three-way change constant indicating a change in right. */
	public final static int RIGHT= 2;
	/** Three-way change constant indicating a change in left. */
	public final static int LEFT= 3;
	/**
	 * Three-way change constant indicating the same change in both right and left,
	 * that is only the ancestor is different.
	 */
	public final static int ANCESTOR= 4;

	/** Constant indicating an unknown change kind. */
	public final static int ERROR= 5;

	/** the kind of change: NOCHANGE, CHANGE, LEFT, RIGHT, ANCESTOR, CONFLICT, ERROR */
	int fKind;

	int fLeftStart;
	int fLeftLength;
	int fRightStart;
	int fRightLength;
	int lAncestorStart;
	int lAncestorLength;

	/**
	 * Creates a new range difference with the given change kind.
	 *
	 * @param changeKind the kind of change
	 */
	/* package */ RangeDifference(int changeKind) {
		fKind= changeKind;
	}

	/**
	 * Creates a new <code>RangeDifference</code> with the given change kind
	 * and left and right ranges.
	 *
	 * @param kind the kind of change
	 * @param rightStart start index of entity on right side
	 * @param rightLength number of entities on right side
	 * @param leftStart start index of entity on left side
	 * @param leftLength number of entities on left side
	 */
	/* package */ RangeDifference(int kind, int rightStart, int rightLength, int leftStart, int leftLength) {
		fKind= kind;
		fRightStart= rightStart;
		fRightLength= rightLength;
		fLeftStart= leftStart;
		fLeftLength= leftLength;
	}

	/**
	 * Creates a new <code>RangeDifference</code> with the given change kind
	 * and left, right, and ancestor ranges.
	 *
	 * @param kind the kind of change
	 * @param rightStart start index of entity on right side
	 * @param rightLength number of entities on right side
	 * @param leftStart start index of entity on left side
	 * @param leftLength number of entities on left side
	 * @param ancestorStart start index of entity on ancestor side
	 * @param ancestorLength number of entities on ancestor side
	 */
	/* package */ RangeDifference(int kind, int rightStart, int rightLength, int leftStart, int leftLength,
									int ancestorStart, int ancestorLength) {
		this(kind, rightStart, rightLength, leftStart, leftLength);
		lAncestorStart= ancestorStart;
		lAncestorLength= ancestorLength;
	}

	/**
	 * Returns the kind of difference.
	 *
	 * @return the kind of difference, one of
	 * <code>NOCHANGE</code>, <code>CHANGE</code>, <code>LEFT</code>, <code>RIGHT</code>,
	 * <code>ANCESTOR</code>, <code>CONFLICT</code>, <code>ERROR</code>
	 */
	public int kind() {
		return fKind;
	}

	/**
	 * Returns the start index of the entity range on the ancestor side.
	 *
	 * @return the start index of the entity range on the ancestor side
	 */
	public int ancestorStart() {
		return lAncestorStart;
	}

	/**
	 * Returns the number of entities on the ancestor side.
	 *
	 * @return the number of entities on the ancestor side
	 */
	public int ancestorLength() {
		return lAncestorLength;
	}

	/**
	 * Returns the end index of the entity range on the ancestor side.
	 *
	 * @return the end index of the entity range on the ancestor side
	 */
	public int ancestorEnd() {
		return lAncestorStart + lAncestorLength;
	}

	/**
	 * Returns the start index of the entity range on the right side.
	 *
	 * @return the start index of the entity range on the right side
	 */
	public int rightStart() {
		return fRightStart;
	}

	/**
	 * Returns the number of entities on the right side.
	 *
	 * @return the number of entities on the right side
	 */
	public int rightLength() {
		return fRightLength;
	}

	/**
	 * Returns the end index of the entity range on the right side.
	 *
	 * @return the end index of the entity range on the right side
	 */
	public int rightEnd() {
		return fRightStart + fRightLength;
	}

	/**
	 * Returns the start index of the entity range on the left side.
	 *
	 * @return the start index of the entity range on the left side
	 */
	public int leftStart() {
		return fLeftStart;
	}

	/**
	 * Returns the number of entities on the left side.
	 *
	 * @return the number of entities on the left side
	 */
	public int leftLength() {
		return fLeftLength;
	}

	/**
	 * Returns the end index of the entity range on the left side.
	 *
	 * @return the end index of the entity range on the left side
	 */
	public int leftEnd() {
		return fLeftStart + fLeftLength;
	}

	/**
	 * Returns the maximum number of entities in the left, right, and ancestor sides of this range.
	 *
	 * @return the maximum number of entities in the left, right, and ancestor sides of this range
	 */
	public int maxLength() {
		return Math.max(fRightLength, Math.max(fLeftLength, lAncestorLength));
	}
}

--- NEW FILE: package.html ---
<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
<html>
<head>
   <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
   <meta name="Author" content="IBM">
   <meta name="GENERATOR" content="Mozilla/4.75 [en] (WinNT; U) [Netscape]">
   <title>Package-level Javadoc</title>
</head>
<body>
Provides support for finding the differences between
two or three sequences of comparable entities.
<h2>
Package Specification</h2>

The class RangeDifferencer finds longest sequences of matching and
non-matching comparable entities. Its implementation is based on
an objectified version of the algorithm described in:
A File Comparison Program, by Webb Miller and Eugene W. Myers,
Software Practice and Experience, Vol. 15, Nov. 1985.

Clients must supply the input to the differencer as an implementation
of the IRangeComparator interface.
An IRangeComparator breaks the input data into a sequence
of entities and provides a method for comparing
one entity with the entity in another IRangeComparator.

For example, to compare two text documents and find longest common
sequences of matching and non-matching lines,
the implementation of IRangeComparator 
must break the document into lines and provide a method for testing
whether two lines are considered equal.
See org.eclipse.compare.internal.DocLineComparator for how this can be done.

The differencer returns the differences among these sequences as an
array of RangeDifference objects.
Every single RangeDifference describes the kind of difference
(no change, change, addition, deletion) and the corresponding ranges
of the underlying comparable entities in the two or three inputs.

</body>
</html>

--- NEW FILE: DifferencesIterator.java ---
/*******************************************************************************
 * Copyright (c) 2000, 2004 IBM Corporation and others.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     IBM Corporation - initial API and implementation
 *******************************************************************************/
package org.eclipse.compare.rangedifferencer;

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

/**
 * A custom iterator to iterate over a List of <code>RangeDifferences</code>.
 * It is used internally by the <code>RangeDifferencer</code>.
 */
/* package */ class DifferencesIterator {

	List fRange;
	int fIndex;
	RangeDifference[] fArray;	
	RangeDifference fDifference;

	/*
	 * Creates a differences iterator on an array of <code>RangeDifference</code>s.
	 */
	DifferencesIterator(RangeDifference[] differenceRanges) {

		fArray= differenceRanges;
		fIndex= 0;
		fRange= new ArrayList();
		if (fIndex < fArray.length)
			fDifference= fArray[fIndex++];
		else
			fDifference= null;
	}

	/*
	  * Returns the number of RangeDifferences
	  */
	int getCount() {
		return fRange.size();
	}

	/*
	 * Appends the edit to its list and moves to the next <code>RangeDifference</code>.
	 */
	void next() {
		fRange.add(fDifference);
		if (fDifference != null) {
			if (fIndex < fArray.length)
				fDifference= fArray[fIndex++];
			else
				fDifference= null;
		}
	}

	/*
	 * Difference iterators are used in pairs.
	 * This method returns the other iterator.
	 */
	DifferencesIterator other(DifferencesIterator right, DifferencesIterator left) {
		if (this == right)
			return left;
		return right;
	}

	/*
	  * Removes all <code>RangeDifference</code>s
	  */
	void removeAll() {
		fRange.clear();
	}
}

--- NEW FILE: RangeDifferencer.java ---
/*******************************************************************************
 * Copyright (c) 2000, 2005 IBM Corporation and others.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     IBM Corporation - initial API and implementation
 *******************************************************************************/
package org.eclipse.compare.rangedifferencer;

import java.util.*;

import org.eclipse.jface.util.Assert;

import org.eclipse.core.runtime.IProgressMonitor;

/**
 * A <code>RangeDifferencer</code> finds the differences between two or three <code>IRangeComparator</code>s.
 * 
 * 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.
 * 
 * Alternatively, the <code>findRanges</code> methods not only return objects for
 * the differing ranges but for non-differing ranges too.
 * 
 * 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)
	 * Cannot be instantiated!
	 */
	private RangeDifferencer() {
		// nothing to do
	}

	/**
	 * Finds the differences between two <code>IRangeComparator</code>s.
	 * The differences are returned as an array of <code>RangeDifference</code>s.
	 * If no differences are detected an empty array 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) {
		return findDifferences((IProgressMonitor)null, left, right);
	}

	/**
	 * Finds the differences between two <code>IRangeComparator</code>s.
	 * The differences are returned as an array of <code>RangeDifference</code>s.
	 * If no differences are detected an empty array is returned.
	 * 
	 * @param pm if not <code>null</code> used to report progress
	 * @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
	 * @since 2.0
	 */
	public static RangeDifference[] findDifferences(IProgressMonitor pm, 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;

		//System.out.println("findDifferences: " + maxDiagonal + " " + lower + " " + upper);

		// for each value of the edit distance
		for (int d= 1; d <= maxDiagonal; ++d) { // d is the current edit distance

			if (pm != null)
				pm.worked(1);

			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 (pm != null && pm.isCanceled())
					return EMPTY_RESULT;

				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);
				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) {
		return findDifferences(null, ancestor, left, right);
	}

	/**
	 * 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 pm if not <code>null</code> used to report progress
	 * @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
	 * @since 2.0
	 */
	public static RangeDifference[] findDifferences(IProgressMonitor pm, IRangeComparator ancestor, IRangeComparator left, IRangeComparator right) {

		if (ancestor == null)
			return findDifferences(pm, left, right);

		RangeDifference[] leftAncestorScript= null;
		RangeDifference[] rightAncestorScript= findDifferences(pm, ancestor, right);
		if (rightAncestorScript != null)
			leftAncestorScript= findDifferences(pm, 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) {
		return findRanges((IProgressMonitor)null, left, right);
	}

	/**
	 * 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 pm if not <code>null</code> used to report progress
	 * @param left the left range comparator
	 * @param right the right range comparator
	 * @return an array of range differences
	 * @since 2.0
	 */
	public static RangeDifference[] findRanges(IProgressMonitor pm, IRangeComparator left, IRangeComparator right) {
		RangeDifference[] in= findDifferences(pm, 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) {
		return findRanges(null, ancestor, left, right);
	}

	/**
	 * 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 pm if not <code>null</code> used to report progress
	 * @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
	 * @since 2.0
	 */
	public static RangeDifference[] findRanges(IProgressMonitor pm, IRangeComparator ancestor, IRangeComparator left, IRangeComparator right) {

		if (ancestor == null)
			return findRanges(pm, left, right);

		RangeDifference[] in= findDifferences(pm, 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= 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</code> 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;
	}
}

--- NEW FILE: LinkedRangeDifference.java ---
/*******************************************************************************
 * Copyright (c) 2000, 2004 IBM Corporation and others.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     IBM Corporation - initial API and implementation
 *******************************************************************************/
package org.eclipse.compare.rangedifferencer;

/* package */ class LinkedRangeDifference extends RangeDifference {

	static final int INSERT= 0;
	static final int DELETE= 1;

	LinkedRangeDifference fNext;

	/*
	 * Creates a LinkedRangeDifference an initializes it to the error state
	 */
	LinkedRangeDifference() {
		super(ERROR);
		fNext= null;
	}

	/*
	 * Constructs and links a LinkeRangeDifference to another LinkedRangeDifference
	 */
	LinkedRangeDifference(LinkedRangeDifference next, int operation) {
		super(operation);
		fNext= next;
	}

	/*
	 * Follows the next link
	 */
	LinkedRangeDifference getNext() {
		return fNext;
	}

	boolean isDelete() {
		return kind() == DELETE;
	}

	boolean isInsert() {
		return kind() == INSERT;
	}

	/*
	 * Sets the next link of this LinkedRangeDifference
	 */
	void setNext(LinkedRangeDifference next) {
		fNext= next;
	}
}

[Jcommander-commit] plugins/org.jcommander.eclipsepatch.compare/compare/org/eclipse/compare/rangedif

[Jcommander-commit] plugins/org.jcommander.eclipsepatch.compare/compare/org/eclipse/compare/rangedifferencer RangeDifferencer.java,NONE,1.1 LinkedRangeDifference.java,NONE,1.1 RangeDifference.java,NONE,1.1 package.html,NONE,1.1 DifferencesIterator.java,NONE,1.1 IRangeComparator.java,NONE,1.1