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_iterator & | operator++ () |
Preincrement. | |
avl_iterator | operator++ (int) |
Postincrement. | |
avl_iterator & | operator-- () |
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. |
typedef const K claw::avl< K, Comp >::avl_iterator::value_type |
typedef const K& claw::avl< K, Comp >::avl_iterator::reference |
typedef const K* const claw::avl< K, Comp >::avl_iterator::pointer |
typedef ptrdiff_t claw::avl< K, Comp >::avl_iterator::difference_type |
typedef std::bidirectional_iterator_tag claw::avl< K, Comp >::avl_iterator::iterator_category |
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]
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]
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 :
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]
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]
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 :
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]
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]
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]
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->()
bool claw::avl< K, Comp >::avl_iterator::operator== | ( | const avl_iterator & | it | ) | const [inline] |
Equality.
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==()
bool claw::avl< K, Comp >::avl_iterator::operator!= | ( | const avl_iterator & | it | ) | const [inline] |
const_avl_node_ptr claw::avl< K, Comp >::avl_iterator::m_current [private] |
Current node in the tree.
Definition at line 133 of file avl.hpp.
Referenced by claw::avl< K, Comp >::avl_iterator::operator*(), claw::avl< K, Comp >::avl_iterator::operator++(), claw::avl< K, Comp >::avl_iterator::operator--(), claw::avl< K, Comp >::avl_iterator::operator->(), and claw::avl< K, Comp >::avl_iterator::operator==().
bool claw::avl< K, Comp >::avl_iterator::m_is_final [private] |
True if we've gone past the last node.
Definition at line 135 of file avl.hpp.
Referenced by claw::avl< K, Comp >::avl_iterator::operator++(), claw::avl< K, Comp >::avl_iterator::operator--(), and claw::avl< K, Comp >::avl_iterator::operator==().