/* --------------------------------------------------------------------

SolverApplet class

Copyright (c) 1996 by Christopher R. Waterson. All Rights Reserved.
Permission to use, copy, modify, and distribute this software
and its documentation for NON-COMMERCIAL purposes and without
fee is hereby granted provided that this copyright notice
appears in all copies.

File:		SolverApplet.java
Synopsis:	An eight-puzzle solver applet
Author:		Christopher R. Waterson <waterson@eecs.umich.edu>
Created:	27 January 1996
Updated:	Christopher R. Waterson <waterson@eecs.umich.edu>
Last Modified:	31 October 1996

-------------------------------------------------------------------- */

package eightpuzzle;

/**
 * A brute-force search engine to solve the eight puzzle.
 */

public class Solver
extends Thread {

	/**
	 * The applet that contains the solver
	 */

	SolverApplet m_containerApplet;


	/**
	 * Construct a new solver, passing in the container applet
	 */

	public
	Solver(SolverApplet containerApplet) {
		m_containerApplet = containerApplet;
	}


	/**
	 * Solve the eight puzzle
	 */

	public PuzzleNode
	solve(Puzzle puzzle) {

		// Create a queue to store the nodes on
		PriorityQueue queue = new PriorityQueue(new SolverQueueSorter());

		// Start with the root node as the puzzle that was
		// passed in to solve.
		PuzzleNode root = new PuzzleNode(puzzle);
		m_containerApplet.getSearchTreePanel().setRoot(root);

		// Push the first node onto the queue to get things rolling
		// and zero out the progress counter.
		queue.addElement(root);

		int numNodesExpanded = 0;

		// Keep iterating until the queue is empty.
		while (queue.hasMoreElements()) {

			// Pop the next node off the queue
			PuzzleNode node = (PuzzleNode) queue.removeTopElement();


			// Have we solved it?
			if (node.getPuzzle().isSolved()) {

				// Yep. Return the solution node.
				m_containerApplet.showStatus("Solved!");
				return node;
			}

			// Expand the current node
			node.expand();

			// And add each child to the queue, and do some
			// miscellaneous user interface stuff.

			for (int i = 0; i < node.getNumChildren(); ++i) {

				// Add the child to the queue
				PuzzleNode child = (PuzzleNode) node.getChild(i);

				queue.addElement(child);

				// Draw the new child on the search tree canvas
				m_containerApplet.getSearchTreePanel().add(child);

				// Indicate the additional nodes have been expanded
				++numNodesExpanded;
				m_containerApplet.showStatus(numNodesExpanded
					+ " nodes expanded...");
			}
		}

		// We didn't find a solution.
		return null;
	}



	/**
	 * Performs the solution discovered at the specified node
	 * by recursing back through the path used to reach the
	 * solution.
	 */

	private void
	doSolution(PuzzleNode node) {
		if (node.getParent() != null)
			doSolution((PuzzleNode) node.getParent());

		m_containerApplet.getPuzzleCanvas().move(node.getOperator());
	}



	/**
	 * The main hook into the Thread.
	 */

	public void
	run() {
		// Disable the container applet's user interface while we're
		// trying to solve the puzzle.
		m_containerApplet.enableUserInterface(false);

		// Get the puzzle from the container applet's puzzle canvas
		// and run it through the mill
		Puzzle puzzle = m_containerApplet.getPuzzleCanvas().getPuzzle();
		PuzzleNode solutionNode = solve(puzzle);

		// If we were able to find a solution, execute it!
		if (solutionNode != null) doSolution(solutionNode);

		// Re-enable the user interface
		m_containerApplet.enableUserInterface(true);
	}
}



/**
 * A utility class for sorting nodes in the closed list.
 */

class SolverQueueSorter
implements Sorter {

	/**
	 * Compare two PuzzleNode objects and return true if the left should
	 * be expanded before the right.
	 */

	public boolean
	greaterThan(Object left, Object right) {
		PuzzleNode l = (PuzzleNode) left;
		PuzzleNode r = (PuzzleNode) right;

		// Remember that we want to expand the node with the
		// CHEAPEST cost first.
		return l.getCost() < r.getCost();
	}


	/**
	 * Compare two PuzzleNode objects and return true if the right should
	 * be expanded before the left.
	 */

	public boolean
	lessThan(Object left, Object right) {
		PuzzleNode l = (PuzzleNode) left;
		PuzzleNode r = (PuzzleNode) right;

		// Remember that we want to expand the node with the
		// CHEAPEST cost first.
		return l.getCost() > r.getCost();
	}
}