#ifndef _TireTree_hpp_
#define _TireTree_hpp_
#include <string>
#include <algorithm>
#include <iostream>
using std::string;
template<typename T>
class TireeTreeNode
{
public:
#define MAX_CHILD_NUM 26
TireeTreeNode() : leaf(false) {
for(int i = 0; i < MAX_CHILD_NUM; i++) childs[i] = 0;
}
~TireeTreeNode() {
for(int i = 0; i < MAX_CHILD_NUM; i++) {
delete childs[i] ;
childs[i] = 0;
}
}
TireeTreeNode* insert(char c) {
int i = std::tolower(c) - 'a';
if (i>= MAX_CHILD_NUM) return 0;
if (!childs[i]) {
childs[i] = new TireeTreeNode();
}
return childs[i];
}
TireeTreeNode* get(char c) {
int i = std::tolower(c) - 'a';
if (i>= MAX_CHILD_NUM) return 0;
return childs[i];
}
bool isLeaf() const { return leaf; }
void setLeaf() { leaf = true; }
void setValue(const T& v) { value = v;}
const T& getValue() const { return value; }
private:
TireeTreeNode* childs[MAX_CHILD_NUM];
bool leaf;
T value;
};
template<typename T>
class TireTree
{
public:
bool insert(const string& word, const T& v) {
int n = word.length();
TireeTreeNode<T>* node = &root;
for(int i =0; i < n && node; i++) {
node = node->insert(word[i]);
}
if(node) {
node->setLeaf();
node->setValue(v);
}
return node != 0;
}
T get(const string& word, const T& def = T() ) {
int n = word.length();
TireeTreeNode<T>* node = &root;
for (int i =0; i < n; i++) {
node = node->get(word[i]);
if (!node) return def;
}
return node && node->isLeaf() ? node->getValue() : def;
}
private:
TireeTreeNode<T> root;
};
int main(int argc, char* argv[]) {
using std::cout;
using std::endl;
TireTree<int> tree;
tree.insert("macro", 1);
tree.insert("iaaa", 2);
tree.insert("oaaa", 2);
tree.insert("aaa", 2);
tree.insert("spider", 3);
for(int i = 0; i < 10000; i++) {
cout << (tree.get("aaa",1) ==2)<< endl;
cout << (tree.get("Macro",1) == 1)<< endl;
cout << (tree.get("iaaa",1) ==2) << endl;
cout << (tree.get("oaaa",1) == 2 )<< endl;
cout << (tree.get("o1aaa") == 0 )<< endl;
cout << (tree.get("spider") == 3 )<< endl;
cout << (tree.get("od") == 0 )<< endl;
}
return 0;
}
#endif
