#include "MazeGenerator.h"
#include <stdlib.h>
#include <time.h>

MazeGenerator::MazeGenerator()
{
  srand(time(NULL));
  m_height = 2;  
  m_width = 2;
  maze_ready = false;
  verticalWalls = new bool[(m_width-1)*m_height];
  horizontalWalls = new bool[(m_height-1)*m_width];
}

MazeGenerator::MazeGenerator(int width, int height)
{
  srand(time(NULL));
  maze_ready = false;
  m_height = height;  
  m_width = width;
  verticalWalls = new bool[(width-1)*height];
  horizontalWalls = new bool[(height-1)*width];
}

void MazeGenerator::setDimensions(int width, int height)
{
  maze_ready = false;
  m_height = height;  
  m_width = width;
  disjset.resetSize(width*height);
  delete [] verticalWalls;
  delete [] horizontalWalls;
  verticalWalls = new bool[(width-1)*height];
  horizontalWalls = new bool[(height-1)*width];
}

void MazeGenerator::generateMaze()
{
  Grabbag<Pair> walls(m_height*m_width);

  // guarantee disjset is reset
  disjset.resetSize(m_width*m_height);

  // randomly choose the start square
  startX = rand()%m_width;
  startY = rand()%m_height;

  // randomly choose a different exit square
  do {
     exitX = rand()%m_width;
     exitY = rand()%m_height;
  } while(exitX == startX && exitY == startY);


  // generate all vertical, non-boundary walls
  for(int j=0; j<m_height; j++)
    for(int i=0; i<m_width-1; i++)
      {
	verticalWalls[j*(m_width-1)+i] = true;
	Pair wall;  
	wall.Ax = i;
	wall.Ay = j;
	wall.Bx = i+1;
	wall.By = j;
	walls.insert(wall);
      }

  // generate all horizontal, non-boundary walls
  for(int j=0; j<m_height-1; j++)
    for(int i=0; i<m_width; i++)
      {
	horizontalWalls[j*(m_width)+i] = true;
	Pair wall;  
	wall.Ax = i;
	wall.Ay = j;
	wall.Bx = i;
	wall.By = j+1;
	walls.insert(wall);
      }


  bool horizontal_wall;
  while(!walls.is_empty())
    {
      int A,B;

      Pair wall = walls.grab();

      if(wall.Ax == wall.Bx) // horizontal wall
	horizontal_wall = true;
      else  // vertical wall
	horizontal_wall = false;

      A = wall.Ax + wall.Ay * m_width;
      B = wall.Bx + wall.By * m_width;

      int rA = disjset.find(A);
      int rB = disjset.find(B);

      if(rA != rB )  // not connected
	{
	  disjset.unionSets(rA, rB);
	  // update out here
	  if(horizontal_wall)
	    horizontalWalls[ wall.Ax + wall.Ay*m_width ] = false;
	  else
	    verticalWalls[ wall.Ax + wall.Ay*(m_width-1) ] = false;
	}
    }

  maze_ready = true;
  // print out the maze
}

void MazeGenerator::printMaze(ostream& os)
{
  if(!maze_ready) {
    os << "No maze generated\n";
    return;
  }
  
  // print dimensions
  os << m_width << " " << m_height << endl;
 
  // print top wall of maze
  for(int i=0; i<m_width; i++)
    os << "+-";
  os << "+" << endl;

  // print first m_height-1 rows of the maze
  for(int j=0; j<m_height; j++) {
    // vertical wall part
    os << "|";
    for(int i=0; i<m_width; i++) {
      if(isStart(i,j))
	os << "*";
      else if(isExit(i,j))
	os << "X";
      else
	os << " ";

      if(i==m_width-1) // always a wall
	os << "|";
      else if(verticalWalls[j*(m_width-1)+i]) // wall
	os << "|";
      else // no wall
	os << " ";
      }
    os << endl;
    
    // horizontal wall part
    for(int i=0; i<m_width; i++) {
      os << "+";
      if(j==m_height-1) // always a wall
	os << "-";
      else if(horizontalWalls[j*(m_width)+i]) // wall
	os << "-";
      else
	os << " ";
    }
    os << "+" << endl;
  }
}
 
bool MazeGenerator::isStart(int i, int j)
{
  if(startX==i && startY==j) return true;
  else return false;
}

bool MazeGenerator::isExit(int i, int j)
{
  if(exitX==i && exitY==j) return true;
  else return false;
}

bool Pair::operator == (Pair otherPair) const
{
  if(Ax == otherPair.Ax && Ay == otherPair.Ay && 
     Bx == otherPair.Bx && By == otherPair.By ) 
    return true;
  else
    return false;
}