operations_on_datastructures::trie_operations::Tnode Class Reference

Class defining the structure of trie node and containing the methods to perform operations on them. More...

Collaboration diagram for operations_on_datastructures::trie_operations::Tnode:

Public Member Functions
	Tnode (const Tnode &node)
Tnode &	operator= (const Tnode &node)=default
	Tnode (Tnode &&)=default
Tnode &	operator= (Tnode &&)=default
uint8_t	numberOfChildren (Tnode *node)
	Function to count the number of children a node in the trie has.
void	Insert (const std::string &entry)
	Function to insert a word in the trie.
void	Delete (std::string entry)
	Function to verify presence and hence delete an entry from the trie.
void	DeleteFrom (Tnode *delete_from, std::string delete_string, int remove_index)
	Function recursively deletes the substring character by character iterating through the string to be deleted. It traverses till the end of word in a recursive fashion, from there it deletes characters one by one till it reaches back to the initial call.
bool	SearchPresence (const std::string &key)
	Function to check a word's presence in the trie (Basic)
void	SuggestAutocomplete (Tnode *new_root, const std::string &prefix)
	Recursive function to suggest all the entries of trie which have a given common prefix.
void	SearchSuggestions (const std::string &key)
	Lists out all the words in trie with the longest prefix of the search key that is present in the trie. For example - if trie contains "abc", "abcde", "abcdefg", "abcddef" and if the search key is "abcdezz", then the longest common prefix is "abcde" and hence search results will be "abcde", "abcdefg".
void	SuggestFreqAutocomplete (Tnode *new_root, const std::string &prefix, std::priority_queue< std::pair< int, std::string > > *suggestions)
	Recursive function to suggest most frequently searched entries of trie which have a given common prefix.
void	SearchFreqSuggestions (const std::string &key)
	Lists out the most frequent words in trie with the longest prefix of the search key that is present in the trie. For example - if trie contains "abc", "abcde", "abcdefg", "abcddef" and they have been previously searched for 3, 1, 2, 4 times respectively, if the search key is "ab", then the longest common prefix is "ab" and only the top 3 frequencies among the matches would be displayed viz. "abcddef", "abc", "abcdefg".
void	SelectionTop_3 (std::priority_queue< std::pair< int, std::string > > *suggestions)
	Function to display the 3 suggestions with highest frequency of search hits.

Private Attributes
std::vector< Tnode * >	english
bool	endOfWord
uint32_t	frequency

Static Private Attributes
static constexpr uint8_t	ENGLISH_ALPHABET_SIZE = 26

Detailed Description

Class defining the structure of trie node and containing the methods to perform operations on them.

Constructor & Destructor Documentation

Tnode() [1/2]

operations_on_datastructures::trie_operations::Tnode::Tnode ( )

inline

            {
        english.resize(ENGLISH_ALPHABET_SIZE, nullptr);
        endOfWord = false;
        frequency = 0;
    }

Tnode() [2/2]

operations_on_datastructures::trie_operations::Tnode::Tnode ( const Tnode & node )

inline

                             {
        english = node.english;
        endOfWord = node.endOfWord;
        frequency = node.frequency;
    }

~Tnode()

operations_on_datastructures::trie_operations::Tnode::~Tnode ( )

inline

             {
        int i = 0;
        for (i = 0; i < ENGLISH_ALPHABET_SIZE; i++) {
            if (english[i]) {
                delete english[i];
            }
        }
    }

Member Function Documentation

Delete()

void operations_on_datastructures::trie_operations::Tnode::Delete

(

std::string

entry

)

Function to verify presence and hence delete an entry from the trie.

Parameters

entry

string entry to be deleted from the trie

                                  {
    Tnode *cur_pos = this,
          *delete_from = this;  // Current pointer pointing to root
    int letter_index = 0, delete_from_index = 0, i = 0, n = entry.size();
 
    for (i = 0; i < n; i++) {
        // To ignore case
        letter_index = tolower(entry[i]) - 97;
 
        // Display error message when given entry is not present in the tree
        if (cur_pos->english[letter_index] == nullptr) {
            std::cout << "Entry not Found" << std::endl;
            return;
        }
        // If the current node is end of word for the current prefix or if it
        // has 2 or more branches It cannot be deleted while deleting the
        // required entry.
        if (numberOfChildren(cur_pos) > 1 || cur_pos->endOfWord) {
            delete_from = cur_pos;      // denotes the beginning of the shortest
                                        // suffix that is allowed to be deleted
            delete_from_index = i - 1;  // Beginning index of the suffix
                                        // corresponding to the 'entry'
        }
 
        // Traversing through the entry
        cur_pos = cur_pos->english[letter_index];
    }
 
    // cur_pos now points to the last char of entry. Display message if that
    // entry does not exist
    if (!cur_pos->endOfWord) {
        std::cout << "Entry not Found" << std::endl;
        return;
    }
 
    // If cur_pos is not a leaf node, unmark end of word and assign 0 to it's
    // frequency for deletion
    if (numberOfChildren(cur_pos)) {
        cur_pos->endOfWord = false;
        cur_pos->frequency = 0;
        return;
    }
 
    // The first character of the suffix to be deleted
    letter_index = tolower(entry[delete_from_index + 1]) - 97;
    // Point cur_pos to the next node
    cur_pos = delete_from->english[letter_index];
    // Sever the connection from the main trie
    delete_from->english[letter_index] = nullptr;
 
    // If number of characters in the suffix are more than 1, recursively delete
    // each character starting from cur_pos using the helper function
    if (n > delete_from_index + 2) {
        DeleteFrom(cur_pos, entry, delete_from_index + 2);
    }
    // If the suffix is only 1 char in length
    else {
        delete cur_pos;
    }
}

Here is the call graph for this function:

DeleteFrom()

void operations_on_datastructures::trie_operations::Tnode::DeleteFrom	(	Tnode *	delete_from,
		std::string	delete_string,
		int	remove_index )

Function recursively deletes the substring character by character iterating through the string to be deleted. It traverses till the end of word in a recursive fashion, from there it deletes characters one by one till it reaches back to the initial call.

Parameters

delete_from	the acting root to the required suffix to be deleted
delete_string	the string to be deleted from the trie
remove_index	index denoting the beginning of the substring to be deleted

                                         {
    if (delete_string.size() == remove_index) {
        int letter_index = tolower(delete_string[remove_index]) - 97;
 
        DeleteFrom(delete_from->english[letter_index], delete_string,
                   remove_index + 1);
 
        delete delete_from;
    }
}

Here is the call graph for this function:

Insert()

void operations_on_datastructures::trie_operations::Tnode::Insert

(

const std::string &

entry

)

Function to insert a word in the trie.

Parameters

entry

string entry to be inserted in the trie

                                         {
    Tnode *cur_pos = this;
    int letter_index = 0;
 
    for (auto &i : entry) {
        // To ignore case
        letter_index = tolower(i) - 97;
 
        // Allocate a node for each character of entry if not present in the
        // trie
        if (cur_pos->english[letter_index] == nullptr) {
            cur_pos->english[letter_index] = new Tnode();
        }
 
        cur_pos = cur_pos->english[letter_index];
    }
    // cur_pos points to the last char, mark it as end of word
    cur_pos->endOfWord = true;
}

numberOfChildren()

uint8_t operations_on_datastructures::trie_operations::Tnode::numberOfChildren ( Tnode * node )

inline

Function to count the number of children a node in the trie has.

Parameters

node	a trie node whose children need to be counted

Returns

count of the number of children of the given node (max 26)

                                                 {
        return ENGLISH_ALPHABET_SIZE -
               std::count(node->english.begin(), node->english.end(), nullptr);
    }

Here is the call graph for this function:

SearchFreqSuggestions()

void operations_on_datastructures::trie_operations::Tnode::SearchFreqSuggestions

(

const std::string &

key

)

Lists out the most frequent words in trie with the longest prefix of the search key that is present in the trie. For example - if trie contains "abc", "abcde", "abcdefg", "abcddef" and they have been previously searched for 3, 1, 2, 4 times respectively, if the search key is "ab", then the longest common prefix is "ab" and only the top 3 frequencies among the matches would be displayed viz. "abcddef", "abc", "abcdefg".

Parameters

key	the string key to be searched for suggestions

                                                      {
    Tnode *cur_pos = nullptr, *prev_pos = nullptr;
    cur_pos = prev_pos = this;  // maintaining 2 pointers, initialized to root
    int letter_index = 0;
    std::string prefix =
        "";  // variable storing the updated value of longest common prefix
    std::priority_queue<std::pair<int, std::string> >
        suggestions;  // max heap to store (frequency, word) in descending order
                      // of freq
 
    std::priority_queue<std::pair<int, std::string> > *Suggestions =
        &suggestions;
 
    for (auto &i : key) {
        letter_index = tolower(i) - 97;
        prev_pos = cur_pos;  // Previous pointer updated to point to the last
                             // char of the longest common prefix
 
        // When the node for the character does not exist, longest prefix has
        // been determined and SuggestFreqAutocomplete is called
        if (cur_pos->english[letter_index] == nullptr) {
            SuggestFreqAutocomplete(prev_pos, prefix, Suggestions);
            // To display the top 3 results
            SelectionTop_3(Suggestions);
            std::cout << "- - - - - - - - - - - - - - - - - - - - - - - - - - "
                      << std::endl;
            return;
        }
        // Updating the longest common prefix
        prefix += char(tolower(i));
        cur_pos = cur_pos->english[letter_index];
    }
    // If the key is a valid entry of trie, display it @ top of the suggestions
    if (cur_pos->endOfWord) {
        (cur_pos->frequency)++;
        std::cout << key << std::endl;
    }
 
    (void)prev_pos;  // Idiom to ignore previous pointer
 
    // Call for Suggestions when the search key is present as an entry/a prefix
    // in the trie
    SuggestFreqAutocomplete(cur_pos, prefix, Suggestions);
    // Display the top 3 results
    SelectionTop_3(Suggestions);
 
    std::cout << "- - - - - - - - - - - - - - - - - - - - - - - - - - "
              << std::endl;
    return;
}

Here is the call graph for this function:

SearchPresence()

bool operations_on_datastructures::trie_operations::Tnode::SearchPresence

(

const std::string &

key

)

Function to check a word's presence in the trie (Basic)

Parameters

key	the string key to be searched in the trie

Returns

true if the key is found

false if the key is not found

                                               {
    Tnode *cur_pos = this;
    int letter_index = 0;
 
    for (auto &i : key) {
        letter_index = tolower(i) - 97;
        // If any character in the order of the key is absent, word not found!
        if (cur_pos->english[letter_index] == nullptr) {
            return false;
        }
        cur_pos = cur_pos->english[letter_index];
    }
    // Word is only present in the trie if the key is a valid complete entry and
    // not just a prefix.
    if (cur_pos->endOfWord) {
        (cur_pos->frequency)++;
        return true;
    } else {
        return false;
    }
}

SearchSuggestions()

void operations_on_datastructures::trie_operations::Tnode::SearchSuggestions

(

const std::string &

key

)

Lists out all the words in trie with the longest prefix of the search key that is present in the trie. For example - if trie contains "abc", "abcde", "abcdefg", "abcddef" and if the search key is "abcdezz", then the longest common prefix is "abcde" and hence search results will be "abcde", "abcdefg".

Parameters

key	the string key to be searched for suggestions

                                                  {
    Tnode *cur_pos = nullptr, *prev_pos = nullptr;
    cur_pos = prev_pos = this;  // maintaining 2 pointers, initialized to root
    int letter_index = 0;
    std::string prefix =
        "";  // variable storing the updated value of longest common prefix
 
    for (auto &i : key) {
        letter_index = tolower(i) - 97;
        prev_pos = cur_pos;  // Previous pointer updated to point to the last
                             // char of the longest common prefix
 
        // When the node for the character does not exist, longest prefix has
        // been determined and SuggestAutocomplete is called
        if (cur_pos->english[letter_index] == nullptr) {
            SuggestAutocomplete(prev_pos, prefix);
            std::cout << "- - - - - - - - - - - - - - - - - - - - - - - - - - "
                      << std::endl;
            return;
        }
        // Updating the longest common prefix
        prefix += char(tolower(i));
        cur_pos = cur_pos->english[letter_index];
    }
    // If the key is a valid entry of trie, display it @ top of the suggestions
    if (cur_pos->endOfWord) {
        std::cout << key << std::endl;
        (cur_pos->frequency)++;
    }
 
    (void)prev_pos;  // Idiom to ignore previous pointer
 
    // Call for suggestions when the search key is present as an entry/a prefix
    // in the trie
    SuggestAutocomplete(cur_pos, prefix);
    std::cout << "- - - - - - - - - - - - - - - - - - - - - - - - - - "
              << std::endl;
    return;
}

Here is the call graph for this function:

SelectionTop_3()

void operations_on_datastructures::trie_operations::Tnode::SelectionTop_3

(

std::priority_queue< std::pair< int, std::string > > *

suggestions

)

Function to display the 3 suggestions with highest frequency of search hits.

Parameters

suggestions

a max heap that contains pairs of (frequency, word) heapified based on frequency

                                                              {
    // Display Either top 3 or total number of suggestions, whichever is smaller
    int n = suggestions->size(), Top = 0;
    Top = n < 3 ? n : 3;
    while (Top--) {
        std::cout << suggestions->top().second << std::endl;
        suggestions->pop();
    }
}

Here is the call graph for this function:

SuggestAutocomplete()

void operations_on_datastructures::trie_operations::Tnode::SuggestAutocomplete	(	Tnode *	new_root,
		const std::string &	prefix )

Recursive function to suggest all the entries of trie which have a given common prefix.

Parameters

new_root	pointer pointing to the node corresponding to the last char of prefix
prefix	the common prefix that all the suggestions must have

                                                                        {
    // Iterate through all 26 nodes as we have to print all strings with the
    // given prefix
    int i = 0;
    for (i = 0; i < ENGLISH_ALPHABET_SIZE; i++) {
        if (new_root->english[i] != nullptr) {
            // Print the sugestion only if it's a valid complete entry and not
            // just a prefix
            if (new_root->english[i]->endOfWord) {
                std::cout << prefix + char(i + 97) << std::endl;
            }
 
            SuggestAutocomplete(new_root->english[i], prefix + char(i + 97));
        }
    }
}

Here is the call graph for this function:

SuggestFreqAutocomplete()

void operations_on_datastructures::trie_operations::Tnode::SuggestFreqAutocomplete	(	Tnode *	new_root,
		const std::string &	prefix,
		std::priority_queue< std::pair< int, std::string > > *	suggestions )

Recursive function to suggest most frequently searched entries of trie which have a given common prefix.

Parameters

new_root	pointer pointing to the node corresponding to the last char of prefix
prefix	the common prefix that all the suggestions must have
suggestions	a max heap that contains pairs of (frequency, word) heapified based on frequency

                                                              {
    int i = 0;
    for (i = 0; i < ENGLISH_ALPHABET_SIZE; i++) {
        if (new_root->english[i] != nullptr) {
            // Add to sugestions only if it's a valid complete entry and not
            // just a prefix
            if (new_root->english[i]->endOfWord) {
                suggestions->push(std::make_pair(
                    new_root->english[i]->frequency, prefix + char(i + 97)));
            }
 
            SuggestFreqAutocomplete(new_root->english[i], prefix + char(i + 97),
                                    suggestions);
        }
    }
}

Here is the call graph for this function:

---

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

• operations_on_datastructures/trie_multiple_search.cpp