import java.awt.Point;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;

public class Maze {
	/**
	 * This variable stores essentially all the data for the maze.
	 * A 4 x 4 maze would look like this:
	 *  _|_|_|_
	 *  _|_|_|_
	 *  _|_|_|_
	 *   | | |
	 *  Where an underscore represents a horizontal wall, and a pipe
	 *  represents a vertical wall. This variable will only use O(r*c)
	 *  memory. Every even number row in the variable will represent the vertical
	 *  walls. Since there will only be cols-1 vertical walls per row, the first
	 *  column on every even row should be ignored. The same thing also goes for the
	 *  last row's horizontal walls. There will only be a maximum of rows-1 horizontal walls
	 *  per column, so the last row in the variable simply should not be read.
	 *  Because of this, the variable is actually initialized with 2*r-1 rows.
	 *
	 *  Basically the generate maze method will fill up this variable and the print one will
	 *  display it in text form.
	 *
	 *  OMG JOSH LOOK HERE PL0x! ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~< look
	 *  Some useful tips for accessing from the "walls" array:
	 *
	 *  Say you have a r x c grid that represents the blocks in the maze...
	 *  to get a boolean of whether or not there is a wall to its...
	 *  right  -> walls[2r][c+1];
	 *  left   -> walls[2r][c];
	 *  top	   -> walls[2r-1][c];
	 *  bottom -> walls[2r+1][c];
	 *
	 *  Of course those will go out of bounds, so you'll have to be careful
	 *  but that should come in handy when trying to display the maze.
	 */
	public boolean [][] walls;


	public Maze(int r, int c){
		walls = new boolean [(2*r)-1][c];
		for(int row= 0; row<walls.length; row++)
			for(int col = 0; col < walls[row].length; col++)
				walls[row][col] = true;
	}
	/**
	 * This method was only used for testing the print method
	 * @param maze
	 */
	public void setMaze(boolean[][] maze){
		walls = maze;
	}
	/**
	 * Be this fills the walls array by breaking walls down for the maze.
	 * It's complicated but I bet you can figure it out. In addition, the
	 * ends arrayList correctly contains the list of all endpoints (in x=r,y=c form) when
	 * the depth first search is complete. It is currently set to just print
	 * the ends afterwards however that could quickly be changed.
	 */
	public void generateMaze(){
		if(walls==null)
			return;
		int r = (walls.length+1)/2;
		int c = walls[0].length;


		int[][] around = {{-1,0,0,1},
				{0,-1,1,0}};

		int numGrids = r*c;

		boolean [][] visited = new boolean[r][c];
		LinkedList<Point []> pointsToVisit = new LinkedList<Point []>();
		LinkedList<Point> surrounding = new LinkedList<Point>();
		ArrayList<Point> ends = new ArrayList<Point>();

		pointsToVisit.add(new Point [] {new Point(0,0),null});

		while(numGrids>0){
			Point [] toCheck = pointsToVisit.removeFirst();
			if(visited[toCheck[0].x][toCheck[0].y]){

			}
			else{
				if(toCheck[1]!=null){
					//update the walls array:
					if(toCheck[1].y>toCheck[0].y){ //right vert wall
						walls[2*toCheck[0].x][toCheck[0].y+1] = false;
					}
					else if(toCheck[1].y<toCheck[0].y){ //left vert wall
						walls[2*toCheck[0].x][toCheck[0].y] = false;
					}
					else if(toCheck[1].x<toCheck[0].x){//horizontal wall above
						walls[2*toCheck[0].x-1][toCheck[0].y] = false;
					}
					else if(toCheck[1].x>toCheck[0].x){//horizontal wall below
						walls[2*toCheck[0].x+1][toCheck[0].y] = false;
					}
				}
				visited[toCheck[0].x][toCheck[0].y] = true;
				numGrids--;
				for(int i = 0; i < around[0].length; i++){
					if(toCheck[0].x+around[0][i]>=0 && toCheck[0].x+around[0][i]<r //makes sure the point to check is in bounds
							&& toCheck[0].y+around[1][i]>=0 && toCheck[0].y+around[1][i]<c //makes sure the point to check is in bounds
							&&	!visited[toCheck[0].x+around[0][i]][toCheck[0].y+around[1][i]]){
						surrounding.add(new Point(toCheck[0].x+around[0][i],toCheck[0].y+around[1][i]));
					}
				}
				if(surrounding.size()>0){
					Collections.shuffle(surrounding);
					pointsToVisit.addFirst(new Point [] {surrounding.removeFirst(),toCheck[0]});
					while(!surrounding.isEmpty()){
						pointsToVisit.addLast(new Point [] {surrounding.removeLast(),toCheck[0]});
					}
				}
				else
					ends.add(toCheck[0]);
			}
		}
		System.out.println(ends);
	}
	/**
	 * Please excuse the extremely shitty string concatenation everywhere.
	 * Run it and the code will make a lot more sense.
	 * @return
	 */
	public String printMaze(){
		if(walls==null)
			return "Empty Maze";
		String out = "";
		for(int i = 0; i < walls[0].length; i++){
			out+="**";
		}
		out+="*\n";
		for(int r = 0; r < walls.length; r+=2){
			out+="*";
			if(r==walls.length-1)
				out+=" ";
			for(int c = 0; c < walls[r].length; c++){
				if(r!=walls.length-1){ //vertical walls
					if(c!=0){
						if(walls[r][c])
							out+="|";
						else
							out+=" ";
					}
					if(walls[r+1][c])
						out+="_";
					else
						out+=" ";
				}
				else{
					if(c!=0){
						if(walls[r][c])
							out+="| ";
						else
							out+="  ";
					}
				}
			}
			out+="*\n";
		}
		for(int i = 0; i < walls[0].length; i++){
			out+="**";
		}
		out+="*";
		return out;
	}
}