Game Development Reference
In-Depth Information
we then create a new node and initialize it to the character and we push this new node into
the current node's children vector, finally if we are at the final character of the word, we
will flag the node to reflect this fact.
The find function in nodes is a straightforward iteration and compare, if we find a match,
we return a pointer to the node, and otherwise we return null, to indicate no match was
found.
std::shared_ptr<node> node::find(wchar_t character)
{
for ( auto& n : m_children )
{
if ( n->GetCharacter() == character )
{
return n;
}
}
return nullptr;
}
Now we can build up a trie out of a set of words, for example, we could parse an entire
dictionary file and send the words into the trie, once constructed we will want to retrieve
information from it.
While there are a few useful functions to implement in a trie, such as functions to verify
if the trie contains a given word, or a given prefix. For text entry we are interested in re-
trieving the information required to build an auto completion system that is smart enough
so that, as we type, the system automatically inserts the closest match it finds.
Figure
56
- Auto completion is done as the user is writing.
The first function that will help us achieve this we will call it
find_prefix
it will receive
some text as input, in the example above it would receive the word “play” and it will
return the node at which the letter y is found. Then we will call a second function called
get_from_prefix
, this function will receive a node and a reference to a string, it will then
iterate down the children of the node we provided and build a string for the remainder of
theword.Thereasonwereturnthenodeinwhichtheletteryisfoundisthat,thisnodewill
