30 #ifndef __CLAW_AVL_BASE_HPP__
31 #define __CLAW_AVL_BASE_HPP__
56 template <
class K,
class Comp = std::less<K> >
67 public binary_node< typename claw::avl_base<K,Comp>::avl_node >
74 explicit avl_node(
const K& k );
77 avl_node* duplicate(
unsigned int& count )
const;
80 unsigned int depth()
const;
82 avl_node*
find(
const K& k );
83 const avl_node*
find(
const K& k )
const;
98 const avl_node* prev()
const;
101 const avl_node* next()
const;
104 explicit avl_node(
const avl_node& that );
123 typedef avl_node* avl_node_ptr;
124 typedef avl_node
const* const_avl_node_ptr;
135 typedef K value_type;
136 typedef K& reference;
137 typedef K*
const pointer;
138 typedef ptrdiff_t difference_type;
140 typedef std::bidirectional_iterator_tag iterator_category;
157 avl_node_ptr m_current;
170 typedef K value_type;
171 typedef const K& reference;
172 typedef const K*
const pointer;
173 typedef ptrdiff_t difference_type;
175 typedef std::bidirectional_iterator_tag iterator_category;
192 const_avl_node_ptr m_current;
200 typedef K value_type;
202 typedef K referent_type;
203 typedef Comp key_less;
204 typedef const K& const_reference;
215 void insert(
const K& key );
216 template<
typename Iterator>
219 void erase(
const K& key );
222 inline unsigned int size()
const;
223 inline bool empty()
const;
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,
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;
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 );
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);
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 );
319 #include <claw/impl/avl_base.tpp>
321 #endif // __CLAW_AVL_HPP__
void insert(const K &key)
Add a value in a tree.
bool operator>(const avl_base< K, Comp > &that) const
Greater than operator.
avl_iterator & operator--()
Predecrement.
bool operator!=(const avl_iterator &it) const
Difference.
bool operator>=(const avl_base< K, Comp > &that) const
Greater or equal operator.
reference operator*() const
Dereference.
iterator begin()
Get an iterator on the nodes of the tree.
iterator find_nearest_greater(const K &key)
Get an iterator on the nodes of the tree on the key imediatly after from a specified key...
reference operator*() const
Dereference.
bool operator==(const avl_base< K, Comp > &that) const
Equality.
avl_const_iterator & operator--()
Predecrement.
Binary search tree base AVL implementation.
unsigned int size() const
Get the size of a tree.
bool operator==(const avl_iterator &it) const
Equality.
pointer operator->() const
Reference.
avl_base< K, Comp > & operator=(const avl_base< K, Comp > &that)
Assignment operator.
bool operator!=(const avl_const_iterator &it) const
Difference.
bool empty() const
Tell if a tree is empty or not.
Fuction object to get the first element of a std::pair.
void erase(const K &key)
Delete a value in a tree.
pointer operator->() const
Reference.
static key_less s_key_less
Function object used to compare keys.
avl_const_iterator & operator++()
Preincrement.
iterator end()
Get an iterator after the end of the tree.
avl_iterator & operator++()
Preincrement.
~avl_base()
AVL destructor.
bool operator==(const avl_const_iterator &it) const
Equality.
iterator upper_bound()
Get an iterator on the gratest value of the tree.
void swap(avl_base< K, Comp > &that)
Swap the values with an other tree.
bool operator!=(const avl_base< K, Comp > &that) const
Disequality.
iterator find(const K &key)
Get an iterator on the nodes of the tree from a specified key.
iterator find_nearest_lower(const K &key)
Get an iterator on the nodes of the tree on the key imediatly before from a specified key...
avl_const_iterator()
Constructor.
iterator lower_bound()
Get an iterator on the lowest value of the tree.
avl_iterator()
Constructor.
avl_base()
AVL constructor.
void clear()
Clear a tree.