#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include <list>
#include <vector>
#include <algorithm>
#include <utility>
#include <cassert>
#include <map>
#include <set>
#include <ctime>
#include <sys/time.h>
#include <sys/resource.h>

#include "hash_function.h"
#include "hash_table.h"

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

//
// NOTE: You may edit the provided file as much or as little as needed.
//

// ===============================================================================
// ===============================================================================
// Helper class to keep track of the count of the edits necessary to
// transform one word into another word

class Edits {
public:
  Edits() : swaps(0),replaces(0),inserts(0),deletes(0) {}
  int get_total() const { return swaps+replaces+inserts+deletes; }
  int swaps;
  int replaces;
  int inserts;
  int deletes;
};

// Recursive function to compute the minimum edit distance necessary
// to transform one word into another.  NOTE: There are more efficient
// algorithms to compute the minimum edit distance.
void ComputeEditDistance(const std::string &a, const std::string &b, Edits &e) {
  // simple base cases
  if (a == "" && b == "") return;
  if (a == "") { e.inserts += b.size(); return; }
  if (b == "") { e.deletes += a.size(); return; }
  if (a[0] == b[0]) { ComputeEditDistance(a.substr(1,1000),b.substr(1,1000),e); return; }

  // if a pairwise swap works, do that
  if (a.size() >= 2 && b.size() >= 2 && a[0] == b[1] && a[1] == b[1]) {
    e.swaps += 1;
    ComputeEditDistance(a.substr(2,1000),b.substr(2,1000),e);
    return;
  }

  // Limit the naive brute-force search.  Searching for the minimum
  // edit distance by this recursive algorithm gets too expensive.
  // For this program we only care about edit distance <= 2.
  if (e.swaps + e.replaces + e.inserts + e.deletes + 1 > 5) { e.swaps += 1; return; }

  // Recurse with each possible edit
  Edits s = e; s.swaps += 1;
  ComputeEditDistance(a.substr(1,1000),b.substr(1,1000),s);
  Edits i = e; i.inserts += 1;
  ComputeEditDistance(a,b.substr(1,1000),i);
  Edits d = e; d.deletes += 1;
  ComputeEditDistance(a.substr(1,1000),b,d);

  // Return the minimum edit distance
  if (s.get_total() < i.get_total() && s.get_total() < d.get_total()) { e = s; }
  else if (i.get_total() < d.get_total()) { e = i; }
  else { e = d; }
}

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

// Helper routine that splits the input text on on whitespace and punctuation.
// (... except single quotes are ignored & discarded but do NOT split word.)
// Capital letters are converted to lowercase.

bool ReadWord(std::ifstream &istr, std::string &answer) {
  char c;
  answer = "";
  while (istr >> std::noskipws >> c) {
    if (c >= 'a' && c <= 'z') answer.push_back(c);
    else if (c >= 'A' && c <= 'Z') answer.push_back(std::tolower(c));
    else if (c == '\'') continue;
    else {
      if (answer != "") return true;      
    }
  }
  return (answer != "");
}

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

void printTableStatistics(const HashTable &hashtable) {

  unsigned int num_entries = hashtable.getNumEntries();
  unsigned int table_size = hashtable.getTableSize();
  
  if (!hashtable.is_open_addressing()) {
      
    int empties = hashtable.getNumEmptyBuckets();
    int singles = hashtable.getNumSingleBuckets();
    int max_bucket = hashtable.getMaxBucket();
    
    std::cerr << "Hash Table Statistics:" << std::endl;
    std::cerr << "Using Separate Chaining" << std::endl;
    std::cerr << "# entries                           = "
              << std::setw(10) << num_entries << std::endl;
    std::cerr << "# buckets                           = "
              << std::setw(10) << table_size << std::endl;
    std::cerr << "# empty buckets                     = "
              << std::setw(10) << empties
              << " (" << std::setw(5) << std::fixed << std::setprecision(2)
              << 100*empties / double(table_size) << "%)" << std::endl;
    std::cerr << "# single entry buckets              = "
              << std::setw(10) << singles
              << " (" << std::setw(5) << std::fixed << std::setprecision(2)
              << 100*singles / double(table_size) << "%)" << std::endl;
    std::cerr << "average bucket count                = "
              << std::setw(10) << std::fixed << std::setprecision(3)
              << num_entries / double(table_size) << std::endl;
    std::cerr << "maximum bucket count                = "
              << std::setw(10) << max_bucket << std::endl;
    std::cerr << "maximum bucket contains:"<< std::endl;

    hashtable.printMaxBucket();
    // NOTE: this print statement should print to std::cerr the 10
    // most frequent items from the largest bucket.

  } else {
    
    std::cerr << "Hash Table Statistics:" << std::endl;
    std::cerr << "Using Open Addressing" << std::endl;
    std::cerr << "# entries                           = "
              << std::setw(10) << num_entries << std::endl;
    std::cerr << "# locations                         = "
              << std::setw(10) << table_size << std::endl;
    std::cerr << "# empty locations                   = "
              << std::setw(10) << (table_size-num_entries)
              << " (" << std::setw(5) << std::fixed << std::setprecision(2)
              << 100*(table_size-num_entries) / double(table_size) << "%)" << std::endl;

    int num_nonempty_sequences; 
    int longest_nonempty_sequence;
    float average_nonempty_sequence_length;
    hashtable.AnalyzeNonEmptySequences(num_nonempty_sequences,longest_nonempty_sequence,
                                       average_nonempty_sequence_length);

    std::cerr << "# non-empty sequences               = "
              << std::setw(10) << num_nonempty_sequences << std::endl;
    std::cerr << "longest non-empty sequence          = "
              << std::setw(10) << longest_nonempty_sequence << std::endl;
    std::cerr << "average non-empty sequence length   = "
              << std::setw(10) << std::fixed << std::setprecision(3)
              << average_nonempty_sequence_length << std::endl;
  }
  std::cerr << std::endl;
}

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

void SuggestReplacements(const HashTable &hashtable, const std::string &misspelled) {

  // complete the implementation of this function

}

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

void ReadOptionalArguments(int argc, char* argv[],
                           int &hash_prefix,
                           int &hash_suffix,
                           int &table_size,
                           bool &use_open_addressing,
                           bool &use_quadratic_probing,
                           bool &skip_letters_while_hashing,
                           std::string &input_file,
                           bool &suggest_replacements) {

  for (int i = 2; i < argc; i++) {
    
    // -----------------------------------------
    // ARGUMENTS RELATED TO THE HASH FUNCTION
    if (argv[i] == std::string("--hash_prefix")) {
      i++;
      assert (i < argc);
      hash_prefix = std::stoi(argv[i]);
      assert (hash_prefix >= 1);
    }
    else if (argv[i] == std::string("--hash_suffix")) {
      i++;
      assert (i < argc);
      hash_suffix = std::stoi(argv[i]);
      assert (hash_suffix >= 1);
    }

    // -----------------------------------------
    // ARGUMENTS RELATED TO THE HASH TABLE
    else if (argv[i] == std::string("--table_size")) {
      i++;
      assert (i < argc);
      table_size = std::stoi(argv[i]);
      assert (table_size >= 1000);
    }
    else if (argv[i] == std::string("--open_addressing")) {
      use_open_addressing = true;
    }
    else if (argv[i] == std::string("--quadratic_probing")) {
      assert (use_open_addressing == true);
      use_quadratic_probing = true;
    }
    else if (argv[i] == std::string("--skip_letters_while_hashing")) {
      skip_letters_while_hashing = true;
    }

    // -----------------------------------------
    // ARGUMENTS RELATED TO THE APPLICATION/OUTPUT
    else if (argv[i] == std::string("--check_spelling")) {
      i++;
      assert (i < argc);
      input_file = argv[i];
    }
    else if (argv[i] == std::string("--suggest_replacements")) {
      assert (input_file != "");
      suggest_replacements = true;
    }

    else {
      std::cerr << "UNKNOWN COMMAND LINE ARGUMENT: " << argv[i] << std::endl;
      exit(1);
    }
  }
}

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

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

  assert (argc >= 2);
  std::string dictionary_file = argv[1];

  // default values for arguments
  int hash_prefix = 0;
  int hash_suffix = 0;
  int table_size = 100000;
  bool use_open_addressing = false;
  bool use_quadratic_probing = false;
  bool skip_letters_while_hashing = 0;
  std::string input_file = "";
  bool suggest_replacements;
  
  ReadOptionalArguments(argc,argv,
                        hash_prefix,hash_suffix,table_size,
                        use_open_addressing,use_quadratic_probing,skip_letters_while_hashing,
                        input_file,suggest_replacements);

  // ----------------------------
  // create the hash function and hash table
  
  // if no prefix or suffix is provided, just hash the entire string
  if (hash_prefix == 0 && hash_suffix == 0) { hash_prefix = 1000; }

  WordHashFunction hashfunction(hash_prefix, hash_suffix);
  HashTable hashtable(table_size, hashfunction, use_open_addressing, use_quadratic_probing);

  // ----------------------------
  // load & store dictionary

  // mark the time before we create & fill the hash table
  clock_t before_create = clock();
  
  std::ifstream istr(dictionary_file);
  assert (istr);
  std::string word;
  double frequency;
  while(istr >> word >> frequency) {
    hashtable.insert(word, frequency, skip_letters_while_hashing);
  }
  
  // mark the time after we finished filling the hash table
  clock_t after_create = clock();

  printTableStatistics(hashtable);

  // ----------------------------
  // check spelling of input text

  clock_t before_spellcheck = 0;
  clock_t after_spellcheck = 0;
  clock_t after_replacement = 0;
  
  std::map<std::string,int> mispelled;
  if (input_file != "") {

    // mark the time after we finished filling the hash table
    before_spellcheck = clock();
    
    std::ifstream istr2(input_file);
    assert (istr2);
    std::string word;
    int mispelled_count = 0;
    while (ReadWord(istr2,word)) {
      if (!hashtable.find(word)) {
        mispelled[word]++;
        mispelled_count++;
      }
    }
    std::cerr << "Total mispelled words               = " << mispelled_count << std::endl;
    std::cerr << "Unique mispelled words              = " << mispelled.size() << std::endl;
    std::cerr << std::endl;

    // mark the time after we finished spell-checking the document
    after_spellcheck = clock();
  
    // ----------------------------
    // print mispelled words & suggested replacements
    
    for (std::map<std::string,int>::iterator itr = mispelled.begin();
         itr != mispelled.end(); itr++) {
      std::cout << "MISPELLED: " << itr->first << " " << itr->second << " time(s)" << std::endl;
      if (suggest_replacements) {
        SuggestReplacements(hashtable,itr->first);
      }
    }
    std::cerr << std::endl;

    // mark the time after we finished suggesting replacement words
    after_replacement = clock();
  }
  
  // print runtime statistics
  double create_time = double(after_create-before_create)/CLOCKS_PER_SEC;
  double spellcheck_time = double(after_spellcheck-before_spellcheck)/CLOCKS_PER_SEC;
  double replacement_time = double(after_replacement-after_spellcheck)/CLOCKS_PER_SEC;
  std::cerr << "hash table creation time            = "
            << std::setw(10) << std::fixed << std::setprecision(3) << create_time << " seconds" << std::endl;
  if (input_file != "") {
    std::cerr << "spellcheck time                     = "
              << std::setw(10) << std::fixed << std::setprecision(3) << spellcheck_time << " seconds" << std::endl;
  }
  if (suggest_replacements) {
    std::cerr << "suggest replacements time           = "
              << std::setw(10) << std::fixed << std::setprecision(3) << replacement_time << " seconds" << std::endl;
  }

  // print memory usage statistics
  struct rusage ruse = {};
  int result = getrusage(RUSAGE_SELF, &ruse);
  assert(result == 0);

#if __APPLE__
  float memory_MB = ruse.ru_maxrss / 1000000.0;
#else
  float memory_MB = ruse.ru_maxrss / 1000.0;
#endif

  std::cerr << "maximum resident set size (RSS)     = "
  << std::setw(10) << std::fixed << std::setprecision(3) << memory_MB << " MB\n";
}

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