/*
 * 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.bcel;

import java.util.ArrayList;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.List;

import t2ext.bcel.utils.Node;
import t2ext.bcel.utils.SimplePath;

/**
 * @author Maaike Gerritsen
 */
public class PrimePathCalculator {
	private Hashtable<Integer, Node> _idToNode;
	private List<SimplePath> _finishedPaths;
	private List<SimplePath> _unfinishedPaths;
	private int _endId;

	public PrimePathCalculator(Hashtable<Integer, Node> idToNode) {
		_idToNode = new Hashtable<Integer, Node>(idToNode);
		_finishedPaths = new ArrayList<SimplePath>();
		filterUnnecessaryNodes();
		setupUnfinishedPaths();
	}
	
	public PrimePathCalculator(){}

	private void filterUnnecessaryNodes() {
		// showTree(0, new ArrayList<Integer>());
		_endId = _idToNode.size() - 1;
		Enumeration<Integer> keys = _idToNode.keys();
		while (keys.hasMoreElements()) {
			Integer id = keys.nextElement();
			// System.out.println("IK: "+id);
			Node node = _idToNode.get(id);
			if (node.isUnnecessaryNode() && id.intValue() != 0) {
				// System.out.println("K: "+node.getId());
				Node childLeft = node.getChildLeft();
				Node childRight = node.getChildRight();
				List<Node> parents = node.getParents();
				if (childLeft != null) {
					modifyChildNode(node, childLeft, parents);
				}
				if (childRight != null) {
					modifyChildNode(node, childRight, parents);
				}
				for (Iterator<Node> iterator = parents.iterator(); iterator
						.hasNext();) {
					Node parent = iterator.next();
					if (parent.getChildLeft().getId() == id.intValue()) {
						parent.setChildLeft(childLeft);
						// parent.setChildRight(childRight);
					}
					if (node.isLast()) {
						parent.setIsLast(true);
						_endId = parent.getId();
					}
					_idToNode.put(parent.getId(), parent);
				}
				_idToNode.remove(id);
			}
		}
	}

	private void modifyChildNode(Node node, Node child, List<Node> parents) {
		child.getParents().remove(node);
		child.getParents().addAll(parents);
		_idToNode.put(child.getId(), child);
	}

	private void setupUnfinishedPaths() {
		_unfinishedPaths = new ArrayList<SimplePath>();
		Enumeration<Integer> keys = _idToNode.keys();
		while (keys.hasMoreElements()) {
			Integer key = keys.nextElement();
			SimplePath pm = new SimplePath(_endId);
			pm.addToList(key, _idToNode.get(key));
			addPathToList(pm);
		}
	}

	private void addPathToList(SimplePath pm) {
		if (pm.getState() == SimplePath.NotFinished)
			_unfinishedPaths.add(pm);
		else
			_finishedPaths.add(pm);
	}

	private void calculatePrimePaths() {
		while (!_unfinishedPaths.isEmpty()) {
			List<SimplePath> copy = new ArrayList<SimplePath>(_unfinishedPaths);
			for (Iterator<SimplePath> iterator = copy.iterator(); iterator
					.hasNext();) {
				SimplePath primePath = iterator.next();
				Integer id = primePath.getList().get(
						primePath.getList().size() - 1);
				Node node = _idToNode.get(id);
				_unfinishedPaths.remove(primePath);
				if (node.getChildRight() != null) {
					SimplePath pm2 = new SimplePath(_endId);
					pm2.setList(primePath.getList());
					pm2.addToList(node.getChildRight().getId(), node
							.getChildRight());
					addPathToList(pm2);
				}
				primePath.addToList(node.getChildLeft().getId(), node
						.getChildLeft());
				addPathToList(primePath);
			}
		}
	}

	public List<List<Integer>> getPrimePaths() {
		calculatePrimePaths();
		List<List<Integer>> result = new ArrayList<List<Integer>>();
		for (Iterator<SimplePath> iterator = _finishedPaths.iterator(); iterator
				.hasNext();) {
			SimplePath pm = iterator.next();
			result.add(pm.getList());
		}
		List<List<Integer>> list = filterList(result);
		return list;
	}

	private List<List<Integer>> filterList(List<List<Integer>> result) {
		List<List<Integer>> finalResult = new ArrayList<List<Integer>>();
		List<List<Integer>> redundantCycles = new ArrayList<List<Integer>>();
		for (int i = 0; i < result.size(); i++) {
			List<Integer> list = result.get(i);
			List<List<Integer>> resultCopy = new ArrayList<List<Integer>>(
					result);
			resultCopy.remove(i);
			String listString = listToString(list);
			String resultString = resultCopy.toString();
			String redundant = redundantCycles.toString();
			if(list.get(0).intValue()==list.get(list.size()-1).intValue() && list.size()>1){//loop
				if(!redundant.contains(listString))
					redundantCycles.addAll(filterCycles(list));
			}
			redundant = redundantCycles.toString();
			if (!resultString.contains(listString) && !redundant.contains(listString))
				finalResult.add(list);
		}
		return finalResult;
	}

	private String listToString(List<Integer> list) {
		String listString = list.toString();
		listString = listString.replace("[", "");
		listString = listString.replace("]", "");
		return listString;
	}

	private List<List<Integer>> filterCycles(List<Integer> list) {
		List<List<Integer>> result = new ArrayList<List<Integer>>();
		List<Integer> copy = new ArrayList<Integer>(list);
		for (int i = 0; i < list.size()-2; i++) {
			Integer firstId = list.get(i+1);
			List<Integer> smallList = new ArrayList<Integer>();
			for (int j = 1; j < copy.size(); j++) {
				Integer id = copy.get(j);
				smallList.add(id);
			}
			smallList.add(firstId);
			copy = new ArrayList<Integer>(smallList);
			result.add(smallList);
		}
		result.add(list);
		int min = list.get(0);
		int index = result.indexOf(list);
		for(int i=0;i<result.size();i++){
			List<Integer> l = result.get(i);
			if(l.get(0).intValue()<min){
				min = l.get(0).intValue();
				index = i;
			}
		}
		result.remove(index);
		return result;
	}
}