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.

Definition at line 39 of file trie_using_hashmap.cpp.

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

Definition at line 122 of file trie_using_hashmap.cpp.

                                     {
        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();
        }
    }

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

Definition at line 160 of file trie_using_hashmap.cpp.

                                                             {
        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;
    }

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

Definition at line 62 of file trie_using_hashmap.cpp.

                                       {
        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;
        }
    }

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

Definition at line 188 of file trie_using_hashmap.cpp.

                                                                {
        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);  
 
        return result;
    }

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

Definition at line 82 of file trie_using_hashmap.cpp.

                                       {
        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

Definition at line 107 of file trie_using_hashmap.cpp.

                                            {
        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

Definition at line 51 of file trie_using_hashmap.cpp.

---

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

• data_structures/trie_using_hashmap.cpp