#include <ctime>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include "cs2hashset.h"

using std::cout;
using std::endl;
using std::ifstream;
using std::ofstream;
using std::sort;
using std::string;
using std::vector;
using std::list;
using std::pair;
using std::set;
using std::map;
using std::priority_queue;


// ================================================================= 
// Create a random string of the specified length for testing

string random_string(int length) {
  string s = "";
  for (int i = 0; i < length; i++) {
    char c = 'a' + rand()%26;
    s += c;
  }
  return s;
}

// ================================================================= 

// A static class which stores a counter of the number of comparison
// operations that have been performed.  Several comparison operations
// are implemented to allow correct counting.

class comparison_data {
public:
  static bool lessthan(const string &a, const string &b) {    
    counter++;
    return a < b;
  }
  static bool greaterthan(const string &a, const string &b) {    
    counter++;
    return a > b;
  }
  static bool equal(const string &a, const string &b) {    
    counter++;
    return a == b;
  }
  static void count_increment() {
    counter++;
  }
  static int num_comparisons() { return counter; }
private:
  static int counter;
};

// the counter variable is initialized once
int comparison_data::counter = 0;

// ================================================================= 
// A function object that should be used with sets & maps so that the
// lessthan comparisons are correctly counted.

class lessthan_functor {
public:
  bool operator() ( const string &a, const string &b ) const {
    return comparison_data::lessthan(a,b); 
  }
};

// ================================================================= 
// A function object that should be used with priority queues so that
// the greaterthan comparisons are correctly counted.

class greaterthan_functor {
public:
  bool operator() ( const string &a, const string &b ) const {
    return comparison_data::greaterthan(a,b); 
  }
};

// ================================================================= 
// A function object that can be used with hash tables of strings

class hash_string_obj {
public:
  unsigned int operator() ( std::string const& key ) const
  {
    comparison_data::count_increment();
    //  This implementation comes from 
    //  http://www.partow.net/programming/hashfunctions/
    unsigned int hash = 1315423911;
    for(unsigned int i = 0; i < key.length(); i++)
      hash ^= ((hash << 5) + key[i] + (hash >> 2));
    return hash;
  }   
};

// =================================================================

// prototypes of the functions that perform the operations
void vector_test(const string* input_data, int input_count, const string &operation, string *output_data, int &output_count);
void list_test(const string* input_data, int input_count, const string &operation, string *output_data, int &output_count);
void set_map_test(const string* input_data, int input_count, const string &operation, string *output_data, int &output_count);
void priority_queue_test(const string* input_data, int input_count, const string &operation, string *output_data, int &output_count);
void cs2hashset_test(const string* input_data, int input_count, const string &operation, string *output_data, int &output_count);

// =================================================================

int main(int argc, char* argv[]) {

  // timing mechanism
  clock_t start, before_operation, after_operation, end;
  start = clock();

  // parse the command line arguments
  if (argc !=6 && argc != 7) {
    cout << "Error: wrong number of arguments." << endl;
    exit(1);
  }
  string data_structure = argv[1];
  string operation = argv[2];
  int input_count = atoi(argv[3]);
  string input = argv[4];
  int string_length = -1;
  string output_file;
  if (input == "random") {
    string_length = atoi(argv[5]);
    output_file = argv[6];
  } else {
    output_file = argv[5];
  } 

  // seed the random number generator
  srand(time(0));

  // load the data
  string *input_data = new string[input_count];
  if (input == "random") {
    for (int i = 0; i < input_count; i++) 
      input_data[i] = random_string(string_length);
  } else {
    ifstream istr(input.c_str());
    if (!istr) {
      cout << "Error: Can't open input file: " << input << endl;
      exit(0);
    }
    string s;
    for (int i = 0; i < input_count; i++) {
      bool success = istr >> s;
      if (!success) {
	cout << "Error: Insufficient data in input file: " << input << endl;
	exit(0);
      }
      input_data[i] = s;
    }
  }

  // prepare space for the answer
  string *output_data = new string[input_count];
  int output_count;

  // mark the time before we start
  before_operation = clock();

  // perform the operation
  if (data_structure == "vector") 
    vector_test(input_data,input_count,operation,output_data,output_count);
  else if (data_structure == "list")
    list_test(input_data,input_count,operation,output_data,output_count);
  else if (data_structure == "set/map")
    set_map_test(input_data,input_count,operation,output_data,output_count);
  else if (data_structure == "priority_queue")
    priority_queue_test(input_data,input_count,operation,output_data,output_count);
  else if (data_structure == "cs2hashset")
    cs2hashset_test(input_data,input_count,operation,output_data,output_count);
  else {
    cout << "Error: unknown data structure: " << data_structure << endl;
  }

  // mark the time once we are done
  after_operation = clock();

  // output the data
  ofstream ostr(output_file.c_str());
  for (int i = 0; i < output_count; i++) {
    ostr << output_data[i] << endl;
  }
  // cleanup
  delete [] input_data;
  delete [] output_data;

  // print statistics
  end = clock();
  double load_time = double(before_operation-start)/CLOCKS_PER_SEC;
  double operation_time = double(after_operation-before_operation)/CLOCKS_PER_SEC;
  double output_time = double(end-after_operation)/CLOCKS_PER_SEC;
  cout << "load time:       " << load_time << endl;
  cout << "operation time:  " << operation_time << endl;
  cout << "output time:     " << output_time << endl;
  cout << "num comparisons: " << comparison_data::num_comparisons() << endl;

  return 0;
}

// =================================================================

void vector_test(const string* input_data, int input_count, const string &operation, string *output_data, int &output_count) {

  // for all cases, simply put the data into a vector
  vector<string> vec;
  for (int i = 0; i < input_count; i++) 
    vec.push_back(input_data[i]);
  
  if (operation == "sort") {
    // use the vector sort algorithm
    sort(vec.begin(),vec.end(),comparison_data::lessthan);
    output_count = input_count;
    for (int i = 0; i < output_count; i++)
      output_data[i] = vec[i];
  } else if (operation == "remove_dups") {
    // don't reorder the elements, just do all pairwise comparisons
    output_count = 0;
    for (int i = 0; i < input_count; i++) {
      bool dup = false;
      for (int j = 0; j < output_count; j++) {
	if (comparison_data::equal(input_data[i],output_data[j])) {
	  dup = true;
	  break;
	}
      }
      // if it has not already been added to the output list
      if (!dup) {
	output_data[output_count] = input_data[i];
	output_count++;
      }
    }
  } else if (operation == "mode") {
    // use the vector sort algorithm
    sort(vec.begin(),vec.end(),comparison_data::lessthan);
    int current_count = 1;
    string mode;
    int mode_count = 0;
    // keep track of two pointers into the structure
    vector<string>::iterator current = vec.begin();
    ++current;
    vector<string>::iterator previous = vec.begin();
    for (; current != vec.end(); ++current, ++previous) {
      if (comparison_data::equal(*current,*previous)) {
	// if they are the same increment the count
        current_count++;
      } else if (current_count >= mode_count) {
        // found a new mode!
        mode = *previous;
        mode_count = current_count;
        current_count = 1;
      } else {
        current_count = 1;
      }
    }
    if (current_count >= mode_count) {
      // last entry is a new mode!
      mode = *previous;
      mode_count = current_count;
    }
    // save the mode to the output vector
    output_count = 1;
    output_data[0] = mode;
  } else {
    cout << "Error: Unknown operation: " << operation << endl;
    exit(0);
  }
}

// =================================================================

void list_test(const string* input_data, int input_count, const string &operation, string *output_data, int &output_count) {
  cout << "Error: Unknown operation: " << operation << endl;
  exit(0);
}

// =================================================================

void set_map_test(const string* input_data, int input_count, const string &operation, string *output_data, int &output_count) {

  // HINT: declare your set like this:
  //   set<string,lessthan_functor> st;
  // HINT: declare your map like this:
  //   map<string,int,lessthan_functor> mp;

  cout << "Error: Unknown operation: " << operation << endl;
  exit(0);
}

// =================================================================

void priority_queue_test(const string* input_data, int input_count, const string &operation, string *output_data, int &output_count) {

  // HINT: declare your priority_queue like this:
  //   priority_queue<string,vector<string>,greaterthan_functor> pq(input_data,input_data+input_count);

  cout << "Error: Unknown operation: " << operation << endl;
  exit(0);
}

// =================================================================

void cs2hashset_test(const string* input_data, int input_count, const string &operation, string *output_data, int &output_count) {

  // HINT: declare your cs2hashset like this:
  //   cs2hashset<string,hash_string_obj> ht(input_count);

  cout << "Error: Unknown operation: " << operation << endl;
  exit(0);
}

// =================================================================