template<typename T, typename V, typename Cmp = std::less<T>, typename Items = SetItems<T, V, Cmp>>
class Mezzanine::Trie< T, V, Cmp, Items >
Trie main class.
- Template Parameters
-
| T | Type for each element in the key |
| V | Type of the value that the key will be representing |
| Cmp | Comparison functor |
| Items | The data structure that represents each node in the Trie. Items can be Mezzanine::SetItems<T, V, Cmp> or Mezzanine::VectorItems<T, V, Cmp, Max>, Max is the integer representing number of elements in each Trie node. |
Usage of the Trie
Declarating the Trie
A Trie with key as chars and value as std::string can be declared as given below
#include <string>
#include <trie.h>
int main(int argc, char ** argv) {
return 0;
}
Populatiion and deletion from the Trie
Trie can be populated by using the Trie::insert method and element can be removed using Trie::erase.
#include <trie.h>
#include <string>
#include <iostream>
int main(int argc, char ** argv) {
if (dictionary.insert("karma$", "Destiny or fate, following as effect from cause").second) {
std::cout << "added karma" << std::endl;
}
if (dictionary.erase("karma$")) {
std::cout << "removed karma" << std::endl;
}
return 0;
}
Retrieval of Value
Value for a key can be retrieved using Trie::get method and the existence of the key can be tested using Trie::hasKey method.
#include <trie.h>
#include <string>
#include <iostream>
int main(int argc, char ** argv) {
dictionary.insert("karma$", "Destiny or fate, following as effect from cause");
if (dictionary.hasKey("karma$")) {
std::cout << "key karma found" << std::endl;
}
std::string * result = dictionary.get("karma$");
if (result) {
std::cout << result->c_str() << std::endl;
}
return 0;
}
Searching keys which have common prefix
Keys which begins with a specific charactars can be retrieved using Trie::startsWith method
#include <trie.h>
#include <string>
#include <iostream>
#include <vector>
int main(int argc, char ** argv) {
dictionary.insert("karma", "Destiny or fate, following as effect from cause");
for (; iter != dictionary.end(); ++iter) {
std::cout << iter->first << " : " << iter->second->c_str() << std::endl;
}
return 0;
}
Trie with each Node as an array
Here each node of the Trie is an array. The advantage is that the searching of a symbol in the array takes O(1) time (is constant time). The disadvantage is that the array will have empty elements so the space used will more than actually required.
#include <trie.h>
#include <string>
#include <iostream>
#include <vector>
int main(int argc, char ** argv) {
return 0;
}
Efficient use of Trie for alphabets
Below example shows how to use Trie to operate on alphabets efficiently. Here VectorItems is used to store alphabets with size of 28 (26 alphabets + space + end symbol).
#include <trie.h>
#include <string>
#include <iostream>
#include <vector>
#include <cctype>
class TrieCaseInsensitiveCompare
{
public:
bool operator()(char v1, char v2) {
int i1 = std::tolower(v1);
int i2 = std::tolower(v2);
return i1 < i2;
}
};
class AlphaToIndex
{
public:
unsigned int operator()(const char & c) const {
unsigned int index = 0;
if (c == ' ') {
index = 27;
} else if (c >= 'A' && c <= 'Z') {
index = c - 'A' + 1;
} else if (c >= 'a' && c <= 'z') {
index = c - 'a' + 1;
}
return index;
}
};
int main(int argc, char ** argv) {
TrieCaseInsensitiveCompare,
> dictionary('\0');
if (dictionary.insert("karma", "Destiny or fate, following as effect from cause").second) {
std::cout << "added karma" << std::endl;
}
if (dictionary.erase("karma")) {
std::cout << "removed karma" << std::endl;
}
return 0;
}
Trie with each Node as a set
Here each node will be an ordered set. Here there will be no extra usage of space but search for a symbol in the node takes logarithmic time. Trie with this feature can also be used for caseinsensitive symbol handling.
#include <trie.h>
#include <string>
#include <iostream>
#include <set>
int main(int argc, char ** argv) {
return 0;
}
Using Trie::iterator
Trie iterator can be used the same way as STL iterator. Key and value can be accessed from iterator using first and secod member. first is vector of key characters and second is a pointer to the value.
#include <trie.h>
#include <string>
#include <iostream>
#include <vector>
int main(int argc, char ** argv) {
dictionary.insert("karma$", "Destiny or fate, following as effect from cause");
for (; iter != iend; ++iter) {
std::cout << iter->first << " " << iter->second->c_str() << std::endl;
}
return 0;
}
Definition at line 1287 of file trie.h.
MezzanineEngine 
1.8.4