2 CLAW - a C++ Library Absolutely Wonderful
4 CLAW is a free library without any particular aim but being useful to
7 Copyright (C) 2005-2011 Julien Jorge
9 This library is free software; you can redistribute it and/or
10 modify it under the terms of the GNU Lesser General Public
11 License as published by the Free Software Foundation; either
12 version 2.1 of the License, or (at your option) any later version.
14 This library is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 Lesser General Public License for more details.
19 You should have received a copy of the GNU Lesser General Public
20 License along with this library; if not, write to the Free Software
21 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
23 contact: julien.jorge@gamned.org
27 * \brief Implementation of the trie structure.
28 * \author Julien Jorge
33 //*************************** trie::trie_node *********************************
36 /*---------------------------------------------------------------------------*/
38 * \brief Trie node constructor.
39 * \param val Value of the node.
40 * \param c Count for the node.
41 * \post (value==val) && (count==c)
43 template<class T, class Comp>
44 claw::trie<T, Comp>::trie_node::trie_node( const T& val,
45 unsigned int c /*= 0*/ )
46 : claw::binary_node< typename claw::trie<T, Comp>::trie_node >(), value(val),
50 } // trie_node() [constructor]
52 /*---------------------------------------------------------------------------*/
54 * \brief Trie node copy constructor.
55 * \param that Node to copy from.
57 template<class T, class Comp>
58 claw::trie<T, Comp>::trie_node::trie_node( const trie_node& that )
59 : claw::binary_node< typename claw::trie<T, Comp>::trie_node >(that),
60 value(that.value), count(that.count)
63 } // trie_node [copy constructor]
65 //********************************* trie **************************************
67 /*---------------------------------------------------------------------------*/
68 template<class T, class Comp>
69 typename claw::trie<T, Comp>::value_equal_to
70 claw::trie<T, Comp>::s_value_equal_to;
72 /*---------------------------------------------------------------------------*/
74 * \brief Trie constructor.
77 template<class T, class Comp>
78 claw::trie<T, Comp>::trie()
84 } // trie() [constructor]
86 /*---------------------------------------------------------------------------*/
88 * \brief Trie copy constructor.
90 template<class T, class Comp>
91 claw::trie<T, Comp>::trie( const claw::trie<T, Comp>& that )
94 m_tree = new trie_node( *that.m_tree );
99 } // trie() [copy constructor]
101 /*---------------------------------------------------------------------------*/
103 * \brief Trie destructor.
105 template<class T, class Comp>
106 claw::trie<T, Comp>::~trie()
110 } // ~trie() [destructor]
112 /*---------------------------------------------------------------------------*/
114 * \brief Gets size (words count) of the structure.
116 template<class T, class Comp>
117 unsigned int claw::trie<T, Comp>::size() const
122 /*---------------------------------------------------------------------------*/
124 * \brief Tell if the structure is empty or not.
126 template<class T, class Comp>
127 bool claw::trie<T, Comp>::empty() const
132 /*---------------------------------------------------------------------------*/
134 * \brief Clear the trie.
135 * \post this->empty() == true
137 template<class T, class Comp>
138 void claw::trie<T, Comp>::clear()
148 /*---------------------------------------------------------------------------*/
150 * \brief Add a word to the structure.
151 * \remark Type requirements :
152 * - *InputIterator is T.
153 * \param first First item of the word.
154 * \param last Item just after the last to add.
156 * \post !empty() && count(first, last) == old(count(first, last)) + 1
158 template<class T, class Comp>
159 template<class InputIterator>
160 void claw::trie<T, Comp>::insert(InputIterator first, InputIterator last)
162 assert( first != last );
164 trie_node_ptr* p = &m_tree; // for tree search
165 trie_node_ptr last_node = NULL; // last node of the inserted word
167 // Try to insert a maximum of items
168 while ( *p && (first!=last) )
169 if ( s_value_equal_to((*p)->value, *first) )
178 // If we haven't inserted the full word,
179 // create the whole subtree.
180 while (first != last)
182 *p = new trie_node(*first);
189 ++(last_node->count);
191 // Don't forget to increase words count.
195 /*---------------------------------------------------------------------------*/
197 * \brief Gets a word count.
198 * \remark Type requirements :
199 * - *InputIterator is T.
200 * \param first First item of the word.
201 * \param last Item just after the last to find.
204 template<class T, class Comp>
205 template <class InputIterator>
206 unsigned int claw::trie<T, Comp>::count(InputIterator first,
209 assert( first != last );
211 trie_node_ptr* p = & m_tree; // for tree search
212 trie_node_ptr last_node = NULL; // last node of the word
214 // Try to find the word
215 while ( *p && (first!=last) )
216 if ( s_value_equal_to((*p)->value, *first) )
227 return last_node->count;