001: /*******************************************************************************
002: * Copyright (c) 2006, 2007 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: import java.util.List;
014:
015: import org.eclipse.compare.internal.CompareMessages;
016: import org.eclipse.compare.internal.LCS;
017: import org.eclipse.compare.internal.LCSSettings;
018: import org.eclipse.core.runtime.*;
019:
020: /* package */class RangeComparatorLCS extends LCS {
021:
022: private final IRangeComparator comparator1, comparator2;
023: private int[][] lcs;
024:
025: public static RangeDifference[] findDifferences(
026: IProgressMonitor pm, LCSSettings settings,
027: IRangeComparator left, IRangeComparator right) {
028: RangeComparatorLCS lcs = new RangeComparatorLCS(left, right);
029: SubMonitor monitor = SubMonitor.convert(pm,
030: CompareMessages.RangeComparatorLCS_0, 100);
031: try {
032: lcs
033: .longestCommonSubsequence(monitor.newChild(95),
034: settings);
035: return lcs.getDifferences(monitor.newChild(5));
036: } finally {
037: if (pm != null)
038: pm.done();
039: }
040: }
041:
042: public RangeComparatorLCS(IRangeComparator comparator1,
043: IRangeComparator comparator2) {
044: this .comparator1 = comparator1;
045: this .comparator2 = comparator2;
046: }
047:
048: protected int getLength1() {
049: return comparator1.getRangeCount();
050: }
051:
052: protected int getLength2() {
053: return comparator2.getRangeCount();
054: }
055:
056: protected void initializeLcs(int lcsLength) {
057: lcs = new int[2][lcsLength];
058: }
059:
060: protected boolean isRangeEqual(int i1, int i2) {
061: return comparator1.rangesEqual(i1, comparator2, i2);
062: }
063:
064: protected void setLcs(int sl1, int sl2) {
065: // Add one to the values so that 0 can mean that the slot is empty
066: lcs[0][sl1] = sl1 + 1;
067: lcs[1][sl1] = sl2 + 1;
068: }
069:
070: public RangeDifference[] getDifferences(SubMonitor subMonitor) {
071: try {
072: List differences = new ArrayList();
073: int length = getLength();
074: if (length == 0) {
075: differences.add(new RangeDifference(
076: RangeDifference.CHANGE, 0, comparator2
077: .getRangeCount(), 0, comparator1
078: .getRangeCount()));
079: } else {
080: subMonitor.beginTask(null, length);
081: int index1, index2;
082: index1 = index2 = 0;
083: int l1, l2;
084: int s1 = -1;
085: int s2 = -1;
086: while (index1 < lcs[0].length && index2 < lcs[1].length) {
087: // Move both LCS lists to the next occupied slot
088: while ((l1 = lcs[0][index1]) == 0) {
089: index1++;
090: if (index1 >= lcs[0].length)
091: break;
092: }
093: if (index1 >= lcs[0].length)
094: break;
095: while ((l2 = lcs[1][index2]) == 0) {
096: index2++;
097: if (index2 >= lcs[1].length)
098: break;
099: }
100: if (index2 >= lcs[1].length)
101: break;
102: // Convert the entry to an array index (see setLcs(int, int))
103: int end1 = l1 - 1;
104: int end2 = l2 - 1;
105: if (s1 == -1 && (end1 != 0 || end2 != 0)) {
106: // There is a diff at the beginning
107: // TODO: We need to conform that this is the proper order
108: differences.add(new RangeDifference(
109: RangeDifference.CHANGE, 0, end2, 0,
110: end1));
111: } else if (end1 != s1 + 1 || end2 != s2 + 1) {
112: // A diff was found on one of the sides
113: int leftStart = s1 + 1;
114: int leftLength = end1 - leftStart;
115: int rightStart = s2 + 1;
116: int rightLength = end2 - rightStart;
117: // TODO: We need to conform that this is the proper order
118: differences.add(new RangeDifference(
119: RangeDifference.CHANGE, rightStart,
120: rightLength, leftStart, leftLength));
121: }
122: s1 = end1;
123: s2 = end2;
124: index1++;
125: index2++;
126: worked(subMonitor, 1);
127: }
128: if (s1 != -1
129: && (s1 + 1 < comparator1.getRangeCount() || s2 + 1 < comparator2
130: .getRangeCount())) {
131: // TODO: we need to find the proper way of representing an append
132: int leftStart = s1 < comparator1.getRangeCount() ? s1 + 1
133: : s1;
134: int rightStart = s2 < comparator2.getRangeCount() ? s2 + 1
135: : s2;
136: // TODO: We need to conform that this is the proper order
137: differences.add(new RangeDifference(
138: RangeDifference.CHANGE, rightStart,
139: comparator2.getRangeCount() - (s2 + 1),
140: leftStart, comparator1.getRangeCount()
141: - (s1 + 1)));
142: }
143:
144: }
145: return (RangeDifference[]) differences
146: .toArray(new RangeDifference[differences.size()]);
147: } finally {
148: subMonitor.done();
149: }
150: }
151:
152: private void worked(SubMonitor subMonitor, int work) {
153: if (subMonitor.isCanceled())
154: throw new OperationCanceledException();
155: subMonitor.worked(work);
156: }
157:
158: }
|