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)
43template<class T, class Comp>
44claw::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.
57template<class T, class Comp>
58claw::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/*---------------------------------------------------------------------------*/
68template<class T, class Comp>
69typename claw::trie<T, Comp>::value_equal_to
70claw::trie<T, Comp>::s_value_equal_to;
72/*---------------------------------------------------------------------------*/
74 * \brief Trie constructor.
77template<class T, class Comp>
78claw::trie<T, Comp>::trie()
84} // trie() [constructor]
86/*---------------------------------------------------------------------------*/
88 * \brief Trie copy constructor.
90template<class T, class Comp>
91claw::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.
105template<class T, class Comp>
106claw::trie<T, Comp>::~trie()
110} // ~trie() [destructor]
112/*---------------------------------------------------------------------------*/
114 * \brief Gets size (words count) of the structure.
116template<class T, class Comp>
117unsigned int claw::trie<T, Comp>::size() const
122/*---------------------------------------------------------------------------*/
124 * \brief Tell if the structure is empty or not.
126template<class T, class Comp>
127bool claw::trie<T, Comp>::empty() const
132/*---------------------------------------------------------------------------*/
134 * \brief Clear the trie.
135 * \post this->empty() == true
137template<class T, class Comp>
138void 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
158template<class T, class Comp>
159template<class InputIterator>
160void 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.
204template<class T, class Comp>
205template <class InputIterator>
206unsigned 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;