/*
 * klotski.cpp
 *
 *
 */

#include "klotski.h"

string err_msg[4] = {"piece is correct", "piece has wrong dimensions", "piece has wrong direction", "piece is out of bounds"};

string piece_tag[] = {"1", "2", "3", "4", "5", "6", "7", "8", "9", "a", "b", "c",
                      "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o",
                      "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "A",
                      "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M",
                      "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y",
                      "Z"};

/* check if Z piece spans last column */
bool checkSoln(Grid grid)
{
    Piece tmp("");
    for (vector<Piece>::size_type ix = 0; ix != grid.getPieces()->size(); ++ix)
    {
        tmp = (*(grid.getPieces()))[ix];
        if (tmp.getName() == "Z")
            break;
    }

    if ( (tmp.getCol() + tmp.getW()) == (*(grid.getCols())+1) )
        return true;

    return false;
}

/* validate piece */
int checkPiece(int rows, int cols, Piece piece)
{
    /* wrong direction */
    if ( piece.getDir() != 'v' && piece.getDir() != 'h' && piece.getDir() != 'b')
    {
        return 2;
    }

    /* out of bonds */
    if ( (piece.getRow() + piece.getH()) > rows+1 || (piece.getCol() + piece.getW()) > cols+1)
        return 3;

    /* wrong dimensions */
    if ( (piece.getH() != 1) && (piece.getW() != 1) )
        return 1;

    return 0;
}

/* take in a grid and return a string representation of it */
string *fillBoard(Grid grid)
{
    int grid_h = *grid.getRows();
    int grid_w = *grid.getCols();
    string *board = new string[grid_h * grid_w + 1];
    int k;
    for (k = 0; k < grid_h * grid_w; k++)
        board[k] = ".";

    int i = 0;
    Piece tmp("");
    string name;
    int row;
    int col;
    int w;
    int h;
    char dir;
    int offset;

    for (vector<Piece>::size_type ix = 0; ix != grid.getPieces()->size(); ++ix, i++)
    {
        tmp = (*(grid.getPieces()))[ix];
        name = tmp.getName();
        row = tmp.getRow();
        col = tmp.getCol();
        w = tmp.getW();
        h = tmp.getH();
        dir = tmp.getDir();

        int j;
        offset = (grid_w * (row-1)) + col;
        if (w == 1)
        {
            for (j = 0; j < h; j++)
                board[offset + (j * grid_w) - 1] = name;
        }
        else if (h == 1)
        {
            for (j = 0; j < w; j++)
                board[offset - 1 + j] = name;
        }
        else
            cout << "oops in fillBoard(), height or width of a piece is not 1!\n";
    }

    board[grid_h * grid_w] = "";

    return board;
}

/* take 1D grid, create 1D representation of it, and print it */
void printGrid(Grid grid)
{
    int grid_h = *grid.getRows();
    int grid_w = *grid.getCols();
    string padding = string(grid_w + 1, '*');
    string *board = new string[grid_h * grid_w];
    int k;
    for (k = 0; k < grid_h * grid_w; k++)
        board[k] = ".";

    int i = 0;
    Piece tmp("");
    string name;
    int row;
    int col;
    int w;
    int h;
    char dir;
    int offset;

    for (vector<Piece>::size_type ix = 0; ix != grid.getPieces()->size(); ++ix, i++)
    {
        tmp = (*(grid.getPieces()))[ix];
        name = tmp.getName();
        row = tmp.getRow();
        col = tmp.getCol();
        w = tmp.getW();
        h = tmp.getH();
        dir = tmp.getDir();

        int j;
        offset = (grid_w * (row-1)) + col;
        if (w == 1)
        {
            for (j = 0; j < h; j++)
                board[offset + (j * grid_w) - 1] = name;
        }
        else if (h == 1)
        {
            for (j = 0; j < w; j++)
                board[offset - 1 + j] = name;
        }
        else
            cout << "oops in printGrid(), height or width of a piece is not 1!\n";
    }

    cout << padding << "*\n*";
    for (int k = 1; k <= grid_h * grid_w; k++)
    {
        cout << board[k-1];
        if (k % grid_w == 0)
            cout << "*\n*";
    }
    cout << padding << endl << endl;

    delete [] board;
}

/* load grid from a file */
Grid loadGrid(char **argv)
{
    FILE *fname = fopen(argv[1], "r");
    if (fname == NULL)
    {
        perror("fopen");
        exit(EXIT_FAILURE);
    }

    Grid grid;
    Piece piece_tmp("");

    /* used for line reading */
    size_t line_sz = 0;
    char *line = NULL;
    int matched_inputs = 0;

    if (getline(&line, &line_sz, fname) != -1)
        sscanf(line, "%d %d\n", grid.getRows(), grid.getCols());

    if (*grid.getRows() < 1 || *grid.getCols() < 1)
    {
        cout << "invalid grid dimensions, read in: " << *grid.getRows() << "h, "
             << *grid.getCols() << "w" << endl;
        exit(EXIT_FAILURE);
    }

    /* parse grid's dimensions */
    int piece_row = -1;
    int piece_col = -1;
    int piece_w = -1;
    int piece_h = -1;
    char piece_dir = 0;
    int line_cnt = 0;
    string piece_name;
    bool foundGoalPiece = false;
    int ret;
    int i;

    for (i = 0; getline(&line, &line_sz, fname) != -1; i++)
    {
        matched_inputs = sscanf(line, "%d %d %d %d %c\n", &piece_row,
                                &piece_col, &piece_w, &piece_h, &piece_dir);

        if (matched_inputs != 5)
        {
            cout << "failed to parse line " << i+2 << ", skipping: " << line;
            continue;
        }
        else if (!foundGoalPiece)
        {
            piece_name = string("Z");
            piece_tmp = Piece(piece_name, piece_row, piece_col, piece_w, piece_h, piece_dir);
            ret = checkPiece(*grid.getRows(), *grid.getCols(), piece_tmp);
            if (ret != 0)
            {
                cout << "failed to parse line " << i+2 << ", " << err_msg[ret] << endl;
                continue;
            }

            grid.getPieces()->push_back(piece_tmp);
            foundGoalPiece = true;
        }
        else
        {
            piece_name = string(piece_tag[line_cnt-1]);
            piece_tmp = Piece(piece_name, piece_row, piece_col, piece_w, piece_h, piece_dir);
            ret = checkPiece(*grid.getRows(), *grid.getCols(), piece_tmp);
            if (ret != 0)
            {
                cout << "failed to parse line " << i+2 << ", " << err_msg[ret] << endl;
                continue;
            }

            grid.getPieces()->push_back(piece_tmp);
        }

        line_cnt++;
    }

    cout << "info: read in " << line_cnt << " pieces" << endl << endl;
    fclose(fname);

    return grid;
}

/* can piece move to left? If so, have many spaces */
int canMoveLeft(string board[], int row_sz, int col_sz, Piece piece)
{
    int ret = 0;
    int i;
    int offset = ( ((piece.getRow() - 1 ) * col_sz) + piece.getCol() ) - 1;

    if (piece.getH() == 1)
    {
        if (!offset || (offset % col_sz == 0))
            return 0;

        while (board[offset-1] == ".")
        {
            offset--;
            ret++;

            if (offset % col_sz == 0)
                break;
        }

        return ret;
    }
    else if (piece.getW() == 1)
    {
        int *offset2 = new int[piece.getH()-1];

        for (i = 0; i < piece.getH(); i++)
            offset2[i] = (offset + (col_sz * i));
        //int offset2 = offset + col_sz; /* fix me later */

        if (!offset || (offset % col_sz == 0))
            return 0;

#if 0   /* XXX: unimplemented */
        int i;
        while(1)
            for (i = 0; i < piece.getH())
            {

            }
#endif

        while (board[offset-1] == ".")
        {
            for (i = 0; i < piece.getH(); i++)
            {
                if (board[offset2[i]-1] != ".")
                    goto end_tag;
            }

            offset--;
            for (i = 0; i < piece.getH(); i++)
                offset2[i] -= 1;

            ret++;

            if (offset % col_sz == 0)
                break;
        }

end_tag:
        return ret;
    }
    else
        cout << "oops in canMoveLeft(), height or width of a piece is not 1!\n";

    return 0;
}

/* can piece move to right? If so, have many spaces */
int canMoveRight(string board[], int row_sz, int col_sz, Piece piece)
{
    int ret = 0;
    int i;
    int offset = ( ((piece.getRow() - 1 ) * col_sz) + piece.getCol() ) - 1;

    if (piece.getH() == 1)
    {
        offset += piece.getW();
        offset--;

        if (!offset || ((offset+1) % col_sz == 0))
            return 0;

        while (board[offset+1] == ".")
        {
            offset++;
            ret++;

            if (offset % col_sz == 0)
                break;
        }

        return ret;
    }
    else if (piece.getW() == 1)
    {
        offset += piece.getW();
        offset--;

        int *offset2 = new int[piece.getH()-1]; /* FIXME: memory leaks */

        for (i = 0; i < piece.getH(); i++)
            offset2[i] = (offset + (col_sz * i));
        //int offset2 = offset + col_sz;  /* fix me later */

        if (!offset || ((offset+1) % col_sz == 0))
            return 0;

        while (board[offset+1] == ".")
        {
            for (i = 0; i < piece.getH(); i++)
            {
                if (board[offset2[i]-1] != ".")
                    goto end2_tag;
            }

            offset++;
            for (i = 0; i < piece.getH(); i++)
                offset2[i] += 1;

            ret++;

            if (offset % col_sz == 0)
                break;
        }

end2_tag:
        return ret;
    }
    else
        cout << "oops in canMoveRight(), height or width of a piece is not 1!\n";

    return 0;
}

/* can piece move up? If so, have many spaces */
int canMoveUp(string board[], int row_sz, int col_sz, Piece piece)
{
    int ret = 0;
    int i;
    int offset = ( ((piece.getRow() - 1 ) * col_sz) + piece.getCol() ) - 1;

    if (piece.getW() == 1)
    {
        if (!offset || offset < col_sz)
            return 0;

        while (board[offset-col_sz] == ".")
        {
            offset -= col_sz;
            ret++;

            if (offset-col_sz < 0)
                break;
        }

        return ret;
    }
    else if (piece.getH() == 1)
    {
        int *offset2 = new int[piece.getW()-1]; /* FIXME: memory leaks */

        for (i = 0; i < piece.getW(); i++)
            offset2[i] = offset + i;
        //int offset2 = offset + piece.getW() - 1; /* fix me later */

        if (!offset || offset < col_sz)
            return 0;

        while (board[offset-col_sz] == ".")
        {
            for (i = 0; i < piece.getW(); i++)
            {
                if (board[offset2[i]-col_sz] != ".")
                    goto end3_tag;
            }

            offset -= col_sz;
            for (i = 0; i < piece.getH(); i++)
                offset2[i] -= col_sz;

            ret++;

            if (offset-col_sz < 0)
                break;
        }

end3_tag:
        return ret;
    }
    else
        cout << "oops in canMoveUp(), height or width of a piece is not 1!\n";

    return 0;
}

/* can piece move down? If so, have many spaces */
int canMoveDown(string board[], int row_sz, int col_sz, Piece piece)
{
    int ret = 0;
    int i;
    int offset = ( ((piece.getRow() - 1 ) * col_sz) + piece.getCol() ) - 1;

    if (piece.getW() == 1)
    {
        if (piece.getH() != 1)
            offset = col_sz * piece.getH();

        if (offset + col_sz > row_sz * col_sz)
            return 0;

        while (board[offset+col_sz] == ".")
        {
            offset += col_sz;
            ret++;

            if (offset+col_sz > row_sz * col_sz)
                break;
        }

        return ret;
    }
    else if (piece.getH() == 1)
    {
        int *offset2 = new int[piece.getW()-1]; /* FIXME: memory leaks */

        for (i = 0; i < piece.getW(); i++)
            offset2[i] = offset + i;
        //int offset2 = offset + piece.getW() - 1; /* fix me later */

        if (offset + col_sz > row_sz * col_sz)
            return 0;

        while (board[offset+col_sz] == ".")
        {
            for (i = 0; i < piece.getW(); i++)
            {
                if (board[offset2[i]+col_sz] != ".")
                    goto end4_tag;
            }

            offset += col_sz;
            for (i = 0; i < piece.getH(); i++)
                offset2[i] += col_sz;

            ret++;

            if (offset+col_sz > row_sz * col_sz)
                break;
        }

end4_tag:
        return ret;
    }
    else
        cout << "oops in canMoveDown(), height or width of a piece is not 1!\n";

    return 0;
}

/* fill in a queue with grids to be checked */
int possibleMoves(Grid grid, queue<Grid> &kway)
{
    Piece tmp("");
    Piece tmp2("");
    string *filled = fillBoard(grid);
    char dir;
    int ret = 0;
    char move[100];
    int howMany = 0;

    int i;
    /* for all pieces in Grid grid */
    for (vector<Piece>::size_type ix = 0; ix != grid.getPieces()->size(); ++ix)
    {
        tmp = (*(grid.getPieces()))[ix];
        dir = tmp.getDir();

        /* check where piece can go and create a new grid */
        if (dir == 'h' || dir == 'b')
        {
            /* right */
            if (grid.getlastMoved() != 1)
            {
                ret = canMoveRight(filled, *grid.getRows(), *grid.getCols(), tmp);
                howMany += ret;

                for (i = 0; i < ret; i++)
                {
                    Grid new_grid = grid;
                    new_grid.setlastMoved(1);

                    tmp2 = (*(new_grid.getPieces()))[ix];
                    tmp2.setCol(tmp2.getCol() + (i+1));
                    (*(new_grid.getPieces()))[ix] = tmp2; /* update position */

                    /* update movement */
                    sprintf(move, "Piece %s right %d space(s)\n", tmp2.getName().c_str(), i+1);
                    new_grid.addMove(string(move));

#ifdef DEBUG
                    cout << "pushing new grid, \"" << tmp2.getName() << "\""
                         << " can move " << i+1 << " space(s)" << " to the right" << endl;
#endif
                    kway.push(new_grid);
                }
            }

            /* left */
            if (grid.getlastMoved() != 0)
            {
                ret = canMoveLeft(filled, *grid.getRows(), *grid.getCols(), tmp);
                howMany += ret;

                for (i = 0; i < ret; i++)
                {
                    Grid new_grid = grid;
                    new_grid.setlastMoved(0);

                    tmp2 = (*(new_grid.getPieces()))[ix];
                    tmp2.setCol(tmp2.getCol() - (i+1));
                    (*(new_grid.getPieces()))[ix] = tmp2; /* update position */

                    /* update movement */
                    sprintf(move, "Piece %s left %d space(s)\n", tmp2.getName().c_str(), i+1);
                    new_grid.addMove(string(move));

#ifdef DEBUG
                    cout << "pushing new grid, \"" << tmp2.getName() << "\""
                         << " can move " << i+1 << " space(s)" << " to the left" << endl;
#endif
                    kway.push(new_grid);
                }
            }
        }

        if (dir == 'v' || dir == 'b')
        {
            /* down */
            if (grid.getlastMoved() != 3)
            {
                ret = canMoveDown(filled, *grid.getRows(), *grid.getCols(), tmp);
                howMany += ret;

                for (i = 0; i < ret; i++)
                {
                    Grid new_grid = grid;
                    new_grid.setlastMoved(3);

                    tmp2 = (*(new_grid.getPieces()))[ix];
                    tmp2.setRow(tmp2.getRow() + (i+1));
                    (*(new_grid.getPieces()))[ix] = tmp2; /* update position */

                    /* update movement */
                    sprintf(move, "Piece %s down %d space(s)\n", tmp2.getName().c_str(), i+1);
                    new_grid.addMove(string(move));

#ifdef DEBUG
                    cout << "pushing new grid, \"" << tmp2.getName() << "\""
                         << " can move " << i+1 << " space(s)" << " down" << endl;
#endif
                    kway.push(new_grid);
                }
            }

            /* up */
            if (grid.getlastMoved() != 2)
            {
                ret = canMoveUp(filled, *grid.getRows(), *grid.getCols(), tmp);
                howMany += ret;

                for (i = 0; i < ret; i++)
                {
                    Grid new_grid = grid;
                    new_grid.setlastMoved(2);

                    tmp2 = (*(new_grid.getPieces()))[ix];
                    tmp2.setRow(tmp2.getRow() - (i+1));
                    (*(new_grid.getPieces()))[ix] = tmp2; /* update position */

                    /* update movement */
                    sprintf(move, "Piece %s up %d space(s)\n", tmp2.getName().c_str(), i+1);
                    new_grid.addMove(string(move));

#ifdef DEBUG
                    cout << "pushing new grid, \"" << tmp2.getName() << "\""
                         << " can move " << i+1 << " space(s)" << " up" << endl;
#endif
                    kway.push(new_grid);
                }
            }
        }

    }

    return howMany;
}