import java.util.*;

public class Maze implements Application {

    	protected static final byte WALL = 0;
    	protected static final byte CORRIDOR = 1;
    	protected static final byte PATH = 9;
    	protected static final byte DEAD_END = 2;

    	protected Position finish;

    	protected byte[ ][ ] grid;


    	/**
         * Initializes this Maze object.
         *
         * @param grid a two-dimensional array of bytes to hold the maze.
         * @param finish the Position that signifies the end of the maze.
         */    	
        public Maze (byte[ ][ ] grid, Position finish) 
	{
        	this.finish = finish;
        	this.grid = grid;
    	} // 2-parameter constructor


	/**
         * Determines if a given position is legal and not a dead end.
         *
         * @param pos - the given position.
         *
         * @return true if pos is a legal position and not a dead end.
         */    	
        public boolean isOK (Position pos)
	{
        	return pos.getRow() >= 0 && pos.getRow() < grid.length &&
                		pos.getColumn() >= 0 && pos.getColumn() < grid [0].length &&
                		grid [pos.getRow()][pos.getColumn()] == CORRIDOR;            		
    	} // method isOK


	/**
         * Indicates that a given position is possibly on a path to a goal.
         *
         * @param pos the position that has been marked as possibly being on a path
         *            to a goal.
         */
    	public void markAsPossible (Position pos)
	{
        	grid [pos.getRow ()][pos.getColumn ()] = PATH;
    	} // method markAsPossible


	/**
         * Indicates whether a given position is a goal position.
         *
         * @param pos the position that may or may not be a goal position.
         *
         * @return true if pos is a goal position; false otherwise.
         */	
    	public boolean isGoal (Position pos)
	{
        	return pos.getRow() == finish.getRow() && 
		pos.getColumn() == finish.getColumn();
    	} // method isGoal


	/**
         * Indicates that a given position is not on any path to a goal position.
         *
         * @param pos the position that has been marked as not being on any path to a
         *            goal position.
         */
    	public void markAsDeadEnd (Position pos)
	{
        	grid [pos.getRow()][pos.getColumn()] = DEAD_END;
    	} // method markAsDeadEnd


	/**
         * Converts this Application object into a String object.
         *
         * @return the String representation of this Application object.
         */
    	public String toString () 
	{
         	String result = "\n";

         	for (int row = 0; row < grid.length; row++) 
		{
              		for (int column = 0; column < grid [0].length; column++)
                 		result += String.valueOf (grid [row][column]) + ' ';
             		result += "\n";
         	} // for row = 0
         	return result;
     	} // method toString


	/**
         * Produces an Iterator object, over elements of type Position, that starts at a given 
         * position.
	 *
         * @param pos - the position the Iterator object starts at.
         *
         * @return the Iterator object.
         */
     	public Iterator<Position> iterator (Position pos) 
	{
         	return new MazeIterator (pos);
     	} // method iterator


	protected class MazeIterator implements Iterator<Position> 
	{
		protected static final int MAX_MOVES = 4;

    		protected int row,
        		      column,
        		      count;

		/**
                 * Initializes this MazeIterator object to start at a given position.
         	 *
         	 * @param pos the position the Iterator objects starts at.
         	 */
    		public MazeIterator (Position pos) 
		{
        		row = pos.getRow();
        		column = pos.getColumn();
			count = 0;
    		} // constructor


		/**
         	 * Determines if this MazeIterator object can advance to another
         	 * position.
         	 *
         	 * @return true if this MazeIterator object can advance; false otherwise.
         	 */
    		public boolean hasNext () 
		{
        		return count < MAX_MOVES;
    		} // method hasNext


		/**
         	 * Advances this MazeIterator object to the next position.
         	 *
         	 * @return the position advanced to.
         	 */		
    		public Position next () 
		{
        		Position nextPosition = new Position();
            	  	switch (count++) 
			{
                		case 0: nextPosition = new Position (row-1, column); // north
                        		break;
                		case 1: nextPosition = new Position (row, column+1); // east
                        		break;
                		case 2: nextPosition = new Position (row+1, column); // south
                        		  break;
                		case 3: nextPosition = new Position (row, column-1); // west
            		} // switch;
            		return nextPosition;
    		} // method next

		
    		public void remove () 
		{ 
			// removal is illegal for a MazeIterator object
			throw new UnsupportedOperationException(); 
		} // method remove

	} // class MazeIterator

} // class Maze