KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > netbeans > modules > java > source > save > 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 JavaDoc[] a;
42     
43     /**
44      * The target array, AKA the "to" values.
45      */

46     protected Object JavaDoc[] 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 JavaDoc[] a, Object JavaDoc[] 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 JavaDoc[] a, Object JavaDoc[] 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 JavaDoc[] 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 JavaDoc 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 JavaDoc x, Object JavaDoc 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 JavaDoc[] 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 JavaDoc(aStart++), new Integer JavaDoc(bStart++));
272         }
273         
274         while (aStart <= aEnd && bStart <= bEnd && equals(a[aEnd], b[bEnd])) {
275             matches.put(new Integer JavaDoc(aEnd--), new Integer JavaDoc(bEnd--));
276         }
277         
278         Map bMatches = null;
279         if (comparator == null) {
280             if (a.length > 0 && a[0] instanceof Comparable JavaDoc) {
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 JavaDoc element = b[bi];
295             Object JavaDoc 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 JavaDoc(bi));
302         }
303         
304         thresh = new TreeMap();
305         Map links = new HashMap();
306         
307         for (int i = aStart; i <= aEnd; ++i) {
308             Object JavaDoc aElement = a[i]; // keygen here.
309
List positions = (List)bMatches.get(aElement);
310             
311             if (positions != null) {
312                 Integer JavaDoc k = new Integer JavaDoc(0);
313                 ListIterator pit = positions.listIterator(positions.size());
314                 while (pit.hasPrevious()) {
315                     Integer JavaDoc j = (Integer JavaDoc)pit.previous();
316                     
317                     k = insert(j, k);
318                     
319                     if (k == null) {
320                         // nothing
321
} else {
322                         Object JavaDoc value = k.intValue() > 0 ? links.get(new Integer JavaDoc(k.intValue() - 1)) : null;
323                         links.put(k, new Object JavaDoc[] { value, new Integer JavaDoc(i), j });
324                     }
325                 }
326             }
327         }
328         
329         if (thresh.size() > 0) {
330             Integer JavaDoc ti = (Integer JavaDoc)thresh.lastKey();
331             Object JavaDoc[] link = (Object JavaDoc[])links.get(ti);
332             while (link != null) {
333                 Integer JavaDoc x = (Integer JavaDoc)link[1];
334                 Integer JavaDoc y = (Integer JavaDoc)link[2];
335                 matches.put(x, y);
336                 link = (Object JavaDoc[])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 JavaDoc[] toArray(TreeMap map) {
347         int size = map.size() == 0 ? 0 : 1 + ((Integer JavaDoc)map.lastKey()).intValue();
348         Integer JavaDoc[] ary = new Integer JavaDoc[size];
349         Iterator it = map.keySet().iterator();
350         
351         while (it.hasNext()) {
352             Integer JavaDoc idx = (Integer JavaDoc)it.next();
353             Integer JavaDoc val = (Integer JavaDoc)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 JavaDoc 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 JavaDoc index, Integer JavaDoc val) {
371         Integer JavaDoc lhs = (Integer JavaDoc)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 JavaDoc index, Integer JavaDoc val) {
380         Integer JavaDoc lhs = (Integer JavaDoc)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 JavaDoc getLastValue() {
388         return (Integer JavaDoc)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 JavaDoc value) {
396         Integer JavaDoc addIdx = null;
397         if (thresh.size() == 0) {
398             addIdx = new Integer JavaDoc(0);
399         } else {
400             Integer JavaDoc lastKey = (Integer JavaDoc)thresh.lastKey();
401             addIdx = new Integer JavaDoc(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 JavaDoc insert(Integer JavaDoc j, Integer JavaDoc k) {
410         if (isNonzero(k) && isGreaterThan(k, j) && isLessThan(new Integer JavaDoc(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 JavaDoc)thresh.lastKey()).intValue();
419             }
420             
421             // off the end?
422
if (hi == -1 || j.compareTo(getLastValue()) > 0) {
423                 append(j);
424                 k = new Integer JavaDoc(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 JavaDoc val = (Integer JavaDoc)thresh.get(new Integer JavaDoc(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 JavaDoc(lo), j);
444                 k = new Integer JavaDoc(lo);
445             }
446         }
447         return k;
448     }
449     
450 }
451
Popular Tags