data_structures::trie_using_hashmap::Trie Class Reference

Trie class, implementation of trie using hashmap in each trie node for all the characters of char16_t(UTF-16)type with methods to insert, delete, search, start with and to recommend words based on a given prefix. More...

Collaboration diagram for data_structures::trie_using_hashmap::Trie:

Classes
struct	Node
	struct representing a trie node. More...

Public Member Functions
	Trie ()=default
	< Constructor
void	insert (const std::string &word)
	insert the string into the trie
bool	search (const std::string &word)
	search a word/string inside the trie
bool	startwith (const std::string &prefix)
	search a word/string that starts with a given prefix
void	delete_word (std::string word)
	delete a word/string from a trie
std::vector< std::string >	get_all_words (std::vector< std::string > results, const std::shared_ptr< Node > &element, std::string prefix)
	helper function to predict/recommend words that starts with a given prefix from the end of prefix's node iterate through all the child nodes by recursively appending all the possible words below the trie
std::vector< std::string >	predict_words (const std::string &prefix)
	predict/recommend a word that starts with a given prefix

Private Attributes
std::shared_ptr< Node >	root_node
	declaring root node of trie

Detailed Description

Trie class, implementation of trie using hashmap in each trie node for all the characters of char16_t(UTF-16)type with methods to insert, delete, search, start with and to recommend words based on a given prefix.

Member Function Documentation

delete_word()

void data_structures::trie_using_hashmap::Trie::delete_word ( std::string word )

inline

delete a word/string from a trie

Parameters

word	string to delete from trie

                                     {
        std::shared_ptr<Node> curr = root_node;
        std::stack<std::shared_ptr<Node>> nodes;
        int cnt = 0;
        for (char ch : word) {
            if (curr->children.find(ch) == curr->children.end()) {
                return;
            }
            if (curr->word_end) {
                cnt++;
            }
 
            nodes.push(curr->children[ch]);
            curr = curr->children[ch];
        }
        // Delete only when it's a word, and it has children after
        // or prefix in the line
        if (nodes.top()->word_end) {
            nodes.top()->word_end = false;
        }
        // Delete only when it has no children after
        // and also no prefix in the line
        while (!(nodes.top()->word_end) && nodes.top()->children.empty()) {
            nodes.pop();
            nodes.top()->children.erase(word.back());
            word.pop_back();
        }
    }

Here is the call graph for this function:

get_all_words()

std::vector< std::string > data_structures::trie_using_hashmap::Trie::get_all_words ( std::vector< std::string > results, const std::shared_ptr< Node > & element, std::string prefix )

inline

helper function to predict/recommend words that starts with a given prefix from the end of prefix's node iterate through all the child nodes by recursively appending all the possible words below the trie

Parameters

prefix	string to recommend the words
element	node at the end of the given prefix
results	list to store the all possible words

Returns

list of recommended words

                                                             {
        if (element->word_end) {
            results.push_back(prefix);
        }
        if (element->children.empty()) {
            return results;
        }
        for (auto const& x : element->children) {
            std::string key = "";
            key = x.first;
            prefix += key;
 
            results =
                get_all_words(results, element->children[x.first], prefix);
 
            prefix.pop_back();
        }
 
        return results;
    }

Here is the call graph for this function:

insert()

void data_structures::trie_using_hashmap::Trie::insert ( const std::string & word )

inline

insert the string into the trie

Parameters

word	string to insert in the trie

                                       {
        std::shared_ptr<Node> curr = root_node;
        for (char ch : word) {
            if (curr->children.find(ch) == curr->children.end()) {
                curr->children[ch] = std::make_shared<Node>();
            }
            curr = curr->children[ch];
        }
 
        if (!curr->word_end && curr != root_node) {
            curr->word_end = true;
        }
    }

Here is the call graph for this function:

predict_words()

std::vector< std::string > data_structures::trie_using_hashmap::Trie::predict_words ( const std::string & prefix )

inline

predict/recommend a word that starts with a given prefix

Parameters

prefix

string to search for

Returns

list of recommended words

< iteratively and recursively get the recommended words

                                                                {
        std::vector<std::string> result;
        std::shared_ptr<Node> curr = root_node;
        // traversing until the end of the given prefix in trie
 
        for (char ch : prefix) {
            if (curr->children.find(ch) == curr->children.end()) {
                return result;
            }
 
            curr = curr->children[ch];
        }
 
        // if the given prefix is the only word without children
        if (curr->word_end && curr->children.empty()) {
            result.push_back(prefix);
            return result;
        }
 
        result = get_all_words(
            result, curr,
            prefix);  ///< iteratively and recursively get the recommended words
 
        return result;
    }

Here is the call graph for this function:

search()

bool data_structures::trie_using_hashmap::Trie::search ( const std::string & word )

inline

search a word/string inside the trie

Parameters

word	string to search for

Returns

true if found

false if not found

                                       {
        std::shared_ptr<Node> curr = root_node;
        for (char ch : word) {
            if (curr->children.find(ch) == curr->children.end()) {
                return false;
            }
            curr = curr->children[ch];
            if (!curr) {
                return false;
            }
        }
 
        if (curr->word_end) {
            return true;
        } else {
            return false;
        }
    }

startwith()

bool data_structures::trie_using_hashmap::Trie::startwith ( const std::string & prefix )

inline

search a word/string that starts with a given prefix

Parameters

prefix

string to search for

Returns

true if found

false if not found

                                            {
        std::shared_ptr<Node> curr = root_node;
        for (char ch : prefix) {
            if (curr->children.find(ch) == curr->children.end()) {
                return false;
            }
            curr = curr->children[ch];
        }
        return true;
    }

Member Data Documentation

root_node

std::shared_ptr<Node> data_structures::trie_using_hashmap::Trie::root_node

private

Initial value:

=
        std::make_shared<Node>()

declaring root node of trie

---

The documentation for this class was generated from the following file:

• data_structures/trie_using_hashmap.cpp