TheAlgorithms/C++ 1.0.0
All the algorithms implemented in C++
Loading...
Searching...
No Matches
trie_tree.cpp
Go to the documentation of this file.
1
10#include <array>
11#include <cassert>
12#include <iostream>
13#include <memory>
14#include <string>
15
19namespace data_structures {
24class trie {
25 private:
26 static constexpr uint8_t NUM_CHARS = 26;
28 std::array<std::shared_ptr<trie>, NUM_CHARS << 1> arr;
29 bool isEndofWord = false;
30
37 uint8_t char_to_int(const char& ch) const {
38 if (ch >= 'A' && ch <= 'Z') {
39 return ch - 'A';
40 } else if (ch >= 'a' && ch <= 'z') {
41 return ch - 'a' + NUM_CHARS;
42 }
43
44 std::cerr << "Invalid character present. Exiting...";
45 std::exit(EXIT_FAILURE);
46 return 0;
47 }
48
55 bool search(const std::shared_ptr<trie>& root, const std::string& str,
56 int index) {
57 if (index == str.length()) {
58 if (!root->isEndofWord) {
59 return false;
60 }
61 return true;
62 }
63 int j = char_to_int(str[index]);
64 if (!root->arr[j]) {
65 return false;
66 }
67 return search(root->arr[j], str, index + 1);
68 }
69
70 public:
71 trie() = default;
72
76 void insert(const std::string& str) {
77 std::shared_ptr<trie> root(nullptr);
78
79 for (const char& ch : str) {
80 int j = char_to_int(ch);
81 if (root) {
82 if (root->arr[j]) {
83 root = root->arr[j];
84 } else {
85 std::shared_ptr<trie> temp(new trie());
86 root->arr[j] = temp;
87 root = temp;
88 }
89 } else if (arr[j]) {
90 root = arr[j];
91 } else {
92 std::shared_ptr<trie> temp(new trie());
93 arr[j] = temp;
94 root = temp;
95 }
96 }
97 root->isEndofWord = true;
98 }
99
106 bool search(const std::string& str, int index) {
107 if (index == str.length()) {
108 if (!isEndofWord) {
109 return false;
110 }
111 return true;
112 }
113 int j = char_to_int(str[index]);
114 if (!arr[j]) {
115 return false;
116 }
117 return search(arr[j], str, index + 1);
118 }
119
133 bool deleteString(const std::string& str, int index) {
134 if (index == str.length()) {
135 if (!isEndofWord) {
136 return false;
137 }
138 isEndofWord = false;
139 // following lines - possible source of error?
140 // for (int i = 0; i < NUM_CHARS; i++)
141 // if (!arr[i])
142 // return false;
143 return true;
144 }
145 int j = char_to_int(str[index]);
146 if (!arr[j]) {
147 return false;
148 }
149 bool var = deleteString(str, index + 1);
150 if (var) {
151 arr[j].reset();
152 if (isEndofWord) {
153 return false;
154 } else {
155 int i = 0;
156 for (i = 0; i < NUM_CHARS; i++) {
157 if (arr[i]) {
158 return false;
159 }
160 }
161 return true;
162 }
163 }
164
165 /* should not return here */
166 std::cout << __func__ << ":" << __LINE__
167 << "Should not reach this line\n";
168 return false;
169 }
170};
171} // namespace data_structures
172
177static void test() {
179 root.insert("Hello");
180 root.insert("World");
181
182 assert(!root.search("hello", 0));
183 std::cout << "hello - " << root.search("hello", 0) << "\n";
184
185 assert(root.search("Hello", 0));
186 std::cout << "Hello - " << root.search("Hello", 0) << "\n";
187
188 assert(!root.search("Word", 0));
189 std::cout << "Word - " << root.search("Word", 0) << "\n";
190
191 assert(root.search("World", 0));
192 std::cout << "World - " << root.search("World", 0) << "\n";
193
194 // Following lines of code give erroneous output
195 // root.deleteString("hello", 0);
196 // assert(!root.search("hello", 0));
197 // std::cout << "hello - " << root.search("world", 0) << "\n";
198}
199
204int main() {
205 test();
206
207 return 0;
208}
Trie implementation for small-case English alphabets a-z
Definition trie_tree.cpp:24
void insert(const std::string &str)
Definition trie_tree.cpp:76
std::array< std::shared_ptr< trie >, NUM_CHARS<< 1 > arr
Recursive tree nodes as an array of shared-pointers.
Definition trie_tree.cpp:28
bool search(const std::string &str, int index)
static constexpr uint8_t NUM_CHARS
Number of alphabets.
Definition trie_tree.cpp:26
bool isEndofWord
identifier if a node is terminal node
Definition trie_tree.cpp:29
trie()=default
Class default constructor.
bool search(const std::shared_ptr< trie > &root, const std::string &str, int index)
Definition trie_tree.cpp:55
uint8_t char_to_int(const char &ch) const
Convert a character to integer for indexing.
Definition trie_tree.cpp:37
bool deleteString(const std::string &str, int index)
for IO operations
for std::assert
static void test()
Testing function.
int main()
Main function.