#include <iostream>
#include <fstream>
#include <map>
#include <vector>
#include <algorithm>   // for sort
#include <set>
#include <string>
#include <sstream> 
#include <cstdlib>     // for exit
using namespace std;

#include "ctimer.h"

/**
 * Show some STL sort functions and overloaded operators
 * 
 * @author Owen Astrachan
 */

ostream& operator <<(ostream& out, const pair<string,int>& p)
// post: string and int printed, int first
{
    out << p.second << "\t" << p.first;
    return out;
}

class WordTracker
{
  public:
    WordTracker();
    virtual void read(const string& filename);
    virtual void top(int n, vector<pair<string,int> >& v);
    
  protected:

    map<string,int> myMap;
};

WordTracker::WordTracker()
{
    // nothing to do currently
}

void WordTracker::read(const string& filename)
{
    ifstream input(filename.c_str());
    string word;
    while (input >> word){
	myMap[word]++;
    }
}


bool sortoccurs(const pair<string,int>& lhs,
		const pair<string,int>& rhs)
{
    return lhs.second > rhs.second;
}


void WordTracker::top(int n, vector<pair<string,int> >& v)
{
    v.clear();
    
    // copy(myMap.begin(), myMap.end(), back_inserter(v));
    
    map<string,int>::iterator it = myMap.begin();
    while (it != myMap.end()){
	v.push_back(*it);
	it++;
    }

    partial_sort(v.begin(), v.begin()+n, v.end(), sortoccurs);
    // sort(v.begin(), v.end(),sortoccurs);
}


int main(int argc, char *argv[])
{
    string filename,line, w;
    if (argc == 1)
    {
	cerr << "usage: " << argv[0] << " filename" << endl;
	exit(1);
    }
    filename = argv[1];
    WordTracker tracker;

    CTimer timer;    
    timer.start();    
    tracker.read(filename);
    vector<pair<string,int> > v;    
    tracker.top(50,v);
    timer.stop();
    
    for(int k=0; k < 53; k++){
	cout << v[k] << endl;
    }
    cout << "time = " << timer.elapsedTime() << endl;
    return 0;
}