/*
 * Copyright (c) 2000, 2001, 2002, 2003, 2004, 2005, 2008, 2009
 *	The President and Fellows of Harvard College.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE UNIVERSITY AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE UNIVERSITY OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

/*
 * These are some constants we use in our program.
 * EMPTY is used to indicate empty spaces in the board.
 * X_MARKER and O_MARKER are used to indicate where each
 *	players has moved
 * DIM indicates the size of the board.  For now
 * we assume a conventional 3x3 playing board.
 *
 * This should work once the basic system calls are complete.
 */

#include <stdio.h>
#include <unistd.h>

#define NEWLINE 012
#define	EMPTY		0
#define X_PLAYER	1
#define	O_PLAYER	2
#define X_MARKER	1
#define	O_MARKER	2
#define DIM		3
#define	DIMCHAR		"2"
#define MAXSTRING	100

typedef enum { FALSE, TRUE } bool;

/* Function Declarations */
bool ask_yesno(const char *msg);
bool do_move(int player);
void initialize_board(void);
bool is_win(int x, int y);
int  read_string(char *buf, int length);
void print_board(void);
void print_instructions(void);
bool win_column(int y, int marker);
bool win_diag_left(int x, int y, int marker);
bool win_diag_right(int x, int y, int marker);
bool win_row(int x, int marker);
bool Strcmp(const char *a, const char *b);


/*
 * The board is gloabally defined.
 */
int board[DIM][DIM];

/* Console I/O routines */

int
main()
{
	bool win = FALSE;
	int move, max_moves;
	int player;

	print_instructions();
	max_moves = DIM * DIM;	/* Maximum number of moves in a game */

	while (TRUE) {
		initialize_board();
		for (move = 1; move <= max_moves; move++) {
			player = move % 2 == 0 ? 2 : 1;
			win = do_move(player);
			print_board();
			if (win) {
				printf("Player %d, you WON!\n\n", player);
				break;		/* out of for loop */
			}
		}
		/*
		 * If we got here by falling through the loop, then it is a
		 * tie game.
		 */
		if (!win)
			printf("Tie Game!\n\n");
		if (!ask_yesno("Do you wish to play again?"))
			break;			/* out of while loop */
	}
	return 0;
}

/*
 * print_instructions
 * Displays the instructions for the game.
 * Input
 *	None
 * Output
 *	None
 * Error
 *	None
 */
void
print_instructions(void)
{
	printf("Welcome to tic-tac-toe!\n");
	printf("Player 1 always plays X and player 2 always play O\n");
	printf("Good luck!\n\n\n");
}

void
/*
 * print_board
 * Display the DIM by DIM board.
 * Input
 *	None.
 * Output
 *	None.
 * Errors
 *	None.
 */
print_board(void)
{
	int i, j;

	/* Print labels across the top */
	printf("\n    0  1  2\n");

	for (i = 0; i < DIM; i++) {
		/* Print row labels */
		printf(" %d ", i);
		for (j = 0; j < DIM; j++) {
			switch (board[i][j]) {
				case EMPTY: printf("   "); break;
				case X_MARKER: printf(" X "); break;
				case O_MARKER: printf(" O "); break;
				default: printf("???"); break;
			}
		}
		printf("\n");
	}
	printf("\n");
}

/*
 * ask_yesno (taken from histo.c)
 * This function prints out the message and asks the user to respond
 * with either a yes or a no.  It continues asking the questions until
 * a valid reply is encountered and returns TRUE/FALSE indicating
 * the answer (True for yes, false for no).
 *
 * Input
 *	Question to be asked.
 * Output
 *	TRUE if response is yes
 *	FALSE if response is no
 * Error
 *	None
 */
bool
ask_yesno(const char *msg)
{
	char answer[MAXSTRING];

	while (TRUE) {
		printf("%s [yes/no] ", msg);
		if (read_string(answer, MAXSTRING) < 0)
			return(FALSE);
		if (Strcmp(answer, "yes"))
			return(TRUE);
		else if (Strcmp(answer, "no"))
			return(FALSE);
		else
			printf("Please answer either yes or no\n");
	}
}

/*
 * do_move
 * Processes one player move.  The player enters a row and column
 * and we have to determine if the square is valid (on the board)
 * and that there is no mark already there.  We continue to ask
 * for row/column pairs until we receive a valid combination.
 * Then we mark the board, check for a win, and return.
 *
 * Input
 *	player		Indicates which player (1 or 2) is moving
 * Output
 *	TRUE if this move won the game.
 *	FALSE if this move did not win the game.
 * Error
 *	None
 */
bool
do_move(int player)
{
	int x, y;
	bool first;
	char answer[MAXSTRING];
	char cx;

	first = TRUE;
	printf("Player %d (%c), your move\n", player, 
	       player == X_PLAYER ? 'X' : 'O');
	
	while (TRUE) {
		printf("Which row [0-%d]: ", DIM-1);
		if (read_string(answer, MAXSTRING) < 0)
			return(FALSE);
		cx = answer[0];
		x = cx - '0';
		if (x < 0 || x >= DIM) {
			printf("Invalid row; must be >= 0 and < %d\n", DIM-1);
			continue;
		}
		printf("Which column [0-%d]: ", DIM-1);
		if (read_string(answer, MAXSTRING) < 0)
			return(FALSE);
		cx = answer[0];
		y = cx - '0';
		if (y < 0 || y >= DIM) {
			printf("Invalid column; must be >= 0 and < %d\n",
				DIM-1);
			continue;
		}

		if (board[x][y] != EMPTY) {
			printf("That location is occupied; please try again\n");
			print_board();
		} else
			break;
	}
	board[x][y] = player == X_PLAYER ? X_MARKER : O_MARKER;

	return(is_win(x, y));

}

/*
 * is_win
 * Checks if the move into position x, y created a tic-tac-toe.
 * There are four possible ways to win -- horizontal, vertical,
 * and the two diagonals; check each one using a separate routine.
 * 
 * Four routines for checking the wins are:
 * win_row	The horizontal spots are all the same as this current mark.
 * win_column	The vertical spots are all the same as this current mark.
 * win_diag_left	The diagonal spots from left to right are all the
 * 			same as the current mark.
 * win_diag_right	The diagonal spots from right to left are all the
 * 			same as the current mark.
 *
 * Input (for all routines)
 *	x x coordinate
 *	y y coordinate
 *	marker the value just placed on the board.
 * Output
 *	TRUE if player won
 *	FALSE otherwise
 */
bool
is_win(int x, int y)
{
	int marker;

	marker = board[x][y];

	/*
	 * Note that C "short circuit evaluation".  As soon as any one
	 * of these functions returns TRUE, we know that the expression
	 * is true.  Therefore, we can return TRUE without executing
	 * any of the other routines.
	 */
	return(win_row(x, marker) || win_column(y, marker) ||
	    win_diag_left(x, y, marker) || win_diag_right(x, y, marker));
}

/*
 * Four helper functions for determining a win.
 */
bool
win_column(int y, int marker)
{
	int i;
	for (i = 0; i < DIM; i++)
		if (board[i][y] != marker)
			return(FALSE);
	return(TRUE);
}

bool
win_row(int x, int marker)
{
	int i;
	for (i = 0; i < DIM; i++)
		if (board[x][i] != marker)
			return(FALSE);
	return(TRUE);
}	

bool
win_diag_left(int x, int y, int marker)
{
	int i;

	/* Check that move is on the diagonal */
	if (x != y)
		return(FALSE);

	for (i = 0; i < DIM; i++)
		if (board[i][i] != marker)
			return(FALSE);
	return(TRUE);
}

bool
win_diag_right(int x, int y, int marker)
{
	int i;

	/* Check that move is on the diagonal */
	if (x + y != DIM - 1)
		return(FALSE);
	for (i = 0; i < DIM; i++)
		if (board[i][DIM - 1 - i] != marker)
			return(FALSE);
	return(TRUE);
}

void
initialize_board(void)
{
	int i, j;

	for (i = 0; i < DIM; i++)
		for (j = 0; j < DIM; j++)
			board[i][j] = EMPTY;
}

int
read_string(char *buf, int length)
{
	int	char_read;
	int	i;

	i = 0;
	while ((char_read = getchar()) != EOF && char_read != NEWLINE && 
	    i < length) {
		buf[i] = (char) char_read;
		i++;
		putchar(char_read);
	}

	if (char_read == EOF)
		return(-1);

	/*
	 * If the input overflows the buffer, just cut it short
	 * at length - 1 characters.
	 */
	if (i >= length)
		i--;
	buf[i] = 0;
	return(i);
}

bool
Strcmp(const char *a, const char *b)
{
	if (a == NULL)
		return(b == NULL);
	if (b == NULL)
		return(FALSE);

	while (*a && *b)
		if (*a++ != *b++)
			return(FALSE);

	return(*a == *b);

}