/* Lecture code 12.1
 *
 * Using a functor to perform a biased sort.  Elements added to a specific
 * set are treated as higher-priority than other elements.
 */

#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>
#include <vector>
#include <set>
#include <fstream>
using namespace std;

const int PREFIX_LENGTH = 20;

/* Functor class that can compare two elements by priority, then name,
 * as well as adding strings to the priority set.
 */
class BiasedSort
{
public:
	void addString(const string& str)
	{
		priority.insert(str);
	}
	bool operator() (const string& one, const string& two) const
	{
		const bool isOnePriority = priority.find(one) != priority.end();
		const bool isTwoPriority = priority.find(two) != priority.end();

		/* If both have high priority, just return the default comparison. */
		if(isOnePriority && isTwoPriority)
			return one < two;
		/* If one has priority and two does not, it compares less than
		 * automatically.
		 */
		if(isOnePriority)
			return true;
		/* If two has priority and one does not, one automatically is greater
		 * than two.
		 */
		if(isTwoPriority)
			return false;

		/* Otherwise, just return the comparison of the two elements. */
		return one < two;
	}

private:
	set<string> priority;
};


int main()
{
	/* Read data into a vector. */
	ifstream input("scrambled-cities.txt");
	string line;
	vector<string> cityData;
	while(getline(input, line))
		cityData.push_back(line);

	/* Push some elements to front, sort the rest. */
	BiasedSort comp;
	comp.addString("Stanford, CA");
	comp.addString("Washington DC");
	comp.addString("Barrow, AK");

	/* Sort according to comp. */
	sort(cityData.begin(), cityData.end(), comp);

	/* Print first twenty elements.  This assumes that the size is greater than
	 * 20, which should be valid.
	 */
	copy(cityData.begin(), cityData.begin() + PREFIX_LENGTH, ostream_iterator<string>(cout, "\n"));
	return 0;
}