Collaboration diagram for Trie:

[legend]

Public Member Functions
	Trie ()

void	insert (string word)

bool	search (string word)

bool	startsWith (string prefix)

Private Attributes
vector< unique_ptr< trie_node > >	tree

vector< bool >	tree_beginnings

Detailed Description

Definition at line 35 of file main.cpp.

Constructor & Destructor Documentation

◆ Trie()

Trie::Trie ( )

inline

Definition at line 42 of file main.cpp.

           : tree(), tree_beginnings(26, false)
    {
        tree.reserve(26);
        for (char c = 'a'; c <= 'z'; ++c)
            tree.push_back(make_unique<trie_node>(c));
    }

References tree.

Member Function Documentation

◆ insert()

void Trie::insert ( string word )

inline

Definition at line 49 of file main.cpp.

    {
        if (word.empty())
            return;
        trie_node* node = tree[word[0] - 'a'].get();
        tree_beginnings[word[0] - 'a'] = true;
        for (int i = 1; i < (int)word.length(); ++i)
        {
            trie_node* child = node->find(word[i]);
            if (child == nullptr)    
                child = node->add_child(word[i]);
            node = child;
        }
        node->set_last();
    }

References trie_node::add_child(), trie_node::find(), trie_node::set_last(), tree, and tree_beginnings.

◆ search()

bool Trie::search ( string word )

inline

Definition at line 65 of file main.cpp.

    {
        if (word.empty())
            return false;
        trie_node* node = tree[word[0] - 'a'].get();
        if ((int)word.length() == 1)
            return node->is_last() && tree_beginnings[word[0] - 'a'];
        for (int i = 1; i < (int)word.length(); ++i)
        {
            trie_node* child = node->find(word[i]);
            if (child == nullptr)    
                return false;
            node = child;
        }
        return node->is_last();
    }

References trie_node::find(), trie_node::is_last(), tree, and tree_beginnings.

◆ startsWith()

bool Trie::startsWith ( string prefix )

inline

Definition at line 82 of file main.cpp.

    {
        if (prefix.empty())
            return true;
        trie_node* node = tree[prefix[0] - 'a'].get();
        if ((int)prefix.length() == 1)
            return tree_beginnings[prefix[0] - 'a'];
        for (int i = 1; i < (int)prefix.length(); ++i)
        {
            trie_node* child = node->find(prefix[i]);
            if (child == nullptr)    
                return false;
            node = child;
        }
        return true;
    }