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

#include <iostream>
#include <string>
#include <stdlib.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);

//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!
void print_path(Board* b, Board* g){
}

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 true if the state of this board is solvable
    bool solvable();
    //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*);

    friend int hash_func(Board* b);

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

struct Table{
    //returns how many nodes there are
    int count;
    //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. does not "exist"

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

            if(iter != NULL){
                while(iter->next() != NULL) iter = iter->next();

                int f;
                if(min == -1 || (f=iter->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);
    }

    return b;
}

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

void Table::insert(Board *b){
    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;
}

//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();

            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;
}

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

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

    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] = 8;
    s[0][1] = 4;
    s[0][2] = 3;
    s[1][0] = 1;
    s[1][1] = 0;
    s[1][2] = 7;
    s[2][0] = 2;
    s[2][1] = 5;
    s[2][2] = 6;

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

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

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

    open->insert(start);

    int iter=0;
    for(Board* i = open->next(); i != NULL; i = open->next()){
        iter++;
        //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))
                successors = remove_node(j, successors);

            if(closed->exists(j))
                successors = remove_node(j, successors);
        }

        if(iter % 9000 == 0){
            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;
        //for each of the remaining successors, insert them into open table
        while(k != NULL){

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

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


        }

        closed->insert(i);
    }

    return 0;
}