Claw 1.7.3
trie.tpp
1/*
2 CLAW - a C++ Library Absolutely Wonderful
3
4 CLAW is a free library without any particular aim but being useful to
5 anyone.
6
7 Copyright (C) 2005-2011 Julien Jorge
8
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.
13
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.
18
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
22
23 contact: julien.jorge@gamned.org
24*/
25/**
26 * \file trie.tpp
27 * \brief Implementation of the trie structure.
28 * \author Julien Jorge
29 */
30#include <iostream>
31#include <cassert>
32
33//*************************** trie::trie_node *********************************
34
35
36/*---------------------------------------------------------------------------*/
37/**
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)
42 */
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),
47 count(0)
48{
49
50} // trie_node() [constructor]
51
52/*---------------------------------------------------------------------------*/
53/**
54 * \brief Trie node copy constructor.
55 * \param that Node to copy from.
56 */
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)
61{
62
63} // trie_node [copy constructor]
64
65//********************************* trie **************************************
66
67/*---------------------------------------------------------------------------*/
68template<class T, class Comp>
69typename claw::trie<T, Comp>::value_equal_to
70claw::trie<T, Comp>::s_value_equal_to;
71
72/*---------------------------------------------------------------------------*/
73/**
74 * \brief Trie constructor.
75 * \post empty()
76 */
77template<class T, class Comp>
78claw::trie<T, Comp>::trie()
79{
80 m_size = 0;
81 m_tree = NULL;
82
83 assert(empty());
84} // trie() [constructor]
85
86/*---------------------------------------------------------------------------*/
87/*
88 * \brief Trie copy constructor.
89 */
90template<class T, class Comp>
91claw::trie<T, Comp>::trie( const claw::trie<T, Comp>& that )
92{
93 if (that.m_tree)
94 m_tree = new trie_node( *that.m_tree );
95 else
96 m_tree = NULL;
97
98 m_size = that.m_size;
99} // trie() [copy constructor]
100
101/*---------------------------------------------------------------------------*/
102/**
103 * \brief Trie destructor.
104 */
105template<class T, class Comp>
106claw::trie<T, Comp>::~trie()
107{
108 if (m_tree)
109 delete m_tree;
110} // ~trie() [destructor]
111
112/*---------------------------------------------------------------------------*/
113/**
114 * \brief Gets size (words count) of the structure.
115 */
116template<class T, class Comp>
117unsigned int claw::trie<T, Comp>::size() const
118{
119 return m_size;
120} // size()
121
122/*---------------------------------------------------------------------------*/
123/**
124 * \brief Tell if the structure is empty or not.
125 */
126template<class T, class Comp>
127bool claw::trie<T, Comp>::empty() const
128{
129 return m_tree==NULL;
130} // empty()
131
132/*---------------------------------------------------------------------------*/
133/**
134 * \brief Clear the trie.
135 * \post this->empty() == true
136 */
137template<class T, class Comp>
138void claw::trie<T, Comp>::clear()
139{
140 if (m_tree)
141 {
142 delete m_tree;
143 m_tree = NULL;
144 m_size = 0;
145 }
146} // clear()
147
148/*---------------------------------------------------------------------------*/
149/**
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.
155 * \pre first != last
156 * \post !empty() && count(first, last) == old(count(first, last)) + 1
157 */
158template<class T, class Comp>
159template<class InputIterator>
160void claw::trie<T, Comp>::insert(InputIterator first, InputIterator last)
161{
162 assert( first != last );
163
164 trie_node_ptr* p = &m_tree; // for tree search
165 trie_node_ptr last_node = NULL; // last node of the inserted word
166
167 // Try to insert a maximum of items
168 while ( *p && (first!=last) )
169 if ( s_value_equal_to((*p)->value, *first) )
170 {
171 last_node = *p;
172 p = & (*p)->right;
173 ++first;
174 }
175 else
176 p = & (*p)->left;
177
178 // If we haven't inserted the full word,
179 // create the whole subtree.
180 while (first != last)
181 {
182 *p = new trie_node(*first);
183 last_node = *p;
184
185 ++first;
186 p = & (*p)->right;
187 }
188
189 ++(last_node->count);
190
191 // Don't forget to increase words count.
192 ++m_size;
193} // insert()
194
195/*---------------------------------------------------------------------------*/
196/**
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.
202 * \pre first != last
203 */
204template<class T, class Comp>
205template <class InputIterator>
206unsigned int claw::trie<T, Comp>::count(InputIterator first,
207 InputIterator last)
208{
209 assert( first != last );
210
211 trie_node_ptr* p = & m_tree; // for tree search
212 trie_node_ptr last_node = NULL; // last node of the word
213
214 // Try to find the word
215 while ( *p && (first!=last) )
216 if ( s_value_equal_to((*p)->value, *first) )
217 {
218 last_node = *p;
219 p = & (*p)->right;
220 ++first;
221 }
222 else
223 p = & (*p)->left;
224
225 // found ?
226 if (first==last)
227 return last_node->count;
228 else
229 return 0;
230} // count()