30 #ifndef __CLAW_AVL_BASE_HPP__ 31 #define __CLAW_AVL_BASE_HPP__ 56 template <
class K,
class Comp = std::less<K> >
66 :
public binary_node<typename claw::avl_base<K, Comp>::avl_node>
73 explicit avl_node(
const K& k);
76 avl_node* duplicate(
unsigned int& count)
const;
79 unsigned int depth()
const;
81 avl_node* find(
const K& k);
82 const avl_node* find(
const K& k)
const;
84 avl_node* find_nearest_greater(
const K& key);
85 const avl_node* find_nearest_greater(
const K& key)
const;
87 avl_node* find_nearest_lower(
const K& key);
88 const avl_node* find_nearest_lower(
const K& key)
const;
90 avl_node* lower_bound();
91 const avl_node* lower_bound()
const;
93 avl_node* upper_bound();
94 const avl_node* upper_bound()
const;
97 const avl_node* prev()
const;
100 const avl_node* next()
const;
103 explicit avl_node(
const avl_node& that);
122 typedef avl_node* avl_node_ptr;
123 typedef avl_node
const* const_avl_node_ptr;
134 typedef K value_type;
135 typedef K& reference;
136 typedef K*
const pointer;
137 typedef ptrdiff_t difference_type;
139 typedef std::bidirectional_iterator_tag iterator_category;
149 reference operator*()
const;
150 pointer operator->()
const;
156 avl_node_ptr m_current;
169 typedef K value_type;
170 typedef const K& reference;
171 typedef const K*
const pointer;
172 typedef ptrdiff_t difference_type;
174 typedef std::bidirectional_iterator_tag iterator_category;
184 reference operator*()
const;
185 pointer operator->()
const;
191 const_avl_node_ptr m_current;
199 typedef K value_type;
201 typedef K referent_type;
202 typedef Comp key_less;
203 typedef const K& const_reference;
215 void insert(
const K& key);
216 template <
typename Iterator>
217 void insert(Iterator
first, Iterator last);
219 void erase(
const K& key);
222 inline unsigned int size()
const;
223 inline bool empty()
const;
234 iterator find_nearest_greater(
const K& key);
237 iterator find_nearest_lower(
const K& key);
249 bool operator<(const avl_base<K, Comp>& that)
const;
251 bool operator<=(const avl_base<K, Comp>& that)
const;
260 bool check_in_bounds(
const avl_node_ptr node,
const K& min,
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;
267 iterator make_iterator(avl_node_ptr node)
const;
268 const_iterator make_const_iterator(const_avl_node_ptr node)
const;
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);
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);
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);
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);
315 #include <claw/avl_base.tpp> 317 #endif // __CLAW_AVL_HPP__ static key_less s_key_less
Function object used to compare keys.
Binary search tree base AVL implementation.
Fuction object to get the first element of a std::pair.
This is the main namespace.