Binary search tree base AVL implementation. More...

#include <avl_base.hpp>

Classes
class	avl_const_iterator
	AVL iterator. More...
class	avl_iterator
	AVL iterator. More...
class	avl_node
	Node of a binary search tree (AVL).

Public Types
typedef K	value_type
typedef K	key_type
typedef K	referent_type
typedef Comp	key_less
typedef const K &	const_reference
typedef avl_iterator	iterator
typedef avl_const_iterator	const_iterator

Public Member Functions
	avl_base ()
	AVL constructor.
	avl_base (const avl_base< K, Comp > &that)
	AVL copy constructor.
	~avl_base ()
	AVL destructor.
void	insert (const K &key)
	Add a value in a tree.
template<typename Iterator >
void	insert (Iterator first, Iterator 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.
iterator	begin ()
	Get an iterator on the nodes of the tree.
const_iterator	begin () const
	Get an iterator on the nodes of the tree.
iterator	end ()
	Get an iterator after the end of the tree.
const_iterator	end () const
	Get an iterator after the end of the tree.
iterator	find (const K &key)
	Get an iterator on the nodes of the tree from a specified key.
const_iterator	find (const K &key) const
	Get an iterator on the nodes of the tree from a specified key.
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.
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.
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.
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.
iterator	lower_bound ()
	Get an iterator on the lowest value of the tree.
const_iterator	lower_bound () const
	Get an iterator on the lowest value of the tree.
iterator	upper_bound ()
	Get an iterator on the gratest value of the tree.
const_iterator	upper_bound () const
	Get an iterator on the gratest value of the tree.
avl_base< K, Comp > &	operator= (const avl_base< K, Comp > &that)
	Assignment operator.
bool	operator== (const avl_base< K, Comp > &that) const
	Equality.
bool	operator!= (const avl_base< K, Comp > &that) const
	Disequality.
bool	operator< (const avl_base< K, Comp > &that) const
	Less than operator.
bool	operator> (const avl_base< K, Comp > &that) const
	Greater than operator.
bool	operator<= (const avl_base< K, Comp > &that) const
	Less or equal operator.
bool	operator>= (const avl_base< K, Comp > &that) const
	Greater or equal operator.
void	swap (avl_base< K, Comp > &that)
	Swap the values with an other tree.

Static Public Attributes
static key_less	s_key_less
	Function object used to compare keys.

Detailed Description

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

Binary search tree base AVL implementation.

Each key appears only once. Nodes are sorted as left_child < node < right_child.

Invariant: this->empty() <==> (this->size() == 0); this is an AVL.

Remarks

Type requirements :

K is LessThanComparable ;
Comp is a binary predicate such that Comp(K a, K b) == true if a < b.

Code is taken from a C implementation, so perhaps it doesn't really look nice for C++. Nevertheless it works perfectly and it's fast conversion : that good things.

Author: Julien Jorge

Definition at line 57 of file avl_base.hpp.

Constructor & Destructor Documentation

template<class K , class Comp >

claw::avl_base< K, Comp >::avl_base ( )

AVL constructor.

Postcondition: empty()

Definition at line 891 of file avl_base.tpp.

template<class K, class Comp>

claw::avl_base< K, Comp >::avl_base ( const avl_base< K, Comp > & that )

explicit

AVL copy constructor.

Parameters

that	AVL instance to copy from.

Definition at line 903 of file avl_base.tpp.

Member Function Documentation

template<class K , class Comp >

void claw::avl_base< K, Comp >::clear ( )

Clear a tree.

Postcondition: empty()

Definition at line 988 of file avl_base.tpp.

template<class K , class Comp >

bool claw::avl_base< 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 1017 of file avl_base.tpp.

template<class K, class Comp >

void claw::avl_base< K, Comp >::erase ( const K & key )

Delete a value in a tree.

Parameters

key Node key.

Postcondition: not exists(key)

Definition at line 972 of file avl_base.tpp.

template<class K, class Comp >

claw::avl_base< K, Comp >::iterator claw::avl_base< K, Comp >::find ( const K & key )

Get an iterator on the nodes of the tree from a specified key.

Parameters

key	Key to find.

Definition at line 1083 of file avl_base.tpp.

template<class K, class Comp >

claw::avl_base< K, Comp >::const_iterator claw::avl_base< K, Comp >::find ( const K & key ) const

Get an iterator on the nodes of the tree from a specified key.

Parameters

key	Key to find.

Definition at line 1095 of file avl_base.tpp.

template<class K, class Comp >

claw::avl_base< K, Comp >::iterator claw::avl_base< K, Comp >::find_nearest_greater ( const K & key )

Get an iterator on the nodes of the tree on the key imediatly after from a specified key.

Parameters

key	Key to find.

Definition at line 1108 of file avl_base.tpp.

template<class K, class Comp >

claw::avl_base< K, Comp >::const_iterator claw::avl_base< 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

key	Key to find.

Definition at line 1121 of file avl_base.tpp.

template<class K, class Comp >

claw::avl_base< K, Comp >::iterator claw::avl_base< K, Comp >::find_nearest_lower ( const K & key )

Get an iterator on the nodes of the tree on the key imediatly before from a specified key.

Parameters

key	Key to find.

Definition at line 1134 of file avl_base.tpp.

template<class K, class Comp >

claw::avl_base< K, Comp >::const_iterator claw::avl_base< 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

key	Key to find.

Definition at line 1147 of file avl_base.tpp.

template<class K, class Comp >

void claw::avl_base< K, Comp >::insert ( const K & key )

Add a value in a tree.

Parameters

key Node key.

Postcondition: exists(key)

Definition at line 934 of file avl_base.tpp.

template<class K , class Comp >

template<typename Iterator >

void claw::avl_base< K, Comp >::insert	(	Iterator	first,
		Iterator	last
	)

Add a range of items in the tree.

Parameters

first	Iterator on the first item to add.
last	Iterator past the last item to add.

Precondition: Iterator::value_type is K

Postcondition: exists( *it ) for all it in [first, last)

Definition at line 959 of file avl_base.tpp.

template<class K, class Comp>

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

Disequality.

Parameters

that	AVL top compare to.

Definition at line 1242 of file avl_base.tpp.

template<class K, class Comp>

bool claw::avl_base< K, Comp >::operator< ( const avl_base< K, Comp > & that ) const

Less than operator.

Parameters

that	AVL top compare to.

Definition at line 1253 of file avl_base.tpp.

References claw::avl_base< K, Comp >::begin(), and claw::avl_base< K, Comp >::end().

template<class K, class Comp>

bool claw::avl_base< K, Comp >::operator<= ( const avl_base< K, Comp > & that ) const

Less or equal operator.

Parameters

that	AVL top compare to.

Definition at line 1276 of file avl_base.tpp.

template<class K, class Comp>

claw::avl_base< K, Comp > & claw::avl_base< K, Comp >::operator= ( const avl_base< K, Comp > & that )

Assignment operator.

Parameters

that	AVL instance to copy from.

Definition at line 1201 of file avl_base.tpp.

template<class K, class Comp>

bool claw::avl_base< K, Comp >::operator== ( const avl_base< K, Comp > & that ) const

Equality.

Parameters

that	AVL top compare to.

Definition at line 1228 of file avl_base.tpp.

References claw::avl_base< K, Comp >::begin().

template<class K, class Comp>

bool claw::avl_base< K, Comp >::operator> ( const avl_base< K, Comp > & that ) const

Greater than operator.

Parameters

that	AVL top compare to.

Definition at line 1265 of file avl_base.tpp.

template<class K, class Comp>

bool claw::avl_base< K, Comp >::operator>= ( const avl_base< K, Comp > & that ) const

Greater or equal operator.

Parameters

that	AVL top compare to.

Definition at line 1287 of file avl_base.tpp.

template<class K , class Comp >

unsigned int claw::avl_base< K, Comp >::size ( ) const

inline

Get the size of a tree.

Returns: The size of the tree.

Definition at line 1006 of file avl_base.tpp.

template<class K, class Comp>

void claw::avl_base< K, Comp >::swap ( avl_base< K, Comp > & that )

Swap the values with an other tree.

Parameters

that	The other tree.

Definition at line 1298 of file avl_base.tpp.

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

avl_base.hpp
impl/avl_base.tpp

Classes

Public Types

Public Member Functions

Static Public Attributes

Detailed Description

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

Constructor & Destructor Documentation

Member Function Documentation

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