#include <algorithm>
#include <functional>
#include <map>
#include <list>
#include <iostream>
#include <utility>
#include <string>
using namespace std;

void printString(const string& str)
{
  cout << " {" << str << "}";
}

void printCounty(const pair<const string, list<string> >& county)
{
  cout << county.first << ":";
  for_each(county.second.begin(), county.second.end(), &printString);
  cout << endl;
}

//
// NameInList
//
// Functor to check if a string is in a list of strings (supplied
// at construction time).
//
class NameInList : public unary_function<string, bool>
{
public:
  NameInList(const list<string>& names) : mNames(names) {}
  bool operator() (const string& val);

protected:
  const list<string>& mNames;
};

//
// function-call operator for NameInList functor
//
// Returns true if it can find name in mNames, false otherwise.
// Uses find() algorithm.
//
bool NameInList::operator() (const string& name)
{
  return (find(mNames.begin(), mNames.end(), name) != mNames.end());
}


//
// RemoveNames
//
// Functor class that takes a string/list<string> pair and removes
// any strings from the list that are found in a list of names
// (supplied in the constructor).
//
class RemoveNames : public unary_function<pair<const string, list<string> >,
    void>
{
public:
  RemoveNames(const list<string>& names) : mNames(names) {}
  void operator() (pair<const string, list<string> >& val);

protected:
  const list<string>& mNames; 
};



//
// Function-call operator for RemoveNames functor.
//
// Uses remove_if() followed by erase to actually delete the names
// from the list.
//
// Names are removed if they are in our list of mNames. Use the NameInList
// functor to check if the name is in the list.
//
void RemoveNames::operator() (pair<const string, list<string> >& val)
{
  list<string>::iterator it = remove_if(val.second.begin(), val.second.end(),
					NameInList(mNames));
  val.second.erase(it, val.second.end());
} 

//
// getDuplicates()
//
// Returns a list of all names that appear in more than one list in
// the map.
//
// The implementation generates one large list of all the names from
// all the lists in the map, sorts it, then finds all duplicates
// in the sorted list with adjacent_find().
//
list<string> getDuplicates(const map<string, list<string> >& voters)
{
  list<string> allNames, duplicates;

  // Collect all the names from all the lists into one big list
  map<string, list<string> >::const_iterator it;
  for(it = voters.begin(); it != voters.end(); ++it) {
    allNames.insert(allNames.end(), it->second.begin(), it->second.end());
  }

  // sort the list -- use the list version, not the general algorithm,
  // because the list version is faster
  allNames.sort();

  //
  // Now that it's sorted, all duplicate names will be next to each other.
  // Use adjacent_find() to find instances of two or more identical names
  // next to each other.
  //
  // Loop until adjacent_find returns the end iterator.
  //
  list<string>::iterator lit;
  for (lit = allNames.begin(); lit != allNames.end(); ++lit) {
    lit = adjacent_find(lit, allNames.end());
    if (lit == allNames.end()) {
      break;
    }
    duplicates.push_back(*lit);
  }

  //
  // If someone was on more than two voter lists, he or she will
  // show up more than once in the duplicates list. Sort the list
  // and remove duplicates with unique.
  //
  // Use the list versions because they are faster than the generic versions.
  //
  duplicates.sort();
  duplicates.unique();

  return (duplicates);
}


//
// auditVoterRolls
//
// Expects a map of string/list<string> pairs keyed on county names
// and containing lists of all the registered voters in those counties.
//
// Removes from each list any name on the convictedFelons list and
// any name that is found on any other list.
//
void auditVoterRolls(map<string, list<string> >& votersByCounty,
		     const list<string>& convictedFelons)
{
  // get all the duplicate names
  list<string> duplicates = getDuplicates(votersByCounty);

  // combine the duplicates and convicted felons -- we want
  // to remove names on both lists from all voter rolls
  duplicates.insert(duplicates.end(), convictedFelons.begin(),
		    convictedFelons.end());

  // If there were any duplicates, remove them.
  // Use the list versions of sort and unique instead of the generic
  // algorithms, because the list versions are more efficient.
  duplicates.sort();
  duplicates.unique();

  // Now remove all the names we need to remove
  for_each(votersByCounty.begin(), votersByCounty.end(),
	   RemoveNames(duplicates));
}

int main(int argc, char** argv)
{
  map<string, list<string> > voters;
  list<string> nameList, felons;
  nameList.push_back("Amy Aardvark");
  nameList.push_back("Bob Buffalo");
  nameList.push_back("Charles Cat");
  nameList.push_back("Dwayne Dog");

  voters.insert(make_pair("Orange", nameList));

  nameList.clear();
  nameList.push_back("Elizabeth Elephant");
  nameList.push_back("Fred Flamingo");
  nameList.push_back("Amy Aardvark");

  voters.insert(make_pair("Los Angeles", nameList));

  nameList.clear();
  nameList.push_back("George Goose");
  nameList.push_back("Heidi Hen");
  nameList.push_back("Fred Flamingo");

  voters.insert(make_pair("San Diego", nameList));

  felons.push_back("Bob Buffalo");
  felons.push_back("Charles Cat");

  for_each(voters.begin(), voters.end(), &printCounty);
  cout << endl;
  auditVoterRolls(voters, felons);
  for_each(voters.begin(), voters.end(), &printCounty);

  return (0);
}