/*******************************************************************************
 * Copyright (c) 2000, 2003 IBM Corporation and others.
 * All rights reserved. This program and the accompanying materials 
 * are made available under the terms of the Common Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/cpl-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;
		for (i=0; (i<fNLeft.size()) && (fNLeft.elementAt(i) != x); i++);
		return i;
	}
	
	/* returns index of node y in fNRight */
	protected int indexOfRN (XMLNode y) {
		int j;
		for (j=0; (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;
					return 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;
						return ret;
					} else {
						ret= 1;
						fDT[index_x][index_y] = ret;
						return 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;
			} else {//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);
}