#include "maze.hpp"
#include "stack.hpp"
#include <vector>

/**
 * Returns the neighbours of a position in a maze.
 *
 * @param matrix A matrix
 * @param pos A matrix position
 * @param space_element A matrix element used to indicate a space in a maze
 */
template <typename Element>
std::vector<std::shared_ptr<Vector2>> get_neighbours(Matrix<Element> *matrix,
													 std::shared_ptr<Vector2> pos,
													 Element space_element)
{
	std::vector<std::shared_ptr<Vector2>> neighbours;
	neighbours.reserve(3);

	if (pos->y() != 1U)
	{
		auto pos_down = (*pos - Vector2(0U, 2U)).copy();

		if (matrix->get(*pos_down) != space_element)
			neighbours.push_back(pos_down);
	}

	if (pos->y() != matrix->rows() - 2U)
	{
		auto pos_up = (*pos + Vector2(0U, 2U)).copy();

		if (matrix->get(*pos_up) != space_element)
			neighbours.push_back(pos_up);
	}

	if (pos->x() != 1U)
	{
		auto pos_left = (*pos - Vector2(2U, 0U)).copy();

		if (matrix->get(*pos_left) != space_element)
			neighbours.push_back(pos_left);
	}

	if (pos->x() != matrix->columns() - 2U)
	{
		auto pos_right = (*pos + Vector2(2U, 0U)).copy();

		if (matrix->get(*pos_right) != space_element)
			neighbours.push_back(pos_right);
	}

	return neighbours;
}

/**
 * Returns the logical size of a maze for a matrix.
 *
 * @param matrix A matrix
 */
template <typename Element>
unsigned int get_maze_size(Matrix<Element> *matrix)
{
	return ((matrix->columns() - 1U) / 2U) * ((matrix->rows() - 1U) / 2U);
}

/**
 * Makes a position be between two coordinates with a differential vector.
 *
 * @param between_pos Target position
 * @param coord A coordinate
 * @param coord A second coordinate that must not be equal too the first
 * @param diff A differential vector to apply to the target position
 */
void pos_to_between(std::shared_ptr<Vector2> between_pos, unsigned int coord,
					unsigned int away_coord, Vector2 diff)
{
	if (away_coord > coord)
		*between_pos += diff;
	else
		*between_pos -= diff;
}

template <typename Element>
void matrix_to_maze(Matrix<Element> *matrix, std::shared_ptr<Vector2> start_pos,
					Element space_element, std::mt19937 random_gen)
{
	Stack<std::shared_ptr<Vector2>> path_stack(get_maze_size(matrix));

	path_stack.push(start_pos);

	unsigned int visited_pos_cnt = 0U;
	while (1)
	{
		auto pos = path_stack.peek();

		matrix->set(*pos, space_element);

		std::vector<std::shared_ptr<Vector2>> neighbours =
			get_neighbours(matrix, pos, space_element);

		if (neighbours.empty())
		{
			if (visited_pos_cnt == get_maze_size(matrix) - 1U)
				break;

			// Go back a step
			path_stack.pop();
			continue;
		}

		visited_pos_cnt++;

		auto random_dist = std::uniform_int_distribution<unsigned int>(
			0U, static_cast<unsigned int>(neighbours.size()) - 1U);

		auto next_pos = neighbours[random_dist(random_gen)];

		auto between_pos = pos->copy();

		if (next_pos->y() != pos->y())
			pos_to_between(between_pos, pos->y(), next_pos->y(), Vector2(0U, 1U));

		if (next_pos->x() != pos->x())
			pos_to_between(between_pos, pos->x(), next_pos->x(), Vector2(1U, 0U));

		matrix->set(*between_pos, space_element);

		path_stack.push(next_pos);
	}
}