Low-level prefix tree node for storing character sequences. More...

#include <prefix-tree.H>

Inheritance diagram for Aleph::Cnode:

Collaboration diagram for Aleph::Cnode:

Classes
class	Clone_Target_Rollback
	Restore a clone target if appending cloned children fails. More...

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

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

Public Member Functions
	Cnode (const char c) noexcept
	Construct a node with the given character.

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

DynList< Cnode * >	children () const
	Return a list of all child nodes.

std::string	to_str () const
	Convert the subtree to a string representation.

bool	is_end_word () const noexcept
	Check if this node marks the end of a word.

void	mark_end_word ()
	Mark this node as the end of a word.

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

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

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

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

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

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

const Cnode *	search_word (const char *word) const noexcept
	Search for a complete word in the tree.

bool	contains (const std::string &word) const noexcept
	Check if a word exists in the tree.

size_t	count () const noexcept
	Count total words stored in this subtree.

DynArray< std::string >	words_with_prefix (const std::string &prefix, const size_t max_word_length=2048) const
	Get all words starting with a given prefix.

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

bool	insert_word (const std::string &word)
	Insert a word into the tree.

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

DynArray< std::string >	words (size_t max_word_length=2048) const
	Get all words stored in this subtree.

void	print_words (const size_t max_word_length=2048) const
	Print all words to stdout.

Cnode *	clone () const
	Create a deep copy of 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 (const Tree_Node< char > src, Tree_Node< char > tgt)
	Clone helper - copies children from src to tgt.

Private Member Functions
void	words_impl (std::string &word, DynArray< std::string > &l, const size_t max_word_length) const

Static Private Member Functions
template<typename Node >
static std::tuple< Node , const char >	search_prefix_impl (Node root, const char prefix) noexcept
	Shared implementation for mutable and const prefix searches.

template<typename Node >
static Node *	search_child_impl (Node *root, const char c) noexcept
	Shared implementation for mutable and const child lookup.

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

Private Attributes
bool	ends_word_ = false

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

Low-level prefix tree node for storing character sequences.

Cnode implements a prefix tree (also known as a trie or digital tree) where each node represents a character. Words are stored as paths from the root. A node-local flag marks complete word endings, so every character value can be used as ordinary input data.

This is the legacy/manual node API. A Cnode does not own its descendants in its destructor; callers that build trees directly with Cnode must call destroy() before the root node is destroyed. Prefer Prefix_Tree when a normal owning container is desired.

Features

Insert: O(m) where m is word length
Search: O(m) where m is word length
Prefix search: O(m) where m is prefix length
Space: O(ALPHABET_SIZE * N * M) worst case

Low-level Usage Example

// Create a manual root node. Its symbol is not part of stored words.
Cnode root('\0');
 
// Insert words
root.insert_word("hello");
root.insert_word("help");
root.insert_word("world");
 
// Search for words
if (root.contains("hello"))
  std::cout << "Found 'hello'\n";
 
// Get all words
auto all_words = root.words();
all_words.for_each([](const std::string& w) {
  std::cout << w << "\n";
});
 
// Search by prefix
auto [node, remaining] = root.search_prefix("hel");
// node points to 'l' in "hel", remaining is ""
 
// Manual cleanup is required when using Cnode directly.
root.destroy();

Implementation Details

Children are stored in sorted order by character for efficient lookup
Word endings are marked by state stored in the terminal node
The tree uses a leftmost-child, right-sibling representation
to_str() reports structural nodes only; word-ending flags are not shown as sentinel children

See also: Prefix_Tree; Tree_Node

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

Constructor & Destructor Documentation

◆ Cnode()

Aleph::Cnode::Cnode ( const char c )

inlineexplicitnoexcept

Construct a node with the given character.

Parameters

[in] c Character to store in this node.

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

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

Member Function Documentation

◆ children()

DynList< Cnode * > Aleph::Cnode::children ( ) const

inline

Return a list of all child nodes.

Returns: DynList containing pointers to all children.

Note: This creates a new list on each call. For iteration, consider using for_each_child() directly.

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

References Aleph::Tree_Node< char >::for_each_child(), and r.

Referenced by TEST_F(), and TEST_F().

◆ clone() [1/2]

Cnode * Aleph::Cnode::clone ( ) const

inline

Create a deep copy of this subtree.

Returns: Pointer to the cloned tree root.

Exceptions

std::bad_alloc If memory allocation fails.

Note: Provides the strong guarantee: no partially cloned tree leaks if allocation fails.

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

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

Referenced by clone(), and clone().

◆ clone() [2/2]

static void Aleph::Cnode::clone	(	const Tree_Node< char > *	src,
		Tree_Node< char > *	tgt
	)

inlinestatic

Clone helper - copies children from src to tgt.

Parameters

[in]	src	Source node to copy from.
[out]	tgt	Target node to copy to.

Exceptions

std::bad_alloc If memory allocation fails.

Note: Provides the strong guarantee for tgt: if cloning throws, any children appended by this call are removed and the previous word-ending flag is restored.

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

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

Referenced by Aleph::Prefix_Tree::operator=(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ contains()

bool Aleph::Cnode::contains ( const std::string & word ) const

inlinenoexcept

Check if a word exists in the tree.

Parameters

[in] word Word to search for.

Returns: true if the word exists, false otherwise.

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

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

Referenced by Aleph::Prefix_Tree::contains().

◆ count()

size_t Aleph::Cnode::count ( ) const

inlinenoexcept

Count total words stored in this subtree.

Returns: Number of complete words.

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

References count(), Aleph::Tree_Node< char >::for_each_child(), and is_end_word().

Referenced by count(), and Aleph::Prefix_Tree::count().

◆ destroy()

void Aleph::Cnode::destroy ( )

inlinenoexcept

Destroy all children of this node.

Recursively deletes all descendant nodes. The node itself is not deleted.

Definition at line 617 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::Cnode::Detached_Subtree_Guard::~Detached_Subtree_Guard(), Aleph::Prefix_Tree::destroy_root(), and PrefixTreeTest::TearDown().

◆ greater_child() [1/2]

const Cnode * Aleph::Cnode::greater_child ( const char c ) const

inlinenoexcept

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

Used for inspecting the sorted child order.

Parameters

[in] c Character threshold.

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

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

References greater_child_impl().

◆ greater_child() [2/2]

Cnode * Aleph::Cnode::greater_child ( const char c )

inlinenoexcept

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

Used for maintaining sorted order of children.

Parameters

[in] c Character threshold.

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

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

References greater_child_impl().

Referenced by insert_child().

◆ greater_child_impl()

template<typename Node >

static Node * Aleph::Cnode::greater_child_impl	(	Node *	root,
		const char	c
	)

inlinestaticprivatenoexcept

Shared implementation for mutable and const sorted-child lookup.

Template Parameters

Node	Either `Cnode` or `const Cnode`.

Parameters

[in]	root	Node whose children are searched.
[in]	c	Character threshold.

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

Precondition: root must not be nullptr.

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

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

Referenced by greater_child(), and greater_child().

◆ insert_child()

Cnode * Aleph::Cnode::insert_child ( Cnode * child )

inline

Insert a child node in sorted order.

Children are maintained in ascending order by character.

Parameters

[in] child Node to insert.

Returns: Pointer to the inserted child.

Precondition: No child with the same character should exist.

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

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

◆ insert_word()

bool Aleph::Cnode::insert_word ( const std::string & word )

inline

Insert a word into the tree.

Creates all necessary nodes for the word and marks the ending.

Parameters

[in] word Word to insert.

Returns: true if the word was inserted, false if it already existed.

Exceptions

std::bad_alloc If memory allocation fails.

Note: Provides the strong guarantee for allocation failures: if inserting a new path throws, the trie is restored to its previous logical contents.

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

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Cnode::Pending_Path_Guard::release_nodes(), search_prefix(), and Aleph::Cnode::Pending_Path_Guard::set().

Referenced by Aleph::Prefix_Tree::insert_word(), and TEST().

◆ is_end_word()

bool Aleph::Cnode::is_end_word ( ) const

inlinenoexcept

Check if this node marks the end of a word.

A word ending is stored as node state instead of as a child sentinel.

Returns: true if this node ends a word, false otherwise.

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

References ends_word_.

Referenced by count(), mark_end_word(), TEST_F(), TEST_F(), and words_impl().

◆ mark_end_word()

void Aleph::Cnode::mark_end_word ( )

inline

Mark this node as the end of a word.

Sets the node-local word-ending flag.

Precondition: The node must not already be marked as a word ending.

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

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

Referenced by TEST_F().

◆ print_words()

void Aleph::Cnode::print_words ( const size_t max_word_length = 2048 ) const

inline

Print all words to stdout.

Parameters

[in] max_word_length Maximum expected word length (default 2048).

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

References Aleph::blossom_maximum_cardinality_matching(), FunctionalMethods< Container, T >::for_each(), w, and words().

◆ search_child() [1/2]

const Cnode * Aleph::Cnode::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 if not found.

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

References search_child_impl().

◆ search_child() [2/2]

Cnode * Aleph::Cnode::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 if not found.

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

References search_child_impl().

Referenced by insert_child().

◆ search_child_impl()

template<typename Node >

static Node * Aleph::Cnode::search_child_impl	(	Node *	root,
		const char	c
	)

inlinestaticprivatenoexcept

Shared implementation for mutable and const child lookup.

Template Parameters

Node	Either `Cnode` or `const Cnode`.

Parameters

[in]	root	Node whose children are searched.
[in]	c	Character to search for.

Returns: Pointer to the matching child, or nullptr if not found.

Precondition: root must not be nullptr.

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

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

Referenced by search_child(), and search_child().

◆ search_prefix() [1/2]

std::tuple< const Cnode *, const char * > Aleph::Cnode::search_prefix ( const char * prefix ) const

inlinenoexcept

Search for a prefix in the const tree.

Traverses the tree following the characters in prefix.

Parameters

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

Returns: Tuple of (node reached, remaining unmatched suffix). If the entire prefix was found, remaining is "".

Precondition: prefix must not be nullptr.

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

References Aleph::prefix(), and search_prefix_impl().

◆ search_prefix() [2/2]

std::tuple< Cnode *, const char * > Aleph::Cnode::search_prefix ( const char * prefix )

inlinenoexcept

Search for a prefix in the mutable tree.

Traverses the tree following the characters in prefix.

Parameters

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

Returns: Tuple of (node reached, remaining unmatched suffix). If the entire prefix was found, remaining is "".

Precondition: prefix must not be nullptr.

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

References Aleph::prefix(), and search_prefix_impl().

Referenced by insert_word(), and words_with_prefix().

◆ search_prefix_impl()

template<typename Node >

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

inlinestaticprivatenoexcept

Shared implementation for mutable and const prefix searches.

Template Parameters

Node	Either `Cnode` or `const Cnode`.

Parameters

[in]	root	Node where the search starts.
[in]	prefix	Null-terminated prefix to search for.

Returns: Tuple of (node reached, remaining unmatched suffix). If the entire prefix was found, remaining is "".

Precondition: root and prefix must not be nullptr.

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

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

Referenced by search_prefix(), and search_prefix().

◆ search_word()

const Cnode * Aleph::Cnode::search_word ( const char * word ) const

inlinenoexcept

Search for a complete word in the tree.

Parameters

[in] word Null-terminated string to search for.

Returns: Pointer to the ending node if found, nullptr otherwise.

Precondition: word must not be nullptr.

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

References Aleph::blossom_maximum_cardinality_matching().

Referenced by contains().

◆ symbol()

char Aleph::Cnode::symbol ( ) const

inlinenoexcept

Return the character stored in this node.

Returns: The character value.

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

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

Referenced by clone(), TEST(), TEST_F(), TEST_F(), and to_str().

◆ to_str()

std::string Aleph::Cnode::to_str ( ) const

inline

Convert the subtree to a string representation.

Returns: String representation of the tree structure.

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

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Tree_Node< char >::for_each_child(), symbol(), and to_str().

Referenced by to_str().

◆ words()

DynArray< std::string > Aleph::Cnode::words ( size_t max_word_length = 2048 ) const

inline

Get all words stored in this subtree.

Parameters

[in] max_word_length Maximum expected word length (default 2048).

Returns: Array containing all words.

Note: Reuses a single temporary string buffer during traversal.

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

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

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

Referenced by print_words(), and Aleph::Prefix_Tree::words().

◆ words_impl()

void Aleph::Cnode::words_impl	(	std::string &	word,
		DynArray< std::string > &	l,
		const size_t	max_word_length
	)		const

inlineprivate

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

References Aleph::DynList< T >::append(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Tree_Node< char >::child, Aleph::Tree_Node< char >::get_left_child(), is_end_word(), l, and words_impl().

Referenced by words(), and words_impl().

◆ words_with_prefix()

DynArray< std::string > Aleph::Cnode::words_with_prefix	(	const std::string &	prefix,
		const size_t	max_word_length = `2048`
	)		const

inline

Get all words starting with a given prefix.

Parameters

[in]	prefix	Prefix to search for.
[in]	max_word_length	Maximum expected word length (default 2048).

Returns: Array of words that start with prefix.

Note: An empty prefix returns the same set of words as words().

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

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

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

Referenced by Aleph::Prefix_Tree::words_with_prefix().

Member Data Documentation

◆ ends_word_

bool Aleph::Cnode::ends_word_ = false

private

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

Referenced by Aleph::Cnode::Clone_Target_Rollback::Clone_Target_Rollback(), Aleph::Cnode::Clone_Target_Rollback::~Clone_Target_Rollback(), is_end_word(), and mark_end_word().

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

prefix-tree.H

Classes

Public Member Functions

Static Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Features

Low-level Usage Example

Implementation Details

Constructor & Destructor Documentation

◆ Cnode()

Member Function Documentation

◆ children()

◆ clone() [1/2]

◆ clone() [2/2]

◆ contains()

◆ count()

◆ destroy()

◆ greater_child() [1/2]

◆ greater_child() [2/2]

◆ greater_child_impl()

◆ insert_child()

◆ insert_word()

◆ is_end_word()

◆ mark_end_word()

◆ print_words()

◆ search_child() [1/2]

◆ search_child() [2/2]

◆ search_child_impl()

◆ search_prefix() [1/2]

◆ search_prefix() [2/2]

◆ search_prefix_impl()

◆ search_word()

◆ symbol()

◆ to_str()

◆ words()

◆ words_impl()

◆ words_with_prefix()

Member Data Documentation

◆ ends_word_