RangeDifferencer


1   /*******************************************************************************
2    * Copyright (c) 2000, 2007 IBM Corporation and others.
3    * All rights reserved. This program and the accompanying materials
4    * are made available under the terms of the Eclipse Public License v1.0
5    * which accompanies this distribution, and is available at
6    * http://www.eclipse.org/legal/epl-v10.html
7    *
8    * Contributors:
9    *     IBM Corporation - initial API and implementation
10   *******************************************************************************/
11  package org.eclipse.compare.rangedifferencer;
12  
13  import java.util.ArrayList  ;
14  import java.util.List  ;
15  
16  import org.eclipse.compare.internal.CompareMessages;
17  import org.eclipse.compare.internal.CompareUIPlugin;
18  import org.eclipse.core.runtime.*;
19  
20  /**
21   * A <code>RangeDifferencer</code> finds the differences between two or three <code>IRangeComparator</code>s.
22   * <p>
23   * To use the differencer, clients provide an <code>IRangeComparator</code>
24   * that breaks their input data into a sequence of comparable entities. The differencer
25   * returns the differences among these sequences as an array of <code>RangeDifference</code> objects
26   * (<code>findDifferences</code> methods).
27   * Every <code>RangeDifference</code> represents a single kind of difference
28   * and the corresponding ranges of the underlying comparable entities in the
29   * left, right, and optionally ancestor sides.
30   * <p>
31   * Alternatively, the <code>findRanges</code> methods not only return objects for
32   * the differing ranges but for non-differing ranges too.
33   * <p>
34   * The algorithm used is an objectified version of one described in:
35   * <it>A File Comparison Program,</it> by Webb Miller and Eugene W. Myers, 
36   * Software Practice and Experience, Vol. 15, Nov. 1985.
37   *
38   * @see IRangeComparator
39   * @see RangeDifference
40   */
41  public final class RangeDifferencer {
42      
43      private static final RangeDifference[] EMPTY_RESULT= new RangeDifference[0];
44      
45      /* (non Javadoc)
46       * Cannot be instantiated!
47       */
48      private RangeDifferencer() {
49          // nothing to do
50      }
51      
52      /**
53       * Finds the differences between two <code>IRangeComparator</code>s.
54       * The differences are returned as an array of <code>RangeDifference</code>s.
55       * If no differences are detected an empty array is returned.
56       * 
57       * @param left the left range comparator
58       * @param right the right range comparator
59       * @return an array of range differences, or an empty array if no differences were found
60       */
61      public static RangeDifference[] findDifferences(IRangeComparator left, IRangeComparator right) {
62          return findDifferences((IProgressMonitor)null, left, right);
63      }
64      
65      /**
66       * Finds the differences between two <code>IRangeComparator</code>s.
67       * The differences are returned as an array of <code>RangeDifference</code>s.
68       * If no differences are detected an empty array is returned.
69       * 
70       * @param pm if not <code>null</code> used to report progress
71       * @param left the left range comparator
72       * @param right the right range comparator
73       * @return an array of range differences, or an empty array if no differences were found
74       * @since 2.0
75       */
76      public static RangeDifference[] findDifferences(IProgressMonitor pm, IRangeComparator left, IRangeComparator right) {
77          if (isUseOldDifferencer()) {
78              return OldDifferencer.findDifferences(pm, left, right);
79          }
80          return RangeComparatorLCS.findDifferences(pm, left, right);
81      }
82  
83      private static boolean isUseOldDifferencer() {
84          return CompareUIPlugin.getDefault().isUseOldDifferencer();
85      }
86  
87      /**
88       * Finds the differences among three <code>IRangeComparator</code>s.
89       * The differences are returned as a list of <code>RangeDifference</code>s.
90       * If no differences are detected an empty list is returned.
91       * If the ancestor range comparator is <code>null</code>, a two-way
92       * comparison is performed.
93       * 
94       * @param ancestor the ancestor range comparator or <code>null</code>
95       * @param left the left range comparator
96       * @param right the right range comparator
97       * @return an array of range differences, or an empty array if no differences were found
98       */
99      public static RangeDifference[] findDifferences(IRangeComparator ancestor, IRangeComparator left, IRangeComparator right) {
100         return findDifferences(null, ancestor, left, right);
101     }
102     
103     /**
104      * Finds the differences among three <code>IRangeComparator</code>s.
105      * The differences are returned as a list of <code>RangeDifference</code>s.
106      * If no differences are detected an empty list is returned.
107      * If the ancestor range comparator is <code>null</code>, a two-way
108      * comparison is performed.
109      * 
110      * @param pm if not <code>null</code> used to report progress
111      * @param ancestor the ancestor range comparator or <code>null</code>
112      * @param left the left range comparator
113      * @param right the right range comparator
114      * @return an array of range differences, or an empty array if no differences were found
115      * @since 2.0
116      */
117     public static RangeDifference[] findDifferences(IProgressMonitor pm, IRangeComparator ancestor, IRangeComparator left, IRangeComparator right) {
118         try {
119             if (ancestor == null)
120                 return findDifferences(pm, left, right);
121             SubMonitor monitor = SubMonitor.convert(pm, CompareMessages.RangeComparatorLCS_0, 100);
122             RangeDifference[] leftAncestorScript= null;
123             RangeDifference[] rightAncestorScript= findDifferences(monitor.newChild(50), ancestor, right);
124             if (rightAncestorScript != null) {
125                 monitor.setWorkRemaining(100);
126                 leftAncestorScript= findDifferences(monitor.newChild(50), ancestor, left);
127             }
128             if (rightAncestorScript == null || leftAncestorScript == null)
129                 return null;
130     
131             DifferencesIterator myIter= new DifferencesIterator(rightAncestorScript);
132             DifferencesIterator yourIter= new DifferencesIterator(leftAncestorScript);
133     
134             List   diff3= new ArrayList  ();
135             diff3.add(new RangeDifference(RangeDifference.ERROR)); // add a sentinel
136     
137             int changeRangeStart= 0;
138             int changeRangeEnd= 0;
139             //
140             // Combine the two two-way edit scripts into one
141             //
142             monitor.setWorkRemaining(rightAncestorScript.length + leftAncestorScript.length);
143             while (myIter.fDifference != null || yourIter.fDifference != null) {
144     
145                 DifferencesIterator startThread;
146                 myIter.removeAll();
147                 yourIter.removeAll();
148                 //
149                 // take the next diff that is closer to the start
150                 //
151                 if (myIter.fDifference == null)
152                     startThread= yourIter;
153                 else if (yourIter.fDifference == null)
154                     startThread= myIter;
155                 else { // not at end of both scripts take the lowest range
156                     if (myIter.fDifference.fLeftStart <= yourIter.fDifference.fLeftStart) // 2 -> common (Ancestor) change range
157                         startThread= myIter;
158                     else
159                         startThread= yourIter;
160                 }
161                 changeRangeStart= startThread.fDifference.fLeftStart;
162                 changeRangeEnd= startThread.fDifference.leftEnd();
163     
164                 startThread.next();
165                 monitor.worked(1);
166                 //
167                 // check for overlapping changes with other thread
168                 // merge overlapping changes with this range
169                 //
170                 DifferencesIterator other= startThread.other(myIter, yourIter);
171                 while (other.fDifference != null && other.fDifference.fLeftStart <= changeRangeEnd) {
172                     int newMax= other.fDifference.leftEnd();
173                     other.next();
174                     monitor.worked(1);
175                     if (newMax >= changeRangeEnd) {
176                         changeRangeEnd= newMax;
177                         other= other.other(myIter, yourIter);
178                     }
179                 }
180                 diff3.add(createRangeDifference3(myIter, yourIter, diff3, right, left, changeRangeStart, changeRangeEnd));
181             }
182     
183             // remove sentinel
184             diff3.remove(0);
185             return (RangeDifference[]) diff3.toArray(EMPTY_RESULT);
186         } finally {
187             if (pm != null)
188                 pm.done();
189         }
190     }
191 
192     /**
193      * Finds the differences among two <code>IRangeComparator</code>s.
194      * In contrast to <code>findDifferences</code>, the result
195      * contains <code>RangeDifference</code> elements for non-differing ranges too.
196      * 
197      * @param left the left range comparator
198      * @param right the right range comparator
199      * @return an array of range differences
200      */
201     public static RangeDifference[] findRanges(IRangeComparator left, IRangeComparator right) {
202         return findRanges((IProgressMonitor)null, left, right);
203     }
204     
205     /**
206      * Finds the differences among two <code>IRangeComparator</code>s.
207      * In contrast to <code>findDifferences</code>, the result
208      * contains <code>RangeDifference</code> elements for non-differing ranges too.
209      * 
210      * @param pm if not <code>null</code> used to report progress
211      * @param left the left range comparator
212      * @param right the right range comparator
213      * @return an array of range differences
214      * @since 2.0
215      */
216     public static RangeDifference[] findRanges(IProgressMonitor pm, IRangeComparator left, IRangeComparator right) {
217         RangeDifference[] in= findDifferences(pm, left, right);
218         List   out= new ArrayList  ();
219 
220         RangeDifference rd;
221 
222         int mstart= 0;
223         int ystart= 0;
224 
225         for (int i= 0; i < in.length; i++) {
226             RangeDifference es= in[i];
227 
228             rd= new RangeDifference(RangeDifference.NOCHANGE, mstart, es.rightStart() - mstart, ystart, es.leftStart() - ystart);
229             if (rd.maxLength() != 0)
230                 out.add(rd);
231 
232             out.add(es);
233 
234             mstart= es.rightEnd();
235             ystart= es.leftEnd();
236         }
237         rd= new RangeDifference(RangeDifference.NOCHANGE, mstart, right.getRangeCount() - mstart, ystart, left.getRangeCount() - ystart);
238         if (rd.maxLength() > 0)
239             out.add(rd);
240 
241         return (RangeDifference[]) out.toArray(EMPTY_RESULT);
242     }
243 
244     /**
245      * Finds the differences among three <code>IRangeComparator</code>s.
246      * In contrast to <code>findDifferences</code>, the result
247      * contains <code>RangeDifference</code> elements for non-differing ranges too.
248      * If the ancestor range comparator is <code>null</code>, a two-way
249      * comparison is performed.
250      * 
251      * @param ancestor the ancestor range comparator or <code>null</code>
252      * @param left the left range comparator
253      * @param right the right range comparator
254      * @return an array of range differences
255      */
256     public static RangeDifference[] findRanges(IRangeComparator ancestor, IRangeComparator left, IRangeComparator right) {
257         return findRanges(null, ancestor, left, right);
258     }
259     
260     /**
261      * Finds the differences among three <code>IRangeComparator</code>s.
262      * In contrast to <code>findDifferences</code>, the result
263      * contains <code>RangeDifference</code> elements for non-differing ranges too.
264      * If the ancestor range comparator is <code>null</code>, a two-way
265      * comparison is performed.
266      * 
267      * @param pm if not <code>null</code> used to report progress
268      * @param ancestor the ancestor range comparator or <code>null</code>
269      * @param left the left range comparator
270      * @param right the right range comparator
271      * @return an array of range differences
272      * @since 2.0
273      */
274     public static RangeDifference[] findRanges(IProgressMonitor pm, IRangeComparator ancestor, IRangeComparator left, IRangeComparator right) {
275 
276         if (ancestor == null)
277             return findRanges(pm, left, right);
278 
279         RangeDifference[] in= findDifferences(pm, ancestor, left, right);
280         List   out= new ArrayList  ();
281 
282         RangeDifference rd;
283 
284         int mstart= 0;
285         int ystart= 0;
286         int astart= 0;
287 
288         for (int i= 0; i < in.length; i++) {
289             RangeDifference es= in[i];
290 
291             rd= new RangeDifference(RangeDifference.NOCHANGE, mstart, es.rightStart() - mstart, ystart, es.leftStart() - ystart, astart, es.ancestorStart() - astart);
292             if (rd.maxLength() > 0)
293                 out.add(rd);
294 
295             out.add(es);
296 
297             mstart= es.rightEnd();
298             ystart= es.leftEnd();
299             astart= es.ancestorEnd();
300         }
301         rd= new RangeDifference(RangeDifference.NOCHANGE, mstart, right.getRangeCount() - mstart, ystart, left.getRangeCount() - ystart, astart, ancestor.getRangeCount() - astart);
302         if (rd.maxLength() > 0)
303             out.add(rd);
304 
305         return (RangeDifference[]) out.toArray(EMPTY_RESULT);
306     }
307 
308     //---- private methods
309 
310     /*
311      * Creates a <code>RangeDifference3</code> given the
312      * state of two DifferenceIterators.
313      */
314     private static RangeDifference createRangeDifference3(DifferencesIterator myIter, DifferencesIterator yourIter, List   diff3, 
315         IRangeComparator right, IRangeComparator left, int changeRangeStart,  int changeRangeEnd) {
316 
317         int rightStart, rightEnd;
318         int leftStart, leftEnd;
319         int kind= RangeDifference.ERROR;
320         RangeDifference last= (RangeDifference) diff3.get(diff3.size() - 1);
321 
322         Assert.isTrue((myIter.getCount() != 0 || yourIter.getCount() != 0));    // At least one range array must be non-empty
323         //
324         // find corresponding lines to fChangeRangeStart/End in right and left
325         //
326         if (myIter.getCount() == 0) { // only left changed
327             rightStart= changeRangeStart - last.ancestorEnd() + last.rightEnd();
328             rightEnd= changeRangeEnd - last.ancestorEnd() + last.rightEnd();
329             kind= RangeDifference.LEFT;
330         } else {
331             RangeDifference f= (RangeDifference) myIter.fRange.get(0);
332             RangeDifference l= (RangeDifference) myIter.fRange.get(myIter.fRange.size() - 1);
333             rightStart= changeRangeStart - f.fLeftStart + f.fRightStart;
334             rightEnd= changeRangeEnd - l.leftEnd() + l.rightEnd();
335         }
336 
337         if (yourIter.getCount() == 0) { // only right changed
338             leftStart= changeRangeStart - last.ancestorEnd() + last.leftEnd();
339             leftEnd= changeRangeEnd - last.ancestorEnd() + last.leftEnd();
340             kind= RangeDifference.RIGHT;
341         } else {
342             RangeDifference f= (RangeDifference) yourIter.fRange.get(0);
343             RangeDifference l= (RangeDifference) yourIter.fRange.get(yourIter.fRange.size() - 1);
344             leftStart= changeRangeStart - f.fLeftStart + f.fRightStart;
345             leftEnd= changeRangeEnd - l.leftEnd() + l.rightEnd();
346         }
347 
348         if (kind == RangeDifference.ERROR) { // overlapping change (conflict) -> compare the changed ranges
349             if (rangeSpansEqual(right, rightStart, rightEnd - rightStart, left, leftStart, leftEnd - leftStart))
350                 kind= RangeDifference.ANCESTOR;
351             else
352                 kind= RangeDifference.CONFLICT;
353         }
354         return new RangeDifference(kind, rightStart, rightEnd - rightStart, leftStart, leftEnd - leftStart, changeRangeStart, changeRangeEnd - changeRangeStart);
355     }
356 
357     /*
358      * Tests whether <code>right</code> and <code>left</code> changed in the same way
359      */
360     private static boolean rangeSpansEqual(IRangeComparator right, int rightStart, int rightLen, IRangeComparator left, int leftStart, int leftLen) {
361         if (rightLen == leftLen) {
362             int i= 0;
363             for (i= 0; i < rightLen; i++) {
364                 if (!rangesEqual(right, rightStart + i, left, leftStart + i))
365                     break;
366             }
367             if (i == rightLen)
368                 return true;
369         }
370         return false;
371     }
372     
373     /*
374      * Tests if two ranges are equal
375      */
376     private static boolean rangesEqual(IRangeComparator a, int ai, IRangeComparator b, int bi) {
377         return a.rangesEqual(ai, b, bi);
378     }
379 }
380 
381
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags