Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
data_structures::trie Class Reference

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

Collaboration diagram for data_structures::trie:
[legend]

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. More...
 
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
chcharacter to index
Returns
unsigned integer index
38  {
39  if (ch >= 'A' && ch <= 'Z') {
40  return ch - 'A';
41  } else if (ch >= 'a' && ch <= 'z') {
42  return ch - 'a' + NUM_CHARS;
43  }
44 
45  std::cerr << "Invalid character present. Exiting...";
46  std::exit(EXIT_FAILURE);
47  return 0;
48  }
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
strstring to remove
indexindex to remove from
Returns
true if successful
false if unsuccessful
134  {
135  if (index == str.length()) {
136  if (!isEndofWord) {
137  return false;
138  }
139  isEndofWord = false;
140  // following lines - possible source of error?
141  // for (int i = 0; i < NUM_CHARS; i++)
142  // if (!arr[i])
143  // return false;
144  return true;
145  }
146  int j = char_to_int(str[index]);
147  if (!arr[j]) {
148  return false;
149  }
150  bool var = deleteString(str, index + 1);
151  if (var) {
152  arr[j].reset();
153  if (isEndofWord) {
154  return false;
155  } else {
156  int i = 0;
157  for (i = 0; i < NUM_CHARS; i++) {
158  if (arr[i]) {
159  return false;
160  }
161  }
162  return true;
163  }
164  }
165 
166  /* should not return here */
167  std::cout << __func__ << ":" << __LINE__
168  << "Should not reach this line\n";
169  return false;
170  }
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
strString to insert in the tree
77  {
78  std::shared_ptr<trie> root(nullptr);
79 
80  for (const char& ch : str) {
81  int j = char_to_int(ch);
82  if (root) {
83  if (root->arr[j]) {
84  root = root->arr[j];
85  } else {
86  std::shared_ptr<trie> temp(new trie());
87  root->arr[j] = temp;
88  root = temp;
89  }
90  } else if (arr[j]) {
91  root = arr[j];
92  } else {
93  std::shared_ptr<trie> temp(new trie());
94  arr[j] = temp;
95  root = temp;
96  }
97  }
98  root->isEndofWord = true;
99  }

◆ 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
strstring to search for
indexstart index to search from
Returns
true if found
false if not found
57  {
58  if (index == str.length()) {
59  if (!root->isEndofWord) {
60  return false;
61  }
62  return true;
63  }
64  int j = char_to_int(str[index]);
65  if (!root->arr[j]) {
66  return false;
67  }
68  return search(root->arr[j], str, index + 1);
69  }

◆ search() [2/2]

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

search a string exists inside the trie

Parameters
strstring to search for
indexstart index to search from
Returns
true if found
false if not found
107  {
108  if (index == str.length()) {
109  if (!isEndofWord) {
110  return false;
111  }
112  return true;
113  }
114  int j = char_to_int(str[index]);
115  if (!arr[j]) {
116  return false;
117  }
118  return search(arr[j], str, index + 1);
119  }
Here is the call graph for this function:

The documentation for this class was generated from the following file:
std::shared_ptr
STL class.
data_structures::trie::trie
trie()=default
Class default constructor.
std::string::length
T length(T... args)
data_structures::trie::isEndofWord
bool isEndofWord
identifier if a node is terminal node
Definition: trie_tree.cpp:30
std::cerr
data_structures::trie::NUM_CHARS
static constexpr uint8_t NUM_CHARS
Number of alphabets.
Definition: trie_tree.cpp:27
data_structures::trie::char_to_int
uint8_t char_to_int(const char &ch) const
Convert a character to integer for indexing.
Definition: trie_tree.cpp:38
data_structures::trie::deleteString
bool deleteString(const std::string &str, int index)
Definition: trie_tree.cpp:134
data_structures::trie::arr
std::array< std::shared_ptr< trie >, NUM_CHARS<< 1 > arr
Recursive tree nodes as an array of shared-pointers.
Definition: trie_tree.cpp:29
data_structures::trie::search
bool search(const std::shared_ptr< trie > &root, const std::string &str, int index)
Definition: trie_tree.cpp:56
std::exit
T exit(T... args)