Owning prefix tree wrapper. More...

#include <prefix-tree.H>

Collaboration diagram for Aleph::Prefix_Tree:

Public Member Functions
	Prefix_Tree ()
	Construct an empty prefix tree.

	Prefix_Tree (const Prefix_Tree &other)
	Construct a deep copy of another prefix tree.

	Prefix_Tree (Prefix_Tree &&other)
	Move-construct, taking ownership of another tree's contents.

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

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

Prefix_Tree &	operator= (Prefix_Tree &&other)
	Move-assign, taking ownership of another tree's contents.

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

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

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

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

size_t	count () const noexcept
	Count the words stored in the tree.

size_t	size () const noexcept
	Return the number of words stored in the tree.

Cnode *	root () noexcept
	Return the mutable root node.

const Cnode *	root () const noexcept
	Return the const root node.

Private Member Functions
void	swap_state (Prefix_Tree &other) noexcept
	Swap internal ownership and cached count state.

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

Private Attributes
Cnode *	root_ = nullptr

size_t	word_count_ = 0

bool	count_dirty_ = false

bool	mutable_root_exposed_ = false

Detailed Description

Owning prefix tree wrapper.

Prefix_Tree owns a root Cnode and destroys all descendant nodes in its destructor. It provides the same common word-level operations as Cnode, while preserving Cnode as the low-level node API for legacy code and manual tree manipulation.

Copies are deep copies. The root returned by root() is non-owning; callers must not delete it or call destroy_tree() on it.

Thread-safety: None. This is a sequential container; callers must externally synchronize concurrent access to the same object. This includes concurrent const calls to count() or size(), because those functions may refresh the mutable cached word count after the low-level mutable root() API has been exposed.

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

Constructor & Destructor Documentation

◆ Prefix_Tree() [1/3]

Aleph::Prefix_Tree::Prefix_Tree ( )

inline

Construct an empty prefix tree.

The root node uses the conventional ‘’\0'` symbol; the symbol is not part of any stored word.

Exceptions

std::bad_alloc If allocating the root node fails.

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

◆ Prefix_Tree() [2/3]

Aleph::Prefix_Tree::Prefix_Tree ( const Prefix_Tree & other )

inline

Construct a deep copy of another prefix tree.

Parameters

[in] other Tree to copy.

Exceptions

std::bad_alloc If allocating any copied node fails.

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

◆ Prefix_Tree() [3/3]

Aleph::Prefix_Tree::Prefix_Tree ( Prefix_Tree && other )

inline

Move-construct, taking ownership of another tree's contents.

Parameters

[in,out] other Tree to move from. Left as a valid empty tree.

Exceptions

std::bad_alloc If allocating the replacement empty root for other fails; in that case other is left unchanged.

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

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

◆ ~Prefix_Tree()

Aleph::Prefix_Tree::~Prefix_Tree ( )

inlinenoexcept

Destroy the owned root and all descendants.

This destructor does not throw.

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

References destroy_root(), and root_.

Member Function Documentation

◆ contains()

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

inlinenoexcept

Check whether a word exists in the tree.

Parameters

[in] word Word to search for.

Returns: true if the word exists, false otherwise.

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

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Cnode::contains(), and root_.

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

◆ count()

size_t Aleph::Prefix_Tree::count ( ) const

inlinenoexcept

Count the words stored in the tree.

Returns: Number of complete words.

Note: This is O(1) while the tree is modified only through Prefix_Tree. If the mutable root() API was used, this recomputes in O(n), because external code may keep the root pointer and mutate the low-level Cnode API between calls.

Warning: This const method may update the internal mutable cache. It is not safe to call concurrently on the same tree without external synchronization.

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

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Cnode::count(), count_dirty_, mutable_root_exposed_, root_, and word_count_.

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

◆ destroy_root()

static void Aleph::Prefix_Tree::destroy_root ( Cnode * root )

inlinestaticprivatenoexcept

Destroy an owned root and all its descendants.

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

References Aleph::Cnode::destroy(), and root().

Referenced by ~Prefix_Tree(), and operator=().

◆ insert_word()

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

inline

Insert a word into the tree.

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.

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

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), count_dirty_, Aleph::Cnode::insert_word(), mutable_root_exposed_, root_, and word_count_.

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

◆ operator=() [1/2]

Prefix_Tree & Aleph::Prefix_Tree::operator= ( const Prefix_Tree & other )

inline

Replace this tree with a deep copy of another tree.

Parameters

[in] other Tree to copy from.

Returns: Reference to this tree.

Exceptions

std::bad_alloc If allocating any copied node fails.

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

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

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Cnode::clone(), count_dirty_, destroy_root(), mutable_root_exposed_, root_, and word_count_.

◆ operator=() [2/2]

Prefix_Tree & Aleph::Prefix_Tree::operator= ( Prefix_Tree && other )

inline

Move-assign, taking ownership of another tree's contents.

Parameters

[in,out] other Tree to move from. Left as a valid empty tree.

Returns: Reference to this tree.

Exceptions

std::bad_alloc If allocating the replacement empty root for other fails; in that case both trees are left unchanged.

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

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

◆ root() [1/2]

const Cnode * Aleph::Prefix_Tree::root ( ) const

inlinenoexcept

Return the const root node.

Returns: Non-owning pointer to the root node.

Note: The returned root remains owned by this Prefix_Tree. Do not delete it or call destroy_tree() on it.

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

References root_.

◆ root() [2/2]

Cnode * Aleph::Prefix_Tree::root ( )

inlinenoexcept

Return the mutable root node.

Returns: Non-owning pointer to the root node.

Note: The returned root remains owned by this Prefix_Tree. Do not delete it or call destroy_tree() on it.

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

References count_dirty_, mutable_root_exposed_, and root_.

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

◆ size()

size_t Aleph::Prefix_Tree::size ( ) const

inlinenoexcept

Return the number of words stored in the tree.

Returns: Number of complete words.

Note: Alias for count(); it has the same cache-refresh and thread-safety caveats.

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

References count().

Referenced by demo_command_autocomplete(), demo_performance(), demo_prefix_search(), demo_spell_checker(), TEST(), TEST(), and TEST().

◆ swap_state()

void Aleph::Prefix_Tree::swap_state ( Prefix_Tree & other )

inlineprivatenoexcept

Swap internal ownership and cached count state.

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

References Aleph::blossom_maximum_cardinality_matching(), count_dirty_, mutable_root_exposed_, root_, and word_count_.

Referenced by Prefix_Tree(), and operator=().

◆ words()

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

inline

Get all words stored in the tree.

Parameters

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

Returns: Array containing all words.

Exceptions

std::bad_alloc If memory allocation fails.

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

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

References Aleph::blossom_maximum_cardinality_matching(), root_, and Aleph::Cnode::words().

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

◆ words_with_prefix()

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

inline

Get all words with a given prefix.

Parameters

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

Returns: Array containing all matching words.

Exceptions

std::bad_alloc If memory allocation fails.

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

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

References Aleph::blossom_maximum_cardinality_matching(), Aleph::prefix(), root_, and Aleph::Cnode::words_with_prefix().

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

Member Data Documentation

◆ count_dirty_

bool Aleph::Prefix_Tree::count_dirty_ = false

mutableprivate

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

Referenced by count(), insert_word(), operator=(), root(), and swap_state().

◆ mutable_root_exposed_

bool Aleph::Prefix_Tree::mutable_root_exposed_ = false

mutableprivate

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

Referenced by count(), insert_word(), operator=(), root(), and swap_state().

◆ root_

Cnode* Aleph::Prefix_Tree::root_ = nullptr

private

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

Referenced by ~Prefix_Tree(), contains(), count(), insert_word(), operator=(), root(), root(), swap_state(), words(), and words_with_prefix().

◆ word_count_

size_t Aleph::Prefix_Tree::word_count_ = 0

mutableprivate

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

Referenced by count(), insert_word(), operator=(), and swap_state().

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

prefix-tree.H

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ Prefix_Tree() [1/3]

◆ Prefix_Tree() [2/3]

◆ Prefix_Tree() [3/3]

◆ ~Prefix_Tree()

Member Function Documentation

◆ contains()

◆ count()

◆ destroy_root()

◆ insert_word()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ root() [1/2]

◆ root() [2/2]

◆ size()

◆ swap_state()

◆ words()

◆ words_with_prefix()

Member Data Documentation

◆ count_dirty_

◆ mutable_root_exposed_

◆ root_

◆ word_count_