Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00030 #ifndef __CLAW_TRIE_HPP__
00031 #define __CLAW_TRIE_HPP__
00032
00033 #include <list>
00034 #include <functional>
00035 #include <claw/binary_node.hpp>
00036
00037 namespace claw
00038 {
00039
00062 template<class T, class Comp = std::equal_to<T> > class trie
00063 {
00064 private:
00065
00066
00073 struct trie_node : public binary_node< trie_node >
00074 {
00076 T value;
00081 unsigned int count;
00082
00083 trie_node( const T& val, unsigned int c = 0 );
00084 trie_node( const trie_node& that );
00085
00086 };
00087
00088 public:
00089
00090
00091 typedef const T value_type;
00092 typedef Comp value_equal_to;
00093
00094 private:
00095 typedef trie_node* trie_node_ptr;
00096
00097 public:
00098
00099 trie();
00100 trie( const trie<T, Comp>& that );
00101 ~trie();
00102
00103 unsigned int size() const;
00104 bool empty() const;
00105
00106 void clear();
00107
00108 template<class InputIterator>
00109 void insert(InputIterator first, InputIterator last);
00110
00111 template <class InputIterator>
00112 unsigned int count(InputIterator first, InputIterator last);
00113
00114 private:
00116 static value_equal_to s_value_equal_to;
00117
00119 trie_node_ptr m_tree;
00120
00122 unsigned int m_size;
00123 };
00124
00125 }
00126
00127 #include <claw/impl/trie.tpp>
00128
00129 #endif // __CLAW_TRIE_HPP__