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  */
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),
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  */
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)
61 {
62 
63 } // trie_node [copy constructor]
64 
65 //********************************* trie **************************************
66 
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;
71 
72 /*---------------------------------------------------------------------------*/
73 /**
74  * \brief Trie constructor.
75  * \post empty()
76  */
77 template<class T, class Comp>
78 claw::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  */
90 template<class T, class Comp>
91 claw::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  */
105 template<class T, class Comp>
106 claw::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  */
116 template<class T, class Comp>
117 unsigned 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  */
126 template<class T, class Comp>
127 bool 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  */
137 template<class T, class Comp>
138 void 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  */
158 template<class T, class Comp>
159 template<class InputIterator>
160 void 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  */
204 template<class T, class Comp>
205 template <class InputIterator>
206 unsigned 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()