#include "mazegen.h"
#include "modifiableboard.h"
#include <boost/multi_array.hpp>
#include <vector>
#include <utility>
#include <algorithm>

struct Wall {
	Wall() {}
	Wall(int r, int c, bool h): row(r), column(c), horizontal(h)
	{}
	
	int row, column;
	bool horizontal;

	int nRow() const {
		return horizontal ? row+1 : row;
	}
	int nCol() const {
		return horizontal ? column : column+1;
	}
};

template<class Iter>
void MazeGen::addWalls(Iter i, int row, int col)
{
	Board& b = *m_board;
	if (row>0 && b[row-1][col]&1) {
		*i = Wall(row-1, col, 1);
		++i;
	}
	if (col>0 && b[row][col]&2) {
		*i = Wall(row, col-1, 0);
		++i;
	}
	if (row<b.getY()-1 && b[row][col]&1) {
		*i = Wall(row, col, 1);
		++i;
	}
	if (col<b.getX()-1 && b[row][col]&2) {
		*i = Wall(row, col, 0);
		++i;
	}
}

MazeGen::MazeGen()
{
	m_board = new ModifiableBoard;
}

Board& MazeGen::genMaze(int w, int h, Algorithm algo)
{
	m_board->create(h, w);
	switch (algo) {
		case PRIM:
			genPrim();
			break;
		case DFS:
			genDFS();
			break;
		case KRUSKAL:
			genKruskal();
			break;
		case CHAMBERS:
			genChambers();
			break;
		default:
			break;
	};
	return *m_board;
}

inline
void MazeGen::fillWalls()
{
	for(int y=0; y<m_board->getY(); ++y) {
		for(int x=0; x<m_board->getX(); ++x) {
			m_board->setWall(y, x, 3);
		}
	}
}

inline
void MazeGen::setStartEnd(int sx, int sy, int ex, int ey)
{
	m_board->setStart(sy, sx);
	m_board->setBlock(ey, ex, END);
}

void MazeGen::genPrim()
{
	fillWalls();
	setStartEnd(0, 0, m_board->getX()-1, m_board->getY()-1);

	typedef std::vector<Wall> WallV;
	typedef boost::multi_array<bool, 2> CellM;

	CellM cells(boost::extents[m_board->getY()][m_board->getX()]);
	for(CellM::iterator i=cells.begin(); i!=cells.end(); ++i) {
		for(CellM::subarray<1>::type::iterator j=i->begin(); j!=i->end(); ++j) {
			*j = 0;
		}
	}

	WallV walls;
	int startX = rand()%m_board->getX();
	int startY = rand()%m_board->getY();
	if (startX > 0)
		walls.push_back(Wall(startY, startX-1, 0));
	if (startY > 0)
		walls.push_back(Wall(startY-1, startX, 1));
	if (startX < m_board->getX()-1)
		walls.push_back(Wall(startY, startX, 0));
	if (startY < m_board->getY()-1)
		walls.push_back(Wall(startY, startX, 1));
	cells[startY][startX] = 1;

	while(!walls.empty()) {
		int place = rand()%walls.size();
		Wall cur = walls[place];	// copy because the vector is modified later

		bool& cell1 = cells[cur.row][cur.column];
		bool& cell2 = cells[cur.nRow()][cur.nCol()];
		if (wallExists(cur) && (!cell1 || !cell2)) {
			m_board->toggleWall(cur.row, cur.column, ModifiableBoard::WallT(!cur.horizontal));
			if (!cell1) {
				cell1 = 1;
				addWalls(std::back_inserter(walls), cur.row, cur.column);
			} else {
				cell2 = 1;
				addWalls(std::back_inserter(walls), cur.nRow(), cur.nCol());
			}
		}

		if (static_cast<unsigned int>(place) != walls.size()-1)
			walls[place] = walls[walls.size()-1];
		walls.pop_back();
	}
}

inline
bool MazeGen::wallExists(const Wall& w) const
{
	return (*m_board)[w.row][w.column] & 1<<!w.horizontal;
}

void MazeGen::genDFS()
{
	fillWalls();
	setStartEnd(0, 0, m_board->getX()-1, m_board->getY()-1);

	typedef boost::multi_array<bool, 2> CellM;

	CellM cells(boost::extents[m_board->getY()][m_board->getX()]);
	for(CellM::iterator i=cells.begin(); i!=cells.end(); ++i) {
		for(CellM::subarray<1>::type::iterator j=i->begin(); j!=i->end(); ++j) {
			*j = 0;
		}
	}

	recurseDFS(cells, 0, 0);
}

void MazeGen::recurseDFS(boost::multi_array_ref<bool, 2> cells, int x, int y)
{
	cells[y][x] = 1;
	typedef std::pair<int, int> coord;
	std::vector<coord> next;
	next.reserve(4);
	if (x>0) {
		next.push_back(coord(y, x-1));
	}
	if (y>0) {
		next.push_back(coord(y-1, x));
	}
	if (x<m_board->getX()-1) {
		next.push_back(coord(y, x+1));
	}
	if (y<m_board->getY()-1) {
		next.push_back(coord(y+1, x));
	}
	while(!next.empty()) {
		coord& cur = next[rand()%next.size()];
		if (!cells[cur.first][cur.second]) {
			toggleBetween(x, y, cur.second, cur.first);
			recurseDFS(cells, cur.second, cur.first);
		}
		cur = next[next.size()-1];
		next.pop_back();
	}
}

void MazeGen::toggleBetween(int x1, int y1, int x2, int y2)
{
	if (x1 != x2) {
		if (x1 < x2)
			m_board->toggleWall(y1, x1, ModifiableBoard::RIGHT);
		else
			m_board->toggleWall(y2, x2, ModifiableBoard::RIGHT);
	} else {
		if (y1 < y2)
			m_board->toggleWall(y1, x1, ModifiableBoard::DOWN);
		else
			m_board->toggleWall(y2, x2, ModifiableBoard::DOWN);
	}
}

struct CellNode {
	CellNode(): parent(0), rank(0) {}
	CellNode* parent;
	int rank;

	CellNode& find() {
		if (!parent)
			return *this;
		parent = &parent->find();
		return *parent;
	}
	bool merge(CellNode& n) {
		CellNode& r1 = find();
		CellNode& r2 = n.find();

		if (&r1 != &r2) {
			if (r1.rank > r2.rank)
				r2.parent = &r1;
			else if (r2.rank > r1.rank)
				r1.parent = &r2;
			else {
				r1.parent = &r2;
				++r2.rank;
			}
			return 1;
		}
		return 0;
	}
};

void MazeGen::genKruskal()
{
	fillWalls();
	setStartEnd(0, 0, m_board->getX()-1, m_board->getY()-1);

	typedef boost::multi_array<CellNode, 2> CellM;
	CellM cells(boost::extents[m_board->getY()][m_board->getX()]);

	typedef std::vector<Wall> WallV;
	WallV walls;
	for(int y=0; y<m_board->getY()-1; ++y) {
		for(int x=0; x<m_board->getX()-1; ++x) {
			walls.push_back(Wall(y, x, 0));
			walls.push_back(Wall(y, x, 1));
		}
	}
	for(int y=0; y<m_board->getY()-1; ++y) {
		walls.push_back(Wall(y, m_board->getX()-1, 1));
	}
	for(int x=0; x<m_board->getX()-1; ++x) {
		walls.push_back(Wall(m_board->getY()-1, x, 0));
	}

	std::random_shuffle(walls.begin(), walls.end());

	for(WallV::iterator i = walls.begin(); i != walls.end(); ++i) {
		int y1=i->row, x1=i->column;
		int y2=i->nRow(), x2=i->nCol();

		if (cells[y1][x1].merge(cells[y2][x2])) {
			m_board->toggleWall(y1, x1, ModifiableBoard::WallT(!i->horizontal));
		}
	}
}

void MazeGen::genChambers()
{
	int x=m_board->getX(), y=m_board->getY();
	setStartEnd(0, 0, x-1, y-1);
	recurseChambers(0, 0, x, y);
}

void MazeGen::recurseChambers(int sx, int sy, int ex, int ey)
{
	if (ex-sx == 1) {
		if (ey < m_board->getY())
			m_board->toggleWall(ey-1, sx, ModifiableBoard::DOWN);
		if (ex < m_board->getX()) {
			for(int i=sy; i<ey; ++i) {
				m_board->toggleWall(i, ex-1, ModifiableBoard::RIGHT);
			}
		}
		return;
	} else if (ey-sy == 1) {
		if (ex < m_board->getX())
			m_board->toggleWall(sy, ex-1, ModifiableBoard::RIGHT);
		if (ey < m_board->getY()) {
			for(int i=sx; i<ex; ++i) {
				m_board->toggleWall(ey-1, i, ModifiableBoard::DOWN);
			}
		}
		return;
	}
	
	int mx = sx + rand()%(ex-sx-1) + 1;
	int my = sy + rand()%(ey-sy-1) + 1;

	recurseChambers(sx, sy, mx, my);
	recurseChambers(mx, sy, ex, my);
	recurseChambers(sx, my, mx, ey);
	recurseChambers(mx, my, ex, ey);

	int noHole = rand()%4;
	if (noHole!=0)
		m_board->toggleWall(sy+rand()%(my-sy), mx-1, ModifiableBoard::RIGHT);
	if (noHole!=1)
		m_board->toggleWall(my+rand()%(ey-my), mx-1, ModifiableBoard::RIGHT);
	if (noHole!=2)
		m_board->toggleWall(my-1, sx+rand()%(mx-sx), ModifiableBoard::DOWN);
	if (noHole!=3)
		m_board->toggleWall(my-1, mx+rand()%(ex-mx), ModifiableBoard::DOWN);
}
