// HUGE SET - stored in a string
string HugeSetOfIntegers_empty()
{
	return "";
}
float HugeSetOfIntegers_get(string pArr, float i)
{
	return stof(substring(pArr, i * 4, 4));
}
float HugeSetOfIntegers_length(string pArr)
{
	return strlen(pArr) / 4;
}
string HugeSetOfIntegers_concat(string a1, string a2)
{
	return strcat(a1, a2);
}
string HugeSetOfIntegers_insert(string a1, float n, string a2)
	// special concat function to build up large lists in less time by binary concatenation
{
	string s;
	s = strcat("    ", ftos(n));
	return strcat(a1, substring(s, strlen(s) - 4, 4), a2);
}

// generic string stuff
float startsWith(string haystack, string needle)
{
	return substring(haystack, 0, strlen(needle)) == needle;
}
string extractRestOfLine(string haystack, string needle)
{
	if(startsWith(haystack, needle))
		return substring(haystack, strlen(needle), strlen(haystack) - strlen(needle));
	return string_null;
}
string car(string s)
{
	float o;
	o = strstrofs(s, " ", 0);
	if(o < 0)
		return s;
	return substring(s, 0, o);
}
string cdr(string s)
{
	float o;
	o = strstrofs(s, " ", 0);
	if(o < 0)
		return string_null;
	return substring(s, o + 1, strlen(s) - (o + 1));
}

// GLOB HANDLING (for all BSP files)
float _MapInfo_globopen;
float _MapInfo_globcount; 
float _MapInfo_globhandle;
string _MapInfo_GlobItem(float i)
{
	string s;
	s = search_getfilename(_MapInfo_globhandle, i);
	return substring(s, 5, strlen(s) - 9); // without maps/ and .bsp
}

void MapInfo_Enumerate()
{
	if(_MapInfo_globopen)
		search_end(_MapInfo_globhandle);
	_MapInfo_globhandle = search_begin("maps/*.bsp", TRUE, TRUE);
	_MapInfo_globcount = search_getsize(_MapInfo_globhandle);
	_MapInfo_globopen = 1;
}

// filter the info by game type mask (updates MapInfo_count)
string _MapInfo_filtered;
string MapInfo_FilterGametype_Recursive(float pGametype, float pFeatures, float pBegin, float pEnd)
{
	float m, valid;
	string l, r;

	if(pBegin == pEnd)
		return HugeSetOfIntegers_empty();

	m = floor((pBegin + pEnd) / 2);

	l = MapInfo_FilterGametype_Recursive(pGametype, pFeatures, pBegin, m);
	if not(l)
		return string_null; // BAIL OUT
	if(MapInfo_Get_ByName(_MapInfo_GlobItem(m), 1, 0) == 2) // if we generated one... BAIL OUT and let the caller continue in the next frame.
		return string_null; // BAIL OUT
	valid = ((MapInfo_Map_supportedGametypes & pGametype) != 0) && ((MapInfo_Map_supportedFeatures & pFeatures) == pFeatures);
	r = MapInfo_FilterGametype_Recursive(pGametype, pFeatures, m + 1, pEnd);
	if not(r)
		return string_null; // BAIL OUT

	if(valid)
		return HugeSetOfIntegers_insert(l, m, r);
	else
		return HugeSetOfIntegers_concat(l, r);
}
float MapInfo_FilterGametype(float pGametype, float pFeatures)
{
	if(_MapInfo_filtered)
		strunzone(_MapInfo_filtered);
	_MapInfo_filtered = MapInfo_FilterGametype_Recursive(pGametype, pFeatures, 0, _MapInfo_globcount);
	if(!_MapInfo_filtered)
	{
		dprint("Autogenerated a .mapinfo, doing the rest later.\n");
		return 0;
	}
	_MapInfo_filtered = strzone(_MapInfo_filtered);
	MapInfo_count = HugeSetOfIntegers_length(_MapInfo_filtered);
	dprint("Filter ", ftos(pGametype), "/", ftos(pFeatures), " results in ", _MapInfo_filtered, "\n");
	// TODO clear cache
	return 1;
}

// load info about the i-th map into the MapInfo_Map_* globals
float MapInfo_Get_ByID(float i)
{
	// TODO check cache
	if(MapInfo_Get_ByName(_MapInfo_GlobItem(HugeSetOfIntegers_get(_MapInfo_filtered, i)), 0, 0))
	{
		// TODO save in cache
		return 1;
	}
	return 0;
}

float _MapInfo_Generate(string pFilename) // 0: failure, 1: ok ent, 2: ok bsp
{
	string fn;
	float fh;
	string s, v;
	vector o;
	float inWorldspawn, l;
	float r;
	float twoBaseModes;

	vector mapMins, mapMaxs;

	r = 1;
	fn = strcat("maps/", pFilename, ".ent");
	fh = fopen(fn, FILE_READ);
	if(fh < 0)
	{
		r = 2;
		fn = strcat("maps/", pFilename, ".bsp");
		fh = fopen(fn, FILE_READ);
	}
	if(fh < 0)
		return 0;
	print("Analyzing ", fn, " to generate initial mapinfo; please edit that file later\n");

	inWorldspawn = 2;
	MapInfo_Map_supportedGametypes = 0;

	for(;;)
	{
		if not((s = fgets(fh)))
			break;
		if(inWorldspawn == 1)
			if(startsWith(s, "}"))
				inWorldspawn = 0;
		if(inWorldspawn)
		{
			if(startsWith(s, "\"classname\" \"worldspawn\""))
				inWorldspawn = 1;
			else if((v = extractRestOfLine(s, "\"message\" \"")))
			{
				for(l = strlen(v) - 1; l > 0; --l)
					if(substring(v, l, 1) == "\"")
						break;
				MapInfo_Map_title = substring(v, 0, l);
			}
		}
		else
		{
			if((v = extractRestOfLine(s, "\"origin\" \"")))
			{
				for(l = strlen(v) - 1; l > 0; --l)
					if(substring(v, l, 1) == "\"")
						break;
				o = stov(strcat("'", substring(v, 0, l), "'"));
				mapMins_x = min(mapMins_x, o_x);
				mapMins_y = min(mapMins_y, o_y);
				mapMins_z = min(mapMins_z, o_z);
				mapMaxs_x = max(mapMaxs_x, o_x);
				mapMaxs_y = max(mapMaxs_y, o_y);
				mapMaxs_z = max(mapMaxs_z, o_z);
			}
			else if((v = extractRestOfLine(s, "\"classname\" \"")))
			{
				if(startsWith(v, "dom_controlpoint\""))
					MapInfo_Map_supportedGametypes |= MAPINFO_TYPE_DOMINATION;
				else if(startsWith(v, "item_flag_team2\""))
					MapInfo_Map_supportedGametypes |= MAPINFO_TYPE_CTF;
				else if(startsWith(v, "runematch_spawn_point\""))
					MapInfo_Map_supportedGametypes |= MAPINFO_TYPE_RUNEMATCH;
				else if(startsWith(v, "target_assault_roundend\""))
					MapInfo_Map_supportedGametypes |= MAPINFO_TYPE_ASSAULT;
				else if(startsWith(v, "onslaught_generator\""))
					MapInfo_Map_supportedGametypes |= MAPINFO_TYPE_ONSLAUGHT;
				else if(startsWith(v, "info_player_team1\""))
					++MapInfo_Map_spawnpoints;
				else if(startsWith(v, "info_player_team2\""))
					++MapInfo_Map_spawnpoints;
				else if(startsWith(v, "info_player_deathmatch\""))
					++MapInfo_Map_spawnpoints;
				else if(startsWith(v, "info_player_start\""))
					++MapInfo_Map_spawnpoints;
				else if(startsWith(v, "weapon_") && !startsWith(v, "weapon_nex\"") && !startsWith(v, "weapon_railgun\""))
					MapInfo_Map_supportedFeatures |= MAPINFO_FEATURE_WEAPONS;
			}
		}
	}
	if(inWorldspawn)
	{
		print(fn, " ended still in worldspawn, BUG\n");
		return 0;
	}
	MapInfo_Map_diameter = vlen(mapMaxs - mapMins);

	twoBaseModes = MapInfo_Map_supportedGametypes & (MAPINFO_TYPE_CTF | MAPINFO_TYPE_ASSAULT);
	if(twoBaseModes && (MapInfo_Map_supportedGametypes == twoBaseModes))
	{
		// we have a CTF-only or Assault-only map. Don't add other modes then,
		// as the map is too symmetric for them.
	}
	else
	{
		MapInfo_Map_supportedGametypes |= MAPINFO_TYPE_DEATHMATCH;      // DM always works
		MapInfo_Map_supportedGametypes |= MAPINFO_TYPE_RUNEMATCH;       // Rune always works
		MapInfo_Map_supportedGametypes |= MAPINFO_TYPE_LMS;             // LMS always works

		if(MapInfo_Map_spawnpoints >= 8  && MapInfo_Map_diameter > 4096)
			MapInfo_Map_supportedGametypes |= MAPINFO_TYPE_TEAM_DEATHMATCH;
		if(                MapInfo_Map_diameter < 4096)
			MapInfo_Map_supportedGametypes |= MAPINFO_TYPE_ARENA;
		if(MapInfo_Map_spawnpoints >= 12 && MapInfo_Map_diameter > 5120)
			MapInfo_Map_supportedGametypes |= MAPINFO_TYPE_KEYHUNT;
	}

	fclose(fh);
	dprint(fn, ": types = ", ftos(MapInfo_Map_supportedGametypes), " MapInfo_Map_spawnpoints ", ftos(MapInfo_Map_spawnpoints), " MapInfo_Map_diameter ", ftos(MapInfo_Map_diameter), "\n");
	return r;
}

void _MapInfo_Map_Reset()
{
	MapInfo_Map_title = "Untitled1";
	MapInfo_Map_description = "Bleh.";
	MapInfo_Map_supportedGametypes = 0;
	MapInfo_Map_supportedFeatures = 0;
	MapInfo_Map_diameter = 0;
	MapInfo_Map_spawnpoints = 0;
}

void _MapInfo_Map_ApplyGametype(string s, float pWantedType, float pThisType)
{
	MapInfo_Map_supportedGametypes |= pThisType;
	if(!(pThisType & pWantedType))
		return;
	
	cvar_set("fraglimit", car(s));
	s = cdr(s);

	cvar_set("timelimit", car(s));
	s = cdr(s);

	if(pWantedType == MAPINFO_TYPE_TEAM_DEATHMATCH)
	{
		cvar_set("g_tdm_teams", car(s));
		s = cdr(s);
	}

	if(pWantedType == MAPINFO_TYPE_KEYHUNT)
	{
		cvar_set("g_keyhunt_teams", car(s));
		s = cdr(s);
	}
}

// load info about a map by name into the MapInfo_Map_* globals
float MapInfo_Get_ByName(string pFilename, float pAllowGenerate, float pGametypeToSet)
{
	string fn;
	string s, t;
	float fh;
	float r;

	r = 1;

	// default all generic fields so they have "good" values in case something fails
	fn = strcat("maps/", pFilename, ".mapinfo");
	fh = fopen(fn, FILE_READ);
	if(fh < 0)
	{
		if(!pAllowGenerate)
			return 0;
		_MapInfo_Map_Reset();
		r = _MapInfo_Generate(pFilename);
		if(!r)
			return 0;
		fh = fopen(fn, FILE_WRITE);
		fputs(fh, strcat("title ", MapInfo_Map_title, "\n"));
		fputs(fh, strcat("description ", MapInfo_Map_description, "\n"));
		fputs(fh, strcat("_diameter ", ftos(MapInfo_Map_diameter), "\n"));
		fputs(fh, strcat("_spawnpoints ", ftos(MapInfo_Map_spawnpoints), "\n"));
		if(MapInfo_Map_supportedFeatures & MAPINFO_FEATURE_WEAPONS)       fputs(fh, "has weapons\n");
		if(MapInfo_Map_supportedGametypes & MAPINFO_TYPE_DEATHMATCH)      fputs(fh, "type dm 30 20\n");
		if(MapInfo_Map_supportedGametypes & MAPINFO_TYPE_TEAM_DEATHMATCH) fputs(fh, "type tdm 50 20 2\n");
		if(MapInfo_Map_supportedGametypes & MAPINFO_TYPE_DOMINATION)      fputs(fh, "type dom 200 20\n");
		if(MapInfo_Map_supportedGametypes & MAPINFO_TYPE_CTF)             fputs(fh, "type ctf 300 20\n");
		if(MapInfo_Map_supportedGametypes & MAPINFO_TYPE_RUNEMATCH)       fputs(fh, "type rune 200 20\n");
		if(MapInfo_Map_supportedGametypes & MAPINFO_TYPE_LMS)             fputs(fh, "type lms 9 20\n");
		if(MapInfo_Map_supportedGametypes & MAPINFO_TYPE_ARENA)           fputs(fh, "type arena 10 20\n");
		if(MapInfo_Map_supportedGametypes & MAPINFO_TYPE_KEYHUNT)         fputs(fh, "type kh 1000 20 3\n");
		if(MapInfo_Map_supportedGametypes & MAPINFO_TYPE_ASSAULT)         fputs(fh, "type as 20\n");
		if(MapInfo_Map_supportedGametypes & MAPINFO_TYPE_ONSLAUGHT)       fputs(fh, "type ons 20\n");
		fclose(fh);
		r = 2;
		// return r;
		fh = fopen(fn, FILE_READ);
		if(fh < 0)
			error("... but I just wrote it!");
	}

	_MapInfo_Map_Reset();
	for(;;)
	{
		if not((s = fgets(fh)))
			break;
		t = car(s); s = cdr(s);
		if     (t == "title")
			MapInfo_Map_title = t;
		else if(t == "description")
			MapInfo_Map_description = substring(s, 12, strlen(s) - 12);
		else if(t == "_diameter")
			MapInfo_Map_diameter = stof(s);
		else if(t == "_spawnpoints")
			MapInfo_Map_spawnpoints = stof(s);
		else if(t == "has")
		{
			t = car(s); s = cdr(s);
			if     (t == "weapons") MapInfo_Map_supportedFeatures |= MAPINFO_FEATURE_WEAPONS;
			else
				dprint("Map ", pFilename, " supports unknown feature ", t, ", ignored\n");
		}
		else if(t == "type")
		{
			t = car(s); s = cdr(s);
			if     (t == "dm")    _MapInfo_Map_ApplyGametype (s, pGametypeToSet, MAPINFO_TYPE_DEATHMATCH);
			else if(t == "tdm")   _MapInfo_Map_ApplyGametype (s, pGametypeToSet, MAPINFO_TYPE_TEAM_DEATHMATCH);
			else if(t == "dom")   _MapInfo_Map_ApplyGametype (s, pGametypeToSet, MAPINFO_TYPE_DOMINATION);
			else if(t == "ctf")   _MapInfo_Map_ApplyGametype (s, pGametypeToSet, MAPINFO_TYPE_CTF);
			else if(t == "rune")  _MapInfo_Map_ApplyGametype (s, pGametypeToSet, MAPINFO_TYPE_RUNEMATCH);
			else if(t == "lms")   _MapInfo_Map_ApplyGametype (s, pGametypeToSet, MAPINFO_TYPE_LMS);
			else if(t == "arena") _MapInfo_Map_ApplyGametype (s, pGametypeToSet, MAPINFO_TYPE_ARENA);
			else if(t == "kh")    _MapInfo_Map_ApplyGametype (s, pGametypeToSet, MAPINFO_TYPE_KEYHUNT);
			else if(t == "as")    _MapInfo_Map_ApplyGametype (s, pGametypeToSet, MAPINFO_TYPE_ASSAULT);
			else if(t == "ons")   _MapInfo_Map_ApplyGametype (s, pGametypeToSet, MAPINFO_TYPE_ONSLAUGHT);
			else
				dprint("Map ", pFilename, " supports unknown game type ", t, ", ignored\n");
		}
		else
			dprint("Map ", pFilename, " provides unknown info item ", t, ", ignored\n");
	}
	fclose(fh);
	print(pFilename, " -> ", ftos(MapInfo_Map_supportedGametypes), ", ", ftos(MapInfo_Map_supportedFeatures), "\n");
	if(pGametypeToSet)
		if(!(MapInfo_Map_supportedGametypes & pGametypeToSet))
			error("Can't select the requested game type. Bailing out.");
	if(MapInfo_Map_supportedGametypes != 0)
		return r;
	dprint("Map ", pFilename, " supports no game types, ignored\n");
	return 0;
}

string MapInfo_FixName(string s)
{
	// if there is exactly one map of prefix s, return it
	// if not, return the null string
	// note that DP sorts glob results... so I can use a binary search
	string match;
	float l, r, m, cmp;
	l = 0;
	r = MapInfo_count;
	// invariants: r is behind s, l-1 is equal or before
	while(l != r)
	{
		m = floor((l + r) / 2);
		cmp = strcasecmp(_MapInfo_GlobItem(HugeSetOfIntegers_get(_MapInfo_filtered, m)), s);
		if(cmp == 0)
			return s; // found and good
		if(cmp < 0)
			l = m + 1; // l-1 is before s
		else
			r = m; // behind s
	}
	// r == l, so: l is behind s, l-1 is before
	// SO: if there is any, l is the one with the right prefix
	//     and l+1 may be one too
	if(l == MapInfo_count)
		return string_null; // no match, behind last item
	match = _MapInfo_GlobItem(HugeSetOfIntegers_get(_MapInfo_filtered, l));
	if(!startsWith(match, s))
		return string_null; // wrong prefix
	if(l == MapInfo_count - 1)
		return match; // last one, nothing can follow => unique
	if(startsWith(_MapInfo_GlobItem(HugeSetOfIntegers_get(_MapInfo_filtered, l + 1)), s))
		return string_null; // ambigous match
	return match;
}

float MapInfo_CurrentFeatures()
{
	float req;
	req = 0;
	if(!(cvar("g_instagib") || cvar("g_minstagib") || cvar("g_nixnex") || cvar("g_rocketarena")))
		req |= MAPINFO_FEATURE_WEAPONS;
	return req;
}

float MapInfo_CurrentGametype()
{
	if(cvar("g_domination"))
		return MAPINFO_TYPE_DOMINATION;
	else if(cvar("g_ctf"))
		return MAPINFO_TYPE_CTF;
	else if(cvar("g_runematch"))
		return MAPINFO_TYPE_RUNEMATCH;
	else if(cvar("g_tdm"))
		return MAPINFO_TYPE_TEAM_DEATHMATCH;
	else if(cvar("g_assault"))
		return MAPINFO_TYPE_ASSAULT;
	else if(cvar("g_lms"))
		return MAPINFO_TYPE_LMS;
	else if(cvar("g_arena"))
		return MAPINFO_TYPE_ARENA;
	else if(cvar("g_keyhunt"))
		return MAPINFO_TYPE_KEYHUNT;
	else if(cvar("g_onslaught"))
		return MAPINFO_TYPE_ONSLAUGHT;
	else
		return MAPINFO_TYPE_DEATHMATCH;
}

float MapInfo_CheckMap(string s) // returns 0 if the map can't be played with the current settings, 1 otherwise
{
	if(!MapInfo_Get_ByName(s, 1, 0))
		return 0;
	if((MapInfo_Map_supportedGametypes & MapInfo_CurrentGametype()) == 0)
		return 0;
	if((MapInfo_Map_supportedFeatures & MapInfo_CurrentFeatures()) != MapInfo_CurrentFeatures())
		return 0;
	return 1;
}

void MapInfo_LoadMap(string s)
{
	if(!MapInfo_CheckMap(s))
	{
		print("EMERGENCY: can't play the selected map in the given game mode. Falling back to deathmatch.\n");
		cvar_set("g_domination", "0");
		cvar_set("g_ctf", "0");
		cvar_set("g_runematch", "0");
		cvar_set("g_tdm", "0");
		cvar_set("g_assault", "0");
		cvar_set("g_lms", "0");
		cvar_set("g_arena", "0");
		cvar_set("g_keyhunt", "0");
		cvar_set("g_onslaught", "0");
	}
	MapInfo_Get_ByName(s, 1, MapInfo_CurrentGametype());
	localcmd(strcat("\nchangelevel ", s, "\n"));
}

string MapInfo_ListAllowedMaps()
{
	string out;
	float i;

	// to make absolutely sure:
	MapInfo_Enumerate();
	for(;;)
		if(MapInfo_FilterGametype(MapInfo_CurrentGametype(), MapInfo_CurrentFeatures()))
			break;

	out = "";
	for(i = 0; i < MapInfo_count; ++i)
		out = strcat(out, " ", _MapInfo_GlobItem(HugeSetOfIntegers_get(_MapInfo_filtered, i)));
	return substring(out, 1, strlen(out) - 1);
}