OldDifferencer


1   /*******************************************************************************
2    * Copyright (c) 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.compare.rangedifferencer;
12  
13  import java.util.ArrayList  ;
14  
15  import org.eclipse.core.runtime.Assert;
16  import org.eclipse.core.runtime.IProgressMonitor;
17  
18  /**
19   * The algorithm used is an objectified version of one described in:
20   * <it>A File Comparison Program,</it> by Webb Miller and Eugene W. Myers, 
21   * Software Practice and Experience, Vol. 15, Nov. 1985.
22   */
23  /* package */ class OldDifferencer {
24      
25      private static final RangeDifference[] EMPTY_RESULT= new RangeDifference[0];
26  
27      private static class LinkedRangeDifference extends RangeDifference {
28  
29          static final int INSERT= 0;
30          static final int DELETE= 1;
31  
32          LinkedRangeDifference fNext;
33  
34          /*
35           * Creates a LinkedRangeDifference an initializes it to the error state
36           */
37          LinkedRangeDifference() {
38              super(ERROR);
39              fNext= null;
40          }
41  
42          /*
43           * Constructs and links a LinkeRangeDifference to another LinkedRangeDifference
44           */
45          LinkedRangeDifference(LinkedRangeDifference next, int operation) {
46              super(operation);
47              fNext= next;
48          }
49  
50          /*
51           * Follows the next link
52           */
53          LinkedRangeDifference getNext() {
54              return fNext;
55          }
56  
57          boolean isDelete() {
58              return kind() == DELETE;
59          }
60  
61          boolean isInsert() {
62              return kind() == INSERT;
63          }
64  
65          /*
66           * Sets the next link of this LinkedRangeDifference
67           */
68          void setNext(LinkedRangeDifference next) {
69              fNext= next;
70          }
71      }
72      
73      public static RangeDifference[] findDifferences(IProgressMonitor pm, IRangeComparator left, IRangeComparator right) {
74  
75          // assert that both IRangeComparators are of the same class
76          Assert.isTrue(right.getClass().equals(left.getClass()));
77  
78          int rightSize= right.getRangeCount();
79          int leftSize= left.getRangeCount();
80          //
81          // Differences matrix:
82          // only the last d of each diagonal is stored, i.e., lastDiagonal[k] = row of d    
83          //
84          int diagLen= 2 * Math.max(rightSize, leftSize); // bound on the size of edit script
85          int maxDiagonal= diagLen;
86          int lastDiagonal[]= new int[diagLen + 1]; // the row containing the last d
87          // on diagonal k (lastDiagonal[k] = row)
88          int origin= diagLen / 2; // origin of diagonal 0
89  
90          // script corresponding to d[k] 
91          LinkedRangeDifference script[]= new LinkedRangeDifference[diagLen + 1];
92          int row, col;
93  
94          // find common prefix
95          for (row= 0; row < rightSize && row < leftSize && rangesEqual(right, row, left, row) == true;)
96              row++;
97  
98          lastDiagonal[origin]= row;
99          script[origin]= null;
100         int lower= (row == rightSize) ? origin + 1 : origin - 1;
101         int upper= (row == leftSize) ? origin - 1 : origin + 1;
102 
103         if (lower > upper)
104             return EMPTY_RESULT;
105             
106         //System.out.println("findDifferences: " + maxDiagonal + " " + lower + " " + upper);
107         
108         // for each value of the edit distance
109         for (int d= 1; d <= maxDiagonal; ++d) { // d is the current edit distance
110             
111             if (pm != null)
112                 pm.worked(1);
113 
114             if (right.skipRangeComparison(d, maxDiagonal, left))
115                 return EMPTY_RESULT; // should be something we already found
116 
117             // for each relevant diagonal (-d, -d+2 ..., d-2, d)
118             for (int k= lower; k <= upper; k += 2) { // k is the current diagonal
119                 LinkedRangeDifference edit;
120 
121                 if (pm != null && pm.isCanceled())
122                     return EMPTY_RESULT;
123 
124                 if (k == origin - d || k != origin + d && lastDiagonal[k + 1] >= lastDiagonal[k - 1]) {
125                     //
126                     // move down
127                     //
128                     row= lastDiagonal[k + 1] + 1;
129                     edit= new LinkedRangeDifference(script[k + 1], LinkedRangeDifference.DELETE);
130                 } else {
131                     //
132                     // move right
133                     //
134                     row= lastDiagonal[k - 1];
135                     edit= new LinkedRangeDifference(script[k - 1], LinkedRangeDifference.INSERT);
136                 }
137                 col= row + k - origin;
138                 edit.fRightStart= row;
139                 edit.fLeftStart= col;
140                 Assert.isTrue(k >= 0 && k <= maxDiagonal);
141                 script[k]= edit;
142 
143                 // slide down the diagonal as far as possible 
144                 while (row < rightSize && col < leftSize && rangesEqual(right, row, left, col) == true) {
145                     ++row;
146                     ++col;
147                 }
148 
149                 Assert.isTrue(k >= 0 && k <= maxDiagonal); // Unreasonable value for diagonal index
150                 lastDiagonal[k]= row;
151 
152                 if (row == rightSize && col == leftSize) {
153                     //showScript(script[k], right, left);
154                     return createDifferencesRanges(script[k]);
155                 }
156                 if (row == rightSize)
157                     lower= k + 2;
158                 if (col == leftSize)
159                     upper= k - 2;
160             }
161             --lower;
162             ++upper;
163         }
164         // too many differences
165         Assert.isTrue(false);
166         return null;
167     }
168     
169     /*
170      * Tests if two ranges are equal
171      */
172     private static boolean rangesEqual(IRangeComparator a, int ai, IRangeComparator b, int bi) {
173         return a.rangesEqual(ai, b, bi);
174     }
175     
176     /*
177      * Creates a Vector of DifferencesRanges out of the LinkedRangeDifference.
178      * It coalesces adjacent changes.
179      * In addition, indices are changed such that the ranges are 1) open, i.e,
180      * the end of the range is not included, and 2) are zero based.
181      */
182     private static RangeDifference[] createDifferencesRanges(LinkedRangeDifference start) {
183 
184         LinkedRangeDifference ep= reverseDifferences(start);
185         ArrayList   result= new ArrayList  ();
186         RangeDifference es= null;
187 
188         while (ep != null) {
189             es= new RangeDifference(RangeDifference.CHANGE);
190 
191             if (ep.isInsert()) {
192                 es.fRightStart= ep.fRightStart + 1;
193                 es.fLeftStart= ep.fLeftStart;
194                 RangeDifference b= ep;
195                 do {
196                     ep= ep.getNext();
197                     es.fLeftLength++;
198                 } while (ep != null && ep.isInsert() && ep.fRightStart == b.fRightStart);
199             } else {
200                 es.fRightStart= ep.fRightStart;
201                 es.fLeftStart= ep.fLeftStart;
202 
203                 RangeDifference a= ep;
204                 //
205                 // deleted lines
206                 //
207                 do {
208                     a= ep;
209                     ep= ep.getNext();
210                     es.fRightLength++;
211                 } while (ep != null && ep.isDelete() && ep.fRightStart == a.fRightStart + 1);
212 
213                 boolean change= (ep != null && ep.isInsert() && ep.fRightStart == a.fRightStart);
214 
215                 if (change) {
216                     RangeDifference b= ep;
217                     //
218                     // replacement lines
219                     //
220                     do {
221                         ep= ep.getNext();
222                         es.fLeftLength++;
223                     } while (ep != null && ep.isInsert() && ep.fRightStart == b.fRightStart);
224                 } else {
225                     es.fLeftLength= 0;
226                 }
227                 es.fLeftStart++; // meaning of range changes from "insert after", to "replace with"
228 
229             }
230             //
231             // the script commands are 1 based, subtract one to make them zero based
232             //
233             es.fRightStart--;
234             es.fLeftStart--;
235             result.add(es);
236         }
237         return (RangeDifference[]) result.toArray(EMPTY_RESULT);
238     }
239     
240     /*
241      * Reverses the range differences
242      */
243     private static LinkedRangeDifference reverseDifferences(LinkedRangeDifference start) {
244         LinkedRangeDifference ep, behind, ahead;
245 
246         ahead= start;
247         ep= null;
248         while (ahead != null) {
249             behind= ep;
250             ep= ahead;
251             ahead= ahead.getNext();
252             ep.setNext(behind);
253         }
254         return ep;
255     }
256 }
257
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags