/* The CityFinder example from Thursday's lecture.
 *
 * Comments have been added to the relevant sections.
 */

#include <iostream>
#include <string>
#include <sstream>
#include <map>
#include <set>
#include <fstream>
#include <algorithm> // For set_intersection
#include <iterator>  // For inserter
using namespace std;

/* Type: cityT
 * A type that stores a city's longitude, and latitude.
 */
struct cityT
{
	double latitude;
	double longitude;
};

/* The number of degrees of longitude per mile, when.
 * measured at the equator.  This number is mostly
 * accurate for the US, though for polar regions in
 * Alaska might be a bit skewed.
 */
const double kDegreesPerMile = 1.0 / 69.172;

/* Straight out of the earlier lecture code. */
string GetLine()
{
	string result;
	getline(cin, result);
	return result;
}

/* A modified version of the GetInteger function
 * that accepts positive real numbers.
 */
double GetPositiveReal()
{
	while(true)
	{
		stringstream converter;
		converter << GetLine();
		
		double result;
		converter >> result;
		if(converter.fail())
			cout << "Please enter a real number." << endl;
		else
		{
			char ch;
			converter >> ch;
			
			if(converter.fail())
			{
				if(result > 0.0)
					return result;
				else
					cout << "Please enter a positive real number." << endl;
			}
			else
				cout << "Unexpected character: " << ch << endl;
		}
		
		cout << "Retry: ";
	}
}

/* Loads the place-data.txt file from disk and populates a
 * map<string, cityT> with the information.
 */
void LoadData(map<string, cityT> &cityLookup)
{
	ifstream input("place-data.txt");
	string data, name;

	/* This uses a bit of shorthand that reads in the line and then
	 * continues looping while the input stream isn't in a fail state.
	 * In general, you can test if(myStream) as shorthand for
	 * if(!myStream.fail());
	 */
	while(getline(input, name))
	{
		/* Assuming data is well-formatted, read in the line
		 * with the longitude and latitude data and run it
		 * through a stringstream.
		 */
		getline(input, data);
		stringstream converter(data);

		/* Load the information into the cityT struct.
		 * We'll assume the file is well-formed.
		 */
		cityT city;
		converter >> city.latitude;
		converter >> city.longitude;

		/* Insert the key-value pair "name: city" into the map. */
		cityLookup.insert(make_pair(name, city));
	}

	/* Print some useful information out. */
	cout << "Data exists for ";
	cout << cityLookup.size() << " cities." << endl;
}

/* Useful typedefs to simplify the code we'll be writing.
 * The code is much longer without these!
 */
typedef multimap<double, string> CoordMap;
typedef map<string, cityT> CityMap;

/* Given a map from strings to cityTs, construct two
 * multimaps mapping from doubles to cityTs that correspond
 * to the longitude and latitudes of the cities.
 */
void PopulateLookupTables(CityMap& cityLookup, CoordMap& longLookup, CoordMap& latLookup)
{
	for(CityMap::iterator itr = cityLookup.begin(); itr != cityLookup.end(); ++itr)
	{
		/* Key should be longitude (latitude) of the
		 * element being iterated over with value
		 * equal to the city name.
		 */
		longLookup.insert(make_pair(itr->second.longitude, itr->first));
		latLookup.insert(make_pair(itr->second.latitude, itr->first));
	}
}

/* Runs the algorithm described in class to locate cities
 * near the center city.
 */
void FindNearbyCities(CoordMap& longLookup, CoordMap& latLookup, cityT center, double radius,
					  CityMap& cityLookup)
{
	/* Find cities with nearby longitudes.  Note that if
	 * we wanted to performance-tune this code we would
	 * pull the code for computing upper_bound out of the
	 * loop to avoid recomputing it.
	 */
	set<string> nearbyLongs;
	for(CoordMap::iterator itr = longLookup.lower_bound(center.longitude - radius);
		itr != longLookup.upper_bound(center.longitude + radius); ++itr)
		nearbyLongs.insert(itr->second);

	/* Repeat the above for latitude. */
	set<string> nearbyLats;
	for(CoordMap::iterator itr = latLookup.lower_bound(center.latitude - radius);
		itr != latLookup.upper_bound(center.latitude + radius); ++itr)
		nearbyLats.insert(itr->second);

	/* Using the set_intersection algorithm, compute the
	 * intersection of these sets.  We'll discuss algorithms
	 * more next week.
	 */
	set<string> intersection;
	set_intersection(nearbyLongs.begin(), nearbyLongs.end(),
					 nearbyLats.begin(), nearbyLats.end(),
					 inserter(intersection, intersection.begin()));

	/* Finally, iterate over the intersection and see what
	 * cities are in range.
	 */
	for(set<string>::iterator itr = intersection.begin(); itr != intersection.end(); ++itr)
	{
		cityT city = cityLookup[*itr];
		double dx = city.longitude - center.longitude;
		double dy = city.latitude  - center.latitude;

		if(dx * dx + dy * dy <= radius * radius)
			cout << *itr << endl;
	}
}

int main()
{
	/* The city lookup tables. */
	map<string, cityT> cityLookup;
	multimap<double, string> longLookup;
	multimap<double, string> latLookup;
	
	/* Fill our tables with some info. */
	LoadData(cityLookup);
	PopulateLookupTables(cityLookup, longLookup, latLookup);

	while(true)
	{
		/* Prompt the user for a city name. */
		cout << "Please enter a city: ";
		string city = GetLine();

		/* If the user just hit enter, we're done. */
		if(city.empty())
			break;

		/* Look up the city, print data if found. */
		map<string, cityT>::iterator itr = cityLookup.find(city);

		/* If the city exists, ask the user for more information. */
		if(itr != cityLookup.end())
		{
			cout << "Enter radius: ";
			double radius = GetPositiveReal() * kDegreesPerMile;

			FindNearbyCities(longLookup, latLookup,	itr->second, radius, cityLookup);
		}
		else
			cout << "City not found." << endl;
	}

	return 0;
}