claw  1.9.0
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 
38 namespace 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 
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 
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:
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;
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__
static key_less s_key_less
Function object used to compare keys.
Definition: avl_base.hpp:303
Binary search tree base AVL implementation.
Definition: avl_base.hpp:57
Fuction object to get the first element of a std::pair.
Definition: functional.hpp:42
Basic binary node.
Definition: binary_node.hpp:41
Basic binary node.
This is the main namespace.
Definition: application.hpp:49