//TODO
//add sizeof() to show memory usage -- graph it
//add Table::next()
//destructor for Node
//add end pointer to Table

#include <iostream>
#include <string>
#include <stdlib.h>
#include <stdio.h>

//#include <ext/hash_map> -- too cool for STL

using std::cout;	using std::endl;
using std::string;

struct Board;
struct Table;

typedef enum Direction{Down=0,Right,Up,Left} Direction;
typedef enum Algorithm{AS=0,BFS,DFS} Algorithm;

const int N = 3;
static int (*heur_f)(int**) = NULL;//for A* only
static int (*hash_f)(Board*) = NULL;//for A* only
static int **goal_state;
static Algorithm alg;

//pass a string with error message and then terminates
void die_with_error(string s);
//swaps (i,j) with (x,y) on tile map
void swap_tiles(int **b,int i,int j,int x,int y);
//returns false if the empty tile can move up; otherwise true;
//CHANGES change state of board if it is a valid move; you must specify
//where the empty tile is (i,j) where both variables range from [0,N)
bool empty_up(int **board,int i,int j);
//similar logic as empty_up() but for down
bool empty_down(int **board,int i,int j);
bool empty_left(int **board,int i,int j);
bool empty_right(int **board,int i,int j);
//checks where a given tile map is solvable
bool solvable(int**);

//adds a child, a single Board* node, to parent; DFS adds it to front of
//list otherwise adds it at the end; if A*, then the function assumes parent
//list is already sorted with descending f()
Board* add_node(Board* list, Board* node);
//for all Boards in a and b, it will remove any matching nodes from b in a
//and return new b; a and b are lists
Board* filter(Board* a, Board* b);
//same as filter but find_me is a single node
Board* remove_node(Board* find_me,Board* list);
//prints a Board* linked list
void print_list(Board* b);
//prints the path followed from a Board; pass the terminal Board!
//b is the found goal state with direction, g is the initial state, c is the closed list.
void print_path(Board* b, Board* g, Table* c);


int heuristic_func(int** state){
	int cnt=0;

	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++){
			if(goal_state[i][j] != state[i][j]) cnt++;
		}

	return cnt;
}

//returns hash value for table from a given board state
int hash_func(Board*);

struct Board{
	Board(int**,int,Direction);
	//returns the f() value in f = g+h
	int f();
	//returns the g() value in f = g+h
	int g();
	//returns the h() value in f = g+h
	int h();
	//returns the direction the move was made to arrive to this state
	Direction direction();
	//prints the state and f,g,h,path values
	void print();
	//returns the array of the state, not f,g,h,path
	//remember to free after use
	int** array();
	//files in the variables passed on the coordinates where a tile T is;
	//both x and y are in [0,N); returns (-1,-1) if not found
	void tile_pos(int T,int* x,int* y);
	//returns pointer(Board*) to Board* element pointed by the current one
	Board* next();
	//allows you to update what next() returns which is a pointer to a Board
	void next(Board*);
	//returns true if both nodes have the same tile configuration; it does
	//not compare f,g,h, or path; otherwise, false
	bool same(Board*);
	//Returns the state in string form
	string deconstruct_state();

	friend int hash_func(Board* b);

	private:
	int x,y;
	Board* _next;
};

struct Table{
	//returns how many nodes there are
	int count;
	//prints all entries of a hash table
	//size of hash table is passed as parameter
	Table(int);
	//valid only for BFS DFS
	Table();
	//inserts a SINGLE board into the table
	void insert(Board*);
	//returns the next Board* element; NULL if none exists; automatically
	//returns appropriate Board* depending on whether BFS, DFS, or A*
	Board* next();
	//returns true if a given Board exists
	Board* exists(Board*);
	private:
	Board** t;
	int _n;
};

Board* Table::exists(Board* b){
	Board* iter;

	if(_n != -1)
		iter = t[hash_f(b)%_n];
	else
		iter = t[0];

	while(iter != NULL){
		if(iter->same(b))
			return iter;
		else
			iter = iter->next();
	}


	return NULL;
}

bool Board::same(Board* b){
	if(b == NULL) return false;

	if(x == b->x && ((y&0xF0000000) == (b->y&0xF0000000)))
			return true;

	return false;
}

Board* Table::next(){
	Board* b = NULL;//most legible node per algorithm

	if(_n != -1){
		int min = -1; //min. not yet found if it is == -1

		for(int i=0;i<_n;i++){
			Board* iter = t[i];

			//assuming list is in decreasing order
			if(iter != NULL){
				while(iter->next() != NULL) iter = iter->next();

				int f = iter->f();
				if(min == -1 || f < min){
					min = f;
					b = iter;
				}
			}

		}
		//remove the node from the t[i] list
		if(b != NULL){//a smallest node exists
			Board* n = new Board(*b);
			int hash_val = hash_f(b)%_n;
			t[hash_val] = remove_node(n,t[hash_val]);
			n->next(NULL);
			b = n;
		}
	}
	else{
		//whether BFS or DFS, first node is located at t[0] because insert()
		//inserts at front
		b = t[0];

		if(b == NULL)
			return NULL;
		else
			t[0] = t[0]->next();

		b->next(NULL);
	}

	if(b != NULL) count--;

	return b;
}

Table::Table(){
	_n = -1;
	t = new Board*[1];
	t[0] = NULL;
}

void Table::insert(Board *b){
	if(b == NULL) return;

	b->next(NULL);
	count++;
	if(_n != -1){
		int h = hash_f(b)%_n;
		t[h] = add_node(t[h],b);
	}
	else{
		t[0] = add_node(t[0],b);
	}
}

Table::Table(int n) : _n(n){
	t = new Board*[_n];

	for(int i=0;i<_n;i++)
		t[i] = NULL;
}

Board* Board::next(){return _next;}
void Board::next(Board* b){_next	=	b;}

void Board::tile_pos(int tile,int* x,int* y){
	int** state = this->array();

	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			if(state[i][j] == tile){
				*x = i;
				*y = j;
				return;
			}

	for(int i=0;i<N;i++)
		delete [] state[i];
	delete [] state;
}

Direction Board::direction(){

	switch(0x3&y){
		case Down: return Down; break;
		case Up: return Up; break;
		case Left: return Left; break;
		default: return Right;
	}

}

int Board::f(){
	return g()+h();
}

int Board::g(){
	return 0x1FFF&(y>>15);
}

int Board::h(){
	return 0x1FFF&(y>>2);
}

//print the state along with the f,g,h,path values
void Board::print(){
	int** state = this->array();

	cout << endl;
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			cout << state[i][j];

			if(state[i][j] < 10) cout << "  ";
			else cout << " ";
		}
		cout << endl;
	}

	if(alg == AS)
		cout << "f(" << f() << ") g(" << g() << ") h(" << h() << ") ";

	switch(direction()){
		case Up: cout << "Up"; break;
		case Down: cout << "Down"; break;
		case Left: cout << "Left"; break;
		case Right: cout << "Right"; break;
	}

	cout << endl;

	for(int i=0;i<N;i++)
		delete [] state[i];
	delete [] state;
}

string Board::deconstruct_state(){
	int** b = this->array();
	char* num;
	string state = "";

	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			if (i > 0 || j > 0) state += " ";
			sprintf(num,"%d",b[i][j]);
			state += num;
		}
	}
	return state;
}


//don't forget to delete array after finished with it
//returns NxN array
//contains hardcoded values
int** Board::array(){
	int **state;

	state = new int*[N];
	for(int i=0;i<3;i++)
		state[i] = new int[N];

	//first 8 numbers go into the first integer; 8 segements of 4-bits
	for(int i=0;i<8;i++)
		state[i/N][i%N] = (x>>(4*(7-i)))&0xF;

	//last number and g,h,path go into second integer
	state[2][2] = 0xF&(y>>28);

	return state;
}

//contains hardcoded values
Board::Board(int** state,int g,Direction path){
	next(NULL);
	int j;

	//first 8 numbers go into the first integer; 8 segements of 4-bits
	j=0;
	for(int i=0;i<8;i++)
		j = (j<<4)|(state[i/3][i%3]&0xF);

	x = j;

	//last number and f,g,h,path go into second integer
	j=0;
	int heur = heur_f(state);
	j = 0xF&state[2][2]; //last integer in array 4-bits
	j = (j<<13)|(0x1FFF&g); // g 8-bits
	j = (j<<13)|(0x1FFF&heur); // h 8-bits
	j = (j<<2)|(0x3&path); //path 2-bits

	y=j;
}

bool empty_up(int **board,int i,int j){
	if(i-1<0) return true;
	else swap_tiles(board,i-1,j,i,j);

	return false;
}

bool empty_down(int **board,int i,int j){
	if(i+1>=N) return true;
	else swap_tiles(board,i+1,j,i,j);

	return false;
}

bool empty_left(int **board,int i,int j){
	if(j-1<0) return true;
	else swap_tiles(board,i,j,i,j-1);

	return false;
}

bool empty_right(int **board,int i,int j){
	if(j+1>=N) return true;
	else swap_tiles(board,i,j+1,i,j);

	return false;
}

//psedo function
Board* expand(Board *p){
	Board* list = NULL;
	int x,y,cnt;//for coords for empty tile

	if(p == NULL) return NULL;

	//find the position of empty tile on parent board
	p->tile_pos(0,&x,&y);
	if(x == -1 || y == -1)
		die_with_error("tile_pos() returned values out of bounds");

	//copy parent state for use by a max of four children
	int*** state = new int**[4];
	for(int i=0;i<4;i++)
		state[i] = p->array();

	cnt = 0;
	//attempt to move empty tile for all four children; these functions
	//autmatically update the board if it is a valid move
	if(!empty_up(state[0],x,y))
		list = add_node(list,new Board(state[0],p->g()+1,Up));
	if(!empty_down(state[1],x,y))
		list = add_node(list,new Board(state[1],p->g()+1,Down));
	if(!empty_left(state[2],x,y))
		list = add_node(list,new Board(state[2],p->g()+1,Left));
	if(!empty_right(state[3],x,y))
		list = add_node(list,new Board(state[3],p->g()+1,Right));


	//free the 3d state array
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			delete [] state[i][j];

	for(int i=0;i<N;i++)
		delete [] state[i];

	delete [] state;

	return list;
}

Board* add_node(Board* p, Board* c){
	if(p == NULL) return c;
	else if(c == NULL) return p;


	c->next(NULL);

	if(alg == DFS){
		c->next(p);
		return c;
	}
	else if(alg == AS){
		//only check f() for first node only because we don't know whether
		//to return c or p
		Board *b = p;
		if(b->f() <= c->f()){
			c->next(b);
			return c;
		}
		else{
			while(b->next() != NULL && b->f() >= c->f())
				b = b->next();

			c->next(b->next());
			b->next(c);
			return p;
		}
	}
	else{
		Board *b = p;
		while(b->next() != NULL) b = b->next();
		b->next(c);
	}

	return p;
}

void swap_tiles(int **b,int i,int j,int x,int y){
	int t = b[x][y];
	b[x][y] = b[i][j];
	b[i][j] = t;
}

void die_with_error(string s){
	cout << "\nError: " << s << ". Terminating..." << endl;
	exit(1);
}

int hash_func(Board* b){
	int h = b->x;
	h = (h<<4)&((b->y&0xF0000000)>>28);
	return h;
}

Board* remove_node(Board* find_me,Board* list){
	Board *pp = NULL, *cp = list;
	//pp = previous pointer from list, cp = current pointer from list

	if(find_me == NULL || list == NULL) return list;

	while(cp != NULL){
		if(cp->same(find_me)){
			if(pp != NULL){
				pp->next(cp->next());
				delete cp;
				cp = pp->next();
			}
			else{
				Board* t = cp;
				list = list->next();
				delete t;
				cp = list;
			}
		}
		else{
			pp = cp;
			cp = cp->next();
		}
	}

	return list;
}

Board *filter(Board *hp,Board *succ){
	Board* pp = NULL, *cp = succ, *p = hp;
	//pp = previous pointer from succ list, cp = current pointer from succ
	//list , p = working pointer from hp list

	if(hp == NULL || succ == NULL) return succ;

	while(p != NULL){
		cp = succ;
		pp = NULL;

		while(cp != NULL){

			if(p->same(cp)){

				if(pp != NULL){//has a previous pointer
					pp->next(cp->next());
					delete cp;
					cp = pp->next();
				}
				else{
					Board* t = succ;
					succ = succ->next();
					delete t;
					cp = succ;
				}
			}
			else{
				pp = cp;
				cp = cp->next();
			}

		}

		p = p->next();
	}


	return succ;
}

bool solvable(int** state){
	if(state == NULL) return false;

	int cnt,agg[N*N];

	//aggregate into one a 1-d array
	cnt=0;
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++){
			if(state[i][j] == 0)
				continue;

			agg[cnt++] = state[i][j];
		}

	//count number of inversions
	cnt=0;
	for(int i=0;i<N*N-1;i++)
		for(int j=i+1;j<N*N-1;j++){
			if(agg[j]<agg[i])
				cnt++;
		}

//If the grid width is odd, then the number of inversions in a solvable situation is even.
//If the grid width is even, and the blank is on an even row counting from the bottom (second-last, fourth-last etc), then the number of inversions in a solvable situation is odd.
//If the grid width is even, and the blank is on an odd row counting from the bottom (last, third-last, fifth-last etc) then the number of inversions in a solvable situation is even.

	//we know N is odd
	if(cnt % 2 == 0) return true;

	return false;
}

void print_list(Board* b){
	while(b != NULL){
		b->print();
		b = b->next();
	}
}

void print_path(Board* b, Board* g, Table* c){
	int x, y;
	Direction d;
	string state;
	int** state_array;
//	FILE* solution;
//	solution = fopen ("solution.txt","w");
	while (!b->same(g)){
		state_array = b->array();
		state = b->deconstruct_state();
//		state += "\n";
//		fwrite(state.c_str(), 1, sizeof(state.c_str()), solution);
//		rewind(solution);
		cout<<"\n"<<state<<endl;
		d = b->direction();
		b->tile_pos(0, &x, &y);
		switch(d){
			case Down: empty_up(state_array, x, y); break;
			case Up: empty_down(state_array, x, y); break;
			case Left: empty_right(state_array, x, y); break;
			default: empty_left(state_array, x, y);
		}
		b = new Board(state_array, b->g() - 1, d);
		b->print();
		cout<<"\nhash: "<<hash_func(b)<<endl;
		printf("-------------------");
		b = c->exists(b);
		if (b == NULL) cout<<"b is NULL"<<endl;
	}
//		fclose(solution);
}

int main(int argc, char *argv[]){
	int** g= new int*[N];
	int** s= new int*[N];
	goal_state = g;

	for(int i=0;i<N;i++){
		g[i] = new int[N];
		s[i] = new int[N];
	}

	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++){
			g[i][j] = i*N+j;
			s[i][j] = i*N+j;
		}


	s[0][0] = 1;
	s[0][1] = 2;
	s[0][2] = 3;
	s[1][0] = 4;
	s[1][1] = 5;
	s[1][2] = 6;
	s[2][0] = 0;
	s[2][1] = 7;
	s[2][2] = 8;

	heur_f = &heuristic_func;
	hash_f = &hash_func;
	alg = AS;

	Board *goal = new Board(g,0,Down);
	Board *start = new Board(s,0,Down);

	//check solvability of both goal and start states
	if(!solvable(s) || !solvable(g))
		die_with_error("goal or initial state is unsolvable");

	Table* open = new Table(7919);
//	Table* open = new Table;
	Table* closed = new Table(7919);
	open->count = 0;
	closed->count = 0;

	open->insert(start);

	int iter=0;
	for(Board* i = open->next(); ; i = open->next()){
		if(i == NULL){
			if(open->exists(goal)){
				cout << "goal exists in open";
			}
			if(closed->exists(goal)){
				cout << "goal exists in closed";
			}
			die_with_error("no nodes remaining! BAD!");
			//insert this above into for loop
		}
		//expand node i; generates a linked list of successors
		Board* successors = expand(i);

		//for each Board in successor, check that it does not exist; if
		//it does, remove it from the successor list
		for(Board* j = successors; j != NULL; j = j->next()){
			if(open->exists(j)){
				Board* temp = new Board(*j);
				temp->next(NULL);
				successors = remove_node(temp, successors);
				delete temp;
			}

			if(closed->exists(j)){
				Board* temp = new Board(*j);
				temp->next(NULL);
				successors = remove_node(temp, successors);
				delete temp;
			}
		}

//		if(iter % 10000 == 0 || (closed->count+open->count) == 181420){
			cout << "/" <<string(20,'-') << endl;
			cout << "Iter : " << iter << " clos(" << closed->count
				<< ") open(" << open->count << ")" << endl;
			i->print();
			cout << string(20,'-') << endl;
			print_list(successors);
			cout << "\\" << string(20,'-') << endl;
//		}


		Board* k = successors;
		closed->insert(i);
		//for each of the remaining successors, insert them into open table
		while(k != NULL){

			if(goal->same(k)){
				print_path(k ,start, closed);
				cout << iter << endl;
				die_with_error("GOAL FOUND");
			}

			Board* n = k;
			k = k->next();
			n->next(NULL);
			open->insert(n);
		}

		//closed->insert(i);
		iter++;
	}

	return 0;
}