/*******************************************************************************
 * Copyright (c) 2015, 2018 Willink Transformations and others.
 * All rights reserved.   This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v2.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v20.html
 *
 * Contributors:
 *   E.D.Willink - Initial API and implementation
 *******************************************************************************/
package org.eclipse.qvtd.compiler.internal.qvts2qvts.utilities;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.eclipse.jdt.annotation.NonNull;
import org.eclipse.jdt.annotation.Nullable;
import org.eclipse.ocl.pivot.utilities.ClassUtil;
import org.eclipse.qvtd.pivot.qvtschedule.Edge;
import org.eclipse.qvtd.pivot.qvtschedule.NavigableEdge;
import org.eclipse.qvtd.pivot.qvtschedule.NavigationEdge;
import org.eclipse.qvtd.pivot.qvtschedule.Node;
import org.eclipse.qvtd.pivot.qvtschedule.SharedEdge;
import org.eclipse.qvtd.pivot.qvtschedule.utilities.QVTscheduleUtil;
import com.google.common.collect.Lists;

/**
 * The ReachabilityForest comprises a tree of preferred edge paths from each head/leaf-constant root node to the
 * nodes that can be reached from them. It answers the question: what preceding nodes are necessary to ensure
 * that a given node is reachable.
 */
public class ReachabilityForest
{
	private static final int FORWARD_NAVIGATION_COST = 1;
	private static final int INVERSE_MANY_NAVIGATION_COST = 5;
	private static final int INVERSE_NAVIGATION_COST = 3;
	private static final int ITERATOR_COST = 1;
	private static final int OPERATION_COST = 10;
	private static final int RESULT_COST = 1;
	private static final int SHARED_NAVIGATION_COST = 10;

	/**
	 * The preferred non-secondary edges to be used in the tree.
	 */
	private final @NonNull Set<@NonNull NavigationEdge> forwardEdges = new HashSet<>();

	/**
	 * The shared edges to be used in the tree.
	 */
	private @Nullable List<@NonNull SharedEdge> sharedEdges = null;

	/**
	 * Edges that have no opposite.
	 */
	private final @NonNull Set<@NonNull Edge> manyToOneEdges = new HashSet<>();

	/**
	 * The incoming edge for each node in the traversal forest, null at a root.
	 */
	private final @NonNull Map<@NonNull Node, @Nullable Edge> node2reachingEdge = new HashMap<>();

	/**
	 * The cost for each node from the root in the traversal forest, 0 at a root. The cost is equal
	 * to the sum of the costs of each edge on the lowest cost path from the root.
	 */
	private @NonNull Map<@NonNull Node, @NonNull Integer> node2cost = new HashMap<>();

	/**
	 * Lazily created compartor to order nodes lowest cost first.
	 */
	private @Nullable Comparator<@NonNull Edge> edgeCostComparator = null;

	/**
	 * Lazily created compartor to order nodes lowest cost first.
	 */
	private @Nullable Comparator<@NonNull Node> nodeCostComparator = null;


	/**
	 * Construct the Reachability forest for the specified rootNodes using the availableNavigableEdges to locate
	 * paths to further nodes and also any old computation edges.
	 */
	public ReachabilityForest(@NonNull Iterable<@NonNull Node> rootNodes, @NonNull Iterable<@NonNull NavigableEdge> availableNavigableEdges) {
		for (@NonNull Node rootNode : rootNodes) {
			node2reachingEdge.put(rootNode, null);
		}
		for (@NonNull NavigableEdge edge : availableNavigableEdges) {
			addEdge(edge);
		}
		//
		//	Analyze the descendants of the roots to identify the most simply navigated forest.
		//
		analyze(node2reachingEdge.keySet());
	}

	protected void addEdge(@NonNull NavigableEdge edge) {
		if (edge instanceof NavigationEdge) {
			NavigationEdge navigationEdge = (NavigationEdge)edge;
			if (!navigationEdge.isSecondary()) {
				forwardEdges.add(navigationEdge);
				if ((navigationEdge.getEdgeSource().isClass()) && (navigationEdge.getOppositeEdge() == null)) {
					manyToOneEdges.add(navigationEdge);
				}
			}
		}
		else if (edge instanceof SharedEdge) {
			List<@NonNull SharedEdge> sharedEdges2 = sharedEdges;
			if (sharedEdges2 == null) {
				sharedEdges = sharedEdges2 = new ArrayList<>();
			}
			sharedEdges2.add((SharedEdge)edge);
		}
	}

	/**
	 * Identify the forest from the given roots.
	 */
	protected void analyze(@NonNull Iterable<@NonNull Node> rootNodes) {
		List<@Nullable List<@NonNull Node>> costs2nodes = new ArrayList<>();
		for (@NonNull Node rootNode : rootNodes) {
			node2cost.put(rootNode, 0);
		}
		costs2nodes.add(Lists.newArrayList(rootNodes));
		//
		//	Advance breadth first, one cost at a time, accumulating all edges that make one stage of progress.
		//
		for (int thisCost = 0; thisCost < costs2nodes.size(); thisCost++) {
			List<@NonNull Node> thisCostNodes = costs2nodes.get(thisCost);
			if (thisCostNodes != null) {
				//
				//	Add the forward edges that make progress to moreMoreNodes and remember the
				//	backward and inverse edges in case forward egdes alone are inadequate.
				//
				for (@NonNull Node sourceNode : thisCostNodes) {
					assert node2cost.get(sourceNode) == thisCost;
					for (@NonNull Edge edge : QVTscheduleUtil.getOutgoingEdges(sourceNode)) {
						assert !edge.isCast();
						Node targetNode = edge.getEdgeTarget();
						if (!node2reachingEdge.containsKey(targetNode)) {
							Integer targetCost = node2cost.get(targetNode);
							assert (targetCost == null) || (thisCost < targetCost);
							if (edge.isNavigation()) {
								NavigationEdge navigationEdge = (NavigationEdge) edge;
								if (forwardEdges.contains(navigationEdge)) {
									int nextCost = thisCost + FORWARD_NAVIGATION_COST;
									if ((targetCost == null) || (nextCost < targetCost)) {
										node2cost.put(targetNode, nextCost);
										node2reachingEdge.put(targetNode, edge);
										putCosts(costs2nodes, nextCost, targetNode);
									}
								}
								else {
									NavigationEdge oppositeEdge = navigationEdge.getOppositeEdge();
									if (forwardEdges.contains(oppositeEdge)) {
										boolean isImplicit = QVTscheduleUtil.getReferredProperty(oppositeEdge).isIsImplicit();
										int nextCost = thisCost + (isImplicit ? INVERSE_NAVIGATION_COST : FORWARD_NAVIGATION_COST);
										if ((targetCost == null) || (nextCost < targetCost)) {
											node2cost.put(targetNode, nextCost);
											node2reachingEdge.put(targetNode, oppositeEdge);
											putCosts(costs2nodes, nextCost, targetNode);
										}
									}
									else if (manyToOneEdges.contains(oppositeEdge)) {
										int nextCost = thisCost + INVERSE_MANY_NAVIGATION_COST;
										if ((targetCost == null) || (nextCost < targetCost)) {
											node2cost.put(targetNode, nextCost);
											node2reachingEdge.put(targetNode, oppositeEdge);
											putCosts(costs2nodes, nextCost, targetNode);
										}
									}
								}
							}
							else if (edge.isComputation() /*&& edge.isUnconditional()*/) {
								int nextCost = thisCost + OPERATION_COST;
								if (targetNode.isOperation()) {
									for (@NonNull Edge incomingEdge : QVTscheduleUtil.getIncomingEdges(targetNode)) {
										if (incomingEdge.isOld() && incomingEdge.isComputation()) {
											Node node = QVTscheduleUtil.getSourceNode(incomingEdge);
											Integer cost = node2cost.get(node);
											if ((cost == null) || (cost > thisCost)) {
												nextCost = -1;
												break;
											}
										}
									}
								}
								else if (targetNode.isIterator()) {
									nextCost = thisCost + ITERATOR_COST;
								}
								else {
									nextCost = thisCost + RESULT_COST;
								}
								if (nextCost > 0) {
									if ((targetCost == null) || (nextCost < targetCost)) {
										node2cost.put(targetNode, nextCost);
										node2reachingEdge.put(targetNode, edge);
										putCosts(costs2nodes, nextCost, targetNode);
									}
								}
							}
						}
					}
				}
			}
		}
		if (sharedEdges != null) {
			for (@NonNull SharedEdge sharedEdge : sharedEdges) {
				Node targetNode = sharedEdge.getEdgeTarget();
				if (!node2reachingEdge.containsKey(targetNode)) {
					Integer targetCost = node2cost.get(targetNode);
					assert targetCost == null;
					Node sourceNode = sharedEdge.getEdgeSource();
					Integer sourceCost = node2cost.get(sourceNode);
					if (sourceCost != null) {
						int nextCost = sourceCost + SHARED_NAVIGATION_COST;
						node2cost.put(targetNode, nextCost);
						node2reachingEdge.put(targetNode, sharedEdge);
					}
				}
			}
		}
	}

	public @Nullable Integer getCost(@NonNull Node node) {
		return node2cost.get(node);
	}

	/**
	 * Return a comparator to sort edges source cost first then target cost then alphabetically.
	 */
	public @NonNull Comparator<@NonNull Edge> getEdgeCostComparator() {
		Comparator<@NonNull Edge> edgeCostComparator2 = edgeCostComparator;
		if (edgeCostComparator2 == null) {
			edgeCostComparator = edgeCostComparator2 = new Comparator<@NonNull Edge>()
			{
				@Override
				public int compare(@NonNull Edge e1, @NonNull Edge e2) {
					Node s1 = QVTscheduleUtil.getSourceNode(e1);
					Node t1 = QVTscheduleUtil.getTargetNode(e1);
					Node s2 = QVTscheduleUtil.getSourceNode(e2);
					Node t2 = QVTscheduleUtil.getTargetNode(e2);
					Integer d1s = node2cost.get(s1);
					Integer d1t = node2cost.get(t1);
					Integer d2s = node2cost.get(s2);
					Integer d2t = node2cost.get(t2);
					assert d1s != null : s1 + " is not reachable within " + s1.getOwningRegion();		// FIXME chnage to PartitionProblem
					assert d1t != null : t1 + " is not reachable within " + t1.getOwningRegion();
					assert d2s != null : s2 + " is not reachable within " + s2.getOwningRegion();
					assert d2t != null : t2 + " is not reachable within " + t2.getOwningRegion();
					int d1 = Math.max(d1s,  d1t);
					int d2 = Math.max(d2s,  d2t);
					if (d1 != d2) {
						return d1 - d2;
					}
					if (d1s != d2s) {
						return d1s - d2s;
					}
					String n1 = e1.getDisplayName();
					String n2 = e2.getDisplayName();
					int d = ClassUtil.safeCompareTo(n1, n2);
					if (d != 0) {
						return d;
					}
					n1 = s1.getDisplayName();
					n2 = s2.getDisplayName();
					d = ClassUtil.safeCompareTo(n1, n2);
					if (d != 0) {
						return d;
					}
					n1 = t1.getDisplayName();
					n2 = t2.getDisplayName();
					d = ClassUtil.safeCompareTo(n1, n2);
					return d;
				}
			};
		}
		return edgeCostComparator2;
	}

	/**
	 * Return a comparator to sort nodes cost first then alphabetically.
	 */
	public @NonNull Comparator<@NonNull Node> getNodeCostComparator() {
		Comparator<@NonNull Node> nodeCostComparator2 = nodeCostComparator;
		if (nodeCostComparator2 == null) {
			nodeCostComparator = nodeCostComparator2 = new Comparator<@NonNull Node>()
			{
				@Override
				public int compare(@NonNull Node o1, @NonNull Node o2) {
					Integer c1 = node2cost.get(o1);
					Integer c2 = node2cost.get(o2);
					assert (c1 != null) && (c2 != null);
					int diff = c1 - c2;
					if (diff != 0) {
						return diff;
					}
					return ClassUtil.safeCompareTo(o1.getName(), o2.getName());
				}
			};
		}
		return nodeCostComparator2;
	}

	public @NonNull Iterable<@NonNull Node> getNodes() {
		return node2reachingEdge.keySet();
	}

	public @NonNull Iterable<@NonNull Node> getPredecessors(@NonNull Node targetNode) {
		Set<@NonNull Node> precedingNodes = new HashSet<@NonNull Node>();
		getPredecessors(precedingNodes, targetNode);
		precedingNodes.remove(targetNode);
		return precedingNodes;
	}
	private void getPredecessors(@NonNull Set<@NonNull Node> precedingNodes, @NonNull Node targetNode) {
		if (precedingNodes.add(targetNode)) {
			Edge parentEdge = null;
			if (targetNode.isOperation()) {
				Edge reachingEdge = getReachingEdge(targetNode);
				if ((reachingEdge != null) && reachingEdge.isNavigation()) {
					parentEdge = reachingEdge;
				}
				else {
					for (@NonNull Edge edge : QVTscheduleUtil.getIncomingEdges(targetNode)) {
						assert !edge.isCast();
						if (edge.isComputation() || (edge.isNavigation() && !edge.isRealized())) {
							getPredecessors(precedingNodes, edge.getEdgeSource());
						}
					}
				}
			}
			else {
				parentEdge = getReachingEdge(targetNode);
			}
			if (parentEdge != null) {
				Node sourceNode = parentEdge.getEdgeSource();
				if (sourceNode == targetNode) {		// invert a backward edge
					sourceNode = parentEdge.getEdgeTarget();
				}
				getPredecessors(precedingNodes, sourceNode);
			}
		}
	}

	/**
	 * Return the edge from the preceding reachable node to the given reachable node. Null if none.
	 */
	public @Nullable Edge getReachingEdge(@NonNull Node node) {
		return node2reachingEdge.get(node);
	}

	private void putCosts(@NonNull List<@Nullable List<@NonNull Node>> costs2nodes, int cost, @NonNull Node node) {
		while (costs2nodes.size() <= cost) {
			costs2nodes.add(null);
		}
		List<@NonNull Node> nodes = costs2nodes.get(cost);
		if (nodes == null) {
			nodes = new ArrayList<>();
			costs2nodes.set(cost, nodes);
		}
		if (!nodes.contains(node)) {
			nodes.add(node);
		}
	}

	@Override
	public @NonNull String toString() {
		Comparator<@NonNull Node> nodeComparator = getNodeCostComparator();
		StringBuilder s = new StringBuilder();
		List<@NonNull Node> nodes = new ArrayList<>(node2cost.keySet());
		Collections.sort(nodes, nodeComparator);
		for (@NonNull Node node : nodes) {
			if (s.length() > 0) {
				s.append("\n");
			}
			s.append(node2cost.get(node));
			s.append(": ");
			s.append(node.getName());
			s.append(" : ");
			s.append(node2reachingEdge.get(node));
		}
		return s.toString();
	}
}