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

/**
 * Returns a filled grid.
 *
 * @param width The width of the new grid
 * @param height The height of the new grid
 * @param fill A string to fill the new grid with
 */
char ***create_grid(int width, int height, char *fill)
{
	char ***grid;

	// Fill the grid
	grid = malloc(height * sizeof(char **));
	for (int y = 0; y < height; y++)
	{
		grid[y] = malloc(width * sizeof(char *));

		for (int x = 0; x < width; x++)
		{
			grid[y][x] = fill;
		}
	}

	return grid;
}

Maze maze_create(Dimensions dimens, char *wall)
{
	Maze maze;

	maze.dimens = dimens;

	Dimensions full_dimens = {.width = dimens.width * 2 + 1,
							  .height = dimens.height * 2 + 1};

	maze.full_dimens = full_dimens;

	maze.grid = create_grid(full_dimens.width, full_dimens.height, wall);

	return maze;
}

void maze_destroy(Maze *maze)
{
	// Deallocate the memory of the maze's grid
	for (int y = 0; y < maze->full_dimens.height; y++)
	{
		free(maze->grid[y]);
	}
	free(maze->grid);
}

void get_neighbours(Maze *maze, Position pos, Position neighbours[3], int *neighbour_cnt)
{
	if (pos.y != 0 && strcmp(maze->grid[pos.y * 2 - 1][pos.x * 2 + 1], " ") != 0)
	{
		Position down_neighbour_pos = {.x = pos.x, .y = pos.y - 1};
		neighbours[*neighbour_cnt] = down_neighbour_pos;
		(*neighbour_cnt)++;
	}
	if (pos.y != maze->dimens.height - 1 &&
		strcmp(maze->grid[(pos.y + 1) * 2 + 1][pos.x * 2 + 1], " ") != 0)
	{
		Position up_neighbour_pos = {.x = pos.x, .y = pos.y + 1};
		neighbours[*neighbour_cnt] = up_neighbour_pos;
		(*neighbour_cnt)++;
	}
	if (pos.x != 0 && strcmp(maze->grid[pos.y * 2 + 1][pos.x * 2 - 1], " ") != 0)
	{
		Position left_neighbour_pos = {.x = pos.x - 1, .y = pos.y};
		neighbours[*neighbour_cnt] = left_neighbour_pos;
		(*neighbour_cnt)++;
	}
	if (pos.x != maze->dimens.width - 1 &&
		strcmp(maze->grid[pos.y * 2 + 1][(pos.x + 1) * 2 + 1], " ") != 0)
	{
		Position right_neighbour_pos = {.x = pos.x + 1, .y = pos.y};
		neighbours[*neighbour_cnt] = right_neighbour_pos;
		(*neighbour_cnt)++;
	}
}

int is_whole_maze_visited(Maze *maze, int visited_pos_cnt)
{
	if (visited_pos_cnt == (maze->dimens.height * maze->dimens.width) - 1)
	{
		return 1;
	}

	return 0;
}

void maze_excavate(Maze *maze, Position start_pos)
{
	PositionStack *path = pos_stack_create(maze->dimens.width * maze->dimens.height);

	pos_stack_push(path, start_pos);

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

		maze->grid[pos.y * 2 + 1][pos.x * 2 + 1] = " ";

		Position neighbours[3] = {};
		int neighbour_cnt = 0;

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

		if (neighbour_cnt == 0)
		{
			if (is_whole_maze_visited(maze, visited_pos_cnt))
			{
				break;
			}

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

		visited_pos_cnt++;

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

		maze->grid[pos.y * 2 - (pos.y - next_pos.y) + 1]
				  [pos.x * 2 - (pos.x - next_pos.x) + 1] = " ";

		pos_stack_push(path, next_pos);
	}

	pos_stack_destroy(path);
}

void maze_print(Maze maze)
{
	for (int y = 0; y < maze.full_dimens.height; y++)
	{
		for (int x = 0; x < maze.full_dimens.width; x++)
		{
			printf("%s", maze.grid[y][x]);
		}
		printf("\n");
	}
}