/// \file main.cpp
/// \brief This is the main code file.

/// \mainpage Hash Table Speed Demo
///
/// This program demonstrates the speed advantage of a hash table versus a
/// plain table using binary search in a Scrabble cheat program. It
/// prompts the user to enter a string of letters, then outputs a list of
/// words that can be made with those letters using a dictionary of words
/// read from a file. Actually, it does it twice, once using a straight table
/// and binary search for the dictionary, the other using an open hash table,
/// reporting CPU time for each. This code uses functors in order to avoid
/// code duplication.

#include <string>
#include <vector>
#include <unordered_map>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <time.h>

/// Get CPU time in milliseconds.
/// \return User CPU time in milliseconds.

unsigned CPUTime(){
	return unsigned((1000.f*(float)clock())/(float)CLOCKS_PER_SEC);
} //CPUTime

/// \brief Sort a string
void sort(std::string& str){
	std::sort(str.begin(), str.end());
}

std::unordered_map<std::string, std::vector<std::string>> wordList;	//Still a hash map

/// Read the dictionary from `words.txt` into both a plain word table and a
/// hash table implementation of a dictionary.
/// \param wt0 Plain word table.
/// \param wt1 Word hash table.
/// \return true if successful.

bool GetDictionary(){	//Edit with my own implementation
	std::cerr << "Loading dictionary..." << std::endl;
	bool bLoaded = false;

	std::ifstream input;
	input.open("words.txt");

	size_t numberOfWords = 0;
	size_t maxLength = 0;
	size_t minLength = 999999;
	if(input.is_open()){ //success
		std::string s; //current line of text
		while(std::getline(input, s)){ //get and process line of text
			++numberOfWords;
			std::string sorted = s;
			sort(sorted);	//Sorts the characters
			size_t length = s.size();
			if(length > maxLength) maxLength = length;
			if(length < minLength) minLength = length;
			if(wordList.find(sorted) == wordList.end()) wordList[sorted] = std::vector<std::string>();
			wordList[sorted].push_back(s);
		} //while

		input.close();
		bLoaded = true;
	} //if

	//print output statistics

	if(bLoaded){
		std::cerr << numberOfWords << " words loaded. ";
		std::cerr << "Shortest word length " << minLength << ". ";
		std::cerr << "Longest word length " << maxLength << ". " << std::endl;
	} //if
	else std::cerr << "Dictionary file (words.txt) not found" << std::endl;

	return bLoaded;
} //GetDictionary

/// Read a string of letters from the current line of stdin. All upper-case
/// letters are made lower-case. All non-letter characters are ignored.
/// \param s [out] input string.

void GetInput(std::string& s){
	std::string temp; //temporary string for unprocessed input, may contain bad chars
	std::cout << "> "; //prompt
	std::getline(std::cin, temp);
	std::transform(temp.begin(), temp.end(), temp.begin(), ::tolower); //make lower case

	//put only alphabetic characters into s

	s.clear();
	for(char c: temp)
		if('a' <= c && c <= 'z')
			s += c;
} //GetInput

///https://stackoverflow.com/a/36184405/10141528	A lot of other good ways to do this, but this one is the cleanest
/// \brief Makes a power set
/// Makes a list of all of the possible subsets, aka combinations of elements
//template<typename T>
//std::vector<std::vector<T>> makePowerSet(const T* begin, const T* end){	//Really messy, but gets the job done
//	std::vector<std::vector<T>> powerSet;
//	for(const T* it = begin; it != end; ++it){
//		for(std::vector<T> bruh : powerSet){
//			//std::vector<T> bruh = set;
//			bruh.push_back(*it);	//I'm really hoping bruh does not modify the internal data
//			powerSet.push_back(bruh);
//		}
//		powerSet.push_back(std::vector<T>(*it));
//	}
//	return powerSet;
//}
//Same thing but for a string
std::vector<std::string> makePowerSet(const std::string& str){	//Really messy, but gets the job done
	std::vector<std::string> powerSet;
	for(std::string::const_iterator it = str.cbegin(); it != str.cend(); ++it){
		size_t lastSize = powerSet.size();
		for(size_t i = 0; i < lastSize; i++){
			std::string bruh = powerSet[i];
			bruh += (*it);	//I'm really hoping bruh does not modify the internal data
			powerSet.push_back(bruh);
		}
		powerSet.push_back(std::string()+*it);	//Hopefully this explicit cast works and this static variable gets copied to the vector
	}
	return powerSet;
}

void print_map(std::unordered_map<std::string,std::vector<std::string>> const &m)
{
    for (auto const& pair: m) {
        std::cout << "{" << pair.first << ": ";
	for(auto const& elm : pair.second){
		std::cout << elm << " ,";
	}
	std::cout << "}\n";
    }
}

/// Main. Prompt user to enter a string of letters, then output a list of
/// words that can be made with those letters using a dictionary of words
/// read from a file. Actually, we do it twice, once using a straight table
/// and binary search for the dictionary, the other using an open hash table
/// so that we can compare the running time for each.
/// \return 0.

int main(){
	std::cerr << "Scrabble cheater by Ian Parberry" << std::endl;
	std::cerr << "edited by Leif Messinger" << std::endl;
	if(GetDictionary()){
		//print_map(wordList);
		std::cerr << "Enter a string of alphabetic characters.";
		std::cerr << " Hit Return to exit." << std::endl;

		std::string strInput; //input string
		std::string strWord; //current word.
		do{
			//get the input
			strInput.clear();
			GetInput(strInput);

			//process the input

			if(!strInput.empty()){ //do nothing for empty string
				std::cout << "Results using my implementation." << std::endl;
				size_t matches = 0;

				unsigned checkpoint = CPUTime();	//Pre sort time
				sort(strInput);	//If you sort the string before you make the powerSet, then the powerSet will hold sorted strings. Neat.
				unsigned checkpoint2 = CPUTime();	//Post sort time
				std::vector<std::string> powerSet = makePowerSet(strInput);
				unsigned checkpoint3 = CPUTime();	//Map effectiveness
				for(std::vector<std::string>::iterator it = powerSet.begin(); it != powerSet.end(); ++it){
					//std::cout << bruh << std::endl;
					if(wordList.find(*it) != wordList.end()){	//I'll probably learn how to store that so I don't have to check the map twice
					//if(wordList[bruh] != std::vector<std::string>()){
						for(std::string word : wordList[*it]){
							++matches;
							std::cout << word << " ";
							std::cout.flush();
						}
					}
				}
				unsigned endTime = CPUTime();
				std::cout << std::endl << matches << " words found in " << (endTime-checkpoint) << " miliseconds." << std::endl;
				std::cout << (endTime-checkpoint3) << " ms just to look through the map." << std::endl;
			} //if
		}while(!strInput.empty()); //exit on empty string
	} //if

	return 0;
} //main