Skip to main content
summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat (limited to 'bundles/org.eclipse.compare/compare/org/eclipse/compare/rangedifferencer/RangeDifferencer.java')
-rw-r--r--bundles/org.eclipse.compare/compare/org/eclipse/compare/rangedifferencer/RangeDifferencer.java532
1 files changed, 0 insertions, 532 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
deleted file mode 100644
index 43b880853..000000000
--- a/bundles/org.eclipse.compare/compare/org/eclipse/compare/rangedifferencer/RangeDifferencer.java
+++ /dev/null
@@ -1,532 +0,0 @@
-/*
- * (c) Copyright IBM Corp. 2000, 2001.
- * All Rights Reserved.
- */
-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.
- * <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 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
- */
- 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
- */
- 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
- */
- 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 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
- */
- 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
- */
- 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= (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;
- }
-}
-

Back to the top