/*
 * Copyright 2008 Wishnu Prasetya.
 *
 * This file is part of T2.
 * T2 is free software; you can redistribute it and/or modify it under
 * the terms of the GNU General Public License (GPL) as published by the
 * Free Software Foundation; either version 3 of the License, or any
 * later version.
 * 
 * T2 is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * for more details.
 *
 * A copy of the GNU General Public License can be found in T2 distribution.
 * If it is missing, see http://www.gnu.org/licenses.
 */

package t2ext.trace;

import java.util.ArrayList;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import org.w3c.dom.Document;
import org.w3c.dom.Element;
import org.w3c.dom.NodeList;

import t2ext.xml.XMLBuilder;

/**
 * @author Maaike Gerritsen
 */
public class PathComparison {
	Hashtable<Integer, Integer> _matchPaths;
	List<Integer> _loopOwnIds;
	int _longestPath;

	@SuppressWarnings("unchecked")
	public Hashtable<Integer, Integer> findBestPath(Element method) {
		_matchPaths = new Hashtable<Integer, Integer>();
		List<Element> unfoundPaths = new ArrayList<Element>();
		List<Element> foundPaths = new ArrayList<Element>();
		boolean first = true;
		// String name = method.getAttribute("name").toString();
		NodeList paths = method.getChildNodes();
		for(int i=0;i<paths.getLength();i++) {
			Element path = (Element) paths.item(i);
			Element nodes = (Element) path.getChildNodes().item(0);
			String value = nodes.getAttribute("value").toString();
			String[] split = value.split(", ");
			int children = split.length;
			if (first) {
				first = false;
				_longestPath = children;
			} else if (children > _longestPath) {
				_longestPath = children;
			}
			boolean found = new Boolean(path.getAttribute("found").toString());
			if (found)
				foundPaths.add(path);
			else
				unfoundPaths.add(path);
		}
		if (unfoundPaths.size() > 0)
			matchPaths(foundPaths, unfoundPaths);
		return _matchPaths;
	}

	private void matchPaths(List<Element> foundPaths,
			List<Element> unfoundPaths) {
		for (Iterator<Element> iterator = unfoundPaths.iterator(); iterator
				.hasNext();) {
			Element path = iterator.next();
			Document doc = (new XMLBuilder()).getNewDocument();
			Element bestPath = doc.createElement("path");
			int lowestDifference = _longestPath;
			for (Iterator<Element> iterator2 = foundPaths.iterator(); iterator2
					.hasNext();) {
				Element fPath = iterator2.next();
				int difference = comparePaths(path, fPath);
				if (difference < lowestDifference) {
					bestPath = fPath;
					lowestDifference = difference;
				}
			}
			Integer id = new Integer(path.getAttribute("id").toString());
			if (bestPath.getAttribute("id") != null) {
				Integer fId = new Integer(bestPath.getAttribute("id")
						.toString());
				_matchPaths.put(id, fId);
			}
		}
	}

	@SuppressWarnings("unchecked")
	private int comparePaths(Element path, Element fPath) {
		int different = 0;
		Queue<String> queue = createQueueFromNodes((Element) path.getChildNodes().item(0));
		Queue<String> fQueue = createQueueFromNodes((Element) fPath.getChildNodes().item(0));
		while (!queue.isEmpty()) {
			String edge = queue.poll();
			if (!fQueue.isEmpty()) {
				String fEdge = fQueue.peek();
				if (!edge.equals(fEdge) && !fQueue.contains(edge)) {
					different++;
				} else if (!edge.equals(fEdge) && fQueue.contains(edge)) {
					fEdge = fQueue.poll();
					while (!fEdge.equals(edge)) {
						fEdge = fQueue.poll();
					}
				} else {
					fQueue.poll();
				}
			} else {
				different += queue.size() + 1; // first has already been polled
			}
		}
		return different;
	}

	private Queue<String> createQueueFromNodes(Element nodes) {
		String value = nodes.getAttribute("value").toString();
		String[] split = value.split(", ");
		Queue<String> queue = new LinkedList<String>();
		for (int i = 0; i < split.length - 1; i++) {
			String id = split[i];
			String nextId = split[i+1];
			id += "," + nextId;
			queue.add(id);
		}
		return queue;
	}

//	@SuppressWarnings("unchecked")
//	public void checkForSideTrips() {
//		XMLBuilder builder = new XMLBuilder();
//		XMLElement root = builder.readXMLFile("paths.xml");
//		Enumeration<XMLElement> methods = root.enumerateChildren();
//		while (methods.hasMoreElements()) {
//			XMLElement method = methods.nextElement();
//			boolean allFound = new Boolean(method.getAttribute("allfound")
//					.toString());
//			if (method.getChildren().size() > 1 && !allFound) {
//				studyPathsPerMethod(method);
//			}
//		}
//	}

//	@SuppressWarnings("unchecked")
//	private void studyPathsPerMethod(XMLElement method) {
//		List<XMLElement> loops = getLoops(method);
//		if (loops.size() > 0) { // if there are no loops, then there are no
//								// sidetrips allowed
//
//		}
//	}
//
//	@SuppressWarnings("unchecked")
//	private List<XMLElement> getLoops(XMLElement method) {
//		_loopOwnIds = new ArrayList<Integer>();
//		List<XMLElement> loops = new ArrayList<XMLElement>();
//		Enumeration<XMLElement> paths = method.enumerateChildren();
//		while (paths.hasMoreElements()) {
//			XMLElement path = paths.nextElement();
//			Vector<XMLElement> nodes = path.getChildren();
//			int firstValue = Integer.parseInt(nodes.get(0)
//					.getAttribute("value").toString());
//			int lastValue = Integer.parseInt(nodes.get(nodes.size() - 1)
//					.getAttribute("value").toString());
//			if (firstValue == lastValue) {
//				loops.add(path);
//				if (nodes.size() == 2) {
//					Integer id = new Integer(path.getAttribute("id").toString());
//					_loopOwnIds.add(id);
//				}
//			}
//		}
//		return loops;
//	}

}