001: /*******************************************************************************
002: * Copyright (c) 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.compare.rangedifferencer;
011:
012: import java.util.ArrayList;
013:
014: import org.eclipse.core.runtime.Assert;
015: import org.eclipse.core.runtime.IProgressMonitor;
016:
017: /**
018: * The algorithm used is an objectified version of one described in:
019: * <it>A File Comparison Program,</it> by Webb Miller and Eugene W. Myers,
020: * Software Practice and Experience, Vol. 15, Nov. 1985.
021: */
022: /* package */class OldDifferencer {
023:
024: private static final RangeDifference[] EMPTY_RESULT = new RangeDifference[0];
025:
026: private static class LinkedRangeDifference extends RangeDifference {
027:
028: static final int INSERT = 0;
029: static final int DELETE = 1;
030:
031: LinkedRangeDifference fNext;
032:
033: /*
034: * Creates a LinkedRangeDifference an initializes it to the error state
035: */
036: LinkedRangeDifference() {
037: super (ERROR);
038: fNext = null;
039: }
040:
041: /*
042: * Constructs and links a LinkeRangeDifference to another LinkedRangeDifference
043: */
044: LinkedRangeDifference(LinkedRangeDifference next, int operation) {
045: super (operation);
046: fNext = next;
047: }
048:
049: /*
050: * Follows the next link
051: */
052: LinkedRangeDifference getNext() {
053: return fNext;
054: }
055:
056: boolean isDelete() {
057: return kind() == DELETE;
058: }
059:
060: boolean isInsert() {
061: return kind() == INSERT;
062: }
063:
064: /*
065: * Sets the next link of this LinkedRangeDifference
066: */
067: void setNext(LinkedRangeDifference next) {
068: fNext = next;
069: }
070: }
071:
072: public static RangeDifference[] findDifferences(
073: IProgressMonitor pm, IRangeComparator left,
074: IRangeComparator right) {
075:
076: // assert that both IRangeComparators are of the same class
077: Assert.isTrue(right.getClass().equals(left.getClass()));
078:
079: int rightSize = right.getRangeCount();
080: int leftSize = left.getRangeCount();
081: //
082: // Differences matrix:
083: // only the last d of each diagonal is stored, i.e., lastDiagonal[k] = row of d
084: //
085: int diagLen = 2 * Math.max(rightSize, leftSize); // bound on the size of edit script
086: int maxDiagonal = diagLen;
087: int lastDiagonal[] = new int[diagLen + 1]; // the row containing the last d
088: // on diagonal k (lastDiagonal[k] = row)
089: int origin = diagLen / 2; // origin of diagonal 0
090:
091: // script corresponding to d[k]
092: LinkedRangeDifference script[] = new LinkedRangeDifference[diagLen + 1];
093: int row, col;
094:
095: // find common prefix
096: for (row = 0; row < rightSize && row < leftSize
097: && rangesEqual(right, row, left, row) == true;)
098: row++;
099:
100: lastDiagonal[origin] = row;
101: script[origin] = null;
102: int lower = (row == rightSize) ? origin + 1 : origin - 1;
103: int upper = (row == leftSize) ? origin - 1 : origin + 1;
104:
105: if (lower > upper)
106: return EMPTY_RESULT;
107:
108: //System.out.println("findDifferences: " + maxDiagonal + " " + lower + " " + upper);
109:
110: // for each value of the edit distance
111: for (int d = 1; d <= maxDiagonal; ++d) { // d is the current edit distance
112:
113: if (pm != null)
114: pm.worked(1);
115:
116: if (right.skipRangeComparison(d, maxDiagonal, left))
117: return EMPTY_RESULT; // should be something we already found
118:
119: // for each relevant diagonal (-d, -d+2 ..., d-2, d)
120: for (int k = lower; k <= upper; k += 2) { // k is the current diagonal
121: LinkedRangeDifference edit;
122:
123: if (pm != null && pm.isCanceled())
124: return EMPTY_RESULT;
125:
126: if (k == origin - d || k != origin + d
127: && lastDiagonal[k + 1] >= lastDiagonal[k - 1]) {
128: //
129: // move down
130: //
131: row = lastDiagonal[k + 1] + 1;
132: edit = new LinkedRangeDifference(script[k + 1],
133: LinkedRangeDifference.DELETE);
134: } else {
135: //
136: // move right
137: //
138: row = lastDiagonal[k - 1];
139: edit = new LinkedRangeDifference(script[k - 1],
140: LinkedRangeDifference.INSERT);
141: }
142: col = row + k - origin;
143: edit.fRightStart = row;
144: edit.fLeftStart = col;
145: Assert.isTrue(k >= 0 && k <= maxDiagonal);
146: script[k] = edit;
147:
148: // slide down the diagonal as far as possible
149: while (row < rightSize && col < leftSize
150: && rangesEqual(right, row, left, col) == true) {
151: ++row;
152: ++col;
153: }
154:
155: Assert.isTrue(k >= 0 && k <= maxDiagonal); // Unreasonable value for diagonal index
156: lastDiagonal[k] = row;
157:
158: if (row == rightSize && col == leftSize) {
159: //showScript(script[k], right, left);
160: return createDifferencesRanges(script[k]);
161: }
162: if (row == rightSize)
163: lower = k + 2;
164: if (col == leftSize)
165: upper = k - 2;
166: }
167: --lower;
168: ++upper;
169: }
170: // too many differences
171: Assert.isTrue(false);
172: return null;
173: }
174:
175: /*
176: * Tests if two ranges are equal
177: */
178: private static boolean rangesEqual(IRangeComparator a, int ai,
179: IRangeComparator b, int bi) {
180: return a.rangesEqual(ai, b, bi);
181: }
182:
183: /*
184: * Creates a Vector of DifferencesRanges out of the LinkedRangeDifference.
185: * It coalesces adjacent changes.
186: * In addition, indices are changed such that the ranges are 1) open, i.e,
187: * the end of the range is not included, and 2) are zero based.
188: */
189: private static RangeDifference[] createDifferencesRanges(
190: LinkedRangeDifference start) {
191:
192: LinkedRangeDifference ep = reverseDifferences(start);
193: ArrayList result = new ArrayList();
194: RangeDifference es = null;
195:
196: while (ep != null) {
197: es = new RangeDifference(RangeDifference.CHANGE);
198:
199: if (ep.isInsert()) {
200: es.fRightStart = ep.fRightStart + 1;
201: es.fLeftStart = ep.fLeftStart;
202: RangeDifference b = ep;
203: do {
204: ep = ep.getNext();
205: es.fLeftLength++;
206: } while (ep != null && ep.isInsert()
207: && ep.fRightStart == b.fRightStart);
208: } else {
209: es.fRightStart = ep.fRightStart;
210: es.fLeftStart = ep.fLeftStart;
211:
212: RangeDifference a = ep;
213: //
214: // deleted lines
215: //
216: do {
217: a = ep;
218: ep = ep.getNext();
219: es.fRightLength++;
220: } while (ep != null && ep.isDelete()
221: && ep.fRightStart == a.fRightStart + 1);
222:
223: boolean change = (ep != null && ep.isInsert() && ep.fRightStart == a.fRightStart);
224:
225: if (change) {
226: RangeDifference b = ep;
227: //
228: // replacement lines
229: //
230: do {
231: ep = ep.getNext();
232: es.fLeftLength++;
233: } while (ep != null && ep.isInsert()
234: && ep.fRightStart == b.fRightStart);
235: } else {
236: es.fLeftLength = 0;
237: }
238: es.fLeftStart++; // meaning of range changes from "insert after", to "replace with"
239:
240: }
241: //
242: // the script commands are 1 based, subtract one to make them zero based
243: //
244: es.fRightStart--;
245: es.fLeftStart--;
246: result.add(es);
247: }
248: return (RangeDifference[]) result.toArray(EMPTY_RESULT);
249: }
250:
251: /*
252: * Reverses the range differences
253: */
254: private static LinkedRangeDifference reverseDifferences(
255: LinkedRangeDifference start) {
256: LinkedRangeDifference ep, behind, ahead;
257:
258: ahead = start;
259: ep = null;
260: while (ahead != null) {
261: behind = ep;
262: ep = ahead;
263: ahead = ahead.getNext();
264: ep.setNext(behind);
265: }
266: return ep;
267: }
268: }
|