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

6 Apr 2009

      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()));
}