Game Development Reference
In-Depth Information
contain all the children that share the same prefix up to the letter y, allowing us to call the
node's next function to iterate over its children, this allows us to implement a method to
cyclethroughautocompletesuggestionsbybindingthecalltonexttoakeypress,typically
using the TAB key.
std::shared_ptr<node> trie::find_prefix(const std::wstring& prefix) const
{
if ( prefix.size() == 0 )
{
return nullptr;
}
std::shared_ptr<node> current = m_root;
std::shared_ptr<node> last = nullptr;
while ( current != nullptr )
{
for (size_t i = 0; i < prefix.size(); ++i )
{
auto tmp = current->find(prefix.c_str()[i]);
if ( tmp == nullptr )
{
return nullptr;
}
current = tmp;
if ( !current->IsWord() )
{
last = current;
}
}
break;
}
if ( !current->IsWord() )
{
return last;
}
return nullptr;
}
The goal of
find_prefix
is to traverse the tree, searching for each of the characters in the
prefix, once we have finished iterating over the prefix, we will return the last node that
was not flagged as a word, this will allow us to cycle over the results with ease. If at any
moment during the iteration we do not find a match from the prefix, we return
nullptr
to
indicate thatnomatchwasfoundorifwehavefoundafullword,wealsoreturnnullptr,no
need to return the prefix if it is the full word.
