/*
Copyright (C) 1997-2001 Id Software, Inc.

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  

See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

*/

#include "g_local.h"
#include "g_gametypes.h"


//==========================================================
//					Teams
//==========================================================

cvar_t	*g_maxteams;
cvar_t	*g_teams_maxplayers;
cvar_t	*g_teams_lock;
cvar_t	*g_teams_teamdamage;

//=================
//G_Teams_NewMap
//=================
void G_Teams_NewMap( void )
{
	int		team;
	edict_t	*e;

	//unlock all teams and clear up team lists
	memset( teamlist, 0, sizeof(teamlist) );
	for( team = TEAM_SPECTATOR; team < GS_MAX_TEAMS; team++ )
		teamlist[team].playerIndices[0] = -1;

	for( e = game.edicts + 1; PLAYERNUM(e) < game.maxclients; e++ ) {
		if( !e->r.client || !e->r.client->pers.connected )
			continue;

		G_Teams_SetTeam( e, TEAM_SPECTATOR );
	}

	level.maptime = 0;
}

//=================
//G_Teams_Init
//=================
void G_Teams_Init( void )
{
	//not much to do here, just start up the cvars
	g_maxteams = trap_Cvar_Get ("g_maxteams", "2", CVAR_ARCHIVE);
	if( g_maxteams->integer > GS_MAX_TEAMS - TEAM_PLAYERS ) {
		trap_Cvar_Set( "g_maxteams", va("%i",(GS_MAX_TEAMS - TEAM_PLAYERS)) );
	}

	g_teams_maxplayers = trap_Cvar_Get( "g_teams_maxplayers", "6", CVAR_ARCHIVE );
	g_teams_lock = trap_Cvar_Get( "g_teams_lock", "0", CVAR_ARCHIVE );
	g_teams_teamdamage = trap_Cvar_Get( "g_teams_teamdamage", "1", CVAR_ARCHIVE );
}


//=================
//G_Teams_UpdateMembersList
// It's better to count the list in detail once per fame, than
// creating a quick list each time we need it.
//=================
void G_Teams_UpdateMembersList( void )
{
	static int			list[MAX_CLIENTS];
	static int			sorted[MAX_CLIENTS];
	static int			count;

	edict_t	*ent;
	int	i, team;
	int	bestscore;
	int	bestplayer = 0;

	for( team = TEAM_SPECTATOR; team < TEAM_RED + g_maxteams->integer; team++ )
	{
		count = 0;
		//create a temp list with the clients inside this team
		for( i = 0, ent = game.edicts + 1; i < game.maxclients; i++, ent++ )
		{
			if( !ent->r.client || !ent->r.client->pers.connected ) continue;
			
			if( ent->s.team == team ) {
				list[count] = ENTNUM(ent);
				count++;
			}
		}

		teamlist[team].numplayers = 0;

		if( count )
		{
			memset( sorted, 0, sizeof(int)*MAX_CLIENTS);
			bestplayer = -2;
			while( bestplayer != -1 )
			{
				bestscore = -9999;
				bestplayer = -1;
				//now sort them by their score
				for( i = 0; i < count; i++ ) {
					if( !sorted[i] )
					{
						ent = game.edicts + list[i];
						if( match.scores[PLAYERNUM(ent)].score >= bestscore ) {
							bestplayer = i;
							bestscore = match.scores[PLAYERNUM(ent)].score;
						}
					}
				}
				
				if( bestplayer > -1 ) {
					sorted[bestplayer] = qtrue;
					teamlist[team].playerIndices[teamlist[team].numplayers] = list[bestplayer];
					teamlist[team].numplayers++;
					
				}
			}
		}

		//terminate the list with -1
		teamlist[team].playerIndices[teamlist[team].numplayers] = -1; 
	}
}

//=================
//G_Teams_TeamIsLocked
//=================
qboolean G_Teams_TeamIsLocked( int team )
{
	if( team && team < GS_MAX_TEAMS )
		return teamlist[team].locked;
	else
		return qfalse;
}

//=================
//G_Teams_LockTeam
//=================
void G_Teams_LockTeam( int team )
{
	if( team && team < GS_MAX_TEAMS )
		teamlist[team].locked = qtrue;
}

//=================
//G_Teams_UnLockTeam
//=================
void G_Teams_UnLockTeam( int team )
{
	if( team && team < GS_MAX_TEAMS )
		teamlist[team].locked = qfalse;
}

//=================
//G_Teams_PlayerIsInvited
//=================
qboolean G_Teams_PlayerIsInvited( int team, edict_t *ent )
{
	int i;

	if( team < TEAM_PLAYERS || team >= GS_MAX_TEAMS )
		return qfalse;

	if( !ent->r.inuse || !ent->r.client )
		return qfalse;

	for( i = 0; teamlist[team].invited[i] && i < MAX_CLIENTS; i++ ) {
		if( teamlist[team].invited[i] == ENTNUM(ent) )
			return qtrue;
	}

	return qfalse;
}

//=================
//G_Teams_InvitePlayer
//=================
void G_Teams_InvitePlayer( int team, edict_t *ent )
{
	int i;

	if( team < TEAM_PLAYERS || team >= GS_MAX_TEAMS )
		return;

	if( !ent->r.inuse || !ent->r.client )
		return;

	for( i = 0; teamlist[team].invited[i] && i < MAX_CLIENTS; i++ ) {
		if( teamlist[team].invited[i] == ENTNUM(ent) )
			return;
	}

	teamlist[team].invited[i] = ENTNUM(ent);
}

//=================
//G_Teams_UnInvitePlayer
//=================
void G_Teams_UnInvitePlayer( int team, edict_t *ent )
{
	int i;

	if( team < TEAM_PLAYERS || team >= GS_MAX_TEAMS )
		return;

	if( !ent->r.inuse || !ent->r.client )
		return;

	for( i = 0; teamlist[team].invited[i] && i < MAX_CLIENTS; i++ ) {
		if( teamlist[team].invited[i] == ENTNUM(ent) )
			break;
	}
	while( teamlist[team].invited[i] && i+1 < MAX_CLIENTS ) {
		teamlist[team].invited[i] = teamlist[team].invited[i+1];
		i++;
	}
	teamlist[team].invited[MAX_CLIENTS-1] = 0;
}

//=================
//G_Teams_RemoveInvites
// Removes all invites from all teams
//=================
void G_Teams_RemoveInvites( void )
{
	int team;

	for( team = TEAM_PLAYERS; team < GS_MAX_TEAMS; team++ )
		teamlist[team].invited[0] = 0;
}

//=================
//G_Teams_Lock_f
//=================
void G_Teams_Lock_f( edict_t *ent )
{
	if( !ent->r.inuse || !ent->r.client || ent->s.team == TEAM_SPECTATOR )
		return;

	if( !g_teams_lock->integer ) {
		G_PrintMsg( ent, "Team locking is not currently enabled on this server.\n" );
		return;
	}

	if( match.state < MATCH_STATE_COUNTDOWN || match.state > MATCH_STATE_PLAYTIME ) {
		G_PrintMsg( ent, "Team locking is only possible during the match.\n" );
		return;
	}

	if( G_Teams_TeamIsLocked( ent->s.team ) ) {
		G_PrintMsg( ent, "Your team is already locked.\n" );
		return;
	}

	G_Teams_LockTeam( ent->s.team );
	G_PrintMsg( ent, "Team %s%s locked by %s%s.\n", GS_TeamName(ent->s.team), S_COLOR_WHITE,
		ent->r.client->pers.netname, S_COLOR_WHITE );
}

//=================
//G_Teams_UnLock_f
//=================
void G_Teams_UnLock_f( edict_t *ent )
{
	if( !ent->r.inuse || !ent->r.client || ent->s.team == TEAM_SPECTATOR )
		return;

	if( !G_Teams_TeamIsLocked( ent->s.team ) ) {
		G_PrintMsg( ent, "Your team is already unlocked.\n" );
		return;
	}

	if( !g_teams_lock->integer ) {
		G_PrintMsg( ent, "Team locking is not currently enabled on this server.\n" );
		return;
	}

	if( match.state < MATCH_STATE_COUNTDOWN || match.state > MATCH_STATE_PLAYTIME ) {
		G_PrintMsg( ent, "Team unlocking is only possible during the match.\n" );
		return;
	}

	G_Teams_UnLockTeam( ent->s.team );
	G_PrintMsg( ent, "Team %s%s unlocked by %s%s.\n", GS_TeamName(ent->s.team), S_COLOR_WHITE,
		ent->r.client->pers.netname, S_COLOR_WHITE );
}

//=================
//G_Teams_Invite_f
//=================
void G_Teams_Invite_f( edict_t *ent )
{
	char *text;
	edict_t *toinvite;

	if( !ent->r.inuse || !ent->r.client || ent->s.team == TEAM_SPECTATOR )
		return;

	text = trap_Cmd_Argv(1);

	if( !text || !strlen(text) ) {
		int i;
		edict_t *e;
		char msg[1024];

		msg[0] = 0;
		Q_strncatz( msg, "Usage: invite <player>\n", sizeof(msg) );
		Q_strncatz( msg, "- List of current players:\n", sizeof(msg) );

		for( i = 0, e = game.edicts+1; i < game.maxclients; i++, e++ ) {
			if( !e->r.inuse ) continue;
			Q_strncatz( msg, va("%3i: %s\n", PLAYERNUM(e), e->r.client->pers.netname), sizeof(msg) );
		}

		G_PrintMsg( ent, "%s", msg );
		return;
	}

	if( !G_Teams_TeamIsLocked( ent->s.team ) ) {
		G_PrintMsg( ent, "Your team is not locked.\n" );
		return;
	}

	toinvite = G_PlayerForText( text );

	if( !toinvite ) {
		G_PrintMsg( ent, "No such player.\n" );
		return;
	}

	if( G_Teams_PlayerIsInvited( ent->s.team, toinvite ) ) {
		G_PrintMsg( ent, "%s%s is already invited to your team.\n", toinvite->r.client->pers.netname, S_COLOR_WHITE );
		return;
	}

	G_Teams_InvitePlayer( ent->s.team, toinvite );
	G_PrintMsg( NULL, "%s%s invited %s%s to team %s%s.\n", ent->r.client->pers.netname, S_COLOR_WHITE,
		toinvite->r.client->pers.netname, S_COLOR_WHITE, GS_TeamName(ent->s.team), S_COLOR_WHITE );
}

//=================
//G_Teams_AssignTeamSkin
//=================
void G_Teams_AssignTeamSkin( edict_t *ent, char *userinfo )
{
	char	skin[MAX_QPATH], model[MAX_QPATH];
	char	*userskin, *usermodel;

	// index skin file
	userskin = GS_TeamSkinName( ent->s.team ); // is it a team skin?
	if( !userskin || !userskin[0] )	// NULL indicates *user defined* 
		userskin = Info_ValueForKey( userinfo, "skin" );
	if( !userskin[0] ) userskin = NULL;

	// index player model
	usermodel = Info_ValueForKey( userinfo, "model" );
	if( !usermodel[0] ) usermodel = NULL;

	if( userskin && usermodel ) {
		Q_snprintfz( model, sizeof(model), "$models/players/%s", usermodel );
		Q_snprintfz( skin, sizeof(skin), "models/players/%s/%s", usermodel, userskin );
	} else {
		Q_snprintfz( model, sizeof(model), "$models/players/%s", DEFAULT_PLAYERMODEL );
		Q_snprintfz( skin, sizeof(skin), "models/players/%s/%s", DEFAULT_PLAYERMODEL, DEFAULT_PLAYERSKIN );
	}

	ent->s.modelindex = trap_ModelIndex( model );
	ent->s.skinnum = trap_SkinIndex( skin );
}

void G_Gametype_CTF_CleanUpPlayerStats( edict_t *ent );
//=================
//G_Teams_SetTeam - sets clients team without any checking
//=================
void G_Teams_SetTeam( edict_t *ent, int team )
{
	//clean scores at changing team
	memset( &match.scores[PLAYERNUM(ent)], 0, sizeof(client_scores_t) );
	if( game.gametype == GAMETYPE_CTF ) {
		G_Gametype_CTF_DeadDropFlag(ent);
		G_Gametype_CTF_CleanUpPlayerStats(ent);
	}
	// remove weapon in the case he had one
	ent->r.client->latched_weapon = 0;
	ChangeWeapon( ent );

	ent->s.team = ent->r.client->pers.team = team;

	if( team == TEAM_SPECTATOR ) {
		client_persistant_t		pers;
		client_teamchange_t		teamchange;
		char	userinfo[MAX_INFO_STRING];
		int		i;

		// reset player ready state
		match.ready[PLAYERNUM(ent)] = qfalse;
		G_AddEvent( ent, EV_TELEPORT, 0, qtrue );

		pers = ent->r.client->pers;
		teamchange = ent->r.client->teamchange;

		memcpy( userinfo, ent->r.client->pers.userinfo, sizeof(userinfo) );
		memset( ent->r.client, 0, sizeof(*ent->r.client) );
		ent->r.client->pers = pers;
		ent->r.client->teamchange = teamchange;
		ClientUserinfoChanged( ent, userinfo );

		// set the delta angle
		for( i = 0; i < 3; i++ )
			ent->r.client->ps.pmove.delta_angles[i] = ANGLE2SHORT(ent->s.angles[i]) - ent->r.client->pers.cmd_angles[i];

		ent->deadflag = DEAD_NO;
		ent->movetype = MOVETYPE_NOCLIP;
		ent->r.solid = SOLID_NOT;
		ent->r.svflags |= SVF_NOCLIENT;

		trap_LinkEntity( ent );

		G_ClearPlayerStateEvents( ent->r.client );

	} else { //known team found

		//G_ClearPlayerStateEvents( ent->r.client );
		
		// call for spawn
		G_Teams_UnInvitePlayer( team, ent );
		G_Gametype_ClientRespawn( ent );		// already updates the skin
	}

	// reset ready up announcer timers
	ent->r.client->pers.readyUpWarningNext = game.realtime + 3000;
	ent->r.client->pers.readyUpWarningCount = 0;

	// reset spawncount etc.
	InitClientResp( ent->r.client );

	G_ScoreboardEvent();
	G_Teams_UpdateMembersList();
	G_Match_CheckReadys();
	G_UpdatePlayerMatchMsg( ent );
}

enum {
	ER_TEAM_OK,
	ER_TEAM_INVALID,
	ER_TEAM_FULL,
	ER_TEAM_LOCKED,
	ER_TEAM_MATCHSTATE,
	ER_TEAM_CHALLENGERS
};

//=================
//G_GameTypes_DenyJoinTeam
//=================
int G_GameTypes_DenyJoinTeam( edict_t *ent, int team )
{
	if( team < 0 || team >= GS_MAX_TEAMS ) {
		G_Printf( "WARNING: 'G_GameTypes_CanJoinTeam' parsing a unrecognized team value\n" );
		return ER_TEAM_INVALID;
	}

	if( team == TEAM_SPECTATOR )
		return ER_TEAM_OK;

	if( match.state > MATCH_STATE_PLAYTIME )
		return ER_TEAM_MATCHSTATE;

	// waiting for chanllengers queue to be executed
	if( G_Gametype_hasChallengersQueue( game.gametype ) &&
		level.maptime < (unsigned)(G_CHALLENGERS_MIN_JOINTEAM_MAPTIME + game.framemsec * 2) )
		return ER_TEAM_CHALLENGERS;

	// force eveyone to go through queue so things work on map change
	if( G_Gametype_hasChallengersQueue( game.gametype ) && !ent->r.client->pers.queueTimeStamp )
		return ER_TEAM_CHALLENGERS;

	//see if team is locked
	if( G_Teams_TeamIsLocked(team) && !G_Teams_PlayerIsInvited(team, ent) ) {
		return ER_TEAM_LOCKED;
	}

	if( GS_Gametype_IsTeamBased(game.gametype) && team >= TEAM_RED && 
		team <= TEAM_YELLOW && (team - TEAM_RED < g_maxteams->integer) ) {
			//see if team is full
			if( team > TEAM_PLAYERS ) 
			{
				int	count = teamlist[team].numplayers;

				if( ( count + 1 > gametypes[game.gametype].maxPlayersPerTeam &&
					gametypes[game.gametype].maxPlayersPerTeam > 0 ) || 
					( count + 1 > g_teams_maxplayers->integer &&
					g_teams_maxplayers->integer > 0 ) ) 
				{
					return ER_TEAM_FULL;
				}
			}

			return ER_TEAM_OK;
		}
	else if( team == TEAM_PLAYERS ) {
		return ER_TEAM_OK;
	}

	return ER_TEAM_INVALID;
}

//=================
//G_Teams_JoinTeam - checks that client can join the given team and then joins it
//=================
qboolean G_Teams_JoinTeam( edict_t *ent, int team )
{
	int error;
	G_Teams_UpdateMembersList(); // make sure we have up-to-date data

	if( !ent->r.client )
		return qfalse;

	if( (error = G_GameTypes_DenyJoinTeam( ent, team )) ) {
		if( error == ER_TEAM_INVALID ) {
			G_PrintMsg( ent, "Can't join %s in %s\n", GS_TeamName( team ),
			GS_Gametype_ShortName(game.gametype) );
		}
		else if( error == ER_TEAM_CHALLENGERS ) {
			G_Teams_JoinChallengersQueue( ent );
		}
		else if( error == ER_TEAM_FULL ) {
			G_PrintMsg( ent, "Team %s is FULL\n", GS_TeamName( team ) );
			G_Teams_JoinChallengersQueue( ent );
		}
		else if( error == ER_TEAM_LOCKED ) {
			G_PrintMsg( ent, "Team %s is LOCKED\n", GS_TeamName( team ) );
			G_Teams_JoinChallengersQueue( ent );
		}
		else if( error == ER_TEAM_MATCHSTATE ) {
			G_PrintMsg( ent, "Can't join %s at this moment\n", GS_TeamName( team ) );
		}
		return qfalse;
	}

	//ok, can join, proceed
	G_Teams_SetTeam( ent, team );
	return qtrue;
}

//=================
//G_Teams_JoinAnyTeam - find us a team since we are too lazy to do ourselves
//=================
qboolean G_Teams_JoinAnyTeam( edict_t *ent, qboolean silent )
{
	int		best = game.maxclients+1;
	int		i, team = -1;
	qboolean	wasinqueue = (ent->r.client->pers.queueTimeStamp);

	G_Teams_UpdateMembersList(); // make sure we have up-to-date data

	//depending on the gametype, of course
	if( !GS_Gametype_IsTeamBased(game.gametype) ) {
		if( ent->s.team == TEAM_PLAYERS ) {
			if( !silent ) {
				G_PrintMsg( ent, "You are already in %s team\n", GS_TeamName(TEAM_PLAYERS) );
			}
			return qfalse;
		}
		if( G_Teams_JoinTeam( ent, TEAM_PLAYERS ) ) {
			if( !silent ) {
				G_PrintMsg( NULL, "%s%s joined the %s team.\n",
					ent->r.client->pers.netname, S_COLOR_WHITE, GS_TeamName(ent->s.team) );
			}
		}
		return qtrue;

	} else {	//team based

		//find the available team with smaller player count
		for( i = TEAM_RED; i < TEAM_RED + g_maxteams->integer; i++ )
		{
			if( G_GameTypes_DenyJoinTeam(ent, i) ) {
					continue;
			}

			if( teamlist[i].numplayers < best ) {
				best = teamlist[i].numplayers;
				team = i;
			}
		}

		if( team == ent->s.team ) { // he is at the right team
			if( !silent ) {
				G_PrintMsg( ent, "%sCouldn't find an emptier team than team %s.\n",
					S_COLOR_WHITE, GS_TeamName(ent->s.team) );
			}
			return qfalse;
		}

		if( team != -1 ) {
			if( G_Teams_JoinTeam( ent, team ) ) {
				if( !silent ) {
					G_PrintMsg( NULL, "%s%s joined the %s team.\n",
						ent->r.client->pers.netname, S_COLOR_WHITE, GS_TeamName(ent->s.team) );
				}
				return qtrue;
			}
		}
		if( match.state <= MATCH_STATE_PLAYTIME && !silent )
			G_Teams_JoinChallengersQueue( ent );
	}

	// don't print message if we joined the queue
	if( !silent && (!G_Gametype_hasChallengersQueue( game.gametype ) || wasinqueue ||
		!ent->r.client->pers.queueTimeStamp) )
		G_PrintMsg( ent, "You can't join the game now\n" );

	return qfalse;
}

//=================
//G_Teams_Join_Cmd
//=================
void G_Teams_Join_Cmd( edict_t *ent )
{
	char	*t;
	int		team;

	t = trap_Cmd_Argv(1);
	if( !t || *t == 0 ) {
		G_Teams_JoinAnyTeam( ent, qfalse );
		return;
	}

	team = GS_Teams_TeamFromName( t );
	if( team != -1 ) {
		if( team == TEAM_SPECTATOR ) { // special handling for spectator team
			Cmd_Spec_f( ent );
			return;
		}
		if( team == ent->s.team ) {
			G_PrintMsg( ent, "You are already in %s team\n", GS_TeamName(team) );
			return;
		}
		if( G_Teams_JoinTeam( ent, team ) ) { //found a team to join
			G_PrintMsg( NULL, "%s%s joined the %s%s team.\n", ent->r.client->pers.netname, S_COLOR_WHITE,
				GS_TeamName(ent->s.team), S_COLOR_WHITE );
			return;
		}
	} else {
		G_PrintMsg( ent, "No such team.\n" );
		return;
	}
}

//======================================================================
//
//TEAM TAB
//
//======================================================================
void LocationName(vec3_t origin, char *buf, int buflen);
int	LocationTAG( char *name );

//==================
//G_Teams_TDM_UpdateTeamTabMessages
//==================
void G_Teams_UpdateTeamTabMessages( void )
{
	static int nexttime = 0;
	static char		teammessage[MAX_STRING_CHARS];
	edict_t			*ent, *e;
	unsigned int	len;
	int				i;
	char			entry[MAX_TOKEN_CHARS];
	char			scratch[MAX_TOKEN_CHARS];
	int				locationTag;


	nexttime -= game.framemsec;
	if( nexttime > 0 )
		return;

	while( nexttime <= 0 ) nexttime += 2 * 1000; // 2 seconds

	// time for a new update
	for( ent = game.edicts + 1; PLAYERNUM(ent) < game.maxclients; ent++ )
	{
		if( !ent->r.inuse || !ent->r.client )
			continue;

		if( ent->s.team <= TEAM_PLAYERS || ent->s.team >= GS_MAX_TEAMS )
			continue;

		*teammessage = 0;
		Q_snprintfz( teammessage, sizeof(teammessage), "ti \"" ); 
		len = strlen(teammessage);

		// add our teammates info to the string
		for( i = 0; teamlist[ent->s.team].playerIndices[i] != -1; i++ )
		{
			e = game.edicts + teamlist[ent->s.team].playerIndices[i];
			if( e == ent )
				continue;

			// get location name
			*scratch = 0;
			LocationName( e->s.origin, scratch, sizeof(scratch) );
			locationTag = LocationTAG( scratch );
			if( locationTag == -1 )
				continue;

			*entry = 0;
			Q_snprintfz( entry, sizeof(entry), "%i %i ",
				PLAYERNUM(e),
				locationTag
				);

			if( MAX_STRING_CHARS - len > strlen(entry) ) {
				Q_strncatz( teammessage, entry, sizeof(teammessage) );
				len = strlen(teammessage);
			}
		}

		// add closing quote
		*entry = 0;
		Q_snprintfz( entry, sizeof(entry), "\"" );
		if( MAX_STRING_CHARS - len > strlen(entry) ) {
			Q_strncatz( teammessage, entry, sizeof(teammessage) );
			len = strlen(teammessage);
		}

		trap_ServerCmd( ent, teammessage );

		// see if there are spectators chasing this player and send them the layout too
		for( i = 0; teamlist[TEAM_SPECTATOR].playerIndices[i] != -1; i++ )
		{
			e = game.edicts + teamlist[TEAM_SPECTATOR].playerIndices[i];
			if( !e->r.inuse || !e->r.client) continue;
			if( e->r.client->chase.active && e->r.client->chase.target == ENTNUM(ent) ) {
				trap_ServerCmd( e, teammessage );
			}
		}
	}
}


//======================================================================
//
// CHALLENGERS QUEUE
//
//======================================================================

//=================
//G_Teams_BestInChallengersQueue
//=================
edict_t *G_Teams_BestInChallengersQueue( unsigned int lastTimeStamp, edict_t *ignore ) {
	edict_t *e, *best = NULL;
	unsigned int bestTimeStamp = game.realtime+10000;

	// fill the teams with the players with the lowest timestamps
	for( e = game.edicts + 1; PLAYERNUM(e) < game.maxclients; e++ ) {
		if( !e->r.inuse || !e->r.client || !e->r.client->pers.connected )
			continue;
		if( !e->r.client->pers.queueTimeStamp || e->s.team != TEAM_SPECTATOR )
			continue;
		if( trap_GetClientState(PLAYERNUM(e)) < CS_SPAWNED || e->r.client->pers.connecting )
			continue;
		if( e == ignore )
			continue;
		if( e->r.client->pers.queueTimeStamp >= lastTimeStamp ) {
			if( e->r.client->pers.queueTimeStamp < bestTimeStamp ) {
				bestTimeStamp = e->r.client->pers.queueTimeStamp;
				best = e;
			}
		}
	}

	return best;
}

//=================
//G_Teams_ExecuteChallengersQueue
//=================
void G_Teams_ExecuteChallengersQueue( void ) {
	edict_t *ent;
	qboolean restartmatch = qfalse;

	// Medar fixme: this is only really makes sense, if playerlimit per team is one
	if( match.state == MATCH_STATE_PLAYTIME )
		return;

	if( !G_Gametype_hasChallengersQueue( game.gametype ) )
		return;

	if( level.maptime < G_CHALLENGERS_MIN_JOINTEAM_MAPTIME ) {
		static int time, lasttime;
		time = (int)((G_CHALLENGERS_MIN_JOINTEAM_MAPTIME - level.maptime)*0.001);
		if( lasttime && time == lasttime )
			return;
		lasttime = time;
		if( lasttime )
			G_CenterPrintMsg( NULL, "Waiting... %i", lasttime );
		else
			G_CenterPrintMsg( NULL, "" );
		return;
	}

	// pick players in join order and try to put them in the
	// game until we get the first refused one.
	ent = G_Teams_BestInChallengersQueue( 0, NULL );
	while( ent && G_Teams_JoinAnyTeam( ent, qtrue ) ) {
		// if we successfully execute the challengers queue during the countdown, revert to warmup
		if( match.state == MATCH_STATE_COUNTDOWN ) {
			restartmatch = qtrue;
		}

		ent = G_Teams_BestInChallengersQueue( ent->r.client->pers.queueTimeStamp, ent );
	}

	if( restartmatch == qtrue ) {
		G_Match_AutorecordCommand( qfalse, qtrue );
		match.state = MATCH_STATE_WARMUP - 1;
		G_Match_SetUpNextState();
	}
}

//=================
////G_Teams_BestScoreBelow
//=================
edict_t *G_Teams_BestScoreBelow( int maxscore ) {
	int team, i;
	edict_t *e, *best = NULL;
	int		bestScore = -9999999;

	if( GS_Gametype_IsTeamBased(game.gametype) ) {
		for( team = TEAM_RED; team < TEAM_RED + g_maxteams->integer; team++ ) {
			for( i = 0; teamlist[team].playerIndices[i] != -1; i++ ) {
				e = game.edicts + teamlist[team].playerIndices[i];
				if( match.scores[PLAYERNUM(e)].score > bestScore &&
					match.scores[PLAYERNUM(e)].score <= maxscore
					&& !e->r.client->pers.queueTimeStamp )
				{
					bestScore = match.scores[PLAYERNUM(e)].score;
					best = e;
				}
			}
		}
	} else {
		for( i = 0; teamlist[TEAM_PLAYERS].playerIndices[i] != -1; i++ ) {
			e = game.edicts + teamlist[TEAM_PLAYERS].playerIndices[i];
			if( match.scores[PLAYERNUM(e)].score > bestScore &&
				match.scores[PLAYERNUM(e)].score <= maxscore
				&& !e->r.client->pers.queueTimeStamp )
			{
				bestScore = match.scores[PLAYERNUM(e)].score;
				best = e;
			}
		}
	}

	return best;
}

//=================
//G_Teams_AdvanceChallengersQueue
//=================
void G_Teams_AdvanceChallengersQueue( void ) 
{
	int i, team, loserscount, winnerscount, playerscount = 0;
	int maxscore = 999999;
	edict_t *won, *e;
	int START_TEAM = TEAM_PLAYERS, END_TEAM = TEAM_PLAYERS+1;

	if( !G_Gametype_hasChallengersQueue( game.gametype ) )
		return;

	G_Teams_UpdateMembersList();

	if( GS_Gametype_IsTeamBased(game.gametype) ) { 
		START_TEAM = TEAM_RED;
		END_TEAM = TEAM_RED + g_maxteams->integer;
	}

	// assign new timestamps to all the players inside teams
	for( team = START_TEAM; team < END_TEAM; team++ ) {
		playerscount += teamlist[team].numplayers;
	}

	if( !playerscount )
		return;

	loserscount = 0;
	if( playerscount > 1 ) {
		loserscount = (int)(playerscount / 2);
	}
	winnerscount = playerscount - loserscount;

	// put everyone who just played out of the challengers queue
	for( team = START_TEAM; team < END_TEAM; team++ ) {
		for( i = 0; teamlist[team].playerIndices[i] != -1; i++ ) {
			e = game.edicts + teamlist[team].playerIndices[i];
			e->r.client->pers.queueTimeStamp = 0;
		}
	}

	// put (back) the best scoring players in first positions of challengers queue
	for( i=0; i < winnerscount; i++ ) {
		won = G_Teams_BestScoreBelow( maxscore );
		if( won ) {
			maxscore = match.scores[PLAYERNUM(won)].score;
			won->r.client->pers.queueTimeStamp = 1 + (winnerscount-i); // never have 2 players with the same timestamp
		}
	}
}

//=================
//G_Teams_LeaveChallengersQueue
//=================
void G_Teams_LeaveChallengersQueue( edict_t *ent ) {
	if( !G_Gametype_hasChallengersQueue( game.gametype ) ) {
		ent->r.client->pers.queueTimeStamp = 0;
		return;
	}

	if( ent->s.team != TEAM_SPECTATOR )
		return;

	// exit the challengers queue
	if( ent->r.client->pers.queueTimeStamp ) {
		ent->r.client->pers.queueTimeStamp = 0;
		G_PrintMsg( ent, "%sYou left the challengers queue\n", S_COLOR_CYAN );
		G_UpdatePlayerMatchMsg( ent );
	}
}

//=================
//G_Teams_JoinChallengersQueue
//=================
void G_Teams_JoinChallengersQueue( edict_t *ent ) {
	int pos = 0;
	edict_t *e;

	if( !G_Gametype_hasChallengersQueue( game.gametype ) ) {
		ent->r.client->pers.queueTimeStamp = 0;
		return;
	}

	if( ent->s.team != TEAM_SPECTATOR )
		return;

	// enter the challengers queue
	if( !ent->r.client->pers.queueTimeStamp ) { // enter the line
		ent->r.client->pers.queueTimeStamp = game.realtime;
		for( e = game.edicts + 1; PLAYERNUM(e) < game.maxclients; e++ ) {
			if( !e->r.inuse || !e->r.client || !e->r.client->pers.connected )
				continue;
			if( !e->r.client->pers.queueTimeStamp || e->s.team != TEAM_SPECTATOR )
				continue;
			// if there are other players with the same timestamp, increase ours
			if( e->r.client->pers.queueTimeStamp >= ent->r.client->pers.queueTimeStamp )
				ent->r.client->pers.queueTimeStamp = e->r.client->pers.queueTimeStamp+1;
			if( e->r.client->pers.queueTimeStamp < ent->r.client->pers.queueTimeStamp )
				pos++;
		}
		G_PrintMsg( ent, "%sYou entered the challengers queue in position %i\n", S_COLOR_CYAN, pos+1 );
		G_UpdatePlayerMatchMsg( ent );
	}
}

//======================================================================
//
//TEAM COMMUNICATIONS
//
//======================================================================

static edict_t *point;
static vec3_t point_location;

//======================================================================
//	LOCATIONS
//======================================================================

void G_RegisterMapLocationName( char *name ) {
	int i;

	if( !name )
		return;

	for( i = 0; i < level.numLocations; i++ ) {
		if( !Q_stricmp( name, level.locationNames[i] ) )
			return;
	}

	Q_strncpyz( level.locationNames[level.numLocations], name, MAX_STRING_CHARS );
	level.numLocations++;
}

int	LocationTAG( char *name )
{
	int i;

	if( !level.numLocations )
		return -1;

	for( i = 0; i < level.numLocations; i++ ) {
		if( !Q_stricmp( name, level.locationNames[i] ) )
			return i;
	}

	return 0;
}

void LocationName(vec3_t origin, char *buf, int buflen)
{
	edict_t *what = NULL;
	edict_t *hot = NULL;
	float hotdist = 3.0f*8192.0f*8192.0f;
	vec3_t v;

	while( (what = G_Find(what, FOFS(classname), "target_location")) != NULL ) {
		VectorSubtract( what->s.origin, origin, v );

		if ( VectorLengthFast( v ) > hotdist ) {
			continue;
		}

		if ( !trap_inPVS ( what->s.origin, origin ) )
			continue;

		hot = what;
		hotdist = VectorLengthFast( v );
	}

	if (!hot || !hot->message)
		Q_snprintfz( buf, buflen, "someplace" );
	else if (hot->count > 0 && hot->count < 10)
		Q_snprintfz( buf, buflen, "%c%c%s", Q_COLOR_ESCAPE, hot->count + '0', hot->message );
	else
		Q_snprintfz( buf, buflen, "%s", hot->message );
}

static void UpdatePoint( edict_t *who )
{
	vec3_t angles, forward, diff;
	trace_t trace;
	edict_t *ent, *ent_best = NULL;
	int i, j;
	float value, value_best = 0.35f; // if nothing better is found, print nothing
	gclient_t *client = who->r.client;
	vec3_t boxpoints[8], viewpoint;

	AngleVectors(client->ps.viewangles, forward, NULL, NULL);
	VectorCopy(who->s.origin, viewpoint);
	viewpoint[2] += who->viewheight;

	for (i = 0; i < game.numentities; i++) {
		ent = game.edicts + i;

		if (!ent->r.inuse || !ent->s.modelindex || ent == who)
			continue;
		if (ent->r.svflags & SVF_NOCLIENT || ent->r.solid == SOLID_NOT)
			continue;
		if (ent->s.type != ET_PLAYER && ent->s.type != ET_ITEM)
			continue;

		VectorSubtract(ent->s.origin, viewpoint, angles);
		VectorNormalize(angles);
		VectorSubtract(forward, angles, diff);
		for (j = 0; j < 3; j++) if (diff[j] < 0) diff[j] = -diff[j];
		value = VectorLengthFast(diff);

		if (value < value_best) {
			BuildBoxPoints( boxpoints, ent->s.origin, ent->r.mins, ent->r.maxs );
			for (j = 0; j < 8; j++) {
				trap_Trace( &trace, viewpoint, vec3_origin, vec3_origin, boxpoints[j], who, MASK_OPAQUE );
				if (trace.fraction == 1) {
					value_best = value;
					ent_best = ent;
					break;
				}
			}
		}
	}

	if (ent_best != NULL) {
		point = ent_best;
		VectorCopy(ent_best->s.origin, point_location);
	} else {
		vec3_t dest;

		VectorMA( viewpoint, 8192, forward, dest );
		trap_Trace( &trace, viewpoint, vec3_origin, vec3_origin, dest, who, MASK_OPAQUE );

		point = NULL;
		VectorCopy(trace.endpos, point_location);
	}
}

static void Say_Team_Location(edict_t *who, char *buf, int buflen, const char *current_color)
{
	LocationName(who->s.origin, buf, buflen);
	Q_strncatz( buf, current_color, buflen );
}

static void Say_Team_Armor(edict_t *who, char *buf, int buflen, const char *current_color)
{
	if (who->r.client->armortag) {
		Q_snprintfz(buf, buflen, "%s%i%s", game.items[who->r.client->armortag]->color,
				ARMOR_TO_INT(who->r.client->armor), current_color);
	} else {
		Q_snprintfz(buf, buflen, "%s0%s", S_COLOR_GREEN, current_color);
	}
}

static void Say_Team_Health(edict_t *who, char *buf, int buflen, const char *current_color)
{
	int health = HEALTH_TO_INT(who->health);

	if (health <= 0)
		Q_snprintfz (buf, buflen, "%s0%s", S_COLOR_RED, current_color);
	else if (health <= 50)
		Q_snprintfz (buf, buflen, "%s%i%s", S_COLOR_YELLOW, health, current_color);
	else if (health <= 100)
		Q_snprintfz (buf, buflen, "%s%i%s", S_COLOR_WHITE, health, current_color);
	else
		Q_snprintfz (buf, buflen, "%s%i%s", S_COLOR_GREEN, health, current_color);
}

static void WeaponString(edict_t *who, int weapon, char *buf, int buflen, const char *current_color)
{
	weapon_info_t *weaponinfo;
	int strong_ammo, weak_ammo;

	Q_snprintfz(buf, buflen, "%s%s%s", (game.items[weapon]->color ? game.items[weapon]->color : ""),
	            game.items[weapon]->short_name, current_color);

	weaponinfo = &g_weaponInfos[weapon];
	strong_ammo = who->r.client->inventory[weaponinfo->firedef->ammo_id];
	weak_ammo = who->r.client->inventory[weaponinfo->firedef_weak->ammo_id];

	if (weapon == WEAP_GUNBLADE)
		Q_strncatz(buf, va(":%i", strong_ammo), buflen);
	else if (strong_ammo > 0)
		Q_strncatz(buf, va(":%i/%i", strong_ammo, weak_ammo), buflen);
	else
		Q_strncatz(buf, va(":%i", weak_ammo), buflen);
}

static qboolean HasItem(edict_t *who, int item)
{
	return (who->r.client->inventory[item]);
}

static void Say_Team_Best_Weapons(edict_t *who, char *buf, int buflen, const char *current_color)
{
	char weapon_strings[2][20];
	int weap, printed = 0;

	for (weap = WEAP_TOTAL-1; weap > WEAP_GUNBLADE; weap--) {
		// evil hack to make RL more important than PG
		if (weap == WEAP_PLASMAGUN) weap = WEAP_ROCKETLAUNCHER;
		else if (weap == WEAP_ROCKETLAUNCHER) weap = WEAP_PLASMAGUN;

		if (HasItem(who, weap)) {
			WeaponString(who, weap, weapon_strings[printed], sizeof(weapon_strings[printed]), current_color);
			if (++printed == 2)
				break;
		}

		if (weap == WEAP_PLASMAGUN) weap = WEAP_ROCKETLAUNCHER;
		else if (weap == WEAP_ROCKETLAUNCHER) weap = WEAP_PLASMAGUN;
	}

	if (printed == 2) {
		Q_snprintfz (buf, buflen, "%s%s %s%s", weapon_strings[1], current_color, weapon_strings[0], current_color);
	} else if (printed == 1) {
		Q_snprintfz (buf, buflen, "%s%s", weapon_strings[0], current_color);
	} else {
		WeaponString(who, WEAP_GUNBLADE, buf, buflen, current_color);
		Q_strncatz(buf, current_color, buflen);
	}
}

static void Say_Team_Current_Weapon(edict_t *who, char *buf, int buflen, const char *current_color)
{
	if (!who->s.weapon) {
		buf[0] = 0;
		return;
	}

	WeaponString(who, who->s.weapon, buf, buflen, current_color);
	Q_strncatz(buf, current_color, buflen);
}

static void Say_Team_Point(edict_t *who, char *buf, int buflen, const char *current_color)
{
	if (!point) {
		Q_snprintfz(buf, buflen, "nothing");
		return;
	}

	if (point->s.type == ET_ITEM) {
		gitem_t *item = GS_FindItemByClassname(point->classname);
		if (item)
			Q_snprintfz(buf, buflen, "%s%s%s", (item->color ? item->color : ""), item->short_name, current_color);
		else
			Q_snprintfz(buf, buflen, point->classname);
	} else {
		Q_snprintfz(buf, buflen, "%s%s", point->classname, current_color);
	}
}

static void Say_Team_Point_Location(edict_t *who, char *buf, int buflen, const char *current_color)
{
	LocationName(point_location, buf, buflen);
	Q_strncatz ( buf, current_color, buflen );
}

static void Say_Team_Pickup(edict_t *who, char *buf, int buflen, const char *current_color)
{
	if (!who->r.client->resp.last_pickup) {
		buf[0] = 0;
	} else {
		gitem_t *item = GS_FindItemByClassname(who->r.client->resp.last_pickup->classname);
		if (item)
			Q_snprintfz(buf, buflen, "%s%s%s", (item->color ? item->color : ""), item->short_name, current_color);
		else
			buf[0] = 0;
	}
}

static void Say_Team_Pickup_Location(edict_t *who, char *buf, int buflen, const char *current_color)
{
	if (!who->r.client->resp.last_pickup) {
		buf[0] = 0;
	} else {
		LocationName(who->r.client->resp.last_pickup->s.origin, buf, buflen);
		Q_strncatz(buf, current_color, buflen);
	}
}

static void Say_Team_Drop(edict_t *who, char *buf, int buflen, const char *current_color)
{
	gitem_t *item = who->r.client->resp.last_drop_item;

	if (!item)
		buf[0] = 0;
	else
		Q_snprintfz(buf, buflen, "%s%s%s", (item->color ? item->color : ""), item->short_name, current_color);
}

static void Say_Team_Drop_Location(edict_t *who, char *buf, int buflen, const char *current_color)
{
	if (!who->r.client->resp.last_drop_item) {
		buf[0] = 0;
	} else {
		LocationName(who->r.client->resp.last_drop_location, buf, buflen);
		Q_strncatz(buf, current_color, buflen);
	}
}

void G_Say_Team(edict_t *who, char *msg, qboolean checkflood)
{
	char outmsg[256];
	char buf[256];
	int i;
	char *p;
	edict_t *cl_ent;
	char current_color[3];

	Q_strncpyz( current_color, S_COLOR_WHITE, sizeof(current_color) );

	if( checkflood ) {
		if(CheckFlood(who))
			return;
	}

	memset(outmsg, 0, sizeof(outmsg));

	if (*msg == '\"') {
		msg[strlen(msg) - 1] = 0;
		msg++;
	}

	UpdatePoint(who);

	for (p = outmsg; *msg && (p - outmsg) < sizeof(outmsg) - 3; msg++) {
		if (*msg == '%') {
			buf[0] = 0;
			switch (*++msg) {
				case 'l':
					Say_Team_Location(who, buf, sizeof(buf), current_color);
					break;
				case 'a':
					Say_Team_Armor(who, buf, sizeof(buf), current_color);
					break;
				case 'h':
					Say_Team_Health(who, buf, sizeof(buf), current_color);
					break;
				case 'b':
					Say_Team_Best_Weapons(who, buf, sizeof(buf), current_color);
					break;
				case 'w':
					Say_Team_Current_Weapon(who, buf, sizeof(buf), current_color);
					break;
				case 'x':
					Say_Team_Point(who, buf, sizeof(buf), current_color);
					break;
				case 'y':
					Say_Team_Point_Location(who, buf, sizeof(buf), current_color);
					break;
				case 'X':
					Say_Team_Pickup(who, buf, sizeof(buf), current_color);
					break;
				case 'Y':
					Say_Team_Pickup_Location(who, buf, sizeof(buf), current_color);
					break;
				case 'd':
					Say_Team_Drop(who, buf, sizeof(buf), current_color);
					break;
				case 'D':
					Say_Team_Drop_Location(who, buf, sizeof(buf), current_color);
					break;
				case '%':
					*p++ = *msg;
					break;
				default :
					// Maybe add a warning here?
					*p++ = '%';
					*p++ = *msg;
			}
			if (strlen(buf) + (p - outmsg) < sizeof(outmsg) - 3) {
				Q_strncatz(outmsg, buf, sizeof(outmsg));
				p += strlen(buf);
			}
		} else if (*msg == '^') {
			*p++ = *msg++;
			*p++ = *msg;
			Q_strncpyz( current_color, p-2, sizeof(current_color) );
		} else {
			*p++ = *msg;
		}
	}
	*p = 0;

	for (i = 0; i < game.maxclients; i++) {
		cl_ent = game.edicts + 1 + i;
		if (!cl_ent->r.inuse)
			continue;
		if (cl_ent->s.team == who->s.team)
			G_ChatMsg (cl_ent, "%s[TEAM]%s %s%s: %s\n",
				S_COLOR_YELLOW, S_COLOR_WHITE, who->r.client->pers.netname, S_COLOR_YELLOW, outmsg);
	}
}