data_structures::trie Class Reference

Trie implementation for small-case English alphabets a-z More...

Public Member Functions
	trie ()=default
	Class default constructor.
void	insert (const std::string &str)
bool	search (const std::string &str, int index)
bool	deleteString (const std::string &str, int index)

Private Member Functions
uint8_t	char_to_int (const char &ch) const
	Convert a character to integer for indexing.
bool	search (const std::shared_ptr< trie > &root, const std::string &str, int index)

Private Attributes
std::array< std::shared_ptr< trie >, NUM_CHARS<< 1 >	arr
	Recursive tree nodes as an array of shared-pointers.
bool	isEndofWord = false
	identifier if a node is terminal node

Static Private Attributes
static constexpr uint8_t	NUM_CHARS = 26
	Number of alphabets.

Detailed Description

Trie implementation for small-case English alphabets a-z

Member Function Documentation

char_to_int()

uint8_t data_structures::trie::char_to_int ( const char & ch ) const

inlineprivate

Convert a character to integer for indexing.

Parameters

ch	character to index

Returns

unsigned integer index

                                              {
        if (ch >= 'A' && ch <= 'Z') {
            return ch - 'A';
        } else if (ch >= 'a' && ch <= 'z') {
            return ch - 'a' + NUM_CHARS;
        }
 
        std::cerr << "Invalid character present. Exiting...";
        std::exit(EXIT_FAILURE);
        return 0;
    }

Here is the call graph for this function:

deleteString()

bool data_structures::trie::deleteString ( const std::string & str, int index )

inline

removes the string if it is not a prefix of any other string, if it is then just sets the ::data_structure::trie::isEndofWord to false, else removes the given string

Note

the function ::data_structure::trie::deleteString might be erroneous

Todo

review the function ::data_structure::trie::deleteString and the commented lines

Parameters

str	string to remove
index	index to remove from

Returns

true if successful

false if unsuccessful

                                                       {
        if (index == str.length()) {
            if (!isEndofWord) {
                return false;
            }
            isEndofWord = false;
            // following lines - possible source of error?
            // for (int i = 0; i < NUM_CHARS; i++)
            //     if (!arr[i])
            //         return false;
            return true;
        }
        int j = char_to_int(str[index]);
        if (!arr[j]) {
            return false;
        }
        bool var = deleteString(str, index + 1);
        if (var) {
            arr[j].reset();
            if (isEndofWord) {
                return false;
            } else {
                int i = 0;
                for (i = 0; i < NUM_CHARS; i++) {
                    if (arr[i]) {
                        return false;
                    }
                }
                return true;
            }
        }
 
        /* should not return here */
        std::cout << __func__ << ":" << __LINE__
                  << "Should not reach this line\n";
        return false;
    }

Here is the call graph for this function:

insert()

void data_structures::trie::insert ( const std::string & str )

inline

insert string into the trie

Parameters

str	String to insert in the tree

                                      {
        std::shared_ptr<trie> root(nullptr);
 
        for (const char& ch : str) {
            int j = char_to_int(ch);
            if (root) {
                if (root->arr[j]) {
                    root = root->arr[j];
                } else {
                    std::shared_ptr<trie> temp(new trie());
                    root->arr[j] = temp;
                    root = temp;
                }
            } else if (arr[j]) {
                root = arr[j];
            } else {
                std::shared_ptr<trie> temp(new trie());
                arr[j] = temp;
                root = temp;
            }
        }
        root->isEndofWord = true;
    }

Here is the call graph for this function:

search() [1/2]

bool data_structures::trie::search ( const std::shared_ptr< trie > & root, const std::string & str, int index )

inlineprivate

search a string exists inside a given root trie

Parameters

str	string to search for
index	start index to search from

Returns

true if found

false if not found

                           {
        if (index == str.length()) {
            if (!root->isEndofWord) {
                return false;
            }
            return true;
        }
        int j = char_to_int(str[index]);
        if (!root->arr[j]) {
            return false;
        }
        return search(root->arr[j], str, index + 1);
    }

Here is the call graph for this function:

search() [2/2]

bool data_structures::trie::search ( const std::string & str, int index )

inline

search a string exists inside the trie

Parameters

str	string to search for
index	start index to search from

Returns

true if found

false if not found

                                                 {
        if (index == str.length()) {
            if (!isEndofWord) {
                return false;
            }
            return true;
        }
        int j = char_to_int(str[index]);
        if (!arr[j]) {
            return false;
        }
        return search(arr[j], str, index + 1);
    }

Here is the call graph for this function:

---

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

• data_structures/trie_tree.cpp