#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
using namespace std;

const char PLAYER_SYMBOL = 'X';
const char PC_SYMBOL = 'O';
const char DEFAULT_SYMBOL = '-';

class TicTacToe
{
private:
	vector <int> freeNodes; // the free nodes
	vector <int> usedNodes; // the used nodes
	char board [3] [3]; // set the board

public:
	void setBoard () // set the board to empty
	{
		for (int i = 0; i < 3; i++)
		{
			for (int j = 0; j < 3; j++)
			{
				board  [j] = '-';
			}
		}
	}

	void setFreeNodes ()
	{
		for (int i = 1; i <= 9; i++)
		{
			freeNodes.push_back (i);
		}
	}

	void printBoard () // print the board on the screen
	{
		cout << "\n";
		for (int i = 0; i < 3; i++)
		{
			for (int j = 0; j < 3; j++)
			{
				cout << board  [j] << " ";
			} 
			cout << "\n";
		}
	}
	int getNode ()
	{	
		int node;
		cout << "\n" << "Enter a number from 1-9: ";
		cin >> node;
		return node;
	}
	bool checkInput (int node)
	{
		vector <int>::iterator it;

		for (it = freeNodes.begin(); it < freeNodes.end(); it++)
		{
			if (node == *it)
			{
				return true;
			}
		}
		cout << "\n" << "Invalid input.";
		return false;
	}
	void applyInputToBoard (int node, bool playsP1, bool playsPC)
	{
		int i, j;
		if (node % 3 != 0)
		{
			i = node / 3;
			j = node % 3 - 1;
		}
		else
		{
			i = node / 3 - 1;
			j = 2;
		}

		if (playsP1 == true)
			board  [j] = PLAYER_SYMBOL; // ('X')
		else
			board  [j] = PC_SYMBOL; // ('O')
	}
	void undoInputToBoard (int node) // undo the pc's move (see pcNode)
	{
		int i, j;
		if (node % 3 != 0)
		{
			i = node / 3;
			j = node % 3 - 1;
		}
		else
		{
			i = node / 3 - 1;
			j = 2;
		}
		
		// undo the move
		board  [j] = DEFAULT_SYMBOL; // ('-')
	}
	void addRemoveNodes (int node)
	{
		usedNodes.push_back (node); // add the node in usedNodes
		sort (usedNodes.begin(), usedNodes.end() );

		//remove the node from freeNodes
		int position = 0;
		vector <int>::const_iterator it;
		for (it = freeNodes.begin(); it < freeNodes.end(); it++)
		{
			if (*it == node)
			{
				break;
			}

			position ++; // position is the position of the number (node) in the vector
		}
		
		/*when (*it = node), position isn't increased, because it breaks the loop. But that doesn't matter because when  erase, I have to delete -1
		 because it starts from the the first element. position is already -1 so I don't have to subtract anything.
		eg it should have been "freeNodes.erase (freeNodes.begin() + position - 1);", but position is -1 from the 
		node's position, so, it's ok.*/
		
		freeNodes.erase (freeNodes.begin() + position);
		sort (freeNodes.begin(), freeNodes.end() );
	}
	int checkWin ()
	{
		enum Won
		{
			none = 0,
			winsP1 = 1,
			winsPC = 2,
			tie = 3
		};

		/* This is how the board is.
		 (i, j)		 (i, j+1)	 (i, j+2) 
		(i+1, j)	(i+1, j+1)	(i+1, j+2)
		(i+2, j)	(i+2, j+1)	(i+2, j+2)
		*/

		//horizontal
		for (int i = 0; i < 3; i++)
		{
			int j = 0;
				
			if (board [j] == board [j+1] && board [j] == board [j+2])
			{
				if (board [j] == PLAYER_SYMBOL)
					return winsP1;
				else if (board [j] == PC_SYMBOL)
					return winsPC;
			}
		}

		//vertical
		for (int j = 0; j < 3; j++)
		{
			int i = 0;

			if (board [j] == board [i+1][j] && board [j] == board [i+2][j])
			{
				if (board [j] == PLAYER_SYMBOL)
					return winsP1;
				else if (board [j] == PC_SYMBOL)
					return winsPC;
			}
		}

		//diagonal
		int i = 0, j = 0;
		// 1 - 5 - 9
		if (board [j] == board [i+1][j+1] && board [j] == board [i+2][j+2])
		{
			if (board [j] == PLAYER_SYMBOL)
				return winsP1;
			else if (board [j] == PC_SYMBOL)
				return winsPC;
		}
		// 3 - 5 - 7
		if (board [j+2] == board [i+1][j+1] && board [j+2] == board [i+2][j])
		{
			if (board [j+2] == PLAYER_SYMBOL)
				return winsP1;
			else if (board [j+2] == PC_SYMBOL)
				return winsPC;
		}

		if (freeNodes.empty() == true)
			return tie;
		else
			return none;
	}
	int pcNode ()
	{
		vector <int>::iterator it = freeNodes.begin();

		// for every free node, check IF CAN WIN
		for (it = freeNodes.begin(); it < freeNodes.end(); it++)
		{
			bool winsP1, winsPC;

			applyInputToBoard (*it, false, true);

			int win = checkWin(); // check if this node is a winning node
			if (win == 1)
				winsP1 = true;
			else if (win == 2)
				winsPC = true;

			if (winsPC == true) // if this is a winning move for the pc, return the value
				return *it;
			else // if not, undo the move :)
			{
				undoInputToBoard (*it);
			}
		}
		/* -------------------------------------------------------------------------------------------------------------*/
		srand (static_cast <unsigned int> (time(NULL)));	
		// for every free node, check IF THE PLAYER CAN WIN (if he can, block him)
		int block;
		if (usedNodes.size() <= 4) //the pc will block until x nodes are used, then will have 60% to block			
			block = 1; //it will always block when <= x nodes have been used
		else if (usedNodes.size() <= 6)
			block = 1 + rand() % 80; // when the nodes used are 5 or 6, the pc has more chance to block than after
		else
			block = 1 + rand() % 100;

		int blockChance;
		if (board [1][1] == PLAYER_SYMBOL)
			blockChance = 70; // if the player has the middle node, the PC has more chance to block him (plays smarter)
		else
			blockChance = 60;

		//->
		if (block <= blockChance)
		{
			for (it = freeNodes.begin(); it < freeNodes.end(); it++)
			{
				bool winsP1, winsPC;

				applyInputToBoard (*it, true, false);

				int win = checkWin(); // check if this node is a winning node
				if (win == 1)
					winsP1 = true;
				else if (win == 2)
					winsPC = true;

				if (winsP1 == true) // if this is a winning move for the player, block him
					return *it;
				else // if not, undo the move :)
				{
					undoInputToBoard (*it);
				}
			}
		}
		// -----------------------------------------------------------------------------------------------------------
		//if the middle node is free, apply node
		int chance = 1 + rand() % 100;
		if (usedNodes.size() == 1)
		{
			if (chance <= 60)
			{
				for (it = freeNodes.begin(); it < freeNodes.end(); it++)
				{
					if (*it == 5)
						return *it;
				}
			}
		}
		else // if usedNodes > 1
		{
			for (it = freeNodes.begin(); it < freeNodes.end(); it++)
			{
				if (*it == 5)
					return *it;
			}
		}
		
		// if the player chooses the middle node, then the pc chooses a node in a corner
		random_shuffle (freeNodes.begin(), freeNodes.end() );
		if (board [1][1] == PLAYER_SYMBOL) 
		{
			for (it = freeNodes.begin(); it < freeNodes.end(); it++)
			{
				if ( (*it == 1) || (*it == 3) || (*it == 7) || (*it == 9) )
					return *it;
			}
		}

		//-----------------------------------------------------------------------------------------------------------
		//else choose a random node
		int node;
		int randomNode = 1 + rand() % 9;
		
		it = freeNodes.begin();

		while (it < freeNodes.end() )
		{
			if (randomNode == *it) // if node is free
			{
				int i = randomNode;
				return randomNode;
			}
			
			it++;

			if (it == freeNodes.end() ) // if the node is not in freeNodes (if it's not free), repeat again
			{
				it = freeNodes.begin();
				randomNode = 1 + rand () % 9;
			}
		}

		node = randomNode;
		return node;
	}
	void print()
	{
		cout << "\n" << "Used nodes: ";
		vector <int>::const_iterator it;
		for (it = usedNodes.begin(); it < usedNodes.end(); it++)
		{
			cout << *it << " ";
		}

		cout << "\n" << "Free nodes: ";
		for (it = freeNodes.begin(); it < freeNodes.end(); it++)
		{
			cout << *it << " ";
		}

		cout << "\n";
	}
};

int main()
{
	cout << "Tic Tac Toe" << "\t" << "[by Minas Mina]"
		 << "\n" << "You: X" << "\t" << "PC: O" << "\n";

	TicTacToe game; // create an object for the class

	game.setBoard(); // set the board
	game.setFreeNodes();

	bool playsP1 = true, playsPC = false;
	bool winsP1 = false, winsPC = false, tie = false;

	while ( (winsP1 == false) && (winsPC == false) && (tie == false) )
	{
		if (playsP1 == true)
		{
			int node;
			bool acceptInput = false;
			
			while (acceptInput == false)
			{	
				node = game.getNode();
				acceptInput = game.checkInput (node); // check if the node is free	
			}
			game.addRemoveNodes (node);
			game.applyInputToBoard (node, playsP1, playsPC); //update the board	
			
			int win = game.checkWin();
			if (win == 1)
				winsP1 = true;
			else if (win == 3)
				tie = true;

			game.printBoard();
			playsP1 = false;
			playsPC = true;
			//game.print(); // // prints the vectors
		}

		if (winsP1 == true || tie == true)
			break;
		cout << "\n--------------------------------------------------------------------------\n";
		
		if (playsPC == true)
		{	
			int node = game.pcNode();
			cout << "\n" << "PC plays " << node << "\n";
			game.addRemoveNodes (node);
			game.applyInputToBoard (node, playsP1, playsPC); //update the board

			int win = game.checkWin();

			if (win == 1)
				winsP1 = true;
			else if (win == 2)
				winsPC = true;
			else if (win == 3)
				tie = true;

			game.printBoard();
			playsP1 = true;
			playsPC = false;
			//game.print(); // prints the vectors
			cout << "\n--------------------------------------------------------------------------\n";
		}
	}

	if (winsP1 == true)
		cout << "\n" << "->You win!!";
	else if (winsPC == true)
		cout << "\n" << "->You lose..";
	else
		cout << "\n" << "->Tie..";

	cout << "\n";
	system ("PAUSE");
	return 0;
}