| /******************************************************************************* |
| * Copyright (c) 2000, 2004 IBM Corporation and others. |
| * All rights reserved. This program and the accompanying materials |
| * are made available under the terms of the Eclipse Public License v1.0 |
| * which accompanies this distribution, and is available at |
| * http://www.eclipse.org/legal/epl-v10.html |
| * |
| * Contributors: |
| * IBM Corporation - initial API and implementation |
| *******************************************************************************/ |
| package org.eclipse.compare.examples.xml; |
| |
| import java.util.ArrayList; |
| import java.util.Vector; |
| |
| import org.eclipse.compare.rangedifferencer.IRangeComparator; |
| import org.eclipse.compare.rangedifferencer.RangeDifference; |
| import org.eclipse.compare.rangedifferencer.RangeDifferencer; |
| import org.eclipse.core.runtime.IProgressMonitor; |
| |
| /** |
| * @version 1.0 |
| * @author |
| */ |
| public abstract class AbstractMatching { |
| |
| protected static final int NO_ENTRY = -1;//value with which fDT elements are initialized |
| protected static final String SIGN_ELEMENT= XMLStructureCreator.SIGN_ELEMENT; |
| int[][] fDT;//Distance Table; 1st index from fNLeft, 2nd index from fNRight |
| ArrayList[][] fDT_Matchings;//Mathing entries of children for a match. 1st index from fNLeft, 2nd index from fNRight |
| Vector fNLeft; |
| Vector fNRight; |
| Vector fMatches; |
| |
| /* methods used for match */ |
| |
| /* finds all the leaves of a tree and puts them in a vector */ |
| protected void findLeaves(XMLNode root, ArrayList leaves) { |
| if (isLeaf(root)) { |
| leaves.add(root); |
| } else { |
| Object[] children = root.getChildren(); |
| for (int i=0; i<children.length; i++) |
| findLeaves((XMLNode) children[i], leaves); |
| } |
| } |
| |
| /* true if x is a leaf */ |
| protected boolean isLeaf(XMLNode x) { |
| if (x == null) return true; |
| return x.getChildren() == null || x.getChildren().length <= 0; |
| } |
| |
| /* Numbers all nodes of tree. The number of x is its index in the vector numbering */ |
| protected void numberNodes(XMLNode root, Vector numbering) { |
| if (root != null) { |
| numbering.add(root); |
| Object[] children = root.getChildren(); |
| if (children != null) { |
| for (int i=0; i<children.length; i++) |
| numberNodes((XMLNode) children[i], numbering); |
| } |
| } |
| } |
| |
| /* counts # of nodes in tree including root */ |
| protected int countNodes(XMLNode root) { |
| if (root == null) return 0; |
| int count = 1; |
| if (isLeaf(root)) return count; |
| Object[] children = root.getChildren(); |
| for (int i=0; i<children.length; i++) |
| count+=countNodes((XMLNode) children[i]); |
| return count; |
| } |
| |
| /* returns index of node x in fNLeft */ |
| protected int indexOfLN (XMLNode x) { |
| int i= 0; |
| while ((i<fNLeft.size()) && (fNLeft.elementAt(i) != x)) |
| i++; |
| return i; |
| } |
| |
| /* returns index of node y in fNRight */ |
| protected int indexOfRN (XMLNode y) { |
| int j= 0; |
| while ((j<fNRight.size()) && (fNRight.elementAt(j) != y)) |
| j++; |
| return j; |
| } |
| |
| /* for testing */ |
| public Vector getMatches() { |
| return fMatches; |
| } |
| |
| protected class XMLComparator implements IRangeComparator { |
| |
| private Object[] fXML_elements; |
| |
| public XMLComparator(Object[] xml_elements) { |
| fXML_elements= xml_elements; |
| } |
| |
| /* |
| * @see IRangeComparator#getRangeCount() |
| */ |
| public int getRangeCount() { |
| return fXML_elements.length; |
| } |
| |
| /* |
| * @see IRangeComparator#rangesEqual(int, IRangeComparator, int) |
| */ |
| public boolean rangesEqual( |
| int thisIndex, |
| IRangeComparator other_irc, |
| int otherIndex) { |
| |
| if (other_irc instanceof XMLComparator) { |
| XMLComparator other= (XMLComparator) other_irc; |
| //return ((XMLNode)fXML_elements[thisIndex]).subtreeEquals(other.getXML_elements()[otherIndex]); |
| |
| //ordered compare of subtrees |
| //boolean result= ((XMLNode)fXML_elements[thisIndex]).subtreeEquals(other.getXML_elements()[otherIndex]); |
| |
| //taking ids into account |
| boolean sameId= false; |
| XMLNode thisNode= (XMLNode)fXML_elements[thisIndex]; |
| XMLNode otherNode= (XMLNode)other.getXML_elements()[otherIndex]; |
| if ( thisNode.usesIDMAP() && otherNode.usesIDMAP() ) { |
| if ( otherNode.getOrigId().equals(thisNode.getOrigId()) ) { |
| sameId= true; |
| } |
| } |
| |
| //unordered compare of subtrees |
| int distance= dist((XMLNode)other.getXML_elements()[otherIndex] , (XMLNode)fXML_elements[thisIndex]); |
| return sameId || distance == 0; |
| } |
| return false; |
| } |
| |
| /* |
| * @see IRangeComparator#skipRangeComparison(int, int, IRangeComparator) |
| */ |
| public boolean skipRangeComparison( |
| int length, |
| int maxLength, |
| IRangeComparator other) { |
| return false; |
| } |
| |
| public Object[] getXML_elements() { |
| return fXML_elements; |
| } |
| |
| } |
| |
| /* represents a matching between a node in the Left tree and a node in the Right tree */ |
| class Match { |
| public XMLNode fx; |
| public XMLNode fy; |
| |
| Match(XMLNode x, XMLNode y) { |
| fx = x; |
| fy = y; |
| } |
| |
| public boolean equals(Object obj) { |
| if (obj instanceof Match) { |
| Match m = (Match) obj; |
| if (m != null) |
| return fx == m.fx && fy == m.fy; |
| } |
| return false; |
| } |
| } |
| |
| protected int handleRangeDifferencer(Object[] xc_elements, Object[] yc_elements, ArrayList DTMatching, int distance) { |
| RangeDifference[] differences= RangeDifferencer.findDifferences(new XMLComparator(xc_elements), new XMLComparator(yc_elements)); |
| |
| int cur_pos_left= 0; |
| int cur_pos_right= 0; |
| for (int i= 0; i < differences.length; i++) { |
| RangeDifference rd= differences[i]; |
| int equal_length= rd.leftStart(); |
| //handle elements before current range which are unchanged |
| while (cur_pos_left < equal_length) { |
| //assuming XMLComparator has already filled fDT and fDT_Matchings for subtrees |
| //rooted at xc_elements[cur_pos_left] and yc_elements[cur_pos_right] |
| // if ( fDT[indexOfLN( (XMLNode)xc_elements[cur_pos_left])][indexOfRN( (XMLNode)yc_elements[cur_pos_right])] != 0) |
| // System.out.println("distance not 0"); |
| // distance += fDT[indexOfLN( (XMLNode)xc_elements[cur_pos_left])][indexOfRN( (XMLNode)yc_elements[cur_pos_right])]; |
| //DTMatching.addAll(fDT_Matchings[index_left][index_right]); |
| DTMatching.add(new Match( (XMLNode)xc_elements[cur_pos_left], (XMLNode)yc_elements[cur_pos_right])); |
| cur_pos_left++; |
| cur_pos_right++; |
| } |
| //now handle RangeDifference rd[i] |
| int smaller_length, greater_length; |
| boolean leftGreater= rd.leftLength() > rd.rightLength(); |
| if (leftGreater) { |
| smaller_length= rd.rightLength(); |
| greater_length= rd.leftLength(); |
| } else { |
| smaller_length= rd.leftLength(); |
| greater_length= rd.rightLength(); |
| } |
| |
| //handle elements elements in range |
| for (int j=0; j < smaller_length; j++) { |
| distance += dist((XMLNode) xc_elements[cur_pos_left], (XMLNode) yc_elements[cur_pos_right]); |
| DTMatching.add(new Match( (XMLNode)xc_elements[cur_pos_left], (XMLNode)yc_elements[cur_pos_right])); |
| cur_pos_left++; |
| cur_pos_right++; |
| } |
| //int cur_pos_greater= (leftGreater)?cur_pos_left:cur_pos_right; |
| if (leftGreater) { |
| for (int j=smaller_length; j < greater_length; j++) { |
| distance += countNodes((XMLNode) xc_elements[cur_pos_left]); |
| DTMatching.add(new Match( (XMLNode)xc_elements[cur_pos_left], null)); |
| cur_pos_left++; |
| } |
| } else { |
| for (int j=smaller_length; j < greater_length; j++) { |
| distance += countNodes((XMLNode) yc_elements[cur_pos_right]); |
| DTMatching.add(new Match( null, (XMLNode)yc_elements[cur_pos_right])); |
| cur_pos_right++; |
| } |
| } |
| // for (int j=smaller_length; j < greater_length; j++) { |
| // distance += countNodes((XMLNode) xc_elements[cur_pos_greater]); |
| // cur_pos_greater++; |
| // } |
| // if (leftGreater) |
| // cur_pos_left= cur_pos_greater; |
| // else |
| // cur_pos_right= cur_pos_greater; |
| } |
| |
| for (int i= cur_pos_left; i < xc_elements.length; i++) { |
| //distance += fDT[indexOfLN( (XMLNode)xc_elements[cur_pos_left])][indexOfRN( (XMLNode)yc_elements[cur_pos_right])]; |
| //DTMatching.addAll(fDT_Matchings[index_left][index_right]); |
| DTMatching.add(new Match( (XMLNode)xc_elements[cur_pos_left], (XMLNode)yc_elements[cur_pos_right])); |
| cur_pos_left++; |
| cur_pos_right++; |
| } |
| |
| return distance; |
| } |
| |
| abstract public void match(XMLNode LeftTree, XMLNode RightTree, boolean rightTreeIsAncestor, IProgressMonitor monitor) throws InterruptedException; |
| |
| protected int dist(XMLNode x, XMLNode y) { |
| //System.out.println("dist( "+x.getSignature()+" , "+y.getSignature()+")"); |
| int ret= NO_ENTRY; |
| |
| int index_x= indexOfLN(x); |
| int index_y= indexOfRN(y); |
| if (fDT[index_x][index_y] != NO_ENTRY) return fDT[index_x][index_y]; |
| |
| if (isLeaf(x) && isLeaf(y)) { |
| if (x.getXMLType() == XMLStructureCreator.TYPE_ELEMENT) { |
| if ( x.getSignature().equals(y.getSignature()) ) { |
| ret= 0; |
| fDT[index_x][index_y] = ret; |
| } else { |
| ret= 2; |
| fDT[index_x][index_y] = ret; |
| } |
| return ret; |
| } else if (x.getXMLType() == XMLStructureCreator.TYPE_ATTRIBUTE || x.getXMLType() == XMLStructureCreator.TYPE_TEXT) { |
| if ( x.getSignature().equals(y.getSignature()) ) { |
| if (x.getValue().equals(y.getValue())) { |
| ret= 0; |
| fDT[index_x][index_y] = ret; |
| } else { |
| ret= 1; |
| fDT[index_x][index_y] = ret; |
| } |
| } else { |
| ret= 2; |
| fDT[index_x][index_y] = ret; |
| } |
| return ret; |
| } |
| } else {//x or y are not leaves |
| if ( !x.getSignature().equals(y.getSignature()) ) { |
| ret= countNodes(x) + countNodes(y); |
| fDT[index_x][index_y] = ret; |
| return ret; |
| } |
| //x.getSignature().equals(y.getSignature()) |
| if (isLeaf(x)) { |
| ret= countNodes(y)-1; |
| fDT[index_x][index_y] = ret; |
| return ret; |
| } |
| if (isLeaf(y)) { |
| ret= countNodes(x)-1; |
| fDT[index_x][index_y] = ret; |
| return ret; |
| } |
| //both x and y have children |
| return handleXandYnotLeaves(x,y); |
| } |
| return ret; |
| } |
| |
| abstract int handleXandYnotLeaves(XMLNode x, XMLNode y); |
| } |
