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

#include <tpl_patricia_trie.H>

Collaboration diagram for Aleph::PatriciaSet< UInt >:

Classes
struct	Node

Public Types
using	Key = UInt
	Key type stored by the set.

Public Member Functions
	PatriciaSet ()=default
	Construct an empty set.

	~PatriciaSet ()=default
	Destructor.

	PatriciaSet (const PatriciaSet &other)
	Deep-copy constructor.

PatriciaSet &	operator= (const PatriciaSet &other)
	Deep-copy assignment.

	PatriciaSet (PatriciaSet &&other) noexcept
	Move constructor.

PatriciaSet &	operator= (PatriciaSet &&other) noexcept
	Move assignment.

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

bool	is_empty () const noexcept
	Check whether the set has no keys.

void	clear () noexcept
	Remove every key from the set.

bool	contains (const Key key) const noexcept
	Check whether `key` is stored.

bool	insert (const Key key)
	Insert `key` if absent.

bool	erase (const Key key) noexcept
	Remove `key` if present.

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 >

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>
requires (std::is_integral_v<UInt> and std::is_unsigned_v<UInt> and not std::is_same_v<UInt, bool>)
class Aleph::PatriciaSet< UInt >

Compressed bitwise set for unsigned integral keys.

PatriciaSet is a PATRICIA/crit-bit tree over the fixed-width bit pattern of UInt. It stores unique keys only; use RadixTree when string keys or mapped values are required.

Template Parameters

UInt	Unsigned integral key type. `bool` is rejected because it has only two values and does not benefit from a trie representation.

Definition at line 324 of file tpl_patricia_trie.H.

Member Typedef Documentation

◆ Detail

template<typename UInt >

using Aleph::PatriciaSet< UInt >::Detail = patricia_trie_detail::Bitwise_Trie_Utils<Key>

private

Definition at line 347 of file tpl_patricia_trie.H.

◆ Key

template<typename UInt >

using Aleph::PatriciaSet< UInt >::Key = UInt

Key type stored by the set.

Definition at line 328 of file tpl_patricia_trie.H.

Constructor & Destructor Documentation

◆ PatriciaSet() [1/3]

template<typename UInt >

Aleph::PatriciaSet< UInt >::PatriciaSet ( )

default

Construct an empty set.

Exceptions

Nothing.

◆ ~PatriciaSet()

template<typename UInt >

Aleph::PatriciaSet< UInt >::~PatriciaSet ( )

default

Destructor.

Recursively releases every node.

Exceptions

Nothing.

◆ PatriciaSet() [2/3]

template<typename UInt >

Aleph::PatriciaSet< UInt >::PatriciaSet ( const PatriciaSet< UInt > & other )

inline

Deep-copy constructor.

Parameters

[in] other Set to copy.

Exceptions

std::bad_alloc if cloning nodes fails.

Definition at line 378 of file tpl_patricia_trie.H.

◆ PatriciaSet() [3/3]

template<typename UInt >

Aleph::PatriciaSet< UInt >::PatriciaSet ( PatriciaSet< UInt > && other )

inlinenoexcept

Move constructor.

Parameters

[in,out] other Source set, left empty.

Exceptions

Nothing.

Definition at line 401 of file tpl_patricia_trie.H.

References Aleph::blossom_maximum_cardinality_matching().

Member Function Documentation

◆ check_invariants()

template<typename UInt >

bool Aleph::PatriciaSet< UInt >::check_invariants ( ) const

inlinenoexcept

Verify structural invariants recursively.

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

Returns: true iff all invariants hold.

Exceptions

Nothing.

Definition at line 524 of file tpl_patricia_trie.H.

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

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

◆ clear()

template<typename UInt >

void Aleph::PatriciaSet< UInt >::clear ( )

inlinenoexcept

Remove every key from the set.

Exceptions

Nothing.

Definition at line 444 of file tpl_patricia_trie.H.

Referenced by TEST().

◆ clone_node()

template<typename UInt >

static std::unique_ptr< Node > Aleph::PatriciaSet< UInt >::clone_node ( const Node * src )

inlinestaticprivate

Definition at line 349 of file tpl_patricia_trie.H.

References Aleph::PatriciaSet< UInt >::Node::bit_index, Aleph::blossom_maximum_cardinality_matching(), Aleph::PatriciaSet< UInt >::Node::child, Aleph::PatriciaSet< UInt >::Node::key, and Aleph::PatriciaSet< UInt >::Node::leaf.

◆ contains()

template<typename UInt >

bool Aleph::PatriciaSet< UInt >::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 455 of file tpl_patricia_trie.H.

References Aleph::and, and Aleph::PatriciaSet< UInt >::Node::key.

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

◆ erase()

template<typename UInt >

bool Aleph::PatriciaSet< UInt >::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 498 of file tpl_patricia_trie.H.

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

◆ insert()

template<typename UInt >

bool Aleph::PatriciaSet< UInt >::insert ( const Key key )

inline

Insert key if absent.

Parameters

[in] key Key to insert.

Returns: true if inserted, false if it was already present.

Exceptions

std::bad_alloc if allocating a new leaf or internal node fails.

Definition at line 466 of file tpl_patricia_trie.H.

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

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

◆ is_empty()

template<typename UInt >

bool Aleph::PatriciaSet< UInt >::is_empty ( ) const

inlinenoexcept

Check whether the set has no keys.

Returns: true iff size() == 0.

Exceptions

Nothing.

Definition at line 436 of file tpl_patricia_trie.H.

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

◆ keys()

template<typename UInt >

Array< Key > Aleph::PatriciaSet< UInt >::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 507 of file tpl_patricia_trie.H.

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

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

◆ operator=() [1/2]

template<typename UInt >

PatriciaSet & Aleph::PatriciaSet< UInt >::operator= ( const PatriciaSet< UInt > & other )

inline

Deep-copy assignment.

Parameters

[in] other Set to copy.

Returns: *this.

Exceptions

std::bad_alloc if cloning nodes fails.

Definition at line 387 of file tpl_patricia_trie.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ operator=() [2/2]

template<typename UInt >

PatriciaSet & Aleph::PatriciaSet< UInt >::operator= ( PatriciaSet< UInt > && other )

inlinenoexcept

Move assignment.

Parameters

[in,out] other Source set, left empty.

Returns: *this.

Exceptions

Nothing.

Definition at line 412 of file tpl_patricia_trie.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ size()

template<typename UInt >

size_t Aleph::PatriciaSet< UInt >::size ( ) const

inlinenoexcept

Return the number of stored keys.

Returns: Current cardinality.

Exceptions

Nothing.

Definition at line 427 of file tpl_patricia_trie.H.

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

Member Data Documentation

◆ bit_width

template<typename UInt >

constexpr size_t Aleph::PatriciaSet< UInt >::bit_width = std::numeric_limits<Key>::digits

staticconstexpr

Number of significant bits in Key.

Definition at line 331 of file tpl_patricia_trie.H.

◆ root_

template<typename UInt >

std::unique_ptr<Node> Aleph::PatriciaSet< UInt >::root_

private

Definition at line 345 of file tpl_patricia_trie.H.

◆ size_

template<typename UInt >

size_t Aleph::PatriciaSet< UInt >::size_ = 0

private

Definition at line 346 of file tpl_patricia_trie.H.

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

tpl_patricia_trie.H

Classes

Public Types

Public Member Functions

Static Public Attributes

Private Types

Static Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ Detail

◆ Key

Constructor & Destructor Documentation

◆ PatriciaSet() [1/3]

◆ ~PatriciaSet()

◆ PatriciaSet() [2/3]

◆ PatriciaSet() [3/3]

Member Function Documentation

◆ check_invariants()

◆ clear()

◆ clone_node()

◆ contains()

◆ erase()

◆ insert()

◆ is_empty()

◆ keys()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ size()

Member Data Documentation

◆ bit_width

◆ root_

◆ size_