Claw 1.7.3
avl_base.hpp
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#ifndef __CLAW_AVL_BASE_HPP__
31#define __CLAW_AVL_BASE_HPP__
32
33#include <iterator>
34#include <cstddef>
35
36#include <claw/binary_node.hpp>
37
38namespace claw
39{
40 //---------------------------------------------------------------------------
56 template < class K, class Comp = std::less<K> >
58 {
59 private:
60
61 //**************************** avl_node ***********************************
62
66 class avl_node:
67 public binary_node< typename claw::avl_base<K,Comp>::avl_node >
68 {
69 private:
72
73 public:
74 explicit avl_node( const K& k );
75 ~avl_node();
76
77 avl_node* duplicate( unsigned int& count ) const;
78
79 void del_tree();
80 unsigned int depth() const;
81
82 avl_node* find( const K& k );
83 const avl_node* find( const K& k ) const;
84
85 avl_node* find_nearest_greater( const K& key );
86 const avl_node* find_nearest_greater( const K& key ) const;
87
88 avl_node* find_nearest_lower( const K& key );
89 const avl_node* find_nearest_lower( const K& key ) const;
90
91 avl_node* lower_bound();
92 const avl_node* lower_bound() const;
93
94 avl_node* upper_bound();
95 const avl_node* upper_bound() const;
96
97 avl_node* prev();
98 const avl_node* prev() const;
99
100 avl_node* next();
101 const avl_node* next() const;
102
103 private:
104 explicit avl_node( const avl_node& that );
105
106 public:
108 K key;
109
115 char balance;
116
118 avl_node *father;
119
120 }; // class avl_node
121
122 private:
123 typedef avl_node* avl_node_ptr;
124 typedef avl_node const* const_avl_node_ptr;
125
126 public:
127 //*************************** avl::avl_iterator ***************************
128
133 {
134 public:
135 typedef K value_type;
136 typedef K& reference;
137 typedef K* const pointer;
138 typedef ptrdiff_t difference_type;
139
140 typedef std::bidirectional_iterator_tag iterator_category;
141
142 public:
143 avl_iterator();
144 avl_iterator( avl_node_ptr node, bool final );
145
146 avl_iterator& operator++();
147 avl_iterator operator++(int);
148 avl_iterator& operator--();
149 avl_iterator operator--(int);
150 reference operator*() const;
151 pointer operator->() const;
152 bool operator==(const avl_iterator& it) const;
153 bool operator!=(const avl_iterator& it) const;
154
155 private:
157 avl_node_ptr m_current;
158
160 bool m_is_final;
161
162 }; // class avl_iterator
163
168 {
169 public:
170 typedef K value_type;
171 typedef const K& reference;
172 typedef const K* const pointer;
173 typedef ptrdiff_t difference_type;
174
175 typedef std::bidirectional_iterator_tag iterator_category;
176
177 public:
179 avl_const_iterator( const_avl_node_ptr node, bool final );
180
181 avl_const_iterator& operator++();
182 avl_const_iterator operator++(int);
183 avl_const_iterator& operator--();
184 avl_const_iterator operator--(int);
185 reference operator*() const;
186 pointer operator->() const;
187 bool operator==(const avl_const_iterator& it) const;
188 bool operator!=(const avl_const_iterator& it) const;
189
190 private:
192 const_avl_node_ptr m_current;
193
195 bool m_is_final;
196
197 }; // class avl_const_iterator
198
199 public:
200 typedef K value_type;
201 typedef K key_type;
202 typedef K referent_type;
203 typedef Comp key_less;
204 typedef const K& const_reference;
205 typedef avl_iterator iterator;
207
208 public:
209 //**************************** avl_base (main) *****************************
210
211 avl_base();
212 explicit avl_base( const avl_base<K, Comp>& that );
213 ~avl_base();
214
215 void insert( const K& key );
216 template<typename Iterator>
217 void insert( Iterator first, Iterator last );
218
219 void erase( const K& key );
220 void clear();
221
222 inline unsigned int size() const;
223 inline bool empty() const;
224
225 iterator begin();
226 const_iterator begin() const;
227
228 iterator end();
229 const_iterator end() const;
230
231 iterator find( const K& key );
232 const_iterator find( const K& key ) const;
233
234 iterator find_nearest_greater( const K& key );
235 const_iterator find_nearest_greater( const K& key ) const;
236
237 iterator find_nearest_lower( const K& key );
238 const_iterator find_nearest_lower( const K& key ) const;
239
240 iterator lower_bound();
241 const_iterator lower_bound() const;
242
243 iterator upper_bound();
244 const_iterator upper_bound() const;
245
246 avl_base<K, Comp>& operator=( const avl_base<K, Comp>& that );
247 bool operator==( const avl_base<K, Comp>& that ) const;
248 bool operator!=( const avl_base<K, Comp>& that ) const;
249 bool operator<( const avl_base<K, Comp>& that ) const;
250 bool operator>( const avl_base<K, Comp>& that ) const;
251 bool operator<=( const avl_base<K, Comp>& that ) const;
252 bool operator>=( const avl_base<K, Comp>& that ) const;
253
254 void swap( avl_base<K, Comp>& that );
255
256 private:
257 //-------------------------------------------------------------------------
258 // We need some methods to check the validity of our trees
259
260 bool check_in_bounds( const avl_node_ptr node, const K& min,
261 const K& max ) const;
262 bool check_balance( const avl_node_ptr node ) const;
263 bool correct_descendant( const avl_node_ptr node ) const;
264 bool validity_check() const;
265
266 private:
267 iterator make_iterator( avl_node_ptr node ) const;
268 const_iterator make_const_iterator( const_avl_node_ptr node ) const;
269
270 //-------------------------------------------------------------------------
271 // Tree management methods
272
273 void rotate_right( avl_node_ptr& node );
274 void rotate_left( avl_node_ptr& node );
275 void rotate_left_right( avl_node_ptr& node );
276 void rotate_right_left( avl_node_ptr& node );
277
278 void update_balance( avl_node_ptr node, const K& key );
279 void adjust_balance( avl_node_ptr& node );
280 void adjust_balance_left( avl_node_ptr& node );
281 void adjust_balance_right( avl_node_ptr& node );
282
283
284 //-------------------------------------------------------------------------
285 // Methods for insertion
286 //-------------------------------------------------------------------------
287
288
289 void insert_node( const K& key );
290 avl_node_ptr* find_node_reference( const K& key,
291 avl_node_ptr& last_imbalanced,
292 avl_node_ptr& node_father);
293
294
295 //-------------------------------------------------------------------------
296 // Methods for deletion
297 //-------------------------------------------------------------------------
298
299
300 bool recursive_delete( avl_node_ptr& node, const K& key );
301 bool new_balance( avl_node_ptr& node, int imbalance );
302 bool recursive_delete_node( avl_node_ptr& node );
303 int recursive_delete_max( avl_node_ptr& root, avl_node_ptr node );
304
305 public:
307 static key_less s_key_less;
308
309 private:
311 unsigned int m_size;
312
314 avl_node_ptr m_tree;
315
316 }; // class avl_base
317} // namespace claw
318
319#include <claw/impl/avl_base.tpp>
320
321#endif // __CLAW_AVL_HPP__
Basic binary node.
Binary search tree base AVL implementation.
Definition avl_base.hpp:58
static key_less s_key_less
Function object used to compare keys.
Definition avl_base.hpp:307
Basic binary node.
Fuction object to get the first element of a std::pair.
This is the main namespace.
Definition algorithm.hpp:34