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

#include <tpl_persistent_treap.H>

Collaboration diagram for Aleph::PersistentTreapSet< Key, Compare >:

Classes
struct	Node

Public Member Functions
	PersistentTreapSet (Compare cmp=Compare())
	Construct an empty persistent set.

bool	is_empty () const noexcept
	Return true when the set has no keys.

size_t	size () const noexcept
	Return the number of keys stored in this version.

const Key *	find (const Key &key) const
	Find a key equivalent to `key`.

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

PersistentTreapSet	insert (const Key &key) const
	Return a new version with `key` inserted by copy.

PersistentTreapSet	insert (Key &&key) const
	Return a new version with `key` inserted by move.

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

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

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

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

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

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

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

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

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

Static Private Member Functions
static NodePtr	make_node (std::shared_ptr< const Key > key, 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, const std::uint64_t priority, const Compare &cmp, bool &inserted)

Private Attributes
NodePtr	root_

Compare	cmp_

std::uint64_t	next_priority_ = 0

Detailed Description

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

Immutable ordered set backed by a path-copying treap.

Template Parameters

Key	Key type stored by the set.
Compare	Strict weak ordering used for keys. Defaults to `Aleph::less<Key>`.

Definition at line 282 of file tpl_persistent_treap.H.

Member Typedef Documentation

◆ NodeOps

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

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

private

Definition at line 294 of file tpl_persistent_treap.H.

◆ NodePtr

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

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

private

Definition at line 293 of file tpl_persistent_treap.H.

Constructor & Destructor Documentation

◆ PersistentTreapSet() [1/2]

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

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

inlineprivate

Definition at line 363 of file tpl_persistent_treap.H.

◆ PersistentTreapSet() [2/2]

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

Aleph::PersistentTreapSet< Key, Compare >::PersistentTreapSet ( Compare cmp = Compare() )

inlineexplicit

Construct an empty persistent set.

Parameters

cmp	Comparator used for key ordering.

Exceptions

Nothing unless copying cmp throws.

Definition at line 374 of file tpl_persistent_treap.H.

Member Function Documentation

◆ contains()

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

bool Aleph::PersistentTreapSet< Key, 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 416 of file tpl_persistent_treap.H.

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

Referenced by main(), and TEST().

◆ erase()

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

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

inline

Return a new version without key.

Parameters

key	Key to erase.

Returns: New set 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 459 of file tpl_persistent_treap.H.

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

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

◆ find()

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

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

inline

Find a key equivalent to key.

Parameters

key	Key to search.

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

Exceptions

Whatever Compare throws.

Definition at line 398 of file tpl_persistent_treap.H.

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

Referenced by Aleph::PersistentTreapSet< Key, Compare >::contains().

◆ insert() [1/2]

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

PersistentTreapSet Aleph::PersistentTreapSet< Key, Compare >::insert ( const Key & key ) const

inline

Return a new version with key inserted by copy.

Parameters

key	Key to insert.

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

Exceptions

std::bad_alloc or whatever Compare/Key copy construction throws.

Definition at line 427 of file tpl_persistent_treap.H.

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

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

◆ insert() [2/2]

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

PersistentTreapSet Aleph::PersistentTreapSet< Key, Compare >::insert ( Key && key ) const

inline

Return a new version with key inserted by move.

Parameters

key	Key to move into the new version.

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

Exceptions

std::bad_alloc or whatever Compare/Key move construction throws.

Definition at line 443 of file tpl_persistent_treap.H.

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

◆ insert_rec()

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

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

inlinestaticprivate

Definition at line 327 of file tpl_persistent_treap.H.

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

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

◆ is_empty()

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

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

inlinenoexcept

Return true when the set has no keys.

Returns: true iff size() == 0.

Exceptions

Nothing.

Definition at line 384 of file tpl_persistent_treap.H.

References Aleph::PersistentTreapSet< Key, Compare >::root_.

Referenced by TEST().

◆ join() [1/2]

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

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

inlinestatic

Join two ordered, non-overlapping set versions.

Parameters

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

Returns: Joined set 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 489 of file tpl_persistent_treap.H.

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

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

◆ join() [2/2]

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

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

inline

Join this version with right.

Parameters

right Set whose keys must all be greater than every key in this set.

Returns: Joined set version.

Exceptions

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

Definition at line 508 of file tpl_persistent_treap.H.

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

◆ keys()

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

Array< Key > Aleph::PersistentTreapSet< Key, 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 517 of file tpl_persistent_treap.H.

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

Referenced by TEST().

◆ make_node()

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

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

inlinestaticprivate

Definition at line 300 of file tpl_persistent_treap.H.

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

Referenced by Aleph::PersistentTreapSet< Key, Compare >::insert_rec(), and Aleph::PersistentTreapSet< Key, Compare >::rebuild_node().

◆ rebuild_node()

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

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

inlinestaticprivate

Definition at line 322 of file tpl_persistent_treap.H.

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

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

◆ size()

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

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

inlinenoexcept

Return the number of keys stored in this version.

Returns: Number of keys.

Exceptions

Nothing.

Definition at line 390 of file tpl_persistent_treap.H.

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

Referenced by Aleph::PersistentTreapSet< Key, Compare >::keys(), and Aleph::PersistentTreapSet< Key, Compare >::verify().

◆ split()

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

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

inline

Split this version around pivot.

Parameters

pivot Split key.

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

Exceptions

std::bad_alloc or whatever Compare throws.

Definition at line 473 of file tpl_persistent_treap.H.

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

Referenced by TEST().

◆ verify()

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

bool Aleph::PersistentTreapSet< Key, 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 531 of file tpl_persistent_treap.H.

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

Referenced by TEST(), and TEST().

Member Data Documentation

◆ cmp_

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

Compare Aleph::PersistentTreapSet< Key, Compare >::cmp_

private

Definition at line 297 of file tpl_persistent_treap.H.

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

◆ next_priority_

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

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

private

Definition at line 298 of file tpl_persistent_treap.H.

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

◆ root_

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

NodePtr Aleph::PersistentTreapSet< Key, Compare >::root_

private

Definition at line 296 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

◆ PersistentTreapSet() [1/2]

◆ PersistentTreapSet() [2/2]

Member Function Documentation

◆ contains()

◆ erase()

◆ find()

◆ insert() [1/2]

◆ insert() [2/2]

◆ insert_rec()

◆ is_empty()

◆ join() [1/2]

◆ join() [2/2]

◆ keys()

◆ make_node()

◆ rebuild_node()

◆ size()

◆ split()

◆ verify()

Member Data Documentation

◆ cmp_

◆ next_priority_

◆ root_