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.

Definition at line 37 of file trie_multiple_search.cpp.

Constructor & Destructor Documentation

Tnode() [1/2]

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

inline

Definition at line 50 of file trie_multiple_search.cpp.

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

Tnode() [2/2]

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

inline

Definition at line 56 of file trie_multiple_search.cpp.

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

~Tnode()

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

inline

Definition at line 93 of file trie_multiple_search.cpp.

             {
        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

Definition at line 153 of file trie_multiple_search.cpp.

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

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

Definition at line 137 of file trie_multiple_search.cpp.

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

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

Definition at line 107 of file trie_multiple_search.cpp.

                                         {
    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)

Definition at line 72 of file trie_multiple_search.cpp.

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

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

Definition at line 368 of file trie_multiple_search.cpp.

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

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

Definition at line 220 of file trie_multiple_search.cpp.

                                               {
    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

Definition at line 274 of file trie_multiple_search.cpp.

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

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

Definition at line 320 of file trie_multiple_search.cpp.

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

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

Definition at line 249 of file trie_multiple_search.cpp.

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

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

Definition at line 340 of file trie_multiple_search.cpp.

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

Member Data Documentation

endOfWord

bool operations_on_datastructures::trie_operations::Tnode::endOfWord

private

Definition at line 44 of file trie_multiple_search.cpp.

english

std::vector<Tnode *> operations_on_datastructures::trie_operations::Tnode::english

private

Definition at line 41 of file trie_multiple_search.cpp.

ENGLISH_ALPHABET_SIZE

uint8_t operations_on_datastructures::trie_operations::Tnode::ENGLISH_ALPHABET_SIZE = 26

staticconstexprprivate

Definition at line 39 of file trie_multiple_search.cpp.

frequency

uint32_t operations_on_datastructures::trie_operations::Tnode::frequency

private

Definition at line 47 of file trie_multiple_search.cpp.

---

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

• operations_on_datastructures/trie_multiple_search.cpp