package org.maltparser.parser;

import java.util.Set;
import java.util.SortedSet;
import java.util.Iterator;
import java.util.Stack;
import java.util.TreeSet;
import java.util.ArrayList;
import java.util.HashSet;


import org.maltparser.core.exception.MaltChainedException;
import org.maltparser.core.syntaxgraph.DependencyStructure;
import org.maltparser.core.syntaxgraph.edge.Edge;
import org.maltparser.core.syntaxgraph.node.DependencyNode;
import org.maltparser.core.syntaxgraph.node.Node;
import org.maltparser.core.syntaxgraph.node.TokenNode;
import org.maltparser.core.syntaxgraph.edge.GraphEdge;
import org.maltparser.core.syntaxgraph.DependencyGraph;


import org.maltparser.parser.algorithm.twoplanar3T.TwoPlanar3TConfig;
import org.maltparser.parser.algorithm.ucovington.UcovingtonConfig;
import org.maltparser.parser.algorithm.planar3TLabelStrat.Planar3TLabelStratConfig;
import org.maltparser.parser.guide.ClassifierGuide;
import org.maltparser.parser.guide.SingleGuide;
import org.maltparser.parser.history.GuideHistory;
import org.maltparser.parser.history.action.GuideDecision;
import org.maltparser.parser.history.action.GuideUserAction;
import org.maltparser.parser.history.action.SimpleDecisionAction;
import org.maltparser.parser.history.container.ActionContainer;

import org.maltparser.parser.history.GuideUserHistory;
import org.maltparser.parser.history.History;
import org.maltparser.parser.history.container.TableContainer;
import org.maltparser.parser.history.action.ComplexDecisionAction;

public class DeterministicParser extends Parser {
	private int parseCount;
	
	public DeterministicParser(DependencyParserConfig manager) throws MaltChainedException {
		super(manager);
		setManager(manager);
		initParserState(1);
		((SingleMalt)manager).addRegistry(org.maltparser.parser.Algorithm.class, this);
		setGuide(new SingleGuide(manager, (GuideHistory)parserState.getHistory(), ClassifierGuide.GuideMode.CLASSIFY));
	}
	
	public DependencyStructure parse(DependencyStructure parseDependencyGraph) throws MaltChainedException {
	 
		//Nuevos flags
		String opcion="label";
		if	(parserState.getTransitionSystem().getName().compareTo("two-planar 3t arc-eager")==0){
			opcion=((TwoPlanar3TConfig)parserState.getConfiguration()).getMode();
		}
		if	(parserState.getTransitionSystem().getName().compareTo("ucovnonproj")==0){
			opcion=((UcovingtonConfig)parserState.getConfiguration()).getMode();
		}
	
		String opcion2="old"; 
		if	(parserState.getTransitionSystem().getName().compareTo("two-planar 3t arc-eager")==0){
			opcion2=((TwoPlanar3TConfig)parserState.getConfiguration()).getHeuristic();
		}
		if	(parserState.getTransitionSystem().getName().compareTo("planar 3t label strategy arc-eager")==0){
			opcion2=((Planar3TLabelStratConfig)parserState.getConfiguration()).getHeuristic();
		}
		if	(parserState.getTransitionSystem().getName().compareTo("ucovnonproj")==0){
			opcion2=((UcovingtonConfig)parserState.getConfiguration()).getHeuristic();
		}
		//=============================================================================
		
		parserState.clear();
		parserState.initialize(parseDependencyGraph);
	    if(parserState.getTransitionSystem().getName().compareTo("planar 3t arc-eager")==0 
	        	|| parserState.getTransitionSystem().getName().compareTo("planar 3t label strategy arc-eager")==0
	        	|| parserState.getTransitionSystem().getName().compareTo("two-planar 3t arc-eager")==0
	        	|| parserState.getTransitionSystem().getName().compareTo("ucovnonproj")==0){
				
				((DependencyGraph)parseDependencyGraph).setSingleHeadedConstraint(false);
			}
	    
		currentParserConfiguration = parserState.getConfiguration();
		parseCount++;
		if (diagnostics == true) {
			writeToDiaFile(parseCount + "");
		}
		
		while (!parserState.isTerminalState()) {
			
			GuideUserAction action = parserState.getTransitionSystem().getDeterministicAction(parserState.getHistory(), currentParserConfiguration);
			
			if (action == null) {
				action = predict();
			} else if (diagnostics == true) {
				writeToDiaFile(" *");
			}
			if (diagnostics == true) {
				writeToDiaFile(" " + parserState.getTransitionSystem().getActionString(action));
			}
			
			parserState.apply(action);
			
		} 
		 if(parserState.getTransitionSystem().getName().compareTo("planar 3t arc-eager")==0 
				 || parserState.getTransitionSystem().getName().compareTo("planar 3t label strategy arc-eager")==0 
					|| parserState.getTransitionSystem().getName().compareTo("two-planar 3t arc-eager")==0
					|| parserState.getTransitionSystem().getName().compareTo("ucovnonproj")==0){
				copyEdgesForPlanar3T(currentParserConfiguration.getDependencyGraph(), parseDependencyGraph);
				copyDynamicInput(currentParserConfiguration.getDependencyGraph(), parseDependencyGraph);
			}else{
				copyEdges(currentParserConfiguration.getDependencyGraph(), parseDependencyGraph);
				copyDynamicInput(currentParserConfiguration.getDependencyGraph(), parseDependencyGraph);
			}

	
		 
//--------------------------------------------------------------------------------------------------------------------------------------------------		 
	if(opcion.compareTo("root")==0){
		//2Planar3tROOT
		if(parserState.getTransitionSystem().getName().compareTo("planar 3t arc-eager")==0 
				|| parserState.getTransitionSystem().getName().compareTo("two-planar 3t arc-eager")==0
				|| parserState.getTransitionSystem().getName().compareTo("ucovnonproj")==0){
			
			graphToDependencyTree(parseDependencyGraph);
			
			if(!parseDependencyGraph.isConnected()){
//				parseDependencyGraph.linkAllTreesToRoot();
				linkNoConectedComponent(parseDependencyGraph);
				graphToDependencyTree(parseDependencyGraph);
				//removeRootLinks(parseDependencyGraph);
				
			}
		}else{
			
			if(parserState.getTransitionSystem().getName().compareTo("planar 3t label strategy arc-eager")==0 )
			{
				labeledUndirectedGraphToDepTree(parseDependencyGraph);
				
				//LABEL ANTERIOR 
				parseDependencyGraph.linkAllTreesToRoot();
				removeGuiltyRootLinks(parseDependencyGraph);
				
				if(!parseDependencyGraph.isSingleHeaded())
				{
					solveDoubleHeadProblem(parseDependencyGraph);
				}
			
				if(!parseDependencyGraph.isSingleHeaded())
				{
					solveDoubleHeadProblemAgain(parseDependencyGraph);
					
				}
				
				//NUEVO LABEL
//				linkNoConectedComponent(parseDependencyGraph);
//				holdSingleHead(parseDependencyGraph);
				
			}else{
				parseDependencyGraph.linkAllTreesToRoot();
				
			}
		}
		
	
//--------------------------------------------------------------------------------------------------------------------------------------------------
	}else{
		
		
		if(parserState.getTransitionSystem().getName().compareTo("planar 3t arc-eager")==0){
			
			graphToDependencyTree(parseDependencyGraph);
		  	
			if(!parseDependencyGraph.isConnected()){
				//parseDependencyGraph.linkAllTreesToRoot();
				linkNoConectedComponent(parseDependencyGraph);
				graphToDependencyTree(parseDependencyGraph);
				//removeRootLinks(parseDependencyGraph);
				
			}
		}else{
			
			if(parserState.getTransitionSystem().getName().compareTo("planar 3t label strategy arc-eager")==0 
					|| parserState.getTransitionSystem().getName().compareTo("two-planar 3t arc-eager")==0
					|| parserState.getTransitionSystem().getName().compareTo("ucovnonproj")==0)
			{
				labeledUndirectedGraphToDepTree(parseDependencyGraph);
				if(opcion2.compareTo("old")==0){
 				
					//LABEL ANTERIOR
					parseDependencyGraph.linkAllTreesToRoot();
					removeGuiltyRootLinks(parseDependencyGraph);
				
				
					if(!parseDependencyGraph.isSingleHeaded())
					{
						solveDoubleHeadProblem(parseDependencyGraph);
					}
				
					if(!parseDependencyGraph.isSingleHeaded())
					{
						solveDoubleHeadProblemAgain(parseDependencyGraph);
					
					}
				}else{
					//NUEVO LABEL
					linkNoConectedComponent(parseDependencyGraph);
					holdSingleHead(parseDependencyGraph);

				}
				
			}else{
				parseDependencyGraph.linkAllTreesToRoot();
				
			}
		}
	}
//--------------------------------------------------------------------------------------------------------------------------------------------------		
		if (diagnostics == true) {
			writeToDiaFile("\n");
		}
		
		
		return parseDependencyGraph;
	 
	}
	
	private GuideUserAction predict() throws MaltChainedException {
	    GuideUserAction currentAction = parserState.getHistory().getEmptyGuideUserAction();
		
		
		try {
			classifierGuide.predict((GuideDecision)currentAction);
			
			
			
			while (!parserState.permissible(currentAction)) {
				if (classifierGuide.predictFromKBestList((GuideDecision)currentAction) == false) {
					currentAction = getParserState().getTransitionSystem().defaultAction(parserState.getHistory(), currentParserConfiguration);
					break;
				}
			}
		} catch (NullPointerException e) {
			throw new MaltChainedException("The guide cannot be found. ", e);
		}
		return currentAction;
	}
	
	public void terminate() throws MaltChainedException {
		if (diagnostics == true) {
			closeDiaWriter();
		}
	}
	
	
	private void graphToDependencyTree(DependencyStructure graph) throws MaltChainedException 
	{
        SortedSet<Edge> arcos=graph.getEdges();
		
        Iterator<Edge> itR=arcos.iterator();
		Stack<Edge> roots=new Stack<Edge>();
		Edge arco=null;
		while(itR.hasNext())
		{
			arco=itR.next();
			if(arco.getSource().getIndex()==0)
			{
				roots.push(arco);
			}
		}
		
	  while(!roots.isEmpty()){
		arco=roots.pop();
		  
		Stack<Node> destinos=new Stack<Node>();
		Stack<Node> cabezaDestinos=new Stack<Node>();
		destinos.push(arco.getTarget());
		cabezaDestinos.push(arco.getSource());
		
		while(!destinos.isEmpty()){	
			
			Node puntoDePartida=destinos.pop();
			Node cabezaPDP=cabezaDestinos.pop();
			Iterator<Edge> it=puntoDePartida.getOutgoingEdgeIterator();
			while(it.hasNext())
			{
				arco=it.next();
				destinos.push(arco.getTarget());
				cabezaDestinos.push(arco.getSource());
			}
			
			Iterator<Edge> itI=puntoDePartida.getIncomingEdgeIterator();
			TreeSet<Edge> modificar=new TreeSet<Edge>();
			 
			 while(itI.hasNext())
			 {
				 arco=itI.next();
				if(arco.getSource().getIndex()!=cabezaPDP.getIndex()&&arco.getSource().getIndex()!=0){
					destinos.push(arco.getSource());
				    cabezaDestinos.push(arco.getTarget()); 
				    modificar.add(arco);
				    
				 }      
			 }
			 Edge arcoAModif=null;
			 while(!modificar.isEmpty())
			 {
				 arcoAModif=modificar.first();
				 ((GraphEdge)arcoAModif).changeSense(arcoAModif.getTarget(),arcoAModif.getSource(), 1);
				 modificar.remove(arcoAModif);
			 }
			 
		}	
	  }
		
	}
//	private void removeRootLinks(DependencyStructure graph) throws MaltChainedException 
//	{
//		SortedSet<Integer> nodos=graph.getTokenIndices();
//		for(Integer nodo:nodos)
//		{
//			if(checkIfNodesAreRelated(graph,0,nodo.intValue())&& graph.getTokenNode(nodo).getHeads().size()>1)
//			{
//				graph.removeDependencyEdge(0, nodo);
//			}
//		}
//	}
	
	private void removeGuiltyRootLinks(DependencyStructure graph) throws MaltChainedException 
	{
		SortedSet<Integer> nodos=graph.getTokenIndices();
		for(Integer nodo : nodos)
		{
			if(checkIfNodesAreRelated(graph,0,nodo.intValue())&& graph.getTokenNode(nodo).getHeads().size()>1)
			{
				SortedSet<Integer> nodosE=graph.getTokenIndices();
				for(Integer nodoE : nodosE)
				{
					if(checkIfNodesAreRelated(graph,0,nodoE.intValue())&& nodoE.compareTo(nodo)!=0 && graph.getTokenNode(nodoE).getHeads().size()==1 )
					{
						getEdgeGraph(graph,0,nodoE.intValue()).addLabel(graph.getSymbolTables().getSymbolTable("DEPREL"), "ROOT");
						//graph.removeDependencyEdge(0, nodoE);
						GraphEdge a=(GraphEdge)getEdgeGraph(graph,0,nodo.intValue());
						a.changeSense(a.getSource(), (Node)graph.getTokenNode(nodoE.intValue()), 1);
						getEdgeGraph(graph,0,nodoE.intValue()).addLabel(graph.getSymbolTables().getSymbolTable("DEPREL"), "ROOT");
						break;
					}
				}
				
				
			}
		}
	}
	
	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;
	}
	
	private void labeledUndirectedGraphToDepTree(DependencyStructure graph) throws MaltChainedException
	{
		SortedSet<Edge> edges=graph.getEdges();
		for(Edge edge:edges)
		{
			
			Set<String> names=graph.getSymbolTables().getSymbolTableNames();
			for(String name:names)
			{
				
			 if(name.compareTo("DEPREL")==0)
			 {
				 String label=edge.getLabelSymbol(graph.getSymbolTables().getSymbolTable(name));
				 if(label.charAt(label.length()-1)=='L')
				 {
					 ((GraphEdge)edge).changeSense(edge.getTarget(),edge.getSource(), 1);
				 }
				 label=label.substring(0,label.length()-1);
				 edge.addLabel(graph.getSymbolTables().getSymbolTable(name), label);
			 } 
            }
	       	
		}
	}
	
	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;
	}
	
	private void solveDoubleHeadProblem(DependencyStructure graph) throws MaltChainedException
	{
		SortedSet<Integer> nodos=graph.getTokenIndices();
		for(Integer nodo : nodos)
		{
			if(graph.getTokenNode(nodo).getHeads().size()>1)
			{
				Set<DependencyNode> heads=graph.getTokenNode(nodo).getHeads();
				for(DependencyNode head: heads)
				{
					if(!head.isRoot() && head.getHeads().size()==1 ) 
					{
						Set<DependencyNode> headshead =head.getHeads();
						Iterator<DependencyNode> it=headshead.iterator();
  					    DependencyNode headhead=it.next();
						if(headhead.isRoot()){
						
							GraphEdge a=(GraphEdge)getEdgeGraph(graph,head.getIndex(),nodo.intValue());
							a.changeSense(a.getTarget(), a.getSource(), 1);
							graph.removeDependencyEdge(0, head.getIndex());
							break;
						}	
					}
				}
					
			}
		}
	}
	
	private void solveDoubleHeadProblemAgain(DependencyStructure graph) throws MaltChainedException
	{
	    SortedSet<Integer> nodos=graph.getTokenIndices();
		for(Integer nodo : nodos)
		{
			if(graph.getTokenNode(nodo).getHeads().size()>1)
			{
				Set<DependencyNode> heads=graph.getTokenNode(nodo).getHeads();
				
				Iterator<DependencyNode> it=heads.iterator();
				DependencyNode head1=it.next();
				DependencyNode head2=it.next();
				Stack<Integer> pilaHead1=new Stack<Integer>();
				pilaHead1.push(new Integer(nodo));
				Stack<Integer> pilaHead2=new Stack<Integer>();
				pilaHead2.push(new Integer(nodo));
					
				DependencyNode nextHead1=head1;
				while(!nextHead1.getHead().isRoot())
				{
					pilaHead1.push(new Integer(nextHead1.getIndex()));
					nextHead1=nextHead1.getHead();
				}	
				pilaHead1.push(new Integer(nextHead1.getIndex()));
				
				DependencyNode nextHead2=head2;
				while(!nextHead2.getHead().isRoot())
				{
					pilaHead2.push(new Integer(nextHead2.getIndex()));
					nextHead2=nextHead2.getHead();
				}
				pilaHead2.push(new Integer(nextHead2.getIndex()));
				
				if(nextHead1.getIndex()<nextHead2.getIndex())
				{
					graph.removeDependencyEdge(0, nextHead2.getIndex());
					while(pilaHead2.peek().intValue()!=nodo)
					{
						int origen=pilaHead2.pop().intValue();
						int destino=pilaHead2.peek().intValue();	
						GraphEdge a=(GraphEdge)getEdgeGraph(graph,origen,destino);
						a.changeSense(a.getTarget(), a.getSource(), 1);
					}
					
					
				}else{
					graph.removeDependencyEdge(0, nextHead1.getIndex());
					while(pilaHead1.peek().intValue()!=nodo)
					{
						int origen=pilaHead1.pop().intValue();
						int destino=pilaHead1.peek().intValue();	
						GraphEdge a=(GraphEdge)getEdgeGraph(graph,origen,destino);
						a.changeSense(a.getTarget(), a.getSource(), 1);
					}
				}
			}
		}
	}
	
	private boolean holdSingleHead(DependencyStructure graph) throws MaltChainedException
	{
		
		SortedSet<Integer> unattach = graph.getTokenIndices();
		SortedSet<Integer> nodos=graph.getTokenIndices();
		
		
		for(Integer nodo : nodos)
		{
		   if(graph.getTokenNode(nodo).hasHead())
		    {
		    	  unattach.remove(nodo);
		    }
		}
		
		if(unattach.isEmpty()){
			return true;
		}
		
		//Cambiamos el sentido de los arcos
		for(Integer unodo : unattach)
		{
			//Es necesario seleccionar el hijo del nodo que lleva al ROOT
			SortedSet<DependencyNode> hijosIzq = graph.getTokenNode(unodo).getLeftDependents();
			SortedSet<DependencyNode> hijosDer = graph.getTokenNode(unodo).getRightDependents();
			for(DependencyNode hijo:hijosDer)
			{
				hijosIzq.add(hijo);
			}
			
			int destino=graph.getTokenNode(unodo).getClosestLeftDependent().getIndex();
			for(DependencyNode hijo:hijosIzq)
			{
				Set<Integer> conectedNodes= new HashSet<Integer>();
				conectedNodes(hijo.getIndex(),unodo, conectedNodes, graph);
				if(conectedNodes.contains(0))
				{
					destino=hijo.getIndex();	
					break;
				}
			}
			
			
			int origen=unodo;
			GraphEdge a=(GraphEdge)getEdgeGraph(graph,origen,destino);
			a.changeSense(a.getTarget(), a.getSource(), 1);
			
		}
		
        unattach = graph.getTokenIndices();
		nodos=graph.getTokenIndices();
		for(Integer nodo : nodos)
		{
		    if(graph.getTokenNode(nodo).hasHead())
		    {
		    	unattach.remove(nodo);
		    }
		}
		
		if(unattach.isEmpty()){
			return true;
		}else{
		    return 	holdSingleHead(graph);
		}
	}
	
	private void linkNoConectedComponent(DependencyStructure graph) throws MaltChainedException
	{
        SortedSet<Integer> nodos=graph.getTokenIndices();
		
		for(Integer nodo : nodos)
		{
			if(!graph.getTokenNode(nodo).hasHead())
			{
				Set<Integer> conectedNodes= new HashSet<Integer>();
				conectedNodes(nodo, nodo, conectedNodes, graph);
				if(!conectedNodes.contains(0))
				{
					graph.addDependencyEdge(0, nodo);
				}
			}
		}
	}
	
	private void conectedNodes(int node, int nodeObj, Set<Integer> conectedNodes, DependencyStructure graph) throws MaltChainedException
	{
		SortedSet<Integer> allNodes=graph.getTokenIndices();
		//Es necesario aádir el ROOT a allNodes ya que getTokenIndices() no lo incluye
		allNodes.add(0);
		
	
	
		for(Integer nodo : allNodes)
		{
			
			if(checkIfNodesAreRelated( graph , nodo , node ))
			{	
				//Nunca se puede incluir en los nodos a los que conecta el nodo objetivo
				if(!conectedNodes.contains(nodo)&&nodo!=nodeObj)
				{   
					 conectedNodes.add(nodo);
					 conectedNodes(nodo,nodeObj,conectedNodes,graph);
				}
			}
		}
	
	}
	
	}
