package edu.unl.consystlab.sudokuSolver;

import java.util.Collection;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

import edu.unl.consystlab.sudokuSolver.consistencyAlgorithms.arcConsistency;
import edu.unl.consystlab.sudokuSolver.consistencyAlgorithms.binaryForwardCheckAll;
import edu.unl.consystlab.sudokuSolver.consistencyAlgorithms.consistencyAlgorithm;
import edu.unl.consystlab.sudokuSolver.consistencyAlgorithms.nonBinaryMAC;
import edu.unl.consystlab.sudokuSolver.consistencyAlgorithms.nonBinaryRestrictedArcConsistency;
import edu.unl.consystlab.sudokuSolver.consistencyAlgorithms.shavingGAC;
import edu.unl.consystlab.sudokuSolver.consistencyAlgorithms.shavingMAC;
import edu.unl.consystlab.sudokuSolver.consistencyAlgorithms.shavingSingleGAC;
import edu.unl.consystlab.sudokuSolver.consistencyAlgorithms.shavingSingleMAC;
import java.util.logging.Level;
import java.util.logging.Logger;

public class hints extends Thread
{
	
	
	private static String FC_LEVEL = "FC";
	private static String AC_LEVEL = "AC";
	private static String SINGLE_GAC_LEVEL = "Single GAC";
	private static String GAC_LEVEL = "GAC";
	private static String SINGLE_SAC_LEVEL = "Single SAC";
	private static String SAC_LEVEL = "SAC";
	private static String SINGLE_SGAC_LEVEL = "Single SGAC";
	private static String SGAC_LEVEL = "SGAC";
	
	//we do all of the consistency algorithms on a copy of the problem and return
	// all results as elements of the original problem
	private constraintProblem myOriginalProblem;
	private constraintProblem myInternalCopy;
	private String hintLevel;
	private String hintType;
	private int currentHintIndex;
	//this is a list of hint variables stored internally as the copy problem's variables
	//we only convert them when returning them.
	private List hintVariables;
	//since GAC, Single SAC, and Single SGAC are so complicated we keep a copy of the vitals or singletons
	// that we currently aren't using in here.
	private List switchVariables;
	//same thing with the errorConstraint, it is stored as the copy's error and converted to
	// the original's error when returning.
	private problemConstraint errorConstraint;

    

    hints(constraintProblem originalProblem, constraintProblem myCopy) {
        myOriginalProblem = originalProblem;
		hintVariables = null;
		errorConstraint = null;
		hintLevel = null;
		hintType = null;
		currentHintIndex = -1;
		myInternalCopy = myCopy;
    }

    
   

	public void calculateHint() 
	{
        try {
            calculateHint(null);
        } catch (InterruptedException ex) {
            
        }
	}
	
	public void incrementLevel() throws InterruptedException
	{
        //reset everything
        hintVariables = null;
        errorConstraint = null;
        //hintLevel = null;
        hintType = null;
        currentHintIndex = -1;
        myInternalCopy = myOriginalProblem.copy();

        if(hintLevel.equals(FC_LEVEL))
		{
			calculateHint(AC_LEVEL);
			return;
		}
		else if(hintLevel.equals(AC_LEVEL))
		{
			calculateHint(SINGLE_GAC_LEVEL);
			return;
		}
		else if(hintLevel.equals(SINGLE_GAC_LEVEL))
		{
			calculateHint(GAC_LEVEL);
			return;
		}
		else if(hintLevel.equals(GAC_LEVEL))
		{
			calculateHint(SINGLE_SAC_LEVEL);
			return;
		}		
		else if(hintLevel.equals(SINGLE_SAC_LEVEL))
		{
			calculateHint(SAC_LEVEL);
			return;
		}
		else if(hintLevel.equals(SAC_LEVEL))
		{
			calculateHint(SINGLE_SGAC_LEVEL);
			return;
		}
		else if(hintLevel.equals(SINGLE_SGAC_LEVEL))
		{
			calculateHint(SGAC_LEVEL);
			return;
		}
		else if(hintLevel.equals(SGAC_LEVEL))
		{
			calculateHint(FC_LEVEL);
			return;
		}
	}

    public void decrementLevel() throws InterruptedException {

        //reset everything and go back to FC_LEVEL
        hintVariables = null;
        errorConstraint = null;
        //hintLevel = null;
        hintType = null;
        currentHintIndex = -1;
        myInternalCopy = myOriginalProblem.copy();

        if(hintLevel.equals(AC_LEVEL))
		{
			calculateHintPrev(FC_LEVEL);
			return;
		}
		else if(hintLevel.equals(SINGLE_GAC_LEVEL))
		{
			calculateHintPrev(AC_LEVEL);
			return;
		}
		else if(hintLevel.equals(GAC_LEVEL))
		{
			calculateHintPrev(SINGLE_GAC_LEVEL);
			return;
		}
		else if(hintLevel.equals(SINGLE_SAC_LEVEL))
		{
			calculateHintPrev(GAC_LEVEL);
			return;
		}
		else if(hintLevel.equals(SAC_LEVEL))
		{
			calculateHintPrev(SINGLE_SAC_LEVEL);
			return;
		}
		else if(hintLevel.equals(SINGLE_SGAC_LEVEL))
		{
			calculateHintPrev(SAC_LEVEL);
			return;
		}
		else if(hintLevel.equals(SGAC_LEVEL))
		{
			calculateHintPrev(SINGLE_SGAC_LEVEL);
			return;
		}
		else if(hintLevel.equals(FC_LEVEL))
		{
			calculateHintPrev(SGAC_LEVEL);
			return;
		}
    }

    

	//level and type can be null or specify a specific level that we should be looking for
	private void calculateHint(String level) throws InterruptedException
    {
        if(myInternalCopy == null)
		{
			return;
		}
    
		if(level == null || level.equals(FC_LEVEL))
		{
            //run FC
			consistencyAlgorithm myFC = new binaryForwardCheckAll(myInternalCopy, null);
			//if it finds something stop
			if(runConsistencyLevel(FC_LEVEL, myFC))
			{
				return;
			}
			//if we didn't find anything then we want to keep going so we set level to null
			level = null;
		}

		if(level == null || level.equals(AC_LEVEL))
		{
			//run AC
			consistencyAlgorithm myAC = new arcConsistency(myInternalCopy, null);
			//if it finds something stop
			if(runConsistencyLevel(AC_LEVEL, myAC))
			{
				return;
			}
			//if we didn't find anything then we want to keep going so we set level to null
			level = null;
			
			//undo the reductions.
			Iterator i = myAC.getVariableReductions().iterator();
			while(i.hasNext())
			{
				variableIndexAndValueGrouping currentReduction = (variableIndexAndValueGrouping)i.next();
				myInternalCopy.getVariable(currentReduction.getVariableIndex())
					.addToCurrentDomain(currentReduction.getValue());
				
			}
		}

        
		
		if(level == null || level.equals(SINGLE_GAC_LEVEL))
		{
			
			//now we run GAC on each row, gather all the new hints, undo it
			// run GAC on each col, gather all the new hints, undo it
			// run GAC on each unit, gather all the new hints, undo it
			// and consider this all one level of hints
			Set gacSingletonHints = new HashSet();
			Set gacVitalHints = new HashSet();
	
			//run GAC on the lines
			//if there is an error stop
			if(!runGACLineCol(gacSingletonHints,gacVitalHints, "L"))
			{
				return;
			}
			
			//run GAC on the cols
			//if there is an error stop
			if(!runGACLineCol(gacSingletonHints,gacVitalHints, "C"))
			{
				return;
			}
			
			//run GAC on the units
			//if there is an error stop
			if(!runGACUnit(gacSingletonHints,gacVitalHints))
			{
				return;
			}
			
			//now check if we are have found a hint and can stop
			if(gacSingletonHints.size() > 0)
			{
				hintVariables = new LinkedList(gacSingletonHints);
				switchVariables = new LinkedList(gacVitalHints);
				errorConstraint = null;
				hintLevel = SINGLE_GAC_LEVEL;
				hintType = "Singleton";
				currentHintIndex = 0;
				return;
			}
			else if(gacVitalHints.size() > 0)
			{
				hintVariables = new LinkedList(gacVitalHints);
				switchVariables = new LinkedList(gacSingletonHints);
				errorConstraint = null;
				hintLevel = SINGLE_GAC_LEVEL;
				hintType = "Vital";
				currentHintIndex = 0;
				return;
			}
			//if we didn't find anything then we want to keep going so we set level to null
			level = null;
		}
	
		if(level == null || level.equals(GAC_LEVEL))
		{
			//run GAC on the entire problem
			consistencyAlgorithm myGAC = new nonBinaryMAC(myInternalCopy, null);
			//if it finds something stop
			if(runConsistencyLevel(GAC_LEVEL, myGAC))
			{
				return;
			}
			//if we didn't find anything then we want to keep going so we set level to null
			level = null;
			//undo the reductions.
			Iterator i = myGAC.getVariableReductions().iterator();
			while(i.hasNext())
			{
				variableIndexAndValueGrouping currentReduction = (variableIndexAndValueGrouping)i.next();
				myInternalCopy.getVariable(currentReduction.getVariableIndex())
					.addToCurrentDomain(currentReduction.getValue());
				
			}
		}

		if(level == null || level.equals(SINGLE_SAC_LEVEL))
		{	
			Set newHints = new HashSet();
			Set switchHints = new HashSet();
			Iterator i = myInternalCopy.getAllVariables().iterator();
			while(i.hasNext())
			{
				problemVariable currentVariable = (problemVariable)i.next();
				consistencyAlgorithm mySingleSAC = new shavingSingleMAC(myInternalCopy, null, currentVariable);

				if(mySingleSAC.runAlgorithm())
				{
					newHints.addAll(checkSingletons());
					switchHints.addAll(checkVitals());

				}
				else //there was an error
				{
					logError(mySingleSAC, SINGLE_SAC_LEVEL);
					return;
				}
				
				//undo the reductions.
				Iterator j = mySingleSAC.getVariableReductions().iterator();
				while(j.hasNext())
				{
					variableIndexAndValueGrouping currentReduction = (variableIndexAndValueGrouping)j.next();
					myInternalCopy.getVariable(currentReduction.getVariableIndex())
						.addToCurrentDomain(currentReduction.getValue());
					
				}

			}

			String currLevel = SINGLE_SAC_LEVEL;
			if(newHints.isEmpty())
			{
				//make it the switchHints;
				Collection temp = switchHints;
				switchHints = newHints;
				newHints = (Set)temp;
				if(newHints.isEmpty())
				{
					//if we didn't find anything then we want to keep going so we set level to null
					level = null;
				}
				else
				{
					List newHintsList = new LinkedList(newHints);
					List switchHintsList = new LinkedList(switchHints);
					setPrivates(currLevel, "Vital", newHintsList, switchHintsList);
					return;
				}
			}
			else
			{
				List newHintsList = new LinkedList(newHints);
				List switchHintsList = new LinkedList(switchHints);
				setPrivates(currLevel, "Singleton", newHintsList, switchHintsList);
				return;
			}
			

		}

		if(level == null || level.equals(SAC_LEVEL))
		{
			//run SAC on the entire problem
			consistencyAlgorithm mySAC = new shavingMAC(myInternalCopy, null);
			//if it finds something stop
			if(runConsistencyLevel(SAC_LEVEL, mySAC))
			{
				return;
			}
			//if we didn't find anything then we want to keep going so we set level to null
			level = null;
			//undo the reductions.
			Iterator i = mySAC.getVariableReductions().iterator();
			while(i.hasNext())
			{
				variableIndexAndValueGrouping currentReduction = (variableIndexAndValueGrouping)i.next();
				myInternalCopy.getVariable(currentReduction.getVariableIndex())
					.addToCurrentDomain(currentReduction.getValue());
				
			}
		}

        
		if(level == null || level.equals(SINGLE_SGAC_LEVEL))
		{	
			Set newHints = new HashSet();
			Set switchHints = new HashSet();
			Iterator i = myInternalCopy.getAllVariables().iterator();
			while(i.hasNext())
			{
				problemVariable currentVariable = (problemVariable)i.next();
				consistencyAlgorithm mySingleSGAC = new shavingSingleGAC(myInternalCopy, null, currentVariable);

				if(mySingleSGAC.runAlgorithm())
				{
					newHints.addAll(checkSingletons());
					switchHints.addAll(checkVitals());

				}
				else //there was an error
				{
					logError(mySingleSGAC, SINGLE_SGAC_LEVEL);
					return;
				}
				
				//undo the reductions.
				Iterator j = mySingleSGAC.getVariableReductions().iterator();
				while(j.hasNext())
				{
					variableIndexAndValueGrouping currentReduction = (variableIndexAndValueGrouping)j.next();
					myInternalCopy.getVariable(currentReduction.getVariableIndex())
						.addToCurrentDomain(currentReduction.getValue());
					
				}

			}

			String currLevel = SINGLE_SGAC_LEVEL;
			if(newHints.isEmpty())
			{
				//make it the switchHints;
				Collection temp = switchHints;
				switchHints = newHints;
				newHints = (Set)temp;
				if(newHints.isEmpty())
				{
					//if we didn't find anything then we want to keep going so we set level to null
					level = null;
				}
				else
				{
					List newHintsList = new LinkedList(newHints);
					List switchHintsList = new LinkedList(switchHints);
					setPrivates(currLevel, "Vital", newHintsList, switchHintsList);
					return;
				}
			}
			else
			{
				List newHintsList = new LinkedList(newHints);
				List switchHintsList = new LinkedList(switchHints);
				setPrivates(currLevel, "Singleton", newHintsList, switchHintsList);
				return;
			}
			

		}
		
		
		if(level == null || level.equals(SGAC_LEVEL))
		{
			//run SGAC on the entire problem
			consistencyAlgorithm mySGAC = new shavingGAC(myInternalCopy, null);
			//if it finds something stop
			if(runConsistencyLevel(SGAC_LEVEL, mySGAC))
			{
				return;
			}
		}


        
		
		//no hint was found
		hintVariables = null;
		errorConstraint = null;
		hintLevel = null;
		hintType = null;
		currentHintIndex = -1;
		return;
	}

    private void calculateHintPrev(String level) throws InterruptedException
	{
		if(myInternalCopy == null)
		{
			return;
		}

        if(level == null || level.equals(SGAC_LEVEL))
		{
			//run SGAC on the entire problem
			consistencyAlgorithm mySGAC = new shavingGAC(myInternalCopy, null);
			//if it finds something stop
			if(runConsistencyLevel(SGAC_LEVEL, mySGAC))
			{
				return;
			}
		}

		if(level == null || level.equals(SINGLE_SGAC_LEVEL))
		{
			Set newHints = new HashSet();
			Set switchHints = new HashSet();
			Iterator i = myInternalCopy.getAllVariables().iterator();
			while(i.hasNext())
			{
				problemVariable currentVariable = (problemVariable)i.next();
				consistencyAlgorithm mySingleSGAC = new shavingSingleGAC(myInternalCopy, null, currentVariable);

				if(mySingleSGAC.runAlgorithm())
				{
					newHints.addAll(checkSingletons());
					switchHints.addAll(checkVitals());

				}
				else //there was an error
				{
					logError(mySingleSGAC, SINGLE_SGAC_LEVEL);
					return;
				}

				//undo the reductions.
				Iterator j = mySingleSGAC.getVariableReductions().iterator();
				while(j.hasNext())
				{
					variableIndexAndValueGrouping currentReduction = (variableIndexAndValueGrouping)j.next();
					myInternalCopy.getVariable(currentReduction.getVariableIndex())
						.addToCurrentDomain(currentReduction.getValue());

				}

			}

			String currLevel = SINGLE_SGAC_LEVEL;
			if(newHints.isEmpty())
			{
				//make it the switchHints;
				Collection temp = switchHints;
				switchHints = newHints;
				newHints = (Set)temp;
				if(newHints.isEmpty())
				{
					//if we didn't find anything then we want to keep going so we set level to null
					level = null;
				}
				else
				{
					List newHintsList = new LinkedList(newHints);
					List switchHintsList = new LinkedList(switchHints);
					setPrivates(currLevel, "Vital", newHintsList, switchHintsList);
					return;
				}
			}
			else
			{
				List newHintsList = new LinkedList(newHints);
				List switchHintsList = new LinkedList(switchHints);
				setPrivates(currLevel, "Singleton", newHintsList, switchHintsList);
				return;
			}


		}

		if(level == null || level.equals(SAC_LEVEL))
		{
			//run SAC on the entire problem
			consistencyAlgorithm mySAC = new shavingMAC(myInternalCopy, null);
			//if it finds something stop
			if(runConsistencyLevel(SAC_LEVEL, mySAC))
			{
				return;
			}
			//if we didn't find anything then we want to keep going so we set level to null
			level = null;
			//undo the reductions.
			Iterator i = mySAC.getVariableReductions().iterator();
			while(i.hasNext())
			{
				variableIndexAndValueGrouping currentReduction = (variableIndexAndValueGrouping)i.next();
				myInternalCopy.getVariable(currentReduction.getVariableIndex())
					.addToCurrentDomain(currentReduction.getValue());

			}
		}

		if(level == null || level.equals(SINGLE_SAC_LEVEL))
		{
			Set newHints = new HashSet();
			Set switchHints = new HashSet();
			Iterator i = myInternalCopy.getAllVariables().iterator();
			while(i.hasNext())
			{
				problemVariable currentVariable = (problemVariable)i.next();
				consistencyAlgorithm mySingleSAC = new shavingSingleMAC(myInternalCopy, null, currentVariable);

				if(mySingleSAC.runAlgorithm())
				{
					newHints.addAll(checkSingletons());
					switchHints.addAll(checkVitals());

				}
				else //there was an error
				{
					logError(mySingleSAC, SINGLE_SAC_LEVEL);
					return;
				}

				//undo the reductions.
				Iterator j = mySingleSAC.getVariableReductions().iterator();
				while(j.hasNext())
				{
					variableIndexAndValueGrouping currentReduction = (variableIndexAndValueGrouping)j.next();
					myInternalCopy.getVariable(currentReduction.getVariableIndex())
						.addToCurrentDomain(currentReduction.getValue());

				}

			}

			String currLevel = SINGLE_SAC_LEVEL;
			if(newHints.isEmpty())
			{
				//make it the switchHints;
				Collection temp = switchHints;
				switchHints = newHints;
				newHints = (Set)temp;
				if(newHints.isEmpty())
				{
					//if we didn't find anything then we want to keep going so we set level to null
					level = null;
				}
				else
				{
					List newHintsList = new LinkedList(newHints);
					List switchHintsList = new LinkedList(switchHints);
					setPrivates(currLevel, "Vital", newHintsList, switchHintsList);
					return;
				}
			}
			else
			{
				List newHintsList = new LinkedList(newHints);
				List switchHintsList = new LinkedList(switchHints);
				setPrivates(currLevel, "Singleton", newHintsList, switchHintsList);
				return;
			}


		}

		if(level == null || level.equals(GAC_LEVEL))
		{
			//run GAC on the entire problem
			consistencyAlgorithm myGAC = new nonBinaryMAC(myInternalCopy, null);
			//if it finds something stop
			if(runConsistencyLevel(GAC_LEVEL, myGAC))
			{
				return;
			}
			//if we didn't find anything then we want to keep going so we set level to null
			level = null;
			//undo the reductions.
			Iterator i = myGAC.getVariableReductions().iterator();
			while(i.hasNext())
			{
				variableIndexAndValueGrouping currentReduction = (variableIndexAndValueGrouping)i.next();
				myInternalCopy.getVariable(currentReduction.getVariableIndex())
					.addToCurrentDomain(currentReduction.getValue());

			}
		}



		if(level == null || level.equals(SINGLE_GAC_LEVEL))
		{

			//now we run GAC on each row, gather all the new hints, undo it
			// run GAC on each col, gather all the new hints, undo it
			// run GAC on each unit, gather all the new hints, undo it
			// and consider this all one level of hints
			Set gacSingletonHints = new HashSet();
			Set gacVitalHints = new HashSet();

			//run GAC on the lines
			//if there is an error stop
			if(!runGACLineCol(gacSingletonHints,gacVitalHints, "L"))
			{
				return;
			}

			//run GAC on the cols
			//if there is an error stop
			if(!runGACLineCol(gacSingletonHints,gacVitalHints, "C"))
			{
				return;
			}

			//run GAC on the units
			//if there is an error stop
			if(!runGACUnit(gacSingletonHints,gacVitalHints))
			{
				return;
			}

			//now check if we are have found a hint and can stop
			if(gacSingletonHints.size() > 0)
			{
				hintVariables = new LinkedList(gacSingletonHints);
				switchVariables = new LinkedList(gacVitalHints);
				errorConstraint = null;
				hintLevel = SINGLE_GAC_LEVEL;
				hintType = "Singleton";
				currentHintIndex = 0;
				return;
			}
			else if(gacVitalHints.size() > 0)
			{
				hintVariables = new LinkedList(gacVitalHints);
				switchVariables = new LinkedList(gacSingletonHints);
				errorConstraint = null;
				hintLevel = SINGLE_GAC_LEVEL;
				hintType = "Vital";
				currentHintIndex = 0;
				return;
			}
			//if we didn't find anything then we want to keep going so we set level to null
			level = null;
		}

		if(level == null || level.equals(AC_LEVEL))
		{
			//run AC
			consistencyAlgorithm myAC = new arcConsistency(myInternalCopy, null);
			//if it finds something stop
			if(runConsistencyLevel(AC_LEVEL, myAC))
			{
				return;
			}
			//if we didn't find anything then we want to keep going so we set level to null
			level = null;

			//undo the reductions.
			Iterator i = myAC.getVariableReductions().iterator();
			while(i.hasNext())
			{
				variableIndexAndValueGrouping currentReduction = (variableIndexAndValueGrouping)i.next();
				myInternalCopy.getVariable(currentReduction.getVariableIndex())
					.addToCurrentDomain(currentReduction.getValue());

			}
		}


		if(level == null || level.equals(FC_LEVEL))
		{
			//run FC
			consistencyAlgorithm myFC = new binaryForwardCheckAll(myInternalCopy, null);
			//if it finds something stop
			if(runConsistencyLevel(FC_LEVEL, myFC))
			{
				return;
			}
			//if we didn't find anything then we want to keep going so we set level to null
			level = null;
		}


		//no hint was found
		hintVariables = null;
		errorConstraint = null;
		hintLevel = null;
		hintType = null;
		currentHintIndex = -1;
		return;
	}
	public boolean hasHint()
	{
		if(hintVariables == null)
		{
			return false;
		}
		return true;
	}
	
	public boolean foundError()
	{
		if (errorConstraint != null)
		{
			return true;
		}
		return false;
	}

//	public problemVariable getHintVariable() {
//		return hintVariable;
//	}

	//TODO: This code is very limiting to new constraints
	//TODO: THIS CODE IS PRETTY BAD ALL AROUND
	public problemConstraint getErrorConstraint() 
	{
		if(errorConstraint == null)
		{
			return null;
		}
		List scope = new LinkedList(errorConstraint.getScope());
		if(scope.size() == 2)
		{
			List key = new LinkedList();
			key.add(myOriginalProblem.getVariable(((problemVariable)scope.get(0)).getIndex()));
			key.add(myOriginalProblem.getVariable(((problemVariable)scope.get(1)).getIndex()));
			return myOriginalProblem.getConstraint(key);
		}
		else if(scope.size() == 9)
		{
			return myOriginalProblem.getNonBinaryIntensiveConstraint(((nonBinaryIntensiveConstraint)errorConstraint).getKey());
		}
		return null;
	}
	
	private boolean runConsistencyLevel(String currLevel, consistencyAlgorithm currAlg) throws InterruptedException
	{
		//if the algorithm runs successfully
		if(currAlg.runAlgorithm())
		{
			if(findHints(currLevel))
			{
				return true;
			}
		}
		else //there was an error
		{
			logError(currAlg, currLevel);
			return true;
		}
		return false;
	}
	
	//return false if there is an error
	//return true otherwise.
	private boolean runGACUnit(Collection gacSingletonHints, Collection gacVitalHints) throws InterruptedException
	{
		List myReductions = new LinkedList();
		myInternalCopy.registerDomainReductionListener(myReductions);

		int unitsWide = (int)(myInternalCopy.totalColumns/myInternalCopy.columnsPerUnit);
		int unitsHigh = (int)(myInternalCopy.totalLines/myInternalCopy.linesPerUnit);
		
		for(int row =1; row<=unitsHigh; row++)
		{
			for(int col =1; col<=unitsWide; col++)
			{
				consistencyAlgorithm myGAC = new nonBinaryRestrictedArcConsistency(myInternalCopy, null, "U"+row+","+col);
				//if there is an error stop
				if(!myGAC.runAlgorithm())
				{
					//unregister the listener
					myReductions.add("deleteme");
					myInternalCopy.unregisterDomainReductionList(myReductions);
					myReductions.remove("deleteme");
					
					logError(myGAC, SINGLE_GAC_LEVEL);
					return false;
				}
			}
		}

		//get the hints
		gacSingletonHints.addAll(getSingletons(myInternalCopy));
		gacVitalHints.addAll(getVitalLinks(myInternalCopy));
		
		//undo the reductions
		myReductions.add("deleteme");
		myInternalCopy.unregisterDomainReductionList(myReductions);
		myReductions.remove("deleteme");
		
		Iterator i = myReductions.iterator();
		while(i.hasNext())
		{
			variableIndexAndValueGrouping currentReduction = (variableIndexAndValueGrouping)i.next();
			myInternalCopy.getVariable(currentReduction.getVariableIndex())
				.addToCurrentDomain(currentReduction.getValue());
		}
		return true;
	}
	
	
	//return false if there is an error
	//return true otherwise.
	private boolean runGACLineCol(Collection gacSingletonHints, Collection gacVitalHints, String lineColType) throws InterruptedException
	{
		List myReductions = new LinkedList();
		myInternalCopy.registerDomainReductionListener(myReductions);
		
		int limit = 0;
		//run GAC on rows or cols
		if(lineColType.equals("L"))
		{
			limit = myInternalCopy.totalLines;
		}
		else if(lineColType.equals("C"))
		{
			limit = myInternalCopy.totalColumns;
		}
		for(int i =1; i<limit; i++)
		{
			consistencyAlgorithm myGAC = new nonBinaryRestrictedArcConsistency(myInternalCopy, null, lineColType+i);
			//if there is an error stop
			if(!myGAC.runAlgorithm())
			{
				//unregister the listener
				myReductions.add("deleteme");
				myInternalCopy.unregisterDomainReductionList(myReductions);
				myReductions.remove("deleteme");
				
				logError(myGAC, SINGLE_GAC_LEVEL);
				return false;
			}
		}

		//get the hints
		gacSingletonHints.addAll(getSingletons(myInternalCopy));
		gacVitalHints.addAll(getVitalLinks(myInternalCopy));
		
		//undo the reductions
		myReductions.add("deleteme");
		myInternalCopy.unregisterDomainReductionList(myReductions);
		myReductions.remove("deleteme");
		
		Iterator i = myReductions.iterator();
		while(i.hasNext())
		{
			variableIndexAndValueGrouping currentReduction = (variableIndexAndValueGrouping)i.next();
			myInternalCopy.getVariable(currentReduction.getVariableIndex())
				.addToCurrentDomain(currentReduction.getValue());
			
		}
		return true;
	}
	
	
	private void logError(consistencyAlgorithm myAlg, String currLevel)
	{
		hintVariables = null;
		errorConstraint = myAlg.getBrokenConstraint();
		hintLevel = currLevel;
		hintType = "Error";
		currentHintIndex = -2;
	}
	
//	private boolean checkSingletons(String currLevel, problemVariable currVariable)
//	{
//
//		if(!currVariable.isAssigned() && currVariable.getCurrentDomainSize() == 1)
//		{
//			List newHints = new LinkedList();
//			newHints.add(currVariable);
//			setPrivates(currLevel, "Singleton", newHints);
//			return true;
//		}
//		else return false;
//	}
//	
//	private boolean checkVitals(String currLevel, problemVariable currVariable)
//	{
//
//		if(!currVariable.isAssigned() && currVariable.getCurrentDomainSize() == 1)
//		{
//			List newHints = new LinkedList();
//			newHints.add(currVariable);
//			setPrivates(currLevel, "Vitals", newHints);
//			return true;
//		}
//		else return false;
//	}
	
	private boolean findHints(String currLevel)
	{
		List newHints;
		List switchHints;
		//if there are any singletons
		newHints = checkSingletons();

		if(newHints.isEmpty())
		{
			//make it the switchHints;
			switchHints = newHints;
			newHints = checkVitals();
			if(newHints.isEmpty())
			{
				return false;
			}
			setPrivates(currLevel, "Vital", newHints, switchHints);
			return true;
		}
		else
		{
			switchHints = checkVitals();

			setPrivates(currLevel, "Singleton", newHints, switchHints);
			return true;
		}
	}
	
	private List checkSingletons()
	{
		List newHints;
		
		newHints = new LinkedList(this.getSingletons(myInternalCopy));
		return newHints;
	}
	
	private List checkVitals()
	{
		List newHints;

		newHints = new LinkedList(this.getVitalLinks(myInternalCopy));
		return newHints;
	}
	
	private void setPrivates(String currLevel, String currType, List hints, List switchHints)
	{
		hintVariables = hints;
		switchVariables = switchHints;
		errorConstraint = null;
		hintLevel = currLevel;
		hintType = currType;
		currentHintIndex = 0;
		return;
	}
	
	private Collection getSingletons(constraintProblem myProblem)
	{
		List singletonVariables = new LinkedList();
		
		List problemVariables = new LinkedList(myProblem.getAllVariables());
		Iterator i = problemVariables.iterator();
		
		while(i.hasNext())
		{
			problemVariable currentVariable = (problemVariable)i.next();
			if(!currentVariable.isAssigned())
			{
				if(currentVariable.getCurrentDomainSize() == 1)
				{
					singletonVariables.add(currentVariable);
				}
			}
		}
		
		return singletonVariables;
	}
	
	private Collection getVitalLinks(constraintProblem myProblem)
	{
		List vitalLinkVariables = new LinkedList();
		
		Hashtable[] lineValueFrequency;
		Hashtable[] colValueFrequency;
		Hashtable[][] unitValueFrequency;
		//set up the hashtables
		lineValueFrequency = new Hashtable[myInternalCopy.totalLines+1];
		for(int i= 1; i <= myInternalCopy.totalLines; i++)
		{
			//lineValueFrequency[i].clear();
			lineValueFrequency[i]= new Hashtable();
		}
		
		colValueFrequency = new Hashtable[myInternalCopy.totalColumns+1];
		for(int i= 1; i <= myInternalCopy.totalColumns; i++)
		{
			colValueFrequency[i]= new Hashtable();
		}
		
		unitValueFrequency = new Hashtable[myInternalCopy.columnsPerUnit+1][myInternalCopy.linesPerUnit+1];
		for(int i= 1; i <= myInternalCopy.columnsPerUnit; i++)
		{
			for(int j = 1; j <= myInternalCopy.linesPerUnit; j++)
			{
				unitValueFrequency[i][j]= new Hashtable();				
			}
		}
		
		for(int colIndex= 1; colIndex <= myInternalCopy.totalColumns; colIndex++)
		{
			for(int lineIndex = 1; lineIndex <= myInternalCopy.totalLines; lineIndex++)
			{
				LinkedList valueList = new LinkedList(myInternalCopy.getVariable(colIndex + "," + lineIndex).getEntireDomain());
				while(!valueList.isEmpty())
				{
					String currentValue = (String)valueList.get(0);
					valueList.remove(0);
					
					//increment the number of times that value appears in the line
					if(!lineValueFrequency[lineIndex].containsKey(currentValue))
					{
						lineValueFrequency[lineIndex].put(
								currentValue,
								new Integer( 1 ) );
					}
					else
					{
						lineValueFrequency[lineIndex].put(
								currentValue,
								new Integer( ((Integer)lineValueFrequency[lineIndex].get(currentValue)).intValue() + 1 ) );
					}
					
					//increment the number of times that value appears in the column
					if(!colValueFrequency[colIndex].containsKey(currentValue))
					{
						colValueFrequency[colIndex].put(
								currentValue,
								new Integer( 1 ) );
					}
					else
					{
						colValueFrequency[colIndex].put(
								currentValue,
								new Integer( ((Integer)colValueFrequency[colIndex].get(currentValue)).intValue() + 1 ) );
					}
					
					//increment the number of times that value appears in an unit
					if(!unitValueFrequency
							[(int)(Math.floor((lineIndex-1)/myInternalCopy.linesPerUnit)) +1]
							 [(int)(Math.floor((colIndex-1)/myInternalCopy.columnsPerUnit)) +1]
							  .containsKey(currentValue))
					{
						unitValueFrequency
						[(int)(Math.floor((lineIndex-1)/myInternalCopy.linesPerUnit)) +1]
						 [(int)(Math.floor((colIndex-1)/myInternalCopy.columnsPerUnit)) +1]
						 .put(
								currentValue,
								new Integer( 1 ) );
					}
					else
					{
						unitValueFrequency
						[(int)(Math.floor((lineIndex-1)/myInternalCopy.linesPerUnit)) +1]
						 [(int)(Math.floor((colIndex-1)/myInternalCopy.columnsPerUnit)) +1]
						  .put(
								currentValue,
								new Integer( ((Integer)unitValueFrequency
										[(int)(Math.floor((lineIndex-1)/myInternalCopy.linesPerUnit)) +1]
										 [(int)(Math.floor((colIndex-1)/myInternalCopy.columnsPerUnit)) +1]
										  .get(currentValue)).intValue() + 1 ) );
					}
				}
			}
		}
		for(int xIndex = 1; xIndex <= myInternalCopy.totalLines; xIndex++)
		{
			for(int yIndex = 1; yIndex <= myInternalCopy.totalColumns; yIndex++)
			{
				if(!myInternalCopy.getVariable(yIndex+","+xIndex).isAssigned())
				{
					Iterator i = myInternalCopy.getVariable(yIndex+","+xIndex).getEntireDomain().iterator();
					while(i.hasNext())
					{
						String value = (String)i.next();
						//if it is the only variable in the unit, row, or column attempt to add it to the set
						if(  (unitValueFrequency
								[(int)(Math.floor((xIndex-1)/myInternalCopy.linesPerUnit)) +1]
								 [(int)(Math.floor((yIndex-1)/myInternalCopy.columnsPerUnit)) +1].containsKey(value) &&
								 ((Integer)(unitValueFrequency
									[(int)(Math.floor((xIndex-1)/myInternalCopy.linesPerUnit)) +1]
									 [(int)(Math.floor((yIndex-1)/myInternalCopy.columnsPerUnit)) +1].get(value))).intValue() == 1)
									||  (colValueFrequency[yIndex].containsKey(value) &&
											((Integer)(colValueFrequency[yIndex].get(value))).intValue() == 1)
											||  (lineValueFrequency[xIndex].containsKey(value) &&
													((Integer)(lineValueFrequency[xIndex].get(value))).intValue() == 1)  )
						{
							vitalLinkVariables.add(myInternalCopy.getVariable(yIndex + "," + xIndex));
							//don't check anymore values in this variable
							while(i.hasNext()){i.next();}
						}
					}
				}
			}
		}
		return(vitalLinkVariables);

	}

	public String getHintType() {
		return hintType;
	}

	public String getHintLevel() {
		return hintLevel;
	}

	
	//adds one to the hint index unless it = size -1 then it resets it to zero
	public void incrementHintIndex() {
		//handle the case of errors;
		if(hintVariables == null)
		{
			return;
		}
		if(this.currentHintIndex >= hintVariables.size()-1)
		{
			currentHintIndex = 0;
		}
		else
		{
			currentHintIndex++;
		}
	}

    public void decrementHintIndex() {
        //handle the case of errors;
		if(hintVariables == null)
		{
			return;
		}
		if(this.currentHintIndex <= 0)
		{
			currentHintIndex = hintVariables.size()-1;
		}
		else
		{
			currentHintIndex--;
		}
    }

	public int getCurrentHintIndex() {
		return currentHintIndex;
	}

	public int getHintVariablesSize() {
		if(hintVariables == null)
		{
			return -1;
		}
		return hintVariables.size();
	}
	
	public problemVariable getCurrentHintVariable()
	{
		problemVariable copyVar = (problemVariable)hintVariables.get(currentHintIndex);
		return myOriginalProblem.getVariable(copyVar.getIndex());
	}
	
	public void switchType()
	{
		if (hintType.equals("Error"))
		{
			return;
		}

		List temp = hintVariables;
		hintVariables = switchVariables;
		switchVariables = temp;
		if(hintType.equals("Vital"))
		{
			hintType = "Singelton";
		}
		else if(hintType.equals("Singleton"))
		{
			hintType = "Vital";
		}
		currentHintIndex = 0;
		return;


	}
}