IterExplorer_test Class Reference

Description

Test:

use a simple source iterator yielding numbers to build various functional evaluation pipelines, based on the IterExplorer template.

• the adapter to wrap the source, which can either be a state core, or can be a Lumiera Forward Iterator
• the defining use case for IterExplorer is to build a pipeline for depth-first exploration of a (functional) tree structure. This "tree" is created by invoking a "expand functor", which can be defined in various ways.
• the usual building blocks for functional evaluation pipelines, that is filtering and transforming of the elements yielded by the wrapped source iterator.
• building complex pipelines by combining the aforementioned building blocks
• using an opaque source, hidden behind the IterSource interface, and an extension (sub interface) to allow for "tree exploration" without any knowledge regarding the concrete implementation of the data source.

Explanation

These tests build a evaluation pipeline by wrapping some kind of data source and then layering some evaluation stages on top. There are two motivations why one might want to build such a filter pipeline:

• on demand processing ("pull principle")
• separation of source computation and "evaluation mechanics" when building complex search and backtracking algorithms.

This usage style is inspired from the Monad design pattern. In our case here, the Iterator pipeline would be the monad, and can be augmented and reshaped by attaching further processing steps. How those processing steps are to be applied remains an internal detail, defined by the processing pipeline. »Monads« are heavily used in functional programming, actually they originate from Category Theory. Basically, Monad is a pattern where we combine several computation steps in a specific way; but instead of intermingling the individual computation steps and their combination, the goal is to isolate and separate the mechanics of combination, so we can focus on the actual computation steps: The mechanics of combination are embedded into the Monad type, which acts as a kind of container, holding some entities to be processed. The actual processing steps are then attached to the monad as "function object" parameters. It is up to the monad to decide if, and when those processing steps are applied to the embedded values and how to combine the results into a new monad.

See also

IterExplorer

IterAdapter

Definition at line 262 of file iter-explorer-test.cpp.

Classes
struct	MagicTestRubbish
	demo of a custom processing layer interacting directly with the iteration mechanism. More...

Private Member Functions
void	demonstrate_LayeredEvaluation ()
virtual void	run (Arg)
void	verify_aggregatingGroupItration ()
void	verify_asIterSource ()
void	verify_combinedExpandTransform ()
void	verify_customProcessingLayer ()
void	verify_dedup ()
void	verify_depthFirstExploration ()
void	verify_effuse ()
void	verify_elementGroupingOperation ()
void	verify_expand_rootCurrent ()
void	verify_expandOperation ()
void	verify_FilterChanges ()
void	verify_FilterIterator ()
void	verify_IterSource ()
void	verify_reduceVal ()
void	verify_scheduledExpansion ()
void	verify_transformOperation ()
template<class EXP >
void	verify_treeExpandingIterator (EXP ii)
void	verify_untilStopTrigger ()
void	verify_wrappedIterator ()
void	verify_wrappedState ()

Member Function Documentation

verify_wrappedState()

void verify_wrappedState ( )

inlineprivate

Test:

without using any extra functionality, IterExplorer just wraps an iterable state.

Definition at line 300 of file iter-explorer-test.cpp.

References lib::explore().

Here is the call graph for this function:

verify_wrappedIterator()

void verify_wrappedIterator ( )

inlineprivate

Test:

IterExplorer is able to wrap any Lumiera Forward Iterator

Definition at line 326 of file iter-explorer-test.cpp.

verify_expandOperation()

void verify_expandOperation ( )

inlineprivate

Test:

use a preconfigured "expand" functor to recurse into children.

The expand() builder function predefines a way how to expand the current head element of the iteration. However, expansion does not happen automatically, rather, it needs to be invoked by the client, similar to increment of the iterator. When expanding, the current head element is consumed and fed into the expand functor; the result of this functor invocation is injected instead into the result sequence, and consequently this result needs to be again an iterable with compatible value type. Conceptually, the evaluation forks into the children of the expanded element, before continuing with the successor of the expansion point. Obviously, expansion can be applied again on the result of the expansion, possibly leading to a tree of side evaluations.

The expansion functor may be defined in various ways and will be adapted appropriately

• it may follow the classical "monadic pattern", i.e. take individual values and return a _"child monad"_, which is then "flat mapped" (integrated) into the resulting iteration
• the resulting child collection may be returned as yet another iterator, which is then moved by the implementation into the stack of child sequences currently in evaluation
• or alternatively the resulting child collection may be returned just as a "state core", which can be adapted into a iterable state (see lib::IterStateWrapper).
• or it may even return the reference to a STL collection existing elsewhere, which will then be iterated to yield the child elements
• and, quite distinct to the aforementioned "monadic" usage, the expansion functor may alternatively be written in a way as to collaborate with the "state core" used when building the IterExplorer. In this case, the functor typically takes a reference to this underlying state core or iterator. The purpose for this definition variant is to allow exploring a tree-like evaluation, without the need to disclose anything about the backing implementation; the expansion functor just happens to know the implementation type of the "state core" and manipulate it through its API to create a "derived core" representing a child evaluation state.
• and finally, there is limited support for generic lambdas. In this case, the implementation will try to instantiate the passed lambda by using the concrete source iterator type as argument.

Note

expansion functor may use side-effects and indeed return something entirely different than the original sequence, as long as it is iterable and yields compatible values.

Definition at line 391 of file iter-explorer-test.cpp.

References lib::explore().

Here is the call graph for this function:

verify_expand_rootCurrent()

void verify_expand_rootCurrent ( )

inlineprivate

Test:

special feature of the Expander to lock into current child sequence.

This feature was added to support a specific use-case in the IterChainSearch component. After expanding several levels deep into a tree, it allows to turn the current child sequence into a new root sequence and discard the whole rest of the tree, including the original root sequence. It is implemented by moving the current child sequence down into the root sequence. We demonstrate this behaviour with the simple standard setup from verify_expandOperation()

Definition at line 504 of file iter-explorer-test.cpp.

References lib::explore(), and lib::test::anonymous_namespace{iter-explorer-test.cpp}::materialise().

Here is the call graph for this function:

verify_transformOperation()

void verify_transformOperation ( )

inlineprivate

Test:

pipe each result through a transformation function.

The transforming iterator is added as a decorator, wrapping the original iterator, TreeEplorer or state core. As you'd expect, the given functor is required to accept compatible argument types, and a generic lambda is instantiated to take a reference to the embedded iterator's value type. Several transformation steps can be chained, and the resulting entity is again a Lumiera Forward Iterator with suitable value type. The transformation function is invoked only once per step and the result produced by this invocation is placed into a holder buffer embedded within the iterator.

Note

since the implementation uses the same generic adaptor framework, the transformation functor may be defined with the same variations as described for the expand-operation above. In theory, it might collaborate with the embedded "state core" type, thereby possibly bypassing other decorators added below.

Warning

don't try this at home

Definition at line 559 of file iter-explorer-test.cpp.

References lib::explore().

Here is the call graph for this function:

verify_elementGroupingOperation()

void verify_elementGroupingOperation ( )

inlineprivate

Test:

package elements from the source pipeline into fixed-sized groups.

These groups are implemented as std::array and initialised with the values yielded consecutively from the underlying source pipeline. The main iterator then yields a reference to this data (which can be unpacked conveniently by a structured binding, or processed as a STL container. Moreover, there is a secondary interface, allowing to iterate over the values stored in this group; this is also exposed for the rest, which did not suffice to fill a full group.

Definition at line 679 of file iter-explorer-test.cpp.

References lib::explore(), and lib::test::anonymous_namespace{iter-explorer-test.cpp}::materialise().

Here is the call graph for this function:

verify_aggregatingGroupItration()

void verify_aggregatingGroupItration ( )

inlineprivate

Test:

another form of grouping, where groups are formed by a derived property thereby passing each element in the group to an aggregator function, working on an accumulator per group.

Downstream, the resulting, accumulated value is exposed for each group, while consuming all source values belonging to this group.

• in the simple form, all members of a group are "added" together
• the elaborate form allows to provide a custom aggregation function, which takes the »accumulator« as first argument by reference; the type of this argument implicitly defines what is instantiated for each group and yielded as result.

Definition at line 740 of file iter-explorer-test.cpp.

References lib::explore(), and lib::test::anonymous_namespace{iter-explorer-test.cpp}::materialise().

Here is the call graph for this function:

verify_combinedExpandTransform()

void verify_combinedExpandTransform ( )

inlineprivate

Test:

combine the recursion into children with a tail mapping operation.

Wile basically this is just the layering structure of IterExplorer put into action, you should note one specific twist: the iter_explorer::Expander::expandChildren() call is meant to be issued from ``downstream'', from the consumer side. Yet the consumer at that point might well see the items as processed by a transforming step layered on top. So what the consumer sees and thinks will be expanded need not actually be what will be processed by the expand functor. This may look like a theoretical or cosmetic issue – yet in fact it is this tiny detail which is crucial to make abstraction of the underlying data source actually work in conjunction with elaborate searching and matching algorithms. Even more so, when other operations like filtering are intermingled; in that case it might even happen that the downstream consumer does not even see the items resulting from child expansion, because they are evaluated and then filtered away by transformers and filters placed in between.

Note

as a consequence of the flexible automatic adapting of bound functors, it is possible for bound functors within different "layers" to collaborate, based on additional knowledge regarding the embedded data source internals. This test demonstrates a transform functor, which takes the source iterator as argument and invokes it.expandChildren() to manipulate the underlying evaluation. However, since the overall evaluation is demand driven, there are inherent limitations to such a setup, which bends towards fragility when leaving the realm of pure functional evaluation.

Definition at line 794 of file iter-explorer-test.cpp.

References lib::explore(), and lib::test::anonymous_namespace{iter-explorer-test.cpp}::materialise().

Here is the call graph for this function:

verify_customProcessingLayer()

void verify_customProcessingLayer ( )

inlineprivate

Test:

extension point to inject a client-defined custom processing layer This special builder function allows to install a template, which needs to wrap a source iterator and expose a state core like interface.

We demonstrate this extension mechanism here by defining a processing layer which skips each other element.

Definition at line 858 of file iter-explorer-test.cpp.

References lib::explore(), steam::mobject::session::test::anonymous_namespace{scope-query-test.cpp}::filter(), and lib::test::anonymous_namespace{iter-explorer-test.cpp}::materialise().

Here is the call graph for this function:

verify_scheduledExpansion()

void verify_scheduledExpansion ( )

inlineprivate

Test:

child expansion can be scheduled to happen on next iteration.

As such, _"child expansion"_ happens right away, thereby consuming a node and replacing it with its child sequence. Sometimes, when building search and matching algorithms, we rather just want to plan a child expansion to happen on next increment. Such is especially relevant when searching for a locally or global maximal solution, which is rather simple to implement with an additional filtering layer – and this approach requires us to deliver all partial solutions for the filter layer to act on. Obviously this functionality leads to additional state and thus is provided as optional layer in the IterExplorer builder.

Definition at line 887 of file iter-explorer-test.cpp.

References lib::explore().

Here is the call graph for this function:

verify_untilStopTrigger()

void verify_untilStopTrigger ( )

inlineprivate

Test:

control end of iteration by a stop condition predicate.

When decorating the pipeline with this adapter, iteration end depends not only on the source iterator, but also on the end condition; once the condition flips, the overall pipeline iterator is exhausted and can never be re-activated again (unless some special trickery is done by conspiring with the data source)

Definition at line 943 of file iter-explorer-test.cpp.

References lib::explore(), and lib::test::anonymous_namespace{iter-explorer-test.cpp}::materialise().

Here is the call graph for this function:

verify_FilterIterator()

void verify_FilterIterator ( )

inlineprivate

Test:

add a filtering predicate into the pipeline.

As in all the previously demonstrated cases, also the filtering is added as decorator, wrapping the source and all previously attached decoration layers. And in a similar way, various kinds of functors can be bound, and will be adapted automatically to work as a predicate to approve the elements to yield.

Definition at line 979 of file iter-explorer-test.cpp.

References lib::explore(), steam::mobject::session::test::anonymous_namespace{scope-query-test.cpp}::filter(), and lib::test::anonymous_namespace{iter-explorer-test.cpp}::materialise().

Here is the call graph for this function:

verify_FilterChanges()

void verify_FilterChanges ( )

inlineprivate

Test:

a special filter layer which can be re-configured on the fly

Definition at line 1088 of file iter-explorer-test.cpp.

References lib::explore().

Here is the call graph for this function:

verify_reduceVal()

void verify_reduceVal ( )

inlineprivate

Test:

verify terminal operation to sum or reduce all values from the pipeline.

Definition at line 1177 of file iter-explorer-test.cpp.

References lib::explore(), and stage::widget::anonymous_namespace{element-box-widget.cpp}::reduce().

Here is the call graph for this function:

verify_effuse()

void verify_effuse ( )

inlineprivate

Test:

verify terminal operation to append all results into a container.

Definition at line 1219 of file iter-explorer-test.cpp.

References lib::explore(), and steam::mobject::session::test::anonymous_namespace{scope-query-test.cpp}::filter().

Here is the call graph for this function:

verify_dedup()

void verify_dedup ( )

inlineprivate

Test:

verify to deduplicate the iterator's results into a std::set

Definition at line 1235 of file iter-explorer-test.cpp.

References lib::explore(), and lib::test::anonymous_namespace{iter-explorer-test.cpp}::materialise().

Here is the call graph for this function:

verify_asIterSource()

void verify_asIterSource ( )

inlineprivate

Test:

package the resulting Iterator as automatically managed, polymorphic opaque entity implementing the IterSource interface.

The builder operations on IterExplorer each generate a distinct, implementation defined type, which is meant to be captured by auto. However, the terminal builder function asIterSource() moves the whole compound iterator object, as generated by preceding builder steps, into a heap allocation and exposes a simplified front-end, which is only typed to the result value type. Obviously, the price to pay comes in terms of virtual function calls for iteration, delegating to the pipeline backend.

• thus a variable typed to that front-end, IterSource<VAL> is polymorphic and can be reassigned at runtime with an entirely different pipeline.
• but this structure also has the downside, that the implementation no longer resides directly within the iterator: several front-end copies share the same back-end. Note however that the behaviour of iterators copied this way is implementation defined anyway. There is never a guarantee that a clone copy evolves with state independent from its ancestor; it just happens to work this way in many simple cases. You should never use more than one copy of a given iterator at any time, and you should discard it, when done with iteration.
• actually, the returned front-end offers an extended API over plain vanilla IterSource<T>::iterator, to expose the expandChildren() operation.

Definition at line 1270 of file iter-explorer-test.cpp.

verify_IterSource()

void verify_IterSource ( )

inlineprivate

Test:

ability to wrap and handle IterSource based iteration.

Contrary to the preceding test case, here the point is to base the whole pipeline on a data source accessible through the IterSource (VTable based) interface. The notable point with this technique is the ability to use some extended sub interface of IterSource and to rely on this interface to implement some functor bound into the IterExplorer pipeline. Especially this allows to delegate the "child expansion" through such an interface and just return a compatible IterSource as result. This way, the opaque implementation gains total freedom regarding the concrete implementation of the "child series" iterator. In fact, it may even use a different implementation on each level or even on each individual call; only the result type and thus the base interface need to match.

Definition at line 1339 of file iter-explorer-test.cpp.

References lib::explore(), and lib::test::anonymous_namespace{iter-explorer-test.cpp}::materialise().

Here is the call graph for this function:

verify_depthFirstExploration()

void verify_depthFirstExploration ( )

inlineprivate

Test:

use a preconfigured exploration scheme to expand depth-first until exhaustion.

This is a simple extension where all elements are expanded automatically. In fact, the expandChildren() operation implies already an iteration step, namely to dispose of the parent element before injecting the expanded child elements. Based on that observation, when we just replace the regular iteration step by a call to expandChildren(), we'll encounter first the parent element and then delve depth-first into exploring the children.

Note

such continued expansion leads to infinite iteration, unless the expand functor contains some kind of termination condition.

• in the first example, we spawn a child sequence with starting point one below the current element's value. And since such a sequence is defined to terminate when reaching zero, we'll end up spawning an empty sequence at leaf nodes, which prompts the evaluation mechanism to pop back to the last preceding expansion.
• the second example demonstrates how to use value tuples for the intermediary computation. In this case, we only generate a linear chain of children, thereby summing up all encountered values. Termination is checked explicitly in this case, returning an empty child iterator.

Definition at line 1442 of file iter-explorer-test.cpp.

References lib::explore(), and lib::test::anonymous_namespace{iter-explorer-test.cpp}::materialise().

Here is the call graph for this function:

demonstrate_LayeredEvaluation()

void demonstrate_LayeredEvaluation ( )

inlineprivate

Test:

Demonstration how to build complex algorithms by layered tree expanding iteration

Remarks

this is the actual use case which inspired the design of IterExplorer: Search with backtracking over an opaque (abstracted), tree-shaped search space.

• the first point to note is that the search algorithm knows nothing about its data source, beyond its ability to delve down (expand) into child nodes
• in fact our data source for this test here is "infinite", since it is an very large random root sequence, where each individual number can be expanded into a limited random sub sequence, down to arbitrary depth. We just assume that the search has good chances to find its target sequence eventually and thus only ever visits a small fraction of the endless search space.
• on top of this (opaque) tree navigation we build a secondary search pipeline based on a state tuple, which holds onto the underlying data source
• the actual decision logic to guide the search lives within the filter predicate to pull for the first acceptable solution, i.e. a path down from root where each node matches the next element from the search string. It is from here that the expandChildren() function is actually triggered, whenever we've found a valid match on the current level. The (random) data source was chosen such as to make it very likely to find a match eventually, but also to produce some partial matches followed by backtracking
• note how the "downstream" processing accesses the depth() information exposed on the opaque data source to react on navigation into nested scopes: here, we use this feature to create a protocol of the search to indicate the actual "winning path"

Definition at line 1499 of file iter-explorer-test.cpp.

References lib::explore().

Here is the call graph for this function:

Inheritance diagram for IterExplorer_test:

Collaboration diagram for IterExplorer_test:

---

The documentation for this class was generated from the following file:

• iter-explorer-test.cpp