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 }