#include "maze.h"
#include "grid.h"
#include "position.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int is_pos_empty(Grid grid, Position pos)
{
	return strcmp(grid_get(grid, pos), " ") != 0;
}

void add_neighbour(Position neighbours[3], unsigned int *neighbour_cnt,
				   Position neighbour_pos)
{
	neighbours[*neighbour_cnt] = neighbour_pos;
	(*neighbour_cnt)++;
}

void get_neighbours(Grid grid, Position pos, Position neighbours[3],
					unsigned int *neighbour_cnt)
{
	if (pos.y != 1U)
	{
		Position pos_down = position_create(pos.x, pos.y - 2U);

		if (is_pos_empty(grid, pos_down))
			add_neighbour(neighbours, neighbour_cnt, pos_down);
	}

	if (pos.y != grid.dimens.height - 2U)
	{
		Position pos_up = position_create(pos.x, pos.y + 2U);

		if (is_pos_empty(grid, pos_up))
			add_neighbour(neighbours, neighbour_cnt, pos_up);
	}

	if (pos.x != 1U)
	{
		Position pos_left = position_create(pos.x - 2U, pos.y);

		if (is_pos_empty(grid, pos_left))
			add_neighbour(neighbours, neighbour_cnt, pos_left);
	}

	if (pos.x != grid.dimens.width - 2U)
	{
		Position pos_right = position_create(pos.x + 2U, pos.y);

		if (is_pos_empty(grid, pos_right))
			add_neighbour(neighbours, neighbour_cnt, pos_right);
	}
}

unsigned int get_maze_size(Grid grid)
{
	return ((grid.dimens.width - 1U) / 2U) * ((grid.dimens.height - 1U) / 2U);
}

int is_whole_maze_visited(Grid grid, unsigned int visited_pos_cnt)
{
	return visited_pos_cnt == get_maze_size(grid) - 1U;
}

void grid_to_maze(Grid grid, Position start_pos)
{
	PositionStack *path = pos_stack_create(get_maze_size(grid));

	pos_stack_push(path, start_pos);

	unsigned int visited_pos_cnt = 0U;
	while (1)
	{
		Position pos = pos_stack_peek(path);

		grid_set(grid, pos, " ");

		Position neighbours[3];
		unsigned int neighbour_cnt = 0U;

		get_neighbours(grid, pos, neighbours, &neighbour_cnt);

		if (neighbour_cnt == 0U)
		{
			if (is_whole_maze_visited(grid, visited_pos_cnt))
				break;

			// Go back a step
			pos_stack_pop(path);
			continue;
		}

		visited_pos_cnt++;

		Position next_pos = neighbours[rand() % neighbour_cnt];

		Position between_pos = position_create(pos.x, pos.y);

		if (next_pos.y != pos.y)
		{
			if (next_pos.y > pos.y)
				between_pos.y += 1U;
			else
				between_pos.y -= 1U;
		}

		if (next_pos.x != pos.x)
		{
			if (next_pos.x > pos.x)
				between_pos.x += 1U;
			else
				between_pos.x -= 1U;
		}

		grid_set(grid, between_pos, " ");

		pos_stack_push(path, next_pos);

		// grid_print(grid);
	}

	pos_stack_destroy(path);
}