/*
 * This file has been developed at the University of Munich, Chair for Programming & Software Engineering.
 * 
 * This file is licensed under the Eclipse Public License (EPL) 1.0
 * 
 */
package eu.mdd4soa.trans.uml2smm.transform;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Queue;
import java.util.Set;
import java.util.concurrent.LinkedBlockingQueue;

import org.eclipse.emf.common.util.EList;
import org.eclipse.uml2.uml.ActivityEdge;
import org.eclipse.uml2.uml.ActivityNode;

import eu.mdd4soa.smm.exception.TransformationException;
import eu.mdd4soa.trans.uml2smm.UMLNodeUtil;

/**
 * Finds partitions in a set of activity nodes corresponding to loops,
 * decisions, and parallel.
 * 
 * We allow partitions which do not have an explicit end node, but only if all
 * paths end in terminations or exceptions (i.e. two incoming edges are never
 * allowed on a non-decision/merge node). This is not a problem for the
 * partitioning algorithm, as:
 * 
 * <ul>
 * <li>Loop in Loop. A loop MUST have a final decision node, and it MUST have a
 * direct edge leading back to the initial merge node. Therefore it is possible
 * to identifiy loop nesting.</li>
 * <li>Decision in Decision. A decision may not have a final merge node, but
 * needs an initial decision node. If no merge is found at all, or it is a loop
 * merge, the complete rest of the elements is assumed to be the decision (note
 * that a new initial decision node inside is not a problem). A merge, however,
 * may be found which belongs to an inner decision. This case, however, is
 * solved by counting the nesting depth. Note that if an inner decision does not
 * have a closing merge, it cannot contribute to the outer merge anyway.</li>
 * <li>Parallel in Parallel.
 * </ul>
 * TODO more documentation.
 * 
 * Another problem is the double meaning of decision and merge nodes: The former
 * might be a branch start or a loop end, while the latter might be a branch end
 * or a loop start.
 * 
 * @author Philip Mayer, mayer@pst.ifi.lmu.de
 * 
 */
public class PathFinder {

	public static enum SearchType {
		LOOP, DECISION, PARALLEL
	}

	public static class FinderResult {

		private ActivityNode fFinalNode;

		private List<ActivityNode> fElements;

		private ActivityNode fNextNode;

		private ActivityNode fStartNode;

		public FinderResult(ActivityNode startNode, ActivityNode finalNode, ActivityNode nextNode, List<ActivityNode> elementsFound) {
			fStartNode= startNode;
			fFinalNode= finalNode;
			fNextNode= nextNode;
			fElements= elementsFound;
		}

		public ActivityNode getFinalNode() {
			return fFinalNode;
		}

		public List<ActivityNode> getElements() {
			return fElements;
		}

		public ActivityNode getNextNode() {
			return fNextNode;
		}

		public ActivityNode getStartNode() {
			return fStartNode;
		}
	}

	private SearchType fSearchType;

	private ActivityNode fStartNode;

	private List<ActivityNode> fElements;

	private FinderResult fResult;

	private ArrayList<ActivityNode> fInPartition;

	private ActivityNode fFinalNode;

	public PathFinder(SearchType searchType, ActivityNode startNode, List<ActivityNode> inElements) {
		fSearchType= searchType;
		fStartNode= startNode;
		fElements= inElements;
	}


	/**
	 * Returns a list of activity nodes which lie between the from node and the
	 * node to look for in the given elements.
	 * 
	 * @param lookFor
	 * @param searchType
	 * @param inElements
	 * @return
	 * @throws TransformationException
	 */
	public static FinderResult resolve(SearchType searchType, ActivityNode startNode, List<ActivityNode> inElements) throws TransformationException {

		PathFinder p= new PathFinder(searchType, startNode, inElements);
		p.execute();
		return p.getResult();
	}

	private void execute() throws TransformationException {

		fInPartition= new ArrayList<ActivityNode>();
		fFinalNode= null;

		look(fStartNode, 0);

		/*
		 * If an end is required but we did not find one, throw an exception.
		 */
		if (fFinalNode == null && fSearchType.equals(SearchType.LOOP))
			throw new TransformationException("Could not find an end node from " + fStartNode + " looking for a " + fSearchType);

		/*
		 * Find out if there are any nodes after the path we just find. If there
		 * is no final node, there is obviously no next node.
		 */
		ActivityNode nextNode= null;

		if (fFinalNode != null) {

			List<ActivityNode> nextElements= UMLNodeUtil.getNextElements(fFinalNode);
			if (nextElements.size() == 0) {
				// No next node.
				nextNode= null;
			} else if (nextElements.size() == 1)
				// One definite next node. In case of loops, this might still
				// not be what we are looking for...

				if (nextElements.get(0).equals(fStartNode))
					nextNode= null;
				else
					nextNode= nextElements.get(0);
			if (nextElements.size() > 1) {

				/*
				 * Multiple next nodes after the final node.
				 */
				if (fSearchType.equals(SearchType.LOOP)) {
					/*
					 * Did we look for a loop? In this case, one of the outgoing
					 * links must lead back to the start.
					 */
					if (nextElements.get(0).equals(fStartNode)) {
						nextNode= nextElements.get(1);
					} else if (nextElements.get(1).equals(fStartNode))
						nextNode= nextElements.get(0);
					else
						throw new TransformationException("Found an end node from " + fStartNode + " looking for a " + fSearchType
								+ ", but 2 outgoing edges from the final node " + fFinalNode + " of which none leads back to the start node.");
				} else {
					/*
					 * We were not looking for a loop. Multiple outgoing edges
					 * are thus not acceptable.
					 */
					throw new TransformationException("Found an end node from " + fStartNode + " looking for a " + fSearchType
							+ ", but multiple outgoing edges from the final node " + fFinalNode);
				}
			}
		}

		fResult= new FinderResult(fStartNode, fFinalNode, nextNode, fInPartition);
	}

	private void look(ActivityNode newElement, int nestingDepth) {

		int nextDepth= nestingDepth;
		boolean found= false;

		// In some cases, an element might occur multiple times (for
		// example, the closing merge node of a branch).
		if (fInPartition.contains(newElement))
			return;

		fInPartition.add(newElement);

		System.out.println("  PathFinder:: look " + newElement);

		// Check if we need to change the nesting depth.
		if (!newElement.equals(fStartNode)) {
			switch (fSearchType) {
				case PARALLEL: {
					/*
					 * A fork node always means increase of depth on this path.
					 */
					if (UMLNodeUtil.isForkNode(newElement))
						nextDepth++;
					break;
				}
				case LOOP: {
					/*
					 * Another loop start node increases the depth.
					 */
					if (isLoopStart(newElement))
						nextDepth++;
					break;
				}
				case DECISION: {
					/*
					 * Another decision start node increases the depth.
					 */
					if (isBranchStart(newElement))
						nextDepth++;
					break;
				}
			}
		}

		// Check if we are done or if we need to decrease the nesting depth.
		switch (fSearchType) {
			case PARALLEL: {
				/*
				 * Parallel is ended by a join node.
				 */
				if (UMLNodeUtil.isJoinNode(newElement)) {
					if (nextDepth == 0) {
						fFinalNode= newElement;
						found= true;
						// Do not continue.
					} else {
						nextDepth--;
					}
				}
				break;
			}
			case LOOP: {
				/*
				 * Loops are ended by a decision node which is NOT a branch
				 * start :)
				 */
				if (UMLNodeUtil.isDecisionNode(newElement) && !isBranchStart(newElement)) {
					if (nextDepth == 0) {
						fFinalNode= newElement;
						found= true;
						// Do not continue.
					} else {
						nextDepth--;
					}
				}
				break;
			}
			case DECISION: {
				/*
				 * Decisions are ended by a merge node which is not a loop
				 * start.
				 */
				if (UMLNodeUtil.isMergeNode(newElement) && !isLoopStart(newElement)) {
					if (nextDepth == 0) {
						fFinalNode= newElement;
						found= true;
						// Do not continue.
					} else {
						nextDepth--;
					}
				}
				break;
			}
		}

		if (!found) {
			/*
			 * No, we have not found it. This means we need to continue on
			 * outgoing paths.
			 */
			Collection<? extends ActivityNode> nextElements= UMLNodeUtil.getNextElements(newElement);
			for (ActivityNode activityNode : nextElements) {
				/*
				 * We only continue if we do not go back to the start (loops!)
				 * and if the element is in fact in our scan range.
				 */
				if (!activityNode.equals(fStartNode) && fElements.contains(activityNode))
					look(activityNode, nextDepth);
			}
		}

	}

	public FinderResult getResult() {
		return fResult;
	}

	/**
	 * 
	 * isLoopStart() returns true for a node if:
	 * <ul>
	 * <li>The node is a merge node.</li>
	 * <li>There is a decision node which comes AFTER the given node in the path
	 * and it has a link back to the given node.</li>
	 * </ul>
	 * 
	 * Note that the above criteria rule out that the node is a decision end
	 * node. So, if !isLoopStart(some merge node), then the merge node is a
	 * branch end.
	 * 
	 * @param currentNode
	 * @return
	 */
	private boolean isLoopStart(ActivityNode currentNode) {

		if (!UMLNodeUtil.isMergeNode(currentNode))
			return false;

		Queue<ActivityNode> look= new LinkedBlockingQueue<ActivityNode>();
		look.add(currentNode);

		Set<ActivityNode> seen= new HashSet<ActivityNode>();

		while (!look.isEmpty()) {

			ActivityNode current= look.poll();
			seen.add(current);

			EList<ActivityEdge> outgoings= current.getOutgoings();
			for (ActivityEdge activityEdge : outgoings) {
				ActivityNode target= activityEdge.getTarget();

				if (UMLNodeUtil.isDecisionNode(current) && target.equals(currentNode))
					return true;

				if (!seen.contains(target) && fElements.contains(target))
					look.add(target);
			}
		}

		return false;
	}

	/**
	 * isBranchStart() is true for a given node if
	 * <ul>
	 * <li>it is a decision node.</li>
	 * <li>there is no merge node before the given node in the path which
	 * contains an incoming link which comes from the given node.</li>
	 * </ul>
	 * 
	 * Note that the above criteria rule out that the node is a loop end node.
	 * So, if !isBranchStart(some decision node), then the decision node is a
	 * loop end.
	 * 
	 * @param currentNode
	 * @return
	 */
	private boolean isBranchStart(ActivityNode currentNode) {

		if (!UMLNodeUtil.isDecisionNode(currentNode))
			return false;

		Queue<ActivityNode> look= new LinkedBlockingQueue<ActivityNode>();
		look.add(currentNode);

		Set<ActivityNode> seen= new HashSet<ActivityNode>();

		while (!look.isEmpty()) {

			ActivityNode current= look.poll();
			seen.add(current);

			EList<ActivityEdge> incomings= current.getIncomings();
			for (ActivityEdge activityEdge : incomings) {

				ActivityNode source= activityEdge.getSource();

				if ( (UMLNodeUtil.isMergeNode(current) && source.equals(currentNode)))
					return false;

				if (!seen.contains(source) && fElements.contains(source))
					look.add(source);
			}
		}
		return true;
	}
}
