// Encoding.cpp
// Author: Brandon Corfman, 7/2/02

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

using namespace std;

typedef map<string, string> Mappings;
typedef multimap<string, string> Dict;
typedef list<string> StrList;
typedef StrList::iterator StrListIter;

Mappings gMappings;
Dict gDict;

// insert each pair of letter/number mappings into a map structure
void BuildMappings()
{
    ifstream file("mapping.txt");
    string letter, number;
    while (!file.eof())
    {
        file >> letter >> number;
        gMappings.insert(make_pair<string, string>(letter, number));
    }
    file.close();
}

// encode a number/word pair in the dictionary by breaking up the
// letters in the word, and retrieving the appropriate digit for each
// letter. Once a full representation of the word is built, it is
// inserted into the multimap for later retrieval.
void BuildDictMap(string word)
{
    string result, curr_word, first, rest;
    curr_word = word;
    // makes current word uppercase
    transform(curr_word.begin(), curr_word.end(), curr_word.begin(), toupper);
    // while there are more characters to go in the current word, build a
    // string that contains the valid numeric mapping of the current word.
    while (curr_word != "")
    {
        first = curr_word.substr(0,1);
        rest = curr_word.substr(1, curr_word.size()-1);
        curr_word = rest;
        if (first != "\"")
        {
            Mappings::iterator i = gMappings.find(first);
            result = result + i->second;
        }
    }
    
    // insert the number/word pair into the dictionary
    gDict.insert(make_pair(result, word));

}

// Pulls in each of the words in the dictionary file and
// stores them in a number/word pair in a multimap.
void BuildDictionary()
{
    ifstream file("sample-dict.txt");
    if (file.fail())
    {
        cout << "Dictionary file error" << endl;
        return;
    }

    char word[50];
    while (!file.eof())
    {
        file.getline(word, 50);
        BuildDictMap(word);
    }
    file.close();

}    

// Determines whether a given phone number can be translated
// into a valid alphanumeric form.
bool IsEncodable(string number, bool numberUsed)
{
    // if no number was given, then it's encodable!
    if (number == "")
        return true;
    
    string attempt, remaining, result;
    Dict::iterator begin, end;
    StrList new_transl;

    // strip out dashes and slashes
    while (number.find("-") != string::npos)
        number.replace(number.find("-"), 1, "");
    while (number.find("/") != string::npos)
        number.replace(number.find("/"), 1, "");

    // attempt to translate each substring slice into an
    // alphanumeric form
    for (string::size_type i=0; i<number.size(); i++)
    {
        attempt = number.substr(0, i+1);
        remaining = number.substr(i+1, number.size()-1);
        
        if (gDict.find(attempt) != gDict.end() && IsEncodable(remaining, false))
            return true;
    }

    if (!numberUsed)
    {
        attempt = number.substr(0, 1);
        remaining = number.substr(1, number.size()-1);

        if (IsEncodable(remaining, true))
            return true;
    }

    return false;
}

// Translates a given phone number into a valid alphanumeric form.
// Returns a list of strings that contain all possible valid
// alphanumeric encodings of the phone number.
StrList GetPhoneText(string number, bool numberUsed)
{
    if (number == "")
        return StrList();

    string copy = number;
    string attempt, remaining, result;
    Dict::iterator begin, end;
    StrList new_transl;

    bool found = false;
    for (string::size_type i=0; i<number.size(); i++)
    {
        attempt = number.substr(0, i+1);
        remaining = number.substr(i+1, number.size()-1);
        
        if (gDict.find(attempt) != gDict.end() && IsEncodable(remaining, false))
        {
            found = true;
            begin = gDict.equal_range(attempt).first;
            end = gDict.equal_range(attempt).second;
        
            for (Dict::iterator j = begin; j != end; ++j)
            {
                StrList transl = GetPhoneText(remaining, false);
                if (transl.empty())
                    new_transl.push_back(j->second);
                else
                {
                    for (StrListIter k = transl.begin(); k != transl.end(); ++k)
                    {
                        string result = j->second + " " + (*k);
                        new_transl.push_back(result);
                    }
                }
            }
        }
    }
    if (!found && !numberUsed)
    {
        attempt = number.substr(0, 1);
        remaining = number.substr(1, number.size()-1);

        StrList transl = GetPhoneText(remaining, true);
        if (transl.empty())
            new_transl.push_back(attempt);
        else
        {
            for (StrListIter k = transl.begin(); k != transl.end(); ++k)
            {
                string result = attempt + " " + (*k);
                new_transl.push_back(result);
            }
        }
    }

    return new_transl;

}

// Translates a given phone number into a valid alphanumeric forms,
// printing all possible encodings according to specs.
void PrintPhoneNumberText(string number, bool numberUsed)
{
    if (number == "")
        return;
    
    string copy = number;
    string attempt, remaining, result;
    Dict::iterator begin, end;
    StrList new_transl;

    while (number.find("-") != string::npos)
        number.replace(number.find("-"), 1, "");
    while (number.find("/") != string::npos)
        number.replace(number.find("/"), 1, "");

    bool found = false;
    for (string::size_type i=0; i<number.size(); i++)
    {
        attempt = number.substr(0, i+1);
        remaining = number.substr(i+1, number.size()-1);
        
        if (gDict.find(attempt) != gDict.end() && IsEncodable(remaining, false))
        {
            found = true;
            begin = gDict.equal_range(attempt).first;
            end = gDict.equal_range(attempt).second;
        
            for (Dict::iterator j = begin; j != end; ++j)
            {
                StrList transl = GetPhoneText(remaining, false);
                if (transl.empty())
                {
                    cout << copy << ": ";
                    cout << j->second << "\n";
                }
                else
                {
                    for (StrListIter k = transl.begin(); k != transl.end(); ++k)
                    {
                        cout << copy << ": ";
                        string result = j->second + " " + (*k);
                        cout << result << "\n";
                    }
                }
            }
        }
    }

    if (!found && !numberUsed)
    {
        attempt = number.substr(0, 1);
        remaining = number.substr(1, number.size()-1);

        if (IsEncodable(remaining, true))
        {
            StrList transl = GetPhoneText(remaining, true);
            for (StrListIter k = transl.begin(); k != transl.end(); ++k)
            {
                cout << copy << ": ";
                cout << attempt << " " << (*k) << endl;
            }
        }
    }

    return;

}

// Reads in all phone numbers from file and attempts
// to encode each of them in alphanumeric form.
void TranslatePhoneNumbers()
{
    ifstream file("phonelist.txt");
    if (file.fail())
    {
        cout << "Phonelist file error" << endl;
        return;
    }

    char number[50];
    while (!file.eof())
    {
        file.getline(number, 50);
        PrintPhoneNumberText(number, false);
    }
    file.close();

}

int main()
{
    BuildMappings();
    BuildDictionary();
    TranslatePhoneNumbers();

    return 0;
}