/* Search.java */

import DataStructures.*;
import Exceptions.*;

/** Defines the main application class, Search. Search prompts the user 
 *  for a maze and determines whether or not there is a solution
 *  path through it. All mazes are assumed to have a starting square
 *  in the upper-left corner of the maze, and a finishing
 *  square in the lower-right corner.
 */
public class Search {

  /**
   *  Reads in a maze from the user and determines
   *  whether or not there exists a path through
   *  the given maze.
   */
  public static void main( String[] argv ) throws java.io.IOException {
    // initialization
    Stack route = new StackLi();    // stores points to be searched
    Maze  maze = new Maze();

    System.out.println( "\nMaze: " );
    System.out.println( maze.toString() );

    // begin search for a path
    Point currentPoint = maze.startPoint();

    if( maze.validPoint(currentPoint) ) {
      maze.clearMarks();
      maze.markPoint(currentPoint);
      route.push(currentPoint);

      while (!route.isEmpty()) {
	try {
	  currentPoint = (Point) route.top();
	  route.pop();
	  if (currentPoint.equals(maze.endPoint())) {
	    break;
	  }
	} catch (Underflow uf) {
	  System.err.println("Program error: stack underflow.");
	}
	int dir;
	for( dir  = Direction.NORTH;
	     dir <= Direction.SOUTH;
	     dir  = Direction.nextDir(dir) ) {
	  Point nextPoint = currentPoint.move(dir);
	  if (maze.validPoint(nextPoint) && !maze.pointMarked(nextPoint)) {
	    maze.markPoint(nextPoint);
	    route.push(nextPoint);
	  }
	}
      }
    }

    if (currentPoint.equals(maze.endPoint())) {
      System.out.println( "Path found through maze" );
    } else {
      System.out.println( "No path through maze" );
    }
  }
}