| /******************************************************************************* |
| * 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.Iterator; |
| import java.util.ListIterator; |
| import java.util.Vector; |
| |
| import org.eclipse.core.runtime.IProgressMonitor; |
| |
| public class OrderedMatching extends AbstractMatching { |
| |
| public OrderedMatching() { |
| super(); |
| } |
| |
| protected int orderedMath(XMLNode x, XMLNode y) { |
| //assumes x and y have children |
| Object[] xc= x.getChildren(); |
| Object[] yc= y.getChildren(); |
| |
| ArrayList xc_elementsAL= new ArrayList(); |
| ArrayList xc_attrsAL= new ArrayList(); |
| |
| ArrayList yc_elementsAL= new ArrayList(); |
| ArrayList yc_attrsAL= new ArrayList(); |
| |
| //find attributes and elements and put them in xc_elementsAL and xc_attrsAL, respectively |
| for (int i= 0; i < xc.length; i++) { |
| XMLNode x_i= (XMLNode) xc[i]; |
| if (x_i.getXMLType().equals(XMLStructureCreator.TYPE_ELEMENT)) { |
| xc_elementsAL.add(x_i); |
| } else if ( |
| x_i.getXMLType().equals(XMLStructureCreator.TYPE_ATTRIBUTE)) { |
| xc_attrsAL.add(x_i); |
| } |
| } |
| |
| //do the same for yc |
| for (int i= 0; i < yc.length; i++) { |
| XMLNode y_i= (XMLNode) yc[i]; |
| if (y_i.getXMLType().equals(XMLStructureCreator.TYPE_ELEMENT)) { |
| yc_elementsAL.add(y_i); |
| } else if ( |
| y_i.getXMLType().equals(XMLStructureCreator.TYPE_ATTRIBUTE)) { |
| yc_attrsAL.add(y_i); |
| } |
| } |
| |
| Object[] xc_elements= xc_elementsAL.toArray(); |
| Object[] yc_elements= yc_elementsAL.toArray(); |
| |
| ArrayList DTMatching= new ArrayList(); |
| // Matching to be added to Entry in fDT_Matchings |
| int distance= 0; //distance to be added to entry in fDT |
| |
| // perform unordered matching on attributes |
| // this updates fDT and fDT_Matchings |
| if (xc_attrsAL.size() > 0 || yc_attrsAL.size() > 0) { |
| if (xc_attrsAL.size() == 0) |
| distance += yc_attrsAL.size(); |
| else if (yc_attrsAL.size() == 0) |
| distance += xc_attrsAL.size(); |
| else { |
| //unorderedMatch(x, y, xc_attrs, yc_attrs); |
| // distance += fDT[indexOfLN(x)][indexOfRN(y)]; |
| // DTMatching= fDT_Matchings[indexOfLN(x)][indexOfRN(y)]; |
| distance= handleAttributes(xc_attrsAL, yc_attrsAL, DTMatching); |
| } |
| } |
| |
| //perform ordered matching on element children, i.e. number them in order of appearance |
| |
| /* start new */ |
| distance= |
| handleRangeDifferencer( |
| xc_elements, |
| yc_elements, |
| DTMatching, |
| distance); |
| /* end new */ |
| |
| /* start: Naive ordered compare /* |
| // int minlength= (xc_elements.length > yc_elements.length)?yc_elements.length:xc_elements.length; |
| // for (int i= 0; i < minlength; i++) { |
| // distance += dist((XMLNode) xc_elements[i], (XMLNode) yc_elements[i]); |
| // DTMatching.add(new Match( (XMLNode)xc_elements[i], (XMLNode)yc_elements[i])); |
| // } |
| // if (xc_elements.length > yc_elements.length) { |
| // for (int i= minlength; i < xc_elements.length; i++) { |
| // distance += countNodes((XMLNode) xc_elements[i]); |
| // } |
| // } else if (xc_elements.length < yc_elements.length) { |
| // for (int i= minlength; i < yc_elements.length; i++) { |
| // distance += countNodes((XMLNode) yc_elements[i]); |
| // } |
| // } |
| /* end: Naive ordered compare */ |
| |
| fDT[indexOfLN(x)][indexOfRN(y)]= distance; |
| fDT_Matchings[indexOfLN(x)][indexOfRN(y)]= DTMatching; |
| return distance; |
| |
| } |
| |
| /* matches two trees according to paper "X-Diff", p. 16 */ |
| public void match( |
| XMLNode LeftTree, |
| XMLNode RightTree, |
| boolean rightTreeIsAncestor, |
| IProgressMonitor monitor) |
| throws InterruptedException { |
| |
| fNLeft= new Vector(); |
| //numbering LeftTree: Mapping nodes in LeftTree to numbers to be used as array indexes |
| fNRight= new Vector(); |
| //numbering RightTree: Mapping nodes in RightTree to numbers to be used as array indexes |
| numberNodes(LeftTree, fNLeft); |
| numberNodes(RightTree, fNRight); |
| fDT= new int[fNLeft.size()][fNRight.size()]; |
| fDT_Matchings= new ArrayList[fNLeft.size()][fNRight.size()]; |
| for (int i= 0; i < fDT.length; i++) { |
| fDT[i]= new int[fNRight.size()]; |
| for (int j= 0; j < fDT[0].length; j++) { |
| fDT[i][j]= NO_ENTRY; |
| } |
| } |
| |
| dist(LeftTree, RightTree); |
| // /* mark matchings on LeftTree and RightTree */ |
| fMatches= new Vector(); |
| if (!LeftTree.getSignature().equals(RightTree.getSignature())) { |
| //matching is empty |
| } else { |
| fMatches.add(new Match(LeftTree, RightTree)); |
| for (int i_M= 0; i_M < fMatches.size(); i_M++) { |
| Match m= (Match) fMatches.elementAt(i_M); |
| if (!isLeaf(m.fx) && !isLeaf(m.fy)) { |
| // if (fDT_Matchings[ indexOfLN(m.fx) ][ indexOfRN(m.fy) ] == null) |
| // System.out.println("Error: ID not unique for " + m.fx.getId()); |
| // else |
| // fMatches.addAll(fDT_Matchings[ indexOfLN(m.fx) ][ indexOfRN(m.fy) ]); |
| if (fDT_Matchings[indexOfLN(m.fx)][indexOfRN(m.fy)] |
| != null) |
| fMatches.addAll( |
| fDT_Matchings[indexOfLN(m.fx)][indexOfRN(m.fy)]); |
| } |
| } |
| } |
| //end of Step2 |
| /* Renumber Id of Nodes to follow Matches. Or for ancestor, copy over Id to ancestor */ |
| if (rightTreeIsAncestor) { |
| for (ListIterator it_M= fMatches.listIterator(); it_M.hasNext();) { |
| Match m= (Match) it_M.next(); |
| if (m.fx != null && m.fy != null) |
| m.fy.setId(m.fx.getId()); |
| } |
| } else { |
| int newId= 0; |
| for (ListIterator it_M= fMatches.listIterator(); |
| it_M.hasNext(); |
| newId++) { |
| Match m= (Match) it_M.next(); |
| if (m.fx != null) |
| m.fx.setId(Integer.toString(newId)); |
| if (m.fy != null) |
| m.fy.setId(Integer.toString(newId)); |
| // System.out.println("Matching: "+ ((m.fx != null)?m.fx.getOrigId():"null")+" -> "+((m.fx != null)?m.fx.getId():"null")+" , "+((m.fy != null)?m.fy.getOrigId():"null")+" -> "+((m.fy != null)?m.fy.getId():"null")); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$ |
| } |
| } |
| //if (monitor != null) monitor.done(); |
| } |
| |
| public int handleAttributes( |
| ArrayList xc_attrs, |
| ArrayList yc_attrs, |
| ArrayList DTMatching) { |
| int distance= 0; |
| x_for : for ( |
| Iterator iter_xc= xc_attrs.iterator(); iter_xc.hasNext();) { |
| XMLNode x_attr= (XMLNode) iter_xc.next(); |
| String x_attr_name= x_attr.getName(); |
| for (Iterator iter_yc= yc_attrs.iterator(); iter_yc.hasNext();) { |
| XMLNode y_attr= (XMLNode) iter_yc.next(); |
| if (y_attr.getName().equals(x_attr_name)) { |
| if (!y_attr.getValue().equals(x_attr.getValue())) |
| distance += 1; |
| DTMatching.add(new Match(x_attr, y_attr)); |
| yc_attrs.remove(y_attr); |
| continue x_for; |
| } |
| } |
| DTMatching.add(new Match(x_attr, null)); |
| distance += 1; |
| } |
| |
| for (Iterator iter_yc= yc_attrs.iterator(); iter_yc.hasNext();) { |
| DTMatching.add(new Match(null, (XMLNode) iter_yc.next())); |
| distance += 1; |
| } |
| |
| return distance; |
| } |
| |
| protected int handleXandYnotLeaves(XMLNode x, XMLNode y) { |
| /* handle entries as ordered*/ |
| return orderedMath(x, y); |
| } |
| } |