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;
143 avl_iterator(avl_node_ptr node,
bool final);
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;
156 avl_node_ptr m_current;
166 class avl_const_iterator
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;
177 avl_const_iterator();
178 avl_const_iterator(const_avl_node_ptr node,
bool final);
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;
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;
212 explicit avl_base(
const avl_base<K, Comp>& that);
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;
226 const_iterator begin()
const;
229 const_iterator end()
const;
231 iterator find(
const K& key);
232 const_iterator find(
const K& key)
const;
234 iterator find_nearest_greater(
const K& key);
235 const_iterator find_nearest_greater(
const K& key)
const;
237 iterator find_nearest_lower(
const K& key);
238 const_iterator find_nearest_lower(
const K& key)
const;
240 iterator lower_bound();
241 const_iterator lower_bound()
const;
243 iterator upper_bound();
244 const_iterator upper_bound()
const;
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;
254 void swap(avl_base<K, Comp>& that);
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);