package Sequenic.T2ext.Selection;

import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.Map.Entry;

import Sequenic.Graph.Vertex;
import Sequenic.T2ext.Instrumenter.Node;
import Sequenic.T2ext.Selection.PathSelector.Factory;

public class RothermelHarrold
{
	
	/** 
	 * Returns a set of dangerous edges in the original method CFG.
	 * All tests traversing these edges must be selected.
	 * 
	 * If the startNodes of the CFG are not lexically equivalent it returns null 
	 * and all tests that cover the method need to be selected.
	 * 
	 */
	public PathSelector getDangerousEdges(Node origStart, Node modStart)
	{				
		if(!origStart.lexEquivalent(modStart)) 
			return PathSelector.ALWAYS;
						
		visitRH(origStart,modStart, true);
		
		markings.clear();
		psFactory.relabelStartNodeIfNeeded(origStart.getId(), modStart.getId());
		return psFactory.resetAndReturn();
	}	
	
	
	/**
	 * This is the Rothermel-Harrold algorithm, it performs a DFS walk of the CFG.
	 * 
	 * NOTE: Pre-condition to calling visitRH:
	 * 1) For every outgoing edge in orig, there is a similarly labeled outgoing edge in mod
	 * 
	 * This pre-condition can be satisfied by ensuring that:
	 * 1) compare is only invoked if orig is lexically equivalent to mod, AND
	 * 2) Two lexically equivalent nodes have the same set of outgoing labels.
	 */
	private void visitRH(Node orig, Node mod, boolean startNodes) 
	{
		markVisited(orig,mod);
		
		for(Entry<String, Vertex> kv : orig.childEdges().entrySet()) 
		{
			Node origChild = (Node) kv.getValue();
			Node modChild  = (Node) mod.getChild(kv.getKey());
			
			if(!isVisited(origChild, modChild)) 
			{
				//If a pair of nodes are not yet visited then they are either:				
				if(origChild.lexEquivalent(modChild)) {
					
					// (1) Lexically equivalent, just not yet visited
					// So we visit them.
					visitRH(origChild,modChild, false);
					
					//Also relabel if children don't have same id
					psFactory.relabelIfNeeded(orig.getId(), origChild.getId(), modChild.getId());
	
				} else {
					
					// (2) Lexically different, i.e. we have discovered a modified entity in the CFG.
					// The paths that follow are traversal will be modification-traversing.
					// So we mark the corresponding edge in the original CFG as dangerous.
					psFactory.markDangerous(orig.getId(), origChild.getId());
				}
			}
		}
	}
			
	/** This marks the node _Mark as visited by the node _Visited
	 */	
	private void markVisited(Node _Mark, Node _Visited) 
	{
		/*			 
		 * Multiply visited nodes are those marked as visited by multiple nodes.
		 * These are rare: _Mark will most likely only ever be marked as visited 
		 * by a single node (the one currently referenced as _Visited).
		 * 
		 * In the common case there will be no previous marking.
		 * m will be null and we will use the cheap singletonMap.
		 */
		Set<Node> m = markings.put(_Mark, Collections.singleton(_Visited));
		
		//The uncommon case
		if(m!=null) 
		{
			if(m.size()==1)  //m is still an immutable singleton, so make it mutable.
				m = new HashSet<Node>(m);
			m.add(_Visited);
			markings.put(_Mark, m);
		}
	}
	
	/** Returns true if node _Mark is marked as visited by _Visited
	 */
	private boolean isVisited(Node _Mark, Node _Visited) 
	{
		Set<Node> m = markings.get(_Mark);
		return m!=null
			&& m.contains(_Visited);
	}
		
	private final Map<Node,Set<Node>> markings = new HashMap<Node, Set<Node>>();			

	private final PathSelector.Factory psFactory = new Factory();
}