datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, TNode > Class Template Reference

Base class for avl trees. More...

#include <_avl_common.hpp>

Inheritance diagram for datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, TNode >:

Public Types
using	key_type = TKey
using	item_type = TItem
using	comparator_type = TKeyComp
using	allocator_type = TAlloc
using	node_type = TNode
using	node_alloc_type = avl_node_allocator_type< node_type, allocator_type >
	The node allocator type.
using	node_ptr = avl_node_ptr< node_type, allocator_type >
	The node pointer type.
using	node_alloc_traits = std::allocator_traits< node_alloc_type >
	Node allocator traits.
using	size_type = typename node_alloc_traits::size_type
	The size type.

Public Member Functions
	avl_tree_base (const comparator_type &comparator, const allocator_type &allocator)
	avl_tree_base (comparator_type &&comparator, allocator_type &&allocator) noexcept
virtual	~avl_tree_base ()=0
node_alloc_type	get_allocator () const noexcept
	Returns the associated allocator.

Static Public Member Functions
static node_ptr	min_from (node_ptr node) noexcept
	Finds the minimum value starting at the given node.
static node_ptr	max_from (node_ptr node) noexcept
	Finds the maximum value starting at the given node.

Protected Types
using	sign_type = avl_sign_type

Protected Member Functions
template<class T > requires (!std::is_invocable_v<T>)
node_ptr	create_node (T &&item)
	Constructs a new node with the given item.
template<class TCallback > requires std::is_invocable_v<TCallback>
node_ptr	create_node (TCallback &&callback)
	Constructs a new node with the item being the result of callback().
void	destroy_node (node_ptr node) noexcept
	Destroys the node and frees the memory.

Protected Attributes
comparator_type	comparator
node_alloc_type	allocator

Detailed Description

template<class TKey, class TItem, class TKeyComp, class TAlloc, class TNode>
class datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, TNode >

Base class for avl trees.

Member Typedef Documentation

allocator_type

template<class TKey , class TItem , class TKeyComp , class TAlloc , class TNode >

using datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, TNode >::allocator_type = TAlloc

comparator_type

template<class TKey , class TItem , class TKeyComp , class TAlloc , class TNode >

using datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, TNode >::comparator_type = TKeyComp

item_type

template<class TKey , class TItem , class TKeyComp , class TAlloc , class TNode >

using datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, TNode >::item_type = TItem

key_type

template<class TKey , class TItem , class TKeyComp , class TAlloc , class TNode >

using datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, TNode >::key_type = TKey

node_alloc_traits

template<class TKey , class TItem , class TKeyComp , class TAlloc , class TNode >

using datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, TNode >::node_alloc_traits = std::allocator_traits<node_alloc_type>

Node allocator traits.

Defined here so that I don't have to write so much raven brackets.

node_alloc_type

template<class TKey , class TItem , class TKeyComp , class TAlloc , class TNode >

using datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, TNode >::node_alloc_type = avl_node_allocator_type<node_type, allocator_type>

The node allocator type.

node_ptr

template<class TKey , class TItem , class TKeyComp , class TAlloc , class TNode >

using datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, TNode >::node_ptr = avl_node_ptr<node_type, allocator_type>

The node pointer type.

Can be also a fancy pointer depending on the allocator type.

node_type

template<class TKey , class TItem , class TKeyComp , class TAlloc , class TNode >

using datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, TNode >::node_type = TNode

sign_type

template<class TKey , class TItem , class TKeyComp , class TAlloc , class TNode >

using datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, TNode >::sign_type = avl_sign_type

protected

size_type

template<class TKey , class TItem , class TKeyComp , class TAlloc , class TNode >

using datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, TNode >::size_type = typename node_alloc_traits::size_type

The size type.

Usually will be set to std::size_t.

Constructor & Destructor Documentation

avl_tree_base() [1/2]

template<class TKey , class TItem , class TKeyComp , class TAlloc , class TNode >

datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, TNode >::avl_tree_base ( const comparator_type &  comparator, const allocator_type &  allocator  )

inline

avl_tree_base() [2/2]

template<class TKey , class TItem , class TKeyComp , class TAlloc , class TNode >

datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, TNode >::avl_tree_base ( comparator_type &&  comparator, allocator_type &&  allocator  )

inlinenoexcept

~avl_tree_base()

template<class TKey , class TItem , class TKeyComp , class TAlloc , class TNode >

datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, TNode >::~avl_tree_base ( )

pure virtualdefault

Member Function Documentation

create_node() [1/2]

template<class TKey , class TItem , class TKeyComp , class TAlloc , class TNode >
requires (!std::is_invocable_v<T>)

template<class T >
requires (!std::is_invocable_v<T>)

avl_tree_base< TKey, TItem, TKeyComp, TAlloc, TNode >::node_ptr datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, TNode >::create_node ( T &&  item )

protected

Constructs a new node with the given item.

Perfectly forwards the item to the constructor.

In the case of an exception during the construction, the allocated memory will be freed (Strong exception guarantee).

Returns

A pointer to the new node.

create_node() [2/2]

template<class TKey , class TItem , class TKeyComp , class TAlloc , class TNode >
requires std::is_invocable_v<TCallback>

template<class TCallback >
requires std::is_invocable_v<TCallback>

avl_tree_base< TKey, TItem, TKeyComp, TAlloc, TNode >::node_ptr datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, TNode >::create_node ( TCallback &&  callback )

protected

Constructs a new node with the item being the result of callback().

The item will be perfectly forwarded. In the case of an exception during the construction, the allocated memory will be freed (strong exception guarantee).

Returns

A pointer to the new node.

destroy_node()

template<class TKey , class TItem , class TKeyComp , class TAlloc , class TNode >

void datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, TNode >::destroy_node ( node_ptr  node )

protectednoexcept

Destroys the node and frees the memory.

get_allocator()

template<class TKey , class TItem , class TKeyComp , class TAlloc , class TNode >

node_alloc_type datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, TNode >::get_allocator ( ) const

inlinenoexcept

Returns the associated allocator.

max_from()

template<class TKey , class TItem , class TKeyComp , class TAlloc , class TNode >

avl_tree_base< TKey, TItem, TKeyComp, TAlloc, TNode >::node_ptr datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, TNode >::max_from ( node_ptr  node )

staticnoexcept

Finds the maximum value starting at the given node.

Returns a maximum value from a subtree of this tree, with the subtrees root being the given node.

You can call this even on a nullptr, in that case a nullptr will be returned.

Parameters

node	The root of the subtree to search in.

Returns

The node with the maximum key or nullptr if such node does not exist.

min_from()

template<class TKey , class TItem , class TKeyComp , class TAlloc , class TNode >

avl_tree_base< TKey, TItem, TKeyComp, TAlloc, TNode >::node_ptr datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, TNode >::min_from ( node_ptr  node )

staticnoexcept

Finds the minimum value starting at the given node.

Returns a minimum value from a subtree of this tree, with the subtrees root being the given node.

You can call this even on a nullptr, in that case a nullptr will be returned.

Parameters

node	The root of the subtree to search in.

Returns

The node with the minimum key or nullptr if such node does not exist.

Member Data Documentation

allocator

template<class TKey , class TItem , class TKeyComp , class TAlloc , class TNode >

node_alloc_type datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, TNode >::allocator

protected

comparator

template<class TKey , class TItem , class TKeyComp , class TAlloc , class TNode >

comparator_type datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, TNode >::comparator

protected

---

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

• include/datastructures/_avl_common.hpp
• include/datastructures/_avl_common.ipp