import java.util.ArrayList;


public class MazeNoSolver {
	Cell[][] cells ;
	int N ;
	
	public MazeNoSolver(int inN) 
	{
		N = inN ;
		double interval = 1.0 / N ;
		double halfInt = interval / 2 ;
		
		cells = new Cell[N][N] ;
		for (int i = 0 ; i < N ; i++)
			for (int j = 0 ; j < N ; j++)
				cells[i][j] = new Cell(i,j,i*interval+halfInt,j*interval+halfInt, halfInt) ;
	}
	
	public Cell getCell(int i, int j)
	{
		return( cells[i][j] ) ;
	}
	
	public int getN() { return N;}
	
	public void printMazeNoSolver()
	{
		System.out.println("") ;
		for (int i = 0 ; i < N ; i++)
			for (int j = 0 ; j < N ; j++)
				getCell(i,j).printTerse() ;
		
	}
	
	public void printMazeNoSolverOneZero()
	{
		System.out.println("") ;
		for (int i = 0 ; i < N ; i++)
			for (int j = 0 ; j < N ; j++)
				getCell(i,j).printTerseOneZero() ;
		
	}
	
	
	public void draw()
	{
		
		StdDraw.setPenColor(StdDraw.BLACK) ;
		StdDraw.setPenRadius(0.005) ;
		for (int i = 0 ; i < N ; i++)
			for (int j = 0 ; j < N ; j++)
				cells[i][j].draw();
		StdDraw.setPenRadius(0.002) ;
	}
	
	
	public void makePath()
	{
		
		// clear visits of MazeNoSolver
		for (int i = 0 ; i < N ;i++)
			for (int j =0 ; j < N ; j++)
				getCell(i,j).setVisited(false) ;
	
		
		// ArrayList<Point> points = new ArrayList<Point>() ;
		Stack<Cell> cellStack = new Stack<Cell>() ;
		
		// algorithm suggest chosing random start, I chose middle
		Point p1 = new Point(N/2,N/2) ;
		Cell currentCell = getCell(0,0);
		Cell newCell ;
		
		int numCellsVisited = 1 ; 
		// points.add(p1) ;
		
		while (numCellsVisited < N*N)
		{
			// pick a random neighbor cell that has all walls up
			
			
			
			Cell neighbors[] = new Cell[4] ;
			for (int i = 0 ; i < 4 ; i++)
				neighbors[i] = null ;
			
			int i = currentCell.getI();
			int j = currentCell.getJ() ;
			
			if (i < N-1) neighbors[0] = getCell(i+1,j) ;
			if (j < N-1) neighbors[1] = getCell(i,j+1) ;
			if (i > 0) neighbors[2] = getCell(i-1,j) ;
			if (j > 0) neighbors[3] = getCell(i,j-1) ;
			
			int numChoices = 0 ;
			for (int k = 0 ; k < 4 ; k++)
				if ( (neighbors[k] != null) && (neighbors[k].numWallsUp() == 4) )
					numChoices++ ;
			
			if (numChoices == 0)  
			{
				if (!cellStack.isEmpty())
				{
					currentCell = cellStack.pop();
					
				}
				else
				{
					System.out.println("trying to pop from empty stack") ;
					System.out.println("numVisted = " + numCellsVisited) ;
					this.draw();
					System.exit(1) ;
				}
			}
			else
			{
				
				newCell = null ;
				int rNum = (int) Math.floor( Math.random() * 4 );
				
				// randomly chose one of the 4 neigbors, if it exists and has
				//  all 4 walls up, it has not been visited yet, so make it the new cell
				if ( neighbors[(rNum+0)%4] != null && neighbors[ rNum % 4].numWallsUp() == 4)
					newCell = neighbors[ rNum %4] ;
				else if ( neighbors[(rNum+1)%4] != null && neighbors[ (rNum+1) % 4].numWallsUp() == 4)
					newCell = neighbors[ (rNum+1) %4] ;
				else if ( neighbors[(rNum+2)%4] != null && neighbors[ (rNum+2) % 4].numWallsUp() == 4)
					newCell = neighbors[ (rNum+2) %4] ;
				else if ( neighbors[(rNum+3)%4] != null && neighbors[ (rNum+3) % 4].numWallsUp() == 4)
					newCell = neighbors[ (rNum+3) %4] ;
				
				
				// add something to drive path into middle
				// Without the next two if statement MazeNoSolver paths tend towards the perimeter
				if ( (currentCell.getI() < N/2) && (neighbors[0]!=null) && (neighbors[0].numWallsUp()==4) )
					newCell = neighbors[0] ;
				if ( (currentCell.getI() > N/2) && (neighbors[2]!=null) && (neighbors[2].numWallsUp()==4) )
					newCell = neighbors[2] ;
				
				
				// knock down wall between them
				knockDownWalls(currentCell,newCell) ;
				
				// push current cell onto stack
				cellStack.push(currentCell) ;
				
				// set currentCell to the new cell
				currentCell = newCell ;
				
				numCellsVisited++ ;
				
				
			}
				
		}
		// System.out.println("Done") ;
		// this.draw();	
	}
	
	
	public void knockDownWalls(Cell cell1, Cell cell2) 
	{
		int i1, j1, i2, j2 ;
		
		i1 = cell1.getI() ;
		j1 = cell1.getJ();
		i2 = cell2.getI();
		j2 = cell2.getJ() ;
		
		if (i1 == i2)   // one above, one below
		{
			if (j1 < j2)
			{
				cell1.removeWall(0) ;   // remove upper wall
				cell2.removeWall(2) ;   // remove lower wall
				
			}
			else
			{
				cell1.removeWall(2) ;   // remove lower wall
				cell2.removeWall(0) ;   // remove upper wall
				
			}
		}
		else
		{
			if (i1 < i2)
			{
				cell1.removeWall(1) ;   // remove right wall
				cell2.removeWall(3) ;   // remove left wall
				
			}
			else
			{
				cell1.removeWall(3) ;   // remove left wall
				cell2.removeWall(1) ;   // remove right wall
				
			}
		
		}
	}
	
	
	

}