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 >

List of all members.

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.

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.


Member Typedef Documentation

template<class K, class Comp = std::less<K>>
typedef impl_type::avl_const_iterator claw::avl< K, Comp >::const_iterator
template<class K, class Comp = std::less<K>>
typedef const K& claw::avl< K, Comp >::const_reference
template<class K, class Comp = std::less<K>>
typedef avl_base<K, Comp> claw::avl< K, Comp >::impl_type [private]

Definition at line 46 of file avl.hpp.

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

Definition at line 52 of file avl.hpp.

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

Definition at line 50 of file avl.hpp.

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

Constructor & Destructor Documentation

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

AVL constructor.

Postcondition:
empty()

Definition at line 38 of file avl.tpp.

00039 {
00040 
00041 } // avl::avl() [constructor]

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

AVL copy constructor.

Parameters:
that AVL instance to copy from.

Definition at line 49 of file avl.tpp.

00050   : m_tree(that.m_tree)
00051 {
00052 
00053 } // avl::avl() [copy constructor]

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

Constructor from a range.

Parameters:
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.

00064 {
00065   m_tree.insert(first, last);
00066 } // avl::avl() [constructor from range]


Member Function Documentation

template<class K , class Comp >
claw::avl< K, Comp >::const_iterator claw::avl< K, Comp >::begin (  )  const [inline]
template<class K , class Comp >
void claw::avl< K, Comp >::clear (  )  [inline]

Clear a tree.

Postcondition:
empty()

Definition at line 113 of file avl.tpp.

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

00114 {
00115   m_tree.clear();
00116 } // avl::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_base< K, Comp >::empty(), and claw::avl< K, Comp >::m_tree.

00136 {
00137   return m_tree.empty();
00138 } // avl::empty()

template<class K , class Comp >
claw::avl< K, Comp >::const_iterator claw::avl< K, Comp >::end (  )  const [inline]
template<class K, class Comp >
void claw::avl< K, Comp >::erase ( const K &  key  )  [inline]

Delete a value in a tree.

Parameters:
key Node key.
Postcondition:
not exists(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().

00103 {
00104   m_tree.erase(key);
00105 } // avl::erase()

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

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

00169 {
00170   return m_tree.find(key);
00171 } // avl::find()

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

Parameters:
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()

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

Parameters:
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()

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

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 90 of file avl.tpp.

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

00091 {
00092   m_tree.insert(first, last);
00093 } // avl::insert()

template<class K, class Comp >
void claw::avl< K, Comp >::insert ( const K &  key  )  [inline]
template<class K , class Comp >
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()

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

Disequality.

Parameters:
that The instance to compare to.

Definition at line 250 of file avl.tpp.

References claw::avl< K, Comp >::m_tree.

00251 {
00252   return m_tree != that.m_tree;
00253 } // avl::operator!=()

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

Less than operator.

Parameters:
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.

00262 {
00263   return m_tree < that.m_tree;
00264 } // avl::operator<()

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

Less or equal operator.

Parameters:
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.

00284 {
00285   return m_tree <= that.m_tree;
00286 } // avl::operator<=()

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

Assignment.

Parameters:
that The instance to copy from.

Definition at line 227 of file avl.tpp.

References claw::avl< K, Comp >::m_tree.

00228 {
00229   m_tree = that.m_tree;
00230   return *this;
00231 } // avl::operator=()

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

Equality.

Parameters:
that The instance to compare to.

Definition at line 239 of file avl.tpp.

References claw::avl< K, Comp >::m_tree.

00240 {
00241   return m_tree == that.m_tree;
00242 } // avl::operator==()

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

Greater than operator.

Parameters:
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.

00273 {
00274   return m_tree > that.m_tree;
00275 } // avl::operator>()

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

Greater or equal operator.

Parameters:
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.

00295 {
00296   return m_tree >= that.m_tree;
00297 } // avl::operator>=()

template<class K , class Comp >
unsigned int claw::avl< K, Comp >::size (  )  const [inline]
template<class K , class Comp >
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()


Member Data Documentation

template<class K, class Comp = std::less<K>>
impl_type claw::avl< K, Comp >::m_tree [private]

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

Generated on 9 Nov 2009 for CLAW Library (a C++ Library Absolutely Wonderful) by  doxygen 1.6.1