001: /*******************************************************************************
002: * Copyright (c) 2000, 2006 IBM Corporation and others.
003: * All rights reserved. This program and the accompanying materials
004: * are made available under the terms of the Eclipse Public License v1.0
005: * which accompanies this distribution, and is available at
006: * http://www.eclipse.org/legal/epl-v10.html
007: *
008: * Contributors:
009: * IBM Corporation - initial API and implementation
010: *******************************************************************************/package org.eclipse.ui.internal.texteditor.quickdiff.compare.rangedifferencer;
011:
012: import java.util.ArrayList;
013: import java.util.Arrays;
014: import java.util.List;
015:
016: import org.eclipse.core.runtime.Assert;
017: import org.eclipse.core.runtime.IProgressMonitor;
018:
019: import org.eclipse.ui.internal.texteditor.quickdiff.compare.rangedifferencer.LinkedRangeFactory.LowMemoryException;
020:
021: /**
022: * A <code>RangeDifferencer</code> finds the differences between two or three <code>IRangeComparator</code>s.
023: * <p>
024: * To use the differencer, clients provide an <code>IRangeComparator</code>
025: * that breaks their input data into a sequence of comparable entities. The differencer
026: * returns the differences among these sequences as an array of <code>RangeDifference</code> objects
027: * (<code>findDifferences</code> methods).
028: * Every <code>RangeDifference</code> represents a single kind of difference
029: * and the corresponding ranges of the underlying comparable entities in the
030: * left, right, and optionally ancestor sides.
031: * <p>
032: * Alternatively, the <code>findRanges</code> methods not only return objects for
033: * the differing ranges but for non-differing ranges too.
034: * <p>
035: * The algorithm used is an objectified version of one described in:
036: * <it>A File Comparison Program,</it> by Webb Miller and Eugene W. Myers,
037: * Software Practice and Experience, Vol. 15, Nov. 1985.
038: *
039: * @see IRangeComparator
040: * @see RangeDifference
041: * @since 3.0
042: */
043: public final class RangeDifferencer {
044:
045: private static final RangeDifference[] EMPTY_RESULT = new RangeDifference[0];
046:
047: /*
048: * Non instantiateable!
049: */
050: private RangeDifferencer() {
051: }
052:
053: /**
054: * Finds the differences between two <code>IRangeComparator</code>s.
055: * The differences are returned as an array of <code>RangeDifference</code>s.
056: * If no differences are detected an empty array is returned.
057: *
058: * @param left the left range comparator
059: * @param right the right range comparator
060: * @return an array of range differences, or an empty array if no differences were found
061: */
062: public static RangeDifference[] findDifferences(
063: IRangeComparator left, IRangeComparator right) {
064: return findDifferences((IProgressMonitor) null, left, right);
065: }
066:
067: /**
068: * Finds the differences between two <code>IRangeComparator</code>s.
069: * The differences are returned as an array of <code>RangeDifference</code>s.
070: * If no differences are detected an empty array is returned.
071: *
072: * @param pm if not <code>null</code> used to report progress
073: * @param left the left range comparator
074: * @param right the right range comparator
075: * @return an array of range differences, or an empty array if no differences were found
076: * @since 2.0
077: */
078: private static RangeDifference[] findDifferences(
079: IProgressMonitor pm, IRangeComparator left,
080: IRangeComparator right) {
081: try {
082: return findDifferencesUkkonen(pm, left, right);
083: } catch (LowMemoryException e) {
084: return Levenshtein.findDifferences(pm, left, right);
085: }
086: }
087:
088: /**
089: * Finds the differences between two <code>IRangeComparator</code>s.
090: * The differences are returned as an array of <code>RangeDifference</code>s.
091: * If no differences are detected an empty array is returned.
092: *
093: * @param pm if not <code>null</code> used to report progress
094: * @param left the left range comparator
095: * @param right the right range comparator
096: * @return an array of range differences, or an empty array if no differences were found
097: * @throws LowMemoryException if the differencer runs out of memory
098: * @since 2.0
099: */
100: private static RangeDifference[] findDifferencesUkkonen(
101: IProgressMonitor pm, IRangeComparator left,
102: IRangeComparator right) throws LowMemoryException {
103:
104: // assert that both IRangeComparators are of the same class
105: Assert.isTrue(right.getClass().equals(left.getClass()));
106:
107: int rightSize = right.getRangeCount();
108: int leftSize = left.getRangeCount();
109: //
110: // Differences matrix:
111: // only the last d of each diagonal is stored, i.e., lastDiagonal[k] = row of d
112: //
113: int diagLen = 2 * Math.max(rightSize, leftSize); // bound on the size of edit script
114: int maxDiagonal = diagLen;
115: int lastDiagonal[] = new int[diagLen + 1]; // the row containing the last d
116: Arrays.fill(lastDiagonal, -1);
117: // on diagonal k (lastDiagonal[k] = row)
118: int origin = diagLen / 2; // origin of diagonal 0
119:
120: // script corresponding to d[k]
121: LinkedRangeDifference script[] = new LinkedRangeDifference[diagLen + 1];
122: int row, col;
123:
124: // find common prefix
125: for (row = 0; row < rightSize && row < leftSize
126: && rangesEqual(right, row, left, row); ++row) {
127: // do nothing
128: }
129:
130: lastDiagonal[origin] = row;
131: script[origin] = null;
132: int lower = (row == rightSize) ? origin + 1 : origin - 1;
133: int upper = (row == leftSize) ? origin - 1 : origin + 1;
134:
135: if (lower > upper)
136: return EMPTY_RESULT;
137:
138: //System.out.println("findDifferences: " + maxDiagonal + " " + lower + " " + upper);
139: LinkedRangeFactory factory = new LinkedRangeFactory();
140:
141: // for each value of the edit distance
142: for (int d = 1; d <= maxDiagonal; ++d) { // d is the current edit distance
143:
144: if (pm != null)
145: pm.worked(1);
146:
147: if (right.skipRangeComparison(d, maxDiagonal, left))
148: return EMPTY_RESULT; // should be something we already found
149:
150: // for each relevant diagonal (-d, -d+2 ..., d-2, d)
151: for (int k = lower; k <= upper; k += 2) { // k is the current diagonal
152: LinkedRangeDifference edit;
153:
154: if (pm != null && pm.isCanceled())
155: return EMPTY_RESULT;
156:
157: if (k == origin - d || k != origin + d
158: && lastDiagonal[k + 1] >= lastDiagonal[k - 1]) {
159: //
160: // move down
161: //
162: row = lastDiagonal[k + 1] + 1;
163: edit = factory.newRange(script[k + 1],
164: LinkedRangeDifference.DELETE);
165: } else {
166: //
167: // move right
168: //
169: row = lastDiagonal[k - 1];
170: edit = factory.newRange(script[k - 1],
171: LinkedRangeDifference.INSERT);
172: }
173: col = row + k - origin;
174: edit.fRightStart = row;
175: edit.fLeftStart = col;
176: Assert.isTrue(k >= 0 && k <= maxDiagonal);
177: script[k] = edit;
178:
179: // slide down the diagonal as far as possible
180: while (row < rightSize && col < leftSize
181: && rangesEqual(right, row, left, col) == true) {
182: ++row;
183: ++col;
184: }
185:
186: Assert.isTrue(k >= 0 && k <= maxDiagonal); // Unreasonable value for diagonal index
187: lastDiagonal[k] = row;
188:
189: if (row == rightSize && col == leftSize) {
190: //showScript(script[k], right, left);
191: return createDifferencesRanges(script[k]);
192: }
193: if (row == rightSize)
194: lower = k + 2;
195: if (col == leftSize)
196: upper = k - 2;
197: }
198: --lower;
199: ++upper;
200: }
201: // too many differences
202: Assert.isTrue(false);
203: return null;
204: }
205:
206: /**
207: * Finds the differences among two <code>IRangeComparator</code>s.
208: * In contrast to <code>findDifferences</code>, the result
209: * contains <code>RangeDifference</code> elements for non-differing ranges too.
210: *
211: * @param left the left range comparator
212: * @param right the right range comparator
213: * @return an array of range differences
214: */
215: public static List findRanges(IRangeComparator left,
216: IRangeComparator right) {
217: return findRanges((IProgressMonitor) null, left, right);
218: }
219:
220: /**
221: * Finds the differences among two <code>IRangeComparator</code>s.
222: * In contrast to <code>findDifferences</code>, the result
223: * contains <code>RangeDifference</code> elements for non-differing ranges too.
224: *
225: * @param pm if not <code>null</code> used to report progress
226: * @param left the left range comparator
227: * @param right the right range comparator
228: * @return an array of range differences
229: * @since 2.0
230: */
231: public static List findRanges(IProgressMonitor pm,
232: IRangeComparator left, IRangeComparator right) {
233: RangeDifference[] in = findDifferences(pm, left, right);
234: List out = new ArrayList();
235:
236: RangeDifference rd;
237:
238: int mstart = 0;
239: int ystart = 0;
240:
241: for (int i = 0; i < in.length; i++) {
242: RangeDifference es = in[i];
243:
244: rd = new RangeDifference(RangeDifference.NOCHANGE, mstart,
245: es.rightStart() - mstart, ystart, es.leftStart()
246: - ystart);
247: if (rd.maxLength() != 0)
248: out.add(rd);
249:
250: out.add(es);
251:
252: mstart = es.rightEnd();
253: ystart = es.leftEnd();
254: }
255: rd = new RangeDifference(RangeDifference.NOCHANGE, mstart,
256: right.getRangeCount() - mstart, ystart, left
257: .getRangeCount()
258: - ystart);
259: if (rd.maxLength() > 0)
260: out.add(rd);
261:
262: return out;
263: }
264:
265: //---- private methods
266:
267: /**
268: * Creates an array <code>DifferencesRanges</code> out of the
269: * <code>LinkedRangeDifference</code>. It coalesces adjacent changes. In
270: * addition, indices are changed such that the ranges are 1) open, i.e, the
271: * end of the range is not included, and 2) are zero based.
272: *
273: * @param start the start difference
274: * @return the created array of difference ranges
275: */
276: private static RangeDifference[] createDifferencesRanges(
277: LinkedRangeDifference start) {
278:
279: LinkedRangeDifference ep = reverseDifferences(start);
280: ArrayList result = new ArrayList();
281: RangeDifference es = null;
282:
283: while (ep != null) {
284: es = new RangeDifference(RangeDifference.CHANGE);
285:
286: if (ep.isInsert()) {
287: es.fRightStart = ep.fRightStart + 1;
288: es.fLeftStart = ep.fLeftStart;
289: RangeDifference b = ep;
290: do {
291: ep = ep.getNext();
292: es.fLeftLength++;
293: } while (ep != null && ep.isInsert()
294: && ep.fRightStart == b.fRightStart);
295: } else {
296: es.fRightStart = ep.fRightStart;
297: es.fLeftStart = ep.fLeftStart;
298:
299: RangeDifference a = ep;
300: //
301: // deleted lines
302: //
303: do {
304: a = ep;
305: ep = ep.getNext();
306: es.fRightLength++;
307: } while (ep != null && ep.isDelete()
308: && ep.fRightStart == a.fRightStart + 1);
309:
310: boolean change = (ep != null && ep.isInsert() && ep.fRightStart == a.fRightStart);
311:
312: if (change) {
313: RangeDifference b = ep;
314: //
315: // replacement lines
316: //
317: do {
318: ep = ep.getNext();
319: es.fLeftLength++;
320: } while (ep != null && ep.isInsert()
321: && ep.fRightStart == b.fRightStart);
322: } else {
323: es.fLeftLength = 0;
324: }
325: es.fLeftStart++; // meaning of range changes from "insert after", to "replace with"
326:
327: }
328: //
329: // the script commands are 1 based, subtract one to make them zero based
330: //
331: es.fRightStart--;
332: es.fLeftStart--;
333: result.add(es);
334: }
335: return (RangeDifference[]) result.toArray(EMPTY_RESULT);
336: }
337:
338: /**
339: * Tests whether two ranges at the given indices are equal.
340: *
341: * @param a the first comparator
342: * @param ai the index of the first range
343: * @param b the second comparator
344: * @param bi the index of the second range
345: * @return <code>true</code> if the ranges are equal, <code>false</code> otherwise
346: */
347: private static boolean rangesEqual(IRangeComparator a, int ai,
348: IRangeComparator b, int bi) {
349: return a.rangesEqual(ai, b, bi);
350: }
351:
352: /**
353: * Reverses the list of range differences thus that the given start difference becomes the
354: * end of the list.
355: *
356: * @param start the start of the list
357: * @return the reverted list
358: */
359: private static LinkedRangeDifference reverseDifferences(
360: LinkedRangeDifference start) {
361: LinkedRangeDifference ep, behind, ahead;
362:
363: ahead = start;
364: ep = null;
365: while (ahead != null) {
366: behind = ep;
367: ep = ahead;
368: ahead = ahead.getNext();
369: ep.setNext(behind);
370: }
371: return ep;
372: }
373: }
|