Lazy, composable graph traversal framework built on C++20 generators. More...

#include <deque>
#include <list>
#include <optional>
#include <type_traits>
#include <utility>
#include <vector>
#include <entttree/defs.h>
#include <entttree/generator.h>

Classes
struct	entttree::Traversal< Node_, Successors_ >
	A lazy description of a rooted graph traversal. More...

Concepts
concept	entttree::GeneratorConcept
	A type `G` that can be advanced, dereferenced, and tested for exhaustion.

concept	entttree::TraversalConcept
	Satisfied by types that have a root and a successors function yielding `Node`.

concept	entttree::AnyTraversalConcept
	Satisfied by any type that is a Traversal over its own Node type.

Typedefs
template<typename T >
using	entttree::TraversalValue = std::remove_cvref_t< T >
	Strip references/cv to get the bare Traversal type.

template<typename T >
using	entttree::TraversalNode = typename TraversalValue< T >::Node
	Extract the Node type from a Traversal (after stripping cvref).

template<typename T >
using	entttree::TraversalSuccessors = typename TraversalValue< T >::Successors
	Extract the Successors callable type from a Traversal.

template<typename Successors , typename Node >
using	entttree::SuccessorGenerator = std::invoke_result_t< Successors &, Node & >
	The generator type returned by a successor function.

template<typename Successors , typename Node >
using	entttree::SuccessorOutput = decltype(*std::declval< SuccessorGenerator< Successors, Node > & >())
	The value type yielded by a successor generator.

template<typename Traversal >
using	entttree::TraversalOutput = SuccessorOutput< TraversalSuccessors< Traversal >, TraversalNode< Traversal > >
	The value type yielded by a traversal's successor generator.

template<typename Traversal >
using	entttree::TraversalGenerator = std::remove_cvref_t< SuccessorGenerator< TraversalSuccessors< Traversal >, TraversalNode< Traversal > > >
	The concrete generator type produced by a traversal's successor function.

Functions
template<typename Node , typename Successors > requires requires (Successors s, Node& n) { { s(n) } -> GeneratorConcept<Node>; }
auto	entttree::make_traversal (std::optional< Node > &&root, Successors &&successors)
	Construct a Traversal from an optional root and a successor function.

template<typename Node , typename Successors > requires requires (Successors s, Node& n) { { s(n) } -> GeneratorConcept<Node>; }
auto	entttree::make_traversal (const std::optional< Node > &root, Successors &&successors)
	Construct a Traversal from an optional root and a successor function.

template<typename Node , typename Successors > requires requires (Successors s, std::remove_cvref_t<Node>& n) { { s(n) } -> GeneratorConcept<std::remove_cvref_t<Node>>; }
auto	entttree::make_traversal (Node &&root, Successors &&successors)

template<AnyTraversalConcept T, typename Filter >
auto	entttree::walk::prune_if (T &&t, Filter should_explore)
	Prevent certain nodes from generating successors.

template<AnyTraversalConcept T, typename Filter >
auto	entttree::walk::exclude_if (T &&t, Filter should_admit)
	Remove certain nodes from the graph entirely.

template<AnyTraversalConcept T>
auto	entttree::walk::reverse_successors (T &&t)
	Reverse the order of each node's successors.

template<AnyTraversalConcept Traversal, typename Transform >
auto	entttree::walk::map_nodes (Traversal &&t, Transform &&xform)
	Transform the node type of a traversal.

template<DfsOrder recursion_order = DfsOrder::ShallowFirst, AnyTraversalConcept T>
auto	entttree::walk::dfs (T &&t)
	Flatten a Traversal into a depth-first Generator.

template<AnyTraversalConcept T>
auto	entttree::walk::dfs (T &&t, DfsOrder recursion_order)

template<AnyTraversalConcept T>
auto	entttree::walk::bfs (T &&t)
	Flatten a Traversal into a breadth-first Generator.

and std::invocable< Get &, Value & > auto	entttree::inductive_transform (Trav &&t, Compose &&make_successor, Get &&get_node)

Variables
template<typename Node , typename Value , typename Trav , typename Compose , typename Get >
	entttree::and
	Transform a traversal inductively, threading parent context through successors.

Detailed Description

Lazy, composable graph traversal framework built on C++20 generators.

A Traversal encapsulates a starting node (root) and a successor function that generates children for each node. The traversal itself is abstract — it describes the structure of the graph rather than a specific walk order.

Traversal adaptors (in the walk namespace) compose to filter, prune, map, or reverse the successor structure. Walk functions (walk::dfs, walk::bfs) flatten a Traversal into a linear Generator of nodes.

Definition in file traverse.h.

Typedef Documentation

◆ SuccessorGenerator

template<typename Successors , typename Node >

using entttree::SuccessorGenerator = typedef std::invoke_result_t<Successors&, Node&>

The generator type returned by a successor function.

Definition at line 126 of file traverse.h.

◆ SuccessorOutput

template<typename Successors , typename Node >

using entttree::SuccessorOutput = typedef decltype(*std::declval<SuccessorGenerator<Successors,Node>&>())

The value type yielded by a successor generator.

Definition at line 130 of file traverse.h.

◆ TraversalGenerator

template<typename Traversal >

using entttree::TraversalGenerator = typedef std::remove_cvref_t< SuccessorGenerator< TraversalSuccessors<Traversal>, TraversalNode<Traversal> > >

The concrete generator type produced by a traversal's successor function.

Definition at line 141 of file traverse.h.

◆ TraversalNode

template<typename T >

using entttree::TraversalNode = typedef typename TraversalValue<T>::Node

Extract the Node type from a Traversal (after stripping cvref).

Definition at line 90 of file traverse.h.

◆ TraversalOutput

template<typename Traversal >

using entttree::TraversalOutput = typedef SuccessorOutput< TraversalSuccessors<Traversal>, TraversalNode<Traversal> >

The value type yielded by a traversal's successor generator.

Definition at line 134 of file traverse.h.

◆ TraversalSuccessors

template<typename T >

using entttree::TraversalSuccessors = typedef typename TraversalValue<T>::Successors

Extract the Successors callable type from a Traversal.

Definition at line 94 of file traverse.h.

◆ TraversalValue

template<typename T >

using entttree::TraversalValue = typedef std::remove_cvref_t<T>

Strip references/cv to get the bare Traversal type.

Definition at line 86 of file traverse.h.

Function Documentation

◆ bfs()

template<AnyTraversalConcept T>

auto entttree::walk::bfs ( T && t )

Flatten a Traversal into a breadth-first Generator.

Nodes are visited level by level, using an internal queue.

Definition at line 503 of file traverse.h.

References entttree::walk::bfs().

Referenced by entttree::walk::bfs().

◆ dfs() [1/2]

template<DfsOrder recursion_order = DfsOrder::ShallowFirst, AnyTraversalConcept T>

auto entttree::walk::dfs ( T && t )

Flatten a Traversal into a depth-first Generator.

The walk order is selected at compile time via the template parameter. Uses an explicit stack (not recursion) for efficiency.

Template Parameters

recursion_order DfsOrder::ShallowFirst (pre-order, default) or DfsOrder::DeepFirst (post-order).

Definition at line 472 of file traverse.h.

References entttree::walk::dfs().

Referenced by entttree::walk::dfs().

◆ dfs() [2/2]

template<AnyTraversalConcept T>

auto entttree::walk::dfs	(	T &&	t,
		DfsOrder	recursion_order
	)

Definition at line 486 of file traverse.h.

◆ exclude_if()

template<AnyTraversalConcept T, typename Filter >

auto entttree::walk::exclude_if	(	T &&	t,
		Filter	should_admit
	)

Remove certain nodes from the graph entirely.

If should_admit(node) returns true, the node is visited; otherwise it is skipped. Excluded nodes are not explored, so their subtrees are also excluded. To visit a node but suppress its children, use prune_if().

Parameters

t	The source traversal.
should_admit	`(const Node&) -> bool`

Definition at line 266 of file traverse.h.

References entttree::and, entttree::walk::exclude_if(), and entttree::make_traversal().

Referenced by entttree::walk::exclude_if().

◆ inductive_transform()

and std::invocable< Get &, Value & > auto entttree::inductive_transform	(	Trav &&	t,
		Compose &&	make_successor,
		Get &&	get_node
	)

Definition at line 546 of file traverse.h.

◆ make_traversal() [1/3]

template<typename Node , typename Successors >
requires requires (Successors s, Node& n) { { s(n) } -> GeneratorConcept<Node>; }

auto entttree::make_traversal	(	const std::optional< Node > &	root,
		Successors &&	successors
	)

Definition at line 181 of file traverse.h.

References entttree::make_traversal().

◆ make_traversal() [2/3]

template<typename Node , typename Successors >
requires requires (Successors s, std::remove_cvref_t<Node>& n) { { s(n) } -> GeneratorConcept<std::remove_cvref_t<Node>>; }

auto entttree::make_traversal	(	Node &&	root,
		Successors &&	successors
	)

Definition at line 198 of file traverse.h.

◆ make_traversal() [3/3]

template<typename Node , typename Successors >
requires requires (Successors s, Node& n) { { s(n) } -> GeneratorConcept<Node>; }

auto entttree::make_traversal	(	std::optional< Node > &&	root,
		Successors &&	successors
	)

Construct a Traversal from an optional root and a successor function.

Parameters

root	The starting node (or empty to create a disabled traversal).
successors	A callable `(Node&) -> Generator<Node>` that yields the children of a given node.

Definition at line 164 of file traverse.h.

References entttree::make_traversal().

Referenced by entttree::TransformSystem< HTag, T, N, XTag >::augment_with_transforms(), entttree::walk::exclude_if(), entttree::make_traversal(), entttree::make_traversal(), entttree::walk::map_nodes(), entttree::walk::prune_if(), entttree::walk::reverse_successors(), and entttree::HierarchySystem< HTag >::traverse().

◆ map_nodes()

template<AnyTraversalConcept Traversal, typename Transform >

auto entttree::walk::map_nodes	(	Traversal &&	t,
		Transform &&	xform
	)

Transform the node type of a traversal.

Applies xform(Node&) -> Value to every node, producing a new Traversal with node type Value. Common uses include extracting fields from a node or augmenting it with additional computed data.

Parameters

t	The source traversal.
xform	`(Node&) -> Value`

Definition at line 340 of file traverse.h.

References entttree::make_traversal(), and entttree::walk::map_nodes().

Referenced by entttree::walk::map_nodes().

◆ prune_if()

template<AnyTraversalConcept T, typename Filter >

auto entttree::walk::prune_if	(	T &&	t,
		Filter	should_explore
	)

Prevent certain nodes from generating successors.

If should_explore(node) returns true, the node's children are explored normally; otherwise the node generates zero successors. The node itself is still visited regardless — to suppress the node entirely, use exclude_if() instead.

Parameters

t	The source traversal.
should_explore	`(const Node&) -> bool`

Definition at line 233 of file traverse.h.

References entttree::make_traversal(), and entttree::walk::prune_if().

Referenced by entttree::walk::prune_if().

◆ reverse_successors()

template<AnyTraversalConcept T>

auto entttree::walk::reverse_successors ( T && t )

Reverse the order of each node's successors.

This is a generic operation that buffers all children of each node before yielding them in reverse. If the traversal source can enumerate children in reverse cheaply (e.g. HierarchySystem::children(..., SiblingOrder::Backward)), prefer that approach instead.

Definition at line 305 of file traverse.h.

References entttree::make_traversal(), and entttree::walk::reverse_successors().

Referenced by entttree::walk::reverse_successors().

Variable Documentation

◆ and

template<typename Node , typename Value , typename Trav , typename Compose , typename Get >

entttree::and

Initial value:

{

{ c(parent, std::move(n)) } -> std::convertible_to<std::optional<Value>>

Transform a traversal inductively, threading parent context through successors.

Changes the traversal from node type Node to Value, where each child's value is computed from its parent's value and the original child node.

Parameters

t	The source traversal.
make_successor	`(optional<Value>& parent, Node&& child) -> optional<Value>`. The root's parent is `std::nullopt`. If the function returns `std::nullopt`, the node is skipped.
get_node	`(Value&) -> Node&` extracts the original node from a Value so the inner successor function can operate on it.

Definition at line 542 of file traverse.h.

Referenced by entttree::Position::after(), entttree::Position::before(), entttree::walk::exclude_if(), entttree::HierarchySystem< HTag >::is_ancestor_of(), entttree::Generator< T, V >::is_valid(), entttree::HierarchySystem< HTag >::order_child_before(), entttree::HierarchySystem< HTag >::path(), entttree::BoundsSystem< HTag, T, N, BTag, XTag >::remove_intrinsic_bounds(), entttree::BoundsSystem< HTag, T, N, BTag, XTag >::search_under_point(), and entttree::HierarchySystem< HTag >::set_parent().

Classes

Concepts

Typedefs

Functions

Variables

Detailed Description

Typedef Documentation

◆ SuccessorGenerator

◆ SuccessorOutput

◆ TraversalGenerator

◆ TraversalNode

◆ TraversalOutput

◆ TraversalSuccessors

◆ TraversalValue

Function Documentation

◆ bfs()

◆ dfs() [1/2]

◆ dfs() [2/2]

◆ exclude_if()

◆ inductive_transform()

◆ make_traversal() [1/3]

◆ make_traversal() [2/3]

◆ make_traversal() [3/3]

◆ map_nodes()

◆ prune_if()

◆ reverse_successors()

Variable Documentation

◆ and