Claw  1.7.3
avl.tpp
Go to the documentation of this file.
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 */
30 #include <cassert>
31 
32 /*----------------------------------------------------------------------------*/
37 template<class K, class Comp>
39 {
40 
41 } // avl::avl() [constructor]
42 
43 /*----------------------------------------------------------------------------*/
48 template<class K, class Comp>
50  : m_tree(that.m_tree)
51 {
52 
53 } // avl::avl() [copy constructor]
54 
55 /*----------------------------------------------------------------------------*/
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 /*----------------------------------------------------------------------------*/
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 /*----------------------------------------------------------------------------*/
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 /*----------------------------------------------------------------------------*/
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 /*----------------------------------------------------------------------------*/
112 template<class K, class Comp>
114 {
115  m_tree.clear();
116 } // avl::clear()
117 
118 /*----------------------------------------------------------------------------*/
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 /*----------------------------------------------------------------------------*/
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 /*----------------------------------------------------------------------------*/
144 template<class K, class Comp>
147 {
148  return m_tree.begin();
149 } // avl::begin()
150 
151 /*----------------------------------------------------------------------------*/
155 template<class K, class Comp>
157 {
158  return m_tree.end();
159 } // avl::end()
160 
161 /*----------------------------------------------------------------------------*/
166 template<class K, class Comp>
168 claw::avl<K,Comp>::find( const K& key ) const
169 {
170  return m_tree.find(key);
171 } // avl::find()
172 
173 /*----------------------------------------------------------------------------*/
179 template<class K, class Comp>
182 {
183  return m_tree.find_nearest_greater(key);
184 } // avl::find_nearest_greater()
185 
186 /*----------------------------------------------------------------------------*/
192 template<class K, class Comp>
195 {
196  return m_tree.find_nearest_lower(key);
197 } // avl::find_nearest_lower()
198 
199 /*----------------------------------------------------------------------------*/
203 template<class K, class Comp>
206 {
207  return m_tree.lower_bound();
208 } // avl::lower_bound()
209 
210 /*----------------------------------------------------------------------------*/
214 template<class K, class Comp>
217 {
218  return m_tree.upper_bound();
219 } // avl::upper_bound()
220 
221 /*----------------------------------------------------------------------------*/
226 template<class K, class Comp>
228 {
229  m_tree = that.m_tree;
230  return *this;
231 } // avl::operator=()
232 
233 /*----------------------------------------------------------------------------*/
238 template<class K, class Comp>
240 {
241  return m_tree == that.m_tree;
242 } // avl::operator==()
243 
244 /*----------------------------------------------------------------------------*/
249 template<class K, class Comp>
251 {
252  return m_tree != that.m_tree;
253 } // avl::operator!=()
254 
255 /*----------------------------------------------------------------------------*/
260 template<class K, class Comp>
262 {
263  return m_tree < that.m_tree;
264 } // avl::operator<()
265 
266 /*----------------------------------------------------------------------------*/
271 template<class K, class Comp>
273 {
274  return m_tree > that.m_tree;
275 } // avl::operator>()
276 
277 /*----------------------------------------------------------------------------*/
282 template<class K, class Comp>
284 {
285  return m_tree <= that.m_tree;
286 } // avl::operator<=()
287 
288 /*----------------------------------------------------------------------------*/
293 template<class K, class Comp>
295 {
296  return m_tree >= that.m_tree;
297 } // avl::operator>=()
void insert(const K &key)
Add a value in a tree.
Definition: avl.tpp:75
unsigned int size() const
Get the size of a tree.
Definition: avl.tpp:124
bool operator<=(const avl< K, Comp > &that) const
Less or equal operator.
Definition: avl.tpp:283
const_iterator upper_bound() const
Get an iterator on the gratest value of the tree.
Definition: avl.tpp:216
bool operator!=(const avl< K, Comp > &that) const
Disequality.
Definition: avl.tpp:250
Binary search tree AVL implementation.
Definition: avl.hpp:43
const_iterator end() const
Get an iterator after the end of the tree.
Definition: avl.tpp:156
void erase(const K &key)
Delete a value in a tree.
Definition: avl.tpp:102
bool operator>(const avl< K, Comp > &that) const
Greater than operator.
Definition: avl.tpp:272
void clear()
Clear a tree.
Definition: avl.tpp:113
bool empty() const
Tell if a tree is empty or not.
Definition: avl.tpp:135
Fuction object to get the first element of a std::pair.
Definition: functional.hpp:44
bool operator==(const avl< K, Comp > &that) const
Equality.
Definition: avl.tpp:239
bool operator<(const avl< K, Comp > &that) const
Less than operator.
Definition: avl.tpp:261
bool operator>=(const avl< K, Comp > &that) const
Greater or equal operator.
Definition: avl.tpp:294
const_iterator find_nearest_greater(const K &key) const
Get an iterator on the nodes of the tree on the key imediatly after from a specified key...
Definition: avl.tpp:181
const_iterator find_nearest_lower(const K &key) const
Get an iterator on the nodes of the tree on the key imediatly before from a specified key...
Definition: avl.tpp:194
avl()
AVL constructor.
Definition: avl.tpp:38
const_iterator find(const K &key) const
Get an iterator on the nodes of the tree from a specified key.
Definition: avl.tpp:168
avl< K, Comp > & operator=(const avl< K, Comp > &that)
Assignment.
Definition: avl.tpp:227
const_iterator lower_bound() const
Get an iterator on the lowest value of the tree.
Definition: avl.tpp:205
const_iterator begin() const
Get an iterator on the nodes of the tree.
Definition: avl.tpp:146