trie_multiple_search.cpp

Go to the documentation of this file.

 
#include <algorithm>  
#include <cassert>    
#include <cctype>     
#include <cstdint>    
#include <cstring>    
#include <iostream>   
#include <queue>      
 
namespace operations_on_datastructures {
namespace trie_operations {
class Tnode {
 private:
    static constexpr uint8_t ENGLISH_ALPHABET_SIZE = 26;
    // pointers to alphabets
    std::vector<Tnode *> english;
 
    // To mark the end of word
    bool endOfWord;
 
    // To store the frequency of searches for the word
    uint32_t frequency;
 
 public:
    Tnode() {
        english.resize(ENGLISH_ALPHABET_SIZE, nullptr);
        endOfWord = false;
        frequency = 0;
    }
    // Copy Constructor
    Tnode(const Tnode &node) {
        english = node.english;
        endOfWord = node.endOfWord;
        frequency = node.frequency;
    }
 
    Tnode &operator=(const Tnode &node) = default;
 
    Tnode(Tnode &&) = default;
 
    Tnode &operator=(Tnode &&) = default;
    inline uint8_t numberOfChildren(Tnode *node) {
        return ENGLISH_ALPHABET_SIZE -
               std::count(node->english.begin(), node->english.end(), nullptr);
    }
 
    // Functions to perform operations on trie
    void Insert(const std::string &entry);
    void Delete(std::string entry);
    void DeleteFrom(Tnode *delete_from, std::string delete_string,
                    int remove_index);
    bool SearchPresence(const std::string &key);
    void SuggestAutocomplete(Tnode *new_root, const std::string &prefix);
    void SearchSuggestions(const std::string &key);
    void SuggestFreqAutocomplete(
        Tnode *new_root, const std::string &prefix,
        std::priority_queue<std::pair<int, std::string> > *suggestions);
    void SearchFreqSuggestions(const std::string &key);
    void SelectionTop_3(
        std::priority_queue<std::pair<int, std::string> > *suggestions);
 
    // To free up the dynamically allocated objects
    ~Tnode() {
        int i = 0;
        for (i = 0; i < ENGLISH_ALPHABET_SIZE; i++) {
            if (english[i]) {
                delete english[i];
            }
        }
    }
};
 
void Tnode::Insert(const std::string &entry) {
    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;
}
 
void Tnode::DeleteFrom(Tnode *delete_from, std::string delete_string,
                       int remove_index) {
    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;
    }
}
 
void Tnode::Delete(std::string entry) {
    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;
    }
}
 
bool Tnode::SearchPresence(const std::string &key) {
    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;
    }
}
 
void Tnode::SuggestAutocomplete(Tnode *new_root, const std::string &prefix) {
    // 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));
        }
    }
}
 
void Tnode::SearchSuggestions(const std::string &key) {
    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;
}
 
void Tnode::SelectionTop_3(
    std::priority_queue<std::pair<int, std::string> > *suggestions) {
    // 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();
    }
}
 
void Tnode::SuggestFreqAutocomplete(
    Tnode *new_root, const std::string &prefix,
    std::priority_queue<std::pair<int, std::string> > *suggestions) {
    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);
        }
    }
}
 
void Tnode::SearchFreqSuggestions(const std::string &key) {
    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;
}
}  // namespace trie_operations
}  // namespace operations_on_datastructures
 
static void test() {
    auto root = new operations_on_datastructures::trie_operations::Tnode();
    std::vector<std::string> inputs = {
        "abcde", "sss",    "ssss",  "ssst", "sssu", "sssv",
        "sst",   "ssts",   "sstt",  "sstu", "tutu", "tutuv",
        "tutuu", "tutuvs", "tutus", "tvst", "tvsu", "vvvv"};
 
    for (auto &i : inputs) {
        root->Insert(i);
    }
    // Search an existing entry
    assert(root->SearchPresence("vvvv"));
    std::cout << root->SearchPresence("vvvv") << std::endl;
    // Delete it
    root->Delete("vvvv");
    // Search for the entry again
    assert(!root->SearchPresence("vvvv"));
    std::cout << root->SearchPresence("vvvv") << std::endl;
 
    std::cout << root->SearchPresence("tutu") << std::endl;
    root->SearchSuggestions("tutu");
    std::cout << root->SearchPresence("tutu") << std::endl;
 
    root->SearchSuggestions("tutuv");
    std::cout << root->SearchPresence("tutuv") << std::endl;
 
    root->SearchSuggestions("tutuvs");
 
    root->SearchFreqSuggestions(
        "tu");  // The top 3 frequent entries with prefix tu are tutu, tutuv &
                // tutuvs respectively
    root->SearchSuggestions(
        "");  // Empty search to list all the entries in the trie
}
 
int main(int argc, char const *argv[]) {
    test();  // run self-test implementations
    return 0;
}