AbstractMatching


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.pde.internal.ui.compare;
12  
13  import java.util.ArrayList  ;
14  import java.util.Vector  ;
15  
16  import org.eclipse.compare.rangedifferencer.IRangeComparator;
17  import org.eclipse.compare.rangedifferencer.RangeDifference;
18  import org.eclipse.compare.rangedifferencer.RangeDifferencer;
19  import org.eclipse.core.runtime.IProgressMonitor;
20  
21  /**
22   * @version     1.0
23   * @author
24   */
25  public abstract class AbstractMatching {
26  
27      protected static final int NO_ENTRY = -1;//value with which fDT elements are initialized
28      protected static final String   SIGN_ELEMENT= XMLStructureCreator.SIGN_ELEMENT;
29      int[][] fDT;//Distance Table; 1st index from fNLeft, 2nd index from fNRight
30      ArrayList  [][] fDT_Matchings;//Mathing entries of children for a match. 1st index from fNLeft, 2nd index from fNRight
31      Vector   fNLeft;
32      Vector   fNRight;
33      Vector   fMatches;
34      
35      /* methods used for match */
36  
37      /* finds all the leaves of a tree and puts them in a vector */
38      protected void findLeaves(XMLNode root, ArrayList   leaves) {
39          if (isLeaf(root)) {
40              leaves.add(root);           
41          } else {
42              Object  [] children = root.getChildren();
43              for (int i=0; i<children.length; i++)
44                  findLeaves((XMLNode) children[i], leaves);
45          }
46      }
47  
48      /* true if x is a leaf */
49      protected boolean isLeaf(XMLNode x) {
50          if (x == null) return true;
51          return x.getChildren() == null || x.getChildren().length <= 0;
52      }
53  
54      /* Numbers all nodes of tree. The number of x is its index in the vector numbering */
55      protected void numberNodes(XMLNode root, Vector   numbering) {
56          if (root != null) {
57              numbering.add(root);
58              Object  [] children = root.getChildren();
59              if (children != null) {
60                  for (int i=0; i<children.length; i++)
61                      numberNodes((XMLNode) children[i], numbering);
62              }
63          }
64      }
65      
66      /* counts # of nodes in tree including root */
67      protected int countNodes(XMLNode root) {
68          if (root == null) return 0;
69          int count = 1;
70          if (isLeaf(root)) return count;
71          Object  [] children = root.getChildren();
72          for (int i=0; i<children.length; i++)
73              count+=countNodes((XMLNode) children[i]);
74          return count;
75      }
76  
77      /* returns index of node x in fNLeft */
78      protected int indexOfLN (XMLNode x) {
79          int i= 0;
80          while ((i<fNLeft.size()) && (fNLeft.elementAt(i) != x))
81              i++;
82          return i;
83      }
84      
85      /* returns index of node y in fNRight */
86      protected int indexOfRN (XMLNode y) {
87          int j= 0;
88          while ((j<fNRight.size()) && (fNRight.elementAt(j) != y))
89              j++;
90          return j;
91      }
92  
93  /* for testing */
94      public Vector   getMatches() {
95          return fMatches;
96      }
97  
98      protected class XMLComparator implements IRangeComparator {
99      
100         private Object  [] fXML_elements;
101     
102         public XMLComparator(Object  [] xml_elements) {
103             fXML_elements= xml_elements;
104         }
105     
106         /*
107          * @see IRangeComparator#getRangeCount()
108          */
109         public int getRangeCount() {
110             return fXML_elements.length;
111         }
112     
113         /*
114          * @see IRangeComparator#rangesEqual(int, IRangeComparator, int)
115          */
116         public boolean rangesEqual(
117             int thisIndex,
118             IRangeComparator other_irc,
119             int otherIndex) {
120             
121             if (other_irc instanceof XMLComparator) {
122                 XMLComparator other= (XMLComparator) other_irc;
123                 //return ((XMLNode)fXML_elements[thisIndex]).subtreeEquals(other.getXML_elements()[otherIndex]);
124                 
125                 //ordered compare of subtrees
126                 //boolean result= ((XMLNode)fXML_elements[thisIndex]).subtreeEquals(other.getXML_elements()[otherIndex]);
127                 
128                 //taking ids into account
129                 boolean sameId= false;
130                 XMLNode thisNode= (XMLNode)fXML_elements[thisIndex];
131                 XMLNode otherNode= (XMLNode)other.getXML_elements()[otherIndex]; 
132                 if ( thisNode.usesIDMAP() && otherNode.usesIDMAP() ) {
133                     if ( otherNode.getOrigId().equals(thisNode.getOrigId()) ) {
134                         sameId= true;
135                     }
136                 }
137                 
138                 //unordered compare of subtrees
139                 int distance= dist((XMLNode)other.getXML_elements()[otherIndex] , (XMLNode)fXML_elements[thisIndex]);
140                 return sameId || distance == 0;
141             }
142             return false;
143         }
144     
145         /*
146          * @see IRangeComparator#skipRangeComparison(int, int, IRangeComparator)
147          */
148         public boolean skipRangeComparison(
149             int length,
150             int maxLength,
151             IRangeComparator other) {
152             return false;
153         }
154     
155         public Object  [] getXML_elements() {
156             return fXML_elements;
157         }
158     
159     }
160 
161     /* represents a matching between a node in the Left tree and a node in the Right tree */
162     class Match {
163         public XMLNode fx;
164         public XMLNode fy;
165         
166         Match(XMLNode x, XMLNode y) {
167             fx = x;
168             fy = y; 
169         }
170         
171         public boolean equals(Object   obj) {
172             if (obj instanceof Match) {
173                 Match m = (Match) obj;
174                 if (m != null)
175                     return fx == m.fx && fy == m.fy;
176             }
177             return false;
178         }
179     }
180     
181     protected int handleRangeDifferencer(Object  [] xc_elements, Object  [] yc_elements, ArrayList   DTMatching, int distance) {
182         RangeDifference[] differences= RangeDifferencer.findDifferences(new XMLComparator(xc_elements), new XMLComparator(yc_elements));
183         
184         int cur_pos_left= 0;
185         int cur_pos_right= 0;
186         for (int i= 0; i < differences.length; i++) {
187             RangeDifference rd= differences[i];
188             int equal_length= rd.leftStart();
189             //handle elements before current range which are unchanged
190             while (cur_pos_left < equal_length) {
191                 //assuming XMLComparator has already filled fDT and fDT_Matchings for subtrees
192                 //rooted at xc_elements[cur_pos_left] and yc_elements[cur_pos_right]
193 //              if ( fDT[indexOfLN( (XMLNode)xc_elements[cur_pos_left])][indexOfRN( (XMLNode)yc_elements[cur_pos_right])] != 0)
194 //                  System.out.println("distance not 0");
195 //              distance += fDT[indexOfLN( (XMLNode)xc_elements[cur_pos_left])][indexOfRN( (XMLNode)yc_elements[cur_pos_right])];
196                 //DTMatching.addAll(fDT_Matchings[index_left][index_right]);
197                 DTMatching.add(new Match( (XMLNode)xc_elements[cur_pos_left], (XMLNode)yc_elements[cur_pos_right]));
198                 cur_pos_left++;
199                 cur_pos_right++;
200             }
201             //now handle RangeDifference rd[i]
202             int smaller_length, greater_length;
203             boolean leftGreater= rd.leftLength() > rd.rightLength();
204             if (leftGreater) {
205                 smaller_length= rd.rightLength();
206                 greater_length= rd.leftLength();
207             } else {
208                 smaller_length= rd.leftLength();
209                 greater_length= rd.rightLength();
210             }
211             
212             //handle elements elements in range
213             for (int j=0; j < smaller_length; j++) {
214                 distance += dist((XMLNode) xc_elements[cur_pos_left], (XMLNode) yc_elements[cur_pos_right]);
215                 DTMatching.add(new Match( (XMLNode)xc_elements[cur_pos_left], (XMLNode)yc_elements[cur_pos_right]));
216                 cur_pos_left++;
217                 cur_pos_right++;
218             }
219             //int cur_pos_greater= (leftGreater)?cur_pos_left:cur_pos_right;
220             if (leftGreater) {
221                 for (int j=smaller_length; j < greater_length; j++) {
222                     distance += countNodes((XMLNode) xc_elements[cur_pos_left]);
223                     DTMatching.add(new Match( (XMLNode)xc_elements[cur_pos_left], null));
224                     cur_pos_left++;
225                 }
226             } else {
227                 for (int j=smaller_length; j < greater_length; j++) {
228                     distance += countNodes((XMLNode) yc_elements[cur_pos_right]);
229                 DTMatching.add(new Match( null, (XMLNode)yc_elements[cur_pos_right]));
230                     cur_pos_right++;
231                 }
232             }
233 //          for (int j=smaller_length; j < greater_length; j++) {
234 //              distance += countNodes((XMLNode) xc_elements[cur_pos_greater]);
235 //              cur_pos_greater++;
236 //          }
237 //          if (leftGreater)
238 //              cur_pos_left= cur_pos_greater;
239 //          else
240 //              cur_pos_right= cur_pos_greater;
241         }
242         
243         for (int i= cur_pos_left; i < xc_elements.length; i++) {
244             //distance += fDT[indexOfLN( (XMLNode)xc_elements[cur_pos_left])][indexOfRN( (XMLNode)yc_elements[cur_pos_right])];
245             //DTMatching.addAll(fDT_Matchings[index_left][index_right]);
246             DTMatching.add(new Match( (XMLNode)xc_elements[cur_pos_left], (XMLNode)yc_elements[cur_pos_right]));
247             cur_pos_left++;
248             cur_pos_right++;
249         }
250         
251         return distance;
252     }
253 
254     abstract public void match(XMLNode LeftTree, XMLNode RightTree, boolean rightTreeIsAncestor, IProgressMonitor monitor);
255 
256     protected int dist(XMLNode x, XMLNode y) {
257         //System.out.println("dist( "+x.getSignature()+" , "+y.getSignature()+")");
258         int ret= NO_ENTRY;
259 
260         int index_x= indexOfLN(x);
261         int index_y= indexOfRN(y);
262         if (fDT[index_x][index_y] != NO_ENTRY) return fDT[index_x][index_y];
263         
264         if (isLeaf(x) && isLeaf(y)) {
265             if (x.getXMLType() == XMLStructureCreator.TYPE_ELEMENT) {
266                 if ( x.getSignature().equals(y.getSignature()) ) {
267                     ret= 0;
268                     fDT[index_x][index_y] = ret;
269                 } else {
270                     ret= 2;
271                     fDT[index_x][index_y] = ret;
272                 }
273                 return ret;
274             } else if (x.getXMLType() == XMLStructureCreator.TYPE_ATTRIBUTE || x.getXMLType() == XMLStructureCreator.TYPE_TEXT) {
275                 if ( x.getSignature().equals(y.getSignature()) ) {
276                     if (x.getValue().equals(y.getValue())) {
277                         ret= 0;
278                         fDT[index_x][index_y] = ret;
279                     } else {
280                         ret= 1;
281                         fDT[index_x][index_y] = ret;
282                     }
283                 } else {
284                     ret= 2;
285                     fDT[index_x][index_y] = ret;
286                 }
287                 return ret;
288             }
289         } else {//x or y are not leaves
290             if ( !x.getSignature().equals(y.getSignature()) ) {
291                 ret= countNodes(x) + countNodes(y);
292                 fDT[index_x][index_y] = ret;
293                 return ret;
294             }
295             //x.getSignature().equals(y.getSignature())
296             if (isLeaf(x)) {
297                 ret= countNodes(y)-1;
298                 fDT[index_x][index_y] = ret;
299                 return ret;
300             }
301             if (isLeaf(y)) {
302                 ret= countNodes(x)-1;
303                 fDT[index_x][index_y] = ret;
304                 return ret;
305             }
306             //both x and y have children
307             return handleXandYnotLeaves(x,y);
308         }
309         return ret;
310     }
311     
312     abstract int handleXandYnotLeaves(XMLNode x, XMLNode y);
313 }
314
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags