Claw  1.7.3
Public Types | Public Member Functions | List of all members
claw::avl< K, Comp > Class Template Reference

Binary search tree AVL implementation. More...

#include <avl.hpp>

Inheritance diagram for claw::avl< K, Comp >:
claw::math::ordered_set< K, Comp >

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.

Detailed Description

template<class K, class Comp = std::less<K>>
class claw::avl< K, Comp >

Binary search tree AVL implementation.

Author
Julien Jorge

Definition at line 43 of file avl.hpp.

Constructor & Destructor Documentation

template<class K , class Comp >
claw::avl< K, Comp >::avl ( )

AVL constructor.

Postcondition
empty()

Definition at line 38 of file avl.tpp.

template<class K, class Comp>
claw::avl< K, Comp >::avl ( const avl< K, Comp > &  that)
explicit

AVL copy constructor.

Parameters
thatAVL instance to copy from.

Definition at line 49 of file avl.tpp.

template<class K , class Comp >
template<typename InputIterator >
claw::avl< K, Comp >::avl ( InputIterator  first,
InputIterator  last 
)

Constructor from a range.

Parameters
firstIterator on the first element of the range.
lastIterator just past the last element of the range.

Definition at line 63 of file avl.tpp.

References claw::avl< K, Comp >::insert().

Member Function Documentation

template<class K , class Comp >
void claw::avl< K, Comp >::clear ( )

Clear a tree.

Postcondition
empty()

Definition at line 113 of file avl.tpp.

References claw::avl< K, Comp >::clear().

Referenced by claw::avl< K, Comp >::clear().

template<class K , class Comp >
bool claw::avl< K, Comp >::empty ( ) const
inline

Tell if a tree is empty or not.

Returns
true if the tree is empty, false otherwise.

Definition at line 135 of file avl.tpp.

References claw::avl< K, Comp >::empty().

Referenced by claw::avl< K, Comp >::empty().

template<class K, class Comp >
void claw::avl< K, Comp >::erase ( const K &  key)

Delete a value in a tree.

Parameters
keyNode key.
Postcondition
not exists(key)

Definition at line 102 of file avl.tpp.

References claw::avl< K, Comp >::erase().

Referenced by claw::avl< K, Comp >::erase().

template<class K, class Comp >
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.

Parameters
keyKey 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().

template<class K, class Comp >
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.

Parameters
keyKey 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().

template<class K, class Comp >
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.

Parameters
keyKey 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().

template<class K, class Comp >
void claw::avl< K, Comp >::insert ( const K &  key)

Add a value in a tree.

Parameters
keyNode key.
Postcondition
exists(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().

template<class K , class Comp >
template<typename InputIterator >
void claw::avl< K, Comp >::insert ( InputIterator  first,
InputIterator  last 
)

Add a range of items in the tree.

Parameters
firstIterator on the first item to add.
lastIterator past the last item to add.
Precondition
Iterator::value_type is K
Postcondition
exists( *it ) for all it in [first, last)

Definition at line 90 of file avl.tpp.

References claw::avl< K, Comp >::insert().

template<class K, class Comp>
bool claw::avl< K, Comp >::operator!= ( const avl< K, Comp > &  that) const

Disequality.

Parameters
thatThe instance to compare to.

Definition at line 250 of file avl.tpp.

template<class K, class Comp>
bool claw::avl< K, Comp >::operator< ( const avl< K, Comp > &  that) const

Less than operator.

Parameters
thatThe instance to compare to.

Definition at line 261 of file avl.tpp.

template<class K, class Comp>
bool claw::avl< K, Comp >::operator<= ( const avl< K, Comp > &  that) const

Less or equal operator.

Parameters
thatThe instance to compare to.

Definition at line 283 of file avl.tpp.

template<class K, class Comp>
claw::avl< K, Comp > & claw::avl< K, Comp >::operator= ( const avl< K, Comp > &  that)

Assignment.

Parameters
thatThe instance to copy from.

Definition at line 227 of file avl.tpp.

template<class K, class Comp>
bool claw::avl< K, Comp >::operator== ( const avl< K, Comp > &  that) const

Equality.

Parameters
thatThe instance to compare to.

Definition at line 239 of file avl.tpp.

template<class K, class Comp>
bool claw::avl< K, Comp >::operator> ( const avl< K, Comp > &  that) const

Greater than operator.

Parameters
thatThe instance to compare to.

Definition at line 272 of file avl.tpp.

template<class K, class Comp>
bool claw::avl< K, Comp >::operator>= ( const avl< K, Comp > &  that) const

Greater or equal operator.

Parameters
thatThe instance to compare to.

Definition at line 294 of file avl.tpp.

template<class K , class Comp >
unsigned int claw::avl< K, Comp >::size ( ) const
inline

The documentation for this class was generated from the following files: