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.Node;



public class PrimePathSelector implements PathSelector{
	
	public PrimePathSelector(Node origStartNode, Node modStartNode) {
		childrenMap = new HashMap<HashEqualsEdge, Set<HashEqualsEdge>>();
		accept = new HashSet<HashEqualsEdge>();
		reject = new HashSet<HashEqualsEdge>();
		startNode = visitNode(origStartNode, modStartNode);
	}
	
	private final Map<HashEqualsEdge,Set<HashEqualsEdge>> childrenMap;
	
	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);
			}
			return thisNode;
		}		
	}
	

	
	
	//Add all ancestors of startNode to result
	private void fillDescendents(HashEqualsEdge startNode, Set<HashEqualsEdge> result)
	{
		if(result.add(startNode))
		{
			//If node was not already in result, traverse its parents.
    		Iterator<HashEqualsEdge> children = childrenMap.get(startNode).iterator();
    		while(children.hasNext())
    			fillDescendents(children.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);
			}

		}
	}
	
	private Map<Integer,Set<HashEqualsEdge>> origToIG;
	
	private Map<HashEqualsEdge,Set<HashEqualsEdge>> cycles = Collections.emptyMap();
	
	private void hasMultiplyVisitedNode()
	{
		boolean hasMultiplyVisitedNodes = false;
		Map<Integer, Set<HashEqualsEdge>> temp = new HashMap<Integer, Set<HashEqualsEdge>>(childrenMap.size());
		for(HashEqualsEdge node : childrenMap.keySet()) {
			Set<HashEqualsEdge> old = temp.put(node.fst(), Collections.singleton(node));
			if(old!=null) 
			{
				old = new HashSet<HashEqualsEdge>(old);
				old.add(node);
				temp.put(node.fst(), old);
				System.out.println("Multiply-visited Node: "+old.toString()+" "+node.toString());
				hasMultiplyVisitedNodes = true;
			}
		}
		origToIG = temp;
		
		if(!hasMultiplyVisitedNodes)
			return;
		
		cycles = new HashMap<HashEqualsEdge, Set<HashEqualsEdge>>();
		for(Set<HashEqualsEdge> s : temp.values())
		{
			if(s.size()>1)
			{
				for(HashEqualsEdge e : s)
				{
					HashSet<HashEqualsEdge> descendents = new HashSet<HashEqualsEdge>();
					fillDescendents(e, descendents);
					descendents.retainAll(s);
					descendents.remove(e);
					if(!descendents.isEmpty())
						cycles.put(e, descendents);
				}
			}
		}
	}
	
}