// CARD PACK INFRASTRUCTURE
// ````````````````````````

var TEAM_RED    = 0;
var TEAM_BLUE   = 1;
var TEAM_GREEN  = 2;
var TEAM_YELLOW = 3;

var SUIT_HEARTS   = 3;
var SUIT_DIAMONDS = 2;
var SUIT_CLUBS    = 1;
var SUIT_SPADES   = 0;

var FACE_ACE   = 12; // ace-high for numerical comparisons
var FACE_KING  = 11;
var FACE_QUEEN = 10;
var FACE_JACK  = 9;
var FACE_TEN   = 8;
var FACE_NINE  = 7;
var FACE_EIGHT = 6;
var FACE_SEVEN = 5;
var FACE_SIX   = 4;
var FACE_FIVE  = 3;
var FACE_FOUR  = 2;
var FACE_THREE = 1;
var FACE_TWO   = 0;

var deck_create = function() {
	var ret = [];
	for (var card_id = 0; card_id < (4*13); card_id++) {
		ret.push(card_id);
	}
	deck_shuffle_inplace(ret);
	return ret;
};

var deck_shuffle_inplace = function(deck) {
	for (var i = 0, e = deck.length; i != e; ++i) {
		var source_idx = i;
		var dest_idx = Math.floor(Math.random() * deck.length);
		
		var tmp = deck[dest_idx];
		deck[dest_idx] = deck[source_idx];
		deck[source_idx] = tmp;
	}
};

var card_suit = function(card_id) {
	return Math.floor(card_id / 13); // 0..3
};

var card_face = function(card_id) {
	return Math.floor(card_id % 13); // 0-indexed
};

var card_is = function(card_id, suit, face) {
	return card_suit(card_id) == suit && card_face(card_id) == face;
};

var card_name_face = function(face) {
	switch(face) {
		case FACE_ACE:   return 'Ace';
		case FACE_TWO:   return 'Two';
		case FACE_THREE: return 'Three';
		case FACE_FOUR:  return 'Four';
		case FACE_FIVE:  return 'Five';
		case FACE_SIX:   return 'Six';
		case FACE_SEVEN: return 'Seven';
		case FACE_EIGHT: return 'Eight';
		case FACE_NINE:  return 'Nine';
		case FACE_TEN:   return 'Ten';
		case FACE_JACK:  return 'Jack';
		case FACE_QUEEN: return 'Queen';
		case FACE_KING:  return 'King';
	}
};

var card_name_suit = function(suit) {
	switch(suit) {
		case SUIT_HEARTS:   return 'Hearts';
		case SUIT_DIAMONDS: return 'Diamonds';
		case SUIT_CLUBS:    return 'Clubs';
		case SUIT_SPADES:   return 'Spades';
	}
};

var card_name = function(card_id) {
	if (card_is(card_id, SUIT_SPADES, FACE_QUEEN)) {
		return "** THE QUEEN OF SPADES **";
	} else {
		return card_name_face(card_face(card_id)) + " of " + card_name_suit(card_suit(card_id));
	}
};


// GAME-AGNOSTIC INFRASTRUCTURE
// ````````````````````````````


var GameState = function() {
	this.moveHistory = [];
};
GameState.prototype.clone = function() {
	var ret = new GameState();
	ret.moveHistory = this.moveHistory.slice(0);
	return ret;
};
GameState.prototype.applyMove = function(move) {
	this.moveHistory.push(move);
};
GameState.prototype.getNextPlayerID = function() {
	throw new Error("Game not loaded");
};
GameState.prototype.evaluatePosition = function() {
	// determine who's winning, even mid-round
	// return { TEAM_RED: number, ... }
	throw new Error("Game not loaded");
};
GameState.prototype.gameHasEnded = function() {
	throw new Error("Game not loaded");
};
GameState.prototype.evaluatePositionOnBehalfOf = function(team_id) {
	var team_scores = this.evaluatePosition();
		
	// Turn the team scores into a single +/- number.
	var our_score = team_scores[team_id];
	
	var other_scores = [];
	
	for (var tid in team_scores) {
		if (tid != team_id) {
			other_scores.push( team_scores[tid] );
		}
	}
	
	var other_players_max  = Math.max.apply(null, other_scores);
	var other_players_sum  = other_scores.reduce(function(a, b) { return a + b; }, 0);	
	var other_players_mean = other_players_sum / other_scores.length;
	
	// Positive if we're winning, negative if we're losing.
	// This is accurate but naive, it'd be better to return how many stddev's we're ahead/behind
	
	return (our_score - other_players_max);
};

//

var Move = function(player_id) {
	this.player_id = player_id;
	// Anything else goes - 500/hearts have only a single card, but KNA could have multiple, shouldn't matter in general
};

//

var Player = function() {
	this.cards     = []; // private
	this.player_id = 0; // public
	this.team_id   = TEAM_RED; // public
};

Player.prototype.enumerateLegalMoves = function(gamestate) {
	// use this.cards;
	throw new Error("Game not loaded");
};
Player.prototype.buildMentalModelOfOtherPlayers = function(gamestate) {
	throw new Error("Game not loaded");
	// use gamestate.moveHistory;
	// return [null (self), Player, Player, Player] with probably-wrong card information
};
Player.prototype.determineMove = function(gamestate, recurse_limit, score_on_behalf_of_team_id) {
	var avail_moves = this.enumerateLegalMoves(gamestate);
	if (! avail_moves.length) {
		return null;
	}
	
	var nextPlayer = null;
	if (recurse_limit > 0) {
		nextPlayer = this.buildMentalModelOfOtherPlayers(gamestate)[ gamestate.getNextPlayerID() ];
		// n.b. that took into account recursive calls should have removed cards from players' hands
	}
	
	var best_move = null;
	var best_score = -Infinity;
	for(var i = 0, e = avail_moves.length; i < e; ++i) {
		
		var proposed_gamestate = gamestate.clone();
		proposed_gamestate.applyMove( avail_moves[i] );
		
		var move_score = proposed_gamestate.evaluatePositionOnBehalfOf(this.team_id);
		
		
		if (recurse_limit > 0 && ! proposed_gamestate.gameHasEnded()) {
			
			// depth-first search
			var recurse_move_arr = nextPlayer.determineMove(proposed_gamestate, recurse_limit - 1, score_on_behalf_of_team_id); 
			
			// It's possible the game hasn't ended yet, but there would be no more moves from this player
			if (recurse_move_arr != null) {
				// use the score from recursion, but, we need to return our own move to get to this score
				move_score = recurse_move_arr[1]; 
			}
			
		}
		
		if (move_score > best_score) {
			best_score = move_score;
			best_move = avail_moves[i];
		}
		
	}
	
	// The best_score determined what move *this player* would have made. But we were asked to determine
	//  the score on behalf of someone else
	if (this.team_id != score_on_behalf_of_team_id) {
		var temp_gs = gamestate.clone();
		temp_gs.applyMove(best_move);
		best_score = temp_gs.evaluatePositionOnBehalfOf( score_on_behalf_of_team_id ); // overwrite
	}
	
	return [best_move, best_score];
};


// HEARTS
// ``````

Player.prototype.enumerateLegalMoves = function(gamestate) {
	// use this.cards;
	
	// HEARTS {{{
	
	// We could play any card, with some exceptions
	var play_options = this.cards.slice(0); // clone
	var leading = (gamestate.moveHistory.length % 4) == 0;
	
	// If hearts aren't broken, we can't lead them
	if (leading) {
		var hearts_broken = false;
		for(var i = 0; i < gamestate.moveHistory.length; i += 4) { // leading moves only
			if ( card_suit(gamestate.moveHistory[i].card_id) == SUIT_HEARTS ) {
				hearts_broken = true;
			}
		}
		if (! hearts_broken) {
			play_options = play_options.filter(function(card_id) {
				return card_suit(card_id) != SUIT_HEARTS;
			});
		}
	}
	
	// No point cards on the first round
	if (gamestate.moveHistory.length < 4) {
		play_options = play_options.filter(function(card_id) {
			return (
				card_suit(card_id) != SUIT_HEARTS &&
				!card_is(card_id, SUIT_SPADES, FACE_QUEEN)
			);
		});
	}
	
	// Follow suit if we can
	if (! leading) {
		var lead_move = gamestate.moveHistory[ Math.floor(gamestate.moveHistory.length / 4)*4 ];
		
		var follow_suit_options = play_options.filter(function(card_id) {
			return card_suit(card_id) == card_suit(lead_move.card_id)
		});
		if (follow_suit_options.length) {
			play_options = follow_suit_options;
		}
	}
	
	// If there were no legal moves, gotta break a rule, any card goes i guess
	if (! play_options.length) {
		play_options = this.cards.slice(0); // clone
	}
	
	// Build \Move objects for return
	var ret = [];
	for(var i = 0; i < play_options.length; ++i) {
		var move = new Move();
		move.player_id = this.player_id;
		move.card_id = play_options[i];
		ret.push(move);
	}
	return ret;
	// }}}
};

Player.prototype.buildMentalModelOfOtherPlayers = function(gamestate) {
	var retn = hearts_create_players();
	
	// Start out by assuming anyone could have any card
	for (var i = 0; i < 4; ++i) {
		retn[i].cards = deck_create();
	}
	
	// Go through the move history...
	for (var i = 0; i < gamestate.moveHistory.length; ++i) {
		var played_card_id   = gamestate.moveHistory[i].card_id;
		var played_player_id = gamestate.moveHistory[i].player_id;
	
		var is_lead_card = (i % 4) == 0;
		if (is_lead_card) {
			var last_lead_card = played_card_id;
		}
		
		// Once a move has been made, nobody has that card any more
		for (var j = 0; j < 4; ++j) {
			retn[j].cards = retn[j].cards.filter(function(card_id) {
				return card_id != played_card_id;
			});
		}
		
		// If this player didn't follow suit, then they were out of the lead suit
		if (! is_lead_card) {
			if (card_suit(played_card_id) != card_suit(last_lead_card)) {
				retn[ played_player_id ].cards = retn[ played_player_id ].cards.filter(function(card_id) {
					return card_suit(card_id) != card_suit(last_lead_card);
				});
			}
		}
	}
	
	// ...and of course, we know more about our own situation
	retn[ this.player_id ] = this;
	
	// That's all we can infer
	return retn;
};

GameState.prototype.evaluatePosition = function() {	
	// determine who's winning, even mid-round.
	
	var retn = {};
	for (var i = 0; i < 4; ++i) {
		retn[i] = 0;
	}
	
	// We can get an explicit score for all the completed rounds..
	var completedRounds = Math.floor(this.moveHistory.length/4);
	
	var last_winner = 0;
	
	for (var i = 0; i < completedRounds; ++i) {
		
		// Determine trick value
		
		var trick_value = 0;		
		for (var j = 0; j < 4; ++j) {
			var move = this.moveHistory[i*4 + j];
			if (card_suit(move.card_id) == SUIT_HEARTS) {
				trick_value += 1;
			} else if (card_is(move.card_id, SUIT_SPADES, FACE_QUEEN)) {
				trick_value += 13;
			}
		}
		
		// Determine trick winner
		
		var lead_move = this.moveHistory[i*4 + 0];
		var winning_player = lead_move.player_id;
		for (var j = 1; j < 4; ++j) {
			var contender_move = this.moveHistory[i*4 + j];
			if (
				card_suit(contender_move.card_id) == card_suit(lead_move.card_id) &&
				card_face(contender_move.card_id) > card_face(lead_move.card_id)
			) {
				winning_player = contender_move.player_id;
			}
		}
		
		// That player loses the points
		
		retn[winning_player /* should be team id, but they're equal */] -= (trick_value * 100);
		last_winner = winning_player;
	}
	
	// If there's an incomplete round,	
	// then we can see who's in the best position for the round so far
	
	
	
	// If this was the trick-ending play, apply a penalty for whoever's in the lead - unless it's the last trick
	var is_time_for_new_trick = ( (this.moveHistory.length % 4) == 0 && ! this.gameHasEnded() );
	if (is_time_for_new_trick) {
		retn[last_winner] -= 50;
	}
	
	return retn;
};

GameState.prototype.gameHasEnded = function() {
	return this.moveHistory.length >= (4*13);
};

GameState.prototype.getNextPlayerID = function() {
	if (this.moveHistory.length) {
		
		if (this.moveHistory.length % 4 == 0) {
			
			// It's a new round. Who won the last round?
			var last_round_starting_move = this.moveHistory[this.moveHistory.length-4];
			var winning_player_id = last_round_starting_move.player_id;
			var highest_face_in_lead_suit = card_face(last_round_starting_move.card_id);
			
			for (var i = 0; i < 3; ++i) {
				var round_move = this.moveHistory[this.moveHistory.length-3 + i];
				if (
					card_suit(round_move.card_id) == card_suit(last_round_starting_move.card_id) &&
					card_face(round_move.card_id) > highest_face_in_lead_suit
				) {
					
					winning_player_id = round_move.player_id;
					highest_face_in_lead_suit = card_face(round_move.card_id);
				}
			}
			
			return winning_player_id; // Math.floor(Math.random() * 4); // FIXME: who won the last round?
			
		} else {
			
			// We're mid-round, pick the next player
			return (this.moveHistory[this.moveHistory.length - 1].player_id + 1) % 4; // num_players
		}
		
	} else {
		
		// No moves have bene played yet, youngest player starts
		return 0;
	}
};

var hearts_create_players = function() {
	var deck = deck_create();
	var retn = [new Player(), new Player(), new Player(), new Player()];
	for (var i = 0; i < 4; ++i) {
		retn[i].cards = deck.slice( 13*i, 13*(i+1) );
		retn[i].player_id = i;
		retn[i].team_id   = i;
	}
	return retn;
}

var hearts_mainloop = function() {
	
	var players = hearts_create_players();
	
	var gs = new GameState();
	while (! gs.gameHasEnded()) {
				
		var player_id = gs.getNextPlayerID();
		
		var move = players[player_id].determineMove(gs, 3, players[player_id].team_id)[0];
		
		gs.applyMove(move);
		players[player_id].cards = players[player_id].cards.filter(function(card_id) {
			return card_id != move.card_id;
		});
	}

	return gs;
}

// SAMPLE GAME
// ```````````

var main = function() {
	
	var heartsgame = hearts_mainloop();
	
	for(var i = 0; i < heartsgame.moveHistory.length; ++i) {
		
		var move = heartsgame.moveHistory[i];
		
		console.log("Player "+move.player_id + ": " + card_name(move.card_id));
		
		if (i % 4 == 3) {
			var temp_gs = heartsgame.clone();
			temp_gs.moveHistory = temp_gs.moveHistory.slice(0, i+1);
			console.log("Scores: " + JSON.stringify(temp_gs.evaluatePosition()) + "\n");
			
		}
		
	}

	console.log("The game ended.");
}

main();