Claw  1.7.3
avl.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 avl.tpp
27  * \brief The avl class implementation.
28  * \author Julien Jorge
29  */
30 #include <cassert>
31 
32 /*----------------------------------------------------------------------------*/
33 /**
34  * \brief AVL constructor.
35  * \post empty()
36  */
37 template<class K, class Comp>
38 claw::avl<K,Comp>::avl()
39 {
40 
41 } // avl::avl() [constructor]
42 
43 /*----------------------------------------------------------------------------*/
44 /**
45  * \brief AVL copy constructor.
46  * \param that AVL instance to copy from.
47  */
48 template<class K, class Comp>
49 claw::avl<K,Comp>::avl( const avl<K, Comp>& that )
50  : m_tree(that.m_tree)
51 {
52 
53 } // avl::avl() [copy constructor]
54 
55 /*----------------------------------------------------------------------------*/
56 /**
57  * \brief Constructor from a range.
58  * \param first Iterator on the first element of the range.
59  * \param last Iterator just past the last element of the range.
60  */
61 template<class K, class Comp>
62 template<typename InputIterator>
63 claw::avl<K,Comp>::avl( InputIterator first, InputIterator last )
64 {
65  m_tree.insert(first, last);
66 } // avl::avl() [constructor from range]
67 
68 /*----------------------------------------------------------------------------*/
69 /**
70  * \brief Add a value in a tree.
71  * \param key Node key.
72  * \post exists(key)
73  */
74 template<class K, class Comp>
75 void claw::avl<K,Comp>::insert( const K& key )
76 {
77  m_tree.insert(key);
78 } // avl::insert()
79 
80 /*----------------------------------------------------------------------------*/
81 /**
82  * \brief Add a range of items in the tree.
83  * \param first Iterator on the first item to add.
84  * \param last Iterator past the last item to add.
85  * \pre Iterator::value_type is K
86  * \post exists( *it ) for all it in [first, last)
87  */
88 template<class K, class Comp>
89 template<typename InputIterator>
90 void claw::avl<K,Comp>::insert( InputIterator first, InputIterator last )
91 {
92  m_tree.insert(first, last);
93 } // avl::insert()
94 
95 /*----------------------------------------------------------------------------*/
96 /**
97  * \brief Delete a value in a tree.
98  * \param key Node key.
99  * \post not exists(key)
100  */
101 template<class K, class Comp>
102 void claw::avl<K,Comp>::erase( const K& key )
103 {
104  m_tree.erase(key);
105 } // avl::erase()
106 
107 /*----------------------------------------------------------------------------*/
108 /**
109  * \brief Clear a tree.
110  * \post empty()
111  */
112 template<class K, class Comp>
113 void claw::avl<K,Comp>::clear()
114 {
115  m_tree.clear();
116 } // avl::clear()
117 
118 /*----------------------------------------------------------------------------*/
119 /**
120  * \brief Get the size of a tree.
121  * \return The size of the tree.
122  */
123 template<class K, class Comp>
124 inline unsigned int claw::avl<K,Comp>::size() const
125 {
126  return m_tree.size();
127 } // avl::size()
128 
129 /*----------------------------------------------------------------------------*/
130 /**
131  * \brief Tell if a tree is empty or not.
132  * \return true if the tree is empty, false otherwise.
133  */
134 template<class K, class Comp>
135 inline bool claw::avl<K,Comp>::empty() const
136 {
137  return m_tree.empty();
138 } // avl::empty()
139 
140 /*----------------------------------------------------------------------------*/
141 /**
142  * \brief Get an iterator on the nodes of the tree.
143  */
144 template<class K, class Comp>
145 typename claw::avl<K,Comp>::const_iterator
146 claw::avl<K,Comp>::begin() const
147 {
148  return m_tree.begin();
149 } // avl::begin()
150 
151 /*----------------------------------------------------------------------------*/
152 /**
153  * \brief Get an iterator after the end of the tree.
154  */
155 template<class K, class Comp>
156 typename claw::avl<K,Comp>::const_iterator claw::avl<K,Comp>::end() const
157 {
158  return m_tree.end();
159 } // avl::end()
160 
161 /*----------------------------------------------------------------------------*/
162 /**
163  * \brief Get an iterator on the nodes of the tree from a specified key.
164  * \param key Key to find.
165  */
166 template<class K, class Comp>
167 typename claw::avl<K,Comp>::const_iterator
168 claw::avl<K,Comp>::find( const K& key ) const
169 {
170  return m_tree.find(key);
171 } // avl::find()
172 
173 /*----------------------------------------------------------------------------*/
174 /**
175  * \brief Get an iterator on the nodes of the tree on the key imediatly after
176  * from a specified key.
177  * \param key Key to find.
178  */
179 template<class K, class Comp>
180 typename claw::avl<K,Comp>::const_iterator
181 claw::avl<K,Comp>::find_nearest_greater( const K& key ) const
182 {
183  return m_tree.find_nearest_greater(key);
184 } // avl::find_nearest_greater()
185 
186 /*----------------------------------------------------------------------------*/
187 /**
188  * \brief Get an iterator on the nodes of the tree on the key imediatly before
189  * from a specified key.
190  * \param key Key to find.
191  */
192 template<class K, class Comp>
193 typename claw::avl<K,Comp>::const_iterator
194 claw::avl<K,Comp>::find_nearest_lower( const K& key ) const
195 {
196  return m_tree.find_nearest_lower(key);
197 } // avl::find_nearest_lower()
198 
199 /*----------------------------------------------------------------------------*/
200 /**
201  * \brief Get an iterator on the lowest value of the tree.
202  */
203 template<class K, class Comp>
204 typename claw::avl<K,Comp>::const_iterator
205 claw::avl<K,Comp>::lower_bound() const
206 {
207  return m_tree.lower_bound();
208 } // avl::lower_bound()
209 
210 /*----------------------------------------------------------------------------*/
211 /**
212  * \brief Get an iterator on the gratest value of the tree.
213  */
214 template<class K, class Comp>
215 typename claw::avl<K,Comp>::const_iterator
216 claw::avl<K,Comp>::upper_bound() const
217 {
218  return m_tree.upper_bound();
219 } // avl::upper_bound()
220 
221 /*----------------------------------------------------------------------------*/
222 /**
223  * \brief Assignment.
224  * \param that The instance to copy from.
225  */
226 template<class K, class Comp>
227 claw::avl<K, Comp>& claw::avl<K,Comp>::operator=( const avl<K, Comp>& that )
228 {
229  m_tree = that.m_tree;
230  return *this;
231 } // avl::operator=()
232 
233 /*----------------------------------------------------------------------------*/
234 /**
235  * \brief Equality.
236  * \param that The instance to compare to.
237  */
238 template<class K, class Comp>
239 bool claw::avl<K,Comp>::operator==( const avl<K, Comp>& that ) const
240 {
241  return m_tree == that.m_tree;
242 } // avl::operator==()
243 
244 /*----------------------------------------------------------------------------*/
245 /**
246  * \brief Disequality.
247  * \param that The instance to compare to.
248  */
249 template<class K, class Comp>
250 bool claw::avl<K,Comp>::operator!=( const avl<K, Comp>& that ) const
251 {
252  return m_tree != that.m_tree;
253 } // avl::operator!=()
254 
255 /*----------------------------------------------------------------------------*/
256 /**
257  * \brief Less than operator.
258  * \param that The instance to compare to.
259  */
260 template<class K, class Comp>
261 bool claw::avl<K,Comp>::operator<( const avl<K, Comp>& that ) const
262 {
263  return m_tree < that.m_tree;
264 } // avl::operator<()
265 
266 /*----------------------------------------------------------------------------*/
267 /**
268  * \brief Greater than operator.
269  * \param that The instance to compare to.
270  */
271 template<class K, class Comp>
272 bool claw::avl<K,Comp>::operator>( const avl<K, Comp>& that ) const
273 {
274  return m_tree > that.m_tree;
275 } // avl::operator>()
276 
277 /*----------------------------------------------------------------------------*/
278 /**
279  * \brief Less or equal operator.
280  * \param that The instance to compare to.
281  */
282 template<class K, class Comp>
283 bool claw::avl<K,Comp>::operator<=( const avl<K, Comp>& that ) const
284 {
285  return m_tree <= that.m_tree;
286 } // avl::operator<=()
287 
288 /*----------------------------------------------------------------------------*/
289 /**
290  * \brief Greater or equal operator.
291  * \param that The instance to compare to.
292  */
293 template<class K, class Comp>
294 bool claw::avl<K,Comp>::operator>=( const avl<K, Comp>& that ) const
295 {
296  return m_tree >= that.m_tree;
297 } // avl::operator>=()