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

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

void add_neighbour(Position neighbours[], uint8_t *neighbour_cnt, Position neighbour_pos)
{
	neighbours[*neighbour_cnt] = neighbour_pos;
	(*neighbour_cnt)++;

}

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

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

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

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

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

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

	if (pos.x != grid.dimens.width - 2)
	{
		Position pos_right = position_create(pos.x + 2, 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 - 1) / 2) * ((grid.dimens.height - 1) / 2);
}

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

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 = 0;
	while (1)
	{
		Position pos = pos_stack_peek(path);

		grid_set(grid, pos, " ");

		Position neighbours[3];
		uint8_t neighbour_cnt = 0;

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

		if (neighbour_cnt == 0)
		{
			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)
			between_pos.y += next_pos.y > pos.y ? 1 : -1;

		if (next_pos.x != pos.x)
			between_pos.x += next_pos.x > pos.x ? 1 : -1;

		grid_set(grid, between_pos, " ");

		pos_stack_push(path, next_pos);
	}

	pos_stack_destroy(path);
}