Owning prefix tree map from strings to values. More...

#include <prefix-tree.H>

Collaboration diagram for Aleph::Prefix_Tree_Map< T >:

Classes
class	Node
	Internal trie node storing one character and an optional value. More...

Public Types
using	Key = std::string
	Key type accepted by the map.

using	Value = T
	Mapped value type stored in terminal nodes.

Public Member Functions
	Prefix_Tree_Map ()
	Construct an empty prefix map.

	Prefix_Tree_Map (const Prefix_Tree_Map &other)
	Construct a deep copy of another prefix map.

	Prefix_Tree_Map (Prefix_Tree_Map &&other) noexcept
	Move-construct, taking ownership of another map's root.

	~Prefix_Tree_Map () noexcept
	Destroy the owned root and all descendants.

Prefix_Tree_Map &	operator= (const Prefix_Tree_Map &other)
	Replace this map with a deep copy of another map.

Prefix_Tree_Map &	operator= (Prefix_Tree_Map &&other) noexcept
	Move-assign, taking ownership of another map's root.

bool	insert (const Key &key, const Value &value)
	Insert key with a copied value if absent.

bool	insert (const Key &key, Value &&value)
	Insert key with a moved value if absent.

void	insert_or_assign (const Key &key, Value value)
	Insert key or overwrite its mapped value.

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.

size_t	size () const noexcept
	Return the number of stored key-value pairs.

size_t	count () const noexcept
	Return the number of stored key-value pairs.

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

void	clear ()
	Remove every key-value pair from the map.

DynArray< Key >	words (const size_t max_word_length=2048) const
	Get all keys stored in the map.

DynArray< Key >	words_with_prefix (const Key &prefix, const size_t max_word_length=2048) const
	Get all keys with a given prefix.

Private Member Functions
void	ensure_root ()
	Ensure the root node exists after a move.

const Node *	find_node (const std::string &word) const noexcept
	Find the terminal node for word.

Node *	find_node (const std::string &word) noexcept
	Find the terminal node for word.

template<typename U >
bool	insert_impl (const std::string &word, U &&value, const bool assign_if_present=false)
	Shared implementation for `insert()`'s copy/move overloads and for `insert_or_assign()`: when `assign_if_present` is `true` (only `insert_or_assign()` sets it), an already-present key's value is overwritten in place instead of leaving it untouched – letting `insert_or_assign()` share this single tree descent instead of calling `find()` first and then re-descending from the root a second time via this function.

Static Private Member Functions
static void	destroy_root (Node *root) noexcept
	Destroy an owned root and all descendants.

Private Attributes
Node *	root_ = nullptr

size_t	size_ = 0

Detailed Description

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

Owning prefix tree map from strings to values.

Prefix_Tree_Map is the mapped-value counterpart of Prefix_Tree. It uses the same one-character-per-edge trie shape, but terminal nodes store a mapped value instead of only a word-ending flag. It is intentionally a separate type so the legacy Prefix_Tree and Cnode APIs remain source-compatible.

Insert, exact lookup, and prefix lookup are O(k) in the length of the key plus the cost of scanning sibling lists at each level. size() and count() are O(1). words() and words_with_prefix() return independent arrays of copied keys.

Recursion depth and long keys: Unlike Aleph::RadixTree (tpl_radix_tree.H), which compresses chains of single-child nodes into one edge, Prefix_Tree_Map never compresses: a single key of length k always creates (or reuses) k nodes on its own path. Destruction, deep copy, and words()/words_with_prefix() all recurse to that depth, so a single very long key (tens of thousands of characters) can exhaust the stack. For workloads with long individual keys or long shared prefixes, prefer RadixTree.

Keys containing embedded NUL bytes: Internally, key traversal is done through std::string::c_str(), which stops at the first ‘’\0'. Two distinctstd::stringkeys that only differ after an embedded NUL byte (legal forstd::string, unlike C strings) are silently treated as the same key. This limitation is shared with the legacyCnode/Prefix_Tree`.

Template Parameters

T	Mapped value type. Move-only values are supported for insertion and lookup; copying the map requires T to be copy-constructible.

Definition at line 1018 of file prefix-tree.H.

Member Typedef Documentation

◆ Key

template<typename T >

using Aleph::Prefix_Tree_Map< T >::Key = std::string

Key type accepted by the map.

Definition at line 1022 of file prefix-tree.H.

◆ Value

template<typename T >

using Aleph::Prefix_Tree_Map< T >::Value = T

Mapped value type stored in terminal nodes.

Definition at line 1025 of file prefix-tree.H.

Constructor & Destructor Documentation

◆ Prefix_Tree_Map() [1/3]

template<typename T >

Aleph::Prefix_Tree_Map< T >::Prefix_Tree_Map ( )

inline

Construct an empty prefix map.

Exceptions

std::bad_alloc If allocating the root node fails.

Definition at line 1519 of file prefix-tree.H.

◆ Prefix_Tree_Map() [2/3]

template<typename T >

Aleph::Prefix_Tree_Map< T >::Prefix_Tree_Map ( const Prefix_Tree_Map< T > & other )

inline

Construct a deep copy of another prefix map.

Parameters

[in] other Map to copy.

Exceptions

Whatever T copying throws, or std::bad_alloc.

Definition at line 1530 of file prefix-tree.H.

◆ Prefix_Tree_Map() [3/3]

template<typename T >

Aleph::Prefix_Tree_Map< T >::Prefix_Tree_Map ( Prefix_Tree_Map< T > && other )

inlinenoexcept

Move-construct, taking ownership of another map's root.

Parameters

[in,out] other Source map, left empty and usable.

Definition at line 1542 of file prefix-tree.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ ~Prefix_Tree_Map()

template<typename T >

Aleph::Prefix_Tree_Map< T >::~Prefix_Tree_Map ( )

inlinenoexcept

Destroy the owned root and all descendants.

Exceptions

Nothing.

Definition at line 1553 of file prefix-tree.H.

References Aleph::Prefix_Tree_Map< T >::destroy_root(), and Aleph::Prefix_Tree_Map< T >::root_.

Member Function Documentation

◆ clear()

template<typename T >

void Aleph::Prefix_Tree_Map< T >::clear ( )

inline

Remove every key-value pair from the map.

Exceptions

std::bad_alloc If recreating the empty root fails.

Definition at line 1739 of file prefix-tree.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Prefix_Tree_Map< T >::destroy_root(), Aleph::Prefix_Tree_Map< T >::root_, and Aleph::Prefix_Tree_Map< T >::size_.

Referenced by TEST().

◆ contains()

template<typename T >

bool Aleph::Prefix_Tree_Map< T >::contains ( const Key & key ) const

inlinenoexcept

Check whether key is stored.

Parameters

[in] key Key to search for.

Returns: true if key exists.

Exceptions

Nothing.

Definition at line 1667 of file prefix-tree.H.

References Aleph::Prefix_Tree_Map< T >::find().

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

◆ count()

template<typename T >

size_t Aleph::Prefix_Tree_Map< T >::count ( ) const

inlinenoexcept

Return the number of stored key-value pairs.

Returns: Current cardinality.

Exceptions

Nothing.

Note: Alias for size().

Definition at line 1719 of file prefix-tree.H.

References Aleph::Prefix_Tree_Map< T >::size().

Referenced by TEST().

◆ destroy_root()

template<typename T >

static void Aleph::Prefix_Tree_Map< T >::destroy_root ( Node * root )

inlinestaticprivatenoexcept

Destroy an owned root and all descendants.

Definition at line 1448 of file prefix-tree.H.

References root().

Referenced by Aleph::Prefix_Tree_Map< T >::~Prefix_Tree_Map(), Aleph::Prefix_Tree_Map< T >::clear(), Aleph::Prefix_Tree_Map< T >::operator=(), and Aleph::Prefix_Tree_Map< T >::operator=().

◆ ensure_root()

template<typename T >

void Aleph::Prefix_Tree_Map< T >::ensure_root ( )

inlineprivate

Ensure the root node exists after a move.

Definition at line 1458 of file prefix-tree.H.

References Aleph::Prefix_Tree_Map< T >::root_.

Referenced by Aleph::Prefix_Tree_Map< T >::insert_impl().

◆ erase()

template<typename T >

bool Aleph::Prefix_Tree_Map< T >::erase ( const Key & key )

inlinenoexcept

Remove key if present.

Parameters

[in] key Key to remove.

Returns: true if key was present, false otherwise.

Exceptions

Nothing.

Note: This removes the logical key by clearing its mapped value. Structural path nodes may be retained and reused by later insertions.

Definition at line 1649 of file prefix-tree.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Prefix_Tree_Map< T >::find_node(), Aleph::Prefix_Tree_Map< T >::Node::has_value(), Aleph::Prefix_Tree_Map< T >::Node::reset_value(), and Aleph::Prefix_Tree_Map< T >::size_.

Referenced by TEST().

◆ find() [1/2]

template<typename T >

const Value * Aleph::Prefix_Tree_Map< T >::find ( const Key & key ) const

inlinenoexcept

Look up key.

Parameters

[in] key Key to search for.

Returns: Pointer to the stored value, or nullptr. The pointer remains valid until the next non-const operation on this map.

Exceptions

Nothing.

Definition at line 1680 of file prefix-tree.H.

References Aleph::Prefix_Tree_Map< T >::find_node(), and Aleph::Prefix_Tree_Map< T >::Node::value().

Referenced by Aleph::Prefix_Tree_Map< T >::contains(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ find() [2/2]

template<typename T >

Value * Aleph::Prefix_Tree_Map< T >::find ( const Key & key )

inlinenoexcept

Mutable lookup overload.

Parameters

[in] key Key to search for.

Returns: Mutable pointer to the stored value, or nullptr. The pointer remains valid until the next non-const operation on this map.

Exceptions

Nothing.

Definition at line 1694 of file prefix-tree.H.

References Aleph::Prefix_Tree_Map< T >::find_node(), and Aleph::Prefix_Tree_Map< T >::Node::value().

◆ find_node() [1/2]

template<typename T >

const Node * Aleph::Prefix_Tree_Map< T >::find_node ( const std::string & word ) const

inlineprivatenoexcept

Find the terminal node for word.

Definition at line 1465 of file prefix-tree.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Prefix_Tree_Map< T >::root_, and Aleph::Prefix_Tree_Map< T >::Node::search_prefix().

Referenced by Aleph::Prefix_Tree_Map< T >::erase(), Aleph::Prefix_Tree_Map< T >::find(), Aleph::Prefix_Tree_Map< T >::find(), and Aleph::Prefix_Tree_Map< T >::find_node().

◆ find_node() [2/2]

template<typename T >

Node * Aleph::Prefix_Tree_Map< T >::find_node ( const std::string & word )

inlineprivatenoexcept

Find the terminal node for word.

Definition at line 1475 of file prefix-tree.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Prefix_Tree_Map< T >::find_node().

◆ insert() [1/2]

template<typename T >

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

inline

Insert key with a copied value if absent.

Parameters

[in]	key	Key to insert. The empty string is valid.
[in]	value	Value to copy.

Returns: true if inserted, false if key already existed.

Exceptions

Whatever T copying throws, or std::bad_alloc.

Definition at line 1607 of file prefix-tree.H.

References Aleph::Prefix_Tree_Map< T >::insert_impl(), and value.

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

◆ insert() [2/2]

template<typename T >

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

inline

Insert key with a moved value if absent.

Parameters

[in]	key	Key to insert. The empty string is valid.
[in,out]	value	Value to move from if insertion succeeds.

Returns: true if inserted, false if key already existed.

Exceptions

Whatever T moving throws, or std::bad_alloc.

Warning: If key already exists, value is left untouched.

Definition at line 1622 of file prefix-tree.H.

References Aleph::Prefix_Tree_Map< T >::insert_impl(), and value.

◆ insert_impl()

template<typename T >

template<typename U >

bool Aleph::Prefix_Tree_Map< T >::insert_impl	(	const std::string &	word,
		U &&	value,
		const bool	assign_if_present = `false`
	)

inlineprivate

Shared implementation for insert()'s copy/move overloads and for insert_or_assign(): when assign_if_present is true (only insert_or_assign() sets it), an already-present key's value is overwritten in place instead of leaving it untouched – letting insert_or_assign() share this single tree descent instead of calling find() first and then re-descending from the root a second time via this function.

Definition at line 1490 of file prefix-tree.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Prefix_Tree_Map< T >::ensure_root(), Aleph::Prefix_Tree_Map< T >::root_, Aleph::Prefix_Tree_Map< T >::Node::search_prefix(), Aleph::Prefix_Tree_Map< T >::size_, and value.

Referenced by Aleph::Prefix_Tree_Map< T >::insert(), Aleph::Prefix_Tree_Map< T >::insert(), and Aleph::Prefix_Tree_Map< T >::insert_or_assign().

◆ insert_or_assign()

template<typename T >

void Aleph::Prefix_Tree_Map< T >::insert_or_assign	(	const Key &	key,
		Value	value
	)

inline

Insert key or overwrite its mapped value.

Parameters

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

Exceptions

Whatever T construction or assignment throws, or std::bad_alloc.

Definition at line 1634 of file prefix-tree.H.

References Aleph::Prefix_Tree_Map< T >::insert_impl(), and value.

Referenced by TEST(), and TEST().

◆ is_empty()

template<typename T >

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

inlinenoexcept

Check whether the map has no keys.

Returns: true if size() == 0.

Exceptions

Nothing.

Definition at line 1730 of file prefix-tree.H.

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

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

◆ operator=() [1/2]

template<typename T >

Prefix_Tree_Map & Aleph::Prefix_Tree_Map< T >::operator= ( const Prefix_Tree_Map< T > & other )

inline

Replace this map with a deep copy of another map.

Parameters

[in] other Map to copy from.

Returns: Reference to this map.

Exceptions

Whatever T copying throws, or std::bad_alloc.

Note: Provides the strong guarantee: if copying fails, this map keeps its previous contents.

Definition at line 1568 of file prefix-tree.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Prefix_Tree_Map< T >::Node::clone(), Aleph::Prefix_Tree_Map< T >::destroy_root(), Aleph::Prefix_Tree_Map< T >::root_, and Aleph::Prefix_Tree_Map< T >::size_.

◆ operator=() [2/2]

template<typename T >

Prefix_Tree_Map & Aleph::Prefix_Tree_Map< T >::operator= ( Prefix_Tree_Map< T > && other )

inlinenoexcept

Move-assign, taking ownership of another map's root.

Parameters

[in,out] other Source map, left empty and usable.

Returns: Reference to this map.

Definition at line 1586 of file prefix-tree.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Prefix_Tree_Map< T >::destroy_root(), Aleph::Prefix_Tree_Map< T >::root_, and Aleph::Prefix_Tree_Map< T >::size_.

◆ size()

template<typename T >

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

inlinenoexcept

Return the number of stored key-value pairs.

Returns: Current cardinality.

Exceptions

Nothing.

Definition at line 1706 of file prefix-tree.H.

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

Referenced by Aleph::Prefix_Tree_Map< T >::count(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ words()

template<typename T >

DynArray< Key > Aleph::Prefix_Tree_Map< T >::words ( const size_t max_word_length = 2048 ) const

inline

Get all keys stored in the map.

Parameters

[in] max_word_length Maximum expected key length.

Returns: Array containing all keys.

Exceptions

std::bad_alloc If allocation fails.

Precondition: max_word_length must be large enough for every stored key when assertions are enabled.

Definition at line 1757 of file prefix-tree.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::DynArray< T >::reserve(), Aleph::Prefix_Tree_Map< T >::root_, and Aleph::Prefix_Tree_Map< T >::Node::words_impl().

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

◆ words_with_prefix()

template<typename T >

DynArray< Key > Aleph::Prefix_Tree_Map< T >::words_with_prefix	(	const Key &	prefix,
		const size_t	max_word_length = `2048`
	)		const

inline

Get all keys with a given prefix.

Parameters

[in]	prefix	Prefix to search for.
[in]	max_word_length	Maximum expected key length.

Returns: Array containing matching keys.

Exceptions

std::bad_alloc If allocation fails.

Precondition: max_word_length must be at least prefix.size() and large enough for every emitted key when assertions are enabled.

Definition at line 1780 of file prefix-tree.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::prefix(), Aleph::Prefix_Tree_Map< T >::root_, and Aleph::Prefix_Tree_Map< T >::Node::search_prefix().

Referenced by TEST().

Member Data Documentation

◆ root_

template<typename T >

Node* Aleph::Prefix_Tree_Map< T >::root_ = nullptr

private

Definition at line 1444 of file prefix-tree.H.

Referenced by Aleph::Prefix_Tree_Map< T >::~Prefix_Tree_Map(), Aleph::Prefix_Tree_Map< T >::clear(), Aleph::Prefix_Tree_Map< T >::ensure_root(), Aleph::Prefix_Tree_Map< T >::find_node(), Aleph::Prefix_Tree_Map< T >::insert_impl(), Aleph::Prefix_Tree_Map< T >::operator=(), Aleph::Prefix_Tree_Map< T >::operator=(), Aleph::Prefix_Tree_Map< T >::words(), and Aleph::Prefix_Tree_Map< T >::words_with_prefix().

◆ size_

template<typename T >

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

private

Definition at line 1445 of file prefix-tree.H.

Referenced by Aleph::Prefix_Tree_Map< T >::clear(), Aleph::Prefix_Tree_Map< T >::erase(), Aleph::Prefix_Tree_Map< T >::insert_impl(), Aleph::Prefix_Tree_Map< T >::is_empty(), Aleph::Prefix_Tree_Map< T >::operator=(), Aleph::Prefix_Tree_Map< T >::operator=(), and Aleph::Prefix_Tree_Map< T >::size().

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

prefix-tree.H

Classes

Public Types

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ Key

◆ Value

Constructor & Destructor Documentation

◆ Prefix_Tree_Map() [1/3]

◆ Prefix_Tree_Map() [2/3]

◆ Prefix_Tree_Map() [3/3]

◆ ~Prefix_Tree_Map()

Member Function Documentation

◆ clear()

◆ contains()

◆ count()

◆ destroy_root()

◆ ensure_root()

◆ erase()

◆ find() [1/2]

◆ find() [2/2]

◆ find_node() [1/2]

◆ find_node() [2/2]

◆ insert() [1/2]

◆ insert() [2/2]

◆ insert_impl()

◆ insert_or_assign()

◆ is_empty()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ size()

◆ words()

◆ words_with_prefix()

Member Data Documentation

◆ root_

◆ size_