dictionary.cpp

1、对于凯撒密文

// Dictionary.cpp: implementation of the Dictionary classes
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Dictionary.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

#define NODE_HAS_NEXT   0x01
#define NODE_HAS_ALTERN 0x02

#define REMOVEDWORD_TERMINATOR  char(-1)

//////////////////////////////////////////////////////////////////////////////
//                                                                          //
//  CNode                                                                   //
//                                                                          //
//////////////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////////////
//                                                                          //
//  Function : CNode                                                        //
//  Purpose  : Constructor                                                  //
//  Params   : c -  Character this node is to represent                     //
//  Returns  : N/A                                                          //
//  Throws   : None                                                         //
//                                                                          //
//////////////////////////////////////////////////////////////////////////////

CNode::CNode(char c)
{
    m_Character = c;
    m_pAlternative = NULL;
    m_pNext = NULL;
}

//////////////////////////////////////////////////////////////////////////////
//                                                                          //
//  Function : ~CNode                                                       //
//  Purpose  : Destructor                                                   //
//  Params   : None                                                         //
//  Returns  : N/A                                                          //
//  Throws   : None                                                         //
//                                                                          //
//////////////////////////////////////////////////////////////////////////////

CNode::~CNode()
{
    delete m_pAlternative;
    delete m_pNext;
}

//////////////////////////////////////////////////////////////////////////////
//                                                                          //
//  Function : InsertWord                                                   //
//  Purpose  : Insert the given word into the tree                          //
//  Params   : szWord - Word to insert into the tree                        //
//  Returns  : None                                                         //
//  Throws   : None                                                         //
//                                                                          //
//////////////////////////////////////////////////////////////////////////////

void CNode::InsertWord(LPCSTR szWord)
{
    if (m_Character == szWord[0])
    {
        // This is the right node for this character!
        if (szWord[0])
        {
            // Only carry on if we have not reached the end of the word!
            if (m_pNext == NULL)
            {
                // Create a new "Next" node
                m_pNext = new CNode(szWord[1]);
            }
            m_pNext->InsertWord(&szWord[1]);
        }
    }
    else
    {
        // This is not the right node, so we need to see if we have an alternative
        if (m_pAlternative == NULL)
        {
            // Create a new alternative node
            m_pAlternative = new CNode(szWord[0]);
        }
        m_pAlternative->InsertWord(szWord);
    }
}

//////////////////////////////////////////////////////////////////////////////
//                                                                          //
//  Function : IsWordListed                                                 //
//  Purpose  : Determine if a word appears in the tree                      //
//  Params   : szWord - Word to check                                       //
//             bMatchCase - true if case must be matched, else false        //
//             match - Enumeration showing if word was found                //
//             pFinalNode - Pointer to the final node encountered           //
//  Returns  : None                                                         //
//  Throws   : None                                                         //
//                                                                          //
//////////////////////////////////////////////////////////////////////////////

void CNode::IsWordListed(LPCSTR szWord, bool bMatchCase, WordMatch & match, bool bIsFirstNode, CNode ** pFinalNode)
{
    // If we are collecting nodes encountered, add ourselves to the array
    if (pFinalNode) *pFinalNode = this;

    // Start out by assuming that we have a perfect match (we may be proved wrong later!)
    if (bIsFirstNode) match = eMatchPerfect;

    if (m_Character == szWord[0])
    {
        // Unless we have reached the end, continue matching the rest of the word
        if (m_Character != '\0')
        {
            if (m_pNext)
            {
                m_pNext->IsWordListed(&szWord[1], bMatchCase, match, false, pFinalNode);

                if ((match != eMatchPerfect) && (m_Character >= 'A') && (m_Character <= 'Z') && m_pAlternative && !bMatchCase)
                {
                    // Could be a case thing - see if we have an alternative
                    WordMatch matchTemp;
                    m_pAlternative->IsWordListed(szWord, bMatchCase, matchTemp, bIsFirstNode, pFinalNode);
                    match = CDictionary::GetBestMatch(match, matchTemp);
                }
            }
            else
            {
                // Something not right here - if the character is not '\0', we should always have a next pointer
                ASSERT(0);
                match = eMatchInternalError;
            }
        }
    }
    else if ((tolower(m_Character) == tolower(szWord[0]) && !bMatchCase))
    {
        // We have found a match, but with the wrong case. Now, we could have the instance where
        // there are two words in the dictionary, with different capitalisation (for example "Bob" and "bob")
        // First off, if we still have a perfect match, see if we can get a perfect match from an alternative
        if (match == eMatchPerfect)
        {
            if (m_pAlternative)
            {
                // Check to see what we can find
                m_pAlternative->IsWordListed(szWord, bMatchCase, match, bIsFirstNode, pFinalNode);
            }
            else
            {
                // No alternative, hence no match
                match = eMatchNone;
            }
        }

        switch (match)
        {
        case eMatchNone:
        case eMatchMixedCase:
        case eMatchCapitalisedFirst:
            // Carry on with this node, but with an imperfect match
            if (m_pNext)
            {
                // Set the match according to whether or not we are the first node
                match = (bIsFirstNode && m_Character == tolower(szWord[0])) ? eMatchCapitalisedFirst : eMatchMixedCase;

                // And carry on trying to find a match
                m_pNext->IsWordListed(&szWord[1], bMatchCase, match, false, pFinalNode);
            }
            else
            {
                // No next node, which is not right
                ASSERT(0);
                match = eMatchInternalError;
            }
            break;
        default:
            // Either we found a perfect match, or the next best thing - a word with only a capitalised first letter
            // Or of course we could have hit an internal error. However, basically, we finish here, as we have the
            // best result we are going to get.
            break;
        }
    }
    else if (m_pAlternative)
    {
        // This character doesn't match - see if any of the alternatives do
        m_pAlternative->IsWordListed(szWord, bMatchCase, match, bIsFirstNode, pFinalNode);
    }
    else
    {
        // We have no match for this character - hence, we have no match
        match = eMatchNone;
    }
}

//////////////////////////////////////////////////////////////////////////////
//                                                                          //
//  Function : GetPatternMatchingWords                                      //
//  Purpose  : Get words in the dictionary that match the given pattern     //
//  Params   : szWord - Pattern to match (? represents a single char)       //
//             straSuggestions - Reference to array for results             //
//             strWordSoFar - Word built so far by parent items             //
//  Returns  : None                                                         //
//  Throws   : None                                                         //
//                                                                          //
//////////////////////////////////////////////////////////////////////////////

void CNode::GetPatternMatchingWords(LPCSTR szWord, CStringArray & straSuggestions, CString strWordSoFar)
{
    if ((m_Character == szWord[0]) || (tolower(m_Character) == tolower(szWord[0])) || (szWord[0] == '?'))
    {
        // We have a match for this character
        if (m_Character == '\0' && szWord[0] == m_Character)
        {
            // We have reached the end of the word, add it to the suggestions
            straSuggestions.Add(strWordSoFar);
        }
        else 
        {
            if (m_pNext)
            {
                // We have not reached the end, and we have more node, so continue checking
                m_pNext->GetPatternMatchingWords(&szWord[1], straSuggestions, strWordSoFar + m_Character);
            }
            if (m_pAlternative)
            {
                // We have not reached the end, and we have more node, so continue checking
                m_pAlternative->GetPatternMatchingWords(szWord, straSuggestions, strWordSoFar);
            }
        }
    }
    else
    {
        // Does not match - see if one of the alternatives match
        if (m_pAlternative)
            m_pAlternative->GetPatternMatchingWords(szWord, straSuggestions, strWordSoFar);
    }
}

//////////////////////////////////////////////////////////////////////////////
//                                                                          //
//  Function : Serialise                                                    //