#include <iostream>
#include <string>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <stdexcept>
using namespace std;

unsigned hash(const string&);

class Dictionary
{
    string** ptrWords;
public:
    Dictionary(const string& wordfile);
    ~Dictionary();
    string findScrambledWord(const string& word);
    static const unsigned NumberOfBuckets;
};

const unsigned Dictionary::NumberOfBuckets = 100000;

Dictionary::Dictionary(const string& wordfile)
    : ptrWords(new string*[NumberOfBuckets])
{
    ifstream fin(wordfile.c_str());
    if (!fin)
    {
        throw (invalid_argument(string("Can't find file ")+wordfile));
    }
    string word;
    unsigned numberOfBucketsUsed = 0;
    unsigned numberOfWordsNotStored = 0;
    unsigned numberOfWords = 0;

    for (auto i = 0u; i < NumberOfBuckets; i++)
    {
        ptrWords[i] = nullptr;
    }

    // create hash table
    while (fin >> word)
    {
        ++numberOfWords;
        auto index = ::hash(word);
        if (ptrWords[index])
        {
            // bucket already taken
            ++numberOfWordsNotStored;
        }
        else
        {
            ptrWords[index] = new string(word);
            numberOfBucketsUsed++;
        }
    }
    cout << "number of buckets used = " << numberOfBucketsUsed << endl;
    cout << "number of words not stored = " << numberOfWordsNotStored << endl;
    cout << "number of words = " << numberOfWords << endl;
}

Dictionary::~Dictionary()
{
    for (auto i = 0u; i < NumberOfBuckets; i++)
    {
        if (ptrWords[i])
        {
            delete ptrWords[i];
        }
    }
    delete [] ptrWords;
    ptrWords = nullptr;
}

string Dictionary::findScrambledWord(const string& word)
{
    auto index = ::hash(word);
    if (ptrWords[index])
        return *(ptrWords[index]);
    else
        return string("");
}

int main()
{
    string scrambledWord;
    try
    {
        Dictionary Words("c:/temp/words");

        while (1)
        {
            cout << "Enter a scrambled word (\"quit\" to exit) => ";
            cin >> scrambledWord;
            if (scrambledWord == "quit")
                return 0;
            else
                cout << "unscramble = " << Words.findScrambledWord(scrambledWord) << endl;
        }
    }
    catch (const invalid_argument& error)
    {
        cout << error.what() << endl;
        exit(-1);
    }
}

unsigned hash(const string& str)
{
    static unsigned primes[26] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
    unsigned product = 1;
    for (auto i = 0u; i < str.size(); i++)
    {
        product *= primes[tolower(str[i])-'a'];
    }
    return product % Dictionary::NumberOfBuckets;
}