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.
37template<class K, class Comp>
38claw::avl<K,Comp>::avl()
41} // avl::avl() [constructor]
43/*----------------------------------------------------------------------------*/
45 * \brief AVL copy constructor.
46 * \param that AVL instance to copy from.
48template<class K, class Comp>
49claw::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.
61template<class K, class Comp>
62template<typename InputIterator>
63claw::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.
74template<class K, class Comp>
75void 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)
88template<class K, class Comp>
89template<typename InputIterator>
90void 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)
101template<class K, class Comp>
102void claw::avl<K,Comp>::erase( const K& key )
107/*----------------------------------------------------------------------------*/
109 * \brief Clear a tree.
112template<class K, class Comp>
113void claw::avl<K,Comp>::clear()
118/*----------------------------------------------------------------------------*/
120 * \brief Get the size of a tree.
121 * \return The size of the tree.
123template<class K, class Comp>
124inline 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.
134template<class K, class Comp>
135inline bool claw::avl<K,Comp>::empty() const
137 return m_tree.empty();
140/*----------------------------------------------------------------------------*/
142 * \brief Get an iterator on the nodes of the tree.
144template<class K, class Comp>
145typename claw::avl<K,Comp>::const_iterator
146claw::avl<K,Comp>::begin() const
148 return m_tree.begin();
151/*----------------------------------------------------------------------------*/
153 * \brief Get an iterator after the end of the tree.
155template<class K, class Comp>
156typename 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.
166template<class K, class Comp>
167typename claw::avl<K,Comp>::const_iterator
168claw::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.
179template<class K, class Comp>
180typename claw::avl<K,Comp>::const_iterator
181claw::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.
192template<class K, class Comp>
193typename claw::avl<K,Comp>::const_iterator
194claw::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.
203template<class K, class Comp>
204typename claw::avl<K,Comp>::const_iterator
205claw::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.
214template<class K, class Comp>
215typename claw::avl<K,Comp>::const_iterator
216claw::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.
226template<class K, class Comp>
227claw::avl<K, Comp>& claw::avl<K,Comp>::operator=( const avl<K, Comp>& that )
229 m_tree = that.m_tree;
233/*----------------------------------------------------------------------------*/
236 * \param that The instance to compare to.
238template<class K, class Comp>
239bool 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.
249template<class K, class Comp>
250bool 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.
260template<class K, class Comp>
261bool claw::avl<K,Comp>::operator<( const avl<K, Comp>& that ) const
263 return m_tree < that.m_tree;
266/*----------------------------------------------------------------------------*/
268 * \brief Greater than operator.
269 * \param that The instance to compare to.
271template<class K, class Comp>
272bool claw::avl<K,Comp>::operator>( const avl<K, Comp>& that ) const
274 return m_tree > that.m_tree;
277/*----------------------------------------------------------------------------*/
279 * \brief Less or equal operator.
280 * \param that The instance to compare to.
282template<class K, class Comp>
283bool 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.
293template<class K, class Comp>
294bool claw::avl<K,Comp>::operator>=( const avl<K, Comp>& that ) const
296 return m_tree >= that.m_tree;
297} // avl::operator>=()