#include <stdio.h>
#include <stdlib.h>
#include <getopt.h>
#include <unistd.h>
#include <ctype.h>
#include <string.h>

// The fundementals for the maze-generation algoritm
// A stack data-structure
struct stack
{
    int max_size;
    int top;        
    int *items;
};

// Create a new stack
struct stack* new_stack(int capacity)
{
    struct stack *pt = (struct stack*)malloc(sizeof(struct stack));

    pt->max_size = capacity;
    pt->top = -1;
    pt->items = (int*)malloc(sizeof(int) * capacity);

    return pt;
}

// Check if a stack is empty
int stack_is_empty(struct stack *pt)
{
    return pt->top == -1;
}

// Check if a stack is full
int stack_is_full(struct stack *pt)
{
    return pt->top == pt->max_size - 1;
}

// Add a new item to a stack
void stack_push(struct stack *pt, int x)
{
    // Avoid a overflow by checking if the stack is full
    if (stack_is_full(pt))
    {
        printf("Overflow error\nProgram terminated\n");
        exit(EXIT_FAILURE);
    }

    // Add an element and increase the top index
    pt->items[++pt->top] = x;
}

// Get the topmost item of a stack
int stack_peek(struct stack *pt)
{
    // Check if the stack is empty
    if (!stack_is_empty(pt))
        return pt->items[pt->top];
    else
        exit(EXIT_FAILURE);
}

// Remove the topmost item of a stack
int stack_pop(struct stack *pt)
{
    // Check for a stack underflow
    if (stack_is_empty(pt))
    {
        printf("Underflow error\nProgram terminated\n");
        exit(EXIT_FAILURE);
    }

    // Decrease the stack size by 1 and (optionally) return the popped element
    return pt->items[pt->top--];
}

// Get a position in the maze from coordinates y and x
//
// This is achieved by concatenating the binary values of the two variables.
//
// For example:
// Y: 8	   00001000
// X: 15   00001111
// Will become:
// 0000100000001111
int get_maze_pos(int posY, int posX)
{
	return ((posY) << 8) | posX;
}

// Get y and x coordinates from a position in the maze
//
// This is achived by using bitwise operations
//
// >> is the bitwise right shift operator and will shift bits to the right
// & is the bitwise and operator and is used to get only specific bits
int get_maze_coords(int pos, int *y, int *x)
{
	*y = pos >> 8;
	*x = pos & 255;
	return 1;
}

// Find out if a string is a number by running it through
// isdigit() char-by-char
int is_number(char * str)
{
	size_t len = strlen(str);
	for(int c = 0; c < len; c++){
		if(!isdigit(str[c]))
			return 0;
	}
	return 1;
}

// Where the magic happends
int main(int argc, char *argv[])
{
	int maze_width = 40;
	int maze_heigth = 20;
	char *wall = "█";
	int seed;

	static struct option options[] = {
		/*   NAME	ARGUMENT		FLAG	SHORTNAME */
		{"width",	required_argument,	NULL,	'w'},
		{"heigth",	required_argument,	NULL,	'h'},
		{"wall",	required_argument,	NULL,	'W'},
		{"seed",	required_argument,	NULL,	's'},
		{"help",	no_argument,		NULL,	0},
		{NULL,		0,			NULL,	0}
	};
	
	int c;
	while((c = getopt_long(argc, argv, "w:h:W:s:", options, NULL)) != -1) {
		switch(c){
		case 'w':
			// Set Width
			if(is_number(optarg) && atoi(optarg) >= 1 && atoi(optarg) <= 255)
				maze_width = atoi(optarg);
			else{
				printf("Invalid option argument for -w/--width!\n");
				exit(1);
			}
			break;
		case 'h':
			// Set heigth
			if(is_number(optarg) && atoi(optarg) >= 1 && atoi(optarg) <= 255)
				maze_heigth = atoi(optarg);
			else{
				printf("Invalid option argument for -h/--heigth!\n");
				exit(1);
			}
			break;
		case 'W':
			// Set the wall
			wall = optarg;
			break;
		case 's':
			// Set the seed
			if(is_number(optarg)){
				seed = atoi(optarg);
				break;
			}
			else{
				printf("Invalid option argument for -s/--seed!\n");
				exit(1);
			}
		case 0:
			// Help
			printf("Usage: mazerator [--help] [-W wall] [-s seed] [-w width] [-h heigth]\n\n\
OPTIONS\n\
    --width        -w     The width of the maze. (1-255). Default: 40\n\
    --heigth       -h     The heigth of the maze. (1-255). Default: 20\n\
    --wall         -W     Single character used as maze walls. Default: '█'\n\
    --seed         -s     The randomization seed used for maze generation. (Any number). Default is to read /dev/urandom\n\
    --help                Displays usage information\n\
");
			exit(0);
		case '?':
			printf("\nTry 'mazerator --help' for more information\n");
			exit(1);
		}
	}
	
	int maze[maze_heigth][maze_width];
	char *maze_visual[maze_heigth * 2 + 1][maze_width * 2 + 1];
	struct stack *path = new_stack(maze_width * maze_heigth);

	// Prepares seed value for randr()
	// Get's a seed from /dev/urandom if not already set
	if(seed == 0){
		FILE *f = fopen("/dev/urandom", "r");
		fread(&seed, sizeof(seed), 1, f);
		fclose(f);
	}
	srand(seed);
	
	// Prepares the maze grids
	// Fills the maze with zeroes indicating that none of the grid squares have been visited
	//
	// Fills the visual maze with walls
	for(int y = 0; y < sizeof(maze) / sizeof(maze[0]); y++){
		for(int x = 0; x < sizeof(maze[0]) / sizeof(maze[0][0]); x++){
			maze[y][x] = 0;
		}
	}
	for(int y = 0; y < sizeof(maze_visual) / sizeof(maze_visual[0]); y++){
		for(int x = 0; x < sizeof(maze_visual[0]) / sizeof(maze_visual[0][0]); x++){
			maze_visual[y][x] = wall;
		}
	}
	
	// Set the start value (0, 0) and begin the algoritm loop
	stack_push(path, 0);
	int cnt = 0;
	while(1){
		int pos = stack_peek(path);
		int posY, posX;
		get_maze_coords(pos, &posY, &posX);
		
		// Set the currently visited grid square to 1 indicating that it has been visited
		// and excavate the visual maze
		maze[posY][posX] = 1;
		maze_visual[posY * 2 + 1][posX * 2 + 1] = " ";

		// Find out available next positions to go to
		int neighbours[3];
		int i = 0;
		if(posY != 0 && maze[posY - 1][posX] == 0){
			neighbours[i] = get_maze_pos(posY - 1, posX);
			i++;
			
		}
		if(posY != maze_heigth - 1 && maze[posY + 1][posX] == 0){
			neighbours[i] = get_maze_pos(posY + 1, posX);
			i++;
		}
		if(posX != 0 && maze[posY][posX - 1] == 0){
			neighbours[i] = get_maze_pos(posY, posX - 1);
			i++;
		}
		if(posX != maze_width - 1 && maze[posY][posX + 1] == 0){
			neighbours[i] = get_maze_pos(posY, posX + 1);
			i++;
		}

		switch(i){
		case 0:
			// No available next positions
			if(cnt == (maze_heigth * maze_width) - 1){
				for(int y = 0; y < sizeof(maze_visual) / sizeof(maze_visual[0]); y++){
					for(int x = 0; x < sizeof(maze_visual[0]) / sizeof(maze_visual[0][0]); x++){
						printf("%s", maze_visual[y][x]);
					}
					printf("\n");
				}
				exit(0);
			}
			stack_pop(path);
			break;
		default:
			// Available next positions
			// Choose a random one and go there
			cnt++;
			int next = neighbours[rand() % i];
			int next_y, next_x;
			get_maze_coords(next, &next_y, &next_x);
			maze_visual[posY * 2 - (posY - next_y) + 1][posX * 2 - (posX - next_x) + 1] = " ";
			stack_push(path, next);
		}
	}
}