Combining different iterators based on a runtime decision

Question

I have an algorithm that given an arbitrary number of vectors runs a specific algorithm and returns the result.

The vectors can be ether read from an input file with lines representing vectors in csv format or the user can specify positive integers (greater than 2) n,k,m and the program will generate n vectors where each of the k coordinates is randomly distributed in the range [0,m-1].

A user can choose between several functions that can be applied to each vector e.g multiply each by a scalar, apply modulus to each element, zero the N-th coordinate etc.

The solution I was thinking about is using iterator much like the standard algorithms (e.g std::copy)

template<class InputIt>
int my_transform(InputIt begin, InputIt end){
    // ... stuff from begin to end
    return result;
}

While it works when I use std::istream_iterator as a parameter and I'm quite confident that I'll work with boost::function_input_iterator for generated values and with boost::transform_iterator to apply the required function I'm not quite sure how to make those combinations at runtime according to user input.

I can aggregate all the user input prior to execution of my_transform but then how would I apply it on the resulting iterator because it can be anything from std::istream_iterator to a boost::transform_iterator or a boost::function_input_iterator?

P.S:

As mentioned in the tags I'm working on VS13 so solutions should be compatible with it.
Iterating more than once is not an option as these files can get quite big.

score 1 · Accepted Answer · edited May 23 '17 at 12:31

I think you want Boost Range's

join
and any_range (based on any_terator)

Alternatively perhaps you can redesign the algorithm to work in "streaming" mode by default and write to an output iterator on the fly as well.

Update A demo program

Here's a sample that demonstrates how to join any combination of input range (of different types) and then apply any sequence of transformation functions on it's combined elements.

The main program looks like:

int main(int argc, char const** argv) {
    using InIt = std::istream_iterator<int>;

    if (argc!=4) return 255;
    std::ifstream f1(argv[1]), f2(argv[2]), f3(argv[3]);

    auto r1 = boost::make_iterator_range(InIt(f1), {}),
         r2 = boost::make_iterator_range(InIt(f2), {}),
         r3 = boost::make_iterator_range(InIt(f3), {});    
    auto r4 = boost::make_iterator_range(boost::make_function_input_iterator(r10gen_, 0), { r10gen_, 10 });

    srand(time(0));
    for (int i : random_compose_input(r1,r2,r3,r4) 
               | transformed(random_transform(
                    [](int i) { return i/3; },
                    [](int i) { return -4*i; },
                    [](int i) { return 100+i; },
                    [](int i) { return sqrt(abs(i)); }
                 ))
        )
    { 
        std::cout << i << " ";
    }
}

Where the functions random_compose_input and random_transform do runtime selections of both the input ranges as well as transformation functions.

random_compose_input returns an any_range that wraps the deduced type of joined range for the selected combination:

/////////////////////////////////////////////
// runtime composition of any input ranges
using AnyR = boost::any_range<int const, boost::single_pass_traversal_tag, int>;

template <typename R1, typename R2, typename R3, typename R4>
    AnyR random_compose_input(R1 const& r1, R2 const& r2, R3 const& r3, R4 const& r4) 
{
    int select = rand()%16;
    std::cout << "selected inputs " << std::showbase << std::hex << select << std::dec << "\n";
    switch(select) {
        case  0:
            static int const* dummy = nullptr;
            return boost::make_iterator_range(dummy, dummy);
        case  1: return multi_join(r1            );
        case  2: return multi_join(    r2        );
        case  3: return multi_join(r1, r2        );
        case  4: return multi_join(        r3    );
        case  5: return multi_join(r1,     r3    );
        case  6: return multi_join(    r2, r3    );
        case  7: return multi_join(r1, r2, r3    );
        case  8: return multi_join(            r4);
        case  9: return multi_join(r1,         r4);
        case 10: return multi_join(    r2,     r4);
        case 11: return multi_join(r1, r2,     r4);
        case 12: return multi_join(        r3, r4);
        case 13: return multi_join(r1,     r3, r4);
        case 14: return multi_join(    r2, r3, r4);
        case 15: return multi_join(r1, r2, r3, r4);
    }
    throw "oops";
}

Note multi_join is where join comes in. See the full program listing for the (straight-forward) implementation of this using a variadic function template.

And the random_transform composition happens to boost::function<int(int)>:

/////////////////////////////////////////////
// random composition of transformation
using Xfrm = boost::function<int(int)>;

template <typename F1, typename F2, typename F3, typename F4>
    Xfrm random_transform(F1 const& f1, F2 const& f2, F3 const& f3, F4 const& f4) 
{
    int select = rand()%16;
    std::cout << "selected transforms " << std::showbase << std::hex << select << std::dec << "\n";
    switch(select) {
        case  0: return [=](int i){ return   (  (  (  (i)))); };
        case  1: return [=](int i){ return   (  (  (f1(i)))); };
        case  2: return [=](int i){ return   (  (f2(  (i)))); };
        case  3: return [=](int i){ return   (  (f2(f1(i)))); };
        case  4: return [=](int i){ return   (f3(  (  (i)))); };
        case  5: return [=](int i){ return   (f3(  (f1(i)))); };
        case  6: return [=](int i){ return   (f3(f2(  (i)))); };
        case  7: return [=](int i){ return   (f3(f2(f1(i)))); };
        case  8: return [=](int i){ return f4(  (  (  (i)))); };
        case  9: return [=](int i){ return f4(  (  (f1(i)))); };
        case 10: return [=](int i){ return f4(  (f2(  (i)))); };
        case 11: return [=](int i){ return f4(  (f2(f1(i)))); };
        case 12: return [=](int i){ return f4(f3(  (  (i)))); };
        case 13: return [=](int i){ return f4(f3(  (f1(i)))); };
        case 14: return [=](int i){ return f4(f3(f2(  (i)))); };
        case 15: return [=](int i){ return f4(f3(f2(f1(i)))); };
    }
    throw "oops";
}

For the sample I've hardcoded 4 input ranges and 4 potential transformation steps.

This leads to efficient code.
But if you prefer you could always just start with "blank" AnyR or boost::function<int(int)>:
```
 boost::function<int(int)> xfrm = [](int i){return i;};

 while (std::getline(std::cin, line))
 {
     if      (line == "+2") xfrm = [=](int i) { return xfrm(i) + 2 };
     else if (line == "-2") xfrm = [=](int i) { return xfrm(i) - 2 };
     else if (line == "*2") xfrm = [=](int i) { return xfrm(i) * 2 };
     else if (line == "/2") xfrm = [=](int i) { return xfrm(i) / 2 };
 }
```
(Note a subtle difference of behaviour vs. the composition of statically known lambdas: the lambdas have a deduced return type (e.g. double for the one doing sqrt(abs(i))), and keeps that type. Since boost::function erases this information, it implicitly coerces to int each step in the transformation sequence.)

Caveats: 2 library bugs

There are two library bugs at play here:

this bug which has a resolution in comment#2 in the tracker
another, not known-to-me bug where any_iterator cannot wrap function_input_iterator whithout adding a constructor overload:
```
function_input_iterator(base_type const& b) : base_type(b) {};
```
This is because at some point any_iterator continues working with just the base class (this should likely be fixed in the function_input_iterator library.

Full Code

It doesn't quite run on Coliru, because of the bugs mentioned just above, but here's a full program that compiles on my GCC and clang installations in c++11 mode:

Live On Coliru

#include <boost/function.hpp>
#include <boost/range.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/range/any_range.hpp>
#include <boost/range/join.hpp>
#include <boost/iterator/function_input_iterator.hpp>

using namespace boost::adaptors;

#include <iostream>
#include <fstream>
#include <vector>

/////////////////////////////////////////////
// multi_join utility
namespace detail {
    struct multi_join_dispatch {
        template <typename R1> static R1 call(R1&& r1) 
            { return std::forward<R1>(r1); }

        template <typename R1, typename... Rs> static auto call(R1&& r1, Rs&&... ranges) 
            -> decltype(boost::range::join(std::forward<R1>(r1), call(std::forward<Rs>(ranges)...)))
            { return boost::range::join(std::forward<R1>(r1), call(std::forward<Rs>(ranges)...)); }
    };
}

template <typename... Rs> auto multi_join(Rs&&... ranges) 
    -> decltype(detail::multi_join_dispatch::call(std::forward<Rs>(ranges)...))
    { return detail::multi_join_dispatch::call(std::forward<Rs>(ranges)...); }

/////////////////////////////////////////////
// generate random numbers [0..9]
struct r10gen {
    typedef int result_type;
    int operator()() const { return rand()%10; } 
} static r10gen_;

/////////////////////////////////////////////
// runtime composition of any input ranges
using AnyR = boost::any_range<int const, boost::single_pass_traversal_tag, int>;

template <typename R1, typename R2, typename R3, typename R4>
    AnyR random_compose_input(R1 const& r1, R2 const& r2, R3 const& r3, R4 const& r4) 
{
    int select = rand()%16;
    std::cout << "selected inputs " << std::showbase << std::hex << select << std::dec << "\n";
    switch(select) {
        case  0:
            static int const* dummy = nullptr;
            return boost::make_iterator_range(dummy, dummy);
        case  1: return multi_join(r1            );
        case  2: return multi_join(    r2        );
        case  3: return multi_join(r1, r2        );
        case  4: return multi_join(        r3    );
        case  5: return multi_join(r1,     r3    );
        case  6: return multi_join(    r2, r3    );
        case  7: return multi_join(r1, r2, r3    );
        case  8: return multi_join(            r4);
        case  9: return multi_join(r1,         r4);
        case 10: return multi_join(    r2,     r4);
        case 11: return multi_join(r1, r2,     r4);
        case 12: return multi_join(        r3, r4);
        case 13: return multi_join(r1,     r3, r4);
        case 14: return multi_join(    r2, r3, r4);
        case 15: return multi_join(r1, r2, r3, r4);
    }
    throw "oops";
}

/////////////////////////////////////////////
// random composition of transformation
using Xfrm = boost::function<int(int)>;

template <typename F1, typename F2, typename F3, typename F4>
    Xfrm random_transform(F1 const& f1, F2 const& f2, F3 const& f3, F4 const& f4) 
{
    int select = rand()%16;
    std::cout << "selected transforms " << std::showbase << std::hex << select << std::dec << "\n";
    switch(select) {
        case  0: return [=](int i){ return   (  (  (  (i)))); };
        case  1: return [=](int i){ return   (  (  (f1(i)))); };
        case  2: return [=](int i){ return   (  (f2(  (i)))); };
        case  3: return [=](int i){ return   (  (f2(f1(i)))); };
        case  4: return [=](int i){ return   (f3(  (  (i)))); };
        case  5: return [=](int i){ return   (f3(  (f1(i)))); };
        case  6: return [=](int i){ return   (f3(f2(  (i)))); };
        case  7: return [=](int i){ return   (f3(f2(f1(i)))); };
        case  8: return [=](int i){ return f4(  (  (  (i)))); };
        case  9: return [=](int i){ return f4(  (  (f1(i)))); };
        case 10: return [=](int i){ return f4(  (f2(  (i)))); };
        case 11: return [=](int i){ return f4(  (f2(f1(i)))); };
        case 12: return [=](int i){ return f4(f3(  (  (i)))); };
        case 13: return [=](int i){ return f4(f3(  (f1(i)))); };
        case 14: return [=](int i){ return f4(f3(f2(  (i)))); };
        case 15: return [=](int i){ return f4(f3(f2(f1(i)))); };
    }
    throw "oops";
}

int main(int argc, char const** argv) {
    using InIt = std::istream_iterator<int>;

    if (argc!=4) return 255;
    std::ifstream f1(argv[1]), f2(argv[2]), f3(argv[3]);

    auto r1 = boost::make_iterator_range(InIt(f1), {}),
         r2 = boost::make_iterator_range(InIt(f2), {}),
         r3 = boost::make_iterator_range(InIt(f3), {});

    auto fi_b = boost::make_function_input_iterator(r10gen_, 0);
    auto fi_l = boost::make_function_input_iterator(r10gen_, 10);
    auto r4 = boost::make_iterator_range(fi_b, fi_l);

    srand(time(0));
    for (int i : random_compose_input(r1,r2,r3,r4) 
               | transformed(random_transform(
                    [](int i) { return i/3; },
                    [](int i) { return -4*i; },
                    [](int i) { return 100+i; },
                    [](int i) { return sqrt(abs(i)); }
                 ))
        )
    { 
        std::cout << i << " ";
    }
}

When I run it with e.g.

watch ./test <(echo {100..110}) <(echo {200..220}) <(echo {300..330})

Typical output is

selected transforms 0x3
selected inputs 0x2
-264 -268 -268 -268 -272 -272 -272 -276 -276 -276 -280 -280 -280 -284 -284 -284 -288 -288 -288 -292 -292

Or, e.g.

selected transforms 0x1
selected inputs 0x8
0 0 2 2 0 1 2 1 1 2

Thanks for the answer! But how would I benefit from join? As it concatenates two streams and doesn't do the equivalent of function composition which is what I'm looking for (e.g for each vector v multipy v by a scalar after zero-ing the n'th coordinate where each v is a line in a file). Perhaps I'm missing something in the documentation so a small example would be very appreciated. Could I maybe just use the `any_iterator` that's mentioned in `any_range`'s page? — Darius, Jan 02 '15 at 18:10
I didn't catch that you /also/ wanted to compose transformation functions. But yeah, it works the same way for both jobs as `any_*` _erases_ the concrete type of the underlying range. It would seem to be much easier to only use `join` to concatenate ranges and compose the transformation functions separately using `std::function<>` (or `boost::function<>`) (so you get a compound functor for that, not more iterator layers) — sehe, Jan 02 '15 at 18:13
I've added a added [tag:ridiculously-comprehensive]™ demonstration of what I meant there. Hope that helps :) — sehe, Jan 02 '15 at 21:41
Wow, well that certainly is **ridiculously-comprehensive**. And it does help a lot. I admire your patience TBH :) — Darius, Jan 02 '15 at 23:36
@Darius Tenacity is a large part of what makes programmers, I think. Cheers — sehe, Jan 02 '15 at 23:37

Combining different iterators based on a runtime decision

1 Answers1

Update A demo program

Caveats: 2 library bugs

Full Code