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

Definition at line 24 of file trie_tree.cpp.

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

Definition at line 37 of file trie_tree.cpp.

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

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

Definition at line 133 of file trie_tree.cpp.

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

insert()

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

inline

insert string into the trie

Parameters

str	String to insert in the tree

Definition at line 76 of file trie_tree.cpp.

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

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

Definition at line 55 of file trie_tree.cpp.

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

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

Definition at line 106 of file trie_tree.cpp.

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

Member Data Documentation

arr

std::array<std::shared_ptr<trie>, NUM_CHARS << 1> data_structures::trie::arr

private

Recursive tree nodes as an array of shared-pointers.

Definition at line 28 of file trie_tree.cpp.

isEndofWord

bool data_structures::trie::isEndofWord = false

private

identifier if a node is terminal node

Definition at line 29 of file trie_tree.cpp.

NUM_CHARS

uint8_t data_structures::trie::NUM_CHARS = 26

staticconstexprprivate

Number of alphabets.

Definition at line 26 of file trie_tree.cpp.

---

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

• data_structures/trie_tree.cpp