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 | |||
) | [inline] |
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_base< K, Comp >::insert(), and claw::avl< K, Comp >::m_tree.
claw::avl< K, Comp >::const_iterator claw::avl< K, Comp >::begin | ( | ) | const [inline] |
Get an iterator on the nodes of the tree.
Definition at line 146 of file avl.tpp.
References claw::avl_base< K, Comp >::begin(), and claw::avl< K, Comp >::m_tree.
Referenced by claw::math::ordered_set< K, Comp >::contains(), claw::math::ordered_set< K, Comp >::difference(), claw::arguments_table::help(), claw::math::ordered_set< K, Comp >::intersection(), claw::math::ordered_set< K, Comp >::join(), claw::arguments_table::parse(), claw::automaton< State, Edge, StateComp, EdgeComp >::reachables(), and claw::arguments_table::required_fields_are_set().
void claw::avl< K, Comp >::clear | ( | ) | [inline] |
Clear a tree.
Definition at line 113 of file avl.tpp.
References claw::avl_base< K, Comp >::clear(), and claw::avl< K, Comp >::m_tree.
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_base< K, Comp >::empty(), and claw::avl< K, Comp >::m_tree.
claw::avl< K, Comp >::const_iterator claw::avl< K, Comp >::end | ( | ) | const [inline] |
Get an iterator after the end of the tree.
Definition at line 156 of file avl.tpp.
References claw::avl_base< K, Comp >::end(), and claw::avl< K, Comp >::m_tree.
Referenced by claw::math::ordered_set< K, Comp >::contains(), claw::math::ordered_set< K, Comp >::difference(), claw::arguments::get_bool(), claw::arguments_table::help(), claw::math::ordered_set< K, Comp >::intersection(), claw::math::ordered_set< K, Comp >::join(), claw::arguments_table::parse(), claw::arguments::parse(), claw::arguments::process_boolean(), claw::automaton< State, Edge, StateComp, EdgeComp >::reachables(), and claw::arguments_table::required_fields_are_set().
void claw::avl< K, Comp >::erase | ( | const K & | key | ) | [inline] |
Delete a value in a tree.
key | Node key. |
Definition at line 102 of file avl.tpp.
References claw::avl_base< K, Comp >::erase(), and claw::avl< K, Comp >::m_tree.
Referenced by claw::math::ordered_set< K, Comp >::difference(), and claw::math::ordered_set< K, Comp >::intersection().
claw::avl< K, Comp >::const_iterator claw::avl< K, Comp >::find | ( | const K & | key | ) | const [inline] |
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_base< K, Comp >::find(), and claw::avl< K, Comp >::m_tree.
Referenced by claw::math::ordered_set< K, Comp >::difference(), claw::arguments::get_bool(), 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 [inline] |
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_base< K, Comp >::find_nearest_greater(), and claw::avl< K, Comp >::m_tree.
00182 { 00183 return m_tree.find_nearest_greater(key); 00184 } // avl::find_nearest_greater()
claw::avl< K, Comp >::const_iterator claw::avl< K, Comp >::find_nearest_lower | ( | const K & | key | ) | const [inline] |
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_base< K, Comp >::find_nearest_lower(), and claw::avl< K, Comp >::m_tree.
00195 { 00196 return m_tree.find_nearest_lower(key); 00197 } // avl::find_nearest_lower()
void claw::avl< K, Comp >::insert | ( | InputIterator | first, | |
InputIterator | last | |||
) | [inline] |
Add a range of items in the tree.
Definition at line 90 of file avl.tpp.
References claw::avl_base< K, Comp >::insert(), and claw::avl< K, Comp >::m_tree.
void claw::avl< K, Comp >::insert | ( | const K & | key | ) | [inline] |
Add a value in a tree.
key | Node key. |
Definition at line 75 of file avl.tpp.
References claw::avl_base< K, Comp >::insert(), and claw::avl< K, Comp >::m_tree.
Referenced by claw::arguments_table::add(), claw::arguments::add_argument(), claw::arguments_table::add_long(), claw::arguments_table::add_short(), claw::math::ordered_set< K, Comp >::join(), 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 [inline] |
Get an iterator on the lowest value of the tree.
Definition at line 205 of file avl.tpp.
References claw::avl_base< K, Comp >::lower_bound(), and claw::avl< K, Comp >::m_tree.
00206 { 00207 return m_tree.lower_bound(); 00208 } // avl::lower_bound()
bool claw::avl< K, Comp >::operator!= | ( | const avl< K, Comp > & | that | ) | const [inline] |
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 [inline] |
Less than operator.
that | The instance to compare to. |
Reimplemented in claw::math::ordered_set< K, Comp >.
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 [inline] |
Less or equal operator.
that | The instance to compare to. |
Reimplemented in claw::math::ordered_set< K, Comp >.
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 | ) | [inline] |
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 [inline] |
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 [inline] |
Greater than operator.
that | The instance to compare to. |
Reimplemented in claw::math::ordered_set< K, Comp >.
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 [inline] |
Greater or equal operator.
that | The instance to compare to. |
Reimplemented in claw::math::ordered_set< K, Comp >.
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 >::m_tree, and claw::avl_base< K, Comp >::size().
Referenced by claw::math::ordered_set< K, Comp >::contains(), claw::automaton< State, Edge, StateComp, EdgeComp >::reachables(), and claw::math::ordered_set< K, Comp >::strictly_contains().
claw::avl< K, Comp >::const_iterator claw::avl< K, Comp >::upper_bound | ( | ) | const [inline] |
Get an iterator on the gratest value of the tree.
Definition at line 216 of file avl.tpp.
References claw::avl< K, Comp >::m_tree, and claw::avl_base< K, Comp >::upper_bound().
00217 { 00218 return m_tree.upper_bound(); 00219 } // avl::upper_bound()
Implementation.
Definition at line 90 of file avl.hpp.
Referenced by claw::avl< K, Comp >::avl(), claw::avl< K, Comp >::begin(), claw::avl< K, Comp >::clear(), claw::avl< K, Comp >::empty(), claw::avl< K, Comp >::end(), claw::avl< K, Comp >::erase(), claw::avl< K, Comp >::find(), claw::avl< K, Comp >::find_nearest_greater(), claw::avl< K, Comp >::find_nearest_lower(), claw::avl< K, Comp >::insert(), claw::avl< K, Comp >::lower_bound(), 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>(), claw::avl< K, Comp >::operator>=(), claw::avl< K, Comp >::size(), and claw::avl< K, Comp >::upper_bound().