KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > netbeans > modules > java > source > save > ListMatcher


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 import org.netbeans.api.java.lexer.JavaTokenId;
23 import static org.netbeans.modules.java.source.save.Measure.*;
24     
25 /**
26  * Implementation of the Longest Common Subsequence algorithm.
27  * That is, given two lists <tt>oldL</tt> and <tt>newL</tt>,
28  * this class will find the longest sequence objects
29  * that are common and ordered in <tt>oldL</tt> and <tt>newL</tt>.
30  *
31  * @author Pavel Flaska
32  */
33 public final class ListMatcher<E> {
34     
35     // old array of elements
36 private final E[] oldL;
37     
38     // new array of elements
39 private final E[] newL;
40     
41     // contains differences. Filled by compute() method
42 private final Stack<ResultItem<E>> result;
43
44     // contains method for distance-measuring
45 private final Measure measure;
46     
47     // create ListMatcher instance
48 private ListMatcher(List<? extends E> oldL, List<? extends E> newL, Measure measure) {
49         this((E[]) oldL.toArray(), (E[]) newL.toArray(), measure);
50     }
51     
52     // create ListMatcher instance
53 private ListMatcher(List<? extends E> oldL, List<? extends E> newL) {
54         this((E[]) oldL.toArray(), (E[]) newL.toArray());
55     }
56     
57     // create ListMatcher instance
58 private ListMatcher(E[] oldL, E[] newL) {
59         this(oldL, newL, null);
60     }
61     
62     private ListMatcher(E[] oldL, E[] newL, Measure measure) {
63         this.oldL = oldL;
64         this.newL = newL;
65         this.measure = measure != null ? measure : Measure.DEFAULT;
66         result = new Stack<ResultItem<E>>();
67     }
68
69     /**
70      * Creates the instance of <tt>ListMatcher</tt> class.
71      *
72      * @param oldL old array of elements to compare.
73      * @param newL new array of elements to compare.
74      * @return created instance.
75      */
76     public static <T> ListMatcher<T> instance(List<? extends T> oldL, List<? extends T> newL) {
77         return new ListMatcher<T>(oldL, newL);
78     }
79
80     /**
81      * Creates the instance of <tt>ListMatcher</tt> class.
82      *
83      * @param oldL old array of elements to compare.
84      * @param newL new array of elements to compare.
85      * @param comparator used for comparing elements.
86      * @return created instance.
87      */
88     public static <T> ListMatcher<T> instance(List<? extends T> oldL, List<? extends T> newL, Measure measure) {
89         return new ListMatcher<T>(oldL, newL, measure);
90     }
91     /**
92      * Creates the instance of <tt>ListMatcher</tt> class.
93      *
94      * @param oldL old array of elements to compare.
95      * @param newL new array of elements to compare.
96      * @return created instance.
97      */
98     public static <T> ListMatcher<T> instance(T[] oldL, T[] newL) {
99         return new ListMatcher<T>(oldL, newL);
100     }
101
102     /**
103      * Represents type of difference.
104      */
105     public static enum Operation {
106         /** Element was inserted. */
107         INSERT("insert"),
108         
109         /** Element was modified. */
110         MODIFY("modify"),
111         
112         /** Element was deleted. */
113         DELETE("delete"),
114         
115         /** Element was not changed, left as it was. */
116         NOCHANGE("nochange");
117         
118         private Operation(String JavaDoc name) {
119             this.name = name;
120         }
121         
122         private final String JavaDoc name;
123         
124         public String JavaDoc toString() {
125             return name;
126         }
127     } // end Operation
128
129     /**
130      * Represents one difference in old and new list.
131      */
132     public static final class ResultItem<S> {
133
134         /** element which differs */
135         public final S element;
136         
137         /** kind of operation */
138         public final Operation operation;
139
140         /**
141          * Creates an instance.
142          *
143          * @param element element which differs. New element when insert
144          * or modify, old element when nochange or delete.
145          * @param operation kind of operation, insert/delete/nochange/modify
146          */
147         public ResultItem(final S element, final Operation operation) {
148             this.element = element;
149             this.operation = operation;
150         }
151         
152         public String JavaDoc toString() {
153             StringBuffer JavaDoc sb = new StringBuffer JavaDoc(128);
154             sb.append('{');
155             sb.append(operation);
156             sb.append("} ");
157             sb.append(element);
158             return sb.toString();
159         }
160     };
161
162     /**
163      * Computes the lists differences. Just call this method after
164      * instance is created.
165      *
166      * @return true, if there were at least one change in new list.
167      */
168     public boolean match() {
169         final int NEITHER = 0;
170         final int UP = 1;
171         final int LEFT = 2;
172         final int UP_AND_LEFT = 3;
173         final int UP_AND_LEFT_MOD = 4;
174         
175         int n = oldL.length;
176         int m = newL.length;
177         int S[][] = new int[n+1][m+1];
178         int R[][] = new int[n+1][m+1];
179         int ii, jj;
180         
181         // initialization
182 for (ii = 0; ii <= n; ++ii) {
183             S[ii][0] = 0;
184             R[ii][0] = UP;
185         }
186         for (jj = 0; jj <= m; ++jj) {
187             S[0][jj] = 0;
188             R[0][jj] = LEFT;
189         }
190         
191             // This is the main dynamic programming loop that computes the score and backtracking arrays.
192 for (ii = 1; ii <= n; ++ii) {
193             for (jj = 1; jj <= m; ++jj) {
194                 if (oldL[ii-1].equals(newL[jj-1])) {
195                     S[ii][jj] = S[ii-1][jj-1] + 1;
196                     R[ii][jj] = UP_AND_LEFT;
197                 } else {
198                     int distance = measure.getDistance(oldL[ii-1], newL[jj-1]);
199                     // if the distance is betwwen OBJECTS_MATCH and INFINITE_DISTANCE,
200 // old element was modified to new element.
201 if (distance > OBJECTS_MATCH && distance < INFINITE_DISTANCE) {
202                         S[ii][jj] = S[ii-1][jj-1] + 1;
203                         R[ii][jj] = UP_AND_LEFT_MOD;
204                     } else {
205                         S[ii][jj] = S[ii-1][jj-1] + 0;
206                         R[ii][jj] = distance == OBJECTS_MATCH ? UP_AND_LEFT : NEITHER;
207                     }
208                 }
209                 
210                 if (S[ii-1][jj] >= S[ii][jj]) {
211                     S[ii][jj] = S[ii-1][jj];
212                     R[ii][jj] = UP;
213                 }
214                 
215                 if (S[ii][jj-1] >= S[ii][jj]) {
216                     S[ii][jj] = S[ii][jj-1];
217                     R[ii][jj] = LEFT;
218                 }
219             }
220         }
221         
222         // The length of the longest substring is S[n][m]
223 ii = n;
224         jj = m;
225         
226         // collect result
227 // ensure stack is empty
228 if (result.empty() == false) result.clear();
229         // Trace the backtracking matrix.
230 while (ii > 0 || jj > 0) {
231             if(R[ii][jj] == UP_AND_LEFT) {
232                 ii--;
233                 jj--;
234                 E element = oldL[ii];
235                 result.push(new ResultItem(element, Operation.NOCHANGE));
236             } else if (R[ii][jj] == UP_AND_LEFT_MOD) {
237                 ii--;
238                 jj--;
239                 E element = newL[ii];
240                 result.push(new ResultItem(element, Operation.MODIFY));
241             } else if (R[ii][jj] == UP) {
242                 ii--;
243                 E element = oldL[ii];
244                 result.push(new ResultItem(element, Operation.DELETE));
245             } else if (R[ii][jj] == LEFT) {
246                 jj--;
247                 E element = newL[jj];
248                 result.push(new ResultItem(element, Operation.INSERT));
249             }
250         }
251         return !result.empty();
252     }
253     
254     /**
255      * Returns a list of differences computed by <tt>compute()</tt> method.
256      * Ensure that method <tt>compute()</tt> was called.
257      *
258      * @return array of differences.
259      */
260     public ResultItem<E>[] getResult() {
261         int size = result.size();
262         ResultItem<E>[] temp = new ResultItem[size];
263         for (ResultItem<E> item : result) {
264             temp[--size] = item;
265         }
266         return temp;
267     }
268     
269     /**
270      * Returns a list of differences computed by <tt>compute()</tt> method.
271      * Moreover, it groups <b>remove</b> operation followed by <b>insert</b>
272      * to one <b>modify</b> operation.
273      *
274      * @return array of differences.
275      */
276     public ResultItem<E>[] getTransformedResult() {
277         Stack<ResultItem<E>> copy = (Stack<ResultItem<E>>) result.clone();
278         ArrayList<ResultItem<E>> temp = new ArrayList<ResultItem<E>>(copy.size());
279         while (!copy.empty()) {
280             ResultItem<E> item = copy.pop();
281             // when operation is remove, ensure that there is not following
282 // insert - in such case, we can merge these two operation to
283 // modify operation.
284 if (item.operation == Operation.DELETE &&
285                 !copy.empty() && copy.peek().operation == Operation.INSERT)
286             {
287                 // yes, it is modify operation.
288 ResultItem nextItem = copy.pop();
289                 temp.add(new ResultItem(nextItem.element, Operation.MODIFY));
290             } else {
291                 temp.add(item);
292             }
293         }
294         return temp.toArray(new ResultItem[0]);
295     }
296     
297     // for testing and debugging reasons.
298 public String JavaDoc printResult(boolean transformed) {
299         StringBuffer JavaDoc sb = new StringBuffer JavaDoc(128);
300         ResultItem<E>[] temp = transformed ? getTransformedResult() : getResult();
301         for (int i = 0; i < temp.length; i++) {
302             sb.append(temp[i]).append('\n');
303         }
304         return sb.toString();
305     }
306     
307     /**
308      * Creates the <tt>Separator</tt> instance.
309      *
310      * @return separator instance.
311      */
312     public Separator separatorInstance() {
313         return new Separator(getTransformedResult(), JavaTokenId.COMMA);
314     }
315     
316     public static final class Separator<E> {
317
318         static final SItem EMPTY = new SItem(null, 0);
319         
320         private final ResultItem<E>[] match;
321         private E lastInList;
322         private E firstInList;
323         private final JavaTokenId separator;
324         private SItem[] result;
325         
326         // these two flags are not used currently, if some of fixes
327 // will not use them, remove it.
328 private boolean allNew;
329         private boolean allOld;
330         
331         public Separator(ResultItem<E>[] match, JavaTokenId separator) {
332             this.match = match;
333             this.separator = separator;
334             this.lastInList = null;
335             // this code can be replaced with providing last element
336 // as a parameter of this constructor. (new list is mostly
337 // available in caller code.)
338 for (int i = match.length-1; i > 0; i--) {
339                 if (match[i].operation != Operation.DELETE) {
340                     lastInList = match[i].element;
341                     break;
342                 }
343             }
344             for (int i = 0; i < match.length; i++) {
345                 if (match[i].operation != Operation.DELETE) {
346                     firstInList = match[i].element;
347                     break;
348                 }
349             }
350             // currently not used code. Left for a while if they
351 // will not be used during bug fixing.
352 allNew = allOld = true;
353             for (int i = 0; i < match.length; i++) {
354                 if (match[i].operation == Operation.MODIFY ||
355                     match[i].operation == Operation.NOCHANGE)
356                     allNew = allOld = false;
357                 else if (match[i].operation == Operation.INSERT)
358                     allOld = false;
359                 else if (match[i].operation == Operation.DELETE)
360                     allNew = false;
361             }
362         }
363
364         // Just for shorter call
365 // create separator item
366 private static SItem create(ResultItem item) {
367             return create(item, SItem.NONE);
368         }
369         
370         // create separator item
371 private static SItem create(ResultItem item, int type) {
372             return new SItem(item, type);
373         }
374
375         /**
376          * Computes separators for every result item. For every result item,
377          * it creates separator item. Just call this method after Separator
378          * creation.
379          * todo (#pf): Should be part of Separator creation?
380          */
381         public void compute() {
382             result = new SItem[match.length];
383             for (int i = match.length-1; i >= 0; --i) {
384                 if (match[i].operation == Operation.DELETE) {
385                     if (i == (match.length-1)) {
386                         // handle last element deletion
387 if (i > 0 && match[i-1].operation == Operation.DELETE) {
388                             result[i] = create(match[i], allOld ? SItem.TAIL : SItem.NONE);
389                             while (i > 0 && match[i-1].operation == Operation.DELETE) {
390                                 if (i > 1 && match[i-2].operation == Operation.DELETE) {
391                                     result[--i] = create(match[i], SItem.NEXT);
392                                 } else {
393                                     int mask = (i-1) == 0 ? SItem.HEAD : SItem.PREV;
394                                     result[--i] = create(match[i], mask | SItem.NEXT);
395                                 }
396                             }
397                         } else {
398                             int mask = i > 0 ? SItem.PREV : SItem.HEAD;
399                             mask |= allOld ? SItem.TAIL : SItem.NONE;
400                             result[i] = create(match[i], mask);
401                         }
402                     } else {
403                         result[i] = create(match[i], SItem.NEXT);
404                     }
405                 } else if (match[i].operation == Operation.INSERT) {
406                     if (i == (match.length-1)) {
407                         // handle last element creation
408 if (i > 0 && match[i-1].operation == Operation.INSERT) {
409                             result[i] = create(match[i], allNew ? SItem.TAIL : SItem.NONE);
410                             while (i > 0 && match[i-1].operation == Operation.INSERT) {
411                                 if (i > 1 && match[i-2].operation == Operation.INSERT) {
412                                     result[--i] = create(match[i], SItem.NEXT);
413                                 } else {
414                                     int mask = (i-1) == 0 ? SItem.HEAD : SItem.PREV;
415                                     result[--i] = create(match[i], mask | SItem.NEXT);
416                                 }
417                             }
418                         } else {
419                             int mask = i > 0 ? SItem.PREV : SItem.HEAD;
420                             mask |= allNew ? SItem.TAIL : SItem.NONE;
421                             result[i] = create(match[i], mask);
422                         }
423                     } else {
424                         result[i] = create(match[i], SItem.NEXT);
425                     }
426                 } else {
427                     result[i] = EMPTY;
428                 }
429             }
430         }
431         
432         /**
433          * Returns true if the generator has to add/remove head token
434          * before the element at <tt>index</tt>.
435          * For example, 'throws' keyword when matching 'throws' clause.
436          * If all throws are removed, throws keyword has to be removed
437          * too.
438          *
439          * @param index index of element in matcher result.
440          * @return true if separator has to be added/removed.
441          */
442         public boolean head(int index) { return result[index].head(); }
443         
444         /**
445          * Returns true if the generator has to add/remove separator
446          * before the element at <tt>index</tt>.
447          *
448          * For example, comma when matching method parameters.
449          *
450          * @param index index of element in matcher result.
451          * @return true if separator has to be added/removed.
452          */
453         public boolean prev(int index) { return result[index].prev(); }
454         
455         /**
456          * Returns true if the generator has to add/remove separator
457          * after the element at <tt>index</tt>.
458          *
459          * For example, comma when matching method parameters.
460          *
461          * @param index index of element in matcher result.
462          * @return true if separator has to be added/removed.
463          */
464         public boolean next(int index) { return result[index].next(); }
465         
466         /**
467          * Returns true if the generator has to add/remove tail token
468          * after the element at <tt>index</tt>.
469          * For example, tail '>' token when matching type parameters.
470          * If all type parameters are removed, tail '>' has to be
471          * removed too. (also, head '<' has to be removed too. See
472          * {@head}.
473          *
474          * @param index index of element in matcher result.
475          * @return true if separator has to be added/removed.
476          */
477         public boolean tail(int index) { return result[index].tail(); }
478         
479         /**
480          * Just print all the item. Should be probably removed,
481          * used in tests right now. toString() should replace it.
482          */
483         public String JavaDoc print() {
484             if (result != null) {
485                  StringBuffer JavaDoc sb = new StringBuffer JavaDoc(128);
486                  for (SItem item : result) {
487                      if (item != EMPTY)
488                          sb.append(item).append('\n');
489                  }
490                  return sb.toString();
491             } else {
492                 return "Result was not computed!";
493             }
494         }
495         
496         // for every result item, instance of SItem class contains
497 // information how to handle separator around the item,
498 // including head/tail tokens.
499 private static final class SItem {
500             private static final int NONE = 0x00;
501             private static final int PREV = 0x01;
502             private static final int NEXT = PREV << 1;
503             private static final int HEAD = NEXT << 1;
504             private static final int TAIL = HEAD << 1;
505             
506             private final int type;
507             private final ResultItem item;
508             
509             private SItem(ResultItem item, int type) {
510                 this.item = item;
511                 this.type = type;
512             }
513             
514             private boolean prev() { return (type & PREV) != NONE; }
515             private boolean next() { return (type & NEXT) != NONE; }
516             private boolean head() { return (type & HEAD) != NONE; }
517             private boolean tail() { return (type & TAIL) != NONE; }
518             
519             public String JavaDoc toString() {
520                 StringBuffer JavaDoc sb = new StringBuffer JavaDoc();
521                 if (head()) sb.append("head ");
522                 if (prev()) sb.append("previous ");
523                 sb.append(item.toString()).append(' ');
524                 if (next()) sb.append("next ");
525                 if (tail()) sb.append("tail ");
526                 return sb.toString();
527             }
528         }
529     }
530 }
Popular Tags