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 The avl class implementation.
28 * \author Julien Jorge
32 /*----------------------------------------------------------------------------*/
34 * \brief AVL constructor.
37 template<class K, class Comp>
38 claw::avl<K,Comp>::avl()
41 } // avl::avl() [constructor]
43 /*----------------------------------------------------------------------------*/
45 * \brief AVL copy constructor.
46 * \param that AVL instance to copy from.
48 template<class K, class Comp>
49 claw::avl<K,Comp>::avl( const avl<K, Comp>& that )
53 } // avl::avl() [copy constructor]
55 /*----------------------------------------------------------------------------*/
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.
61 template<class K, class Comp>
62 template<typename InputIterator>
63 claw::avl<K,Comp>::avl( InputIterator first, InputIterator last )
65 m_tree.insert(first, last);
66 } // avl::avl() [constructor from range]
68 /*----------------------------------------------------------------------------*/
70 * \brief Add a value in a tree.
71 * \param key Node key.
74 template<class K, class Comp>
75 void claw::avl<K,Comp>::insert( const K& key )
80 /*----------------------------------------------------------------------------*/
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)
88 template<class K, class Comp>
89 template<typename InputIterator>
90 void claw::avl<K,Comp>::insert( InputIterator first, InputIterator last )
92 m_tree.insert(first, last);
95 /*----------------------------------------------------------------------------*/
97 * \brief Delete a value in a tree.
98 * \param key Node key.
99 * \post not exists(key)
101 template<class K, class Comp>
102 void claw::avl<K,Comp>::erase( const K& key )
107 /*----------------------------------------------------------------------------*/
109 * \brief Clear a tree.
112 template<class K, class Comp>
113 void claw::avl<K,Comp>::clear()
118 /*----------------------------------------------------------------------------*/
120 * \brief Get the size of a tree.
121 * \return The size of the tree.
123 template<class K, class Comp>
124 inline unsigned int claw::avl<K,Comp>::size() const
126 return m_tree.size();
129 /*----------------------------------------------------------------------------*/
131 * \brief Tell if a tree is empty or not.
132 * \return true if the tree is empty, false otherwise.
134 template<class K, class Comp>
135 inline bool claw::avl<K,Comp>::empty() const
137 return m_tree.empty();
140 /*----------------------------------------------------------------------------*/
142 * \brief Get an iterator on the nodes of the tree.
144 template<class K, class Comp>
145 typename claw::avl<K,Comp>::const_iterator
146 claw::avl<K,Comp>::begin() const
148 return m_tree.begin();
151 /*----------------------------------------------------------------------------*/
153 * \brief Get an iterator after the end of the tree.
155 template<class K, class Comp>
156 typename claw::avl<K,Comp>::const_iterator claw::avl<K,Comp>::end() const
161 /*----------------------------------------------------------------------------*/
163 * \brief Get an iterator on the nodes of the tree from a specified key.
164 * \param key Key to find.
166 template<class K, class Comp>
167 typename claw::avl<K,Comp>::const_iterator
168 claw::avl<K,Comp>::find( const K& key ) const
170 return m_tree.find(key);
173 /*----------------------------------------------------------------------------*/
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.
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
183 return m_tree.find_nearest_greater(key);
184 } // avl::find_nearest_greater()
186 /*----------------------------------------------------------------------------*/
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.
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
196 return m_tree.find_nearest_lower(key);
197 } // avl::find_nearest_lower()
199 /*----------------------------------------------------------------------------*/
201 * \brief Get an iterator on the lowest value of the tree.
203 template<class K, class Comp>
204 typename claw::avl<K,Comp>::const_iterator
205 claw::avl<K,Comp>::lower_bound() const
207 return m_tree.lower_bound();
208 } // avl::lower_bound()
210 /*----------------------------------------------------------------------------*/
212 * \brief Get an iterator on the gratest value of the tree.
214 template<class K, class Comp>
215 typename claw::avl<K,Comp>::const_iterator
216 claw::avl<K,Comp>::upper_bound() const
218 return m_tree.upper_bound();
219 } // avl::upper_bound()
221 /*----------------------------------------------------------------------------*/
224 * \param that The instance to copy from.
226 template<class K, class Comp>
227 claw::avl<K, Comp>& claw::avl<K,Comp>::operator=( const avl<K, Comp>& that )
229 m_tree = that.m_tree;
231 } // avl::operator=()
233 /*----------------------------------------------------------------------------*/
236 * \param that The instance to compare to.
238 template<class K, class Comp>
239 bool claw::avl<K,Comp>::operator==( const avl<K, Comp>& that ) const
241 return m_tree == that.m_tree;
242 } // avl::operator==()
244 /*----------------------------------------------------------------------------*/
246 * \brief Disequality.
247 * \param that The instance to compare to.
249 template<class K, class Comp>
250 bool claw::avl<K,Comp>::operator!=( const avl<K, Comp>& that ) const
252 return m_tree != that.m_tree;
253 } // avl::operator!=()
255 /*----------------------------------------------------------------------------*/
257 * \brief Less than operator.
258 * \param that The instance to compare to.
260 template<class K, class Comp>
261 bool claw::avl<K,Comp>::operator<( const avl<K, Comp>& that ) const
263 return m_tree < that.m_tree;
264 } // avl::operator<()
266 /*----------------------------------------------------------------------------*/
268 * \brief Greater than operator.
269 * \param that The instance to compare to.
271 template<class K, class Comp>
272 bool claw::avl<K,Comp>::operator>( const avl<K, Comp>& that ) const
274 return m_tree > that.m_tree;
275 } // avl::operator>()
277 /*----------------------------------------------------------------------------*/
279 * \brief Less or equal operator.
280 * \param that The instance to compare to.
282 template<class K, class Comp>
283 bool claw::avl<K,Comp>::operator<=( const avl<K, Comp>& that ) const
285 return m_tree <= that.m_tree;
286 } // avl::operator<=()
288 /*----------------------------------------------------------------------------*/
290 * \brief Greater or equal operator.
291 * \param that The instance to compare to.
293 template<class K, class Comp>
294 bool claw::avl<K,Comp>::operator>=( const avl<K, Comp>& that ) const
296 return m_tree >= that.m_tree;
297 } // avl::operator>=()