RangeDifferencer


1   /*******************************************************************************
2    * Copyright (c) 2000, 2006 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.ui.internal.texteditor.quickdiff.compare.rangedifferencer;
12  
13  import java.util.ArrayList  ;
14  import java.util.Arrays  ;
15  import java.util.List  ;
16  
17  import org.eclipse.core.runtime.Assert;
18  import org.eclipse.core.runtime.IProgressMonitor;
19  
20  
21  import org.eclipse.ui.internal.texteditor.quickdiff.compare.rangedifferencer.LinkedRangeFactory.LowMemoryException;
22  
23  /**
24   * A <code>RangeDifferencer</code> finds the differences between two or three <code>IRangeComparator</code>s.
25   * <p>
26   * To use the differencer, clients provide an <code>IRangeComparator</code>
27   * that breaks their input data into a sequence of comparable entities. The differencer
28   * returns the differences among these sequences as an array of <code>RangeDifference</code> objects
29   * (<code>findDifferences</code> methods).
30   * Every <code>RangeDifference</code> represents a single kind of difference
31   * and the corresponding ranges of the underlying comparable entities in the
32   * left, right, and optionally ancestor sides.
33   * <p>
34   * Alternatively, the <code>findRanges</code> methods not only return objects for
35   * the differing ranges but for non-differing ranges too.
36   * <p>
37   * The algorithm used is an objectified version of one described in:
38   * <it>A File Comparison Program,</it> by Webb Miller and Eugene W. Myers,
39   * Software Practice and Experience, Vol. 15, Nov. 1985.
40   *
41   * @see IRangeComparator
42   * @see RangeDifference
43   * @since 3.0
44   */
45  public final class RangeDifferencer {
46  
47      private static final RangeDifference[] EMPTY_RESULT= new RangeDifference[0];
48  
49      /*
50       * Non instantiateable!
51       */
52      private RangeDifferencer() {
53      }
54  
55      /**
56       * Finds the differences between two <code>IRangeComparator</code>s.
57       * The differences are returned as an array of <code>RangeDifference</code>s.
58       * If no differences are detected an empty array is returned.
59       *
60       * @param left the left range comparator
61       * @param right the right range comparator
62       * @return an array of range differences, or an empty array if no differences were found
63       */
64      public static RangeDifference[] findDifferences(IRangeComparator left, IRangeComparator right) {
65          return findDifferences((IProgressMonitor)null, left, right);
66      }
67  
68      /**
69       * Finds the differences between two <code>IRangeComparator</code>s.
70       * The differences are returned as an array of <code>RangeDifference</code>s.
71       * If no differences are detected an empty array is returned.
72       *
73       * @param pm if not <code>null</code> used to report progress
74       * @param left the left range comparator
75       * @param right the right range comparator
76       * @return an array of range differences, or an empty array if no differences were found
77       * @since 2.0
78       */
79      private static RangeDifference[] findDifferences(IProgressMonitor pm, IRangeComparator left, IRangeComparator right) {
80          try {
81              return findDifferencesUkkonen(pm, left, right);
82          } catch (LowMemoryException e) {
83              return Levenshtein.findDifferences(pm, left, right);
84          }
85      }
86  
87      /**
88       * Finds the differences between two <code>IRangeComparator</code>s.
89       * The differences are returned as an array of <code>RangeDifference</code>s.
90       * If no differences are detected an empty array is returned.
91       *
92       * @param pm if not <code>null</code> used to report progress
93       * @param left the left range comparator
94       * @param right the right range comparator
95       * @return an array of range differences, or an empty array if no differences were found
96       * @throws LowMemoryException if the differencer runs out of memory
97       * @since 2.0
98       */
99      private static RangeDifference[] findDifferencesUkkonen(IProgressMonitor pm, IRangeComparator left, IRangeComparator right) throws LowMemoryException {
100 
101         // assert that both IRangeComparators are of the same class
102         Assert.isTrue(right.getClass().equals(left.getClass()));
103 
104         int rightSize= right.getRangeCount();
105         int leftSize= left.getRangeCount();
106         //
107         // Differences matrix:
108         // only the last d of each diagonal is stored, i.e., lastDiagonal[k] = row of d
109         //
110         int diagLen= 2 * Math.max(rightSize, leftSize); // bound on the size of edit script
111         int maxDiagonal= diagLen;
112         int lastDiagonal[]= new int[diagLen + 1]; // the row containing the last d
113         Arrays.fill(lastDiagonal, -1);
114         // on diagonal k (lastDiagonal[k] = row)
115         int origin= diagLen / 2; // origin of diagonal 0
116 
117         // script corresponding to d[k]
118         LinkedRangeDifference script[]= new LinkedRangeDifference[diagLen + 1];
119         int row, col;
120 
121         // find common prefix
122         for (row= 0; row < rightSize && row < leftSize && rangesEqual(right, row, left, row); ++row) {
123             // do nothing
124         }
125 
126         lastDiagonal[origin]= row;
127         script[origin]= null;
128         int lower= (row == rightSize) ? origin + 1 : origin - 1;
129         int upper= (row == leftSize) ? origin - 1 : origin + 1;
130 
131         if (lower > upper)
132             return EMPTY_RESULT;
133 
134         //System.out.println("findDifferences: " + maxDiagonal + " " + lower + " " + upper);
135         LinkedRangeFactory factory= new LinkedRangeFactory();
136 
137         // for each value of the edit distance
138         for (int d= 1; d <= maxDiagonal; ++d) { // d is the current edit distance
139 
140             if (pm != null)
141                 pm.worked(1);
142 
143             if (right.skipRangeComparison(d, maxDiagonal, left))
144                 return EMPTY_RESULT; // should be something we already found
145 
146             // for each relevant diagonal (-d, -d+2 ..., d-2, d)
147             for (int k= lower; k <= upper; k += 2) { // k is the current diagonal
148                 LinkedRangeDifference edit;
149 
150                 if (pm != null && pm.isCanceled())
151                     return EMPTY_RESULT;
152 
153                 if (k == origin - d || k != origin + d && lastDiagonal[k + 1] >= lastDiagonal[k - 1]) {
154                     //
155                     // move down
156                     //
157                     row= lastDiagonal[k + 1] + 1;
158                     edit= factory.newRange(script[k + 1], LinkedRangeDifference.DELETE);
159                 } else {
160                     //
161                     // move right
162                     //
163                     row= lastDiagonal[k - 1];
164                     edit= factory.newRange(script[k - 1], LinkedRangeDifference.INSERT);
165                 }
166                 col= row + k - origin;
167                 edit.fRightStart= row;
168                 edit.fLeftStart= col;
169                 Assert.isTrue(k >= 0 && k <= maxDiagonal);
170                 script[k]= edit;
171 
172                 // slide down the diagonal as far as possible
173                 while (row < rightSize && col < leftSize && rangesEqual(right, row, left, col) == true) {
174                     ++row;
175                     ++col;
176                 }
177 
178                 Assert.isTrue(k >= 0 && k <= maxDiagonal); // Unreasonable value for diagonal index
179                 lastDiagonal[k]= row;
180 
181                 if (row == rightSize && col == leftSize) {
182                     //showScript(script[k], right, left);
183                     return createDifferencesRanges(script[k]);
184                 }
185                 if (row == rightSize)
186                     lower= k + 2;
187                 if (col == leftSize)
188                     upper= k - 2;
189             }
190             --lower;
191             ++upper;
192         }
193         // too many differences
194         Assert.isTrue(false);
195         return null;
196     }
197 
198     /**
199      * Finds the differences among two <code>IRangeComparator</code>s.
200      * In contrast to <code>findDifferences</code>, the result
201      * contains <code>RangeDifference</code> elements for non-differing ranges too.
202      *
203      * @param left the left range comparator
204      * @param right the right range comparator
205      * @return an array of range differences
206      */
207     public static List   findRanges(IRangeComparator left, IRangeComparator right) {
208         return findRanges((IProgressMonitor)null, left, right);
209     }
210 
211     /**
212      * Finds the differences among two <code>IRangeComparator</code>s.
213      * In contrast to <code>findDifferences</code>, the result
214      * contains <code>RangeDifference</code> elements for non-differing ranges too.
215      *
216      * @param pm if not <code>null</code> used to report progress
217      * @param left the left range comparator
218      * @param right the right range comparator
219      * @return an array of range differences
220      * @since 2.0
221      */
222     public static List   findRanges(IProgressMonitor pm, IRangeComparator left, IRangeComparator right) {
223         RangeDifference[] in= findDifferences(pm, left, right);
224         List   out= new ArrayList  ();
225 
226         RangeDifference rd;
227 
228         int mstart= 0;
229         int ystart= 0;
230 
231         for (int i= 0; i < in.length; i++) {
232             RangeDifference es= in[i];
233 
234             rd= new RangeDifference(RangeDifference.NOCHANGE, mstart, es.rightStart() - mstart, ystart, es.leftStart() - ystart);
235             if (rd.maxLength() != 0)
236                 out.add(rd);
237 
238             out.add(es);
239 
240             mstart= es.rightEnd();
241             ystart= es.leftEnd();
242         }
243         rd= new RangeDifference(RangeDifference.NOCHANGE, mstart, right.getRangeCount() - mstart, ystart, left.getRangeCount() - ystart);
244         if (rd.maxLength() > 0)
245             out.add(rd);
246 
247         return out;
248     }
249 
250     //---- private methods
251 
252     /**
253      * Creates an array <code>DifferencesRanges</code> out of the
254      * <code>LinkedRangeDifference</code>. It coalesces adjacent changes. In
255      * addition, indices are changed such that the ranges are 1) open, i.e, the
256      * end of the range is not included, and 2) are zero based.
257      *
258      * @param start the start difference
259      * @return the created array of difference ranges
260      */
261     private static RangeDifference[] createDifferencesRanges(LinkedRangeDifference start) {
262 
263         LinkedRangeDifference ep= reverseDifferences(start);
264         ArrayList   result= new ArrayList  ();
265         RangeDifference es= null;
266 
267         while (ep != null) {
268             es= new RangeDifference(RangeDifference.CHANGE);
269 
270             if (ep.isInsert()) {
271                 es.fRightStart= ep.fRightStart + 1;
272                 es.fLeftStart= ep.fLeftStart;
273                 RangeDifference b= ep;
274                 do {
275                     ep= ep.getNext();
276                     es.fLeftLength++;
277                 } while (ep != null && ep.isInsert() && ep.fRightStart == b.fRightStart);
278             } else {
279                 es.fRightStart= ep.fRightStart;
280                 es.fLeftStart= ep.fLeftStart;
281 
282                 RangeDifference a= ep;
283                 //
284                 // deleted lines
285                 //
286                 do {
287                     a= ep;
288                     ep= ep.getNext();
289                     es.fRightLength++;
290                 } while (ep != null && ep.isDelete() && ep.fRightStart == a.fRightStart + 1);
291 
292                 boolean change= (ep != null && ep.isInsert() && ep.fRightStart == a.fRightStart);
293 
294                 if (change) {
295                     RangeDifference b= ep;
296                     //
297                     // replacement lines
298                     //
299                     do {
300                         ep= ep.getNext();
301                         es.fLeftLength++;
302                     } while (ep != null && ep.isInsert() && ep.fRightStart == b.fRightStart);
303                 } else {
304                     es.fLeftLength= 0;
305                 }
306                 es.fLeftStart++; // meaning of range changes from "insert after", to "replace with"
307 
308             }
309             //
310             // the script commands are 1 based, subtract one to make them zero based
311             //
312             es.fRightStart--;
313             es.fLeftStart--;
314             result.add(es);
315         }
316         return (RangeDifference[]) result.toArray(EMPTY_RESULT);
317     }
318 
319     /**
320      * Tests whether two ranges at the given indices are equal.
321      *
322      * @param a the first comparator
323      * @param ai the index of the first range
324      * @param b the second comparator
325      * @param bi the index of the second range
326      * @return <code>true</code> if the ranges are equal, <code>false</code> otherwise
327      */
328     private static boolean rangesEqual(IRangeComparator a, int ai, IRangeComparator b, int bi) {
329         return a.rangesEqual(ai, b, bi);
330     }
331 
332     /**
333      * Reverses the list of range differences thus that the given start difference becomes the
334      * end of the list.
335      *
336      * @param start the start of the list
337      * @return the reverted list
338      */
339     private static LinkedRangeDifference reverseDifferences(LinkedRangeDifference start) {
340         LinkedRangeDifference ep, behind, ahead;
341 
342         ahead= start;
343         ep= null;
344         while (ahead != null) {
345             behind= ep;
346             ep= ahead;
347             ahead= ahead.getNext();
348             ep.setNext(behind);
349         }
350         return ep;
351     }
352 }
353 
354
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags