#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <unistd.h>
#include <assert.h>
#include <string.h>
#include <ctype.h>
#include <vector>
#include <map>

// Sample code for homework assignment in String matching 2013
// Author: Brona Brejova
// Usage of this program is explained in function printError
// Implement classes FrequencyMap and FrequencyTrie.
// Then uncomment lines creating their instances in the main program
// and you are ready...

using namespace std;

// Several definitions of useful types

// Word is a vector of integers
typedef vector <int> Word;
// List of words is a vector of words
typedef vector <Word> WordList;
// Pair of word and its occurrence counter
typedef pair <Word,int> WordCount;
// List of words with their occurrence counts
typedef vector <WordCount> WordCountList;

// Return the number of seconds since the epoch
double getTime(void)
{
  struct timeval tv;
  struct timezone tz;

  gettimeofday(&tv,&tz);
  double res = tv.tv_sec;
  res += tv.tv_usec/1e6; // add microseconds
  return res;
}

// Abstract class providing common interface 
// for different implementations of the requested data structure
class Frequency {
public:
  virtual void add(const Word &w) = 0;
  virtual WordCountList frequent(int k) = 0;
  virtual ~Frequency() {};
};

// Map-based implementation
class FrequencyMap : public Frequency {
  // Your code here...
};

// Trie-based implementation
class FrequencyTrie : public Frequency {
  // Your code here...
};

// Print error message and exit. 
// If program is not null, print usage explanation.
// If error is not null, print supplied error message.
void printError(const char *program, const char *error) {
  if(program) {
    fprintf(stderr, "\nUsage: %s sigma k repeats program\n", program);
    fprintf(stderr, "Program is M for map or T for trie\n");
    fprintf(stderr, "Input file should be on standard input.\n");
    fprintf(stderr, "Output is written to standard output.\n\n");
  }
  if(error) {
    fprintf(stderr, "%s\n", error);
  }
  exit(1);
}

// Parse input in a given file to a list of words
WordList parseInput(FILE *in, int sigma) {
  WordList result;  // resulting list of words
  Word w;  // current word, possibluy not complete
  int first = 'a'; // first and last valid letter
  int lastGood = first+sigma-1;
  int last = 'z';

  while(!feof(in)) { // read file one character at a time
    int c = tolower(fgetc(in));
    // proper character found, add to w
    if(c>=first && c<=last) {
      if(c>lastGood) {
	printError(0, "Wrong character on input, check alphabet size.");
      }
      w.push_back(c-first);
    }
    // some other character - store word w in result
    else {
      if(w.size()>0) {
	result.push_back(w);
	w.clear();
      }
    }
  }
  // after finishing reading, store the last word
  if(w.size()>0) {
    result.push_back(w);
  }
  return result;
}

// Print one word to the given output file
// converting from numbers of letters
void printWord(FILE *out, const Word & w) {
  for(unsigned int i=0; i<w.size(); i++) {
    char c = w[i]+'a';
    fputc(c, out);
  }
}

int main(int argc, char **argv) 
{  
  //Process the command-line arguments
  if(argc!=5) { 
    printError(argv[0], "Wrong number of arguments.");
  }

  int ret;
  int sigma=0;
  ret = sscanf(argv[1], "%d", &sigma);
  if(ret!=1 || sigma<=0 || sigma>26) {
    printError(argv[0], "Wrong sigma.");
  }

  int k=0;
  ret = sscanf(argv[2], "%d", &k);
  if(ret!=1 || k<=0) {
    printError(argv[0], "Wrong k.");
  }

  int repeat=0;
  ret = sscanf(argv[3], "%d", &repeat);
  if(ret!=1 && repeat<=0) {
    printError(argv[0], "Wrong number of repeats.");
  }

  if(strlen(argv[4])!=1) {
    printError(argv[0], "Wrong program specified.");
  }
  char program  = argv[4][0];
  if(program!='M' && program!='T') {
    printError(argv[0], "Wrong program specified.");
  }

  // read text from standard input and parse into words
  WordList inputList = parseInput(stdin, sigma);
  // compute total length of all words
  int n = 0;
  for(unsigned int i = 0; i<inputList.size(); i++) {
    n+=inputList[i].size();
  }

  //start measuring time
  double start_time = getTime();

  //run the algorithm repeat times
  Frequency *f = 0;
  for(int repCount=0; repCount<repeat; repCount++) {
    // create new instance of appropriate class
    if(program=='M') {
      //f = new FrequencyMap(sigma);
    }
    else if(program=='T') {
      //f = new FrequencyTrie(sigma);
    }
    assert(f);
    
    // add all words to the class
    for(unsigned int i=0; i<inputList.size(); i++) {
      f->add(inputList[i]);
    }

    // delete the structure before the next run if any
    if(repCount+1<repeat) {
      delete f;
      f = 0;
    }
  }

  // stop measuring time 
  double end_time = getTime();

  // find frequently occurring words
  WordCountList output = f->frequent(k);

  // print stats
  printf("sigma %d k %d repeats %d program %c z %d n %d reported %d time %.5e\n",
	 sigma, k, repeat, program, 
	 (int)inputList.size(), n, (int)output.size(), 
	 (end_time-start_time)/repeat);

  // print frequently occurring words
  for(unsigned int i=0; i<output.size(); i++) {
    printWord(stdout, output[i].first);
    printf(" %d\n", output[i].second);
  }

  delete f;
  return 0;
}