#include <queue>
#include <string>
#include <iostream>

class Record {
	private:
		std::string first_name;
		std::string last_name;
		unsigned int id_number;
		std::string user_id;

	public:
		Record( std::string, std::string, unsigned int, std::string );
		void print() const;

		class Alphabetical_sort {
			public:
				bool operator() ( Record const &,
			             	Record const & );
		};

		class ID_number_sort {
			public:
				bool operator() ( Record const &,
			             	Record const & );
		};

		class User_id_sort {
			public:
				bool operator() ( Record const &,
			             	Record const & );
		};

	friend class Alphabetical_sort;
	friend class ID_number_sort;
	friend class User_id_sort;
};

Record::Record( std::string a, std::string b, unsigned int c, std::string d ):
first_name( a ),
last_name( b ),
id_number( c ),
user_id( d ) {
	// Does nothing
}

void Record::print() const {
	std::cout << last_name << ", " << first_name << "  " << user_id << " (" << id_number << ")" << std::endl;
}

bool Record::Alphabetical_sort::operator() ( Record const &a, Record const &b ) {
	return ( a.last_name > b.last_name ) || (a.last_name == b.last_name && a.first_name > b.first_name );
}

bool Record::ID_number_sort::operator() ( Record const &a, Record const &b ) {
	return a.id_number > b.id_number;
}

bool Record::User_id_sort::operator() ( Record const &a, Record const &b ) {
	return a.user_id > b.user_id;
}

int main() {
	int const N = 13;
	Record array[N] = {
		Record( "Douglas", "Harder", 0, "dwharder" ),
		Record( "Peter", "Cushing", 1, "pcushing" ),
		Record( "William", "Hartnell", 2, "whartnel" ),
		Record( "Patrick", "Troughton", 3, "ptrought" ),
		Record( "Jon", "Pertwee", 4, "jpertwee" ),
		Record( "Tom", "Baker", 5, "tbaker" ),
		Record( "Peter", "Davidson", 6, "pdavidso" ),
		Record( "Colin", "Baker", 7, "cbaker" ),
		Record( "Sylverster", "McCoy", 8, "smccoy" ),
		Record( "Paul", "McGann", 9, "pmcgann" ),
		Record( "Christopher", "Eccleston", 10, "cecclest" ),
		Record( "David", "Tennant", 11, "dtennant" ),
		Record( "Matt", "Smith", 12, "msmith" )
	};

	std::priority_queue< Record, std::vector< Record >, Record::Alphabetical_sort > pq_alpha;
	std::priority_queue< Record, std::vector< Record >, Record::User_id_sort > pq_user;
	std::priority_queue< Record, std::vector< Record >, Record::ID_number_sort > pq_number;

	for ( int i = 0; i < N; ++i ) {
		pq_alpha.push( array[i] );
		pq_user.push( array[i] );
		pq_number.push( array[i] );
	}

	std::cout << "Alphabetical order:" << std::endl;

	for ( int i = 0; i < N; ++i ) {
		pq_alpha.top().print();
		pq_alpha.pop();
	}

	std::cout << std::endl << std::endl << "User ID order:" << std::endl;

	for ( int i = 0; i < N; ++i ) {
		pq_user.top().print();
		pq_user.pop();
	}

	std::cout << std::endl << std::endl << "ID# order:" << std::endl;

	for ( int i = 0; i < N; ++i ) {
		pq_number.top().print();
		pq_number.pop();
	}

	std::cout << std::endl;

	return 0;
}