// Maze class - provided for HW#11
// login(s):

class Maze {

	// MazeCell - an inner class supporting Maze
	//
	// The following convention is used in mazes:
	// Walls are represented by '*'
	// Empty area is represented by the blank symbol ' '
	// Other characters are used for other things!


	class MazeCell {

		private int row; // The row at which this cell is located
		private int col; // The col at which this cell is located
		private char contents; // Each cell has contents (a char)
		private boolean visited; // A cell can be marked as visited.
		private MazeCell parent; // parent is where we came from!

		// Constructor of the MazeElement at row, col, with contents c
		// "visited" is set to false, and "parent" is set to null
		private MazeCell(int row, int col, char c) {
			this.row = row; // this is required to avoid name confusion!
			this.col = col; // ditto
			this.contents = c;
			this.visited = false; // we haven't been here yet...
			this.parent = null; // ... so we have no parent yet
		}

		// toString returns the string representation of a MazeElement
		public String toString() {
			return "[" + row + "," + col + "," + contents + "]";
		}

		private boolean isWall() {
			return this.contents == '*';
		}

		private boolean isOpen() {
			return this.contents == ' ' || this.contents == 'D';
		}

		/*
		 * methods to write for Spampede...
		 */
		public int getRow() {
			return this.row;
		}

		public int getCol() {
			return this.col;
		}

		public char getContents() {
			return this.contents;
		}

		public void setContents(char newcontents) {
			this.contents = newcontents;
		}

	}

	/*
	 * data member for the Maze class... a 2d rectangular array of MazeCells
	 */
	protected MazeCell[][] maze; // this is the maze!

	/*
	 * method: constructor input: none output: a maze containing ththe data in
	 * mazeStrings, below
	 */
	protected Maze(String[] mazeStrings) {
		// TODO
	}

	// the findMazeCell method takes the maze and a char token
	// (either 'S' or 'D') and returns the MazeElement containing the
	// location of that token in the maze.
	// PROVIDED METHOD. NO NEED TO ALTER.
	public MazeCell findMazeCell(char charToFind) {
		for (int r = 0; r < maze.length; r++)
			for (int c = 0; c < maze[r].length; c++)
				if (maze[r][c].contents == charToFind)
					return maze[r][c];
		return null; // Error in finding the itemToFind: it's not there!
	}

	/*
	 * method: BFS input: two maze cells output: none; prints the path
	 * 
	 * This is just for reference in writing multiBFS
	 */
	public void BFS(MazeCell start, MazeCell destination) {
		// System.out.println("Breadth-first search\n");
		Queue cellsToVisit = new Queue();

		start.visited = true;
		cellsToVisit.enqueue(start);

		while (!cellsToVisit.isEmpty()) {
			MazeCell current = (MazeCell) cellsToVisit.dequeue();

			if (current == destination) // have we reached the goal?
			{
				MazeCell pathElement = current.parent;
				while (pathElement != start && pathElement != null) {
					pathElement.contents = 'o';
					pathElement = pathElement.parent;
				}
				System.out.println("Maze is\n" + this);
				return; // done!
			}

			/*
			 * This enqueueing of the neighbors could be an obvious helper
			 * method (hint hint)
			 */
			// enqueue neighbors if unmarked and not walls
			int currentRow = current.row;
			int currentCol = current.col;
			MazeCell northNeighbor = maze[(currentRow - 1)][currentCol];
			MazeCell southNeighbor = maze[(currentRow + 1)][currentCol];
			MazeCell eastNeighbor = maze[currentRow][(currentCol + 1)];
			MazeCell westNeighbor = maze[currentRow][(currentCol - 1)];

			/*
			 * all the neighbors in an array
			 */
			MazeCell[] NBRS = { southNeighbor, eastNeighbor, westNeighbor,
					northNeighbor };

			for (MazeCell mc : NBRS) {
				if (!mc.visited && !mc.isWall()) {
					mc.visited = true;
					mc.parent = current;
					cellsToVisit.enqueue(mc);
				}
			}
		} // end of while cellsToVisit is not empty
		System.out.println("\nMaze not solvable!\n");
	}

	/*
	 * method: multiBFS input: a starting cell and a char to seek output: the
	 * maze cell that is BESIDE START and NEXT ALONG the path to the nearest
	 * destination!
	 * 
	 * optional: printing the path to the goal if you do, BE SURE TO CLEAR
	 * _EVERYTHING_ OUT! before returning...
	 * 
	 * if there is no path, this method should return an open MazeCell that is
	 * NEXT TO START
	 * 
	 * if there is no open MazeCell that is NEXT TO START, this method should
	 * return any MazeCell that is next to start (and it will crash)
	 */
	protected MazeCell multiBFS(MazeCell start, char destination) {
		; // TODO - implement multiBFS
		return null; // need to return an appropriate MazeCell...
	}

	/*
	 * toString converts a maze to a string for printing
	 */
	public String toString() {
		String result = "\n";
		for (int r = 0; r < maze.length; ++r) {
			for (int c = 0; c < maze[r].length; ++c)
				result += maze[r][c].contents;
			result += "\n";
		}
		result += "\n";
		return result;
	}

	// PROVIDED METHOD. NO NEED TO ALTER.
	public static void main(String args[]) {
		String[] mazeStrings = {
				"**************************************************",
				"*PS D                                            *",
				"*                                                *",
				"*                                                *",
				"*                                                *",
				"*                                                *",
				"*                                                *",
				"*                                                *",
				"*                                                *",
				"*                                                *",
				"*                                                *",
				"*                                                *",
				"*                       **                       *",
				"*                       **                       *",
				"*                       **                       *",
				"*                       **                       *",
				"*                                                *",
				"*                                                *",
				"*                                                *",
				"*                                                *",
				"*                                                *",
				"*                                                *",
				"*                                                *",
				"*                                                *",
				"*                                                *",
				"*                                        D       *",
				"*                                                *",
				"*                                                *",
				"*                                                *",
				"**************************************************" };

		Maze M = new Maze(mazeStrings);

	}

}