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

Inheritance diagram for Aleph::Prefix_Tree_Map< T >::Node:

Collaboration diagram for Aleph::Prefix_Tree_Map< T >::Node:

Classes
class	Detached_Subtree_Guard
	Own a detached map subtree until it is committed. More...

class	Pending_Path_Guard
	Own standalone insertion nodes until a new path is committed. More...

Public Member Functions
	Node (const char c) noexcept
	Construct a structural node with no mapped value.

template<typename U >
	Node (const char c, U &&value)
	Construct a terminal node with a mapped value.

char	symbol () const noexcept
	Return the character stored in this node.

bool	has_value () const noexcept
	Check whether this node terminates a key.

const Value *	value () const noexcept
	Return the stored mapped value.

Value *	value () noexcept
	Return the stored mapped value.

void	reset_value () noexcept
	Remove this node's mapped value.

template<typename U >
void	emplace_value (U &&value)
	Emplace this node's mapped value.

Node *	search_child (const char c) noexcept
	Search for a mutable child with the given character.

const Node *	search_child (const char c) const noexcept
	Search for a const child with the given character.

Node *	greater_child (const char c) noexcept
	Find the first mutable child with a character greater than c.

const Node *	greater_child (const char c) const noexcept
	Find the first const child with a character greater than c.

std::tuple< Node , const char >	search_prefix (const char *prefix) noexcept
	Search for a prefix in the mutable tree.

std::tuple< const Node , const char >	search_prefix (const char *prefix) const noexcept
	Search for a prefix in the const tree.

Node *	insert_child (Node *child)
	Insert a child node in sorted order.

template<typename U >
void	insert_suffix (const char *suffix, U &&value)
	Insert a key suffix below this node.

void	destroy () noexcept
	Destroy all children of this node.

Node *	clone () const
	Clone this node and all descendants.

void	words_impl (std::string &word, DynArray< std::string > &out, const size_t max_word_length) const
	Append all terminal keys in this subtree.

Public Member Functions inherited from Aleph::Tree_Node< char >
char &	get_key () noexcept
	Returns a modifiable reference to the node contents.

constexpr const char &	get_key () const noexcept

char &	get_data () noexcept
	Returns a modifiable reference to the node contents.

constexpr const char &	get_data () const noexcept

Dlink *	get_child_list () noexcept
	Returns the embedded child-list link.

Dlink *	get_sibling_list () noexcept
	Returns the embedded sibling-list link.

constexpr bool	is_root () const noexcept
	Returns true if this is the root of the general tree.

constexpr bool	is_leaf () const noexcept
	Returns true if this is a leaf node.

constexpr bool	is_leftmost () const noexcept
	Returns true if this is the leftmost node among its siblings.

constexpr bool	is_rightmost () const noexcept
	Returns true if this is the rightmost node among its siblings.

void	set_is_root (bool value) noexcept
	Sets the root flag.

void	set_is_leaf (bool value) noexcept
	Sets the leaf flag.

void	set_is_leftmost (bool value) noexcept
	Sets the leftmost-sibling flag.

void	set_is_rightmost (bool value) noexcept
	Sets the rightmost-sibling flag.

	Tree_Node ()=default
	Empty constructor (undefined key).

	Tree_Node (const char &d)
	Constructor with data value __data.

	Tree_Node (char &&d)

Tree_Node *	get_left_sibling () const noexcept
	Returns the left sibling of this.

Tree_Node *	get_right_sibling () const noexcept
	Returns the right sibling of this.

Tree_Node *	get_left_child () const noexcept
	Returns the leftmost child of this.

Tree_Node *	get_right_child () const noexcept
	Returns the rightmost child of this.

Tree_Node *	get_child (const size_t i) const noexcept
	Returns the i-th child of this.

Tree_Node *	get_parent () const noexcept
	Returns the parent of this.

void	insert_right_sibling (Tree_Node *p) noexcept
	Inserts p to the right of this node.

void	insert_left_sibling (Tree_Node *p)
	Inserts p as the left sibling of this.

void	insert_leftmost_child (Tree_Node *p) noexcept
	Inserts p as the leftmost child of this.

void	insert_rightmost_child (Tree_Node *p) noexcept
	Inserts p as the rightmost child of this.

Tree_Node *	join (Tree_Node *tree)
	join `tree` as subtree of root `this`

void	insert_tree_to_right (Tree_Node *tree)
	Insert `tree` to the right of `this`

Tree_Node *	get_left_tree () const noexcept
	Returns the tree to the left of this.

Tree_Node *	get_right_tree () const noexcept
	Returns the tree to the right of this.

Tree_Node *	get_last_tree () const
	Returns the rightmost tree of the forest containing this.

Container< Tree_Node * >	trees () const
	Return a list with all trees belonging to the forest.

void	for_each_child (Operation &op) const
	Visits each child of this and executes the operation on the child node.

void	for_each_child (Operation &&op=Operation()) const

Container< Tree_Node * >	children_nodes () const
	Returns a list with the child nodes of this.

Container< char >	children () const
	Returns a list with the contents of the children of this.

bool	traverse (Operation op)
	Preorder traversal over all nodes executing op.

bool	traverse (Operation op) const

bool	level_traverse (Op op)

bool	level_traverse (Op op) const

Children_Iterator	children_it () const

Iterator	get_it () const

iterator	begin () noexcept

const_iterator	begin () const noexcept

iterator	end () noexcept

const_iterator	end () const noexcept

const_iterator	cbegin () const noexcept

const_iterator	cbegin () noexcept

const_iterator	cend () const noexcept

const_iterator	cend () noexcept

Public Member Functions inherited from Aleph::FunctionalMixin< Derived, Type >
template<class Operation > requires CallableWith<Operation &, const Type &>
auto	for_each (Operation &operation) const -> decltype(self())
	Apply an operation to each element (read-only).

template<class Operation > requires CallableWith<Operation &, const Type &>
auto	for_each (Operation &operation) -> decltype(self())
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<class Operation > requires CallableWith<Operation &, const Type &>
auto	for_each (Operation &&operation=Operation()) const -> decltype(self())
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<class Operation > requires CallableWith<Operation &, const Type &>
auto	for_each (Operation &&operation=Operation()) -> decltype(self())
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<class Operation > requires CallableWith<Operation &, Type &>
auto	mutable_for_each (Operation &operation) -> decltype(self())
	Apply an operation to each element (mutable).

template<class Operation > requires CallableWith<Operation &, Type &>
auto	mutable_for_each (Operation &&operation=Operation()) -> decltype(self())
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<class Operation > requires requires(const typename concepts_detail::defer<Derived, Operation>::type &c, Operation &op) { { c.template traverse<Operation>(op) } -> std::convertible_to<bool>; }
bool	all (Operation &operation) const
	Test if all elements satisfy a predicate.

template<class Operation > requires requires(const typename concepts_detail::defer<Derived, Operation>::type &c, Operation &op) { { c.template traverse<Operation>(op) } -> std::convertible_to<bool>; }
bool	all (Operation &&operation=Operation()) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<class Operation > requires requires(const typename concepts_detail::defer<Derived, Operation>::type &c, Operation &op) { { c.template traverse<Operation>(op) } -> std::convertible_to<bool>; }
bool	forall (Operation &operation) const
	Alias for all().

template<class Operation > requires requires(const typename concepts_detail::defer<Derived, Operation>::type &c, Operation &op) { { c.template traverse<Operation>(op) } -> std::convertible_to<bool>; }
bool	forall (Operation &&operation=Operation()) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<class Operation > requires PredicateWith<Operation &, const Type &>
bool	exists (Operation &operation) const
	Test if any element satisfies a predicate.

template<class Operation > requires PredicateWith<Operation &, const Type &>
bool	exists (Operation &&operation=Operation()) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<typename __Type = Type, template< typename > class Container = Aleph::DynList, class Operation = Dft_Map_Op<Type, __Type>> requires requires(Container<__Type> &l, Operation &op, const Type &item) { l.append(op(item)); }
Container< __Type >	maps (Operation &operation) const
	Transform elements using a mapping function.

template<typename __Type = Type, template< typename > class Container = Aleph::DynList, class Operation = Dft_Map_Op<Type, __Type>> requires requires(Container<__Type> &l, Operation &op, const Type &item) { l.append(op(item)); }
Container< __Type >	maps (Operation &&operation=Operation()) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<typename __Type = Type>
__Type	foldl (const __Type &init, std::function< __Type(const __Type &, const Type &)> operation) const
	Left fold (reduce) with initial value.

template<typename __Type = Type>
__Type	fold_left (std::function< __Type(const __Type &, const Type &)> operation, const __Type &init) const
	Left fold with operation first (alternative signature).

template<class Operation > requires requires(Type &acc, Operation &op, const Type &item) { acc = op(acc, item); }
Type	fold (const Type &init, Operation &operation) const
	Simple fold with same type for accumulator and elements.

template<class Operation > requires requires(Type &acc, Operation &op, const Type &item) { acc = op(acc, item); }
Type	fold (const Type &init, Operation &&operation=Operation()) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<class Operation > requires PredicateWith<Operation &, const Type &>
DynList< Type >	filter (Operation &operation) const
	Filter elements by a predicate.

template<class Operation > requires PredicateWith<Operation &, const Type &>
DynList< Type >	filter (Operation &&operation=Operation()) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<class Operation > requires PredicateWith<Operation &, const Type &>
DynList< std::tuple< Type, size_t > >	pfilter (Operation &operation) const
	Filter with position information.

template<class Operation > requires PredicateWith<Operation &, const Type &>
DynList< std::tuple< Type, size_t > >	pfilter (Operation &&operation=Operation()) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<class Operation > requires PredicateWith<Operation &, const Type &>
std::pair< DynList< Type >, DynList< Type > >	partition (Operation &op) const
	Partition elements by a predicate.

template<class Operation > requires PredicateWith<Operation &, const Type &>
std::pair< DynList< Type >, DynList< Type > >	partition (Operation &&op=Operation()) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<class Operation > requires PredicateWith<Operation &, const Type &>
std::tuple< DynList< Type >, DynList< Type > >	tpartition (Operation &op) const
	Partition returning tuple instead of pair.

template<class Operation > requires PredicateWith<Operation &, const Type &>
std::tuple< DynList< Type >, DynList< Type > >	tpartition (Operation &&op=Operation()) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

size_t	length () const noexcept
	Count the number of elements.

template<template< typename > class Container = Aleph::DynList>
Container< Type >	rev () const
	Create a reversed copy.

template<template< typename > class Container = Aleph::DynList>
Container< Type >	take (const size_t n) const
	Take the first n elements.

template<template< typename > class Container = Aleph::DynList>
Container< Type >	drop (const size_t n) const
	Skip the first n elements.

Type	sum (const Type &init=Type{}) const
	Compute the sum of all elements.

Type	product (const Type &init) const
	Compute the product of all elements.

const Type *	min () const
	Find the minimum element.

const Type *	max () const
	Find the maximum element.

template<class Compare > requires PredicateWith<Compare &, const Type &, const Type &>
const Type *	min_by (Compare cmp) const
	Find the minimum element using a custom comparator.

template<class Compare > requires PredicateWith<Compare &, const Type &, const Type &>
const Type *	max_by (Compare cmp) const
	Find the maximum element using a custom comparator.

bool	has_value (const Type &val) const
	Check if container has a value.

template<class Predicate > requires PredicateWith<Predicate &, const Type &>
bool	none (Predicate &pred) const
	Check if no element satisfies a predicate.

template<class Predicate > requires PredicateWith<Predicate &, const Type &>
bool	none (Predicate &&pred) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<class Predicate > requires PredicateWith<Predicate &, const Type &>
size_t	count_if (Predicate pred) const
	Count elements satisfying a predicate.

const Type *	first () const
	Get the first element.

Type	first_or (const Type &default_val) const
	Get the first element or a default value.

const Type *	last () const
	Get the last element.

Type	last_or (const Type &default_val) const
	Get the last element or a default value.

template<template< typename > class Container = Aleph::DynList>
Container< std::pair< size_t, Type > >	enumerate () const
	Enumerate elements with their indices.

template<class Predicate > requires PredicateWith<Predicate &, const Type &>
size_t	find_index (Predicate pred) const
	Find the index of the first element satisfying a predicate.

size_t	index_of (const Type &val) const
	Find the index of a specific value.

template<template< typename > class Container = Aleph::DynList> requires requires(Type a, Type b) { { a == b } -> std::convertible_to<bool>; }
Container< Type >	unique () const
	Remove consecutive duplicate elements.

template<template< typename > class Container = Aleph::DynList, class EqPred > requires PredicateWith<EqPred &, const Type &, const Type &>
Container< Type >	unique_by (EqPred eq) const
	Remove consecutive duplicates using a custom equality predicate.

template<template< typename > class Container = Aleph::DynList>
Container< Type >	intersperse (const Type &sep) const
	Intersperse a separator between elements.

template<template< typename > class Container = Aleph::DynList>
Container< Container< Type > >	chunk (size_t n) const
	Split into chunks of fixed size.

template<template< typename > class Container = Aleph::DynList>
Container< Container< Type > >	sliding (size_t size, size_t step=1) const
	Create sliding windows of fixed size.

std::vector< Type >	to_vector () const
	Convert to std::vector.

template<typename DynListType = DynList<Type>>
DynListType	to_dynlist () const
	Convert container to DynList.

template<typename StringType = std::string> requires requires(Type a) { std::to_string(a); }
StringType	join (const StringType &sep=StringType{", "}) const
	Join elements into a string with separator.

std::string	join_str (const std::string &sep=", ") const
	Join string elements with separator.

template<class Other , template< typename > class Container = Aleph::DynList>
Container< std::pair< Type, typename Other::Item_Type > >	zip_with (const Other &other) const
	Zip with another container.

Static Public Member Functions
static void	clone_into (const Node src, Node tgt)
	Copy src contents into an already allocated target node.

Static Private Member Functions
template<typename Node_Type >
static Node_Type *	search_child_impl (Node_Type *root, const char c) noexcept
	Shared mutable and const child lookup.

template<typename Node_Type >
static Node_Type *	greater_child_impl (Node_Type *root, const char c) noexcept
	Shared mutable and const sorted-child lookup.

template<typename Node_Type >
static std::tuple< Node_Type , const char >	search_prefix_impl (Node_Type root, const char prefix) noexcept
	Shared mutable and const prefix search.

Private Attributes
std::optional< Value >	value_

Additional Inherited Members
Public Types inherited from Aleph::Tree_Node< char >
using	Item_Type = Tree_Node *

using	key_type = char
	Generic data type stored in the node.

using	iterator = __iterator< Tree_Node >

using	const_iterator = __const_iterator< Tree_Node >

Protected Member Functions inherited from Aleph::FunctionalMixin< Derived, Type >
const Derived &	self () const noexcept

Derived &	self () noexcept

Detailed Description

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

Internal trie node storing one character and an optional value.

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

Constructor & Destructor Documentation

◆ Node() [1/2]

template<typename T >

Aleph::Prefix_Tree_Map< T >::Node::Node ( const char c )

inlineexplicitnoexcept

Construct a structural node with no mapped value.

Parameters

[in] c Character stored in this node.

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

References Aleph::Tree_Node< char >::get_key().

◆ Node() [2/2]

template<typename T >

template<typename U >

Aleph::Prefix_Tree_Map< T >::Node::Node	(	const char	c,
		U &&	value
	)

inline

Construct a terminal node with a mapped value.

Template Parameters

U	Value forwarding type.

Parameters

[in]	c	Character stored in this node.
[in]	value	Value to store.

Exceptions

Whatever Value construction throws.

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

References Aleph::Tree_Node< char >::get_key().

Member Function Documentation

◆ clone()

template<typename T >

Node * Aleph::Prefix_Tree_Map< T >::Node::clone ( ) const

inline

Clone this node and all descendants.

Returns: Newly allocated subtree root.

Exceptions

Whatever Value copying throws, or std::bad_alloc.

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

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Prefix_Tree_Map< T >::Node::clone_into(), and Aleph::Prefix_Tree_Map< T >::Node::symbol().

Referenced by Aleph::Prefix_Tree_Map< T >::operator=().

◆ clone_into()

template<typename T >

static void Aleph::Prefix_Tree_Map< T >::Node::clone_into	(	const Node *	src,
		Node *	tgt
	)

inlinestatic

Copy src contents into an already allocated target node.

Parameters

[in]	src	Source subtree.
[out]	tgt	Target node with the same symbol as src.

Exceptions

Whatever Value copying throws, or std::bad_alloc.

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

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Tree_Node< char >::child, Aleph::Prefix_Tree_Map< T >::Node::clone_into(), Aleph::Tree_Node< T >::get_left_child(), and Aleph::Tree_Node< T >::insert_rightmost_child().

Referenced by Aleph::Prefix_Tree_Map< T >::Node::clone(), and Aleph::Prefix_Tree_Map< T >::Node::clone_into().

◆ destroy()

template<typename T >

void Aleph::Prefix_Tree_Map< T >::Node::destroy ( )

inlinenoexcept

Destroy all children of this node.

Recursively deletes descendants. The node itself is not deleted.

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

References Aleph::destroy_tree(), Aleph::Tree_Node< char >::get_right_child(), and Aleph::Tree_Node< char >::set_is_leaf().

Referenced by Aleph::Prefix_Tree_Map< T >::Node::Detached_Subtree_Guard::~Detached_Subtree_Guard().

◆ emplace_value()

template<typename T >

template<typename U >

void Aleph::Prefix_Tree_Map< T >::Node::emplace_value ( U && value )

inline

Emplace this node's mapped value.

Template Parameters

U	Value forwarding type.

Parameters

[in] value Value to store.

Exceptions

Whatever Value construction throws.

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

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

◆ greater_child() [1/2]

template<typename T >

const Node * Aleph::Prefix_Tree_Map< T >::Node::greater_child ( const char c ) const

inlinenoexcept

Find the first const child with a character greater than c.

Parameters

[in] c Character threshold.

Returns: Const pointer to the first child with char > c, or nullptr.

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

References Aleph::Prefix_Tree_Map< T >::Node::greater_child_impl().

◆ greater_child() [2/2]

template<typename T >

Node * Aleph::Prefix_Tree_Map< T >::Node::greater_child ( const char c )

inlinenoexcept

Find the first mutable child with a character greater than c.

Parameters

[in] c Character threshold.

Returns: Pointer to the first child with char > c, or nullptr.

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

References Aleph::Prefix_Tree_Map< T >::Node::greater_child_impl().

Referenced by Aleph::Prefix_Tree_Map< T >::Node::insert_child().

◆ greater_child_impl()

template<typename T >

template<typename Node_Type >

static Node_Type * Aleph::Prefix_Tree_Map< T >::Node::greater_child_impl	(	Node_Type *	root,
		const char	c
	)

inlinestaticprivatenoexcept

Shared mutable and const sorted-child lookup.

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

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Tree_Node< char >::child, and root().

Referenced by Aleph::Prefix_Tree_Map< T >::Node::greater_child(), and Aleph::Prefix_Tree_Map< T >::Node::greater_child().

◆ has_value()

template<typename T >

bool Aleph::Prefix_Tree_Map< T >::Node::has_value ( ) const

inlinenoexcept

Check whether this node terminates a key.

Returns: true if the node has a mapped value.

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

References Aleph::Prefix_Tree_Map< T >::Node::value_.

Referenced by Aleph::Prefix_Tree_Map< T >::erase(), and Aleph::Prefix_Tree_Map< T >::Node::words_impl().

◆ insert_child()

template<typename T >

Node * Aleph::Prefix_Tree_Map< T >::Node::insert_child ( Node * child )

inline

Insert a child node in sorted order.

Parameters

[in] child Node to insert.

Returns: Pointer to the inserted child.

Precondition: No child with the same character exists.

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

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Tree_Node< char >::child, Aleph::Prefix_Tree_Map< T >::Node::greater_child(), Aleph::Tree_Node< char >::insert_rightmost_child(), Aleph::Prefix_Tree_Map< T >::Node::search_child(), and Aleph::Tree_Node< char >::sibling.

Referenced by Aleph::Prefix_Tree_Map< T >::Node::insert_suffix().

◆ insert_suffix()

template<typename T >

template<typename U >

void Aleph::Prefix_Tree_Map< T >::Node::insert_suffix	(	const char *	suffix,
		U &&	value
	)

inline

Insert a key suffix below this node.

Template Parameters

U	Value forwarding type.

Parameters

[in]	suffix	Non-empty null-terminated suffix to create.
[in]	value	Value to place at the terminal node.

Exceptions

Whatever node or value allocation/construction throws.

Note: Provides the strong guarantee: no partial path is linked if allocation or value construction fails.

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

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Prefix_Tree_Map< T >::Node::insert_child(), Aleph::Tree_Node< T >::insert_rightmost_child(), Aleph::Prefix_Tree_Map< T >::Node::Pending_Path_Guard::release_nodes(), Aleph::Prefix_Tree_Map< T >::Node::Pending_Path_Guard::set(), Aleph::suffix(), and Aleph::Prefix_Tree_Map< T >::Node::value().

◆ reset_value()

template<typename T >

void Aleph::Prefix_Tree_Map< T >::Node::reset_value ( )

inlinenoexcept

Remove this node's mapped value.

Exceptions

Nothing.

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

References Aleph::Prefix_Tree_Map< T >::Node::value_.

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

◆ search_child() [1/2]

template<typename T >

const Node * Aleph::Prefix_Tree_Map< T >::Node::search_child ( const char c ) const

inlinenoexcept

Search for a const child with the given character.

Parameters

[in] c Character to search for.

Returns: Const pointer to the child node, or nullptr.

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

References Aleph::Prefix_Tree_Map< T >::Node::search_child_impl().

◆ search_child() [2/2]

template<typename T >

Node * Aleph::Prefix_Tree_Map< T >::Node::search_child ( const char c )

inlinenoexcept

Search for a mutable child with the given character.

Parameters

[in] c Character to search for.

Returns: Pointer to the child node, or nullptr.

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

References Aleph::Prefix_Tree_Map< T >::Node::search_child_impl().

Referenced by Aleph::Prefix_Tree_Map< T >::Node::insert_child().

◆ search_child_impl()

template<typename T >

template<typename Node_Type >

static Node_Type * Aleph::Prefix_Tree_Map< T >::Node::search_child_impl	(	Node_Type *	root,
		const char	c
	)

inlinestaticprivatenoexcept

Shared mutable and const child lookup.

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

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Tree_Node< char >::child, and root().

Referenced by Aleph::Prefix_Tree_Map< T >::Node::search_child(), and Aleph::Prefix_Tree_Map< T >::Node::search_child().

◆ search_prefix() [1/2]

template<typename T >

std::tuple< const Node *, const char * > Aleph::Prefix_Tree_Map< T >::Node::search_prefix ( const char * prefix ) const

inlinenoexcept

Search for a prefix in the const tree.

Parameters

[in] prefix Null-terminated prefix to search for.

Returns: Tuple of (node reached, remaining unmatched suffix).

Precondition: prefix must not be nullptr.

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

References Aleph::prefix(), and Aleph::Prefix_Tree_Map< T >::Node::search_prefix_impl().

◆ search_prefix() [2/2]

template<typename T >

std::tuple< Node *, const char * > Aleph::Prefix_Tree_Map< T >::Node::search_prefix ( const char * prefix )

inlinenoexcept

Search for a prefix in the mutable tree.

Parameters

[in] prefix Null-terminated prefix to search for.

Returns: Tuple of (node reached, remaining unmatched suffix).

Precondition: prefix must not be nullptr.

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

References Aleph::prefix(), and Aleph::Prefix_Tree_Map< T >::Node::search_prefix_impl().

Referenced by Aleph::Prefix_Tree_Map< T >::find_node(), Aleph::Prefix_Tree_Map< T >::insert_impl(), and Aleph::Prefix_Tree_Map< T >::words_with_prefix().

◆ search_prefix_impl()

template<typename T >

template<typename Node_Type >

static std::tuple< Node_Type , const char > Aleph::Prefix_Tree_Map< T >::Node::search_prefix_impl	(	Node_Type *	root,
		const char *	prefix
	)

inlinestaticprivatenoexcept

Shared mutable and const prefix search.

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

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Tree_Node< char >::child, Aleph::prefix(), and root().

Referenced by Aleph::Prefix_Tree_Map< T >::Node::search_prefix(), and Aleph::Prefix_Tree_Map< T >::Node::search_prefix().

◆ symbol()

template<typename T >

char Aleph::Prefix_Tree_Map< T >::Node::symbol ( ) const

inlinenoexcept

Return the character stored in this node.

Returns: The character value.

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

References Aleph::Tree_Node< char >::get_key().

Referenced by Aleph::Prefix_Tree_Map< T >::Node::clone().

◆ value() [1/2]

template<typename T >

const Value * Aleph::Prefix_Tree_Map< T >::Node::value ( ) const

inlinenoexcept

Return the stored mapped value.

Returns: Const pointer to the value, or nullptr.

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

References Aleph::Prefix_Tree_Map< T >::Node::value_.

Referenced by Aleph::Prefix_Tree_Map< T >::Node::emplace_value(), Aleph::Prefix_Tree_Map< T >::find(), Aleph::Prefix_Tree_Map< T >::find(), and Aleph::Prefix_Tree_Map< T >::Node::insert_suffix().

◆ value() [2/2]

template<typename T >

Value * Aleph::Prefix_Tree_Map< T >::Node::value ( )

inlinenoexcept

Return the stored mapped value.

Returns: Mutable pointer to the value, or nullptr.

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

References Aleph::Prefix_Tree_Map< T >::Node::value_.

◆ words_impl()

template<typename T >

void Aleph::Prefix_Tree_Map< T >::Node::words_impl	(	std::string &	word,
		DynArray< std::string > &	out,
		const size_t	max_word_length
	)		const

inline

Append all terminal keys in this subtree.

Parameters

[in,out]	word	Current prefix buffer.
[out]	out	Destination array.
[in]	max_word_length	Maximum expected key length.

Exceptions

std::bad_alloc if appending grows the destination.

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

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Tree_Node< char >::child, Aleph::Tree_Node< char >::get_left_child(), Aleph::Prefix_Tree_Map< T >::Node::has_value(), out, and Aleph::Prefix_Tree_Map< T >::Node::words_impl().

Referenced by Aleph::Prefix_Tree_Map< T >::words(), and Aleph::Prefix_Tree_Map< T >::Node::words_impl().

Member Data Documentation

◆ value_

template<typename T >

std::optional<Value> Aleph::Prefix_Tree_Map< T >::Node::value_

private

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

Referenced by Aleph::Prefix_Tree_Map< T >::Node::emplace_value(), Aleph::Prefix_Tree_Map< T >::Node::has_value(), Aleph::Prefix_Tree_Map< T >::Node::reset_value(), Aleph::Prefix_Tree_Map< T >::Node::value(), and Aleph::Prefix_Tree_Map< T >::Node::value().

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

prefix-tree.H

Classes

Public Member Functions

Static Public Member Functions

Static Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ Node() [1/2]

◆ Node() [2/2]

Member Function Documentation

◆ clone()

◆ clone_into()

◆ destroy()

◆ emplace_value()

◆ greater_child() [1/2]

◆ greater_child() [2/2]

◆ greater_child_impl()

◆ has_value()

◆ insert_child()

◆ insert_suffix()

◆ reset_value()

◆ search_child() [1/2]

◆ search_child() [2/2]

◆ search_child_impl()

◆ search_prefix() [1/2]

◆ search_prefix() [2/2]

◆ search_prefix_impl()

◆ symbol()

◆ value() [1/2]

◆ value() [2/2]

◆ words_impl()

Member Data Documentation

◆ value_