Lumiera  0.pre.03
»edit your freedom«
iter-chain-search.hpp File Reference

Go to the source code of this file.

Description

Evaluation mechanism to apply a sequence of conditions onto a linear search.

This search algorithm is implemented on top of a tree expanding (monadic) filter pipeline, to allow for backtracking. The intention is not just to combine the individual conditions, but rather to apply them one by one. After finding a match for the first condition, we'll search for the next condition starting at the position of the previous match. In the most general case, this immediate progression down the search chain might be too greedy; it could be that we don't find a match for the next condition, but if we backtrack and first search further on the previous condition, continuing with the search from that further position might then lead to a match. Basically we have to try all combinations of all possible local matches, to find a solution to satisfy the whole chain of conditions.

Design

The IterChainSearch component is built as a processing pipeline, based on the Iterator-Explorer framework. This yields several benefits, but imposes some drawbacks. Without much effort, we get an extremely flexible and configurable solution, with acceptable / moderate performance. The result automatically adapts to a huge selection of data sources; it is possible (and is even intended) to attach it on top of an existing on-demand data processing pipeline. The "source" can itself be a "state core" and we may install suitable filter predicates to possibly collaborate with the internals of such a state core. Yet we may also confine ourselves to pure functions and value processing.

The obvious downside of such an approach is its complexity in terms of code to understand. The collaboration between several layers in a filter pipeline can be intricate, leading to chains of layered similar functions calling each other. Most of these abstractions and decorations will be resolved by the compiler and optimiser, typically leading to long compilation times and rather large size of the generated code (which in debugging mode with full type information can even become excessively large).

Some caveats

  • the resulting pipeline is copyable, and it is typically moved out from a builder function into the target location. So beware of lambda captures by reference. When you capture anything within the pipeline itself, like some this pointer, you'll end up with a dangling reference for sure. However, it is just fine to capture extended facilities within the scope enclosing the pipeline, as long as this scope remains intact during the whole usage time of the pipeline.
  • the resulting entity, an instantiation of the IterChainSearch template, is not a generic IterExplorer (builder). Be careful when using any builder functions still accessible. The only functions meant to be used in builder style are the IterChainSearch::search() variations.
  • if you copy, the embedded state is copied alongside, but not any further external state referred by it.
See also
IterChainSearch_test
IterCursor_test
iter-explorer.hpp
usage example

Definition in file iter-chain-search.hpp.

#include "lib/error.hpp"
#include "lib/iter-explorer.hpp"
#include "lib/meta/util.hpp"
#include <utility>
#include <vector>
#include <string>

Classes

struct  _IterChainSetup< SRC >
 
class  IterChainSearch< SRC >
 Iterator based linear search mechanism, with the ability to perform consecutive search with backtracking. More...
 

Functions

template<class SRC >
auto buildChainExplorer (SRC &&dataSource)
 define the chained-search mechanism: invoking filter.expandChildren() adds a new layer with the copy of current iteration (search) state, which is a mutableFilter and can thus be augmented. More...
 
template<class SRC >
auto buildSearchFilter (SRC &&dataSource)
 
template<class SRC >
auto chainSearch (SRC &&srcData)
 setup a chain search configuration by suitably wrapping the given container. More...
 

Namespaces

 lib
 Implementation namespace for support and library code.
 

Class Documentation

◆ lib::iter::anonymous_namespace{iter-chain-search.hpp}::_IterChainSetup

struct lib::iter::anonymous_namespace{iter-chain-search.hpp}::_IterChainSetup
Class Members
typedef decltype(buildSearchFilter(declval
< SRC >())
Filter
typedef decltype(buildChainExplorer(declval
< SRC >()))
Pipeline
typedef function< void(Filter &)> StepFunctor each step in the chain is a functor to reconfigure the underlying filter
+ Collaboration diagram for _IterChainSetup< SRC >:

Function Documentation

◆ chainSearch()

auto lib::iter::chainSearch ( SRC &&  srcData)
inline

setup a chain search configuration by suitably wrapping the given container.

Returns
an IterChainSearch instantiation, which is an Iterator to yield all the source elements, but can be outfitted with a sequence of filter conditions, to be applied to the underlying source one by one.
Parameters
srcDataeither a »Lumiera Forward Iterator«, a reference to a STL container, or a »State Core« object.
Warning
if you capture the result of this call by an auto variable, be sure to understand that invoking any further builder operation on IterExplorer will invalidate that variable (by moving it into the augmented iterator returned from such builder call).

Definition at line 319 of file iter-chain-search.hpp.

References lib::iter::chainSearch().

Referenced by IterChainSearch_test::chainedIteration(), lib::iter::chainSearch(), and IterChainSearch_test::simpleSearch().

+ Here is the call graph for this function:
+ Here is the caller graph for this function: