/* Lecture code 6.0
 *
 * Computer hearts simulation.
 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <deque>
#include <utility>
#include <cstdlib>
#include <string>
#include <ctime>
#include <sstream>
using namespace std;

/* Type: suitT
 * A type that stores the suit of a playing card.
 */
enum suitT {Hearts, Diamonds, Clubs, Spades};

/* Type: valueT
 * A type that stores the value of playing card.
 * Note that the values are sorted in increasing
 * order here, so you can compare cards by
 * value.
 */
enum valueT {Two, Three, Four, Five, Six, Seven,
             Eight, Nine, Ten, Jack, Queen, King,
			 Ace};

/* Type: cardT
 * A type that represents a playing card.
 */
struct cardT
{
	suitT suit;
	valueT value;
};

/* Type: deckT
 * A deque of cards.
 */
typedef deque<cardT> deckT;

/* The number of cards in each player's hand. */
const int NUM_CARDS = 13;

/* The number of players in this game. */
const int NUM_PLAYERS = 4;

/* The number of total points to play to. */
const int MAX_POINTS = 100;

/* The names of the players in this game. */
const string PLAYER_NAMES[] = {"Ada Lovelace",
                               "John von Neumann",
							   "Alan Turing",
							   "Alonzo Church"};

/* Type: playerT
 * A player in the game.
 */
struct playerT
{
	deckT hand;
	int pointsTotal;
	string name;
};


/* Randomize()
 * Seeds the randomizer so random shuffling will work
 * correctly.  Look into <cstdlib> and <ctime> for more
 * info on the functions here.
 */
void Randomize()
{
	srand((unsigned int)time(NULL));
}

/* GetLine()
 * Gets a string from the user.
 */
string GetLine()
{
	string result;
	getline(cin, result);
	return result;
}

/* PrintCard(cardT &card)
 * Prints a card's value and suit.
 */
void PrintCard(cardT &card)
{
	switch(card.value)
	{
	case Jack:
		cout << 'J'; break;
	case Queen:
		cout << 'Q'; break;
	case King:
		cout << 'K'; break;
	case Ace:
		cout << 'A'; break;
	default:
		cout << (card.value + 2);
	}
	
	cout << (char(card.suit + '\x03')) << ' ';
}

/* InitPlayers(players)
 * Initializes the players to have no points and the
 * correct name.
 */
void InitPlayers(vector<playerT> &players)
{
	for(vector<playerT>::iterator itr = players.begin();
		itr != players.end(); ++itr)
	{
		itr->pointsTotal = 0;
		itr->name = PLAYER_NAMES[itr - players.begin()];
	}
}

/* FillDeck(deck)
 * Fills the deck of cards with all 52 cards, in sorted
 * order.
 */
void FillDeck(deckT &deck)
{
	for(suitT suit = Hearts; suit <= Spades; suit = suitT(suit + 1))
		for(valueT value = Two; value <= Ace; value = valueT(value + 1))
		{
			cardT card;
			card.suit = suit;
			card.value = value;
			deck.push_back(card);
		}
}

/* GetWinningPlayerIndex(deck)
 * Returns the zero-based index of the player who
 * won the trick.
 */
int GetWinningPlayerIndex(deckT &playedCards)
{
	suitT toFollow = playedCards.front().suit;

	int index = 0;
	valueT value = Two;

	for(int i = 0; i < playedCards.size(); i++)
	{
		if(playedCards[i].suit == toFollow &&
			playedCards[i].value > value)
		{
			index = i;
			value = playedCards[i].value;
		}
	}

	return index;
}

/* GetPoints(trick)
 * Returns the number of points in the specified trick.
 */
int GetPoints(deckT &trick)
{
	int total = 0;
	for(deckT::iterator itr = trick.begin();
		itr != trick.end(); ++itr)
	{
		if(itr->suit == Hearts)
			total++;
		if(itr->suit == Spades && itr->value == Queen)
			total += 13;
	}

	return total;
}

/* PrintAllHands(players)
 * Prints out each player's hand.
 */
void PrintAllHands(vector<playerT> &players)
{
	for(int i = 0; i < players.size(); i++)
	{
		cout << players[i].name << " has ";
		for(int j = 0; j < players[i].hand.size(); j++)
			PrintCard(players[i].hand[j]);
		cout << endl;
	}
}

/* Randomize the cards in the deck using random_shuffle. */
void ShuffleDeck(deckT &deck)
{
	random_shuffle(deck.begin(), deck.end());
}

/* Compares two cards, first by suit, then by value. */
bool CompareTwoCards(cardT one, cardT two)
{
	if(one.suit < two.suit)
		return true;
	if(one.suit > two.suit)
		return false;
	return one.value < two.value;
}

/* Deals 13 cards to each player.  This function does not
 * modify the contents of the deck.
 */
void DealHands(deckT &deck, vector<playerT> &players)
{
	for(int i = 0; i < players.size(); i++)
	{
		// [13 * i, 13 * (i + 1) )
		copy(deck.begin() + 13 * i, deck.begin() + 13 * (i + 1),
			back_inserter(players[i].hand));
		sort(players[i].hand.begin(), players[i].hand.end(),
			 CompareTwoCards);
	}
}

/* Compares two cards by value only. */
bool CompareByValueOnly(cardT one, cardT two)
{
	return one.value < two.value;
}

/* Chooses the lowest card in the player's hand and plays it. */
void PlayFirstCard(deckT &trick, deckT &playerHand)
{
	deckT::iterator toPlay =
		min_element(playerHand.begin(), playerHand.end(), CompareByValueOnly);

	trick.push_back(*toPlay);
	playerHand.erase(toPlay);
}

/* Compares two cards, ignoring value. */
bool CompareBySuitOnly(cardT one, cardT two)
{
	return one.suit < two.suit;
}

/* Plays the lowest card that follows suit OR the highest card in the hand,
 * then plays it.
 */
void PlayFollowingCard(deckT &trick, deckT &playerHand)
{
	pair<deckT::iterator, deckT::iterator> allSuit = 
	equal_range(playerHand.begin(), playerHand.end(), trick[0], 
				CompareBySuitOnly);

	deckT::iterator toPlay;
	if(allSuit.first == allSuit.second)
		toPlay = max_element(playerHand.begin(), playerHand.end(),
				CompareByValueOnly);
	else
		toPlay = allSuit.first;

	trick.push_back(*toPlay);
	playerHand.erase(toPlay);
}

/* Plays a round of Hearts! */
void PlayRound(vector<playerT> &players)
{
	for(int i = 0; i < NUM_CARDS; i++)
	{
		deckT trick;
		for(int player = 0; player < players.size(); player++)
		{
			if(player == 0)
				PlayFirstCard(trick, players[player].hand);
			else
				PlayFollowingCard(trick, players[player].hand);

			cout << players[player].name << " played ";
			PrintCard(trick.back());
			cout << endl;
		}

		int winner = GetWinningPlayerIndex(trick);
		cout << players[winner].name << " takes the trick." << endl << endl;
		players[winner].pointsTotal += GetPoints(trick);
		rotate(players.begin(), players.begin() + winner, players.end());
	}
}

/* Determines whether a player has more than the maximum number of points. */
bool GameOver(vector<playerT> &players)
{
	for(vector<playerT>::iterator itr = players.begin();
		itr != players.end(); ++itr)
		if(itr->pointsTotal >= MAX_POINTS)
			return true;

	return false;
}

/* Compares two playerTs by name only. */
bool CompareByName(playerT one, playerT two)
{
	return one.name < two.name;
}

/* Prints the result of a round of cards. */
void PrintResult(vector<playerT> players)
{
	sort(players.begin(), players.end(), CompareByName);
	for(vector<playerT>::iterator itr = players.begin(); itr != players.end(); ++itr)
	{
		cout << itr->name << " has " << itr->pointsTotal << " points." << endl;
	}
}

int main()
{
	deckT deck;
	vector<playerT> players(NUM_PLAYERS);
	InitPlayers(players);
	Randomize();

	FillDeck(deck);

	while(!GameOver(players))
	{
		ShuffleDeck(deck);
		DealHands(deck, players);

		PrintAllHands(players);

		PlayRound(players);

		PrintResult(players);

		GetLine();
	}
	
	return 0;
}