etl::intrusive_avl_tree< TValue, ID_ >::iterator Class Reference

#include <intrusive_avl_tree.h>

Public Member Functions
iterator &	operator++ () ETL_NOEXCEPT
iterator	operator++ (int) ETL_NOEXCEPT
iterator &	operator-- () ETL_NOEXCEPT
iterator	operator-- (int) ETL_NOEXCEPT
pointer	get () const ETL_NOEXCEPT
pointer	operator-> () const
ETL_EXPLICIT	operator bool () const ETL_NOEXCEPT
ETL_NODISCARD bool	has_value () const ETL_NOEXCEPT
ETL_NODISCARD int_fast8_t	get_balance_factor () const ETL_NOEXCEPT
ETL_NODISCARD iterator	get_parent () const ETL_NOEXCEPT
ETL_NODISCARD iterator	get_child (const bool is_right) const ETL_NOEXCEPT

Friends
class	intrusive_avl_tree
class	const_iterator
bool	operator== (const iterator &lhs, const iterator &rhs) ETL_NOEXCEPT
bool	operator!= (const iterator &lhs, const iterator &rhs) ETL_NOEXCEPT

Additional Inherited Members
Public Types inherited from etl::iterator< ETL_OR_STD::bidirectional_iterator_tag, value_type >
typedef value_type	value_type
typedef ptrdiff_t	difference_type
typedef value_type *	pointer
typedef value_type &	reference
typedef ETL_OR_STD::bidirectional_iterator_tag	iterator_category

Detailed Description

template<typename TValue, size_t ID_ = 0>
class etl::intrusive_avl_tree< TValue, ID_ >::iterator

Defines iterator of mutable items of the tree.

Normally, an iterator might...

• either reference an existing item;
• or be equal to the end. Iterator could also be in "valueless" state:
• see default constructor;
• special cases of find_or_insert;
• advanced traversal methods, like get_parent and get_child. Both "end" and "valueless" conditions could be easily isolated using has_value or bool operator:
• has_value() == true - iterator references a real node
• it == end() - terminal sentinel
• !has_value() && it != end() - valueless iterator The real item (referenced by the iterator) could be modified by the user, but so that it doesn't affect current ordering of the tree.

Member Function Documentation

get()

template<typename TValue, size_t ID_ = 0>

pointer etl::intrusive_avl_tree< TValue, ID_ >::iterator::get ( ) const

inline

Gets address of an existing mutable item (if any). Returns nullptr if iterator doesn't reference a real item.

get_balance_factor()

template<typename TValue, size_t ID_ = 0>

ETL_NODISCARD int_fast8_t etl::intrusive_avl_tree< TValue, ID_ >::iterator::get_balance_factor ( ) const

inline

Gets balance factor of tree node. Complexity: O(1). Normally is not needed unless advanced traversal is required. Result: -1, 0 or +1 depending on children tree height difference.

get_child()

template<typename TValue, size_t ID_ = 0>

ETL_NODISCARD iterator etl::intrusive_avl_tree< TValue, ID_ >::iterator::get_child ( const bool is_right ) const

inline

Gets a child node. Complexity: O(1). Normally is not needed unless advanced traversal is required. Result iterator will be valueless (has_value() == false) if there is no such child.

get_parent()

template<typename TValue, size_t ID_ = 0>

ETL_NODISCARD iterator etl::intrusive_avl_tree< TValue, ID_ >::iterator::get_parent ( ) const

inline

Gets parent node. Complexity: O(1). Normally is not needed unless advanced traversal is required. Result iterator will be valueless (has_value() == false) if there is no parent.

operator++() [1/2]

template<typename TValue, size_t ID_ = 0>

iterator & etl::intrusive_avl_tree< TValue, ID_ >::iterator::operator++ ( )

inline

Increments iterator to point to the next ("greater") item. Complexity: amortized O(1), worst-case O(log(N)).

operator++() [2/2]

template<typename TValue, size_t ID_ = 0>

iterator etl::intrusive_avl_tree< TValue, ID_ >::iterator::operator++ ( int )

inline

Increments iterator to point to the next ("greater") item. Complexity: amortized O(1), worst-case O(log(N)). Returns original iterator (before the increment).

operator--() [1/2]

template<typename TValue, size_t ID_ = 0>

iterator & etl::intrusive_avl_tree< TValue, ID_ >::iterator::operator-- ( )

inline

Decrements iterator to point to the previous ("smaller") item. Complexity: amortized O(1), worst-case O(log(N)).

operator--() [2/2]

template<typename TValue, size_t ID_ = 0>

iterator etl::intrusive_avl_tree< TValue, ID_ >::iterator::operator-- ( int )

inline

Decrements iterator to point to the previous ("smaller") item. Complexity: amortized O(1), worst-case O(log(N)). Returns original iterator (before the decrement).

operator->()

template<typename TValue, size_t ID_ = 0>

pointer etl::intrusive_avl_tree< TValue, ID_ >::iterator::operator-> ( ) const

inline

Dereferences an existing mutable item. Could be used only for iterator which has value (has_value() == true). If asserts or exceptions are enabled, throws an etl::intrusive_avl_tree_iterator_exception if iterator doesn't reference a real item.

---

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

• include/etl/intrusive_avl_tree.h