forest_algorithms

Detailed Description

Higher-level forest algorithms (stlab::forests).

Declarations live in this header; see the @file description for an overview of equal_shape, transcribe, flatten, and unflatten.

Classes
struct	stlab::forests::transcribe_iterator< Container >
	Output iterator that inserts projected values into a forest (or similar container). More...

Functions
template<class Forest1, class Forest2>
auto	stlab::forests::equal_shape (const Forest1 &x, const Forest2 &y) -> bool
	Returns true if x and y have the same full-order edge sequence (values may differ).
template<class Container>
auto	stlab::forests::transcriber (Container &c)
	Returns a transcribe_iterator starting at c.begin() for building c from a walk.
template<class I, class O, class P, class UP>
auto	stlab::forests::transcribe (I first, const I &last, O out, P proj, UP pred)
	Walks [first, last); for positions where pred is true, assigns proj(*first) to out, otherwise calls out.trailing().
template<class R, class O, class P, class UP>
auto	stlab::forests::transcribe (const R &range, O out, P proj, UP pred)
	Range overload of transcribe with explicit leading/trailing predicate pred.
template<class I, class O, class P>
auto	stlab::forests::transcribe (const I &first, const I &last, O out, P proj)
	Walks [first, last) using is_leading as the predicate (default transcribe behavior).
template<class R, class O, class P>
auto	stlab::forests::transcribe (const R &range, O out, P proj)
	Range overload of transcribe with is_leading as the predicate.
template<class I, class O>
auto	stlab::forests::flatten (I first, const I &last, O out)
	Writes each leading node's value to out; writes std::nullopt at trailing edges.
template<class I, class F>
auto	stlab::forests::unflatten (I first, I last, F &f)
	Rebuilds forest f from a flattened std::optional sequence (inverse of flatten).

Function Documentation

equal_shape()

template<class Forest1, class Forest2>

auto stlab::forests::equal_shape	(	const Forest1 &	x,
		const Forest2 &	y ) -> bool

Returns true if x and y have the same full-order edge sequence (values may differ).

("Congruent" would be a nice name here, but in geometry that also implies reflection.) If both forests have a valid cached size() and they differ, returns false immediately.

flatten()

template<class I, class O>

auto stlab::forests::flatten	(	I	first,
		const I &	last,
		O	out )

Writes each leading node's value to out; writes std::nullopt at trailing edges.

The result is a lossless encoding of forest shape plus leading values (see unflatten).