//=========================================================================
#define PROGRAMMER "SOLUTIONS, NoFrills"
#define PROG_CODE  "soln"
#define COURSE     "ECE-1021"
#define YEAR       (2003)
#define TERM       "Fall"
#define SECTION    (0)
#define ASSIGNMENT "HW #6BA"
#define REVISION   (0)
#define TITLE      "Tic-Tac-Toe"
#define SUBTITLE   "Problem 8.10"
#define EMAIL      "wbahn@eas.uccs.edu"
#define FILENAME   "06b0soln.c"
//=========================================================================

// PROBLEM:
//
// Write a Tic Tac Toe game that has two panels on the screen.
// The left panel displays the present board and the right panel displays
// the board as it was on move N. The user can hit the '+' key to advance
// the right panel or the '-' key to step back one move. The move number
// should be displayed above each panel. To make a move, the user moves
// the screen cursor to the desired square using the {2,4,6,8} keys and
// "Enter" to make the move. Your program needs to be sure that it is a
// legal move (square not already taken).
//
// SOLUTION:
//
// We need some type of cursor, so we will create one that we can erase
// and display without affecting anything else (such as the mark from
// a prior move in that square.
//
// Our x's and o's will be made using astrisks. The cursor will be made
// using # signs in the spots used by neither the x nor the o.
//
//    *   *| *** |
//     * * |*   *|
//      *  |*   *|            Shows an x and an o with no cursor
//     * * |*   *|
//    *   *| *** |
//   -------------------      Horizontal line extends 1 space left
//         |     |            and right of pane boundary
//         |     |
//         |     |
//         |     |
//         |     |
//   -------------------
//    *   *| *** |
//     *#* |* # *|
//     #*# |*# #*|            Shows cursor on an x and on an o
//     *#* |* # *|
//    *   *| *** |
//
// Relative to the top left corner of the pane, the cell centers are
// at offsets of 2, 8, and 14.
//
// row or col   offset
//     0          2
//     1          8 (2+6)
//     2         14 (2+12)
//
// Therefore the offset is simply 2 + 6rc where rc is the row or col

// 1) TASK: Display Empty Pannels and Instructions
// 2) TASK: Initialize the game
// 3) LOOP:
// 3.1) TASK: Execute Command
// 3.1.2) TASK: Check for Global Command {x,n}
// 3.1.3) TASK: Check for Left Panel Command {2,4,6,8,\n}
// 3.1.4) TASK: Check for Right Panel Command {+.-}
// 3.2) TASK: Determine if there is a winner
// 3.3) TASK: Get Command from User
// 4) WHILE: Game not Over

//== INCLUDE FILES ========================================================
#include <stdio.h> // printf(), scanf()
#include <conio.h> // gotoxy(), kbhit(), getch()

//== MACRO DEFINITIONS ====================================================
#define LEFT (30)
#define RIGHT (60)
#define PANETOP (8)
#define FALSE (0)
#define TRUE (!FALSE)
#define SHOW ('#')
#define ERASE (' ')
#define MARK ('*')

#define PLAYER_X (1)
#define EMPTY    (0)
#define PLAYER_O (-1)

#define CellOffset(rc) (2 + 6*(rc))
#define Player(move) ( ((move)%2)? PLAYER_O : PLAYER_X )

//== TOP LEVEL SUPPORE FUNCTION PROTOTYPES ================================
void PrintHeader(void);
void PrintInstructions(void);
void PrintTicTacToePanel(int col);
void ClearBoard(int board[][3]);
void LeftPanelCursor(int x, int y, int mode);
int GetCommand(int gameover);
void ResetPane(int pane);
void Flush(int *sp);
int IsFull(int sp);
void Push(int stack[][2], int *sp, int x, int y);
int IsReadAtEnd(int sp, int read_sp);
int IsReadAtStart(int read_sp);
void ReadPush(int stack[][2], int *sp, int *read_sp);
void ReadPop(int stack[][2], int *read_sp);
int CheckForWinner(int board[][3]);

//== MAIN FUNCTION ========================================================
int main(void)
{
	int games, xwon, owon;
	int winner;
	int gameover, gamejustended;
	int catsgame;
	char command;

	int lpcx, lpcy;

	int board[3][3];
	int moves[9][2];
	int moves_sp;
	int history_sp;

	PrintHeader();
	printf("\n"); // Print a blank line

	// 1) TASK: Display Empty Panels and Instructions
	PrintInstructions();

	// 2) TASK: Initialize the game
	games = 0;
	xwon = 0;
	owon = 0;
	command = 'N';

	do
	{
		// TASK: Execute Command
		switch(command)
		{
			// ==============================================================
			// Global Commands
			// ==============================================================
			case 'X':
				// TASK: Process Exit command (done at bottom of loop)
				break;
			case 'N':
				// TASK: Process New Game command
				winner = 0;
				gameover = FALSE;
				PrintTicTacToePanel(LEFT);
				PrintTicTacToePanel(RIGHT);
				Flush(&moves_sp);
				Flush(&history_sp);
				ClearBoard(board);
				lpcx = lpcy = 1;
				LeftPanelCursor(lpcx, lpcy, SHOW);
				gotoxy(56, 24);
				printf("   ");
				break;
			// ==============================================================
			// TASK: Check for Left Panel Command
			// ==============================================================
			case '2':
				// TASK: Process Move Down command
				if(lpcy < 2)
				{
					LeftPanelCursor(lpcx, lpcy, ERASE);
					lpcy++;
					LeftPanelCursor(lpcx, lpcy, SHOW);
				}
				break;
			case '4':
				// TASK: Process Move Left command
				if(lpcx > 0)
				{
					LeftPanelCursor(lpcx, lpcy, ERASE);
					lpcx--;
					LeftPanelCursor(lpcx, lpcy, SHOW);
				}
				break;
			case '6':
				// TASK: Process Move Right command
				if(lpcx < 2)
				{
					LeftPanelCursor(lpcx, lpcy, ERASE);
					lpcx++;
					LeftPanelCursor(lpcx, lpcy, SHOW);
				}
				break;
			case '8':
				// TASK: Process Move Up command
				if(lpcy > 0)
				{
					LeftPanelCursor(lpcx, lpcy, ERASE);
					lpcy--;
					LeftPanelCursor(lpcx, lpcy, SHOW);
				}
				break;
			case '\n':
				// TASK: Process Make Move command
				if(EMPTY == board[lpcx][lpcy])
				{
					board[lpcx][lpcy] = Player(moves_sp);
					Push(moves, &moves_sp, lpcx, lpcy);
				}
				break;
			// ==============================================================
			// TASK: Check for Right Panel Command
			// ==============================================================
			case '+':
				// TASK: Process Game History Forward command
				if(!IsReadAtEnd(moves_sp, history_sp))
					ReadPush(moves, &moves_sp, &history_sp);
				break;
			case '-':
				// TASK: Process Game History Back command
				if(!IsReadAtStart(history_sp))
					ReadPop(moves, &history_sp);
				break;
		}
		//==================================================================
		// TASK: Determine if game is over
		//==================================================================
		winner = CheckForWinner(board);
		if(!gameover)
		{
			gameover = gamejustended = (IsFull(moves_sp)) || (winner);
		}

		catsgame = (gameover) && (!winner);

		if(gamejustended)
		{
			LeftPanelCursor(lpcx, lpcy, ERASE);
			games++;
			if(PLAYER_X == winner)
			{
				xwon++;
				gotoxy(50, 12);
				printf("%3i", xwon);
				gotoxy(56, 24);
				printf("X");
			}
			if(PLAYER_O == winner)
			{
				owon++;
				gotoxy(50, 17);
				printf("%3i", owon);
				gotoxy(56, 24);
				printf("O");
			}
			if(catsgame)
			{
				LeftPanelCursor(0, 0, 'C');
				LeftPanelCursor(1, 0, 'A');
				LeftPanelCursor(2, 0, 'T');
				LeftPanelCursor(0, 1, 'G');
				LeftPanelCursor(0, 2, 'A');
				LeftPanelCursor(1, 2, 'M');
				LeftPanelCursor(2, 2, 'E');
				gotoxy(50, 22);
				printf("%3i", games - (xwon+owon));
				gotoxy(56, 24);
				printf("CAT");
			}
			gamejustended = FALSE;
		}


		//==================================================================
		// TASK: Get Command from User
		//==================================================================
		command = GetCommand( (IsFull(moves_sp)) || (winner) );

	} while('X' != command);

	return(0);
}

//== SUPPORT FUNCTIONS ====================================================
void PrintHeader(void)
{
	printf("========================================"
			 "=======================================\n");
	printf("Course....... %s-%i (%s %i)\n", COURSE, SECTION, TERM, YEAR);
	printf("Programmer... %s (%s)\n", PROGRAMMER, PROG_CODE);
	printf("Assignment... %s (Rev %i) (Source Code in %s)\n",
		ASSIGNMENT, REVISION, FILENAME);
	printf("Description.. %s\n", TITLE);
	printf("              %s\n", SUBTITLE);
	printf("========================================"
			 "=======================================\n");

	return;
}

//== LOWER LEVEL FUNCTION PROTOTYPES ======================================
void MakeMark(int col, int x, int y, int player, int mode);

//== TOP LEVEL SUPPORT FUNCTION DEFINITIONS ===============================

// FUNCTION: PrintInstructions()
//
// This function provides the user with the information needed to enter
// the data properly.
//

void PrintInstructions(void)
{
	printf(" To Move Left Pane Cursor\n");
	printf(" \n");
	printf("           UP\n");
	printf("           '8'\n");
	printf("  LEFT  '4'   '6'  RIGHT\n");
	printf("           '2'\n");
	printf("          DOWN\n");
	printf(" \n");
	printf(" Make Move:....... Enter\n");
	printf(" \n");
	printf(" History Foward:.... '+'\n");
	printf(" History Backward:.. '-'\n");
	printf(" \n");
	printf(" New Game:.......... 'n'\n");
	printf(" Exit:.............. 'x'\n");
	printf(" \n");

	gotoxy(49, 10);
	printf("won by X:");
	gotoxy(49, 15);
	printf("won by O:");
	gotoxy(48, 20);
	printf("won by Cat:");
	gotoxy(48, 24);
	printf("WINNER:");


	return;
}

void 	PrintTicTacToePanel(int col)
{
	int row;

	for(row = 8; row < PANETOP + 3*5 + 2; row++)
	{
		gotoxy(col-1, row);
		printf("      |     |      ");
	}
	gotoxy(col-1, PANETOP+5);
	printf("------+-----+------");
	gotoxy(col-1, PANETOP+11);
	printf("------+-----+------");

	if(LEFT == col)
	{
		gotoxy(LEFT+4, PANETOP+17);
		printf("GAME PANE");
	}

	if(RIGHT == col)
	{
		gotoxy(RIGHT+2, PANETOP+17);
		printf("HISTORY PANE");
	}

	return;
}

void ClearBoard(int board[][3])
{
	int row, col;

	for(row = 0; row < 3; row++)
		for(col = 0; col < 3; col++)
			board[row][col] = EMPTY;

	return;
}

int GetCommand(int gameover)
{
	int command;

	do
	{
		while(kbhit())
		  getch();
		while(!kbhit())
			;
		command = getch();
		switch(command)
		{
			// Global Commands
			case 'x':	command = 'X';
			case 'X':	break;

			case 'n':	command = 'N';
			case 'N':	break;

			// Right Panel Commands
			case '+':
			case '-':	break;

			// Left Panel Commands
			case 13 :	command = '\n'; // Carriage Return
			case '2':
			case '4':
			case '6':
			case '8':
							if(gameover) // Ignore Left Panel Commands
								command = '\0';
							break;

			default :	command = '\0';
		}
	} while ('\0' == command);

	return(command);
}

void LeftPanelCursor(int x, int y, int mode)
{
	int r, c;

	r = PANETOP + CellOffset(y);
	c = LEFT + CellOffset(x);

	gotoxy(c,r-1);
	putch(mode);
	gotoxy(c-1,r);
	putch(mode);
	gotoxy(c+1,r);
	putch(mode);
	gotoxy(c,r+1);
	putch(mode);

	return;
}

void ResetPane(int pane)
{
	PrintTicTacToePanel(pane);
	return;
}

void Flush(int *sp)
{
	*sp = 0;
}

int IsFull(int sp)
{
	return(!(sp<9));
}

void Push(int stack[][2], int *sp, int x, int y)
{
	stack[*sp][0] = x;
	stack[*sp][1] = y;
	MakeMark(LEFT, x, y, Player(*sp), MARK);
	(*sp)++;

	return;
}

int IsReadAtEnd(int sp, int read_sp)
{
	return(!(read_sp < sp));
}

int IsReadAtStart(int read_sp)
{
	return(!(0<read_sp));
}

void ReadPush(int stack[][2], int *sp, int *read_sp)
{
	if(!IsReadAtEnd(*sp, *read_sp))
	{
		MakeMark(RIGHT, stack[*read_sp][0], stack[*read_sp][1],
			Player(*read_sp), MARK);
		(*read_sp)++;
	}
	return;
}

void ReadPop(int stack[][2], int *read_sp)
{
	if(!IsReadAtStart(*read_sp))
	{
		(*read_sp)--;
		MakeMark(RIGHT, stack[*read_sp][0], stack[*read_sp][1],
			Player(*read_sp), ERASE);
	}
	return;
}

//== LOWER LEVEL SUPPORT FUNCTION DEFINITIONS =============================
void MakeMark(int col, int x, int y, int player, int mode)
{
	int r, c;

	r = PANETOP + CellOffset(y);
	c = col + CellOffset(x);

	switch(player)
	{
		case PLAYER_X:
			gotoxy(c,r);
			putch(mode);
			gotoxy(c-1,r-1);
			putch(mode);
			gotoxy(c-1,r+1);
			putch(mode);
			gotoxy(c+1,r-1);
			putch(mode);
			gotoxy(c+1,r+1);
			putch(mode);
			gotoxy(c-2,r-2);
			putch(mode);
			gotoxy(c-2,r+2);
			putch(mode);
			gotoxy(c+2,r-2);
			putch(mode);
			gotoxy(c+2,r+2);
			putch(mode);
			break;
		case PLAYER_O:
			gotoxy(c-2,r-1);
			putch(mode);
			gotoxy(c-2,r);
			putch(mode);
			gotoxy(c-2,r+1);
			putch(mode);
			gotoxy(c+2,r-1);
			putch(mode);
			gotoxy(c+2,r);
			putch(mode);
			gotoxy(c+2,r+1);
			putch(mode);
			gotoxy(c-1,r+2);
			putch(mode);
			gotoxy(c,r+2);
			putch(mode);
			gotoxy(c+1,r+2);
			putch(mode);
			gotoxy(c-1,r-2);
			putch(mode);
			gotoxy(c,r-2);
			putch(mode);
			gotoxy(c+1,r-2);
			putch(mode);
			break;
	}

	return;
}

int IsWinner(int a, int b, int c)
{
	// If PLAYER_X has all three, then (3*PLAYER_X)/3 = PLAYER_X
	// If PLAYER_O has all three, then (3*PLAYER_O)/3 = PLAYER_O
	// Since PLAYER_X and PLAYER_O are additive inverses and
	// since EMPTY squares are equal to zero, any nonwinning combination
	// will yield zero due to integer division.

	return((a+b+c)/3);
}

int CheckForWinner(int board[][3])
{
	int row, col, winner;

	//=====================================================================
	// TASK: See if a winner across
	//=====================================================================
	for(row = 0; row < 3; row++)
	{
		winner =IsWinner(board[row][0],board[row][1],board[row][2]);
		if(winner)
			return(winner);
	}
	//=====================================================================
	// TASK: See if a winner down
	//=====================================================================
	for(col = 0; col < 3; col++)
	{
		winner =IsWinner(board[0][col],board[1][col],board[2][col]);
		if(winner)
			return(winner);
	}
	//=====================================================================
	// TASK: See if a winner diagonally
	//=====================================================================
	{
		winner =IsWinner(board[0][0],board[1][1],board[2][2]);
		if(winner)
			return(winner);

		winner =IsWinner(board[2][0],board[1][1],board[0][2]);
		if(winner)
			return(winner);
	}
	return(EMPTY);
}

//       =================================================================
// 3.2.4) TASK: Perform Post Game Tasks
//       =================================================================
// 3.2.4.1) TASK: Display winner on screen
// 3.2.4.2) TASK: Update Cumulative Statistics