ComputeDiff


1   /*
2    * The contents of this file are subject to the terms of the Common Development
3    * and Distribution License (the License). You may not use this file except in
4    * compliance with the License.
5    *
6    * You can obtain a copy of the License at http://www.netbeans.org/cddl.html
7    * or http://www.netbeans.org/cddl.txt.
8    *
9    * When distributing Covered Code, include this CDDL Header Notice in each file
10   * and include the License file at http://www.netbeans.org/cddl.txt.
11   * If applicable, add the following below the CDDL Header, with the fields
12   * enclosed by brackets [] replaced by your own identifying information:
13   * "Portions Copyrighted [year] [name of copyright owner]"
14   *
15   * The Original Software is NetBeans. The Initial Developer of the Original
16   * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
17   * Microsystems, Inc. All Rights Reserved.
18   */
19  package org.netbeans.modules.java.source.save;
20  
21  import java.util.*;
22  
23  
24  /**
25   * Compares two collections, returning a list of the additions, changes, and
26   * deletions between them. A <code>Comparator</code> may be passed as an
27   * argument to the constructor, and will thus be used. If not provided, the
28   * initial value in the <code>a</code> ("from") collection will be looked at to
29   * see if it supports the <code>Comparable</code> interface. If so, its
30   * <code>equals</code> and <code>compareTo</code> methods will be invoked on the
31   * instances in the "from" and "to" collections; otherwise, for speed, hash
32   * codes from the objects will be used instead for comparison.
33   *
34   * <p>The file FileDiff.java shows an example usage of this class, in an
35   * application similar to the Unix "diff" program.</p>
36   */
37  public class ComputeDiff {
38      /**
39       * The source array, AKA the "from" values.
40       */
41      protected Object  [] a;
42      
43      /**
44       * The target array, AKA the "to" values.
45       */
46      protected Object  [] b;
47      
48      /**
49       * The list of differences, as <code>Difference</code> instances.
50       */
51      protected List diffs = new ArrayList();
52      
53      /**
54       * The pending, uncommitted difference.
55       */
56      private Difference pending;
57      
58      /**
59       * The comparator used, if any.
60       */
61      private Comparator comparator;
62      
63      /**
64       * The thresholds.
65       */
66      private TreeMap thresh;
67      
68      /**
69       * Constructs the Diff object for the two arrays, using the given comparator.
70       */
71      public ComputeDiff(Object  [] a, Object  [] b, Comparator comp) {
72          this.a = a;
73          this.b = b;
74          this.comparator = comp;
75          this.thresh = null;     // created in getLongestCommonSubsequences
76      }
77      
78      /**
79       * Constructs the Diff object for the two arrays, using the default
80       * comparison mechanism between the objects, such as <code>equals</code> and
81       * <code>compareTo</code>.
82       */
83      public ComputeDiff(Object  [] a, Object  [] b) {
84          this(a, b, null);
85      }
86      
87      /**
88       * Constructs the Diff object for the two collections, using the given
89       * comparator.
90       */
91      public ComputeDiff(Collection a, Collection b, Comparator comp) {
92          this(a.toArray(), b.toArray(), comp);
93      }
94      
95      /**
96       * Constructs the Diff object for the two collections, using the default
97       * comparison mechanism between the objects, such as <code>equals</code> and
98       * <code>compareTo</code>.
99       */
100     public ComputeDiff(Collection a, Collection b) {
101         this(a, b, null);
102     }
103     
104     /**
105      * Runs diff and returns the results.
106      */
107     public List diff() {
108         traverseSequences();
109         
110         // add the last difference, if pending:
111         if (pending != null) {
112             diffs.add(pending);
113         }
114         
115         return diffs;
116     }
117     
118     /**
119      * Traverses the sequences, seeking the longest common subsequences,
120      * invoking the methods <code>finishedA</code>, <code>finishedB</code>,
121      * <code>onANotB</code>, and <code>onBNotA</code>.
122      */
123     protected void traverseSequences() {
124         Integer  [] matches = getLongestCommonSubsequences();
125         
126         int lastA = a.length - 1;
127         int lastB = b.length - 1;
128         int bi = 0;
129         int ai;
130         
131         int lastMatch = matches.length - 1;
132         
133         for (ai = 0; ai <= lastMatch; ++ai) {
134             Integer   bLine = matches[ai];
135             
136             if (bLine == null) {
137                 onANotB(ai, bi);
138             } else {
139                 while (bi < bLine.intValue()) {
140                     onBNotA(ai, bi++);
141                 }
142                 
143                 onMatch(ai, bi++);
144             }
145         }
146         
147         boolean calledFinishA = false;
148         boolean calledFinishB = false;
149         
150         while (ai <= lastA || bi <= lastB) {
151             
152             // last A?
153             if (ai == lastA + 1 && bi <= lastB) {
154                 if (!calledFinishA && callFinishedA()) {
155                     finishedA(lastA);
156                     calledFinishA = true;
157                 } else {
158                     while (bi <= lastB) {
159                         onBNotA(ai, bi++);
160                     }
161                 }
162             }
163             
164             // last B?
165             if (bi == lastB + 1 && ai <= lastA) {
166                 if (!calledFinishB && callFinishedB()) {
167                     finishedB(lastB);
168                     calledFinishB = true;
169                 } else {
170                     while (ai <= lastA) {
171                         onANotB(ai++, bi);
172                     }
173                 }
174             }
175             
176             if (ai <= lastA) {
177                 onANotB(ai++, bi);
178             }
179             
180             if (bi <= lastB) {
181                 onBNotA(ai, bi++);
182             }
183         }
184     }
185     
186     /**
187      * Override and return true in order to have <code>finishedA</code> invoked
188      * at the last element in the <code>a</code> array.
189      */
190     protected boolean callFinishedA() {
191         return false;
192     }
193     
194     /**
195      * Override and return true in order to have <code>finishedB</code> invoked
196      * at the last element in the <code>b</code> array.
197      */
198     protected boolean callFinishedB() {
199         return false;
200     }
201     
202     /**
203      * Invoked at the last element in <code>a</code>, if
204      * <code>callFinishedA</code> returns true.
205      */
206     protected void finishedA(int lastA) {
207     }
208     
209     /**
210      * Invoked at the last element in <code>b</code>, if
211      * <code>callFinishedB</code> returns true.
212      */
213     protected void finishedB(int lastB) {
214     }
215     
216     /**
217      * Invoked for elements in <code>a</code> and not in <code>b</code>.
218      */
219     protected void onANotB(int ai, int bi) {
220         if (pending == null) {
221             pending = new Difference(ai, ai, bi, -1);
222         } else {
223             pending.setDeleted(ai);
224         }
225     }
226     
227     /**
228      * Invoked for elements in <code>b</code> and not in <code>a</code>.
229      */
230     protected void onBNotA(int ai, int bi) {
231         if (pending == null) {
232             pending = new Difference(ai, -1, bi, bi);
233         } else {
234             pending.setAdded(bi);
235         }
236     }
237     
238     /**
239      * Invoked for elements matching in <code>a</code> and <code>b</code>.
240      */
241     protected void onMatch(int ai, int bi) {
242         if (pending == null) {
243             // no current pending
244         } else {
245             diffs.add(pending);
246             pending = null;
247         }
248     }
249     
250     /**
251      * Compares the two objects, using the comparator provided with the
252      * constructor, if any.
253      */
254     protected boolean equals(Object   x, Object   y) {
255         return comparator == null ? x.equals(y) : comparator.compare(x, y) == 0;
256     }
257     
258     /**
259      * Returns an array of the longest common subsequences.
260      */
261     public Integer  [] getLongestCommonSubsequences() {
262         int aStart = 0;
263         int aEnd = a.length - 1;
264         
265         int bStart = 0;
266         int bEnd = b.length - 1;
267         
268         TreeMap matches = new TreeMap();
269         
270         while (aStart <= aEnd && bStart <= bEnd && equals(a[aStart], b[bStart])) {
271             matches.put(new Integer  (aStart++), new Integer  (bStart++));
272         }
273         
274         while (aStart <= aEnd && bStart <= bEnd && equals(a[aEnd], b[bEnd])) {
275             matches.put(new Integer  (aEnd--), new Integer  (bEnd--));
276         }
277         
278         Map bMatches = null;
279         if (comparator == null) {
280             if (a.length > 0 && a[0] instanceof Comparable  ) {
281                 // this uses the Comparable interface
282                 bMatches = new TreeMap();
283             } else {
284                 // this just uses hashCode()
285                 bMatches = new HashMap();
286             }
287         } else {
288             // we don't really want them sorted, but this is the only Map
289             // implementation (as of JDK 1.4) that takes a comparator.
290             bMatches = new TreeMap(comparator);
291         }
292         
293         for (int bi = bStart; bi <= bEnd; ++bi) {
294             Object   element   = b[bi];
295             Object   key       = element;
296             List   positions = (List)bMatches.get(key);
297             if (positions == null) {
298                 positions = new ArrayList();
299                 bMatches.put(key, positions);
300             }
301             positions.add(new Integer  (bi));
302         }
303         
304         thresh = new TreeMap();
305         Map links = new HashMap();
306         
307         for (int i = aStart; i <= aEnd; ++i) {
308             Object   aElement  = a[i]; // keygen here.
309             List   positions = (List)bMatches.get(aElement);
310             
311             if (positions != null) {
312                 Integer    k   = new Integer  (0);
313                 ListIterator pit = positions.listIterator(positions.size());
314                 while (pit.hasPrevious()) {
315                     Integer   j = (Integer  )pit.previous();
316                     
317                     k = insert(j, k);
318                     
319                     if (k == null) {
320                         // nothing
321                     } else {
322                         Object   value = k.intValue() > 0 ? links.get(new Integer  (k.intValue() - 1)) : null;
323                         links.put(k, new Object  [] { value, new Integer  (i), j });
324                     }
325                 }
326             }
327         }
328         
329         if (thresh.size() > 0) {
330             Integer    ti   = (Integer  )thresh.lastKey();
331             Object  [] link = (Object  [])links.get(ti);
332             while (link != null) {
333                 Integer   x = (Integer  )link[1];
334                 Integer   y = (Integer  )link[2];
335                 matches.put(x, y);
336                 link = (Object  [])link[0];
337             }
338         }
339         
340         return toArray(matches);
341     }
342     
343     /**
344      * Converts the map (indexed by java.lang.Integers) into an array.
345      */
346     protected static Integer  [] toArray(TreeMap map) {
347         int       size = map.size() == 0 ? 0 : 1 + ((Integer  )map.lastKey()).intValue();
348         Integer  [] ary  = new Integer  [size];
349         Iterator  it   = map.keySet().iterator();
350         
351         while (it.hasNext()) {
352             Integer   idx = (Integer  )it.next();
353             Integer   val = (Integer  )map.get(idx);
354             ary[idx.intValue()] = val;
355         }
356         return ary;
357     }
358     
359     /**
360      * Returns whether the integer is not zero (including if it is not null).
361      */
362     protected static boolean isNonzero(Integer   i) {
363         return i != null && i.intValue() != 0;
364     }
365     
366     /**
367      * Returns whether the value in the map for the given index is greater than
368      * the given value.
369      */
370     protected boolean isGreaterThan(Integer   index, Integer   val) {
371         Integer   lhs = (Integer  )thresh.get(index);
372         return lhs != null && val != null && lhs.compareTo(val) > 0;
373     }
374     
375     /**
376      * Returns whether the value in the map for the given index is less than
377      * the given value.
378      */
379     protected boolean isLessThan(Integer   index, Integer   val) {
380         Integer   lhs = (Integer  )thresh.get(index);
381         return lhs != null && (val == null || lhs.compareTo(val) < 0);
382     }
383     
384     /**
385      * Returns the value for the greatest key in the map.
386      */
387     protected Integer   getLastValue() {
388         return (Integer  )thresh.get(thresh.lastKey());
389     }
390     
391     /**
392      * Adds the given value to the "end" of the threshold map, that is, with the
393      * greatest index/key.
394      */
395     protected void append(Integer   value) {
396         Integer   addIdx = null;
397         if (thresh.size() == 0) {
398             addIdx = new Integer  (0);
399         } else {
400             Integer   lastKey = (Integer  )thresh.lastKey();
401             addIdx = new Integer  (lastKey.intValue() + 1);
402         }
403         thresh.put(addIdx, value);
404     }
405     
406     /**
407      * Inserts the given values into the threshold map.
408      */
409     protected Integer   insert(Integer   j, Integer   k) {
410         if (isNonzero(k) && isGreaterThan(k, j) && isLessThan(new Integer  (k.intValue() - 1), j)) {
411             thresh.put(k, j);
412         } else {
413             int hi = -1;
414             
415             if (isNonzero(k)) {
416                 hi = k.intValue();
417             } else if (thresh.size() > 0) {
418                 hi = ((Integer  )thresh.lastKey()).intValue();
419             }
420             
421             // off the end?
422             if (hi == -1 || j.compareTo(getLastValue()) > 0) {
423                 append(j);
424                 k = new Integer  (hi + 1);
425             } else {
426                 // binary search for insertion point:
427                 int lo = 0;
428                 
429                 while (lo <= hi) {
430                     int     index = (hi + lo) / 2;
431                     Integer   val   = (Integer  )thresh.get(new Integer  (index));
432                     int     cmp   = j.compareTo(val);
433                     
434                     if (cmp == 0) {
435                         return null;
436                     } else if (cmp > 0) {
437                         lo = index + 1;
438                     } else {
439                         hi = index - 1;
440                     }
441                 }
442                 
443                 thresh.put(new Integer  (lo), j);
444                 k = new Integer  (lo);
445             }
446         }
447         return k;
448     }
449     
450 }
451
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags