Claw
1.7.3
|
Binary search tree AVL implementation. More...
#include <avl.hpp>
Public Types | |
typedef K | value_type |
The type of the values in the tree. | |
typedef K | key_type |
The type of the keys in the tree. | |
typedef K | referent_type |
The type passed to the template. | |
typedef Comp | key_less |
The comparator to use to compare the keys. | |
typedef const K & | const_reference |
The type of a const reference on the values. | |
typedef impl_type::avl_const_iterator | const_iterator |
The type of the iterator on the values of the tree. |
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. |
Binary search tree AVL implementation.
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().
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().
|
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().
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(), and claw::math::ordered_set< K, Comp >::intersection().
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().
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().
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().
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().
|
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().