forest

Detailed Description

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

Use this module for hierarchical data and algorithms that need fullorder iterators (leading/trailing edges), child views, and range helpers (preorder_range, postorder_range, depth_range, filter_fullorder_range, etc.). Higher-level shape algorithms live in forest_algorithms.hpp (stlab::forests).

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...
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...
class	stlab::forest< T >
	Hierarchical, node-based container: a forest (ordered sequence of trees) with fullorder iterators and child views. 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.
auto	stlab::forest< T >::size () const -> size_type
	Returns the number of nodes; \(O(1)\) when size_valid() is true, otherwise a linear walk.
auto	stlab::forest< T >::erase (const iterator &first, const iterator &last) -> iterator
	Erases every node in the half-open fullorder range [first, last).
auto	stlab::forest< T >::erase (const iterator &position) -> iterator
	Erases the node at position.
auto	stlab::forest< T >::splice (const iterator &position, forest< T > &x) -> iterator
auto	stlab::forest< T >::splice (const iterator &position, forest< T > &x, iterator i) -> iterator
auto	stlab::forest< T >::insert (iterator position, const const_child_iterator &first, const const_child_iterator &last) -> iterator
auto	stlab::forest< T >::splice (const iterator &position, forest< T > &x, const child_iterator &first, const child_iterator &last, size_type count) -> iterator
auto	stlab::forest< T >::splice (const iterator &position, forest< T > &x, child_iterator first, child_iterator last) -> iterator
auto	stlab::forest< T >::insert_parent (child_iterator front, child_iterator back, const T &x) -> iterator
void	stlab::forest< T >::reverse (child_iterator first, child_iterator last)

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

Function Documentation

erase() [1/2]

template<class T>

auto stlab::forest< T >::erase	(	const iterator &	first,
		const iterator &	last ) -> iterator

Erases every node in the half-open fullorder range [first, last).

Range erase removes each node in [first, last) in fullorder sequence.

erase() [2/2]

template<class T>

auto stlab::forest< T >::erase

(

const iterator &

position

)

-> iterator

Erases the node at position.

Removes position from the tree; former children become siblings immediately after that position (they are not recursively deleted).

find_parent()

template<class I>

auto stlab::find_parent

(

I

i

)

-> I

Returns the trailing-edge iterator of the parent of the subtree containing i.

Walks forward from i until a trailing edge is found; cost is proportional to that walk (often related to depth and subtree shape). In the worst case over arbitrary forests this is linear in the size of the subtree being skipped.

Note

Time complexity is linear in the number of fullorder steps along the search path.

size()

template<class T>

auto stlab::forest< T >::size

(

)

const -> size_type

Returns the number of nodes; \(O(1)\) when size_valid() is true, otherwise a linear walk.

Most operations keep the cached count consistent. Some splice overloads (e.g. moving a range of child nodes when the moved count is unknown) can invalidate size_valid() on the source and/or destination until the next full recount.

Note

Some splices can invalidate cached sizes on source and destination forests.