Prefix tree (Trie) node for storing character sequences. More...

#include <prefix-tree.H>

Inheritance diagram for Aleph::Cnode:

Collaboration diagram for Aleph::Cnode:

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) const noexcept
	Search for a child with the given character.

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

std::tuple< const Cnode , const char >	search_prefix (const char *prefix) const noexcept
	Search for a prefix in the 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

Dlink *	get_sibling_list () noexcept

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

void	set_is_leaf (bool value) noexcept

void	set_is_leftmost (bool value) noexcept

void	set_is_rightmost (bool value) noexcept

	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 as the right sibling of this.

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 forrest.

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 >
auto	for_each (Operation &operation) const -> decltype(self())
	Apply an operation to each element (read-only).

template<class Operation >
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 >
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 >
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 >
auto	mutable_for_each (Operation &operation) -> decltype(self())
	Apply an operation to each element (mutable).

template<class Operation >
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 >
bool	all (Operation &operation) const
	Test if all elements satisfy a predicate.

template<class Operation >
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 >
bool	forall (Operation &operation) const
	Alias for all().

template<class Operation >
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 >
bool	exists (Operation &operation) const
	Test if any element satisfies a predicate.

template<class Operation >
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>>
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>>
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 >
Type	fold (const Type &init, Operation &operation) const
	Simple fold with same type for accumulator and elements.

template<class Operation >
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 >
DynList< Type >	filter (Operation &operation) const
	Filter elements by a predicate.

template<class Operation >
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 >
DynList< std::tuple< Type, size_t > >	pfilter (Operation &operation) const
	Filter with position information.

template<class Operation >
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 >
std::pair< DynList< Type >, DynList< Type > >	partition (Operation &op) const
	Partition elements by a predicate.

template<class Operation >
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 >
std::tuple< DynList< Type >, DynList< Type > >	tpartition (Operation &op) const
	Partition returning tuple instead of pair.

template<class Operation >
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 >
const Type *	min_by (Compare cmp) const
	Find the minimum element using a custom comparator.

template<class Compare >
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 >
bool	none (Predicate &pred) const
	Check if no element satisfies a predicate.

template<class Predicate >
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 >
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 >
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 >
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 (FixedStack< char > &stack, DynArray< std::string > &l) const

Static Private Member Functions
static std::string	extract_word_from_stack (FixedStack< char > &stack)

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

Prefix tree (Trie) 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, with a special '$' character marking word endings.

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

Usage Example

// Create root node (typically with a sentinel character)
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 ""
 
// Clean up
root.destroy();

Implementation Details

Children are stored in sorted order by character for efficient lookup
Word endings are marked with a '$' sentinel child node
The tree uses a leftmost-child, right-sibling representation

See also: Tree_Node

Definition at line 110 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 117 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 135 of file prefix-tree.H.

References Aleph::DynList< T >::append(), and Aleph::Tree_Node< char >::for_each_child().

Referenced by destroy(), TEST_F(), and to_str().

◆ 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.

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

References clone(), Aleph::FunctionalMixin< Derived, Type >::maps(), 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.

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

References clone(), Aleph::Tree_Node< T >::for_each_child(), Aleph::Tree_Node< T >::get_left_child(), Aleph::Tree_Node< T >::insert_rightmost_child(), and Aleph::FunctionalMixin< Derived, Type >::maps().

◆ 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 261 of file prefix-tree.H.

References Aleph::FunctionalMixin< Derived, Type >::maps(), and search_word().

◆ count()

size_t Aleph::Cnode::count ( ) const

inlinenoexcept

Count total words stored in this subtree.

Returns: Number of complete words.

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

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

Referenced by 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 364 of file prefix-tree.H.

References children(), and Aleph::destroy_tree().

Referenced by PrefixTreeTest::TearDown(), and TEST_F().

◆ extract_word_from_stack()

static std::string Aleph::Cnode::extract_word_from_stack ( FixedStack< char > & stack )

inlinestaticprivate

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

References Aleph::FixedStack< T >::base(), Aleph::FunctionalMixin< Derived, Type >::last(), Aleph::FunctionalMixin< Derived, Type >::maps(), Aleph::FixedStack< T >::size(), and Aleph::FixedStack< T >::top().

Referenced by words_impl().

◆ greater_child()

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

inlinenoexcept

Find the first 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 207 of file prefix-tree.H.

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

Referenced by insert_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 317 of file prefix-tree.H.

References Aleph::Tree_Node< char >::child, greater_child(), Aleph::Tree_Node< char >::insert_rightmost_child(), Aleph::FunctionalMixin< Derived, Type >::maps(), search_child(), and Aleph::Tree_Node< char >::sibling.

Referenced by insert_word().

◆ 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.

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

References insert_child(), Aleph::FunctionalMixin< Derived, Type >::maps(), mark_end_word(), and search_prefix().

◆ 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 marked by having a '$' child node.

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

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

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

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

◆ mark_end_word()

void Aleph::Cnode::mark_end_word ( )

inline

Mark this node as the end of a word.

Inserts a '$' sentinel child node.

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

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

References Aleph::Tree_Node< char >::insert_leftmost_child(), is_end_word(), and Aleph::FunctionalMixin< Derived, Type >::maps().

Referenced by insert_word(), and 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 423 of file prefix-tree.H.

References Aleph::FunctionalMixin< Derived, Type >::maps(), w, and words().

◆ search_child()

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

inlinenoexcept

Search for a 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 190 of file prefix-tree.H.

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

Referenced by insert_child(), search_prefix(), and search_word().

◆ search_prefix()

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

inlinenoexcept

Search for a prefix in the 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 "".

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

References Aleph::FunctionalMixin< Derived, Type >::maps(), Aleph::prefix(), search_child(), and search_prefix().

Referenced by insert_word(), search_prefix(), and words_with_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.

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

References is_end_word(), Aleph::FunctionalMixin< Derived, Type >::maps(), search_child(), and search_word().

Referenced by contains(), and search_word().

◆ symbol()

char Aleph::Cnode::symbol ( ) const

inlinenoexcept

Return the character stored in this node.

Returns: The character value.

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

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

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

◆ 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 149 of file prefix-tree.H.

References children(), Aleph::FunctionalMixin< Derived, Type >::maps(), 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: Uses a temporary stack for traversal.

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

References Aleph::Tree_Node< char >::for_each_child(), Aleph::FunctionalMixin< Derived, Type >::maps(), and words_impl().

Referenced by print_words().

◆ words_impl()

void Aleph::Cnode::words_impl	(	FixedStack< char > &	stack,
		DynArray< std::string > &	l
	)		const

inlineprivate

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

References Aleph::DynList< T >::append(), Aleph::Tree_Node< char >::child, extract_word_from_stack(), Aleph::Tree_Node< char >::get_left_child(), l, Aleph::FixedStack< T >::pop(), Aleph::FixedStack< T >::push(), symbol(), 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.

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

References Aleph::FunctionalMixin< Derived, Type >::maps(), Aleph::prefix(), Aleph::FixedStack< T >::push(), and search_prefix().

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

prefix-tree.H

Public Member Functions

Static Public Member Functions

Private Member Functions

Static Private Member Functions

Additional Inherited Members

Detailed Description

Features

Usage Example

Implementation Details

Constructor & Destructor Documentation

◆ Cnode()

Member Function Documentation

◆ children()

◆ clone() [1/2]

◆ clone() [2/2]

◆ contains()

◆ count()

◆ destroy()

◆ extract_word_from_stack()

◆ greater_child()

◆ insert_child()

◆ insert_word()

◆ is_end_word()

◆ mark_end_word()

◆ print_words()

◆ search_child()

◆ search_prefix()

◆ search_word()

◆ symbol()

◆ to_str()

◆ words()

◆ words_impl()

◆ words_with_prefix()