Persitent AVL tree implementation. More...

#include <_persistent_avl.hpp>

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

Collaboration diagram for datastructures::detail::persistent_avl_tree< TKey, TItem, TKeyComp, TAlloc >:

Public Types
using	version_type = persistent_avl_version_type

using	node_ptr = typename base::node_ptr

using	key_type = typename base::key_type

using	size_type = typename base::size_type

Public Types inherited from datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, persistent_avl_node< TItem, TAlloc, persistent_avl_version_type > >
using	key_type = TKey

using	item_type = TItem

using	comparator_type = TKeyComp

using	allocator_type = TAlloc

using	node_type = persistent_avl_node< TItem, TAlloc, persistent_avl_version_type >

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
	persistent_avl_tree (const typename base::comparator_type &comparator, const typename base::allocator_type &allocator)
	Constructs new persistent AVL tree.

	persistent_avl_tree (const persistent_avl_tree &other)
	Copies another tree.

persistent_avl_tree &	operator= (const persistent_avl_tree &other)
	Copies another tree.

	persistent_avl_tree (persistent_avl_tree &&other) noexcept
	Moves another tree into this one.

persistent_avl_tree &	operator= (persistent_avl_tree &&other) noexcept
	Moves another tree into this one.

	~persistent_avl_tree () noexcept
	Destroys the tree.

node_ptr	get_root (version_type version) const noexcept
	Returns the trees root in a given version.

std::vector< node_ptr >	list_in_order (version_type version) const noexcept
	Returns a vector of nodes sorted by keys.

node_ptr	find (const key_type &key, version_type version) const noexcept
	Finds a node with the given key in the given version, if there isn't any returns a `nullptr`.

void	clear_all () noexcept
	Erases the whole tree across versions.

template<std::invocable TCallback>
std::pair< node_ptr, bool >	insert (const key_type &key, TCallback &&callback, version_type version, bool do_assign)
	Inserts an item to the tree.

std::pair< bool, version_type >	erase (const key_type &key, version_type version) noexcept
	Erases the node with the given key or does nothing if the key does not exist.

base::size_type	size (version_type version) const noexcept
	Returns the current number of nodes in the given version.

int	get_height (version_type version) const
	Returns the height of the tree in the given version.

version_type	get_current_version () const noexcept
	Returns the current verison.

version_type	get_preceding_version (version_type version) const
	Returns the preceding version to the given version.

template<std::invocable TCallback>
std::pair< typename persistent_avl_tree< TKey, TItem, TKeyComp, TAlloc >::node_ptr, bool >	insert (const key_type &key, TCallback &&callback, version_type version, bool do_assign)

Public Member Functions inherited from datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, persistent_avl_node< TItem, TAlloc, persistent_avl_version_type > >
	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.

Additional Inherited Members
Static Public Member Functions inherited from datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, persistent_avl_node< TItem, TAlloc, persistent_avl_version_type > >
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 inherited from datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, persistent_avl_node< TItem, TAlloc, persistent_avl_version_type > >
using	sign_type = avl_sign_type

Protected Member Functions inherited from datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, persistent_avl_node< TItem, TAlloc, persistent_avl_version_type > >
node_ptr	create_node (T &&item)
	Constructs a new node with the given item.

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 inherited from datastructures::detail::avl_tree_base< TKey, TItem, TKeyComp, TAlloc, persistent_avl_node< TItem, TAlloc, persistent_avl_version_type > >
comparator_type	comparator

node_alloc_type	allocator

Detailed Description

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

Persitent AVL tree implementation.

Implemented using the path copying method, thus every update operation adds O(log n) space.

It should keep a minimal interface, supports only insertion, deletion and find. Any more high-level shortcut functions should be implemented in wrappers.

Every function is implemented without recursion.

The only time the pointers are invalidated is when .clear_all() is called, deletions do not invalidate pointers, although after every update operation some pointers can point to an old version.

Each update operation creates a new version which is based on the given one. The whole version tree can be retrieved using the .get_preceding_version() method for every version from 0 up to the current one. Multiple "newest" versions can co-exist with each one forming a new branch. To get the newly created version right after some update operation use .get_current_version() after it.

The nodes do not store pointers to parents, because the invariant that each node has just one predecessor no longer holds, thus the implementation of iterators is not possible in the current state.

There are two types TKey and TItem, it is this way to make the class more general and so that it can represent both sets and maps. The key type is the raw type that is used to query and compare nodes, the item type is the internal type stored in nodes, and it can be indentical to the key type.

The node allocator is derived from the item allocator TAlloc.

Template Parameters

TKey	The key type.
TItem	The item type, usually same as the `TKey` or `std::pair<TKey, TValue>` for some `TValue`.
TKeyComp	`TKeyComp` must allow comparisons between all of: two keys; two items; one key and one item; one item and one key. The comparisons must be all `noexcept`.
TAlloc	The item allocator type.

Member Typedef Documentation

◆ key_type

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

using datastructures::detail::persistent_avl_tree< TKey, TItem, TKeyComp, TAlloc >::key_type = typename base::key_type

◆ node_ptr

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

using datastructures::detail::persistent_avl_tree< TKey, TItem, TKeyComp, TAlloc >::node_ptr = typename base::node_ptr

◆ size_type

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

using datastructures::detail::persistent_avl_tree< TKey, TItem, TKeyComp, TAlloc >::size_type = typename base::size_type

◆ version_type

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

using datastructures::detail::persistent_avl_tree< TKey, TItem, TKeyComp, TAlloc >::version_type = persistent_avl_version_type

Constructor & Destructor Documentation

◆ persistent_avl_tree() [1/3]

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

datastructures::detail::persistent_avl_tree< TKey, TItem, TKeyComp, TAlloc >::persistent_avl_tree	(	const typename base::comparator_type &	comparator,
		const typename base::allocator_type &	allocator
	)

Constructs new persistent AVL tree.

The tree needs to get the comparator and allocator instance from its wrapper, because they can store essential context. And to minimize the interface this is the only constructor except for the copy/move ones.

Parameters

comparator	The comparator instance passed from the wrapper.
allocator	The allocator instance passed from the wrapper.

◆ persistent_avl_tree() [2/3]

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

datastructures::detail::persistent_avl_tree< TKey, TItem, TKeyComp, TAlloc >::persistent_avl_tree ( const persistent_avl_tree< TKey, TItem, TKeyComp, TAlloc > & other )

Copies another tree.

◆ persistent_avl_tree() [3/3]

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

datastructures::detail::persistent_avl_tree< TKey, TItem, TKeyComp, TAlloc >::persistent_avl_tree ( persistent_avl_tree< TKey, TItem, TKeyComp, TAlloc > && other )

noexcept

Moves another tree into this one.

◆ ~persistent_avl_tree()

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

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

noexcept

Destroys the tree.

Correctly deallocates all the nodes without allocating any new memory.

Note: Time Complexity: O(n)

Member Function Documentation

◆ clear_all()

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

void datastructures::detail::persistent_avl_tree< TKey, TItem, TKeyComp, TAlloc >::clear_all ( )

noexcept

Erases the whole tree across versions.

Erases every node without allocating any more space and thus cannot throw an exception.

Clears also the roots vector and based_on vector.

Note: Time Complexity: O(n).; Space Complexity: O(1) including the stack size.

◆ erase()

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

std::pair< bool, typename persistent_avl_tree< TKey, TItem, TKeyComp, TAlloc >::version_type > datastructures::detail::persistent_avl_tree< TKey, TItem, TKeyComp, TAlloc >::erase	(	const key_type &	key,
		version_type	version
	)

noexcept

Erases the node with the given key or does nothing if the key does not exist.

Creates a new version based on the given version.

Does not invalidate any pointers because the path will be just copied without the node.

Returns: true if the node was erased, false otherwise; and the newest version it this branch.

Note: Time Complexity: O(log n)

now we are sure that we will delete a node

◆ find()

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

persistent_avl_tree< TKey, TItem, TKeyComp, TAlloc >::node_ptr datastructures::detail::persistent_avl_tree< TKey, TItem, TKeyComp, TAlloc >::find	(	const key_type &	key,
		version_type	version
	)		const

noexcept

Finds a node with the given key in the given version, if there isn't any returns a nullptr.

For version which do not exist yet returns a nullptr.

Parameters

key	The key to look for.
version	The version to search in.

Returns: The requested node or nullptr if such node does not exist.

Note: Time Complexity: O(log n)

◆ get_current_version()

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

version_type datastructures::detail::persistent_avl_tree< TKey, TItem, TKeyComp, TAlloc >::get_current_version ( ) const

inlinenoexcept

Returns the current verison.

◆ get_height()

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

int datastructures::detail::persistent_avl_tree< TKey, TItem, TKeyComp, TAlloc >::get_height ( version_type version ) const

Returns the height of the tree in the given version.

That means the number of edges.

For invalid versions returns -1.

Note: Time Complexity: O(log n)

◆ get_preceding_version()

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

version_type datastructures::detail::persistent_avl_tree< TKey, TItem, TKeyComp, TAlloc >::get_preceding_version ( version_type version ) const

inline

Returns the preceding version to the given version.

◆ get_root()

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

node_ptr datastructures::detail::persistent_avl_tree< TKey, TItem, TKeyComp, TAlloc >::get_root ( version_type version ) const

inlinenoexcept

Returns the trees root in a given version.

For version which do not exist yet returns a nullptr.

◆ insert() [1/2]

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

template<std::invocable TCallback>

std::pair< node_ptr, bool > datastructures::detail::persistent_avl_tree< TKey, TItem, TKeyComp, TAlloc >::insert	(	const key_type &	key,
		TCallback &&	callback,
		version_type	version,
		bool	do_assign
	)

Inserts an item to the tree.

Creates a new version based on the given version.

This function functions as an all-in-one solution to the standard emplace/insert/assign methods. It takes in the key and tries to find it. When the key is present and do_assign is true copies the path and the found node but with the newly given item, that is obtained as the result of calling the callback function. When the key does not exist inserts a new node with the new item using the same logic.

When the do_assign flag is false it does not increase the version nor does it copy anything.

Returns: The newly created node or the old found node if the do_assign is false and the key was already present; true if the item was newly inserted, meaning the key was not present.

Template Parameters

T	The item type.

Parameters

key	The key to insert
callback	The callback function to call when inserting new item, it must return either a rvalue or lvalue reference to the item to be inserted.
version	If the version is not in the tree the new version will be based on the initial version `-1`.
do_assign	Says what to do in the case the key is already in the tree.

Note: Time Complexity: O(log n); Space Complexity: O(1); Strong exception guarantee.

◆ insert() [2/2]

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

template<std::invocable TCallback>

std::pair< typename persistent_avl_tree< TKey, TItem, TKeyComp, TAlloc >::node_ptr, bool > datastructures::detail::persistent_avl_tree< TKey, TItem, TKeyComp, TAlloc >::insert	(	const key_type &	key,
		TCallback &&	callback,
		version_type	version,
		bool	do_assign
	)

◆ list_in_order()

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

std::vector< typename persistent_avl_tree< TKey, TItem, TKeyComp, TAlloc >::node_ptr > datastructures::detail::persistent_avl_tree< TKey, TItem, TKeyComp, TAlloc >::list_in_order ( version_type version ) const

noexcept

Returns a vector of nodes sorted by keys.

The values are returned as const pointers since they are immutable.

For an empty tree or invalid version returns an empty vector.

Returns: The sorted vector.

Note: Time Complexity: O(n); Newly allocated space: O(n)

◆ operator=() [1/2]

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

persistent_avl_tree< TKey, TItem, TKeyComp, TAlloc > & datastructures::detail::persistent_avl_tree< TKey, TItem, TKeyComp, TAlloc >::operator= ( const persistent_avl_tree< TKey, TItem, TKeyComp, TAlloc > & other )

Copies another tree.

◆ operator=() [2/2]

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

persistent_avl_tree< TKey, TItem, TKeyComp, TAlloc > & datastructures::detail::persistent_avl_tree< TKey, TItem, TKeyComp, TAlloc >::operator= ( persistent_avl_tree< TKey, TItem, TKeyComp, TAlloc > && other )

noexcept

Moves another tree into this one.

◆ size()

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

base::size_type datastructures::detail::persistent_avl_tree< TKey, TItem, TKeyComp, TAlloc >::size ( version_type version ) const

inlinenoexcept

Returns the current number of nodes in the given version.

For invalid versions returns 0.

Note: Time Complexity: O(1)

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

include/datastructures/_persistent_avl.hpp
include/datastructures/_persistent_avl.ipp

Public Types

Public Member Functions

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ key_type

◆ node_ptr

◆ size_type

◆ version_type

Constructor & Destructor Documentation

◆ persistent_avl_tree() [1/3]

◆ persistent_avl_tree() [2/3]

◆ persistent_avl_tree() [3/3]

◆ ~persistent_avl_tree()

Member Function Documentation

◆ clear_all()

◆ erase()

◆ find()

◆ get_current_version()

◆ get_height()

◆ get_preceding_version()

◆ get_root()

◆ insert() [1/2]

◆ insert() [2/2]

◆ list_in_order()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ size()