// NorvigEncoding.cpp
// Author: Brandon Corfman, 7/6/02

// My C++ translation of Peter Norvig's Lisp code solution to Erann Gat's
// programming study. Peter's original code can be found at
// http://www.norvig.com/java-lisp.html and the description of the study
// can be found at http://www.alvin.jpl.nasa.gov/gat/ftp/study.txt

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <map>
#include <hash_map>
#include <list>
#include <algorithm>

using namespace std;

typedef map<string, long> Map;
typedef hash_multimap<long, string> HashMap;
typedef list<string> List;
Map gMap;
HashMap gDict;

template <typename T> std::string toString(T i)
{
    std::stringstream ss;
    ss << i;
    return ss.str();
}

int toInt(std::string s)
{
    return atoi(s.c_str());
}

std::string toLower(std::string s)
{
    std::transform(s.begin(), s.end(), s.begin(), tolower);
    return s;
}

template <typename T> T car(const std::list<T>& lst)
{
    if (lst.size() > 0) {
        T val = *(lst.begin());
        return val;
    }
    else
        return T();
}

template <typename T> std::list<T> cons(std::list<T> lst1, const std::list<T>& lst2)
{
    lst1.insert(lst1.end(),lst2.begin(),lst2.end());
    return lst1;
}

template <typename T> std::list<T> cons(const T& atom, std::list<T> lst)
{
    lst.insert(lst.begin(), atom);
    return lst;
}

template <typename T> std::list<T> cons(std::list<T> lst, const T& atom)
{
    lst.insert(lst.end(), atom);
    return lst;
}

template <typename T> void printlist(const std::list<T>& l)
{
    for (std::list<string>::const_iterator i = l.begin(); i != l.end(); ++i)
        cout << *i << " ";
    cout << endl;
}

long charToDigit(char c)
{
    return gMap.find(toString(c))->second;
}

long wordToNum(string word)
{
    word = toLower(word);
    long n = 1;
    for (string::size_type i=0; i<word.size(); i++)
        if (word[i] != '-' && word[i] != '\"')
            n = n * 10 + charToDigit(word[i]);
    return n;
}

void loadMappings()
{
    ifstream file("mapping.txt");
    long number; string letter;
    while (file >> letter >> number)
        gMap.insert(make_pair<string, long>(letter, number));
}

void loadDictionary()
{
    ifstream file("study-dict.txt");
    string word;
    while (file >> word)
        gDict.insert(make_pair<long, string>(wordToNum(word), word));
}

string makeDigits(string num)
{
    while (num.find("-") != string::npos)
        num.replace(num.find("-"), 1, "");
    while (num.find("/") != string::npos)
        num.replace(num.find("/"), 1, "");
    return num;
}

long nthDigit(string s, string::size_type n)
{
    return toInt(toString(s[n]));
}

bool isDigit(string s)
{
    if (s.size() == 1 && s.find_first_of("1234567890") != string::npos)
        return true;
    return false;
}

void printTranslations(string num, string digits, string::size_type start, List words)
{
    if (start >= digits.length()) {
        cout << num << ": ";
        words.reverse();
        printlist(words);
    }
    else {
        bool found_word = false;
        long n = 1;
        for (string::size_type i=start; i<digits.length(); i++)    {
            n = n * 10 + nthDigit(digits, i);
            HashMap::iterator begin = gDict.equal_range(n).first;
            HashMap::iterator end   = gDict.equal_range(n).second;
            for (HashMap::iterator j = begin; j != end; ++j) {
                found_word = true;
                printTranslations(num, digits, i+1, cons(j->second,words));
            }
        }
        if (!found_word && !isDigit(car(words)))
            printTranslations(num, digits, start+1,
                cons(toString(nthDigit(digits, start)), words));
    }
}

void translatePhoneNumbers()
{
    ifstream file("phonelist.txt");
    string number;
    while (file >> number)
        printTranslations(number, makeDigits(number), 0, List());
}

int main()
{
    loadMappings();
    loadDictionary();
    translatePhoneNumbers();
    return 0;
}