/* Lecture code 7.0
 *
 * The CityFinder example.  For this code to work correctly, you'll need to place it in the
 * same directory as the place-data.txt file bundled as lecture code 7.1.  Feel free to play
 * around with this code - if you come up with any interesting examples, I'd love to see them.
 *
 * Comments have been added to the relevant sections.
 */

#include <iostream>
#include <string>
#include <sstream>
#include <map>
#include <set>
#include <fstream>
#include <vector>
#include <algorithm> // for set_intersection
#include <iterator>  // for back_inserter.
using namespace std;

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

/* 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 DegreesPerMile = 1.0 / 69.172;

/* A useful typedef so that we don't have to explicitly
 * spell out the full type of the coordinate lookup maps.
 * typedef works like const but on types and can be used to
 * create aliases for existing data types.
 */
typedef multimap<double, cityT*> CoordLookup;

/* 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;
		city.name = name;
		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;
}

/* Given a map from city names to cityT structs, populates the
 * longLookup and latLookup tables to be lookups from longitude to
 * city and latitude to city.
 */
void PopulateLookupTables(map<string, cityT>& cityLookup,
			  CoordLookup& longLookup,
			  CoordLookup& latLookup)
{
	for(map<string, cityT>::iterator itr = cityLookup.begin();
		itr != cityLookup.end(); ++itr)
	{
		/* Recall that itr->second is the value part of a key/value pair.
		 * This means that itr->second is the cityT associated with the current
		 * key.
		 */
		longLookup.insert(make_pair(itr->second.longitude, &itr->second));
		latLookup.insert(make_pair(itr->second.latitude, &itr->second));
	}
}

/* Actually runs the algorithm.  Remember that we'll be computing slices of
 * longitude and latitude that happen to be near the target city, then intersecting
 * them.
 */
void FindNearbyCities(cityT& center, double radius,
					  CoordLookup& longLookup,
					  CoordLookup& latLookup)
{
	/* Compute two sets - one of cities with nearby longitude and one with
	 * nearby latitude.
	 */
	set<cityT*> nearbyLongs, nearbyLats;
	
	/* Use lower_bound and upper_bound to only iterate over the slices we want to
	 * consider.  Note that in professional code you would probably compute upper_bound
	 * just once and store it outside the for loop rather than recomputing it multiple
	 * times.
	 */
	for(CoordLookup::iterator itr = longLookup.lower_bound(center.longitude - radius);
	    itr != longLookup.upper_bound(center.longitude + radius); ++itr)
		nearbyLongs.insert(itr->second);

	for(CoordLookup::iterator itr =
			latLookup.lower_bound(center.latitude - radius);
		itr != latLookup.upper_bound(center.latitude + radius); ++itr)
		nearbyLats.insert(itr->second);

	/* Use the set_intersection algorithm to compute the intersection of the two
	 * city ranges.  This uses iterator adapters and algorithms, which we haven't
	 * covered yet, so be sure to consult the STL Iterators 2 and STL Algorithms
	 * handouts once they're available for more information.
	 */
	vector<cityT*> intersection;
	set_intersection(nearbyLongs.begin(), nearbyLongs.end(),
					 nearbyLats.begin(), nearbyLats.end(),
					 back_inserter(intersection));

	/* Manually iterate over the vector and check to see that each point is indeed
	 * within the bounds we want.
	 */
	for(int i = 0; i < intersection.size(); ++i)
	{
		double dx = intersection[i]->longitude - center.longitude;
		double dy = intersection[i]->latitude - center.latitude;
		if(dx * dx + dy * dy <= radius * radius)
			cout << intersection[i]->name << endl;
	}
}

int main()
{
	map<string, cityT> cityLookup;
	CoordLookup longLookup;
	CoordLookup 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 == "")
			break;

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

		if(itr != cityLookup.end())
		{
			cout << "Enter radius: ";
			double radius = GetPositiveReal() * DegreesPerMile;
			FindNearbyCities(itr->second, radius,
							 longLookup, latLookup);
		}
		else
			cout << "City not found." << endl;
	}

	return 0;
}