USER INTERFACE ESSENTIALS - User Interface Programming for Games - page 173

The next important function is the one that will build a string by traversing down a branch
of the trie, get_from_prefix .
bool trie::get_from_prefix(std::shared_ptr<node> from, std::wstring& s)
{
if ( from == nullptr )
return false;
std::shared_ptr<node> current = from;
wchar_t c = current->GetCharacter();
if ( c != 0 )
{
s.push_back( c );
}
if ( current->IsWord() )
{
return true;
}
std::shared_ptr<node> n = current->next();
while ( n != nullptr )
{
if ( get_from_prefix(n, s) )
{
return true;
}
n = n->next();
}
return false;
}
This is a recursive implementation that begins by getting the character from the current
node and pushing it back into the output string s , if the current node defines a word, we
can return true, this means we have reached the end of the branch and we have a complete
word in the output string reference s; otherwise, for each child of the current node, we will
recursively call get_from_prefix , if ever this returns true then we have found a complete
word and we can return. If we run out of children, then there are no words with this prefix
and the function will return false.
The last function left to discuss is the next function in the node class, this function will
advance an index and return the child node at that position, and it's the important function
that will allow us to implement cycling through auto complete possibilities.
std::shared_ptr<node> node::next()
{
if ( m_children.size() == 0 )
{
return nullptr;