Loading...
Searching...
No Matches
etl::intrusive_avl_tree< TValue, ID_ > Class Template Reference

`#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