#include "maze.h"
#include <cmath>
#include <stdlib.h>
#include <time.h>
#include <stack>



// CONSTRUCTOR
Maze::Maze(int width, int height, int size)
{
  this->width = width;
  this->height = height;
  this->size = size;
  srand(time(0));
  maze = new Hexagon*[width];
  for(int i = 0; i < width; ++i)
  {
    maze[i] = new Hexagon[height];
  }

  for(int j = 0; j < height; ++j)
  {
    for(int i = 1-j%2; i < width+(1-j%2); ++i)
    {
      maze[i-(1-j%2)][j].setFields(i*2*(sqrt(3)/2)*size+(j%2*(sqrt(3)/2)*size),
                                   size + j*size+j*(size/2), size);
    }    
  }
}

// DESTRUCTOR
Maze::~Maze()
{
  for(int i = 0; i < width; ++i)
  {
    delete[] maze[i];
  }
  delete[] maze;
}


// METHODS

void Maze::getApproximativeSizeForImage(int& width, int& height) const
{
  width  = 2 * this->width * ((sqrt(3.0) / 2.0) * size) + (sqrt(3.0) / 2.0) * size;
  height = (this->height + 1) * (1.0 / 2.0) * size + this->height * size; 
}

void Maze::display(SDL_Surface* image) const
{
  for(int i = 0; i < width; ++i)
  {
    for(int j = 0; j < height; ++j)
    {
      maze[i][j].display(image);
    }
  }
}

void Maze::constructMaze()
{
  std::stack<coordinate> s;
  int x = 0;
  int y = 0;
  maze[x][y].setVisited(true);
  while(unvisitedCell())
  {
    if(asUnvisitedNeighbours(x, y))
    {
      int x_temp;
      int y_temp;
      pickRandomUnvisitedNeighbour(x, y, &x_temp, &y_temp);
      coordinate coord;
      coord.x = x;
      coord.y = y;
      s.push(coord);
      removeWall(x, y, x_temp, y_temp);
      x = x_temp;
      y = y_temp;
      maze[x][y].setVisited(true);
    }
    else if(!s.empty())
    {
      coordinate coord = s.top();
      s.pop();
      x = coord.x;
      y = coord.y;
    }
  }
}

bool Maze::asUnvisitedNeighbours(int x, int y) const
{
  int x2 = getNeighbourX(x, y, top_left);
  int y2 = getNeighbourY(x, y, top_left);
  if(inBounds(x2, y2) && !maze[x2][y2].isVisited())
    return true;
  x2 = getNeighbourX(x, y, top_right);
  y2 = getNeighbourY(x, y, top_right);
  if(inBounds(x2, y2) && !maze[x2][y2].isVisited())
    return true;
  x2 = getNeighbourX(x, y, bottom_left);
  y2 = getNeighbourY(x, y, bottom_left);
  if(inBounds(x2, y2) && !maze[x2][y2].isVisited())
    return true;
  x2 = getNeighbourX(x, y, bottom_right);
  y2 = getNeighbourY(x, y, bottom_right);
  if(inBounds(x2, y2) && !maze[x2][y2].isVisited())
    return true;
  x2 = getNeighbourX(x, y, left);
  y2 = getNeighbourY(x, y, left);
  if(inBounds(x2, y2) && !maze[x2][y2].isVisited())
    return true;
  x2 = getNeighbourX(x, y, right);
  y2 = getNeighbourY(x, y, right);
  if(inBounds(x2, y2) && !maze[x2][y2].isVisited())
    return true;
  return false;
}

int Maze::numberOfUnvisitedNeighbours(int x, int y) const
{
  int total = 0;
  int x2 = getNeighbourX(x, y, top_left);
  int y2 = getNeighbourY(x, y, top_left);
  if(inBounds(x2, y2) && !maze[x2][y2].isVisited())
    total++;
  x2 = getNeighbourX(x, y, top_right);
  y2 = getNeighbourY(x, y, top_right);
  if(inBounds(x2, y2) && !maze[x2][y2].isVisited())
    total++;
  x2 = getNeighbourX(x, y, bottom_left);
  y2 = getNeighbourY(x, y, bottom_left);
  if(inBounds(x2, y2) && !maze[x2][y2].isVisited())
    total++;
  x2 = getNeighbourX(x, y, bottom_right);
  y2 = getNeighbourY(x, y, bottom_right);
  if(inBounds(x2, y2) && !maze[x2][y2].isVisited())
    total++;
  x2 = getNeighbourX(x, y, left);
  y2 = getNeighbourY(x, y, left);
  if(inBounds(x2, y2) && !maze[x2][y2].isVisited())
    total++;
  x2 = getNeighbourX(x, y, right);
  y2 = getNeighbourY(x, y, right);
  if(inBounds(x2, y2) && !maze[x2][y2].isVisited())
    total++;
  return total;
}

void Maze::pickRandomUnvisitedNeighbour(int x, int y, int* x_temp, int* y_temp) const
{
  int number = numberOfUnvisitedNeighbours(x ,y);
  int i = rand()%number + 1;


  int x2 = getNeighbourX(x, y, top_left);
  int y2 = getNeighbourY(x, y, top_left);
  if(inBounds(x2, y2) && !maze[x2][y2].isVisited() && 1 == i--)
  {
    *x_temp = x2;
    *y_temp = y2;
    return;
  }
  x2 = getNeighbourX(x, y, top_right);
  y2 = getNeighbourY(x, y, top_right);
  if(inBounds(x2, y2) && !maze[x2][y2].isVisited() && 1 == i--)
  {
    *x_temp = x2;
    *y_temp = y2;
    return;
  }
  x2 = getNeighbourX(x, y, bottom_left);
  y2 = getNeighbourY(x, y, bottom_left);
  if(inBounds(x2, y2) && !maze[x2][y2].isVisited() && 1 == i--)
  {
    *x_temp = x2;
    *y_temp = y2;
    return;
  }
  x2 = getNeighbourX(x, y, bottom_right);
  y2 = getNeighbourY(x, y, bottom_right);
  if(inBounds(x2, y2) && !maze[x2][y2].isVisited() && 1 == i--)
  {
    *x_temp = x2;
    *y_temp = y2;
    return;
  }
  x2 = getNeighbourX(x, y, left);
  y2 = getNeighbourY(x, y, left);
  if(inBounds(x2, y2) && !maze[x2][y2].isVisited() && 1 == i--)
  {
    *x_temp = x2;
    *y_temp = y2;
    return;
  }
  x2 = getNeighbourX(x, y, right);
  y2 = getNeighbourY(x, y, right);
  if(inBounds(x2, y2) && !maze[x2][y2].isVisited() && 1 == i--)
  {
    *x_temp = x2;
    *y_temp = y2;
    return;
  }
}

void Maze::removeWall(int x1, int y1, int x2, int y2)
{
  if(y1 % 2 == 0)
  {
    if(x1 == x2 && y1 > y2)
    {
      maze[x1][y1].removeWall(top_left);
      maze[x2][y2].removeWall(bottom_right);
    }
    if(x1 < x2 && y1 > y2)
    {
      maze[x1][y1].removeWall(top_right);
      maze[x2][y2].removeWall(bottom_left);
    }
    if(x1 < x2 && y1 == y2)
    {
      maze[x1][y1].removeWall(right);
      maze[x2][y2].removeWall(left);
    }
    if(x1 < x2 && y1 < y2)
    {
      maze[x1][y1].removeWall(bottom_right);
      maze[x2][y2].removeWall(top_left);
    }
    if(x1 == x2 && y1 < y2)
    {
      maze[x1][y1].removeWall(bottom_left);
      maze[x2][y2].removeWall(top_right);
    }
    if(x1 > x2 && y1 == y2)
    {
      maze[x1][y1].removeWall(left);
      maze[x2][y2].removeWall(right);
    }      
  }
  else
  {
    if(x1 > x2 && y1 > y2)
    {
      maze[x1][y1].removeWall(top_left);
      maze[x2][y2].removeWall(bottom_right);
    }
    if(x1 == x2 && y1 > y2)
    {
      maze[x1][y1].removeWall(top_right);
      maze[x2][y2].removeWall(bottom_left);
    }
    if(x1 < x2 && y1 == y2)
    {
      maze[x1][y1].removeWall(right);
      maze[x2][y2].removeWall(left);
    }
    if(x1 == x2 && y1 < y2)
    {
      maze[x1][y1].removeWall(bottom_right);
      maze[x2][y2].removeWall(top_left);
    }
    if(x1 > x2 && y1 < y2)
    {
      maze[x1][y1].removeWall(bottom_left);
      maze[x2][y2].removeWall(top_right);
    }
    if(x1 > x2 && y1 == y2)
    {
      maze[x1][y1].removeWall(left);
      maze[x2][y2].removeWall(right);
    }    
  }


}

bool Maze::inBounds(int x, int y) const
{
  return x >= 0 && x < width && y >= 0 && y < height;
}

bool Maze::unvisitedCell() const
{
  for(int i = 0; i < width; ++i)
  {
    for(int j = 0; j < height; ++j)
    {
      if(!maze[i][j].isVisited())
        return true;
    }
  }
  return false;
}

int Maze::getNeighbourX(int x, int y, direction dir) const
{
  if(dir == top_left)
  {
    return x - y % 2;
  }
  if(dir == top_right)
  {
    return x + (1 - y % 2);
  }
  if(dir == bottom_right)
  {
    return x + (1 - y % 2);
  }
  if(dir == bottom_left)
  {
    return x - y % 2;
  }
  if(dir == left)
  {
    return x - 1;
  }
  if(dir == right)
  {
    return x + 1;
  }
}

int Maze::getNeighbourY(int x, int y, direction dir) const
{
  if(dir == top_left || dir == top_right)
    return y - 1;
  if(dir == bottom_left || dir == bottom_right)
    return y + 1;
  return y;
}