package org.maltparser.parser.algorithm.twoplanar3T;



import org.maltparser.core.exception.MaltChainedException;
import org.maltparser.core.syntaxgraph.DependencyStructure;
import org.maltparser.core.syntaxgraph.LabelSet;
import org.maltparser.core.syntaxgraph.node.DependencyNode;
import org.maltparser.parser.DependencyParserConfig;
import org.maltparser.parser.Oracle;
import org.maltparser.parser.ParserConfiguration;
import org.maltparser.parser.algorithm.twoplanar.TwoPlanar;
import org.maltparser.parser.algorithm.twoplanar.TwoPlanarConfig;
import org.maltparser.parser.history.GuideUserHistory;
import org.maltparser.parser.history.action.GuideUserAction;
import org.maltparser.core.symbol.SymbolTable;
import org.maltparser.core.symbol.SymbolTableHandler;
import org.maltparser.core.symbol.trie.Trie;
import org.maltparser.core.symbol.trie.TrieSymbolTable;

import java.util.IdentityHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;
import java.util.SortedSet;
import org.maltparser.core.syntaxgraph.edge.Edge;
import org.maltparser.core.syntaxgraph.node.TokenNode;
import java.util.Iterator;

public class TwoPlanar3TArcEagerOracle extends Oracle {

	public TwoPlanar3TArcEagerOracle(DependencyParserConfig manager, GuideUserHistory history) throws MaltChainedException {
		super(manager, history);
		setGuideName("2planar3t");
	}
	
	private static final int ANY_PLANE = 0;
	private static final int FIRST_PLANE = 1;
	private static final int SECOND_PLANE = 2;
	private static final int NO_PLANE = 3;
	private Map<Edge,Integer> linksToPlanes = new IdentityHashMap<Edge,Integer>();
	
	public GuideUserAction predict(DependencyStructure gold, ParserConfiguration config) throws MaltChainedException {
		TwoPlanar3TConfig planarConfig = (TwoPlanar3TConfig)config;
		DependencyStructure dg = planarConfig.getDependencyGraph();
		DependencyNode activeStackPeek = planarConfig.getActiveStack().peek();
		DependencyNode inactiveStackPeek = planarConfig.getInactiveStack().peek();
		int activeStackPeekIndex = activeStackPeek.getIndex();
		int inactiveStackPeekIndex = inactiveStackPeek.getIndex();
		int inputPeekIndex = planarConfig.getInput().peek().getIndex();
		
		if ( crossingsGraph == null ) initCrossingsGraph(gold);
		
	    if (checkIfNodesAreRelated(gold, activeStackPeekIndex , inputPeekIndex)
				&& !checkIfNodesAreRelated ( dg , activeStackPeekIndex , inputPeekIndex ) ) {
		   
	   
//		   if(stackPeekIndex==0){
//			   return updateActionContainers(Planar3TLabelStrat.SHIFT, null);
//		   }
	    	if ( planarConfig.getStackActivityState() == TwoPlanar3TConfig.FIRST_STACK )
			{
				propagatePlaneConstraint(gold.getTokenNode(inputPeekIndex).getHeadEdge(), FIRST_PLANE );
			}
			else
			{
				propagatePlaneConstraint(gold.getTokenNode(inputPeekIndex).getHeadEdge(), SECOND_PLANE );
			}
			
		    return updateActionContainers(TwoPlanar3T.ARC, getEdgeGraph( gold , activeStackPeekIndex ,inputPeekIndex ).getLabelSet());
	   
	    } else if (checkIfNodesAreRelated(gold, inactiveStackPeekIndex , inputPeekIndex)
				&& !checkIfNodesAreRelated ( dg , inactiveStackPeekIndex , inputPeekIndex ) ) {   
	    	
	    	return updateActionContainers(TwoPlanar3T.SWITCH, null);
	    
	    }else if ( areInputBufferRelated(gold,planarConfig.getActiveStack(),inputPeekIndex) )
			{
	    		return updateActionContainers(TwoPlanar3T.REDUCE, null);
		}else if ( areInputBufferRelated(gold,planarConfig.getInactiveStack(),inputPeekIndex) )
			{
				return updateActionContainers(TwoPlanar3T.SWITCH, null);
		
		}else 
			{
				return updateActionContainers(TwoPlanar3T.SHIFT, null);
			}
		
	  	
	}
	
//	private boolean checkIfArcExists ( DependencyStructure dg , int index1 , int index2 ) throws MaltChainedException
//	{
//		return dg.getTokenNode(index2).hasHead() && dg.getTokenNode(index2).getHead().getIndex() == index1;
//	}
	
	private boolean checkIfNodesAreRelated( DependencyStructure dg , int index1 , int index2 ) throws MaltChainedException
	{
		TokenNode tk=dg.getTokenNode(index1);
		Set<DependencyNode> heads=null;
		if(tk!=null){
		   heads=tk.getHeads();
		
		   for (DependencyNode head : heads) {
			if(head.getIndex()==index2)
			{
				return true;
			}
		   }
		}   
		
		tk=dg.getTokenNode(index2);
		if(tk!=null){
		   heads=tk.getHeads();
		   for (DependencyNode head : heads) {
			if(head.getIndex()==index1)
			{
				return true;
			}
		  }
		}   
		return false;
	}
	
	//If input is related in GOLD with some node of the Stack under the TOP
	private boolean areInputBufferRelated( DependencyStructure dg , Stack<DependencyNode> stack , int indexBuffer ) throws MaltChainedException
	{
		Iterator<DependencyNode> it=stack.iterator();
		while(it.hasNext())
		{
			DependencyNode nodo=it.next();
			if(checkIfNodesAreRelated(dg,nodo.getIndex(),indexBuffer) && stack.peek().getIndex()!=nodo.getIndex())
			{
				return true;
			}
		}
		return false;
		
	}
	
	private Edge getEdgeGraph( DependencyStructure dg , int index1 , int index2 ) throws MaltChainedException
	{
	  SortedSet<Edge> arcos=dg.getEdges();
	  Iterator<Edge> it=arcos.iterator();
	  while(it.hasNext())
	  {
		Edge arco=it.next();
		if(arco.getSource().getIndex()==index1 && arco.getTarget().getIndex()==index2)
		{
			return arco;
		}
		if(arco.getSource().getIndex()==index2 && arco.getTarget().getIndex()==index1)
		{
			return arco;
		}
	  }
	  return null;
	}
	
	public void finalizeSentence(DependencyStructure dependencyGraph) throws MaltChainedException {
		crossingsGraph = null;
		linksToPlanes.clear();
	}
	
	public void terminate() throws MaltChainedException {}
	
	private static boolean cross ( Edge e1 , Edge e2 )
	{
		int xSource = e1.getSource().getIndex();
		int xTarget = e1.getTarget().getIndex();
		int ySource = e2.getSource().getIndex();
		int yTarget = e2.getTarget().getIndex();
		int xMin = Math.min(xSource,xTarget);
		int xMax = Math.max(xSource,xTarget);
		int yMin = Math.min(ySource,yTarget);
		int yMax = Math.max(ySource,yTarget);
		//System.out.println(xMin+":"+xMax+":"+yMin+":"+yMax);
		return ( xMin < yMin && yMin < xMax && xMax < yMax ) || ( yMin < xMin && xMin < yMax && yMax < xMax );
	}
	
	private Map<Edge,List<Edge>> crossingsGraph = null;
	
	private void initCrossingsGraph ( DependencyStructure dg )
	{
		crossingsGraph = new IdentityHashMap<Edge,List<Edge>>();
		SortedSet<Edge> edges = dg.getEdges();
		//System.out.println(edges.size());
		//System.out.println(dg.nEdges());
		for (Iterator<Edge> iterator1 = edges.iterator(); iterator1.hasNext();) {
			Edge edge1 = iterator1.next();
			for (Iterator<Edge> iterator2 = edges.iterator(); iterator2.hasNext();) {
				Edge edge2 = iterator2.next();
				if ( edge1.getSource().getIndex() < edge2.getSource().getIndex() && cross(edge1,edge2) )
				{
					//System.out.println("Crossing!");
					List<Edge> crossingEdge1 = crossingsGraph.get(edge1);
					if ( crossingEdge1 == null ) { crossingEdge1 = new LinkedList<Edge>(); crossingsGraph.put(edge1, crossingEdge1); }
					crossingEdge1.add(edge2);
					List<Edge> crossingEdge2 = crossingsGraph.get(edge2);
					if ( crossingEdge2 == null ) { crossingEdge2 = new LinkedList<Edge>(); crossingsGraph.put(edge2 , crossingEdge2); }
					crossingEdge2.add(edge1);
				}
			}
		}
	}
	
	private List<Edge> getCrossingEdges ( Edge e )
	{
		return crossingsGraph.get(e);
	}
	
	private void setPlaneConstraint ( Edge e , int requiredPlane )
	{
		linksToPlanes.put(e, requiredPlane);
	}
	
	private int getPlaneConstraint ( Edge e )
	{
		Integer constr = linksToPlanes.get(e);
		if ( constr == null )
		{
			setPlaneConstraint(e,ANY_PLANE);
			return ANY_PLANE;
		}
		else return constr;
	}
	
	private void propagatePlaneConstraint ( Edge e , int requiredPlane )
	{
		setPlaneConstraint(e,requiredPlane);
		if ( requiredPlane == FIRST_PLANE || requiredPlane == SECOND_PLANE )
		{
			List<Edge> crossingEdges = getCrossingEdges(e);
			if ( crossingEdges != null )
			{
				for (Iterator<Edge> iterator = crossingEdges.iterator(); iterator.hasNext();) 
				{
					Edge crossingEdge = iterator.next();
					assert ( requiredPlane == FIRST_PLANE || requiredPlane == SECOND_PLANE );
					int crossingEdgeConstraint = getPlaneConstraint(crossingEdge);
					if ( crossingEdgeConstraint == ANY_PLANE ) 
					{ 
						if ( requiredPlane == FIRST_PLANE )
							propagatePlaneConstraint(crossingEdge,SECOND_PLANE);
						else if ( requiredPlane == SECOND_PLANE )
							propagatePlaneConstraint(crossingEdge,FIRST_PLANE);
					}
					else if ( crossingEdgeConstraint == NO_PLANE ) ;		
					else if ( crossingEdgeConstraint == FIRST_PLANE )
					{
						if ( requiredPlane == FIRST_PLANE )
							propagatePlaneConstraint(crossingEdge,NO_PLANE);
					}
					else if ( crossingEdgeConstraint == SECOND_PLANE )
					{
						if ( requiredPlane == SECOND_PLANE )
							propagatePlaneConstraint(crossingEdge,NO_PLANE);
					}
				}
			}
		}
	}

	/**
	 * Decides in which plane link e should be created.
	 */
//	private int getLinkDecision ( Edge e , TwoPlanar3TConfig config )
//	{
//		int constraint = getPlaneConstraint ( e );
//		if ( constraint == ANY_PLANE )
//		{
//			//choose active plane
//			if ( config.getStackActivityState() == TwoPlanarConfig.FIRST_STACK )
//				return FIRST_PLANE;
//			else
//				return SECOND_PLANE;
//		}
//		else return constraint;
//	}
//	
//	
//	/**
//	 * Gets the shortest pending link between (to or from) the input node and a node to the left of the top of the active stack,
//	 * such that the link can be established on the active plane.
//	 * @param config
//	 * @return
//	 */
//	private Edge getFirstPendingLinkOnActivePlane ( TwoPlanar3TConfig config , DependencyStructure gold ) throws MaltChainedException
//	{
//		return getFirstPendingLinkOnPlane ( config , gold , config.getStackActivityState() == TwoPlanarConfig.FIRST_STACK ? FIRST_PLANE : SECOND_PLANE , 
//				config.getActiveStack().peek().getIndex() );
//	}
//	
//	/**
//	 * Gets the shortest pending link between (to or from) the input node and a node to the left of the top of the inactive stack, 
//	 * such that the link can be established on the inactive plane.
//	 * @param config
//	 * @return
//	 */
//	private Edge getFirstPendingLinkOnInactivePlane ( TwoPlanar3TConfig config , DependencyStructure gold ) throws MaltChainedException
//	{
//		return getFirstPendingLinkOnPlane ( config , gold , config.getStackActivityState() == TwoPlanarConfig.FIRST_STACK ? SECOND_PLANE : FIRST_PLANE ,
//				config.getInactiveStack().peek().getIndex() );
//	}
//	
//	private Edge getFirstPendingLinkOnAnyPlane ( TwoPlanar3TConfig config , DependencyStructure gold ) throws MaltChainedException
//	{
//		Edge e1 = getFirstPendingLinkOnActivePlane ( config , gold );
//		Edge e2 = getFirstPendingLinkOnInactivePlane ( config , gold );
//		int left1 = Math.min(e1.getSource().getIndex(), e1.getTarget().getIndex());
//		int left2 = Math.min(e2.getSource().getIndex(), e2.getTarget().getIndex());
//		if ( left1 > left2 ) return e1;
//		else return e2;
//	}
//	
//	/**
//	 * Gets the shortest pending link between (to or from) the input node and a node to the left of rightmostLimit, such that the link
//	 * can be established on the given plane.
//	 * @param config
//	 * @param plane
//	 * @param rightmostLimit
//	 * @return
//	 */
//	private Edge getFirstPendingLinkOnPlane ( TwoPlanar3TConfig config , DependencyStructure gold ,  int plane , int rightmostLimit )
//		throws MaltChainedException
//	{
//		TwoPlanar3TConfig planarConfig = (TwoPlanar3TConfig)config;
//		//DependencyStructure dg = planarConfig.getDependencyGraph(); -> no need, if rightmostLimit is well chosen, due to algorithm invariants
//		int inputPeekIndex = planarConfig.getInput().peek().getIndex();
//		
//		Edge current = null;
//		int maxIndex;
//		if ( planarConfig.getRootHandling() == TwoPlanar3TConfig.NORMAL )
//			maxIndex = -1; //count links from dummy root
//		else
//			maxIndex = 0; //do not count links from dummy root
//		
//		if ( gold.getTokenNode(inputPeekIndex).hasLeftDependent() && 
//				gold.getTokenNode(inputPeekIndex).getLeftmostDependent().getIndex() < rightmostLimit)
//		{
//			SortedSet<DependencyNode> dependents = gold.getTokenNode(inputPeekIndex).getLeftDependents();
//			for (Iterator<DependencyNode> iterator = dependents.iterator(); iterator.hasNext();) {
//				DependencyNode dependent = (DependencyNode) iterator.next();
//				if ( dependent.getIndex() > maxIndex && dependent.getIndex() < rightmostLimit 
//						&& getLinkDecision(dependent.getHeadEdge(),config) == plane )
//				{
//					maxIndex = dependent.getIndex();
//					current = dependent.getHeadEdge();
//				}
//			}
//		}
//		
//		//at this point, current is the first left-pointing link, but we have to check right-pointing link as well
//		
//		//System.out.println("in" + inputPeekIndex + " rl" + rightmostLimit);
//		if ( gold.getTokenNode(inputPeekIndex).getHead().getIndex() < rightmostLimit )
//		{
//			//System.out.println(":");
//			if ( gold.getTokenNode(inputPeekIndex).getHead().getIndex() > maxIndex && 
//					getLinkDecision(gold.getTokenNode(inputPeekIndex).getHeadEdge(),config) == plane )
//			{
//				//System.out.println("::");
//				current = gold.getTokenNode(inputPeekIndex).getHeadEdge();
//			}
//		}
//		
//		return current;
//		
//		
//	}
	

}

