gistfile1.txt

#include <map>
#include <string>

using std::string;
using std::map;
using std::pair;

class CSpriteTrieNode
{
public:
    CSpriteTrieNode();
    ~CSpriteTrieNode();
    map<char, CSpriteTrieNode*> *m_pNodeMap;  
    bool m_bIsWord;
};

class CSpriteTrie
{
public:
    CSpriteTrie();
    ~CSpriteTrie();
    CSpriteTrieNode m_root;
    std::string m_wordBuilder;
    
    void addWord(const char* string);
    void findWords(char* availableLetters, CSpriteTrieNode* pNode=NULL);
};

IMPLEMENTATION

#include "SpriteTrie2.h"

int g_NodeCount = 0;
int g_NodeCount2 = 0;
int g_NodeMapCount = 0;

// CSpriteTrieNode
CSpriteTrieNode::CSpriteTrieNode()
: m_bIsWord(false), m_pNodeMap(0)
{
    g_NodeCount++;
}

CSpriteTrieNode::~CSpriteTrieNode()
{
    // Free up memory from children
    if (m_pNodeMap) {
        map<char, CSpriteTrieNode*>::iterator iter = m_pNodeMap->begin();
        while (iter != m_pNodeMap->end()) {
            // Delete the child
            delete iter->second;
            iter++;
        }
        m_pNodeMap->clear();
        delete m_pNodeMap;
        m_pNodeMap = 0;
    }
}

// CSpriteTrie
CSpriteTrie::CSpriteTrie()
{
}

CSpriteTrie::~CSpriteTrie()
{

}

void CSpriteTrie::addWord(const char *string)
{
    CSpriteTrieNode* pNode = &m_root;
    for (unsigned int i = 0; i < strlen(string); i++) {
        char current = string[i];
        CSpriteTrieNode* pPreviousNode = pNode;
        // Create a node map for this node if we don't have one because we have children
        if (!pNode->m_pNodeMap) {
            pNode->m_pNodeMap = new map<char, CSpriteTrieNode*>; 
            g_NodeMapCount++;
        }
        map<char, CSpriteTrieNode*>::iterator iter = pNode->m_pNodeMap->find(current);
        if (iter != pNode->m_pNodeMap->end()) {
            pNode = iter->second;
        } else {
            CSpriteTrieNode* pNewNode = new CSpriteTrieNode;
            g_NodeCount2++;
            pPreviousNode->m_pNodeMap->insert(pair<char, CSpriteTrieNode*>(current, pNewNode));
            pNode = pNewNode;
        }
    }
    pNode->m_bIsWord = true;
    
}

void CSpriteTrie::findWords(char* availableLetters, CSpriteTrieNode* pNode)
{
    if (!pNode) {
        pNode = &m_root;
    }
    if (pNode->m_bIsWord) {
        NSLog(@"Found word: %s Letters left: %s", m_wordBuilder.c_str(), availableLetters);
    }
    for (int i = 0; i < strlen(availableLetters); i++) {
        if (pNode->m_pNodeMap) {
            // We have children
            map<char, CSpriteTrieNode*>::iterator iter = pNode->m_pNodeMap->find(availableLetters[i]);
            if (iter != pNode->m_pNodeMap->end()) {
                m_wordBuilder.append(1, iter->first);
                availableLetters[i] = 'X'; // Arbitrary value not found in dictionary and not used
                findWords(availableLetters, iter->second);
                m_wordBuilder.erase(m_wordBuilder.end() - 1);
                availableLetters[i] = iter->first;
            }
        }
    }
}