Re: [Boost-users] [iterators][range][rangeex] range concatenation

Subject: Re: [Boost-users] [iterators][range][rangeex] range concatenation
From: Dmitry Vinogradov (sraider_at_[hidden])
Date: 2009-04-06 16:09:01

Thorsten Ottosen wrote:
> er skrev:
>> Dmitry Vinogradov wrote:
>>> Is it possible with Boost (or RangeEx) to concatenate ranges?
>>>
>>> Sample usage:
>>>
>>> template <class Range> void process_range(Range const &);
>>>
>>> std::vector<foo> v = ...;
>>> std::list<foo> l = ...;
>>> process_range(concat(v, l));
>>
>> I take it you have a good reason not to simply copy v and l into a new 
>> container. iterator_facade might help, and iterator_range to obtain a 
>> range.
> 
> It will be impossible to implement a generic iterator that allows
> for fast iteration over the two ranges. The problem is that the
> iterator would have to check when the new container starts, similar to 
> segments in a std::deque<T>.
> 
> So I would just call process_range() twice. If you really need to
> view the two ranges as one range, then you have to pay an abstraction 
> penalty, albeit it might be more efficiant than copying the two 
> containers into a new one (and it is probably not that trivial to write 
> the iterator that depends on two or more other iterator types).
> 
> If "foo" is a heavy object, then copying the references of the elements
> to a new container std::vector<boost::reference_wrapper<foo>> is 
> probably the most efficient alternative.
> 

Calling process_range() twice is not a solution in my case. Copying 
references to a new container is a better way.

Regarding efficiency, can you look thru my rough concat() implementation 
attached to discover any its disadvantages?


#define BOOST_TEST_MODULE ConcatTest
#include <boost/test/unit_test.hpp>
#include <vector>
#include <list>
#include "concat.h"

template <typename Range1, typename Range2, typename Range3>
bool TestConcat(Range1 &r1, Range2 &r2, Range3 &r3)
{
        std::vector<int> v1, v2;
        v1.insert(v1.end(), r1.begin(), r1.end());
        v1.insert(v1.end(), r2.begin(), r2.end());
        v2.insert(v2.end(), r3.begin(), r3.end());
        return v1 == v2;
}

template <typename Range1, typename Range2>
bool TestConcat(Range1 &r1, Range2 &r2)
{
        return TestConcat(r1, r2, Concatenate(r1, r2));
}

BOOST_AUTO_TEST_CASE(Concat)
{
        int a1[] = { 1, 2, 3, 4, 5 };
        int a2[] = { 10, 11, 12 };
        std::vector<int> v(boost::begin(a1), boost::end(a1));
        std::list<int> l(boost::begin(a2), boost::end(a2));
        int value = 0;
        boost::iterator_range<int*> i(&value, &value+1), n((int*)NULL, (int*)NULL);
    
        BOOST_CHECK(TestConcat(l, v));
        BOOST_CHECK(TestConcat(v, l));
        BOOST_CHECK(TestConcat(v, v));
        BOOST_CHECK(TestConcat(n, v));
        BOOST_CHECK(TestConcat(v, n));
        BOOST_CHECK(TestConcat(n, n));
        BOOST_CHECK(TestConcat(n, i));
        BOOST_CHECK(TestConcat(i, n));
        BOOST_CHECK(TestConcat(i, v));
        BOOST_CHECK(TestConcat(i, i));
}


#pragma once

#include <boost/iterator/iterator_facade.hpp>
#include <boost/range/iterator_range.hpp>
#include <boost/variant.hpp>
#include <boost/variant/apply_visitor.hpp>
#include <boost/variant/static_visitor.hpp>

template <typename reference>
struct DereferenceVisitor : public boost::static_visitor<reference>
{
        template <typename T>
        reference operator()(T Iterator) const
        {
                return *Iterator;
        }
};

struct IncrementVisitor : public boost::static_visitor<void>
{
        template <typename T>
        void operator()(T &Value) const
        {
                ++Value;
        }
};

struct DecrementVisitor : public boost::static_visitor<void>
{
        template <typename T>
        void operator()(T &Value) const
        {
                --Value;
        }
};

template <class TIterator1, class TIterator2, class TValue = typename boost::iterator_value<TIterator1>::type >
class ConcatIterator : public boost::iterator_facade<ConcatIterator<TIterator1, TIterator2, TValue>, TValue, boost::bidirectional_traversal_tag>
{
public:
        template <class TIterator>
        ConcatIterator(TIterator It, size_t Range /* 0 for the first range, 1 for the second range */, TIterator1 End1, TIterator2 Begin2) :
                It(It), Range(Range), End1(End1), Begin2(Begin2)
        {
                Stabilize();
        }

private:
        void Stabilize()
        {
                if ((Range == 0) && (It == End1))
                {
                        It = Begin2;
                        Range = 1;
                }
        }

public:
        reference dereference() const
        {
                return boost::apply_visitor(DereferenceVisitor<reference>(), It);
        }

        void increment()
        {
                boost::apply_visitor(IncrementVisitor(), It);
                if ((Range == 0) && (It == End1))
                {
                        It = Begin2;
                        Range = 1;
                }
        }

        void decrement()
        {
                if ((Range == 1) && (It == Begin2))
                {
                        It = End1;
                        Range = 0;
                }
                boost::apply_visitor(DecrementVisitor(), It);
        }

        bool equal(const ConcatIterator& lhs) const
        {
                return (Range == lhs.Range) && (It == lhs.It);
        }

private:
        size_t Range;
        boost::variant<TIterator1, TIterator2> It, End1, Begin2;
};

template <class TRange1, class TRange2>
boost::iterator_range<ConcatIterator<typename TRange1::iterator, typename TRange2::iterator> >
Concatenate(TRange1 &Range1, TRange2 &Range2)
{
        typedef ConcatIterator<typename TRange1::iterator, typename TRange2::iterator> TIterator;
        return boost::make_iterator_range(
                TIterator(Range1.begin(), 0, Range1.end(), Range2.begin()),
                TIterator(Range2.end  (), 1, Range1.end(), Range2.begin()));
}

template <class TRange1, class TRange2>
boost::iterator_range<ConcatIterator<typename TRange1::const_iterator, typename TRange2::const_iterator> >
Concatenate(TRange1 const &Range1, TRange2 const &Range2)
{
        typedef ConcatIterator<typename TRange1::const_iterator, typename TRange2::const_iterator> TIterator;
        return boost::make_iterator_range(
                TIterator(Range1.begin(), 0, Range1.end(), Range2.begin()),
                TIterator(Range2.end  (), 1, Range1.end(), Range2.begin()));
}