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

#include "ctimer.h"
#include "randgen.h"

class SearchDemo
{
  public:
      void initialize(const string& filename);
      void searchSequential(int amount);
      void searchBinary(int amount);
  private:
    vector<string> myWords;
    RandGen myRandom;
};

char makelower(char ch){
    return tolower(ch);
}

void SearchDemo::initialize(const string& filename){

    CTimer timer;
    timer.start();
    ifstream input(filename.c_str());
    int total = 0;
    string word;
    set<string> unique;
    while (input >> word){
        transform(word.begin(), word.end(),
                  word.begin(), makelower);
        unique.insert(word);
        total++;
    }
    myWords = vector<string>(unique.begin(), unique.end());
    timer.stop();
    cout << "read " << total << " words " << unique.size() << " unique" << endl;
    cout << "reading time " << timer.elapsedTime() << endl;
    timer.start();
    sort(myWords.begin(), myWords.end());
    timer.stop();
    cout << "sorting time " << timer.elapsedTime() << endl;
}

void SearchDemo::searchBinary(int amount){
    CTimer timer;
    timer.start();
    for(int k=0; k < amount; k++){
        int index = myRandom.randInt(myWords.size());
        vector<string>::iterator it = lower_bound(myWords.begin(), myWords.end(),myWords[index]);
//        bool result = binary_search(myWords.begin(), myWords.end(),myWords[index]);
        if (*it != myWords[index]){
        		cout << "search error at " << index << endl;
        }
    }
    timer.stop();
    cout << "time for " << amount << " binary searches " << timer.elapsedTime() << endl;
}

void SearchDemo::searchSequential(int amount){
    CTimer timer;
    timer.start();
    for(int k=0; k < amount; k++){
        int index = myRandom.randInt(myWords.size());
        string key = myWords[index];
        vector<string>::iterator it = find(myWords.begin(), myWords.end(),myWords[index]);
//        for(int j=0; j < myWords.size(); j++){
//        	    if (myWords[j] == key) break;
//        }
//        if (*it != myWords[index]){
//        		cout << "search error at " << index << endl;
//        }
    }
    timer.stop();
    cout << "time for " << amount << " sequential searches " << timer.elapsedTime() << endl;
}

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

    SearchDemo sd;
    sd.initialize(argv[1]);
    int count = atoi(argv[2]);
	
    sd.searchSequential(count);
    sd.searchBinary(count);

    return 0;
}