#include "stdafx.h"
#include <iostream>
#include <string>
#include <list>
#include <fstream>
#include <crtdbg.h>
#include <windows.h>
#include <mmsystem.h>

using namespace std;

#define STR_ADD_DIC "add-dictionary"
#define STR_CONNECT "connect"
#define MAX_NODE    2048
#define SAFE_DELETE(x) if(x) { delete x; x = NULL; }
#define SIMILARITY_DEVIANCE 2
#define MEASURE_TIME

#pragma warning (disable : 4786)

struct DictionaryWord
{
            string strWord;
            bool   bInChain;
};

struct WordTree
{
            WordTree() : nSubTreeCount(0), iterWord(NULL)
            {
            }

            int AddSubTree(string& strTreeWord, list<DictionaryWord>::iterator iter)
            {

                        arrSubTree[nSubTreeCount] = new WordTree();
                        arrSubTree[nSubTreeCount]->strWord = strTreeWord;
                        arrSubTree[nSubTreeCount]->iterWord = iter;
                        nSubTreeCount++;
                        return (nSubTreeCount - 1);
            };

            void DestroyTree()
            {
                        // We loop through all trees we created with "new" and delete them

                        for (int i=0;i<nSubTreeCount;i++)
                        {
                                   arrSubTree[i]->DestroyTree();
                                   SAFE_DELETE(arrSubTree[i]);
                        }

                        if (iterWord != NULL)
                            (*iterWord).bInChain = false;
            };

            string strWord;
            list<DictionaryWord>::iterator iterWord;
            int nSubTreeCount;
            WordTree* arrSubTree[MAX_NODE];
};

class Dictionary
{
public:
            bool LoadDictionary(const string& strFilepath)
            {
                        // Load the dictionary into memory.
                        // Words are stored in a list

                        string str;                   

                        ifstream file;
                        file.open(strFilepath.c_str());

                        if (!file.is_open())
                                   return false;

                        while (file.good())
                        {
                                   char szLine[120] = {'\0'};
                                   file.getline(szLine, 120);                                  

                                   if (strlen(szLine) > 0)
                                   {
                                               DictionaryWord wrd;
                                               wrd.strWord = szLine;
                                               wrd.bInChain = false;
                                               m_wordList.push_back(wrd);
                                   }
                        }

                        file.close();
                       return true;
            }

            bool GetSimilarWords(WordTree& tree, bool bVerifyWord)
            {

                       // bVerifyWord, if set to true, makes us check if
                        // the word exists at all in the dictionary. You need
                        // set it to true only once, as all other words definately
                        // exist in the dictionary.
                        bool bWordFound = false;
                        bool bChildFound = false;
                        int nIndex = 0;

                        list<DictionaryWord>::iterator iter;
                        for (iter=m_wordList.begin(); iter != m_wordList.end(); ++iter)
                        {         
                                   if ((*iter).bInChain)
                                               continue;

                                   if (bVerifyWord && !bWordFound && tree.strWord == (*iter).strWord) // lazy eval
                                   {
                                               tree.iterWord = iter;
                                               bWordFound = true;
                                   }
                                   else
                                   {           
                                    int n = AreSimilar(tree.strWord, (*iter).strWord);

                                               if (n == 1)
                                               {
                                                           bChildFound = true;
                                                           tree.AddSubTree((*iter).strWord, iter);
                                               }
                                   }

                                   nIndex++;
                        }

                       
                        if (bChildFound == false || bVerifyWord && bWordFound == false)
                                   return false;

                        return true;
            };

protected:

            int AreSimilar(string& str1, string& str2)
            {

                        // if the same, return 0, if similar, return 1, else
                        // return -1

                       
                        int nFail  = 0;
                        int nSize1 = str1.size();
                        int nSize2 = str2.size();
                        if (nSize1 != nSize2)
                                   return -1;

                        for (int i=0;i<nSize1;i++)
                        {

                                   if (str1.at(i) != str2.at(i))
                                   {
                                               nFail++;
                                   }

                                   if (nFail == SIMILARITY_DEVIANCE) // failed twice.
                                               return -1;
                        }

                        return nFail; //1 -> similar, 0 -> equal
            }

private:
            list<DictionaryWord> m_wordList;
};

class CommandParser
{

public:
            typedef enum {cmdUnkown = 0, cmdAddDictionary, cmdConnect, cmdExit } Command;

           
            Command ParseCommand(string strInput)
            {
                        if (strInput.compare(0, sizeof(STR_ADD_DIC) - 1, STR_ADD_DIC) == 0)
                        {
                                   return cmdAddDictionary;
                        }
                        else if (strInput.compare(0, sizeof(STR_CONNECT) - 1, STR_CONNECT) == 0)
                        {
                                   return cmdConnect;
                        }
                        else if (strInput == "exit")
                        {
                                   return cmdExit;
                        }
                       
                        return cmdUnkown;
            }

            bool ParseAddDictionary(string strInput, string& strFilepath)
            {
                        // We have a command, which idealy would look like
                        // "add-dictionary c:\dic.txt".
                       
                        if (strInput.size() <= sizeof(STR_ADD_DIC))
                                   return false;

                        strFilepath = strInput.substr(sizeof(STR_ADD_DIC));

                        // We don't perform a check for multiple characters
                        // in this case, because spaces are allowed in paths.
                       
                        return true;
            }

           
            bool ParseConnect(string strInput, string& strStartWord, string& strEndWord)
            {
                        // We have a command, which idealy would look like
                        // "connect coat hook". However, it might be typed wrongly
                        // so we also check that
                        if (strInput.size() <= sizeof(STR_CONNECT))
                        {
                                   // The user typed "connect". This would cause
                                   // an access violation if we do the next call,
                                   // so we return here.
                                   return false;
                        }
                       
                        // remove "connect"
                        strInput = strInput.substr(sizeof(STR_CONNECT));
                       
                       
                        // Find the space char separating the first word
                        // from the second
                        string::size_type nPos;
                        nPos = strInput.find(' ');
                        if (nPos == string::npos)
                        {
                                   // If there is no space, we only have one word,
                                   // so we indicate an error
                                   return false;
                        }
                       
                        // We retrieve the two words
                        strStartWord = strInput.substr(0, nPos);
                        strEndWord  = strInput.substr(nPos + 1);
                       
                        // We check if there are more than two parameters
                        // if so, we indicate an error.
                        if (strEndWord.find(' ') != string::npos)
                        {
                                   return false;
                        }
                        return true;
            }
};
class WordChain : public Dictionary
{
public:
            static bool ConnectWords(string strStartWord, string strEndWord, string& strChain, Dictionary& dic)
            {
                        bool bChained = false;
                        strChain = strStartWord + " > ";
                        WordTree tree;
                        tree.strWord = strStartWord;
                       
                        WordTree* pLink = GetNextLinksInChain(dic, tree, strEndWord, bChained, true);
                        while (pLink && !bChained)
                        {
                                   strChain += pLink->strWord + " > ";
                                   pLink = GetNextLinksInChain(dic, *pLink, strEndWord, bChained, false);
                        }
                       
                        if (bChained && pLink)
                        {
                                   strChain += pLink->strWord + "\n";
                        }
                       
                        tree.DestroyTree();
                        return bChained;
            }
            static WordTree * GetNextLinksInChain(Dictionary& dic, WordTree& tree, string& strEndWord, bool& bComplete, bool bVerifyWord)
            {
                        WordTree * pResult = NULL;
                        if (dic.GetSimilarWords(tree, bVerifyWord))
                        {
                                   (*tree.iterWord).bInChain = true;
                                  
                                   for (int i=0;i<tree.nSubTreeCount;i++)
                                   {
                                               if (tree.arrSubTree[i]->strWord == strEndWord)
                                               {
                                                           bComplete = true;
                                                           return tree.arrSubTree[i];
                                               }
                                               if (dic.GetSimilarWords(*tree.arrSubTree[i], false))
                                               {
                                                           // tree.strWord is definately in our chain
                                                           // We hide it so that future lookups do not use
                                                           // it
                                                           (*tree.iterWord).bInChain = true;
                                                           pResult = tree.arrSubTree[i];
                                               }
                                   }
                        }
                       
                        return pResult;
            }
};
int main(int argc, char* argv[])
{
            char szInput[200] = {'\0'};
            WordChain dic;
            CommandParser cmd;
            while (true)
            {
                        //////
                        // Display prompt and get command
                        cout << "?";
                        cin.get(szInput, 200, '\n');
                        cin.get();
                       
                        ////
                        // Parse command
                        CommandParser::Command cmdType = cmd.ParseCommand(szInput);
                        switch (cmdType)
                        {
                        case CommandParser::cmdUnkown:
                                   {         
                                               cout << "\"" << szInput << "\": This command does not exist. Use \"exit\" to exit.\n";
                                   }
                                   break;
                                   /////////////////////////////////////
                        case CommandParser::cmdAddDictionary:
                                   {
                                               string strFilepath;
                                               if (cmd.ParseAddDictionary(szInput, strFilepath) == true)
                                               {
                                                           if (dic.LoadDictionary(strFilepath))

                                                           {
                                                                       cout << "Added " << strFilepath << "\n";
                                                           }
                                                           else
                                                                       cout << "Error adding " << strFilepath << "\n";
                                               }
                                               else
                                                           cout << "Invalid parameters. Use \"add-dictionary filename\"\n";                                 
                                   }
                                   break;
                                   /////////////////////////////////////    
                        case CommandParser::cmdConnect:
                                   {
                                               string strStartWord, strEndWord, strChain;
                                               if (cmd.ParseConnect(szInput, strStartWord, strEndWord) == true)
                                               {
#if defined(MEASURE_TIME)
                                                           DWORD dwStart = timeGetTime();
#endif
                                                           if (dic.ConnectWords(strStartWord, strEndWord, strChain, dic) == false)
                                                           {
                                                                       cout << "No way to connect " << strStartWord << " to " << strEndWord << "\n";
                                                           }
                                                           else
                                                           {
                                                                       cout << strChain;
                                                           }
#if defined(MEASURE_TIME)
                                                           DWORD dwEnd = timeGetTime();
                                                           cout << "Completed in " << dwEnd - dwStart << " milliseconds\n";
#endif
                                               }
                                               else
                                                           cout << "Invalid parameters. Use \"connect word1 word2\"\n";
                                    }
                                   break;
                                   //////////////////////////////////
                       
                        case CommandParser::cmdExit:
                                   {
                                               return 0;
                                   }
                                   break;
                                   //////////////////////////////////
                        }
            }
            return 0;
}