forest.hpp File Reference

Forest (tree-of-sequences) iterators, ranges, and algorithms. More...

#include <array>
#include <atomic>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <utility>
#include <stlab/algorithm/reverse.hpp>
#include <stlab/config.hpp>
#include <stlab/iterator/set_next.hpp>

Go to the source code of this file.

Classes
struct	stlab::child_iterator< I >
	Iterator over the child sequence of a node: adapts a fullorder iterator to visit only immediate children (skipping descendants). More...
struct	stlab::edge_iterator< I, Edge >
	Fullorder iterator restricted to a single edge kind: visits only leading or trailing positions (e.g. preorder vs. postorder when Edge is fixed). More...
struct	stlab::filter_fullorder_iterator< I, P >
	Fullorder iterator that visits only positions whose values satisfy predicate P (skipping others by advancing through the underlying fullorder sequence). More...
struct	stlab::reverse_fullorder_iterator< I >
	Reverses the direction of a fullorder walk while preserving edge semantics (bidirectional). More...
struct	stlab::depth_fullorder_iterator< I >
	Fullorder iterator that tracks depth in the tree as it advances or retreats. More...
struct	stlab::unsafe::set_next_fn< detail::forest_iterator< T > >
class	stlab::forest< T >
	Hierarchical, node-based container: a forest (ordered sequence of trees) with fullorder iterators and child views. More...
struct	stlab::unsafe::set_next_fn< child_iterator< I > >
class	stlab::child_adaptor< Forest >
	Presents the children of a node (given by a fullorder iterator into forest) as a small sequence-like interface: front / back / push_front / push_back / pop_front / pop_back. More...
struct	stlab::forest_range< I >
	Half-open range [begin, end) of forest iterators; used by child_range, preorder_range, etc. More...

Enumerations
enum class	stlab::forest_edge : bool { trailing , leading }
	Leading and trailing visits in a fullorder walk of a node (see forest iterators).

Functions
constexpr auto	stlab::pivot (forest_edge e)
	Toggles a forest_edge between leading and trailing.
template<class I>
void	stlab::pivot (I &i)
	Flips the edge on iterator i in place.
template<class I>
auto	stlab::pivot_of (I i)
	Returns a copy of i with its edge toggled (pivot).
template<class I>
auto	stlab::leading_of (I i)
	Positions i on the leading edge of the same node.
template<class I>
auto	stlab::trailing_of (I i)
	Positions i on the trailing edge of the same node.
constexpr auto	stlab::is_leading (forest_edge e)
	True if e is a leading-edge position.
template<class I>
auto	stlab::is_leading (const I &i)
	True if iterator i is on its node’s leading edge.
constexpr auto	stlab::is_trailing (forest_edge e)
	True if e is a trailing-edge position.
template<class I>
auto	stlab::is_trailing (const I &i)
	True if iterator i is on its node’s trailing edge.
template<class I>
auto	stlab::find_parent (I i) -> I
	Returns the trailing-edge iterator of the parent of the subtree containing i.
template<class I>
auto	stlab::has_children (const I &i) -> bool
template<class I>
auto	stlab::find_edge (I x, forest_edge edge) -> I
	Advances x forward until x.edge() == edge (or returns last such position).
template<class I>
auto	stlab::find_edge_reverse (I x, forest_edge edge) -> I
	Advances x backward until x.edge() == edge.
template<class T>
auto	stlab::operator== (const forest< T > &x, const forest< T > &y) -> bool
template<class T>
auto	stlab::operator!= (const forest< T > &x, const forest< T > &y) -> bool
template<class I>
auto	stlab::child_begin (const I &x) -> child_iterator< I >
	First child iterator for the node referenced by fullorder iterator x (may equal child_end).
template<class I>
auto	stlab::child_end (const I &x) -> child_iterator< I >
	One-past-last child iterator for the node referenced by x (half-open child sequence).
template<class I>
auto	stlab::child_range (const I &x)
	forest_range of child_iterator over the immediate children of the node at x.
template<class R, typename P>
auto	stlab::filter_fullorder_range (R &x, P p)
	Range of filter_fullorder_iterator over x using predicate p.
template<class R, typename P>
auto	stlab::filter_fullorder_range (const R &x, P p)
	const overload: filters over const_iterators.
template<class R>
auto	stlab::reverse_fullorder_range (R &x)
	Reverses the fullorder traversal of x (see reverse_fullorder_iterator).
template<class R>
auto	stlab::reverse_fullorder_range (const R &x)
	const overload.
template<class R>
auto	stlab::depth_range (R &x)
	Fullorder walk with depth tracking over x (depth_fullorder_iterator).
template<class R>
auto	stlab::depth_range (const R &x)
	const overload.
template<class R>
auto	stlab::postorder_range (R &x)
	Postorder (trailing-edge) walk over x.
template<class R>
auto	stlab::postorder_range (const R &x)
	const overload.
template<class R>
auto	stlab::preorder_range (R &x)
template<class R>
auto	stlab::preorder_range (const R &x)
	const overload.

Variables
constexpr auto	stlab::forest_trailing_edge
constexpr auto	stlab::forest_leading_edge

Detailed Description

Forest (tree-of-sequences) iterators, ranges, and algorithms.

Models an ordered forest: a rooted tree where each node’s children form a sequence. The primary abstraction is fullorder iteration—each node is visited twice, on its leading and trailing edge (see forest_edge). Preorder, postorder, reverse, depth, and filtered walks are built from that representation.

The main container is forest<T>. Child iterators adapt a fullorder iterator to walk only the immediate children of a node; child_adaptor exposes child sequences with sequence-like push_front / push_back / pop_* on a forest and parent iterator.

Background: Tree traversal (Wikipedia).