Immutable ordered map backed by a path-copying treap. More...

#include <tpl_persistent_treap.H>

Collaboration diagram for Aleph::PersistentTreapMap< Key, T, Compare >:

Classes
struct	Node

Public Member Functions
	PersistentTreapMap (Compare cmp=Compare())
	Construct an empty persistent map.

bool	is_empty () const noexcept
	Return true when the map has no bindings.

size_t	size () const noexcept
	Return the number of key/value bindings in this version.

const T *	find (const Key &key) const
	Find a mapped value.

bool	contains (const Key &key) const
	Test whether `key` is present.

template<typename KArg , typename VArg > requires std::constructible_from<Key, KArg &&>
and std::constructible_from< T, VArg && > PersistentTreapMap	insert (KArg &&key, VArg &&value) const
	Return a new version with a binding inserted if absent.

template<typename KArg , typename VArg > requires std::constructible_from<Key, KArg &&>
and std::constructible_from< T, VArg && > PersistentTreapMap	insert_or_assign (KArg &&key, VArg &&value) const
	Return a new version with `key` assigned to `value`.

PersistentTreapMap	erase (const Key &key) const
	Return a new version without `key`.

std::pair< PersistentTreapMap, PersistentTreapMap >	split (const Key &pivot) const
	Split this version around `pivot`.

PersistentTreapMap	join (const PersistentTreapMap &right) const
	Join this version with `right`.

Array< Key >	keys () const
	Return all keys in sorted order.

Array< std::pair< Key, T > >	items () const
	Return all key/value bindings in sorted-key order.

bool	verify () const
	Verify treap, BST and cached-size invariants.

Static Public Member Functions
static PersistentTreapMap	join (const PersistentTreapMap &left, const PersistentTreapMap &right)
	Join two ordered, non-overlapping map versions.

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

using	NodeOps = detail::PersistentTreapNodeOps< Node, Key, Compare >

Private Member Functions
	PersistentTreapMap (NodePtr root, Compare cmp, const std::uint64_t next_priority)

Static Private Member Functions
static NodePtr	make_node (std::shared_ptr< const Key > key, std::shared_ptr< const T > value, const std::uint64_t priority, NodePtr left, NodePtr right)

static NodePtr	rebuild_node (const NodePtr &node, NodePtr left, NodePtr right)

static NodePtr	insert_rec (const NodePtr &node, std::shared_ptr< const Key > key, std::shared_ptr< const T > value, const std::uint64_t priority, const Compare &cmp, bool &inserted)

static NodePtr	insert_or_assign_rec (const NodePtr &node, std::shared_ptr< const Key > key, std::shared_ptr< const T > value, const std::uint64_t priority, const Compare &cmp, bool &inserted)

static void	collect_items (const NodePtr &node, Array< std::pair< Key, T > > &out)

Private Attributes
NodePtr	root_

Compare	cmp_

std::uint64_t	next_priority_ = 0

Detailed Description

template<typename Key, typename T, class Compare = Aleph::less<Key>>
class Aleph::PersistentTreapMap< Key, T, Compare >

Immutable ordered map backed by a path-copying treap.

Template Parameters

Key	Key type.
T	Mapped value type.
Compare	Strict weak ordering used for keys. Defaults to `Aleph::less<Key>`.

Definition at line 546 of file tpl_persistent_treap.H.

Member Typedef Documentation

◆ NodeOps

template<typename Key , typename T , class Compare = Aleph::less<Key>>

using Aleph::PersistentTreapMap< Key, T, Compare >::NodeOps = detail::PersistentTreapNodeOps<Node, Key, Compare>

private

Definition at line 559 of file tpl_persistent_treap.H.

◆ NodePtr

template<typename Key , typename T , class Compare = Aleph::less<Key>>

using Aleph::PersistentTreapMap< Key, T, Compare >::NodePtr = std::shared_ptr<const Node>

private

Definition at line 558 of file tpl_persistent_treap.H.

Constructor & Destructor Documentation

◆ PersistentTreapMap() [1/2]

template<typename Key , typename T , class Compare = Aleph::less<Key>>

Aleph::PersistentTreapMap< Key, T, Compare >::PersistentTreapMap	(	NodePtr	root,
		Compare	cmp,
		const std::uint64_t	next_priority
	)

inlineprivate

Definition at line 685 of file tpl_persistent_treap.H.

◆ PersistentTreapMap() [2/2]

template<typename Key , typename T , class Compare = Aleph::less<Key>>

Aleph::PersistentTreapMap< Key, T, Compare >::PersistentTreapMap ( Compare cmp = Compare() )

inlineexplicit

Construct an empty persistent map.

Parameters

cmp	Comparator used for key ordering.

Exceptions

Nothing unless copying cmp throws.

Definition at line 696 of file tpl_persistent_treap.H.

Member Function Documentation

◆ collect_items()

template<typename Key , typename T , class Compare = Aleph::less<Key>>

static void Aleph::PersistentTreapMap< Key, T, Compare >::collect_items	(	const NodePtr &	node,
		Array< std::pair< Key, T > > &	out
	)

inlinestaticprivate

Definition at line 675 of file tpl_persistent_treap.H.

References Aleph::PersistentTreapMap< Key, T, Compare >::collect_items(), and out.

Referenced by Aleph::PersistentTreapMap< Key, T, Compare >::collect_items(), and Aleph::PersistentTreapMap< Key, T, Compare >::items().

◆ contains()

template<typename Key , typename T , class Compare = Aleph::less<Key>>

bool Aleph::PersistentTreapMap< Key, T, Compare >::contains ( const Key & key ) const

inline

Test whether key is present.

Parameters

key	Key to search.

Returns: true if an equivalent key is stored.

Exceptions

Whatever Compare throws.

Definition at line 738 of file tpl_persistent_treap.H.

References Aleph::PersistentTreapMap< Key, T, Compare >::find().

◆ erase()

template<typename Key , typename T , class Compare = Aleph::less<Key>>

PersistentTreapMap Aleph::PersistentTreapMap< Key, T, Compare >::erase ( const Key & key ) const

inline

Return a new version without key.

Parameters

key	Key to erase.

Returns: New map version. If the key is absent, returns an unchanged version sharing the same root.

Exceptions

std::bad_alloc or whatever Compare throws.

Definition at line 794 of file tpl_persistent_treap.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PersistentTreapMap< Key, T, Compare >::cmp_, Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::erase_rec(), Aleph::PersistentTreapMap< Key, T, Compare >::next_priority_, Aleph::PersistentTreapMap< Key, T, Compare >::rebuild_node(), root(), and Aleph::PersistentTreapMap< Key, T, Compare >::root_.

Referenced by TEST().

◆ find()

template<typename Key , typename T , class Compare = Aleph::less<Key>>

const T * Aleph::PersistentTreapMap< Key, T, Compare >::find ( const Key & key ) const

inline

Find a mapped value.

Parameters

key	Key to search.

Returns: Pointer to the stored mapped value, or nullptr when absent. The pointer remains valid while this map version is alive.

Exceptions

Whatever Compare throws.

Definition at line 720 of file tpl_persistent_treap.H.

References Aleph::PersistentTreapMap< Key, T, Compare >::cmp_, Aleph::PersistentTreapMap< Key, T, Compare >::Node::key, Aleph::PersistentTreapMap< Key, T, Compare >::Node::left, Aleph::PersistentTreapMap< Key, T, Compare >::Node::right, Aleph::PersistentTreapMap< Key, T, Compare >::root_, and Aleph::PersistentTreapMap< Key, T, Compare >::Node::value.

Referenced by Aleph::PersistentTreapMap< Key, T, Compare >::contains(), and main().

◆ insert()

template<typename Key , typename T , class Compare = Aleph::less<Key>>

template<typename KArg , typename VArg >
requires std::constructible_from<Key, KArg &&>

and std::constructible_from< T, VArg && > PersistentTreapMap Aleph::PersistentTreapMap< Key, T, Compare >::insert	(	KArg &&	key,
		VArg &&	value
	)		const

inline

Return a new version with a binding inserted if absent.

Template Parameters

KArg	Type used to construct `Key`.
VArg	Type used to construct `T`.

Parameters

key	Key to insert.
value	Mapped value to insert.

Returns: New map version. If an equivalent key already exists, returns an unchanged version sharing the same root.

Exceptions

std::bad_alloc or whatever construction/comparison throws.

Definition at line 754 of file tpl_persistent_treap.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PersistentTreapMap< Key, T, Compare >::cmp_, Aleph::PersistentTreapMap< Key, T, Compare >::insert_rec(), Aleph::PersistentTreapMap< Key, T, Compare >::next_priority_, Aleph::detail::persistent_treap_priority(), root(), Aleph::PersistentTreapMap< Key, T, Compare >::root_, and value.

Referenced by main(), TEST(), TEST(), TEST(), and TEST().

◆ insert_or_assign()

template<typename Key , typename T , class Compare = Aleph::less<Key>>

template<typename KArg , typename VArg >
requires std::constructible_from<Key, KArg &&>

and std::constructible_from< T, VArg && > PersistentTreapMap Aleph::PersistentTreapMap< Key, T, Compare >::insert_or_assign	(	KArg &&	key,
		VArg &&	value
	)		const

inline

Return a new version with key assigned to value.

Template Parameters

KArg	Type used to construct `Key` when the key is absent.
VArg	Type used to construct `T`.

Parameters

key	Key to insert or update.
value	Mapped value for the returned version.

Returns: New map version with the binding present.

Exceptions

std::bad_alloc or whatever construction/comparison throws.

Definition at line 775 of file tpl_persistent_treap.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PersistentTreapMap< Key, T, Compare >::cmp_, Aleph::PersistentTreapMap< Key, T, Compare >::insert_or_assign_rec(), Aleph::PersistentTreapMap< Key, T, Compare >::next_priority_, Aleph::detail::persistent_treap_priority(), root(), Aleph::PersistentTreapMap< Key, T, Compare >::root_, and value.

Referenced by main(), TEST(), and TEST().

◆ insert_or_assign_rec()

template<typename Key , typename T , class Compare = Aleph::less<Key>>

static NodePtr Aleph::PersistentTreapMap< Key, T, Compare >::insert_or_assign_rec	(	const NodePtr &	node,
		std::shared_ptr< const Key >	key,
		std::shared_ptr< const T >	value,
		const std::uint64_t	priority,
		const Compare &	cmp,
		bool &	inserted
	)

inlinestaticprivate

Definition at line 636 of file tpl_persistent_treap.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), cmp(), Aleph::PersistentTreapMap< Key, T, Compare >::insert_or_assign_rec(), Aleph::PersistentTreapMap< Key, T, Compare >::make_node(), Aleph::PersistentTreapMap< Key, T, Compare >::rebuild_node(), Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::rotate_left(), Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::rotate_right(), and value.

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

◆ insert_rec()

template<typename Key , typename T , class Compare = Aleph::less<Key>>

static NodePtr Aleph::PersistentTreapMap< Key, T, Compare >::insert_rec	(	const NodePtr &	node,
		std::shared_ptr< const Key >	key,
		std::shared_ptr< const T >	value,
		const std::uint64_t	priority,
		const Compare &	cmp,
		bool &	inserted
	)

inlinestaticprivate

Definition at line 595 of file tpl_persistent_treap.H.

References Aleph::blossom_maximum_cardinality_matching(), cmp(), Aleph::PersistentTreapMap< Key, T, Compare >::insert_rec(), Aleph::PersistentTreapMap< Key, T, Compare >::make_node(), Aleph::PersistentTreapMap< Key, T, Compare >::rebuild_node(), Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::rotate_left(), Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::rotate_right(), and value.

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

◆ is_empty()

template<typename Key , typename T , class Compare = Aleph::less<Key>>

bool Aleph::PersistentTreapMap< Key, T, Compare >::is_empty ( ) const

inlinenoexcept

Return true when the map has no bindings.

Returns: true iff size() == 0.

Exceptions

Nothing.

Definition at line 706 of file tpl_persistent_treap.H.

References Aleph::PersistentTreapMap< Key, T, Compare >::root_.

◆ items()

template<typename Key , typename T , class Compare = Aleph::less<Key>>

Array< std::pair< Key, T > > Aleph::PersistentTreapMap< Key, T, Compare >::items ( ) const

inline

Return all key/value bindings in sorted-key order.

Returns: Aleph array with a copy of every binding.

Exceptions

std::bad_alloc or whatever copying Key or T throws.

Definition at line 865 of file tpl_persistent_treap.H.

References Aleph::PersistentTreapMap< Key, T, Compare >::collect_items(), out, Aleph::Array< T >::reserve(), Aleph::PersistentTreapMap< Key, T, Compare >::root_, and Aleph::PersistentTreapMap< Key, T, Compare >::size().

◆ join() [1/2]

template<typename Key , typename T , class Compare = Aleph::less<Key>>

static PersistentTreapMap Aleph::PersistentTreapMap< Key, T, Compare >::join	(	const PersistentTreapMap< Key, T, Compare > &	left,
		const PersistentTreapMap< Key, T, Compare > &	right
	)

inlinestatic

Join two ordered, non-overlapping map versions.

Parameters

left	Map whose keys must all be less than every key in `right`.
right	Map whose keys must all be greater than every key in `left`.

Returns: Joined map version.

Exceptions

std::domain_error	if `right` is not ordered under `left`'s comparator, or if the key ranges overlap or touch.
std::bad_alloc	if node allocation fails.
Whatever	`Compare` throws.

Definition at line 824 of file tpl_persistent_treap.H.

References ah_domain_error_unless, Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::can_join(), Aleph::PersistentTreapMap< Key, T, Compare >::cmp_, Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::is_valid_under(), Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::join_nodes(), Aleph::PersistentTreapMap< Key, T, Compare >::next_priority_, Aleph::PersistentTreapMap< Key, T, Compare >::rebuild_node(), and Aleph::PersistentTreapMap< Key, T, Compare >::root_.

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

◆ join() [2/2]

template<typename Key , typename T , class Compare = Aleph::less<Key>>

PersistentTreapMap Aleph::PersistentTreapMap< Key, T, Compare >::join ( const PersistentTreapMap< Key, T, Compare > & right ) const

inline

Join this version with right.

Parameters

right Map whose keys must all be greater than every key in this map.

Returns: Joined map version.

Exceptions

std::domain_error	if `right` is not ordered under this map's comparator, or if the key ranges overlap or touch.
std::bad_alloc	if node allocation fails.
Whatever	`Compare` throws.

Definition at line 843 of file tpl_persistent_treap.H.

References Aleph::PersistentTreapMap< Key, T, Compare >::join().

◆ keys()

template<typename Key , typename T , class Compare = Aleph::less<Key>>

Array< Key > Aleph::PersistentTreapMap< Key, T, Compare >::keys ( ) const

inline

Return all keys in sorted order.

Returns: Aleph array with a copy of every key.

Exceptions

std::bad_alloc or whatever copying Key throws.

Definition at line 852 of file tpl_persistent_treap.H.

References Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::collect_keys(), out, Aleph::Array< T >::reserve(), Aleph::PersistentTreapMap< Key, T, Compare >::root_, and Aleph::PersistentTreapMap< Key, T, Compare >::size().

◆ make_node()

template<typename Key , typename T , class Compare = Aleph::less<Key>>

static NodePtr Aleph::PersistentTreapMap< Key, T, Compare >::make_node	(	std::shared_ptr< const Key >	key,
		std::shared_ptr< const T >	value,
		const std::uint64_t	priority,
		NodePtr	left,
		NodePtr	right
	)

inlinestaticprivate

Definition at line 565 of file tpl_persistent_treap.H.

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

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

◆ rebuild_node()

template<typename Key , typename T , class Compare = Aleph::less<Key>>

static NodePtr Aleph::PersistentTreapMap< Key, T, Compare >::rebuild_node	(	const NodePtr &	node,
		NodePtr	left,
		NodePtr	right
	)

inlinestaticprivate

Definition at line 589 of file tpl_persistent_treap.H.

References Aleph::PersistentTreapMap< Key, T, Compare >::make_node().

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

◆ size()

template<typename Key , typename T , class Compare = Aleph::less<Key>>

size_t Aleph::PersistentTreapMap< Key, T, Compare >::size ( ) const

inlinenoexcept

Return the number of key/value bindings in this version.

Returns: Number of bindings.

Exceptions

Nothing.

Definition at line 712 of file tpl_persistent_treap.H.

References Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::node_size(), and Aleph::PersistentTreapMap< Key, T, Compare >::root_.

Referenced by Aleph::PersistentTreapMap< Key, T, Compare >::items(), Aleph::PersistentTreapMap< Key, T, Compare >::keys(), and Aleph::PersistentTreapMap< Key, T, Compare >::verify().

◆ split()

template<typename Key , typename T , class Compare = Aleph::less<Key>>

std::pair< PersistentTreapMap, PersistentTreapMap > Aleph::PersistentTreapMap< Key, T, Compare >::split ( const Key & pivot ) const

inline

Split this version around pivot.

Parameters

pivot Split key.

Returns: Pair {less, greater_equal} where the first map contains keys strictly less than pivot and the second contains the rest.

Exceptions

std::bad_alloc or whatever Compare throws.

Definition at line 808 of file tpl_persistent_treap.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PersistentTreapMap< Key, T, Compare >::cmp_, Aleph::PersistentTreapMap< Key, T, Compare >::next_priority_, Aleph::PersistentTreapMap< Key, T, Compare >::rebuild_node(), Aleph::PersistentTreapMap< Key, T, Compare >::root_, and Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::split_rec().

Referenced by TEST().

◆ verify()

template<typename Key , typename T , class Compare = Aleph::less<Key>>

bool Aleph::PersistentTreapMap< Key, T, Compare >::verify ( ) const

inline

Verify treap, BST and cached-size invariants.

Returns: true if the internal structure is consistent.

Exceptions

Nothing unless Compare throws.

Note: Intended for tests and diagnostics; it is O(n).

Definition at line 879 of file tpl_persistent_treap.H.

References Aleph::and, Aleph::PersistentTreapMap< Key, T, Compare >::cmp_, Aleph::count(), Aleph::PersistentTreapMap< Key, T, Compare >::root_, Aleph::PersistentTreapMap< Key, T, Compare >::size(), and Aleph::detail::PersistentTreapNodeOps< Node, Key, Compare >::verify_rec().

Referenced by TEST().

Member Data Documentation

◆ cmp_

template<typename Key , typename T , class Compare = Aleph::less<Key>>

Compare Aleph::PersistentTreapMap< Key, T, Compare >::cmp_

private

Definition at line 562 of file tpl_persistent_treap.H.

Referenced by Aleph::PersistentTreapMap< Key, T, Compare >::erase(), Aleph::PersistentTreapMap< Key, T, Compare >::find(), Aleph::PersistentTreapMap< Key, T, Compare >::insert(), Aleph::PersistentTreapMap< Key, T, Compare >::insert_or_assign(), Aleph::PersistentTreapMap< Key, T, Compare >::join(), Aleph::PersistentTreapMap< Key, T, Compare >::split(), and Aleph::PersistentTreapMap< Key, T, Compare >::verify().

◆ next_priority_

template<typename Key , typename T , class Compare = Aleph::less<Key>>

std::uint64_t Aleph::PersistentTreapMap< Key, T, Compare >::next_priority_ = 0

private

Definition at line 563 of file tpl_persistent_treap.H.

Referenced by Aleph::PersistentTreapMap< Key, T, Compare >::erase(), Aleph::PersistentTreapMap< Key, T, Compare >::insert(), Aleph::PersistentTreapMap< Key, T, Compare >::insert_or_assign(), Aleph::PersistentTreapMap< Key, T, Compare >::join(), and Aleph::PersistentTreapMap< Key, T, Compare >::split().

◆ root_

template<typename Key , typename T , class Compare = Aleph::less<Key>>

NodePtr Aleph::PersistentTreapMap< Key, T, Compare >::root_

private

Definition at line 561 of file tpl_persistent_treap.H.

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

tpl_persistent_treap.H

Classes

Public Member Functions

Static Public Member Functions

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ NodeOps

◆ NodePtr

Constructor & Destructor Documentation

◆ PersistentTreapMap() [1/2]

◆ PersistentTreapMap() [2/2]

Member Function Documentation

◆ collect_items()

◆ contains()

◆ erase()

◆ find()

◆ insert()

◆ insert_or_assign()

◆ insert_or_assign_rec()

◆ insert_rec()

◆ is_empty()

◆ items()

◆ join() [1/2]

◆ join() [2/2]

◆ keys()

◆ make_node()

◆ rebuild_node()

◆ size()

◆ split()

◆ verify()

Member Data Documentation

◆ cmp_

◆ next_priority_

◆ root_