Loading...
Searching...
No Matches
etl::intrusive_avl_tree_base< ID_ > Class Template Reference

`#include <intrusive_avl_tree.h>`

## Classes

struct | link_type

## Public Types

enum | { ID = ID_ }

## Public Member Functions

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

## Protected Member Functions

| intrusive_avl_tree_base () ETL_NOEXCEPT
| Default constructor.
| ~intrusive_avl_tree_base ()
ETL_NODISCARD link_type * | get_root () ETL_NOEXCEPT
ETL_NODISCARD const link_type * | get_root () const ETL_NOEXCEPT
ETL_NODISCARD link_type & | get_origin () ETL_NOEXCEPT
const link_type & | get_origin () const ETL_NOEXCEPT
template<typename TValue, typename TIterator, typename TBinaryCompare>
void | assign_impl (TIterator first, TIterator last, TBinaryCompare binary_comp)
template<typename TValue, typename TCompare, typename TFactory>
etl::pair< TValue *, bool > | find_or_insert_impl (TCompare comp, TFactory factory)

## Static Protected Member Functions

template<typename TLink>
static ETL_NODISCARD TLink * | get_origin (TLink *link) ETL_NOEXCEPT
static ETL_NODISCARD bool | is_real_link (const link_type *link) ETL_NOEXCEPT
template<typename TLink>
static ETL_NODISCARD TLink * | begin_impl (TLink &origin) ETL_NOEXCEPT
template<typename TLink>
static ETL_NODISCARD TLink * | end_impl (TLink &origin) ETL_NOEXCEPT
template<typename TLink>
static ETL_NODISCARD TLink * | find_extremum_impl (TLink *curr, const bool is_max) ETL_NOEXCEPT
template<typename TLink>
static ETL_NODISCARD TLink * | next_in_order_impl (TLink *curr) ETL_NOEXCEPT
template<typename TLink>
static ETL_NODISCARD TLink * | prev_in_order_impl (TLink *curr) ETL_NOEXCEPT
template<typename TLink, typename Visitor>
static void | visit_in_order_impl (TLink *curr, const bool is_reverse, Visitor visitor)
template<typename TLink, typename Visitor>
static void | visit_post_order_impl (TLink *curr, const bool is_reverse, Visitor visitor)
template<typename TLink, typename 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
template<typename TLink>
static ETL_NODISCARD TLink * | get_parent_impl (TLink *const curr) ETL_NOEXCEPT
template<typename TLink>
static ETL_NODISCARD TLink * | get_child_impl (TLink *const curr, const bool is_right) ETL_NOEXCEPT
template<typename TValue, typename TLink, typename TCompare>
static TValue * | find_impl (TLink *const root, TCompare comp)
template<bool IsUpper, typename TValue, typename TLink, typename TCompare>
static TValue * | find_bound_impl (TLink *const root, TCompare comp)
static void | erase_impl (link_type *const z_link) ETL_NOEXCEPT

## Friends

void | swap (intrusive_avl_tree_base &lhs, intrusive_avl_tree_base &rhs) ETL_NOEXCEPT

## Detailed Description

template<size_t ID_>
class etl::intrusive_avl_tree_base< ID_ >

Base for intrusive AVL tree. Stores elements derived from 'intrusive_avl_tree_base<ID>::link_type'.

Template Parameters

  ID_ | The link ID that the value is derived from.

## Constructor & Destructor Documentation

## ~intrusive_avl_tree_base()

template<size_t ID_>

etl::intrusive_avl_tree_base< ID_ >::~intrusive_avl_tree_base | ( |  | ) |

inline protected

Destructor of a tree. Complexity: O(N). All existing nodes will stay alive but will be completely unlinked from the tree (and from each other). If you want more control on what happens with still linked tree nodes, then enumerate and unlink (aka "erase") them first (potentially moving to somewhere else). If needed, the whole content of the tree could be O(1) effectively moved to another tree, leaving this tree as empty - use C++11 move constructor of the tree.

## Member Function Documentation

## clear()

template<size_t ID_>

void etl::intrusive_avl_tree_base< ID_ >::clear | ( |  | ) |

inline

Unlinks all current items, leaving this tree in the empty state. Complexity: O(N). Operation invalidates all existing iterators.

Note that the same "clear all" effect could be achieved by using the erase method for each item, but b/c of intermediate tree rebalancing complexity will be higher - O(N*log(N)).

## empty()

template<size_t ID_>

ETL_NODISCARD bool etl::intrusive_avl_tree_base< ID_ >::empty | ( |  | ) | const

inline

Checks if the tree is in the empty state. Complexity: O(1).

## size()

template<size_t ID_>

ETL_NODISCARD size_t etl::intrusive_avl_tree_base< ID_ >::size | ( |  | ) | const

inline

Returns the number of elements. Complexity: O(1).

## swap()

template<size_t ID_>

void etl::intrusive_avl_tree_base< ID_ >::swap | ( | intrusive_avl_tree_base< ID_ > & | other | ) |

inline

Swap with another tree. Complexity: O(1). Does nothing in case of self-swap (when this == &other).

## Friends And Related Symbol Documentation

## swap

template<size_t ID_>

void swap | ( | intrusive_avl_tree_base< ID_ > & | lhs,
|  | intrusive_avl_tree_base< ID_ > & | rhs )

friend

Swaps the trees. Complexity: O(1). Does nothing in case of self-swap (when &lhs == &rhs).

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

- include/etl/intrusive_avl_tree.h