/* Lecture Code 5.0
 *
 * The City Locator example.  This code is extremely dense
 * and I've attempted to comment it as much as possible.  Feel
 * free to email me with any questions.
 */

#include <iostream>
#include <string>
#include <sstream>
#include <map>
#include <set>
#include <fstream>
#include <algorithm>
using namespace std;

/* Type: cityT
 * A type that stores a city's name, longitude, and latitude.
 * The reason this struct stores all three is so that any of 
 * the map/multimaps we use can get all of the city info without
 * having to include its key as part of the data.
 */
struct cityT
{
	string name;
	double latitude;
	double longitude;
};

/* The number of degrees of longitude per mile.  This number is
 * mostly accurate, though for polar regions in Alaska might be
 * a bit skewed.
 */
const double DegreesPerMile = 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 real numbers.
 */
double GetReal()
{
	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())
				return result;
			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);

		/* We're storing everything as pointers so that when
		 * we change views using the multimaps we don't end up
		 * with all sorts of copies of the data floating around.
		 */
		cityT *city = new cityT;
		city->name = name;
		converter >> city->latitude;
		converter >> city->longitude;

		/* Insert the key-value pair "name: city" into the map.
		 * Note that I don't need to explicitly typecast from a
		 * C string to a C++ string since the variable 'name' is
		 * already a C++ string.
		 */
		cityLookup.insert(make_pair(name, city));
	}

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

/* Cleans up all the dynamically-allocated cityT objects. */
void FreeData(map<string, cityT *> &data)
{
	for(map<string, cityT *>::iterator itr = data.begin();
		itr != data.end(); ++itr)
		delete itr->second;
}

/* Build lookup tables from longitude and latitude to cityT *'s. */
void Populate(map<string, cityT *> & cityLookup,
			  multimap<double, cityT *> &longLookup,
			  multimap<double, cityT *> &latLookup)
{
	for(map<string, cityT *>::iterator itr = cityLookup.begin();
		itr != cityLookup.end(); ++itr)
	{
		longLookup.insert(make_pair(itr->second->longitude, itr->second));
		latLookup.insert(make_pair(itr->second->latitude, itr->second));
	}
}

/* Look up the nearby cities.  The algorithm finds nearby cities by longitude and latitude,
 * finds the overlapping cities, then iterates looking for nearby ones. */
void DoLookup(multimap<double, cityT *> &longLookup,
			  multimap<double, cityT *> &latLookup,
			  cityT * center, double radius)
{
	/* Find cities with nearby longitude. */
	set<cityT *> nearbyLongs;
	for(multimap<double, cityT *>::iterator itr = longLookup.lower_bound(center->longitude - radius);
		itr != longLookup.upper_bound(center->longitude + radius); ++itr)
		nearbyLongs.insert(itr->second);

	/* Find cities with nearby latitude. */
	set<cityT *> nearbyLats;
	for(multimap<double, cityT *>::iterator itr = latLookup.lower_bound(center->latitude - radius);
		itr != latLookup.upper_bound(center->latitude + radius); ++itr)
		nearbyLats.insert(itr->second);

	/* Take the intersection using an insert_iterator. */
	set<cityT *> theSquare;
	set_intersection(nearbyLongs.begin(), nearbyLongs.end(),
					 nearbyLats.begin(), nearbyLats.end(),
					 inserter(theSquare, theSquare.begin()));

	/* Now manually loop over the cities in the box looking for nearby ones. */
	for(set<cityT *>::iterator itr = theSquare.begin();
		itr != theSquare.end(); ++itr)
	{
		double dx = (*itr)->longitude - center->longitude;
		double dy = (*itr)->latitude - center->latitude;
		if(dx * dx + dy * dy <= radius * radius)
			cout << (*itr)->name << endl;
	}
}


int main()
{
	map<string, cityT *> cityLookup;
	multimap<double, cityT *> longLookup;
	multimap<double, cityT *> latLookup;
	
	/* Fill our tables with some info. */
	LoadData(cityLookup);
	Populate(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 a radius, in miles: ";
			double radius = GetReal() * DegreesPerMile;
			DoLookup(longLookup, latLookup, itr->second, radius);
		}
		else
			cout << "City not found." << endl;
	}

	FreeData(cityLookup);
	return 0;
}