#include <iostream>
#include <string>
using namespace std;

#include "ctimer.h"
#include "tpq.h"
#include "comparer.h"

/**
 * Revcomp compares strings "backwards": aardvark > zebra
 */
    
template <class Kind>
struct Revcomp : public Comparer<Kind>
{
    int compare(const Kind& lhs, const Kind& rhs) const
    {
	if (lhs < rhs)      return 1;
	else if (rhs < lhs) return -1;
	else                return 0;
    }
};

void printall(const tpqueue<string>& pq)
// post: pq elements printed
{
    CTimer timer;
    string w;
    timer.Start();
    tpqueue<string> copy = pq;
    
    while (copy.size() > 0) {
	copy.deletemin(w);
	cout << w << endl;
    }
    timer.Stop();
    cout << "remove time: " << timer.ElapsedTime() << endl;
}

int main()
{
    Revcomp<string> rcomp;

    tpqueue<string> pq(rcomp);
    tpqueue<string> pq2;
    string w;

    CTimer timer;

    timer.Start();
    while (cin >> w) {
	pq.insert(w);
	pq2.insert(w);
    }
    timer.Stop();
    cout << pq.size() << "\tread/store " << timer.ElapsedTime() << endl;

    printall(pq);
    cout << "----------" << endl;
    printall(pq2);
    
    return 0;
}