#include <tpl_persistent_treap.H>

Public Types
using	NodePtr = std::shared_ptr< const Node >

Static Public Member Functions
static size_t	node_size (const NodePtr &p) noexcept

static const Key *	min_key (const NodePtr &node) noexcept

static const Key *	max_key (const NodePtr &node) noexcept

static bool	can_join (const NodePtr &left, const NodePtr &right, const Compare &cmp)

template<class Rebuild >
static NodePtr	rotate_right (const NodePtr &node, const Rebuild &rebuild)

template<class Rebuild >
static NodePtr	rotate_left (const NodePtr &node, const Rebuild &rebuild)

template<class Rebuild >
static NodePtr	join_nodes (const NodePtr &left, const NodePtr &right, const Rebuild &rebuild)

template<class Rebuild >
static NodePtr	erase_rec (const NodePtr &node, const Key &key, const Compare &cmp, bool &erased, const Rebuild &rebuild)

template<class Rebuild >
static std::pair< NodePtr, NodePtr >	split_rec (const NodePtr &node, const Key &pivot, const Compare &cmp, const Rebuild &rebuild)

static void	collect_keys (const NodePtr &node, Array< Key > &out)

static bool	verify_rec (const NodePtr &node, const Key lo, const Key hi, const Compare &cmp, size_t &count)

static bool	is_valid_under (const NodePtr &node, const Compare &cmp)

Detailed Description

template<typename Node, typename Key, class Compare>
struct Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >

Definition at line 101 of file tpl_persistent_treap.H.

Member Typedef Documentation

◆ NodePtr

template<typename Node , typename Key , class Compare >

using Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::NodePtr = std::shared_ptr<const Node>

Definition at line 103 of file tpl_persistent_treap.H.

Member Function Documentation

◆ can_join()

template<typename Node , typename Key , class Compare >

static bool Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::can_join	(	const NodePtr &	left,
		const NodePtr &	right,
		const Compare &	cmp
	)

inlinestatic

Definition at line 126 of file tpl_persistent_treap.H.

References Aleph::blossom_maximum_cardinality_matching(), cmp(), Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::max_key(), and Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::min_key().

Referenced by Aleph::PersistentTreapMap< Key, T, Compare >::join(), and Aleph::PersistentTreapSet< Key, Compare >::join().

◆ collect_keys()

template<typename Node , typename Key , class Compare >

static void Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::collect_keys	(	const NodePtr &	node,
		Array< Key > &	out
	)

inlinestatic

Definition at line 223 of file tpl_persistent_treap.H.

References Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::collect_keys(), and out.

Referenced by Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::collect_keys(), Aleph::PersistentTreapSet< Key, Compare >::keys(), and Aleph::PersistentTreapMap< Key, T, Compare >::keys().

◆ erase_rec()

template<typename Node , typename Key , class Compare >

template<class Rebuild >

static NodePtr Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::erase_rec	(	const NodePtr &	node,
		const Key &	key,
		const Compare &	cmp,
		bool &	erased,
		const Rebuild &	rebuild
	)

inlinestatic

Definition at line 170 of file tpl_persistent_treap.H.

References Aleph::blossom_maximum_cardinality_matching(), cmp(), Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::erase_rec(), and Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::join_nodes().

Referenced by Aleph::PersistentTreapSet< Key, Compare >::erase(), Aleph::PersistentTreapMap< Key, T, Compare >::erase(), and Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::erase_rec().

◆ is_valid_under()

template<typename Node , typename Key , class Compare >

static bool Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::is_valid_under	(	const NodePtr &	node,
		const Compare &	cmp
	)

inlinestatic

Definition at line 267 of file tpl_persistent_treap.H.

References Aleph::and, cmp(), Aleph::count(), Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::node_size(), and Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::verify_rec().

Referenced by Aleph::PersistentTreapMap< Key, T, Compare >::join(), and Aleph::PersistentTreapSet< Key, Compare >::join().

◆ join_nodes()

template<typename Node , typename Key , class Compare >

template<class Rebuild >

static NodePtr Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::join_nodes	(	const NodePtr &	left,
		const NodePtr &	right,
		const Rebuild &	rebuild
	)

inlinestatic

Definition at line 150 of file tpl_persistent_treap.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::join_nodes().

Referenced by Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::erase_rec(), Aleph::PersistentTreapMap< Key, T, Compare >::join(), Aleph::PersistentTreapSet< Key, Compare >::join(), and Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::join_nodes().

◆ max_key()

template<typename Node , typename Key , class Compare >

static const Key * Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::max_key ( const NodePtr & node )

inlinestaticnoexcept

Definition at line 118 of file tpl_persistent_treap.H.

Referenced by Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::can_join().

◆ min_key()

template<typename Node , typename Key , class Compare >

static const Key * Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::min_key ( const NodePtr & node )

inlinestaticnoexcept

Definition at line 110 of file tpl_persistent_treap.H.

Referenced by Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::can_join().

◆ node_size()

template<typename Node , typename Key , class Compare >

static size_t Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::node_size ( const NodePtr & p )

inlinestaticnoexcept

Definition at line 105 of file tpl_persistent_treap.H.

Referenced by Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::is_valid_under(), Aleph::PersistentTreapSet< Key, Compare >::make_node(), Aleph::PersistentTreapMap< Key, T, Compare >::make_node(), Aleph::PersistentTreapSet< Key, Compare >::size(), and Aleph::PersistentTreapMap< Key, T, Compare >::size().

◆ rotate_left()

template<typename Node , typename Key , class Compare >

template<class Rebuild >

static NodePtr Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::rotate_left	(	const NodePtr &	node,
		const Rebuild &	rebuild
	)

inlinestatic

Definition at line 142 of file tpl_persistent_treap.H.

References Aleph::blossom_maximum_cardinality_matching().

Referenced by Aleph::PersistentTreapMap< Key, T, Compare >::insert_or_assign_rec(), Aleph::PersistentTreapSet< Key, Compare >::insert_rec(), and Aleph::PersistentTreapMap< Key, T, Compare >::insert_rec().

◆ rotate_right()

template<typename Node , typename Key , class Compare >

template<class Rebuild >

static NodePtr Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::rotate_right	(	const NodePtr &	node,
		const Rebuild &	rebuild
	)

inlinestatic

Definition at line 134 of file tpl_persistent_treap.H.

References Aleph::blossom_maximum_cardinality_matching().

Referenced by Aleph::PersistentTreapMap< Key, T, Compare >::insert_or_assign_rec(), Aleph::PersistentTreapSet< Key, Compare >::insert_rec(), and Aleph::PersistentTreapMap< Key, T, Compare >::insert_rec().

◆ split_rec()

template<typename Node , typename Key , class Compare >

template<class Rebuild >

static std::pair< NodePtr, NodePtr > Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::split_rec	(	const NodePtr &	node,
		const Key &	pivot,
		const Compare &	cmp,
		const Rebuild &	rebuild
	)

inlinestatic

Definition at line 203 of file tpl_persistent_treap.H.

References Aleph::blossom_maximum_cardinality_matching(), cmp(), and Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::split_rec().

Referenced by Aleph::PersistentTreapSet< Key, Compare >::split(), Aleph::PersistentTreapMap< Key, T, Compare >::split(), and Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::split_rec().

◆ verify_rec()

template<typename Node , typename Key , class Compare >

static bool Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::verify_rec	(	const NodePtr &	node,
		const Key *	lo,
		const Key *	hi,
		const Compare &	cmp,
		size_t &	count
	)

inlinestatic

Definition at line 233 of file tpl_persistent_treap.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), cmp(), Aleph::count(), and Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::verify_rec().

Referenced by Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::is_valid_under(), Aleph::PersistentTreapSet< Key, Compare >::verify(), Aleph::PersistentTreapMap< Key, T, Compare >::verify(), and Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::verify_rec().

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

tpl_persistent_treap.H

Public Types

Static Public Member Functions

Detailed Description

Member Typedef Documentation

◆ NodePtr

Member Function Documentation

◆ can_join()

◆ collect_keys()

◆ erase_rec()

◆ is_valid_under()

◆ join_nodes()

◆ max_key()

◆ min_key()

◆ node_size()

◆ rotate_left()

◆ rotate_right()

◆ split_rec()

◆ verify_rec()