//
// insane-british-anagram.cpp - Find words that have valid anagrams
//                              Words sourced from Debian's british-english-insane dictionary
//
// heater - 2019-07-25
// 
#include <fstream>
#include <string>
#include <stdlib.h>
#include <string.h>
#include <unordered_map> 
#include <vector> 

std::string getFileContents(const char *filename) {
    std::ifstream in(filename, std::ios::in | std::ios::binary);
    if (in) {
        std::string contents;
        in.seekg(0, std::ios::end);
        contents.resize(in.tellg());
        in.seekg(0, std::ios::beg);
        in.read(&contents[0], contents.size());
        in.close();
        return(contents);
    }
    throw(std::runtime_error("Shit happened!"));
}

char* sortString (const char* s) {
    int n = strlen(s);
    char* string = (char*)malloc(n + 1); 
    strcpy (string, s); 
    char temp;
    int i, j;

    for (i = 0; i < n-1; i++) {
        for (j = i+1; j < n; j++) {
            if (string[i] > string[j]) {
            temp = string[i];
            string[i] = string[j];
            string[j] = temp;
            }
        }
    }
    return string;
}

int main (int argc, char* argv[]) {
    // Map container for sets of anagrams 
    // An anagram set is simply a vector of pointers to words in the dictionary
    // Keys for the anagram sets in the map are the ordered characters of the words.
    std::unordered_map<std::string, std::vector<char*> >anagramMap;
    std::unordered_map<std::string, std::vector<char*>>::iterator it;

    // An ordered index of anagram set keys 
    std::vector<std::string> index;

    auto dictionary = getFileContents("/usr/share/dict/british-english-insane");
    char* dictionaryPtr = (char*)dictionary.c_str();
    char* wordPtr = dictionaryPtr;
    char* charPtr = wordPtr;
    bool reject = false;
    while (1) {
        if (islower(*charPtr)) {
            // We are scanning a valid word
            charPtr++;
        } else if ((*charPtr) == '\n') {
            // We have hit the end of a word, use the word if it's valid
            *charPtr = 0;
            if (!reject) {
                // Do we have a word with this key (potential anagram)?
                char* key = sortString(wordPtr);
                it = anagramMap.find(key);
                if (it == anagramMap.end()) {
                    // No: Add it to the map as start of new anagram set.
                    anagramMap[key].push_back(wordPtr);

                    // And add the new anagram set to index
                    index.push_back(key);
                } else {
                    // Yes: Append it to the existing anagram set.
                    it->second.push_back(wordPtr); 
                }
                free(key);
            }
            charPtr++;
            wordPtr = charPtr;
            reject = false;
        } else if ((*charPtr) != 0) {
            // Invalid character
            reject = true;
            charPtr++;
        } else {
            // End of dictionary
            break;
        }
    }

    // Iterate over the collected anagram sets in order of the index.
    for(auto const& key: index) {
        it = anagramMap.find(key);
        if (it->second.size() > 1) {
            int count = 0;
            for(const auto& value: it->second) {
                if (count == 1) {
                    fputs(": ", stdout);                
                } else if (count > 1) {
                    fputs(", ", stdout);                
                }
                fputs(value, stdout);                
                count++;
            }
            fputs("\n", stdout);                
        }
    }
    return (0);
}