claw::avl< K, Comp >::avl_iterator Class Reference

List of all members.


Detailed Description

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

AVL iterator.

Definition at line 107 of file avl.hpp.


Public Types

typedef const K value_type
typedef const K & reference
typedef const K *const pointer
typedef ptrdiff_t difference_type
typedef
std::bidirectional_iterator_tag 
iterator_category

Public Member Functions

 avl_iterator ()
 Constructor.
 avl_iterator (const_avl_node_ptr node, bool final)
 Constructor.
avl_iteratoroperator++ ()
 Preincrement.
avl_iterator operator++ (int)
 Postincrement.
avl_iteratoroperator-- ()
 Predecrement.
avl_iterator operator-- (int)
 Postdecrement.
reference operator* () const
 Dereference.
pointer operator-> () const
 Reference.
bool operator== (const avl_iterator &it) const
 Equality.
bool operator!= (const avl_iterator &it) const
 Difference.

Private Attributes

const_avl_node_ptr m_current
 Current node in the tree.
bool m_is_final
 True if we've gone past the last node.

Member Typedef Documentation

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

Definition at line 110 of file avl.hpp.

template<class K, class Comp = std::less<K>>
typedef const K& claw::avl< K, Comp >::avl_iterator::reference

Definition at line 111 of file avl.hpp.

template<class K, class Comp = std::less<K>>
typedef const K* const claw::avl< K, Comp >::avl_iterator::pointer

Definition at line 112 of file avl.hpp.

template<class K, class Comp = std::less<K>>
typedef ptrdiff_t claw::avl< K, Comp >::avl_iterator::difference_type

Definition at line 113 of file avl.hpp.

template<class K, class Comp = std::less<K>>
typedef std::bidirectional_iterator_tag claw::avl< K, Comp >::avl_iterator::iterator_category

Definition at line 115 of file avl.hpp.


Constructor & Destructor Documentation

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

Constructor.

Definition at line 166 of file avl.tpp.

00167   : m_current(NULL), m_is_final(true)
00168 {
00169 
00170 } // avl_iterator::avl_iterator() [constructeur]

template<class K, class Comp>
claw::avl< K, Comp >::avl_iterator::avl_iterator ( const_avl_node_ptr  node,
bool  final 
) [inline]

Constructor.

Definition at line 177 of file avl.tpp.

00179   : m_current(node), m_is_final(final)
00180 {
00181 
00182 } // avl_iterator::avl_iterator() [constructeur with node]


Member Function Documentation

template<class K, class Comp>
claw::avl< K, Comp >::avl_iterator & claw::avl< K, Comp >::avl_iterator::operator++ (  )  [inline]

Preincrement.

When you look at "this", always consider that left subtree is already done :

  • Scan order is infixed : current node is always the leftmost node of the pending nodes.
  • when you ask next of the current node : if node have a right subtree, it's the min of this subtree.
  • if node doesn't have a right subtree then the next node is the first father we reach by the left.
    Precondition:
    not final(this).

Definition at line 200 of file avl.tpp.

References claw::avl< K, Comp >::avl_iterator::m_current, and claw::avl< K, Comp >::avl_iterator::m_is_final.

00201 {
00202   assert(!m_is_final);
00203   assert(m_current);
00204 
00205   // node have a right subtree : go to the min
00206   if (m_current->right != NULL)
00207     {
00208       m_current = m_current->right;
00209   
00210       while (m_current->left != NULL)
00211         m_current = m_current->left;
00212     }
00213   else
00214     {
00215       bool done = false;
00216       const_avl_node_ptr previous_node = m_current;
00217 
00218       // get parent node
00219       while (m_current->father && !done)
00220         {
00221           if (m_current->father->left == m_current)
00222             done = true;
00223 
00224           m_current = m_current->father;
00225         }
00226 
00227       // came back up from the max node to the root
00228       if (!done)
00229         {
00230           m_current = previous_node;
00231           m_is_final = true;
00232         }
00233     }
00234                         
00235   return *this;
00236 } // avl_iterator::operator++() [preincrement]

template<class K, class Comp>
claw::avl< K, Comp >::avl_iterator claw::avl< K, Comp >::avl_iterator::operator++ ( int   )  [inline]

Postincrement.

Definition at line 244 of file avl.tpp.

00245 {
00246   avl_iterator it = *this;
00247   ++(*this);
00248   return it;
00249 } // avl_iterator::operator++ [postincrement]

template<class K, class Comp>
claw::avl< K, Comp >::avl_iterator & claw::avl< K, Comp >::avl_iterator::operator-- (  )  [inline]

Predecrement.

When you look at "this", always consider that right subtree is already done :

  • Scan order is infixed : current node is always the rightmost node of the pending nodes.
  • when you ask next of the current node : if node have a left subtree, it's the max of this subtree.
  • if node doesn't have a left subtree then the next node is the first father that have a we reach by the right.
    Precondition:
    itérator is not at the begining of the container.

Definition at line 267 of file avl.tpp.

References claw::avl< K, Comp >::avl_iterator::m_current, and claw::avl< K, Comp >::avl_iterator::m_is_final.

00268 {
00269   assert(m_current);
00270 
00271   if (m_is_final)
00272     m_is_final = !m_is_final;
00273   else  // node have a left subtree : go to the max
00274     if (m_current->left != NULL)
00275       {
00276         m_current = m_current->left;
00277                 
00278         while (m_current->right != NULL)
00279           m_current = m_current->right;
00280       }
00281     else
00282       {
00283         bool done = false;
00284 
00285         // get parent node
00286         while (m_current->father && !done)
00287           {
00288             if (m_current->father->right == m_current)
00289               done = true;
00290 
00291             m_current = m_current->father;
00292           }
00293 
00294         // came back up from the max node to the root
00295         assert(done);
00296       }
00297   
00298   return *this;
00299 } // avl_iterator::operator--() [predecrement]

template<class K, class Comp>
claw::avl< K, Comp >::avl_iterator claw::avl< K, Comp >::avl_iterator::operator-- ( int   )  [inline]

Postdecrement.

Definition at line 307 of file avl.tpp.

00308 {
00309   avl_iterator it = *this;
00310   --(*this);
00311   return it;
00312 } // avl_iterator::operator-- [postdecrement]

template<class K, class Comp>
claw::avl< K, Comp >::avl_iterator::reference claw::avl< K, Comp >::avl_iterator::operator* (  )  const [inline]

Dereference.

Definition at line 320 of file avl.tpp.

References claw::avl< K, Comp >::avl_iterator::m_current.

00321 {
00322   return m_current->key; 
00323 } // avl_iterator::operator*() [dereference]

template<class K, class Comp>
claw::avl< K, Comp >::avl_iterator::pointer claw::avl< K, Comp >::avl_iterator::operator-> (  )  const [inline]

Reference.

Definition at line 331 of file avl.tpp.

References claw::avl< K, Comp >::avl_iterator::m_current.

00332 {
00333   return &m_current->key; 
00334 } // avl_iterator::operator->()

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

Equality.

Parameters:
it Iterator to compare to.

Definition at line 342 of file avl.tpp.

References claw::avl< K, Comp >::avl_iterator::m_current, and claw::avl< K, Comp >::avl_iterator::m_is_final.

00343 {
00344   return (m_current == it.m_current) && (m_is_final == it.m_is_final); 
00345 } // avl_iterator::operator==()

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

Difference.

Parameters:
it Iterator to compare to.

Definition at line 353 of file avl.tpp.

00354 {
00355   return !( *this == it ); 
00356 } // avl_iterator::operator!=()


Member Data Documentation

template<class K, class Comp = std::less<K>>
const_avl_node_ptr claw::avl< K, Comp >::avl_iterator::m_current [private]

template<class K, class Comp = std::less<K>>
bool claw::avl< K, Comp >::avl_iterator::m_is_final [private]


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

Generated on Thu May 22 21:07:37 2008 for CLAW Library (a C++ Library Absolutely Wonderful) by  doxygen 1.5.5