#include <string>
#include <iostream>
#include <map>
#include <set>

#include "wordlist.hpp"

using namespace std;

map<char, set<string> > PrepList(std::string list[], size_t size){
    map<char, set<string> > containsList;
    for(int i=0; i<size; ++i){
        for(string::iterator j=list[i].begin(); j!=list[i].end(); ++j){
            containsList[*j].insert(list[i]);
        }
    }
    return containsList;
}

int countLetter(char letter, string word){
    int ret=0;
    for(string::iterator i=word.begin(); i!=word.end(); ++i){
        if(*i==letter) ret++;
    }
    return ret;
}

set<string> GetAnagrams(string word, map<char, set<string> > containsList){
    //add all words containing first letter to "possibles" list
    set<string> possibles=containsList[word[0]];
    //for each letter in the word, remove any possiblities that do not contain this letter
    for(string::iterator i=word.begin(); i!=word.end(); ++i){
        set<string> remove;
        for(set<string>::iterator j=possibles.begin(); j!=possibles.end(); ++j){
            if(j->length()!=word.length() || containsList[*i].count(*j)!=1){
                remove.insert(*j);
            }
        }
        for(set<string>::iterator j=remove.begin(); j!=remove.end(); ++j){
#ifdef DEBUG_OUTPUT
            cout << "Possibility '" << *j << "' removed. ";
            if(j->length()!=word.length()){
                cout << "(wrong length)";
            }else{
                cout << "(does not contain '" << *i << "')";
            }
            cout << endl;
#endif
            possibles.erase(*j);
        }
    }
    //for each letter in the word, check that the possibilities contain the same number of
    //instances of that letter
    for(string::iterator i=word.begin(); i!=word.end(); ++i){
        set<string> remove;
        for(set<string>::iterator j=possibles.begin(); j!=possibles.end(); ++j){
            if(countLetter(*i, word)!=countLetter(*i, *j)){
                remove.insert(*j);
            }
        }
        for(set<string>::iterator j=remove.begin(); j!=remove.end(); ++j){
#ifdef DEBUG_OUTPUT
            cout << "Possibility '" << *j << "' removed. (wrong number of '" << *i << "'s)" << endl;
#endif
            possibles.erase(*j);
        }
    }
    return possibles;
}

int main(){
    map<char, set<string> > containsList=PrepList(wordlist, wordlist_size);
    string word="NOTBLANK";
    while(word != ""){
        cout << "Enter word (blank to quit):";
        getline(cin, word);
        cout << "Possibilities:" << endl;
        set<string> anagrams=GetAnagrams(word, containsList);
        for(set<string>::iterator i=anagrams.begin(); i!=anagrams.end(); ++i){
            cout << *i << endl;
        }
    }
    return 0;
}