/**
 *
 * Copyright (C) 2003 Uday Bondhugula
 *
 * This code is available under the GNU GPL version 2. See the file LICENSE
 * for terms and conditions.
 *
 * This class contains methods to solve the Rubik's cube using an IDA*
 * algorithm.
 *
 */

import java.util.*;
import java.applet.Applet;

public class CubeSolver	extends Thread implements Comparator{
	private final static int TOP_CLOCKWISE = 1;
	private final static int TOP_ANTICLOCKWISE = 2;
	private final static int DOWN_CLOCKWISE = 3;
	private final static int DOWN_ANTICLOCKWISE = 4;
	private final static int LEFT_CLOCKWISE = 5;
	private final static int LEFT_ANTICLOCKWISE = 6;
	private final static int RIGHT_CLOCKWISE = 7;
	private final static int RIGHT_ANTICLOCKWISE = 8;
	private final static int FRONT_CLOCKWISE = 9;
	private final static int FRONT_ANTICLOCKWISE = 10;
	private final static int BACK_CLOCKWISE = 11;
	private final static int BACK_ANTICLOCKWISE = 12;
	private final static String [] move = new String[13];

	Cube cube;
	RubiksCubeApplet applet;
	HashMap OPEN, CLOSED;
	TreeSet openPriorityQ;
	Node startNode;
		
	boolean stop = false;
	long startTime;

	CubeSolver(Cube cube, RubiksCubeApplet applet)	{
		// use the IDA* algo to solve the cube
		this.cube = cube;
		this.applet = applet;
		setPriority(Thread.MAX_PRIORITY);
		applet.logBox.setText("");
		applet.log("\nStarted thread for IDA* algo with maximum priority..");
		applet.log("Computing, please wait...");
		startTime = System.currentTimeMillis();
		start();
		
	}

	public static void initialize()	{
		move[TOP_CLOCKWISE] = "T";
		move[TOP_ANTICLOCKWISE] = "T'";
		move[DOWN_CLOCKWISE] = "D";
		move[DOWN_ANTICLOCKWISE] = "D'";
		move[LEFT_CLOCKWISE] = "L";
		move[LEFT_ANTICLOCKWISE] = "L'";
		move[RIGHT_CLOCKWISE] = "R";
		move[RIGHT_ANTICLOCKWISE] = "R'";
		move[FRONT_CLOCKWISE] = "F";
		move[FRONT_ANTICLOCKWISE] = "F'";
		move[BACK_CLOCKWISE] = "B";
		move[BACK_ANTICLOCKWISE] = "B'";
	}
			
		

	// start the IDA* algo to solve the cube in its own thread
	public void run() {
		//initialize OPEN with the start node and CLOSED empty

		float THRESHOLD = 5;

		while (!stop)	{	// threshhod value changes every iteration in this while loop
			OPEN = new HashMap();
			CLOSED = new HashMap();

			openPriorityQ = new TreeSet(this);

			startNode = new Node();
			startNode.f = startNode.h = Heuristics.heur(cube);
		        startNode.g = 0;
			startNode.parent = null;
			startNode.cube = cube;
			startNode.depth = 0;
			OPEN.put(startNode.cube, startNode);
			openPriorityQ.add(startNode);
			float min_exceed = 1000;	
			while (!stop)	{
				//System.out.println("Size of OPEN: "+ OPEN.size());
				if (OPEN.isEmpty())	{	// in the first iteration OPEN has start node
					System.out.println("Search failed with current threshold");
					THRESHOLD += min_exceed;
					System.out.println("Increasing threshold by " + min_exceed);
					//applet.log("Increasing threshold by "+min_exceed+" to "+ THRESHOLD);
					break;
				}
			
				Node BESTNODE = (Node)openPriorityQ.first();
				//System.out.println("BESTNODE selected at depth " + BESTNODE.depth + " with f value " + BESTNODE.f);
				//applet.log("BESTNODE selected at depth " + BESTNODE.depth + " with f value " + BESTNODE.f);
				openPriorityQ.remove(BESTNODE);
				OPEN.remove(BESTNODE.cube);
				CLOSED.put(BESTNODE.cube, BESTNODE);

				if(BESTNODE.isGoalNode())
				{
					showSolution(BESTNODE);
					return;
				}
				Node [] SUCC = new Node[12];
				movegen(BESTNODE, SUCC);
	
				for (int i = 0; i < SUCC.length; i++)	{
					if (BESTNODE.move != -1)	{
						int notAllowedMove;	// avoid duplicate states
						notAllowedMove= BESTNODE.move%2==0?BESTNODE.move-1:BESTNODE.move+1;
						if (notAllowedMove == SUCC[i].move)	continue;
					}
				
					SUCC[i].h = Heuristics.heur(SUCC[i].cube);
					//cost gives the cost of getting from bestnode to successor
					SUCC[i].g = BESTNODE.g + 1;

					if(OPEN.containsKey(SUCC[i].cube))
					{			
						//successor already in open
						System.out.println("already in open");
						Node OLD = (Node)OPEN.get(SUCC[i].cube);
						if(SUCC[i].g < OLD.g)
						{	
							OLD.g = SUCC[i].g;
							OLD.f = OLD.g + OLD.h;
							OLD.parent = BESTNODE;
							OLD.depth = SUCC[i].depth;
						}
						continue;
					}

					if (CLOSED.containsKey(SUCC[i].cube))	{
						// successor in CLOSED
						System.out.println("already in closed");
						Node OLD = (Node)CLOSED.get(SUCC[i].cube);
						if(SUCC[i].g < OLD.g)
						{	
							OLD.g = SUCC[i].g;
							OLD.f = OLD.g + 1;
							OLD.parent = BESTNODE;
							OLD.depth = SUCC[i].depth;
							updateSuccessors_DFS(OLD);
						}
						continue;
					}
					
					// not in open and not in closed
					
					SUCC[i].f = SUCC[i].g + SUCC[i].h;
					if (SUCC[i].f > THRESHOLD)	{	
						// throw away the successor
						if (SUCC[i].f - THRESHOLD < min_exceed)
							min_exceed = SUCC[i].f - THRESHOLD;
					}
					else {
						SUCC[i].parent = BESTNODE;
						BESTNODE.successors.add(SUCC[i]);
						OPEN.put(SUCC[i].cube, SUCC[i]);
						openPriorityQ.add(SUCC[i]);
					}
				}
	/*			Iterator itr = OPEN.keySet().iterator();
				System.out.println("Open contains ");
				
				while (itr.hasNext())	{
					Cube key = (Cube)itr.next();
					System.out.print(((Node)OPEN.get(key)).f + ":"+ ((Node)OPEN.get(key)).depth + "  ");
				}
				System.out.println("");

				System.out.println("Q contains");
				itr = openPriorityQ.iterator();
				while (itr.hasNext())	{
					Node node = (Node)itr.next();
					System.out.print(node.f + ":"+ node.depth + "  ");
				}
				System.out.println("");*/
				
			}
		}
	}

	public void updateSuccessors_DFS(Node n)	{
		applet.log("Doing DFS on closed node");
		Iterator itr = n.successors.iterator();
		while (itr.hasNext())	{
			Node succ = (Node)itr.next();
			if (!succ.parent.equals(n))	{
				if (succ.g > n.g + 1)	{
					succ.g = n.g + 1;
					succ.f = succ.h + succ.g;
					succ.parent = n;
					succ.depth = n.depth+1;
					updateSuccessors_DFS(succ);
				}
			}
			else updateSuccessors_DFS(succ);
		}
	}

	

	public void movegen(Node n, Node [] successors)	{
		Cube cube = n.cube;
		int i;
		for (i = 0; i < 12; i++)	{
			successors[i] = new Node();
			successors[i].depth = n.depth + 1;
		}

		
		i = 0;
		// TOP CLOCKWISE 
		successors[i].cube = Cube.copy(cube);
		successors[i].cube.rotate(Cubelet.AXIS_Y, -1, 2, false);
		//applet.drawCube(successors[i].cube);
		successors[i++].move = TOP_CLOCKWISE;

		// TOP ANTICLOCKWISE
		successors[i].cube = Cube.copy(cube);
		successors[i].cube.rotate(Cubelet.AXIS_Y, 1, 2, false);
		//applet.drawCube(successors[i].cube);
		successors[i++].move = TOP_ANTICLOCKWISE;	
		

		// DOWN CLOCKWISE
		successors[i].cube = Cube.copy(cube);
		successors[i].cube.rotate(Cubelet.AXIS_Y, 1, 0, false);
		//applet.drawCube(successors[i].cube);
		successors[i++].move = DOWN_CLOCKWISE;

		
		//DOWN ANTICLOCKWISE
		successors[i].cube = Cube.copy(cube);
		successors[i].cube.rotate(Cubelet.AXIS_Y, -1, 0, false);
		//applet.drawCube(successors[i].cube);
		successors[i++].move = DOWN_ANTICLOCKWISE;

		//LEFT_CLOCKWISE
		successors[i].cube = Cube.copy(cube);
		successors[i].cube.rotate(Cubelet.AXIS_Z, -1, 2, false);
		successors[i++].move = LEFT_CLOCKWISE;
		
		//LEFT_ANTICLOCKWISE
		successors[i].cube = Cube.copy(cube);
		successors[i].cube.rotate(Cubelet.AXIS_Z, 1, 2, false);
		successors[i++].move = LEFT_ANTICLOCKWISE;
		

		//RIGHT_CLOCKWISE
		successors[i].cube = Cube.copy(cube);
		successors[i].cube.rotate(Cubelet.AXIS_Z, 1, 0, false);
		successors[i++].move = RIGHT_CLOCKWISE;
		
		//RIGHT_ANTICLOCKWISE
		successors[i].cube = Cube.copy(cube);
		successors[i].cube.rotate(Cubelet.AXIS_Z, -1, 0, false);
		successors[i++].move = RIGHT_ANTICLOCKWISE;
		
		//FRONT_CLOCKWISE
		successors[i].cube = Cube.copy(cube);
		successors[i].cube.rotate(Cubelet.AXIS_X, -1, 2, false);
		successors[i++].move = FRONT_CLOCKWISE;
		
		//FRONT_ANTICLOCKWISE
		successors[i].cube = Cube.copy(cube);
		successors[i].cube.rotate(Cubelet.AXIS_X, 1, 2, false);
		successors[i++].move = FRONT_ANTICLOCKWISE;
		
		//BACK_CLOCKWISE
		successors[i].cube = Cube.copy(cube);
		successors[i].cube.rotate(Cubelet.AXIS_X, 1, 0, false);
		successors[i++].move = BACK_CLOCKWISE;
		
		//BACK_ANTICLOCKWISE
		successors[i].cube = Cube.copy(cube);
		successors[i].cube.rotate(Cubelet.AXIS_X, -1, 0, false);
		successors[i++].move = BACK_ANTICLOCKWISE;

	}
		

	public int compare(Object o1, Object o2)	{
		//System.out.println("Calling compare" + o1.getClass().getName()+ "  " + o2.getClass().getName());
		if ((Node)o1 == (Node)o2)	return 0;
		if (((Node)o1).f > ((Node)o2).f)	return 1;
		else return -1;
	}
	
	public boolean equals(Object o1)	{
		//System.out.println("Calling equals");
		return super.equals(o1);
	}

	public void reconstructPath(Node goalNode, Cube [] solution)	{
		solution[goalNode.depth] = goalNode.cube;
		Node currentNode = goalNode.parent;
		int i = goalNode.depth - 1;
		while (currentNode != null)	{
			solution[i--] = currentNode.cube;
			currentNode = currentNode.parent;
		}
	}

	public void showSolution(Node BESTNODE)	{
		applet.log("Size of OPEN is " + OPEN.size());
		applet.log("Size of CLOSED is " + CLOSED.size());
		applet.log("Total no. of nodes generated is " + (OPEN.size() + CLOSED.size()));
		applet.log("Total time taken: " + (System.currentTimeMillis() - startTime)/(float)1000+" seconds");
		applet.log("Search Succeeded at depth " + BESTNODE.depth);
		applet.log("Goal found.................");
		applet.showStatus("Cube solved by IDA* algo. !!!");
		Cube [] solution = new Cube[BESTNODE.depth+1];
		// reconstruct steps from goal node
		reconstructPath(BESTNODE, solution);
		applet.log("Solution length: " + (solution.length - 1) +" moves");
		String movesList = "";
		Node tempNode = BESTNODE;
		while (tempNode.parent != null)	{
			movesList = move[tempNode.move] + movesList;
			tempNode = tempNode.parent;
		}
		applet.log("Solution sequence: " + movesList);
		applet.displaySolution(solution);
	}
}


/*	
class Pair{
	float f;
	Cube cube;

	Pair(float f, Cube cube)	{
		this.f = f;
		this.cube = cube;
	}
}*/

			/*if (depth == 2)	{
				for (int i = 0; i < SUCC.length; i++)	{
				try{
					System.out.println("Drawing");
					applet.drawCube(solution[i-1]);
					Thread.sleep(4000);
				}catch (InterruptedException e)	{System.out.println(e);}

			}
			}*/