package Sequenic.T2ext.Selection;

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

import Sequenic.Graph.Vertex;
import Sequenic.T2ext.Instrumenter.CFG;
import Sequenic.T2ext.Instrumenter.Node;



public class InterclassGraph implements PathSelector{
	
	public InterclassGraph(Node origStartNode, Node modStartNode) {
		childrenMap = new HashMap<HashEqualsEdge, Set<HashEqualsEdge>>();
		parentsMap = new HashMap<HashEqualsEdge, Set<HashEqualsEdge>>();
		accept = new HashSet<HashEqualsEdge>();
		reject = new HashSet<HashEqualsEdge>();
		if(!parentsMap.containsKey(startNode = visitNode(origStartNode, modStartNode))) 
			parentsMap.put(startNode, __EMPTY);
	}
	
	private final Map<HashEqualsEdge,Set<HashEqualsEdge>> childrenMap;
	private final Map<HashEqualsEdge,Set<HashEqualsEdge>> parentsMap;
	
	private final Set<HashEqualsEdge> accept;
	private final Set<HashEqualsEdge> reject;
	
	private final HashEqualsEdge startNode;
			
	private static final Set<HashEqualsEdge> __EMPTY = Collections.emptySet();
	
	private HashEqualsEdge visitNode(Node origNode, Node modNode) 
	{
		HashEqualsEdge thisNode = HashEqualsEdge.weakCache.make(origNode.getId(), modNode.getId());
		
		if(childrenMap.containsKey(thisNode))
			return thisNode;//Do Nothing, already visited	
		
		
		if(!origNode.lexEquivalent(modNode))
		{
			reject.add(thisNode);
			childrenMap.put(thisNode, __EMPTY);//Reject
			return thisNode;
		}
		else if(origNode.children().isEmpty())
		{	//implied: origNode.lexEquivalent(modNode))
			accept.add(thisNode);
			childrenMap.put(thisNode, __EMPTY);//Accept
			return thisNode;
		}
		else 
		{
			Set<HashEqualsEdge> childrenSet = new HashSet<HashEqualsEdge>();
			childrenMap.put(thisNode, childrenSet);
			
			for(Entry<String, Vertex> kv : origNode.childEdges().entrySet()) 
			{
				HashEqualsEdge child = visitNode(   (Node) kv.getValue(), 
													(Node) modNode.getChild(kv.getKey()));
				childrenSet.add(child);
				Set<HashEqualsEdge> parentsSet = parentsMap.get(child);
				if(parentsSet==null)
					parentsMap.put(child, parentsSet = new HashSet<HashEqualsEdge>());
				parentsSet.add(thisNode);
			}
			return thisNode;
		}		
	}
	
	//Return the dangerous edges according to Rothermel Harrold
	Set<HashEqualsEdge> rhDangerousEdges() {
		Set<HashEqualsEdge> dangerousEdges = new HashSet<HashEqualsEdge>();
		
		for(HashEqualsEdge rejectNode : reject)
		{
			int childId = rejectNode.fst();
			for(HashEqualsEdge parent : parentsMap.get(rejectNode))
				dangerousEdges.add(
						HashEqualsEdge.weakCache.make(parent.fst(), childId)
				);
		}

		return dangerousEdges;
	}
	
	//Returns a selector that implements Ball's partial reachability algorithm.
	//Resets the PathSelector Factory after usage.
	PathSelector ballPartialDangerousEdges(PathSelector.Factory psFactory) 
	{
		Set<HashEqualsEdge> vAccept = new HashSet<HashEqualsEdge>();
		for(HashEqualsEdge terminalAcceptNode : accept)
			fillAncestors(terminalAcceptNode, vAccept);
		
		
		//vAccept now contains all terminal accept nodes and their ancestors: it is Vaccept as Ball defines it.
		
		if(!vAccept.contains(startNode))
			//Start node does not lead to accept: all paths are modification-traversing.
			return PathSelector.ALWAYS; 

		psFactory.relabelStartNodeIfNeeded(startNode.fst(), startNode.snd()); 

		//Dangerous edge: one that goes from a node in Vaccept to one not in Vaccept
		for(HashEqualsEdge acceptNode : vAccept)
		{
			int acceptNodeFst = acceptNode.fst();
			for(HashEqualsEdge child : childrenMap.get(acceptNode))
				if(!vAccept.contains(child))
					psFactory.markDangerous(acceptNodeFst, child.fst());//dangerous edge
				else 
					//Relabelling is only necessary for nodes in Vaccept, 
					//other nodes are only reachable through a dangerous edge: 
					//their paths will never be relabeled; they will be selected as modification-traversing.
					psFactory.relabelIfNeeded(acceptNodeFst, child.fst(), child.snd());	
		}
				
		return psFactory.resetAndReturn();
	}
	
	//Add all ancestors of startNode to result
	private void fillAncestors(HashEqualsEdge startNode, Set<HashEqualsEdge> result)
	{
		if(result.add(startNode))
		{
			//If node was not already in result, traverse its parents.
    		Iterator<HashEqualsEdge> parents = parentsMap.get(startNode).iterator();
    		while(parents.hasNext())
    			fillAncestors(parents.next(), result);
		}
	}

	public boolean select(int[] path)
	{
		return modTrav(startNode, path, 1);
	}
	
	private boolean modTrav(HashEqualsEdge key, int[] path, int index)
	{
		if(reject.contains(key))
			return true;
		if(index>=path.length)
			return false;
		int id = path[index++];
		for(HashEqualsEdge child : childrenMap.get(key))
			if(id==child.fst() && modTrav(child,path,index))
				return true;
		return false;//no descendants were in reject.
	}
	
	public int[] synthesize(int[] path)
	{
		if(path.length==0)
			return path;
		
		HashEqualsEdge parent = startNode;
		int index = 0;
		int[] newPath = null;
		while(true)
		{			
			//mod-trav path
			if(reject.contains(parent))
				return null;
			
			//relabel if needed
			if(parent.fst()!=parent.snd())
			{
				if(newPath==null) {
					newPath = new int[path.length];
					System.arraycopy(path, 0, newPath, 0, path.length);
				}
				newPath[index] = parent.snd();
			}
			
			//Proceed to next element on path
			index++;
			
			if(index==path.length)
				//End of path reached.
				return newPath==null? path : newPath;
			
			Iterator<HashEqualsEdge> children = childrenMap.get(parent).iterator();
		
			if(!children.hasNext())
				//If parent is reject we would have returned null earlier.
				//If parent is accept, path is invalid because it continues after terminal node.
				throw new Error("Invalid path, it continues after terminal node.");
			
			int id = path[index];
			while(children.hasNext())
			{
				parent = children.next();
				if(parent.fst()==id)
				{
					while(children.hasNext())
						if(children.next().fst()==id)
							//Two different children are both possible successors on the path
							//Cannot relabel because of ambiguity
							return null;
					
					//We have found our unique successor and the iterator is emptied.
				}			
			}
			
			if(parent.fst()!=id) 
			{
				System.err.println(childrenMap);
				//The path is invalid, there was no successor
				throw new Error("Invalid path, contains non-existant edge: "+Arrays.toString(path)+
						" index "+index+ " selected node: "+parent + "parents: "+parentsMap.get(parent));
			}

		}
	}
	
	public boolean hasMultiplyVisitedNode() 
	{
		boolean ret = false;
		Map<Integer, HashEqualsEdge> temp = new HashMap<Integer, HashEqualsEdge>(childrenMap.size());
		for(HashEqualsEdge node : childrenMap.keySet()) {
			HashEqualsEdge old = temp.put(node.fst(), node);
			if(old!=null) 
			{
				System.out.println("Multiply-visited Node: "+old.toString()+" "+node.toString());
				ret = true;
			}
		}
		return ret;
	}
	
	public static boolean hasMultiplyVisitedNode(Iterable<CFG> old_methods, Iterable<CFG> new_methods) 
	{
		HashMap<String,CFG> newMethods = new HashMap<String,CFG>();
		boolean ret = false;
		
		for(CFG newCFG : new_methods)
			newMethods.put(newCFG.getMethodName(), newCFG);
		
		for(CFG oldCFG : old_methods)
		{
			if(newMethods.containsKey(oldCFG.getMethodName())) 
			{
				InterclassGraph icg = new InterclassGraph(oldCFG.getStartNode(), 
						newMethods.get(oldCFG.getMethodName()).getStartNode());
				ret |= icg.hasMultiplyVisitedNode();
			}
		}
				
		return ret;
	}

	
}