#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <stdlib.h>
#include <assert.h>
#include <gd.h>
#include <cgicc/Cgicc.h>

using namespace std;

template<class T, class K> inline bool contains(const T& t, const K& k) { return (t.find(k) != t.end()); }
inline bool Percentage(const double p) { return (double)rand() / (double)RAND_MAX < p; }
int opposite_direction(const int d);
int pick_direction(const set<int>& s);

int Max_Size = 1024;
double Probability_DeadEnd;
double Probability_Turn;
double Probability_Split;

enum NodeTypes {
    Blank,
	Occupied,
	Start,
	End
    };

enum Directions {
    N,
	S,
	E,
	W
    };

class Path {
    private:
    int x;
    int y;
    int direction;
    
    public:
    Path(const int x_coord, const int y_coord, const int dir):
	x(x_coord), 
	y(y_coord), 
	direction(dir) {};
    int get_x() { return x; };
    int get_y() { return y; };
    int get_dir() { return direction; };
};


class MazeNode {
    private:
    int type;
    int entry_direction;
    set<int> exit_directions;
    
    public:
    MazeNode(): type(Blank) {};
    int get_type() { return type; };
    int get_entry() { return entry_direction; };
    set<int> get_exits() { return exit_directions; };
    void set_type(const int t) { type = t; };
    void set_entry(const int e) { entry_direction = e; }
    void add_exit(const int d) { exit_directions.insert(d); };
    void remove_exit(const int d) { exit_directions.erase(d); };
};


class Maze {
    private:
    vector<vector<MazeNode> > data;
    int size_x;
    int size_y;
    int start_x;
    int start_y;
    int end_x;
    int end_y;
    queue<Path> pq;
    
    public:
    Maze(const int sz_x, const int sz_y, const int st_x = 0, const int st_y = 0, const int e_x = -1, const int e_y = -1):
	size_x(sz_x),
	size_y(sz_y),
	start_x(st_x),
	start_y(st_y),
	end_x(e_x),
	end_y(e_y) {
	
	if(end_x < 0)
	    end_x = size_x - 1;
	if(end_y < 0)
	    end_y = size_y - 1;
	vector<MazeNode> c(size_y);
	data = vector<vector<MazeNode> >(size_x, c);
	init_start();
	init_end();
    }
    set<int> valid_exits(const int x, const int y);
    MazeNode get_node(const int x, const int y) { return data[x][y]; };
    int move_next_path();
    int fill_blank_space();
    void init_start();
    void init_end();
    void print();
    void print_graphics(const gdImagePtr im, const int color, const int sz_x, const int sz_y);
};


void Maze::init_start() {
    data[start_x][start_y].set_type(Start);
    data[start_x][start_y].set_entry(W);
    int dir = pick_direction(valid_exits(start_x, start_y));
    data[start_x][start_y].add_exit(dir);
    pq.push(Path(start_x, start_y, dir));
}


void Maze::init_end() {
    data[end_x][end_y].set_type(End);
    data[end_x][end_y].set_entry(pick_direction(valid_exits(end_x, end_y)));
}


/* Return a set of all the valid directions we can exit from the node at x,y */
set<int> Maze::valid_exits(const int x, const int y) {
    // valid exit direction for a node means:
    // square we'd move into is blank
    // square we'd move into is not blank but contains our square as an exit direction
    set<int> valid_exits;
    
    assert(x >= 0 && x < size_x);
    assert(y >= 0 && y < size_y);
    
    // Check N
    if(y-1 >= 0 && data[x][y].get_entry() != N &&
       (data[x][y-1].get_type() == Blank
	|| contains<set<int>, int>(data[x][y-1].get_exits(), S)))
	valid_exits.insert(N);
    // Check S
    if(y+1 < size_y && data[x][y].get_entry() != S &&
       (data[x][y+1].get_type() == Blank
	|| contains(data[x][y+1].get_exits(), N)))
	valid_exits.insert(S);
    // Check W
    if(x-1 >= 0 && data[x][y].get_entry() != W &&
       (data[x-1][y].get_type() == Blank
	|| contains(data[x-1][y].get_exits(), W)))
	valid_exits.insert(W);
    // Check E
    if(x+1 < size_x && data[x][y].get_entry() != E &&
       (data[x+1][y].get_type() == Blank
	|| contains(data[x+1][y].get_exits(), E)))
	valid_exits.insert(E);
    
    return valid_exits;
}


int Maze::move_next_path() {
    // Pop the next Path off the queue
    // Determine the valid directions we can take from this path's coords
    // If this path's direction is not one of those valid directions, adjust the exit directions of this path's coords and return
    // If it is a valid direction, move into the next square and determine which exit directions to go
    if(pq.size() == 0)
	return -1;
    Path p = pq.front();
    pq.pop();
    int p_x = p.get_x();
    int p_y = p.get_y();
    int p_dir = p.get_dir();
    int n_x;
    int n_y;
    
    set<int> ve = valid_exits(p_x, p_y);
    if(!contains(ve, p_dir)) {
	data[p_x][p_y].remove_exit(p_dir);
	return 0;
    }
    if(p_dir == N) {
	n_x = p_x;
	n_y = p_y - 1;
    } else if(p_dir == S) {
	n_x = p_x;
	n_y = p_y + 1;
    } else if(p_dir == W) {
	n_x = p_x - 1;
	n_y = p_y;
    } else {
	n_x = p_x + 1;
	n_y = p_y;
    }
    
    assert(n_x >= 0 && n_x < size_x);
    assert(n_y >= 0 && n_y < size_y);
    if(data[n_x][n_y].get_type() != Blank) {
	if(Percentage(Probability_Split))
	    return 0;
	else {
	    // must undo the exit on the previous square. try to pick another direction instead.
/*	    if((data[p_x][p_y].get_exits()).size() > 1) {
		set<int> new_exits = data[p_x][p_y].get_exits();
		new_exits.erase(p_dir);
		int new_exit = pick_direction(new_exits);
		data[p_x][p_y].add_exit(new_exit);
		pq.push(Path(p_x, p_y, new_exit));
	    } */
	    data[p_x][p_y].remove_exit(p_dir);
	    return 0;
	}
    }
    
    data[n_x][n_y].set_type(Occupied);
    data[n_x][n_y].set_entry(opposite_direction(p_dir));
    
    // Determine whether we should go straight, turn, split, or dead end
    ve = valid_exits(n_x, n_y);
    if(ve.size() == 0)
	return 0;
    else if(Percentage(Probability_DeadEnd))
	return 0;
    else if(ve.size() == 1) {
	// Continue in the one valid direction
	
	int dir = *(ve.begin());
	data[n_x][n_y].add_exit(dir);
	pq.push(Path(n_x, n_y, dir));
	return 0;
    } else {
	if(Percentage(Probability_Turn)) {
	    // Turn
	    
	    if(ve.size() == 3 || (ve.size() == 2 && !contains(ve, opposite_direction(data[n_x][n_y].get_entry())))) {
		if(data[n_x][n_y].get_entry() == N || data[n_x][n_y].get_entry() == S) {
		    int dir = Percentage(50) ? W : E;
		    data[n_x][n_y].add_exit(dir);
		    pq.push(Path(n_x, n_y, dir));
		    return 0;
		} else {
		    int dir = Percentage(50) ? N : S;
		    data[n_x][n_y].add_exit(dir);
		    pq.push(Path(n_x, n_y, dir));
		    return 0;
		}
	    } else {
		for(set<int>::iterator i = ve.begin(); i != ve.end(); i++) {
		    if(*i != opposite_direction(data[n_x][n_y].get_entry())) {
			int dir = *i;
			data[n_x][n_y].add_exit(dir);
			pq.push(Path(n_x, n_y, dir));
			return 0;
		    }
		}
	    }
	} else if(Percentage(Probability_Split)) {
	    // Split in two directions
	    
	    if((ve.size() == 3 && Percentage(Probability_Split)) || ve.size() == 2) {
		// split in all possible directions (either two or three)
		for(set<int>::iterator i = ve.begin(); i != ve.end(); i++) {
		    data[n_x][n_y].add_exit(*i);
		    pq.push(Path(n_x, n_y, *i));
		}
		return 0;
	    } else {
		// Pick two of the three possible directions to split in
		int non_split_dir = pick_direction(ve);
		for(set<int>::iterator i = ve.begin(); i != ve.end(); i++) {
		    if(*i != non_split_dir) {
			data[n_x][n_y].add_exit(*i);
			pq.push(Path(n_x, n_y, *i));
		    }
		}
		return 0;
	    }
	} else {
	    // Just go in one direction, straight if possible
	    int dir;
	    
	    if(contains(ve, opposite_direction(data[n_x][n_y].get_entry())))
		dir = opposite_direction(data[n_x][n_y].get_entry());
	    else {
		// Pick a random direction of the valid ones
		dir = pick_direction(ve);
	    }
	    data[n_x][n_y].add_exit(dir);
	    pq.push(Path(n_x, n_y, dir));
	    return 0;
	    
	}
    }
}


/* Fill in all blank space in the maze */
int Maze::fill_blank_space() {
	bool found_blank_space = false;
	for(int y=0; y < size_y; y++) {
	    for(int x=0; x < size_x; x++) {
		if(data[x][y].get_type() == Blank) {
		    found_blank_space = true;
		    set<int> bordering_filled;
		    if(y-1 >= 0 && data[x][y-1].get_type() == Occupied)
			bordering_filled.insert(N);
		    if(y+1 < size_y && data[x][y+1].get_type() == Occupied)
			bordering_filled.insert(S);
		    if(x-1 >= 0 && data[x-1][y].get_type() == Occupied)
			bordering_filled.insert(W);
		    if(x+1 < size_x && data[x+1][y].get_type() == Occupied)
			bordering_filled.insert(E);
		    
		    if(bordering_filled.size() == 0)
			continue;
		    
		    int source_dir = pick_direction(bordering_filled);
		    if(source_dir == N) {
			data[x][y-1].add_exit(S);
			pq.push(Path(x, y-1, S));
		    } else if(source_dir == S) {
			data[x][y+1].add_exit(N);
			pq.push(Path(x, y+1, N));
		    } else if(source_dir == E) {
			data[x+1][y].add_exit(W);
			pq.push(Path(x+1, y, W));
		    } else {
			data[x-1][y].add_exit(E);
			pq.push(Path(x-1, y, E));
		    }
		    while(move_next_path() != -1);
		    return 0;
		}
	    }
	}
	if(found_blank_space == false)
	    return -1;
	else
	    return 0;
}


void Maze::print() {
    cout << "|";
    for(int x = 0; x < 2*size_x; x++)
	cout << "-";
    cout << "|" << endl;
    
    for(int y=0; y < size_y; y++) {
	cout << "|";
	for(int x = 0; x < size_x; x++) {
	    if(data[x][y].get_type() == Blank)
		cout << "x";
	    else
		cout << " ";
	    if(data[x][y].get_entry() == W || contains(data[x][y].get_exits(), E))
		cout << " ";
	    else
		cout << "|";
	}
	cout << "|" << endl;
	
	cout << "|";
	for(int x = 0; x < 2*size_x; x++)
	    cout << "-";
	cout << "|" << endl;
    }
    
    cout << "|";
    for(int x = 0; x < 2*size_x; x++)
	cout << "-";
    cout << "|" << endl;
}


void Maze::print_graphics(const gdImagePtr im, const int color, const int sz_x, const int sz_y) {
    for(int y=0; y < size_y; y++) {
	for(int x=0; x < size_x; x++) {
	    if(data[x][y].get_type() == Blank)
		gdImageFilledRectangle(im, x*sz_x+1, y*sz_y+1, (x+1)*sz_x, (y+1)*sz_y, color);
	    else {
		set<int> exits = data[x][y].get_exits();
		// Draw south borders
		if(data[x][y].get_type() != End && !contains(exits, S) && (y+1 == size_y || (y+1 < size_y && data[x][y+1].get_entry() != N &&
							     !contains(data[x][y+1].get_exits(), N))))
		    gdImageLine(im, x*sz_x, (y+1)*sz_y, (x+1)*sz_x, (y+1)*sz_y, color);
		// Draw east borders
		if(!contains(exits, E) && (x+1 == size_x || (x+1 < size_x && data[x+1][y].get_entry() != W &&
							     !contains(data[x+1][y].get_exits(), W))))
		    gdImageLine(im, (x+1)*sz_x, y*sz_y, (x+1)*sz_x, (y+1)*sz_y, color);
	    }
	}
    }
    gdImageLine(im, 0, sz_y, 0, size_y*sz_y, color);  // West border
    gdImageLine(im, 0, 0, size_x*sz_x, 0, color);  // North border
}



int opposite_direction(const int d) {
    if(d == N)
	return S;
    else if(d == S)
	return N;
    else if(d == W)
	return E;
    else if(d == E)
	return W;
    else
	return -1;
}


int pick_direction(const set<int>& s) {
    int pick_e = rand() % s.size();
    set<int>::iterator i;
    int j;
    for(i = s.begin(), j=0; i != s.end(); i++, j++)
	if(j == pick_e)
	    return *i;
}


int main(void) {
    int size_x, size_y;
    gdImagePtr im;
    FILE *pngout;
    int pix_size;
    cgicc::Cgicc cgi;
    cgicc::form_iterator form_x, form_y, form_pix, form_prob_de,
	form_prob_turn, form_prob_split, form_rand_seed, form_fill_iter;
    int rand_seed;
    int fill_iter;

    form_x = cgi.getElement("size_x");
    form_y = cgi.getElement("size_y");
    form_pix = cgi.getElement("pixels");
    form_prob_de = cgi.getElement("prob_deadend");
    form_prob_turn = cgi.getElement("prob_turn");
    form_prob_split = cgi.getElement("prob_split");
    form_rand_seed = cgi.getElement("rand_seed");
    form_fill_iter = cgi.getElement("fill_iter");

    size_x = form_x->getIntegerValue();
    size_y = form_y->getIntegerValue();
    pix_size = form_pix->getIntegerValue();
    Probability_DeadEnd = form_prob_de->getDoubleValue();
    Probability_Turn = form_prob_turn->getDoubleValue();
    Probability_Split = form_prob_split->getDoubleValue();
    rand_seed = form_rand_seed->getIntegerValue();
    fill_iter = form_fill_iter->getIntegerValue();

    if(rand_seed < 0)
	srand(time(0));
    else
	srand(rand_seed);

    if(size_x > Max_Size || size_y > Max_Size) {
	cout << "Content-Type: text/html" << endl << endl;
	cout << "Error: dimensions must be within " << Max_Size << " by " << Max_Size << endl;
	return -1;
    }

    Maze m(size_x, size_y);
    
    while(m.move_next_path() != -1);
    if(fill_iter < 0)
	while(m.fill_blank_space() == -1);
    else
	for(int i=0; i < fill_iter; i++)
	    m.fill_blank_space();
    
    im = gdImageCreate(pix_size*size_x+1, pix_size*size_y+1);
    int white = gdImageColorAllocate(im, 255,255,255);
    int black = gdImageColorAllocate(im, 0,0,0);
    m.print_graphics(im, black, pix_size, pix_size);
    cout << "Content-Type: image/png\r\n\r\n";
    gdImagePng(im, stdout);
    gdImageDestroy(im);
    
    return 0;
}