trie_multiple_search.cpp File Reference

Trie datastructure with search variants More...

#include <algorithm>
#include <cassert>
#include <cctype>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <queue>

Include dependency graph for trie_multiple_search.cpp:

Go to the source code of this file.

Classes
class	operations_on_datastructures::trie_operations::Tnode
	Class defining the structure of trie node and containing the methods to perform operations on them. More...

Namespaces
namespace	operations_on_datastructures
	for std::vector
namespace	trie_operations
	Functions for Trie datastructure implementation.

Functions
static void	test ()
	Function to test a simple search before and after deleting an entry. And to test out the multiple variants of search.
int	main ()
	Main function.

Detailed Description

Trie datastructure with search variants

This provides multiple variants of search functions on a trie structure utilizing STL. The trie is valid for only English alphabets.

Author

Ghanashyam

Definition in file trie_multiple_search.cpp.

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 464 of file trie_multiple_search.cpp.

           {
    test();  // run self-test implementations
    return 0;
}

test()

void test ( )

static

Function to test a simple search before and after deleting an entry. And to test out the multiple variants of search.

Definition at line 425 of file trie_multiple_search.cpp.

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