package algorithms;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import models.*;
import models.algebra.*;
import models.dataConstraintModel.*;
import models.dataFlowModel.*;

/**
 * Algorithms to analyze data transfer model.
 * 
 * @author Nitta
 *
 */
public class DataTransferModelAnalyzer {
	/**
	 * Create data flow graph annotated with node attributes that indicate whether each resource state needs to be stored.
	 * @param model a data transfer model
	 * @return annotated data flow graph
	 */
	static public DataFlowGraph createDataFlowGraphWithStateStoringAttribute(DataTransferModel model) {
		DataFlowGraph graph = model.getDataFlowGraph();
		Collection<Channel> channels = new HashSet<>(model.getInputChannels());
		channels.addAll(model.getChannels());
		for (Channel channel: channels) {
			for (ChannelMember member: ((DataTransferChannel) channel).getOutputChannelMembers()) {
				boolean toBeStored = !member.getStateTransition().isRightUnary();		// The state does not need to be stored if the state transition function is right unary.
				for (Node node : graph.getResourceNodes()) {
					if (((ResourceNode) node).getInSideResources().contains(member.getResource())) {
						setStoreAttribute((ResourceNode) node, toBeStored);
					}
				}
			}
		}
		for (Node node: graph.getResourceNodes()) {
			HashSet<Channel> inChannels = new HashSet<>();
			for(Edge inEdge: ((ResourceNode) node).getInEdges()) {
				if (inEdge instanceof DataFlowEdge) {
					DataFlowEdge dfEdge = (DataFlowEdge) inEdge;
					if (dfEdge.isChannelToResource()) {
						inChannels.add(((ChannelNode) dfEdge.getSource()).getChannel());
					}
				}
			}
			if ((inChannels.size() > 1)) {
				// If the resource has multiple input channels, then the state of the resource needs to be stored.
				setStoreAttribute((ResourceNode) node, true);
			} else if (((ResourceNode) node).getAttribute() == null) {
				setStoreAttribute((ResourceNode) node, false);
			}
		}
		return graph;
	}

	static private void setStoreAttribute(ResourceNode node, boolean toBeStored) {
		NodeAttribute attr = node.getAttribute();
		StoreAttribute store;
		if (attr != null && attr instanceof NodeAttribute) {
			store = (StoreAttribute) attr;
			store.setNeeded(store.isNeeded() || toBeStored);
		} else {
			store = new StoreAttribute();
			store.setNeeded(toBeStored);
			node.setAttribute(store);
		}
	}

	/**
	 * Annotate data flow graph with edge attributes that indicate selectable data transfer methods.
	 * @param graph a data flow graph
	 * @return annotated data flow graph
	 */
	static public DataFlowGraph annotateWithSelectableDataTransferAttiribute(DataFlowGraph graph) {
		HashSet<Node> unvisitedNodes = new HashSet<>(graph.getResourceNodes());
		// Turn push only
		for (Node resNode: graph.getResourceNodes()) {
			if (unvisitedNodes.contains(resNode) && ((StoreAttribute) ((ResourceNode) resNode).getAttribute()).isNeeded()) {
				unvisitedNodes.remove(resNode);
				trackEdgesBackwardForPush(resNode, unvisitedNodes);
			}
		}
		// Turn push/pull only with respect to channel hierarchies.
		while (!unvisitedNodes.isEmpty()) {
			Node resNode = unvisitedNodes.iterator().next();
			unvisitedNodes.remove(resNode);
			for (Edge chToRes : ((ResourceNode) resNode).getInEdges()) {
				ChannelNode chNode = (ChannelNode) chToRes.getSource();
				// Should take into account the channel hierarchy.
				boolean pullContained = false;
				Set<ChannelNode> ancestorChannels = chNode.getAncestors();
				for (ChannelNode ancestorCh: ancestorChannels) {
					for (Edge resToCh: ancestorCh.getInEdges()) {
						ResourceNode srcResNode = (ResourceNode) resToCh.getSource();
						DataTransferChannel ch = (DataTransferChannel) ancestorCh.getChannel();
						for (ChannelMember cm: ch.getInputChannelMembers()) {
							if (cm.isOutside()) {
								PushPullAttribute ppat = new PushPullAttribute();
								ppat.addOption(PushPullValue.PULL);		// To refer to outside resource.
								((DataFlowEdge) resToCh).setAttribute(ppat);
								pullContained = true;
							} else {
								PushPullAttribute ppat = new PushPullAttribute();
								ppat.addOption(PushPullValue.PUSH);		// For broadcasting transfer.
								((DataFlowEdge) resToCh).setAttribute(ppat);
								unvisitedNodes.remove(srcResNode);
								trackEdgesBackwardForPush(srcResNode, unvisitedNodes);
							}
						}
					}
				}
				Set<ChannelNode> descendantChannels = chNode.getDescendants();
				for (ChannelNode descendantCh: descendantChannels) {
					for (Edge resToCh: descendantCh.getInEdges()) {
						PushPullAttribute ppat = new PushPullAttribute();
						ppat.addOption(PushPullValue.PULL);		// For collecting transfer.
						((DataFlowEdge) resToCh).setAttribute(ppat);
						pullContained = true;
					}
				}
				if (pullContained) {
					trackEdgesForwardForPull(resNode, unvisitedNodes);
				}
			}
		}
		// set push/pull attributes to the remaining edges
		for (Edge e : graph.getEdges()) {
			if (!((DataFlowEdge) e).isChannelToResource() && ((DataFlowEdge) e).getAttribute() == null) {
				PushPullAttribute ppat = new PushPullAttribute();
				ppat.addOption(PushPullValue.PUSHorPULL);
				ppat.addOption(PushPullValue.PUSH);
				ppat.addOption(PushPullValue.PULL);
				((DataFlowEdge) e).setAttribute(ppat);
			}
		}
		return graph;
	}

	static private void trackEdgesBackwardForPush(Node resNode, HashSet<Node> unvisitedNodes) {
		// recursively turn push only backward in data-flow.
		for (Edge chToRes : ((ResourceNode) resNode).getInEdges()) {
			ChannelNode chNode = (ChannelNode) chToRes.getSource();
			// Should take into account the channel hierarchy.
			Set<ChannelNode> ancestorChannels = chNode.getAncestors();
			Set<ChannelNode> descendantChannels = chNode.getDescendants();
			Set<Edge> inEdges = new HashSet<>();
			inEdges.addAll(chNode.getInEdges());
			for (ChannelNode ancestorCh: ancestorChannels) {
				inEdges.addAll(ancestorCh.getInEdges());
			}
			for (ChannelNode descendantCh: descendantChannels) {
				inEdges.addAll(descendantCh.getInEdges());
			}
			for (Edge resToCh: inEdges) {
				PushPullAttribute ppat = new PushPullAttribute();
				ppat.addOption(PushPullValue.PUSH);
				((DataFlowEdge) resToCh).setAttribute(ppat);
				Node resNode2 = resToCh.getSource();
				if (unvisitedNodes.contains(resNode2)) {
					unvisitedNodes.remove(resNode2);
					trackEdgesBackwardForPush(resNode2, unvisitedNodes);
				}
			}
		}
	}

	private static void trackEdgesForwardForPull(Node resNode, HashSet<Node> unvisitedNodes) {
		// recursively turn pull only forward in data-flow.
		for (Edge resToCh : ((ResourceNode) resNode).getOutEdges()) {
			PushPullAttribute ppat = new PushPullAttribute();
			ppat.addOption(PushPullValue.PULL);
			((DataFlowEdge) resToCh).setAttribute(ppat);
			ChannelNode chNode = (ChannelNode) resToCh.getDestination();
			// Should take into account the channel hierarchy.
			Set<ChannelNode> ancestorChannels = chNode.getAncestors();
			Set<ChannelNode> descendantChannels = chNode.getDescendants();
			Set<Edge> outEdges = new HashSet<>();
			outEdges.addAll(chNode.getOutEdges());
			for (ChannelNode ancestorCh: ancestorChannels) {
				outEdges.addAll(ancestorCh.getOutEdges());
			}
			for (ChannelNode descendantCh: descendantChannels) {
				outEdges.addAll(descendantCh.getOutEdges());
			}
			for (Edge chToRes: outEdges) {
				Node resNode2 = chToRes.getDestination();
				if (unvisitedNodes.contains(resNode2)) {
					unvisitedNodes.remove(resNode2);
					trackEdgesForwardForPull(resNode2, unvisitedNodes);
				}
			}
		}
	}
}