iter-explorer.hpp File Reference

Go to the source code of this file.

Description

Building tree expanding and backtracking evaluations within hierarchical scopes.

Based on the Lumiera Forward Iterator concept and using the basic IterAdapter templates, these components allow to implement typical evaluation strategies, like conditional expanding or depth-first exploration of a hierarchical structure. Since the access to this structure is abstracted through the underlying iterator, what we effectively get is a functional datastructure. The implementation is based on the idea of a "state core", which is wrapped right into the iterator itself (value semantics) – similar to the IterStateWrapper, which is one of the basic helper templates provided by iter-adapter.hpp.

Remarks

historically, this template, as well as the initial IterExplorer (draft from 2012) can be seen as steps towards a framework of building blocks for tree expanding and backtracking algorithms — driven by a persistent need for this computation pattern, which lies in the nature of Lumiera's design: matching flexible configuration against a likewise hierarchical and rules based model.

Background: Iterators as Monad

The fundamental idea behind the implementation technique used here is the Monad pattern known from functional programming. A Monad is a container holding some arbitrarily typed base value; the monad can be seen as „amplifying“ and enhancing the contained base value by attaching additional properties or capabilities This is a rather detached concept with a wide variety of applications (things like IO state, parsers, combinators, calculations with exception handling but also simple data structures like lists or trees). The key point with any monad is the ability to bind a function into the monad; this function will work on the contained base values and produce a modified new monad instance. In the simple case of a list, "binding" a function basically means to map the function onto the elements in the list. (strictly speaking, it means the flatMap operation)

A Pipeline builder

Based on such concepts, structures and evaluation patterns, the IterExplorer serves the purpose to provide building blocks to assemble a processing pipeline, where processing will happen on demand, while iterating. IterExplorer itself is both a Lumiera Forward Iterator based on some wrapped data source, and at the same time it is a builder to chain up processing steps to work on the data pulled from that source. These processing steps are attached as decorators wrapping the source, in the order the corresponding builder functions were invoked.

• the expand operation installs a function to consume one element and replace it by the sequence of elements (``children'') produced by that »expansion functor«. But this expansion does not happen automatically and on each element, rather it is triggered by issuing a dedicated expandChildren() call on the processing pipeline. Thus, binding the expansion functor has augmented the data source with the ability to explore some part in more detail when required.
• the transform operation installs a function to be mapped onto each element retrieved from the underlying source
• in a similar vein, the filter operation binds a predicate to decide about using or discarding data
• in concert, expand- and transform operation allow to build hierarchy evaluation algorithms without exposing any knowledge regarding the concrete hierarchy used and explored as data source.
• further special convenience adaptors and terminal functions are provided.

In itself, the IterExplorer is an iterator with implementation defined type (all operations being inlined). But it is possible to package this structure behind a conventional iteration interface with virtual functions. By invoking the terminal builder function IterExplorer::asIterSource(), the iterator compound type, as created thus far, will be moved into a heap allocation, returning a front-end based on IterSource. In addition, the actually returned type, IterExplorerSource, exposes the expandChildren() operation as discussed above.

Rationale

This design leads to a complete separation of the transforming operation from the mechanics how to apply that operation and combine the results. More specifically, we rely on an iterator to represent an abstracted source of data and we expose the combined and transformed results again as such an abstracted data sequence. Thereby, a trend towards separation of concerns is introduced; the data source remains opaque, while the manipulation to apply can be selected at runtime or written inline as Lambda. The iterator itself is a self-contained value and represents partial evaluation state without requiring a container for intermediary results.

some implementation details

The builder operations assemble a heavily nested type, each builder call thereby adding yet another layer of subclassing. The templates involved into this build process are specialised, as driven by the actual functor type bound into each builder step; this functor is investigated and possibly adapted, according to its input type, while its output type determines the value type used in the pipeline "downstream". A functor with an input (argument) type incompatible or unsuitable to the existing pipeline will produce that endless sway of template error messages we all love so much. When this happens, please look at the static assertion error message typically to be found below the first template-instantiation stack sequence of messages.

Warning

all builder operations work by moving the existing pipeline built thus far into the parent of the newly built subclass object. The previously existing pipeline is defunct after that move; if you captured it into a variable, be sure to capture the result of the new builder operation as well and don't use the old variable anymore. Moreover, it should be ensured that any "state core" used within IterExplorer has an efficient move ctor; including RVO, the compiler is typically able to optimise such move calls away altogether.

See also

IterExplorer_test

iter-adapter.hpp

itertools.hpp

IterSource (completely opaque iterator)

Definition in file iter-explorer.hpp.

#include "lib/error.hpp"
#include "lib/uninitialised-storage.hpp"
#include "lib/meta/duck-detector.hpp"
#include "lib/meta/function.hpp"
#include "lib/meta/trait.hpp"
#include "lib/wrapper.hpp"
#include "lib/iter-adapter.hpp"
#include "lib/iter-source.hpp"
#include "lib/iter-stack.hpp"
#include "lib/util.hpp"
#include <functional>
#include <optional>
#include <utility>

Classes
struct	_DecoratorTraits< SRC, SEL >
	decide how to adapt and embed the source sequence into the resulting IterExplorer More...
struct	_DecoratorTraits< ISO &, enable_if< is_base_of< IterSource< typename ISO::value_type >, ISO > > >
struct	_DecoratorTraits< ISO *&, enable_if< is_base_of< IterSource< typename ISO::value_type >, ISO > > >
struct	_DecoratorTraits< ISO *, enable_if< is_base_of< IterSource< typename ISO::value_type >, ISO > > >
struct	_DecoratorTraits< SRC, enable_if< is_StateCore< SRC > > >
struct	_DecoratorTraits< SRC, enable_if< shall_use_Lumiera_Iter< SRC > > >
struct	_DecoratorTraits< SRC, enable_if< shall_wrap_STL_Iter< SRC > > >
struct	_ExpanderTraits< SRC, RES >
	helper to derive a suitable common type when expanding children More...
struct	_FunTraits< FUN, SRC >
struct	_ReduceTraits< SRC, FUN >
struct	_FunTraits< FUN, SRC >::ArgAdapter< ARG, SEL >
	adapt to a functor, which accesses the source iterator or embedded "state core" More...
struct	_FunTraits< FUN, SRC >::ArgAdapter< IT, enable_if< __and_< is_base_of< IterSource< typename IT::value_type >, typename IT::Source >, is_base_of< IterSource< typename IT::value_type >, remove_reference_t< Arg > > > > >
	adapt to a functor collaborating with an IterSource based iterator pipeline More...
struct	_FunTraits< FUN, SRC >::ArgAdapter< IT, enable_if< __and_< is_convertible< typename IT::reference, Arg >, __not_< is_convertible< IT, Arg > > > > >
	adapt to a functor, which accepts the value type of the source sequence ("monadic" usage pattern) More...
class	AutoExpander< SRC >
struct	BaseAdapter< SRC >
struct	Grouping< SRC, RES, grp >::Buffer
class	ChildExpandableSource< VAL >
	Interface to indicate and expose the ability for child expansion. More...
struct	CoreYield< COR >
	the value type yielded by a »state core« More...
class	Expander< SRC, RES >
class	Filter< SRC >
struct	_FunTraits< FUN, SRC >::FunDetector< F, SEL >
	handle all regular "function-like" entities More...
struct	_FunTraits< FUN, SRC >::FunDetector< F, disable_if< _Fun< F > > >
	handle a generic lambda, accepting a reference to the SRC iterator More...
class	GroupAggregator< SRC, AGG, GRP >
class	Grouping< SRC, RES, grp >
class	IterExplorer< SRC >
	Adapter to build a demand-driven tree expanding and exploring computation based on a custom opaque state core. More...
struct	IterExploreSource< VAL >
	Iterator front-end to manage and operate a IterExplorer pipeline opaquely. More...
class	IterSourceIter< ISO >
	Adapt an IterSource to make it iterable. More...
class	MutableFilter< SRC >
class	PackagedIterExplorerSource< SRC >
class	ScheduledExpander< SRC >
struct	shall_use_Lumiera_Iter< SRC >
struct	shall_wrap_STL_Iter< SRC >
struct	StlRange< CON >
	Adapt STL compliant container. More...
struct	StlRange< CON & >
struct	StlRange< const CON >
class	StopTrigger< SRC >
class	Transformer< SRC, RES >
class	vector< T >
	STL class.

Typedefs
template<class CON >
using	const_iterator = typename meta::Strip< CON >::TypeReferred::const_iterator
template<class CON >
using	iterator = typename meta::Strip< CON >::TypeReferred::iterator

Functions
template<class IT >
auto	explore (IT &&srcSeq)
	start building a IterExplorer by suitably wrapping the given iterable source. More...
template<typename FUN , typename SRC >
void	static_assert_isPredicate ()

Variables
constexpr auto	ACCEPT_ALL = [](auto){return true;}
constexpr auto	IDENTITY = [](auto it){return *it;}

Namespaces
	lib
	Implementation namespace for support and library code.

---

Class Documentation

lib::anonymous_namespace{iter-explorer.hpp}::_DecoratorTraits

struct lib::anonymous_namespace{iter-explorer.hpp}::_DecoratorTraits

Inheritance diagram for _DecoratorTraits< SRC, SEL >:

Collaboration diagram for _DecoratorTraits< SRC, SEL >:

lib::anonymous_namespace{iter-explorer.hpp}::_DecoratorTraits< ISO *, enable_if< is_base_of< IterSource< typename ISO::value_type >, ISO > > >

struct lib::anonymous_namespace{iter-explorer.hpp}::_DecoratorTraits< ISO *, enable_if< is_base_of< IterSource< typename ISO::value_type >, ISO > > >

Class Members
typedef IterSourceIter< ISO >	SrcIter
typedef typename value_type	SrcVal

Collaboration diagram for _DecoratorTraits< ISO *, enable_if< is_base_of< IterSource< typename ISO::value_type >, ISO > > >:

lib::anonymous_namespace{iter-explorer.hpp}::_DecoratorTraits< SRC, enable_if< is_StateCore< SRC > > >

struct lib::anonymous_namespace{iter-explorer.hpp}::_DecoratorTraits< SRC, enable_if< is_StateCore< SRC > > >

Class Members
typedef typename Strip< SRC >::Type	SrcRaw
typedef typename CoreYield < SrcRaw >::value_type	SrcVal
typedef IterableDecorator < SrcVal, CheckedCore< SrcRaw > >	SrcIter

Collaboration diagram for _DecoratorTraits< SRC, enable_if< is_StateCore< SRC > > >:

lib::anonymous_namespace{iter-explorer.hpp}::_DecoratorTraits< SRC, enable_if< shall_use_Lumiera_Iter< SRC > > >

struct lib::anonymous_namespace{iter-explorer.hpp}::_DecoratorTraits< SRC, enable_if< shall_use_Lumiera_Iter< SRC > > >

Class Members
typedef remove_reference_t< SRC >	SrcIter
typedef typename value_type	SrcVal

Collaboration diagram for _DecoratorTraits< SRC, enable_if< shall_use_Lumiera_Iter< SRC > > >:

lib::anonymous_namespace{iter-explorer.hpp}::_DecoratorTraits< SRC, enable_if< shall_wrap_STL_Iter< SRC > > >

struct lib::anonymous_namespace{iter-explorer.hpp}::_DecoratorTraits< SRC, enable_if< shall_wrap_STL_Iter< SRC > > >

Class Members
typedef StlRange< SRC >	SrcIter
typedef typename value_type	SrcVal

Collaboration diagram for _DecoratorTraits< SRC, enable_if< shall_wrap_STL_Iter< SRC > > >:

lib::anonymous_namespace{iter-explorer.hpp}::CoreYield

struct lib::anonymous_namespace{iter-explorer.hpp}::CoreYield

Class Members
typedef remove_reference_t < decltype(declval< COR >()	Res
typedef typename RefTraits < Res >::Value	value_type
typedef typename RefTraits < Res >::Reference	reference
typedef typename RefTraits < Res >::Pointer	pointer

Collaboration diagram for CoreYield< COR >:

lib::iter_explorer::_FunTraits::FunDetector

struct lib::iter_explorer::_FunTraits::FunDetector

Class Members
typedef typename _Fun< F >::Sig	Sig

Collaboration diagram for _FunTraits< FUN, SRC >::FunDetector< F, SEL >: