Aleph::PatriciaMap< UInt, T > Class Template Reference

Compressed bitwise map for unsigned integral keys. More...

#include <tpl_patricia_trie.H>

Collaboration diagram for Aleph::PatriciaMap< UInt, T >:

Classes
struct	Node

Public Types
using	Key = UInt
	Key type stored by the map.
using	Value = T
	Mapped value type stored at each leaf.

Public Member Functions
	PatriciaMap ()=default
	Construct an empty map.
	~PatriciaMap ()=default
	Destructor.
	PatriciaMap (const PatriciaMap &other)
	Deep-copy constructor.
PatriciaMap &	operator= (const PatriciaMap &other)
	Deep-copy assignment.
	PatriciaMap (PatriciaMap &&other) noexcept
	Move constructor.
PatriciaMap &	operator= (PatriciaMap &&other) noexcept
	Move assignment.
size_t	size () const noexcept
	Return the number of stored key-value pairs.
bool	is_empty () const noexcept
	Check whether the map has no key-value pairs.
void	clear () noexcept
	Remove every key-value pair from the map.
bool	insert (const Key key, const Value &value)
	Insert key with a copy of value, only if key is absent.
bool	insert (const Key key, Value &&value)
	Insert key with value moved in, only if key is absent.
void	insert_or_assign (const Key key, Value value)
	Insert key or overwrite the mapped value if key exists.
bool	erase (const Key key) noexcept
	Remove key if present.
bool	contains (const Key key) const noexcept
	Check whether key is stored.
const Value *	find (const Key key) const noexcept
	Look up key.
Value *	find (const Key key) noexcept
	Mutable lookup overload.
Array< Key >	keys () const
	Return all stored keys.
bool	check_invariants () const noexcept
	Verify structural invariants recursively.

Static Public Attributes
static constexpr size_t	bit_width = std::numeric_limits<Key>::digits
	Number of significant bits in Key.

Private Types
using	Detail = patricia_trie_detail::Bitwise_Trie_Utils< Key >

Private Member Functions
template<typename U >
bool	insert_impl (const Key key, U &&value)

Static Private Member Functions
static std::unique_ptr< Node >	clone_node (const Node *src)

Private Attributes
std::unique_ptr< Node >	root_
size_t	size_ = 0

Detailed Description

template<typename UInt, typename T>
requires (std::is_integral_v<UInt> and std::is_unsigned_v<UInt> and not std::is_same_v<UInt, bool>)
class Aleph::PatriciaMap< UInt, T >

Compressed bitwise map for unsigned integral keys.

PatriciaMap is the mapped-value counterpart of PatriciaSet. It stores unique fixed-width unsigned integer keys and one value per key. Internal nodes only record the first discriminating bit; leaves store the complete key and its associated value.

Template Parameters

UInt	Unsigned integral key type. bool is rejected because it has only two values and does not benefit from a trie representation.
T	Mapped value type. Must be move-constructible for insertion and copy-constructible only if the map itself is copied.

Definition at line 547 of file tpl_patricia_trie.H.

Member Typedef Documentation

Detail

template<typename UInt , typename T >

using Aleph::PatriciaMap< UInt, T >::Detail = patricia_trie_detail::Bitwise_Trie_Utils<Key>

private

Definition at line 576 of file tpl_patricia_trie.H.

Key

template<typename UInt , typename T >

using Aleph::PatriciaMap< UInt, T >::Key = UInt

Key type stored by the map.

Definition at line 551 of file tpl_patricia_trie.H.

Value

template<typename UInt , typename T >

using Aleph::PatriciaMap< UInt, T >::Value = T

Mapped value type stored at each leaf.

Definition at line 554 of file tpl_patricia_trie.H.

Constructor & Destructor Documentation

PatriciaMap() [1/3]

template<typename UInt , typename T >

Aleph::PatriciaMap< UInt, T >::PatriciaMap ( )

default

Construct an empty map.

Exceptions

Nothing.

~PatriciaMap()

template<typename UInt , typename T >

Aleph::PatriciaMap< UInt, T >::~PatriciaMap ( )

default

Destructor.

Recursively releases every node.

Exceptions

Nothing.

PatriciaMap() [2/3]

template<typename UInt , typename T >

Aleph::PatriciaMap< UInt, T >::PatriciaMap ( const PatriciaMap< UInt, T > &  other )

inline

Deep-copy constructor.

Parameters

[in]

other

Map to copy.

Exceptions

Whatever

T's copy constructor throws, or std::bad_alloc.

Definition at line 636 of file tpl_patricia_trie.H.

PatriciaMap() [3/3]

template<typename UInt , typename T >

Aleph::PatriciaMap< UInt, T >::PatriciaMap ( PatriciaMap< UInt, T > &&  other )

inlinenoexcept

Move constructor.

Parameters

[in,out]

other

Source map, left empty.

Exceptions

Nothing.

Definition at line 661 of file tpl_patricia_trie.H.

References Aleph::blossom_maximum_cardinality_matching().

Member Function Documentation

check_invariants()

template<typename UInt , typename T >

bool Aleph::PatriciaMap< UInt, T >::check_invariants ( ) const

inlinenoexcept

Verify structural invariants recursively.

Checks that internal nodes have two children and no value, internal bit indexes strictly increase down every path, each child subtree matches the routing bit used to reach it, every leaf has a value, and the number of leaves equals size().

Returns

true iff all invariants hold.

Exceptions

Nothing.

Definition at line 820 of file tpl_patricia_trie.H.

References Aleph::and, and Aleph::blossom_maximum_cardinality_matching().

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

clear()

template<typename UInt , typename T >

void Aleph::PatriciaMap< UInt, T >::clear ( )

inlinenoexcept

Remove every key-value pair from the map.

Exceptions

Nothing.

Definition at line 704 of file tpl_patricia_trie.H.

clone_node()

template<typename UInt , typename T >

static std::unique_ptr< Node > Aleph::PatriciaMap< UInt, T >::clone_node ( const Node *  src )

inlinestaticprivate

Definition at line 578 of file tpl_patricia_trie.H.

References Aleph::blossom_maximum_cardinality_matching().

contains()

template<typename UInt , typename T >

bool Aleph::PatriciaMap< UInt, T >::contains ( const Key  key ) const

inlinenoexcept

Check whether key is stored.

Parameters

[in]

key

Key to query.

Returns

true if key is present.

Exceptions

Nothing.

Definition at line 768 of file tpl_patricia_trie.H.

References Aleph::find().

Referenced by TEST(), and TEST().

erase()

template<typename UInt , typename T >

bool Aleph::PatriciaMap< UInt, T >::erase ( const Key  key )

inlinenoexcept

Remove key if present.

Parameters

[in]

key

Key to erase.

Returns

true if erased, false if absent.

Exceptions

Nothing.

Definition at line 758 of file tpl_patricia_trie.H.

find() [1/2]

template<typename UInt , typename T >

const Value * Aleph::PatriciaMap< UInt, T >::find ( const Key  key ) const

inlinenoexcept

Look up key.

Parameters

[in]

key

Key to look up.

Returns

Pointer to the stored value if key is present, nullptr otherwise. Valid until the next non-const operation on this map.

Exceptions

Nothing.

Definition at line 779 of file tpl_patricia_trie.H.

References Aleph::and, Aleph::PatriciaMap< UInt, T >::Node::key, and Aleph::PatriciaMap< UInt, T >::Node::value.

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

find() [2/2]

template<typename UInt , typename T >

Value * Aleph::PatriciaMap< UInt, T >::find ( const Key  key )

inlinenoexcept

Mutable lookup overload.

Parameters

[in]

key

Key to look up.

Returns

Mutable pointer to the stored value if key is present, nullptr otherwise. Valid until the next non-const operation on this map.

Exceptions

Nothing.

Definition at line 792 of file tpl_patricia_trie.H.

References Aleph::and, Aleph::PatriciaMap< UInt, T >::Node::key, and Aleph::PatriciaMap< UInt, T >::Node::value.

insert() [1/2]

template<typename UInt , typename T >

bool Aleph::PatriciaMap< UInt, T >::insert ( const Key  key, const Value &  value  )

inline

Insert key with a copy of value, only if key is absent.

Parameters

[in]	key	Key to insert.
[in]	value	Value to copy into the new leaf.

Returns

true if inserted, false if key was already present.

Exceptions

Whatever

T's copy constructor throws, or std::bad_alloc.

Definition at line 717 of file tpl_patricia_trie.H.

References value.

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

insert() [2/2]

template<typename UInt , typename T >

bool Aleph::PatriciaMap< UInt, T >::insert ( const Key  key, Value &&  value  )

inline

Insert key with value moved in, only if key is absent.

Parameters

[in]	key	Key to insert.
[in,out]	value	Value to move into the new leaf.

Returns

true if inserted, false if key was already present.

Exceptions

Whatever

T's move constructor throws, or std::bad_alloc.

Warning

If key is already present, value is left untouched. The duplicate check happens before the value is forwarded.

Definition at line 732 of file tpl_patricia_trie.H.

References value.

insert_impl()

template<typename UInt , typename T >

template<typename U >

bool Aleph::PatriciaMap< UInt, T >::insert_impl ( const Key  key, U &&  value  )

inlineprivate

Definition at line 594 of file tpl_patricia_trie.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), and value.

insert_or_assign()

template<typename UInt , typename T >

void Aleph::PatriciaMap< UInt, T >::insert_or_assign ( const Key  key, Value  value  )

inline

Insert key or overwrite the mapped value if key exists.

Parameters

[in]	key	Key to insert or update.
[in]	value	New value. It is moved into place.

Exceptions

Whatever

T's move/copy constructor or move assignment throws, or std::bad_alloc.

Definition at line 744 of file tpl_patricia_trie.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::find(), and value.

Referenced by TEST(), and TEST().

is_empty()

template<typename UInt , typename T >

bool Aleph::PatriciaMap< UInt, T >::is_empty ( ) const

inlinenoexcept

Check whether the map has no key-value pairs.

Returns

true iff size() == 0.

Exceptions

Nothing.

Definition at line 696 of file tpl_patricia_trie.H.

Referenced by TEST(), and TEST().

keys()

template<typename UInt , typename T >

Array< Key > Aleph::PatriciaMap< UInt, T >::keys ( ) const

inline

Return all stored keys.

Returns

Independent Array containing every key in unspecified order.

Exceptions

std::bad_alloc

if the returned array cannot grow.

Definition at line 802 of file tpl_patricia_trie.H.

References Aleph::Array< T >::reserve().

operator=() [1/2]

template<typename UInt , typename T >

PatriciaMap & Aleph::PatriciaMap< UInt, T >::operator= ( const PatriciaMap< UInt, T > &  other )

inline

Deep-copy assignment.

Parameters

[in]

other

Map to copy.

Returns

*this.

Exceptions

Whatever

T's copy constructor throws, or std::bad_alloc.

Definition at line 646 of file tpl_patricia_trie.H.

References Aleph::blossom_maximum_cardinality_matching().

operator=() [2/2]

template<typename UInt , typename T >

PatriciaMap & Aleph::PatriciaMap< UInt, T >::operator= ( PatriciaMap< UInt, T > &&  other )

inlinenoexcept

Move assignment.

Parameters

[in,out]

other

Source map, left empty.

Returns

*this.

Exceptions

Nothing.

Definition at line 672 of file tpl_patricia_trie.H.

References Aleph::blossom_maximum_cardinality_matching().

size()

template<typename UInt , typename T >

size_t Aleph::PatriciaMap< UInt, T >::size ( ) const

inlinenoexcept

Return the number of stored key-value pairs.

Returns

Current cardinality.

Exceptions

Nothing.

Definition at line 687 of file tpl_patricia_trie.H.

Member Data Documentation

bit_width

template<typename UInt , typename T >

constexpr size_t Aleph::PatriciaMap< UInt, T >::bit_width = std::numeric_limits<Key>::digits

staticconstexpr

Number of significant bits in Key.

Definition at line 557 of file tpl_patricia_trie.H.

root_

template<typename UInt , typename T >

std::unique_ptr<Node> Aleph::PatriciaMap< UInt, T >::root_

private

Definition at line 574 of file tpl_patricia_trie.H.

size_

template<typename UInt , typename T >

size_t Aleph::PatriciaMap< UInt, T >::size_ = 0

private

Definition at line 575 of file tpl_patricia_trie.H.

---

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

• tpl_patricia_trie.H