#include <intrusive_avl_tree.h>

Classes
class	iterator
class	const_iterator

Public Types
typedef base::link_type	link_type
typedef TValue	value_type
typedef value_type *	pointer
typedef const value_type *	const_pointer
typedef value_type &	reference
typedef const value_type &	const_reference
typedef size_t	size_type
Public Types inherited from etl::intrusive_avl_tree_base< 0 >
enum

Public Member Functions
	intrusive_avl_tree () ETL_NOEXCEPT
	Default constructor.
template<typename TIterator, typename TBinaryCompare>
	intrusive_avl_tree (TIterator first, TIterator last, TBinaryCompare binary_comp, typename etl::enable_if<!etl::is_integral< TIterator >::value, int >::type=0)
	~intrusive_avl_tree ()
ETL_NODISCARD iterator	begin () ETL_NOEXCEPT
ETL_NODISCARD const_iterator	begin () const ETL_NOEXCEPT
ETL_NODISCARD const_iterator	cbegin () const ETL_NOEXCEPT
ETL_NODISCARD iterator	end () ETL_NOEXCEPT
ETL_NODISCARD const_iterator	end () const ETL_NOEXCEPT
ETL_NODISCARD const_iterator	cend () const ETL_NOEXCEPT
ETL_NODISCARD iterator	max () ETL_NOEXCEPT
ETL_NODISCARD const_iterator	max () const ETL_NOEXCEPT
ETL_NODISCARD iterator	min () ETL_NOEXCEPT
ETL_NODISCARD const_iterator	min () const ETL_NOEXCEPT
template<typename TCompare>
iterator	lower_bound (TCompare comp)
template<typename TCompare>
const_iterator	lower_bound (TCompare comp) const
template<typename TCompare>
iterator	upper_bound (TCompare comp)
template<typename TCompare>
const_iterator	upper_bound (TCompare comp) const
ETL_NODISCARD iterator	get_root () ETL_NOEXCEPT
ETL_NODISCARD const_iterator	get_root () const ETL_NOEXCEPT
template<typename TCompare>
iterator	find (TCompare comp)
template<typename TCompare>
const_iterator	find (TCompare comp) const
template<typename TCompare, typename TFactory>
etl::pair< iterator, bool >	find_or_insert (TCompare comp, TFactory factory)
iterator	erase (iterator position)
iterator	erase (const_iterator position)
template<typename Visitor>
void	visit_in_order (const bool is_reverse, Visitor visitor)
template<typename Visitor>
void	visit_in_order (const bool is_reverse, Visitor visitor) const
template<typename Visitor>
void	visit_post_order (const bool is_reverse, Visitor visitor)
template<typename Visitor>
void	visit_post_order (const bool is_reverse, Visitor visitor) const
template<typename Visitor>
void	visit_pre_order (const bool is_reverse, Visitor visitor)
template<typename Visitor>
void	visit_pre_order (const bool is_reverse, Visitor visitor) const
Public Member Functions inherited from etl::intrusive_avl_tree_base< 0 >
ETL_NODISCARD bool	empty () const ETL_NOEXCEPT
ETL_NODISCARD size_t	size () const ETL_NOEXCEPT
void	clear () ETL_NOEXCEPT
void	swap (intrusive_avl_tree_base &other) ETL_NOEXCEPT

Additional Inherited Members
Protected Member Functions inherited from etl::intrusive_avl_tree_base< 0 >
	intrusive_avl_tree_base () ETL_NOEXCEPT
	Default constructor.
	~intrusive_avl_tree_base ()
ETL_NODISCARD link_type *	get_root () ETL_NOEXCEPT
ETL_NODISCARD link_type &	get_origin () ETL_NOEXCEPT
void	assign_impl (TIterator first, TIterator last, TBinaryCompare binary_comp)
etl::pair< TValue *, bool >	find_or_insert_impl (TCompare comp, TFactory factory)
Static Protected Member Functions inherited from etl::intrusive_avl_tree_base< 0 >
static ETL_NODISCARD bool	is_real_link (const link_type *link) ETL_NOEXCEPT
static ETL_NODISCARD TLink *	begin_impl (TLink &origin) ETL_NOEXCEPT
static ETL_NODISCARD TLink *	end_impl (TLink &origin) ETL_NOEXCEPT
static ETL_NODISCARD TLink *	find_extremum_impl (TLink *curr, const bool is_max) ETL_NOEXCEPT
static ETL_NODISCARD TLink *	next_in_order_impl (TLink *curr) ETL_NOEXCEPT
static ETL_NODISCARD TLink *	prev_in_order_impl (TLink *curr) ETL_NOEXCEPT
static void	visit_in_order_impl (TLink *curr, const bool is_reverse, Visitor visitor)
static void	visit_post_order_impl (TLink *curr, const bool is_reverse, Visitor visitor)
static void	visit_pre_order_impl (TLink *curr, const bool is_reverse, Visitor visitor)
static ETL_NODISCARD int_fast8_t	get_balance_factor_impl (const link_type *const curr) ETL_NOEXCEPT
static ETL_NODISCARD TLink *	get_parent_impl (TLink *const curr) ETL_NOEXCEPT
static ETL_NODISCARD TLink *	get_child_impl (TLink *const curr, const bool is_right) ETL_NOEXCEPT
static TValue *	find_impl (TLink *const root, TCompare comp)
static TValue *	find_bound_impl (TLink *const root, TCompare comp)
static void	erase_impl (link_type *const z_link) ETL_NOEXCEPT

Detailed Description

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

An intrusive AVL tree. Stores elements derived from 'intrusive_avl_tree<ID>::link_type'.

NB! The tree itself is not the real owner (of memory) of its nodes. The node TValue type contains all the necessary means (via required inheritance from link_type) to be able to participate in the tree as a "linked" node - hence the "intrusive" term.

Warning: This tree cannot be used for concurrent access from multiple threads.

Template Parameters

TValue	The type of value that the tree holds.
ID_	The link ID that the value is derived from.

Constructor & Destructor Documentation

◆ intrusive_avl_tree()

template<typename TValue, size_t ID_ = 0>

template<typename TIterator, typename TBinaryCompare>

etl::intrusive_avl_tree< TValue, ID_ >::intrusive_avl_tree	(	TIterator	first,
		TIterator	last,
		TBinaryCompare	binary_comp,
		typename etl::enable_if<!etl::is_integral< TIterator >::value, int >::type	= 0 )

inline

Constructor from range of items. Complexity: O(N*log(N)). NB! All items in the range must be in the "unlinked" state initially; otherwise the "already linked" exception is thrown. On success, all inserted items (except possible duplicates; see the comparator description below) will be linked.

The binary comparator should accept two const value_type& arguments (aka lhs and rhs), and return integer result (aka lhs - rhs "subtraction" result):

>0 if the lhs is "greater" than the rhs
0 if the lhs is "equal" to the rhs
<0 if the lhs is "smaller" than the rhs
if throws then exception is propagated Hints:
if you want duplicates then always return either >0 or <0, even for equal arguments:
- <0 (e.g. -1) will prepend a duplicate item to the tree
- >0 (e.g. +1) will append a duplicate item to the tree
if you want to avoid duplicates in the result tree then use 0 for "equal" arguments - in such case only the first item of duplicates in the range will be linked to the tree; the rest will be skipped (left unlinked)
etl::compare<value_type>::cmp could be directly used as comparator (if value's less is defined) - its Less, Equal and Greater are convertible/compatible with expected result integers.

If asserts or exceptions are enabled, throws:

an etl::intrusive_avl_tree_iterator_exception if the first > last (DEBUG build only).
an etl::intrusive_avl_tree_value_is_already_linked if any item (in [first, last) range) is already linked to some other tree.
whatever the binary_comp might throw Any exception during tree building will unlink already inserted nodes - so it's all or nothing.

◆ ~intrusive_avl_tree()

template<typename TValue, size_t ID_ = 0>

etl::intrusive_avl_tree< TValue, ID_ >::~intrusive_avl_tree ( )

inline

Destructor. Complexity: O(N).

Member Function Documentation

◆ begin() [1/2]

template<typename TValue, size_t ID_ = 0>

ETL_NODISCARD const_iterator etl::intrusive_avl_tree< TValue, ID_ >::begin ( ) const

inline

Gets the beginning of the intrusive_avl_tree. Complexity: O(log(N)). Returns end if tree is empty.

◆ begin() [2/2]

template<typename TValue, size_t ID_ = 0>

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

inline

Gets the beginning of the intrusive_avl_tree. Complexity: O(log(N)). Returns end if tree is empty.

◆ cbegin()

template<typename TValue, size_t ID_ = 0>

ETL_NODISCARD const_iterator etl::intrusive_avl_tree< TValue, ID_ >::cbegin ( ) const

inline

Gets the beginning of the intrusive_avl_tree. Complexity: O(log(N)). Returns end if tree is empty.

◆ cend()

template<typename TValue, size_t ID_ = 0>

ETL_NODISCARD const_iterator etl::intrusive_avl_tree< TValue, ID_ >::cend ( ) const

inline

Gets the end of the intrusive_avl_tree. Complexity: O(1).

◆ end() [1/2]

template<typename TValue, size_t ID_ = 0>

ETL_NODISCARD const_iterator etl::intrusive_avl_tree< TValue, ID_ >::end ( ) const

inline

Gets the end of the intrusive_avl_tree. Complexity: O(1).

◆ end() [2/2]

template<typename TValue, size_t ID_ = 0>

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

inline

Gets the end of the intrusive_avl_tree. Complexity: O(1).

◆ erase() [1/2]

template<typename TValue, size_t ID_ = 0>

iterator etl::intrusive_avl_tree< TValue, ID_ >::erase ( const_iterator position )

inline

Erases the value at the specified position. Complexity: O(log(N)) - includes tree rebalancing. Operation invalidates any existing iterator to the same item, but it does NOT affect any other iterators.

Parameters

position iterator must originate from the same tree instance. Returns iterator to the next tree node (after the erased one). If asserts or exceptions are enabled, throws etl::intrusive_avl_tree_iterator_exception if iterator doesn't reference a real item. Hint: use clear method if you need to erase all items - no tree rebalancing will be involved.

◆ erase() [2/2]

template<typename TValue, size_t ID_ = 0>

iterator etl::intrusive_avl_tree< TValue, ID_ >::erase ( iterator position )

inline

Erases the value at the specified position. Complexity: O(log(N)) - includes tree rebalancing. Operation invalidates any existing iterator to the same item, but it does NOT affect any other iterators.

Parameters

position iterator must originate from the same tree instance. Returns iterator to the next tree node (after the erased one). If asserts or exceptions are enabled, throws etl::intrusive_avl_tree_iterator_exception if iterator doesn't reference a real item. Hint: use clear method if you need to erase all items - no tree rebalancing will be involved.

◆ find() [1/2]

template<typename TValue, size_t ID_ = 0>

template<typename TCompare>

iterator etl::intrusive_avl_tree< TValue, ID_ >::find ( TCompare comp )

inline

Finds an item using given unary comparator. Complexity: O(log(N)) assuming O(1) for the comparator.

The unary comparator should accept single const value_type& value argument, and return integer result:

>0 (e.g. +1) if the find target is "greater" than the argument
0 if the target is found
<0 (e.g. -1) if the target is "smaller" than the argument
if throws then exception is propagated

Result iterator will be end() if there is no matching item.

◆ find() [2/2]

template<typename TValue, size_t ID_ = 0>

template<typename TCompare>

const_iterator etl::intrusive_avl_tree< TValue, ID_ >::find ( TCompare comp ) const

inline

Finds a constant item using given unary comparator. Complexity: O(log(N)) assuming O(1) for the comparator.

The unary comparator should accept single const value_type& value argument, and return integer result:

>0 (e.g. +1) if the find target is "greater" than the argument
0 if the target is found
<0 (e.g. -1) if the target is "smaller"
if throws then exception is propagated

Result iterator will be end() if there is no matching item.

◆ find_or_insert()

template<typename TValue, size_t ID_ = 0>

template<typename TCompare, typename TFactory>

etl::pair< iterator, bool > etl::intrusive_avl_tree< TValue, ID_ >::find_or_insert	(	TCompare	comp,
		TFactory	factory )

inline

Finds an existing item using given unary comparator, and if not found then invokes factory functor to insert a new item. The new item is inserted at the tree position where the search has stopped. Complexity: O(log(N)) assuming O(1) for the comparator and factory. Operation does NOT invalidate any already existing iterators, but depending on where the new item was linked to the tree the existing iterators may skip the recently linked item.

The unary comparator should accept single const value_type& value argument, and return integer result:

>0 (e.g. +1) if the find target is "greater" than the argument
0 if the target is found
<0 (e.g. -1) if the target is "smaller" than the argument
if throws then exception is propagated Hint: If result tree should contain "duplicates" then return non-zero result even for "equal" items, like e.g.:
+1 to append a new item after existing duplicates
-1 to prepend a new item before existing duplicates

The factory functor should return address of a "new" value (castable to the link_type*). The returned value should not be already linked to any tree, otherwise throws intrusive_avl_tree_value_is_already_linked (if asserts or exceptions are enabled). If return address is nullptr then tree won't be modified, and final result iterator will be valueless. If factory throws then exception is propagated (without modifying the tree).

Result contains a pair of:

iterator to found (or inserted) item (could be valueless, but never end()).
boolean indicating whether tree was modified (due to successful insertion).

◆ get_root() [1/2]

template<typename TValue, size_t ID_ = 0>

ETL_NODISCARD const_iterator etl::intrusive_avl_tree< TValue, ID_ >::get_root ( ) const

inline

Gets root node (if any). Complexity: O(1). Normally is not needed unless advanced traversal is required. Result iterator will be valueless (has_value() == false) if tree is empty.

◆ get_root() [2/2]

template<typename TValue, size_t ID_ = 0>

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

inline

Gets root node (if any). Complexity: O(1). Normally is not needed unless advanced traversal is required. Result iterator will be valueless (has_value() == false) if tree is empty.

◆ lower_bound()

template<typename TValue, size_t ID_ = 0>

template<typename TCompare>

iterator etl::intrusive_avl_tree< TValue, ID_ >::lower_bound ( TCompare comp )

inline

Returns an iterator pointing to the first item that compares as "not less". Complexity: O(log(N)) assuming O(1) for the comparator. The unary comparator should accept single const value_type& value argument, and return integer result:

>0 (e.g. +1) if the find target is "greater" than the argument
0 if the target is found
<0 (e.g. -1) if the target is "smaller" than the argument
if throws then exception is propagated

Result iterator will be end() if no such item exists.

◆ max() [1/2]

template<typename TValue, size_t ID_ = 0>

ETL_NODISCARD const_iterator etl::intrusive_avl_tree< TValue, ID_ >::max ( ) const

inline

Gets the maximum of the intrusive_avl_tree. Complexity: O(log(N)). Returns end if tree is empty.

◆ max() [2/2]

template<typename TValue, size_t ID_ = 0>

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

inline

Gets the maximum of the intrusive_avl_tree. Complexity: O(log(N)). Returns end if tree is empty.

◆ min() [1/2]

template<typename TValue, size_t ID_ = 0>

ETL_NODISCARD const_iterator etl::intrusive_avl_tree< TValue, ID_ >::min ( ) const

inline

Gets the minimum of the intrusive_avl_tree. Complexity: O(log(N)). Returns end if tree is empty.

◆ min() [2/2]

template<typename TValue, size_t ID_ = 0>

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

inline

Gets the minimum of the intrusive_avl_tree. Complexity: O(log(N)). Returns end if tree is empty.

◆ upper_bound()

template<typename TValue, size_t ID_ = 0>

template<typename TCompare>

iterator etl::intrusive_avl_tree< TValue, ID_ >::upper_bound ( TCompare comp )

inline

Returns an iterator pointing to the first item that compares as "greater". Complexity: O(log(N)) assuming O(1) for the comparator. The unary comparator should accept single const value_type& value argument, and return integer result:

>0 (e.g. +1) if the find target is "greater" than the argument
0 if the target is found
<0 (e.g. -1) if the target is "smaller" than the argument
if throws then exception is propagated

Result iterator will be end() if no such item exists.

◆ visit_in_order() [1/2]

template<typename TValue, size_t ID_ = 0>

template<typename Visitor>

void etl::intrusive_avl_tree< TValue, ID_ >::visit_in_order	(	const bool	is_reverse,
		Visitor	visitor )

inline

Visits all items of the tree in (ascending or descending) order. See https://en.wikipedia.org/wiki/Tree_traversal Complexity: O(N); no recursion. is_reverse determines in which order: false -> ascending, true -> descending. The visitor functor will be called with reference to the next in-order item. The item could be modified but so that it doesn't affect current ordering of the tree. NB! The visitor must not modify the tree during visitation. If visitor throws then exception is propagated.

◆ visit_in_order() [2/2]

template<typename TValue, size_t ID_ = 0>

template<typename Visitor>

void etl::intrusive_avl_tree< TValue, ID_ >::visit_in_order	(	const bool	is_reverse,
		Visitor	visitor ) const

inline

Visits all items of the tree in (ascending or descending) order. See https://en.wikipedia.org/wiki/Tree_traversal Complexity: O(N); no recursion. is_reverse determines in which order: false -> ascending, true -> descending. The visitor functor will be called with const reference to the next in-order item. NB! The visitor must not modify the tree during visitation. If visitor throws then exception is propagated.

◆ visit_post_order() [1/2]

template<typename TValue, size_t ID_ = 0>

template<typename Visitor>

void etl::intrusive_avl_tree< TValue, ID_ >::visit_post_order	(	const bool	is_reverse,
		Visitor	visitor )

inline

Visits all items of the tree using "post" ordering - child items first, and then "current" item (finishing with the root one). See https://en.wikipedia.org/wiki/Tree_traversal Complexity: O(N); no recursion. is_reverse determines in which order to visit children:

false -> "smaller" child first (if any), and then "bigger" one
true -> "bigger" child first (if any), and then "smaller" one The visitor functor will be called with reference to the next post-order item. The item could be modified but so that it doesn't affect current ordering of the tree. NB! The visitor must not modify the tree during visitation. If visitor throws then exception is propagated.

◆ visit_post_order() [2/2]

template<typename TValue, size_t ID_ = 0>

template<typename Visitor>

void etl::intrusive_avl_tree< TValue, ID_ >::visit_post_order	(	const bool	is_reverse,
		Visitor	visitor ) const

inline

Visits all items of the tree using "post" ordering - child items first, and then "current" item (finishing with the root one). See https://en.wikipedia.org/wiki/Tree_traversal Complexity: O(N); no recursion. is_reverse determines in which order to visit children:

false -> "smaller" child first (if any), and then "bigger" one
true -> "bigger" child first (if any), and then "smaller" one The visitor functor will be called with const reference to the next post-order item. NB! The visitor must not modify the tree during visitation. If visitor throws then exception is propagated.

◆ visit_pre_order() [1/2]

template<typename TValue, size_t ID_ = 0>

template<typename Visitor>

void etl::intrusive_avl_tree< TValue, ID_ >::visit_pre_order	(	const bool	is_reverse,
		Visitor	visitor )

inline

Visits all items of the tree using "pre" ordering - "current" item first (starting from the root), and then children. See https://en.wikipedia.org/wiki/Tree_traversal Complexity: O(N); no recursion. is_reverse determines in which order to visit children:

false -> "smaller" child first (if any), and then "bigger" one
true -> "bigger" child first (if any), and then "smaller" one The visitor functor will be called with reference to the next pre-order item. The item could be modified but so that it doesn't affect current ordering of the tree. NB! The visitor must not modify the tree during visitation. If visitor throws then exception is propagated.

◆ visit_pre_order() [2/2]

template<typename TValue, size_t ID_ = 0>

template<typename Visitor>

void etl::intrusive_avl_tree< TValue, ID_ >::visit_pre_order	(	const bool	is_reverse,
		Visitor	visitor ) const

inline

Visits all items of the tree using "pre" ordering - "current" item first (starting from the root), and then children. See https://en.wikipedia.org/wiki/Tree_traversal Complexity: O(N); no recursion. is_reverse determines in which order to visit children:

false -> "smaller" child first (if any), and then "bigger" one
true -> "bigger" child first (if any), and then "smaller" one The visitor functor will be called with const reference to the next pre-order item. NB! The visitor must not modify the tree during visitation. If visitor throws then exception is propagated.

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

include/etl/intrusive_avl_tree.h

Classes

Public Types

Public Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ intrusive_avl_tree()

◆ ~intrusive_avl_tree()

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ cbegin()

◆ cend()

◆ end() [1/2]

◆ end() [2/2]

◆ erase() [1/2]

◆ erase() [2/2]

◆ find() [1/2]

◆ find() [2/2]

◆ find_or_insert()

◆ get_root() [1/2]

◆ get_root() [2/2]

◆ lower_bound()

◆ max() [1/2]

◆ max() [2/2]

◆ min() [1/2]

◆ min() [2/2]

◆ upper_bound()

◆ visit_in_order() [1/2]

◆ visit_in_order() [2/2]

◆ visit_post_order() [1/2]

◆ visit_post_order() [2/2]

◆ visit_pre_order() [1/2]

◆ visit_pre_order() [2/2]