Immutable vector backed by a 32-way bitmapped trie. More...

#include <tpl_persistent_vector.H>

Collaboration diagram for Aleph::PersistentVector< T >:

Classes
struct	Node

Public Member Functions
	PersistentVector () noexcept=default
	Construct an empty persistent vector.

bool	is_empty () const noexcept
	Return true when the vector has no values.

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

const T &	get (const size_t index) const
	Read a value by index.

const T &	operator[] (const size_t index) const
	Read a value by index.

PersistentVector	push_back (const T &value) const
	Return a new version with `value` appended by copy.

PersistentVector	push_back (T &&value) const
	Return a new version with `value` appended by move.

PersistentVector	set (const size_t index, const T &value) const
	Return a new version with one index replaced by copy.

PersistentVector	set (const size_t index, T &&value) const
	Return a new version with one index replaced by move.

PersistentVector	pop_back () const
	Return a new version without the last value.

Array< T >	to_array () const
	Return all values in an Aleph array.

bool	verify () const noexcept
	Verify trie shape and logical prefix invariants.

Static Public Member Functions
static constexpr size_t	branching_factor () noexcept
	Return the trie branching factor.

Private Types
using	ValuePtr = std::shared_ptr< const T >

using	NodePtr = std::shared_ptr< const Node >

Private Member Functions
	PersistentVector (NodePtr root, const size_t n, const size_t shift) noexcept

PersistentVector	push_back (ValuePtr value) const

PersistentVector	set (const size_t index, ValuePtr value) const

Static Private Member Functions
static size_t	child_index (const size_t index, const size_t shift) noexcept

static size_t	capacity_for_shift (const size_t shift) noexcept

static NodePtr	set_rec (const NodePtr &node, const size_t shift, const size_t index, ValuePtr value)

static bool	leaf_has_values (const std::shared_ptr< Node > &node) noexcept

static bool	internal_has_children (const std::shared_ptr< Node > &node) noexcept

static NodePtr	clear_rec (const NodePtr &node, const size_t shift, const size_t index)

static const T *	get_ptr (const NodePtr &root, size_t shift, const size_t index) noexcept

static size_t	count_values_rec (const NodePtr &node, const size_t shift, bool &ok) noexcept

Private Attributes
NodePtr	root_

size_t	size_ = 0

size_t	shift_ = 0

Static Private Attributes
static constexpr size_t	branch_bits = 5

static constexpr size_t	branch_factor = size_t{1} << branch_bits

static constexpr size_t	branch_mask = branch_factor - 1

Detailed Description

template<typename T>
class Aleph::PersistentVector< T >

Immutable vector backed by a 32-way bitmapped trie.

What is a Persistent Vector?

Unlike a standard std::vector which stores elements in a contiguous memory block and requires an O(N) copy to duplicate, a PersistentVector is structured as a shallow, wide tree (a Trie) where each node has up to 32 children. Because $32^6 > 10^9$, the tree depth never exceeds 6 levels for any realistic number of elements. Thus, index lookups and updates require at most 6 pointer dereferences, providing "effectively O(1)" performance.

"Persistence" in this context refers to immutability with history (structural sharing or path-copying), not disk storage. When you call push_back or set, the original vector is not mutated. Instead, the container copies only the O(log_32 N) nodes from the root down to the modified leaf. The other 31 branches at each level remain untouched and are shared between the old and new vectors via smart pointers (std::shared_ptr).

Benefits

Lock-free Concurrency: Because older versions are never overwritten, multiple threads can read safely without locks.
Move-only Types: Values are held inside std::shared_ptr<const T>. This allows the vector to store move-only types, and ensures that updating one index does not force the copy constructor of unchanged heavy elements.

Template Parameters

T	Value type stored by the vector. Values are held through `std::shared_ptr<const T>`, so updating one index does not copy untouched values and move-only `T` is supported for `push_back` and `set`.

Definition at line 94 of file tpl_persistent_vector.H.

Member Typedef Documentation

◆ NodePtr

template<typename T >

using Aleph::PersistentVector< T >::NodePtr = std::shared_ptr<const Node>

private

Definition at line 111 of file tpl_persistent_vector.H.

◆ ValuePtr

template<typename T >

using Aleph::PersistentVector< T >::ValuePtr = std::shared_ptr<const T>

private

Definition at line 100 of file tpl_persistent_vector.H.

Constructor & Destructor Documentation

◆ PersistentVector() [1/2]

template<typename T >

Aleph::PersistentVector< T >::PersistentVector	(	NodePtr	root,
		const size_t	n,
		const size_t	shift
	)

inlineexplicitprivatenoexcept

Definition at line 236 of file tpl_persistent_vector.H.

◆ PersistentVector() [2/2]

template<typename T >

Aleph::PersistentVector< T >::PersistentVector ( )

defaultnoexcept

Construct an empty persistent vector.

Exceptions

Nothing.

Referenced by Aleph::PersistentVector< T >::pop_back(), Aleph::PersistentVector< T >::push_back(), and Aleph::PersistentVector< T >::set().

Member Function Documentation

◆ branching_factor()

template<typename T >

static constexpr size_t Aleph::PersistentVector< T >::branching_factor ( )

inlinestaticconstexprnoexcept

Return the trie branching factor.

Returns: Always 32.

Exceptions

Nothing.

Definition at line 252 of file tpl_persistent_vector.H.

References Aleph::PersistentVector< T >::branch_factor.

◆ capacity_for_shift()

template<typename T >

static size_t Aleph::PersistentVector< T >::capacity_for_shift ( const size_t shift )

inlinestaticprivatenoexcept

Definition at line 122 of file tpl_persistent_vector.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::PersistentVector< T >::branch_bits.

Referenced by Aleph::PersistentVector< T >::pop_back(), Aleph::PersistentVector< T >::push_back(), and Aleph::PersistentVector< T >::verify().

◆ child_index()

template<typename T >

static size_t Aleph::PersistentVector< T >::child_index	(	const size_t	index,
		const size_t	shift
	)

inlinestaticprivatenoexcept

Definition at line 117 of file tpl_persistent_vector.H.

References Aleph::PersistentVector< T >::branch_mask.

Referenced by Aleph::PersistentVector< T >::clear_rec(), Aleph::PersistentVector< T >::get_ptr(), and Aleph::PersistentVector< T >::set_rec().

◆ clear_rec()

template<typename T >

static NodePtr Aleph::PersistentVector< T >::clear_rec	(	const NodePtr &	node,
		const size_t	shift,
		const size_t	index
	)

inlinestaticprivate

Definition at line 167 of file tpl_persistent_vector.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PersistentVector< T >::branch_bits, Aleph::PersistentVector< T >::child_index(), Aleph::PersistentVector< T >::clear_rec(), Aleph::copy(), Aleph::PersistentVector< T >::internal_has_children(), and Aleph::PersistentVector< T >::leaf_has_values().

Referenced by Aleph::PersistentVector< T >::clear_rec(), and Aleph::PersistentVector< T >::pop_back().

◆ count_values_rec()

template<typename T >

static size_t Aleph::PersistentVector< T >::count_values_rec	(	const NodePtr &	node,
		const size_t	shift,
		bool &	ok
	)

inlinestaticprivatenoexcept

Definition at line 204 of file tpl_persistent_vector.H.

References Aleph::PersistentVector< T >::branch_bits, Aleph::count(), Aleph::PersistentVector< T >::count_values_rec(), and value.

Referenced by Aleph::PersistentVector< T >::count_values_rec(), and Aleph::PersistentVector< T >::verify().

◆ get()

template<typename T >

const T & Aleph::PersistentVector< T >::get ( const size_t index ) const

inline

Read a value by index.

Parameters

index Zero-based index.

Returns: Constant reference to the stored value.

Exceptions

std::out_of_range if index >= size().

Definition at line 274 of file tpl_persistent_vector.H.

References ah_logic_error_if, ah_out_of_range_error_if, Aleph::PersistentVector< T >::get_ptr(), Aleph::PersistentVector< T >::root_, Aleph::PersistentVector< T >::shift_, Aleph::PersistentVector< T >::size_, and value.

Referenced by main(), Aleph::PersistentVector< T >::operator[](), TEST(), TEST(), TEST(), and Aleph::PersistentVector< T >::to_array().

◆ get_ptr()

template<typename T >

static const T * Aleph::PersistentVector< T >::get_ptr	(	const NodePtr &	root,
		size_t	shift,
		const size_t	index
	)

inlinestaticprivatenoexcept

Definition at line 188 of file tpl_persistent_vector.H.

References Aleph::and, Aleph::PersistentVector< T >::branch_bits, Aleph::PersistentVector< T >::child_index(), Aleph::PersistentVector< T >::Node::children, root(), value, and Aleph::PersistentVector< T >::Node::values.

Referenced by Aleph::PersistentVector< T >::get(), and Aleph::PersistentVector< T >::verify().

◆ internal_has_children()

template<typename T >

static bool Aleph::PersistentVector< T >::internal_has_children ( const std::shared_ptr< Node > & node )

inlinestaticprivatenoexcept

Definition at line 159 of file tpl_persistent_vector.H.

Referenced by Aleph::PersistentVector< T >::clear_rec().

◆ is_empty()

template<typename T >

bool Aleph::PersistentVector< T >::is_empty ( ) const

inlinenoexcept

Return true when the vector has no values.

Returns: true iff size() == 0.

Exceptions

Nothing.

Definition at line 261 of file tpl_persistent_vector.H.

References Aleph::PersistentVector< T >::size_.

Referenced by Aleph::PersistentVector< T >::pop_back(), TEST(), and TEST().

◆ leaf_has_values()

template<typename T >

static bool Aleph::PersistentVector< T >::leaf_has_values ( const std::shared_ptr< Node > & node )

inlinestaticprivatenoexcept

Definition at line 151 of file tpl_persistent_vector.H.

References value.

Referenced by Aleph::PersistentVector< T >::clear_rec().

◆ operator[]()

template<typename T >

const T & Aleph::PersistentVector< T >::operator[] ( const size_t index ) const

inline

Read a value by index.

Parameters

index Zero-based index.

Returns: Constant reference to the stored value.

Exceptions

std::out_of_range if index >= size().

Definition at line 289 of file tpl_persistent_vector.H.

References Aleph::PersistentVector< T >::get().

◆ pop_back()

template<typename T >

PersistentVector Aleph::PersistentVector< T >::pop_back ( ) const

inline

Return a new version without the last value.

Returns: New vector version with size decreased by one.

Exceptions

std::underflow_error	if the vector is empty.
std::bad_alloc	if a path-copy node allocation fails.

Definition at line 349 of file tpl_persistent_vector.H.

References Aleph::PersistentVector< T >::PersistentVector(), ah_underflow_error_if, Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::PersistentVector< T >::branch_bits, Aleph::PersistentVector< T >::capacity_for_shift(), Aleph::PersistentVector< T >::clear_rec(), Aleph::PersistentVector< T >::is_empty(), root(), Aleph::PersistentVector< T >::root_, Aleph::PersistentVector< T >::shift_, and Aleph::PersistentVector< T >::size_.

Referenced by TEST(), and TEST().

◆ push_back() [1/3]

template<typename T >

PersistentVector Aleph::PersistentVector< T >::push_back ( const T & value ) const

inline

Return a new version with value appended by copy.

Parameters

value Value to append.

Returns: New vector version with size increased by one.

Exceptions

std::length_error	if the vector cannot grow further.
std::bad_alloc	or whatever copying `T` throws.

Definition at line 300 of file tpl_persistent_vector.H.

References Aleph::PersistentVector< T >::push_back(), and value.

Referenced by main(), Aleph::PersistentVector< T >::push_back(), Aleph::PersistentVector< T >::push_back(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ push_back() [2/3]

template<typename T >

PersistentVector Aleph::PersistentVector< T >::push_back ( T && value ) const

inline

Return a new version with value appended by move.

Parameters

value Value to move into the returned version.

Returns: New vector version with size increased by one.

Exceptions

std::length_error	if the vector cannot grow further.
std::bad_alloc	or whatever moving `T` throws.

Definition at line 311 of file tpl_persistent_vector.H.

References Aleph::PersistentVector< T >::push_back(), and value.

◆ push_back() [3/3]

template<typename T >

PersistentVector Aleph::PersistentVector< T >::push_back ( ValuePtr value ) const

inlineprivate

Definition at line 413 of file tpl_persistent_vector.H.

References Aleph::PersistentVector< T >::PersistentVector(), ah_length_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::PersistentVector< T >::branch_bits, Aleph::PersistentVector< T >::capacity_for_shift(), root(), Aleph::PersistentVector< T >::root_, Aleph::PersistentVector< T >::set_rec(), Aleph::PersistentVector< T >::shift_, Aleph::PersistentVector< T >::size_, and value.

◆ set() [1/3]

template<typename T >

PersistentVector Aleph::PersistentVector< T >::set	(	const size_t	index,
		const T &	value
	)		const

inline

Return a new version with one index replaced by copy.

Parameters

index	Index to replace.
value	New value.

Returns: New vector version with the same size.

Exceptions

std::out_of_range	if `index >= size()`.
std::bad_alloc	or whatever copying `T` throws.

Definition at line 323 of file tpl_persistent_vector.H.

References ah_out_of_range_error_if, Aleph::PersistentVector< T >::set(), Aleph::PersistentVector< T >::size_, and value.

Referenced by main(), Aleph::PersistentVector< T >::set(), Aleph::PersistentVector< T >::set(), TEST(), and TEST().

◆ set() [2/3]

template<typename T >

PersistentVector Aleph::PersistentVector< T >::set	(	const size_t	index,
		T &&	value
	)		const

inline

Return a new version with one index replaced by move.

Parameters

index	Index to replace.
value	New value.

Returns: New vector version with the same size.

Exceptions

std::out_of_range	if `index >= size()`.
std::bad_alloc	or whatever moving `T` throws.

Definition at line 337 of file tpl_persistent_vector.H.

References ah_out_of_range_error_if, Aleph::PersistentVector< T >::set(), Aleph::PersistentVector< T >::size_, and value.

◆ set() [3/3]

template<typename T >

PersistentVector Aleph::PersistentVector< T >::set	(	const size_t	index,
		ValuePtr	value
	)		const

inlineprivate

Definition at line 437 of file tpl_persistent_vector.H.

References Aleph::PersistentVector< T >::PersistentVector(), ah_out_of_range_error_if, Aleph::PersistentVector< T >::root_, Aleph::PersistentVector< T >::set_rec(), Aleph::PersistentVector< T >::shift_, Aleph::PersistentVector< T >::size_, and value.

◆ set_rec()

template<typename T >

static NodePtr Aleph::PersistentVector< T >::set_rec	(	const NodePtr &	node,
		const size_t	shift,
		const size_t	index,
		ValuePtr	value
	)

inlinestaticprivate

Definition at line 130 of file tpl_persistent_vector.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PersistentVector< T >::branch_bits, Aleph::PersistentVector< T >::child_index(), Aleph::copy(), Aleph::PersistentVector< T >::set_rec(), and value.

Referenced by Aleph::PersistentVector< T >::push_back(), Aleph::PersistentVector< T >::set(), and Aleph::PersistentVector< T >::set_rec().

◆ size()

template<typename T >

size_t Aleph::PersistentVector< T >::size ( ) const

inlinenoexcept

Return the number of values in this version.

Returns: Logical vector length.

Exceptions

Nothing.

Definition at line 267 of file tpl_persistent_vector.H.

References Aleph::PersistentVector< T >::size_.

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

◆ to_array()

template<typename T >

Array< T > Aleph::PersistentVector< T >::to_array ( ) const

inline

Return all values in an Aleph array.

Returns: Array containing a copy of every value in index order.

Exceptions

std::bad_alloc or whatever copying T throws.

Note: T must also satisfy Array<T>'s movable-value requirements.

Definition at line 375 of file tpl_persistent_vector.H.

References Aleph::PersistentVector< T >::get(), out, Aleph::Array< T >::reserve(), Aleph::PersistentVector< T >::size_, and value.

Referenced by TEST(), and TEST().

◆ verify()

template<typename T >

bool Aleph::PersistentVector< T >::verify ( ) const

inlinenoexcept

Verify trie shape and logical prefix invariants.

Returns: true if the internal structure is consistent.

Exceptions

Nothing.

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

Definition at line 394 of file tpl_persistent_vector.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::PersistentVector< T >::capacity_for_shift(), Aleph::count(), Aleph::PersistentVector< T >::count_values_rec(), Aleph::PersistentVector< T >::get_ptr(), Aleph::PersistentVector< T >::root_, Aleph::PersistentVector< T >::shift_, and Aleph::PersistentVector< T >::size_.

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

Member Data Documentation

◆ branch_bits

template<typename T >

constexpr size_t Aleph::PersistentVector< T >::branch_bits = 5

staticconstexprprivate

Definition at line 96 of file tpl_persistent_vector.H.

Referenced by Aleph::PersistentVector< T >::capacity_for_shift(), Aleph::PersistentVector< T >::clear_rec(), Aleph::PersistentVector< T >::count_values_rec(), Aleph::PersistentVector< T >::get_ptr(), Aleph::PersistentVector< T >::pop_back(), Aleph::PersistentVector< T >::push_back(), and Aleph::PersistentVector< T >::set_rec().

◆ branch_factor

template<typename T >

constexpr size_t Aleph::PersistentVector< T >::branch_factor = size_t{1} << branch_bits

staticconstexprprivate

Definition at line 97 of file tpl_persistent_vector.H.

Referenced by Aleph::PersistentVector< T >::branching_factor().

◆ branch_mask

template<typename T >

constexpr size_t Aleph::PersistentVector< T >::branch_mask = branch_factor - 1

staticconstexprprivate

Definition at line 98 of file tpl_persistent_vector.H.

Referenced by Aleph::PersistentVector< T >::child_index().

◆ root_

template<typename T >

NodePtr Aleph::PersistentVector< T >::root_

private

Definition at line 113 of file tpl_persistent_vector.H.

Referenced by Aleph::PersistentVector< T >::get(), Aleph::PersistentVector< T >::pop_back(), Aleph::PersistentVector< T >::push_back(), Aleph::PersistentVector< T >::set(), and Aleph::PersistentVector< T >::verify().

◆ shift_

template<typename T >

size_t Aleph::PersistentVector< T >::shift_ = 0

private

Definition at line 115 of file tpl_persistent_vector.H.

Referenced by Aleph::PersistentVector< T >::get(), Aleph::PersistentVector< T >::pop_back(), Aleph::PersistentVector< T >::push_back(), Aleph::PersistentVector< T >::set(), and Aleph::PersistentVector< T >::verify().

◆ size_

template<typename T >

size_t Aleph::PersistentVector< T >::size_ = 0

private

Definition at line 114 of file tpl_persistent_vector.H.

Referenced by Aleph::PersistentVector< T >::get(), Aleph::PersistentVector< T >::is_empty(), Aleph::PersistentVector< T >::pop_back(), Aleph::PersistentVector< T >::push_back(), Aleph::PersistentVector< T >::set(), Aleph::PersistentVector< T >::set(), Aleph::PersistentVector< T >::set(), Aleph::PersistentVector< T >::size(), Aleph::PersistentVector< T >::to_array(), and Aleph::PersistentVector< T >::verify().

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

tpl_persistent_vector.H

Classes

Public Member Functions

Static Public Member Functions

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

What is a Persistent Vector?

Benefits

Member Typedef Documentation

◆ NodePtr

◆ ValuePtr

Constructor & Destructor Documentation

◆ PersistentVector() [1/2]

◆ PersistentVector() [2/2]

Member Function Documentation

◆ branching_factor()

◆ capacity_for_shift()

◆ child_index()

◆ clear_rec()

◆ count_values_rec()

◆ get()

◆ get_ptr()

◆ internal_has_children()

◆ is_empty()

◆ leaf_has_values()

◆ operator[]()

◆ pop_back()

◆ push_back() [1/3]

◆ push_back() [2/3]

◆ push_back() [3/3]

◆ set() [1/3]

◆ set() [2/3]

◆ set() [3/3]

◆ set_rec()

◆ size()

◆ to_array()

◆ verify()

Member Data Documentation

◆ branch_bits

◆ branch_factor

◆ branch_mask

◆ root_

◆ shift_

◆ size_