Binary search tree AVL implementation. More...
#include <avl.hpp>
Public Types | |
typedef K | value_type |
typedef K | key_type |
typedef K | referent_type |
typedef Comp | key_less |
typedef const K & | const_reference |
typedef impl_type::avl_const_iterator | const_iterator |
Public Member Functions | |
avl () | |
AVL constructor. | |
avl (const avl< K, Comp > &that) | |
AVL copy constructor. | |
template<typename InputIterator > | |
avl (InputIterator first, InputIterator last) | |
Constructor from a range. | |
void | insert (const K &key) |
Add a value in a tree. | |
template<typename InputIterator > | |
void | insert (InputIterator first, InputIterator last) |
Add a range of items in the tree. | |
void | erase (const K &key) |
Delete a value in a tree. | |
void | clear () |
Clear a tree. | |
unsigned int | size () const |
Get the size of a tree. | |
bool | empty () const |
Tell if a tree is empty or not. | |
const_iterator | begin () const |
Get an iterator on the nodes of the tree. | |
const_iterator | end () const |
Get an iterator after the end of the tree. | |
const_iterator | find (const K &key) const |
Get an iterator on the nodes of the tree from a specified key. | |
const_iterator | find_nearest_greater (const K &key) const |
Get an iterator on the nodes of the tree on the key imediatly after from a specified key. | |
const_iterator | find_nearest_lower (const K &key) const |
Get an iterator on the nodes of the tree on the key imediatly before from a specified key. | |
const_iterator | lower_bound () const |
Get an iterator on the lowest value of the tree. | |
const_iterator | upper_bound () const |
Get an iterator on the gratest value of the tree. | |
avl< K, Comp > & | operator= (const avl< K, Comp > &that) |
Assignment. | |
bool | operator== (const avl< K, Comp > &that) const |
Equality. | |
bool | operator!= (const avl< K, Comp > &that) const |
Disequality. | |
bool | operator< (const avl< K, Comp > &that) const |
Less than operator. | |
bool | operator> (const avl< K, Comp > &that) const |
Greater than operator. | |
bool | operator<= (const avl< K, Comp > &that) const |
Less or equal operator. | |
bool | operator>= (const avl< K, Comp > &that) const |
Greater or equal operator. | |
Private Types | |
typedef avl_base< K, Comp > | impl_type |
Private Attributes | |
impl_type | m_tree |
Implementation. |
Binary search tree AVL implementation.
Definition at line 43 of file avl.hpp.
typedef impl_type::avl_const_iterator claw::avl< K, Comp >::const_iterator |
typedef const K& claw::avl< K, Comp >::const_reference |
typedef K claw::avl< K, Comp >::referent_type |
typedef K claw::avl< K, Comp >::value_type |
claw::avl< K, Comp >::avl | ( | InputIterator | first, |
InputIterator | last | ||
) |
Constructor from a range.
first | Iterator on the first element of the range. |
last | Iterator just past the last element of the range. |
Definition at line 63 of file avl.tpp.
References claw::avl< K, Comp >::insert().
claw::avl< K, Comp >::const_iterator claw::avl< K, Comp >::begin | ( | ) | const |
Get an iterator on the nodes of the tree.
Definition at line 146 of file avl.tpp.
References claw::avl< K, Comp >::begin().
Referenced by claw::avl< K, Comp >::begin(), claw::math::ordered_set< K, Comp >::contains(), claw::math::ordered_set< K, Comp >::join(), and claw::automaton< State, Edge, StateComp, EdgeComp >::reachables().
void claw::avl< K, Comp >::clear | ( | ) |
Clear a tree.
Definition at line 113 of file avl.tpp.
References claw::avl< K, Comp >::clear().
Referenced by claw::avl< K, Comp >::clear().
bool claw::avl< K, Comp >::empty | ( | ) | const [inline] |
Tell if a tree is empty or not.
Definition at line 135 of file avl.tpp.
References claw::avl< K, Comp >::empty().
Referenced by claw::avl< K, Comp >::empty().
claw::avl< K, Comp >::const_iterator claw::avl< K, Comp >::end | ( | ) | const |
Get an iterator after the end of the tree.
Definition at line 156 of file avl.tpp.
References claw::avl< K, Comp >::end().
Referenced by claw::math::ordered_set< K, Comp >::contains(), claw::math::ordered_set< K, Comp >::difference(), claw::avl< K, Comp >::end(), claw::math::ordered_set< K, Comp >::intersection(), claw::math::ordered_set< K, Comp >::join(), claw::arguments::parse(), claw::arguments::process_boolean(), and claw::automaton< State, Edge, StateComp, EdgeComp >::reachables().
void claw::avl< K, Comp >::erase | ( | const K & | key ) |
Delete a value in a tree.
key | Node key. |
Definition at line 102 of file avl.tpp.
References claw::avl< K, Comp >::erase().
Referenced by claw::avl< K, Comp >::erase().
claw::avl< K, Comp >::const_iterator claw::avl< K, Comp >::find | ( | const K & | key ) | const |
Get an iterator on the nodes of the tree from a specified key.
key | Key to find. |
Definition at line 168 of file avl.tpp.
References claw::avl< K, Comp >::find().
Referenced by claw::math::ordered_set< K, Comp >::difference(), claw::avl< K, Comp >::find(), claw::math::ordered_set< K, Comp >::intersection(), claw::arguments::parse(), and claw::arguments::process_boolean().
claw::avl< K, Comp >::const_iterator claw::avl< K, Comp >::find_nearest_greater | ( | const K & | key ) | const |
Get an iterator on the nodes of the tree on the key imediatly after from a specified key.
key | Key to find. |
Definition at line 181 of file avl.tpp.
References claw::avl< K, Comp >::find_nearest_greater().
Referenced by claw::avl< K, Comp >::find_nearest_greater().
{ return m_tree.find_nearest_greater(key); } // avl::find_nearest_greater()
claw::avl< K, Comp >::const_iterator claw::avl< K, Comp >::find_nearest_lower | ( | const K & | key ) | const |
Get an iterator on the nodes of the tree on the key imediatly before from a specified key.
key | Key to find. |
Definition at line 194 of file avl.tpp.
References claw::avl< K, Comp >::find_nearest_lower().
Referenced by claw::avl< K, Comp >::find_nearest_lower().
{ return m_tree.find_nearest_lower(key); } // avl::find_nearest_lower()
void claw::avl< K, Comp >::insert | ( | InputIterator | first, |
InputIterator | last | ||
) |
Add a range of items in the tree.
first | Iterator on the first item to add. |
last | Iterator past the last item to add. |
Definition at line 90 of file avl.tpp.
References claw::avl< K, Comp >::insert().
void claw::avl< K, Comp >::insert | ( | const K & | key ) |
Add a value in a tree.
key | Node key. |
Definition at line 75 of file avl.tpp.
References claw::avl< K, Comp >::insert().
Referenced by claw::avl< K, Comp >::avl(), claw::avl< K, Comp >::insert(), claw::arguments_table::parse(), and claw::automaton< State, Edge, StateComp, EdgeComp >::reachables().
claw::avl< K, Comp >::const_iterator claw::avl< K, Comp >::lower_bound | ( | ) | const |
Get an iterator on the lowest value of the tree.
Definition at line 205 of file avl.tpp.
References claw::avl< K, Comp >::lower_bound().
Referenced by claw::avl< K, Comp >::lower_bound().
{ return m_tree.lower_bound(); } // avl::lower_bound()
bool claw::avl< K, Comp >::operator!= | ( | const avl< K, Comp > & | that ) | const |
Disequality.
that | The instance to compare to. |
Definition at line 250 of file avl.tpp.
References claw::avl< K, Comp >::m_tree.
bool claw::avl< K, Comp >::operator< | ( | const avl< K, Comp > & | that ) | const |
Less than operator.
that | The instance to compare to. |
Definition at line 261 of file avl.tpp.
References claw::avl< K, Comp >::m_tree.
bool claw::avl< K, Comp >::operator<= | ( | const avl< K, Comp > & | that ) | const |
Less or equal operator.
that | The instance to compare to. |
Definition at line 283 of file avl.tpp.
References claw::avl< K, Comp >::m_tree.
claw::avl< K, Comp > & claw::avl< K, Comp >::operator= | ( | const avl< K, Comp > & | that ) |
Assignment.
that | The instance to copy from. |
Definition at line 227 of file avl.tpp.
References claw::avl< K, Comp >::m_tree.
bool claw::avl< K, Comp >::operator== | ( | const avl< K, Comp > & | that ) | const |
Equality.
that | The instance to compare to. |
Definition at line 239 of file avl.tpp.
References claw::avl< K, Comp >::m_tree.
bool claw::avl< K, Comp >::operator> | ( | const avl< K, Comp > & | that ) | const |
Greater than operator.
that | The instance to compare to. |
Definition at line 272 of file avl.tpp.
References claw::avl< K, Comp >::m_tree.
bool claw::avl< K, Comp >::operator>= | ( | const avl< K, Comp > & | that ) | const |
Greater or equal operator.
that | The instance to compare to. |
Definition at line 294 of file avl.tpp.
References claw::avl< K, Comp >::m_tree.
unsigned int claw::avl< K, Comp >::size | ( | ) | const [inline] |
Get the size of a tree.
Definition at line 124 of file avl.tpp.
References claw::avl< K, Comp >::size().
Referenced by claw::math::ordered_set< K, Comp >::contains(), claw::automaton< State, Edge, StateComp, EdgeComp >::reachables(), claw::avl< K, Comp >::size(), and claw::math::ordered_set< K, Comp >::strictly_contains().
claw::avl< K, Comp >::const_iterator claw::avl< K, Comp >::upper_bound | ( | ) | const |
Get an iterator on the gratest value of the tree.
Definition at line 216 of file avl.tpp.
References claw::avl< K, Comp >::upper_bound().
Referenced by claw::avl< K, Comp >::upper_bound().
{ return m_tree.upper_bound(); } // avl::upper_bound()
Implementation.
Definition at line 90 of file avl.hpp.
Referenced by claw::avl< K, Comp >::operator!=(), claw::avl< K, Comp >::operator<(), claw::avl< K, Comp >::operator<=(), claw::avl< K, Comp >::operator=(), claw::avl< K, Comp >::operator==(), claw::avl< K, Comp >::operator>(), and claw::avl< K, Comp >::operator>=().