trie.tpp
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 #include <iostream>
00031 #include <cassert>
00032
00033
00034
00035
00036
00043 template<class T, class Comp>
00044 claw::trie<T, Comp>::trie_node::trie_node( const T& val,
00045 unsigned int c )
00046 : claw::binary_node< typename claw::trie<T, Comp>::trie_node >(), value(val),
00047 count(0)
00048 {
00049
00050 }
00051
00052
00057 template<class T, class Comp>
00058 claw::trie<T, Comp>::trie_node::trie_node( const trie_node& that )
00059 : claw::binary_node< typename claw::trie<T, Comp>::trie_node >(that),
00060 value(that.value), count(that.count)
00061 {
00062
00063 }
00064
00065
00066
00067
00068 template<class T, class Comp>
00069 typename claw::trie<T, Comp>::value_equal_to
00070 claw::trie<T, Comp>::s_value_equal_to;
00071
00072
00077 template<class T, class Comp>
00078 claw::trie<T, Comp>::trie()
00079 {
00080 m_size = 0;
00081 m_tree = NULL;
00082
00083 assert(empty());
00084 }
00085
00086
00087
00088
00089
00090 template<class T, class Comp>
00091 claw::trie<T, Comp>::trie( const claw::trie<T, Comp>& that )
00092 {
00093 if (that.m_tree)
00094 m_tree = new trie_node( *that.m_tree );
00095 else
00096 m_tree = NULL;
00097
00098 m_size = that.m_size;
00099 }
00100
00101
00105 template<class T, class Comp>
00106 claw::trie<T, Comp>::~trie()
00107 {
00108 if (m_tree)
00109 delete m_tree;
00110 }
00111
00112
00116 template<class T, class Comp>
00117 unsigned int claw::trie<T, Comp>::size() const
00118 {
00119 return m_size;
00120 }
00121
00122
00126 template<class T, class Comp>
00127 bool claw::trie<T, Comp>::empty() const
00128 {
00129 return m_tree==NULL;
00130 }
00131
00132
00137 template<class T, class Comp>
00138 void claw::trie<T, Comp>::clear()
00139 {
00140 if (m_tree)
00141 {
00142 delete m_tree;
00143 m_tree = NULL;
00144 m_size = 0;
00145 }
00146 }
00147
00148
00158 template<class T, class Comp>
00159 template<class InputIterator>
00160 void claw::trie<T, Comp>::insert(InputIterator first, InputIterator last)
00161 {
00162 assert( first != last );
00163
00164 trie_node_ptr* p = &m_tree;
00165 trie_node_ptr last_node = NULL;
00166
00167
00168 while ( *p && (first!=last) )
00169 if ( s_value_equal_to((*p)->value, *first) )
00170 {
00171 last_node = *p;
00172 p = & (*p)->right;
00173 ++first;
00174 }
00175 else
00176 p = & (*p)->left;
00177
00178
00179
00180 while (first != last)
00181 {
00182 *p = new trie_node(*first);
00183 last_node = *p;
00184
00185 ++first;
00186 p = & (*p)->right;
00187 }
00188
00189 ++(last_node->count);
00190
00191
00192 ++m_size;
00193 }
00194
00195
00204 template<class T, class Comp>
00205 template <class InputIterator>
00206 unsigned int claw::trie<T, Comp>::count(InputIterator first,
00207 InputIterator last)
00208 {
00209 assert( first != last );
00210
00211 trie_node_ptr* p = & m_tree;
00212 trie_node_ptr last_node = NULL;
00213
00214
00215 while ( *p && (first!=last) )
00216 if ( s_value_equal_to((*p)->value, *first) )
00217 {
00218 last_node = *p;
00219 p = & (*p)->right;
00220 ++first;
00221 }
00222 else
00223 p = & (*p)->left;
00224
00225
00226 if (first==last)
00227 return last_node->count;
00228 else
00229 return 0;
00230 }