package edu.unl.consystlab.sudokuSolver;
import java.util.Iterator;
import java.util.Stack;
import java.util.List;
import java.util.LinkedList;
import java.util.Collection;

import com.sun.org.apache.bcel.internal.generic.CPInstruction;
import com.sun.org.apache.xalan.internal.xsltc.runtime.Hashtable;

import edu.unl.consystlab.sudokuSolver.consistencyAlgorithms.arcConsistency;
import edu.unl.consystlab.sudokuSolver.consistencyAlgorithms.binaryForwardCheckOnVariable;
import edu.unl.consystlab.sudokuSolver.consistencyAlgorithms.consistencyAlgorithm;
import edu.unl.consystlab.sudokuSolver.consistencyAlgorithms.nonBinaryMAC;
import edu.unl.consystlab.sudokuSolver.consistencyAlgorithms.shavingGAC;
import edu.unl.consystlab.sudokuSolver.consistencyAlgorithms.shavingMAC;


public class forwardCheckingSearch {

	class domainIterator{
		public List myList;
		public int nextIndex;
		
		public domainIterator(List newList)
		{
			this.myList = newList;
			this.nextIndex = 0;
		}
	}
	
	private constraintProblem problem;
	private List solutions;
	private Stack solutionTree;
	private Stack domainReductions;
	public int BACKTRACKS;
	
	public forwardCheckingSearch(constraintProblem newProblem)
	{
		solutions = new LinkedList();
		problem = newProblem;
		solutionTree = new Stack();
		domainReductions = new Stack();
	}
	
	public int getSolutionNum()
	{
		return solutions.size();
	}

        public List getSolutions()
	{
		return solutions;
	}

	public void solve() throws InterruptedException
	{
		BACKTRACKS = 0;
		
		//run the consistency algorithms
		if(!runConsistancyAlgorithms())
		{
			//there was an error we can't fix
			return;
		}
		
		//put the preassignes and values the consistency found into the solution tree
		for(int lineIndex = 1; lineIndex <= problem.totalLines; lineIndex++)
		{
			for(int columnIndex = 1; columnIndex <= problem.totalColumns; columnIndex++)
			{
				if(problem.getVariable(lineIndex + "," + columnIndex).isAssigned() )
				{
					problemVariable currentVariable = problem.getVariable(lineIndex + "," + columnIndex);
					solutionTree.push(currentVariable);
					//The preassigns should be consistent if the problem is not malformed.
					//check anyway
					if(!reduceDomains(currentVariable))
					{
						//there is a failure we can do nothing to fix. return in failure.
						return;
					}
				}
			}
		}
		
		//get the length of the queue so we know when no solution is found
		int noSolutionCutoff = solutionTree.size();
		
		//get where to begin
		problemVariable currentVariable = getNextVariable();

		//check to see that it is not all filled in
		if(currentVariable == null)
		{
			//it is solved, by consistency or trivially by preassignes
			//get the solution in a 2 dimentional array.
			String[][] newSolution = new String[problem.totalLines+1][problem.totalColumns+1];
			
			Iterator i = solutionTree.iterator();
			while(i.hasNext())
			{
				problemVariable currVar = (problemVariable)i.next();
				newSolution[currVar.getLineIndex()][currVar.getColumnIndex()] = 
						currVar.getAssigned();
			}
			//add the solution to the list
			solutions.add(newSolution);
			return;
		}
		
		//need a hashtable to keep track of its original domain
		Hashtable initialPosibleValues = new Hashtable();
		
		boolean consistentValue;
		//loop until we have gotten all of the variables assigned.
		do
		{
            if(Thread.interrupted())
            {
                throw new InterruptedException();
            }
			//loop until we have found a consistent value for our variable
			do
			{
                if(Thread.interrupted())
                {
                    throw new InterruptedException();
                }
				consistentValue = true;

				//assign the variable the first value in its domain
				// if it is not already assigned a value otherwise give it the next value.
				if(!currentVariable.isAssigned())
				{
					//make sure there is something in the domain
					if(currentVariable.getCurrentDomainSize() != 0)
					{
						//record the possible values it can take
						initialPosibleValues.put( currentVariable, new domainIterator(new LinkedList(currentVariable.getEntireDomain())) );
						currentVariable.setAssigned(
								((String)
										((LinkedList)
												((domainIterator)initialPosibleValues.get(currentVariable)).myList).get(0)) );
						//move curent to the next value
						((domainIterator)initialPosibleValues.get(currentVariable)).nextIndex++;
						consistentValue = reduceDomains(currentVariable);
						//if it was not consistent we need to get rid of the assignments we made
						if(!consistentValue)
						{
							unreduceDomains();
						}
						//if we did succeed we need to get the next variable and add ourselves
						// the the solution tree.
						else
						{
							solutionTree.push(currentVariable);	
							currentVariable = getNextVariable();
						}		
					}
					else
					{
						//we need to backtrack
						
						//all we do is set the variable above us as the currentVariable and it starts
						//looking for a consistent value at the next one
						//we also have to unreduce its effects because they are what made us fail.
						
						//make sure we haven't reached the root of the tree aka the 
						//end of the preassigns.
						if(solutionTree.size()!=noSolutionCutoff)
						{
							consistentValue = false;
							currentVariable.unSetAssigned();
							//restore its domain
							currentVariable.setCurrentDomain(
									((domainIterator)initialPosibleValues.get(currentVariable)).myList
									);
							currentVariable = (problemVariable)solutionTree.pop();
							unreduceDomains();
						}
						else
						{
							//we have failed
							return;
						}
					}
				}
				else //if it is assigned then
				{
					domainIterator currentIterator = (domainIterator)initialPosibleValues.get(currentVariable);
					//make sure we aren't at the last value
					if( currentIterator.nextIndex < currentIterator.myList.size() )
					{//if there are more values
						currentVariable.setAssigned((String)currentIterator.myList.get(currentIterator.nextIndex));
						//remove this value from the possible values it can take
						currentIterator.nextIndex++;
						consistentValue = reduceDomains(currentVariable);
						//if it was not consistent we need to get rid of the assignments we made
						if(!consistentValue)
						{
							unreduceDomains();
						}	
						//if we did succeed we need to get the next variable and add ourselves
						// the the solution tree.
						else
						{
							solutionTree.push(currentVariable);	
							currentVariable = getNextVariable();
						}
					}
					else
					{
						//we need to backtrack
						
						//all we do is set the variable above us as the currentVariable and it starts
						//looking for a consistent value at the next one
						//we also have to unreduce its effects because they are what made us fail.
						
						//make sure we haven't reached the root of the tree aka the 
						//end of the preassigns.
						if(solutionTree.size()!=noSolutionCutoff)
						{
							consistentValue=false;
							currentVariable.unSetAssigned();
							//restore its domain
							currentVariable.setCurrentDomain(
									((domainIterator)initialPosibleValues.get(currentVariable)).myList
									);
							currentVariable = (problemVariable)solutionTree.pop();
							unreduceDomains();
						}
						else
						{
							//we have failed
							return;
						}
					}
				}
			}while(!consistentValue);

			//check to see if the current variable is null, if so we have found a solution.
			//in which case we should backtrack and find any more solutions.
			if(currentVariable == null)
			{
				//get the solution in a 2 dimentional array.
				String[][] newSolution = new String[problem.totalLines+1][problem.totalColumns+1];
				
				Iterator i = solutionTree.iterator();
				while(i.hasNext())
				{
					problemVariable currVar = (problemVariable)i.next();
					newSolution[currVar.getLineIndex()][currVar.getColumnIndex()] = 
							currVar.getAssigned();
				}

				
				//add the solution to the list
				solutions.add(newSolution);

                if(solutions.size() > 50)
                    return;
				
				//backtrack to the last assigned variable
				currentVariable = (problemVariable)solutionTree.pop();
				unreduceDomains(); //this should just pop the top null off that list
				
				//unassign the variable and either backtrack or give it the next value.
			}
			
			//we are ready for the next variable, wether it be forwards or backwards.
			//just make sure it is not the end
		}while( currentVariable != null);
		
		//we should never get here any more
		//since we now find all solutions
		return;

			//if it is not in the solution put it in
				//ititialize it to the first element in its domain
					//redact future domains
						//make sure redacted domains are not empty
							//if any domains are empty try a different value
								//etc
		
	}
	public void printSolution()
	{
		System.out.println("Solutions:"+solutions.size());
		//print all the solutions
		for(int solutionIndex = solutions.size()-1; solutionIndex >= 0; solutionIndex--)
		{
			String[][] solutionArray = (String[][])solutions.get(solutionIndex);
			for(int lineIndex = 1; lineIndex <= problem.totalLines; lineIndex++)
			{
				for(int columnIndex = 1; columnIndex <= problem.totalColumns; columnIndex++)
				{

					System.out.print(solutionArray[lineIndex][columnIndex]);

					if((columnIndex % problem.columnsPerUnit) ==0 && columnIndex!=problem.totalColumns)
					{
						System.out.print("|");
					}
					else if(columnIndex==problem.totalColumns)
					{
						System.out.print('\n');
					}
				}
				if((lineIndex % problem.linesPerUnit) == 0 && lineIndex!=problem.totalLines)
				{
					for(int i=0; i< (problem.totalColumns +problem.linesPerUnit-1); i++)
						System.out.print("-");
					System.out.print('\n');
				}
			}
			if(solutionIndex != 0)
			{
				System.out.println("+"); //put a line between solutions
			}
		}
		System.out.println("BACKTRACKS : "+ BACKTRACKS);
	}
	

	//returns false if there was an error
	// true otherwise
	private boolean runConsistancyAlgorithms() throws InterruptedException
	{
		consistencyAlgorithm myAC = new arcConsistency(problem, null);
		if(!myAC.runAlgorithm())
		{
			return false;
		}
		consistencyAlgorithm myGAC = new nonBinaryMAC(problem, null);
		if(!myGAC.runAlgorithm())
		{
			return false;
		}
		assignSingletons myAssignSingletons = new assignSingletons(problem);
		myAssignSingletons.runAlgorithm();
		consistencyAlgorithm myShavingAC = new shavingMAC(problem, null);
		if(!myShavingAC.runAlgorithm())
		{
			return false;
		}
		myAssignSingletons.runAlgorithm();
		consistencyAlgorithm myShavingGAC = new shavingGAC(problem, null);
		if(!myShavingGAC.runAlgorithm())
		{
			return false;
		}
		myAssignSingletons.runAlgorithm();
		
		return true;
	}
	
	private void unreduceDomains()
	{
		BACKTRACKS++;
		List domainsToUnreduce = (LinkedList)domainReductions.pop();
		variableIndexAndValueGrouping currentReduction;
		while(domainsToUnreduce != null && domainsToUnreduce.size() != 0)
		{
			//get the first element in the list
			currentReduction = (variableIndexAndValueGrouping)domainsToUnreduce.get(0);
			
			//restore its domain
			problem.getVariable(currentReduction.getVariableIndex()).addToCurrentDomain(
					currentReduction.getValue());
			
			//remove it from the list
			domainsToUnreduce.remove(0);

		}
		
	}
	
	public boolean reduceDomains(problemVariable masterVariable) throws InterruptedException
	{
		consistencyAlgorithm mybinaryForwardCheck = new binaryForwardCheckOnVariable(problem, null, masterVariable);
		mybinaryForwardCheck.runAlgorithm();
		//should atleast push an empty one if nothing else.
		domainReductions.push(mybinaryForwardCheck.getVariableReductions());
		return(!mybinaryForwardCheck.isEncounteredError());
	}
	
	private problemVariable getNextVariable ()
	{
		//for now start in the upper left
		for(int lineIndex = 1; lineIndex <= problem.totalLines; lineIndex++)
		{
			for(int columnIndex = 1; columnIndex <= problem.totalColumns; columnIndex++)
			{				
				if(!problem.getVariable(lineIndex + "," + columnIndex).isAssigned() )
				{
					problemVariable nextVariable = problem.getVariable(lineIndex + "," + columnIndex);		
					return(nextVariable);
				}
			}
		}
		//if we get here there are none left to assign
		return(null);
	}
}