#include <stdio.h>
#ifdef __GNUC__
#include "clib.h"
#endif
#include "othello.h"
#include "global.h"
#include "io.h"


/* Forward declarations. */
bool     can_move();
void     check_stability();
bool     stable_half_row();



/*
 * Return TRUE if it is impossible to place a piece of any color
 * into STATE, otherwise return FALSE.
 *
 * Actually, the game may have ended without this function
 * detecting it, but this is taken care of otherwise. This should be
 * a pretty good heuristic, though.
 */

bool
game_ended(state)
State   *state;
{
    return  EMPTY_SQLIST(state->neighbors);
}



/* ==================== Moves in a state ======================== */


/*
 * Return TRUE if the player with the color COLOR can move to the
 * position SQ in STATE. Otherwise, return FALSE.
 */

bool
can_move(state, sq, color)
State    *state;
Square   sq;
Color    color;
{
    Color    *board;
    Square   sq1;
    Color    piece;
    int      dir;
    int      i;

    board = state->board;
    if (board[sq] != EMPTY)
	return FALSE;
    
    for (i = 0; i < 8; ++i) {
	dir = all_directions[i];
	sq1 = sq + dir;
	if (board[sq1] != OTHER(color))
	    continue;

	/* Check a direction for turnable pieces. */
	while (TRUE) {
	    sq1 += dir;
	    piece = board[sq1];
	    if (piece == color) {
		/* We have found the end of a turnable row!! */
		return TRUE;
	    }

	    if (piece != OTHER(color))
		break;
	}
    }

    return FALSE;
}



/*
 * Do a move in STATE to the square SQ for the player COLOR,
 * and record all state changes (number of stable pieces and  the
 * neighbor list) if the move is allowed. Return a boolean,
 * telling if the move was legal.
 */

bool
do_move(state, sq, color)
State    *state;
Square   sq;
Color    color;
{
    Color     *board;
    Sqqueue   stablequeue;
    Square    sq1;
    bool      some_stable;	/* TRUE if there are any stable pieces. */
    bool      legal_move;
    Color     piece;
    int       dir;
    int       i;

    board = state->board;
    reset_queue(&stablequeue);
    some_stable =
	state->mystable != 0 || state->yourstable != 0
	|| sq == 11 || sq == 18 || sq == 81 || sq == 88;

    legal_move = FALSE;
    for (i = 0; i < 8; ++i) {
	dir = all_directions[i];
	sq1 = sq + dir;
	if (board[sq1] != OTHER(color))
	    continue;
	
	/* Check a direction for turnable pieces. */
	while (TRUE) {
	    sq1 += dir;
	    piece = board[sq1];
	    if (piece == color) {
		/* We have found the end of a turnable row!! */
		legal_move = TRUE;
		dir = -dir;
		sq1 += dir;
		
		/* queue the outmost element in this direction */
		if (some_stable)
		    queue(&stablequeue, sq1);
		
		/* turn the pieces on the way back */
		while (sq1 != sq) {
		    board[sq1] = color;
		    sq1 += dir;
		}
		break;
	    }
	    if (piece != OTHER(color))
		break;
	}
    }

    /* If there was a legal move, the update the lists. */
    if (legal_move) {
	board[sq] = color;
	if (some_stable)
	    queue(&stablequeue, sq);

	/* Delete sq from the list of neighbors. */
	delete_element(state->neighbors, sq);

	/* Put all empty positions that surround sq into the */
	/* list of neighbors. */
	for (i = 0; i < 8; ++i) {
	    dir = all_directions[i];
	    sq1 = sq + dir;
	    if (state->board[sq1] == EMPTY)
		add_element(state->neighbors, sq1);
	}
	check_stability(state, &stablequeue);
    }
    
    return legal_move;
}



/*
 * Take a state, a square and a (possibly empty) queue of squares
 * that may have become stable on the move to SQ. If the queue is
 * not empty, then go through all positions in it and check for
 * every position if it has become stable. If so, queue the positions 
 * adjacent to the new stable piece on STABLEQUEUE. Continue until the 
 * queue is empty.
 *
 * Record also in STATE the number of pieces which became stable.
 *
 * footnote: A stable piece is one that can never again be turned,
 *           such as a piece in a corner.
 */

void
check_stability(state, stablequeue)
State     *state;
Sqqueue   *stablequeue;
{
    Square   stablesquare;
    int      stablerows;
    Color    *board;
    Color    color;
    int      dir;
    Square   sq1;
    int      i;
    
    board = state->board;
    while (!emptyqueue(stablequeue)) {

	/* A piece is stable if either it is adjacent to a stable piece*/
	/* of the same color, or there is no empty position to put a new */
	/* piece on in the row, in all four main directions. */

	stablesquare = dequeue_first(stablequeue);
	color = board[stablesquare];
        stablerows = 0;
	for (stablerows = 0, i = 0; stablerows == i && i < 4; ++i) {
	    dir = directions[i];
	    if ( board[stablesquare + dir] == BORDER
		|| board[stablesquare - dir] == BORDER
		|| (board[stablesquare + dir] == color
		    && member(state->stablepieces, stablesquare + dir))
		|| (board[stablesquare - dir] == color
		    && member(state->stablepieces, stablesquare - dir))
		|| ( stable_half_row(state, board, stablesquare, dir) 
		    && stable_half_row(state, board, stablesquare, -dir)) ) {
		stablerows++;
	    }
	}

	/* If the piece became stable, queue the live pieces around it */
	/* and record the piece in STATE. */
	if (stablerows == 4) {
	    add_element(state->stablepieces, stablesquare);
	    if (color == MYCOLOR)
		state->mystable++;
	    else
		state->yourstable++;

	    /* Queue the squares around the new stable square. */
	    for (i = 0; i < 8; ++i) {
		dir = all_directions[i];
		sq1 = stablesquare + dir;
		if ((board[sq1] == MYCOLOR || board[sq1] == YOURCOLOR)
		    && !member(state->stablepieces, sq1))
		    queue(stablequeue, sq1);
	    }
	}
    }
}



/*
 * Check if a piece at the position SQ is impossible to turn
 * from a certain direction. Return TRUE if this is so, otherwise
 * return FALSE.
 */
 
bool
stable_half_row(state, board, sq, dir)
State    *state;
Color    *board;
Square   sq;
int      dir;
{
    sq += dir;
    while (board[sq] != EMPTY && board[sq] != BORDER) {
	if (member(state->stablepieces, sq))
	    return TRUE;
	sq += dir;
    }
    return FALSE;
}



/*
 * Return all legal moves for COLOR in STATE. Return also the number
 * of legal moves in NUM_MOVES.
 */

void
get_legal_moves(state, color, legal_moves, num_moves)
State    *state;
Color    color;
Sqlist   *legal_moves;
int      *num_moves;
{
    sl_traverse(pp);
    Square   sq;

    *num_moves = 0;
    RESET_SQLIST(*legal_moves);
    for_all_in_sqlist(state->neighbors,pp,sq) {
	if ( can_move(state, sq, color) ) {
	    add_element(*legal_moves, sq);
	    ++*num_moves;
	}
    }
}



/*
 * Return the number of legal moves that the side COLOR has in STATE.
 */

int
num_legal_moves(state, color)
State   *state;
Color   color;
{
    int      legal_moves;
    Square   sq;
    sl_traverse(pp);

    legal_moves = 0;
    for_all_in_sqlist(state->neighbors,pp,sq) {
	if (can_move(state, sq, color))
	    ++legal_moves;
    }

    return legal_moves;
}


/* ======================== State ============================ */


/*
 * Put the start configuration into 'state'. This means empty the
 * lists, put a border the board, and put the four starting pieces
 * on it.
 */

void
resetstate(state)
State   *state;
{
    int     i;
    int     j;
    Color   white_player;
    static Square   startneighbors[] =
	{SQ(3,3),SQ(3,4),SQ(3,5),SQ(3,6),SQ(4,3),SQ(4,6),
	 SQ(5,3),SQ(5,6),SQ(6,3),SQ(6,4),SQ(6,5),SQ(6,6)};

    /* Set the border of the board to the color BORDER. */
    for (i = 0; i < 10; ++i) {
	state->board[SQ(i, 0)] = BORDER;
	state->board[SQ(i, 9)] = BORDER;
	state->board[SQ(0, i)] = BORDER;
	state->board[SQ(9, i)] = BORDER;
    }

    /* Set the interior of the board to the color EMPTY. */
    for (i = 1; i <= 8; ++i)
	for (j = 1; j <= 8; ++j)
	    state->board[SQ(j, i)] = EMPTY;

    /* Put the four start pieces on the board. */
    white_player = (mycolor == WHITE) ? MYCOLOR : YOURCOLOR;
    state->board[SQ(4, 4)] = white_player;
    state->board[SQ(5, 4)] = OTHER(white_player);
    state->board[SQ(4, 5)] = OTHER(white_player);
    state->board[SQ(5, 5)] = white_player;

    /* Add the squares outside the start configuration to the */
    /* list of neighbour squares. */
    RESET_SQLIST(state->neighbors);
    for (i = 0; i < 12; ++i)
	add_element(state->neighbors, startneighbors[i]);

    RESET_SQLIST(state->stablepieces);
    state->mystable = 0;
    state->yourstable = 0;
}



/*
 * Count and report the numbers of my and your pieces.
 */

void
count_pieces(state, mypieces, yourpieces)
State   *state;
int     *mypieces;
int     *yourpieces;
{
    int      my;
    int      yours;
    Square   sq;
    int      i, j;

    my = 0;
    yours = 0;

    for (i = 1; i <= 8; ++i) {
	for (j = 1; j <= 8; ++j) {
	    sq = SQ(i, j);
	    if (state->board[sq] == MYCOLOR)
		my++;
	    else if (state->board[sq] == YOURCOLOR)
		yours++;
	}
    }

    *mypieces = my;
    *yourpieces =  yours;
}