claw 1.9.0
 
Loading...
Searching...
No Matches
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@stuff-o-matic.com
24*/
30#ifndef __CLAW_AVL_BASE_HPP__
31#define __CLAW_AVL_BASE_HPP__
32
33#include <cstddef>
34#include <iterator>
35
36#include <claw/binary_node.hpp>
37
38namespace claw
39{
40 //---------------------------------------------------------------------------
56 template <class K, class Comp = std::less<K> >
57 class avl_base
58 {
59 private:
60 //**************************** avl_node ***********************************
61
65 class avl_node
66 : public binary_node<typename claw::avl_base<K, Comp>::avl_node>
67 {
68 private:
71
72 public:
73 explicit avl_node(const K& k);
74 ~avl_node();
75
76 avl_node* duplicate(unsigned int& count) const;
77
78 void del_tree();
79 unsigned int depth() const;
80
81 avl_node* find(const K& k);
82 const avl_node* find(const K& k) const;
83
84 avl_node* find_nearest_greater(const K& key);
85 const avl_node* find_nearest_greater(const K& key) const;
86
87 avl_node* find_nearest_lower(const K& key);
88 const avl_node* find_nearest_lower(const K& key) const;
89
90 avl_node* lower_bound();
91 const avl_node* lower_bound() const;
92
93 avl_node* upper_bound();
94 const avl_node* upper_bound() const;
95
96 avl_node* prev();
97 const avl_node* prev() const;
98
99 avl_node* next();
100 const avl_node* next() const;
101
102 private:
103 explicit avl_node(const avl_node& that);
104
105 public:
107 K key;
108
114 signed char balance;
115
117 avl_node* father;
118
119 }; // class avl_node
120
121 private:
122 typedef avl_node* avl_node_ptr;
123 typedef avl_node const* const_avl_node_ptr;
124
125 public:
126 //*************************** avl::avl_iterator ***************************
127
131 class avl_iterator
132 {
133 public:
134 typedef K value_type;
135 typedef K& reference;
136 typedef K* const pointer;
137 typedef ptrdiff_t difference_type;
138
139 typedef std::bidirectional_iterator_tag iterator_category;
140
141 public:
142 avl_iterator();
143 avl_iterator(avl_node_ptr node, bool final);
144
145 avl_iterator& operator++();
146 avl_iterator operator++(int);
147 avl_iterator& operator--();
148 avl_iterator operator--(int);
149 reference operator*() const;
150 pointer operator->() const;
151 bool operator==(const avl_iterator& it) const;
152 bool operator!=(const avl_iterator& it) const;
153
154 private:
156 avl_node_ptr m_current;
157
159 bool m_is_final;
160
161 }; // class avl_iterator
162
166 class avl_const_iterator
167 {
168 public:
169 typedef K value_type;
170 typedef const K& reference;
171 typedef const K* const pointer;
172 typedef ptrdiff_t difference_type;
173
174 typedef std::bidirectional_iterator_tag iterator_category;
175
176 public:
177 avl_const_iterator();
178 avl_const_iterator(const_avl_node_ptr node, bool final);
179
180 avl_const_iterator& operator++();
181 avl_const_iterator operator++(int);
182 avl_const_iterator& operator--();
183 avl_const_iterator operator--(int);
184 reference operator*() const;
185 pointer operator->() const;
186 bool operator==(const avl_const_iterator& it) const;
187 bool operator!=(const avl_const_iterator& it) const;
188
189 private:
191 const_avl_node_ptr m_current;
192
194 bool m_is_final;
195
196 }; // class avl_const_iterator
197
198 public:
199 typedef K value_type;
200 typedef K key_type;
201 typedef K referent_type;
202 typedef Comp key_less;
203 typedef const K& const_reference;
204 typedef avl_iterator iterator;
205 typedef avl_const_iterator const_iterator;
206
207 public:
208 //**************************** avl_base (main)
209 //*****************************
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 // Methods for insertion
285 //-------------------------------------------------------------------------
286
287 void insert_node(const K& key);
288 avl_node_ptr* find_node_reference(const K& key,
289 avl_node_ptr& last_imbalanced,
290 avl_node_ptr& node_father);
291
292 //-------------------------------------------------------------------------
293 // Methods for deletion
294 //-------------------------------------------------------------------------
295
296 bool recursive_delete(avl_node_ptr& node, const K& key);
297 bool new_balance(avl_node_ptr& node, int imbalance);
298 bool recursive_delete_node(avl_node_ptr& node);
299 int recursive_delete_max(avl_node_ptr& root, avl_node_ptr node);
300
301 public:
303 static key_less s_key_less;
304
305 private:
307 unsigned int m_size;
308
310 avl_node_ptr m_tree;
311
312 }; // class avl_base
313}
314
315#include <claw/avl_base.tpp>
316
317#endif // __CLAW_AVL_HPP__
Basic binary node.
static key_less s_key_less
Definition avl_base.hpp:303
Basic binary node.
Fuction object to get the first element of a std::pair.
This is the main namespace.