Re: [boost] [range][rangex] Joining two unrelated ranges?

Subject: Re: [boost] [range][rangex] Joining two unrelated ranges?
From: adam.butcher_at_[hidden]
Date: 2009-06-23 05:27:26

Hi  Dean,

Dean Michael Berris wrote on 23/06/2009 08:54:32:
> Hi Guys,
> 
> I was wondering if a utility that allows the encapsulation (and
> merging) of two ranges is already part of RangeEx? I was thinking
> along the lines of:
> 
>   vector<int> a, b;
>   // populate a, populate b
>   auto r = concat(a, b); // concatenates the ranges into a single range
>   set<int> c(begin(r), end(r)); // r looks like a single forward range
> 
> I'm not sure if this is already supported in Boost.Range and it'd be
> nice to know if this is already in RangeEx.
> 
I sketched up a trial solution (possibly naive and possibly inefficient) 
to this a while ago when I didn't find the capability in boost.range 
(though maybe I missed it).

It works for two independent ranges whose value-types are convertible. 
Maybe such a utility could be included in boost.range after some 
validation/reviewing.  I've copied the source below (I could attach to 
preserve line endings if requested -- just thought it would be easier to 
quick-scan if I included it in this post).

Instead of providing a view on the concat'd range with concat(a,b) [which 
may be nicer] it allows you to get the begin and end iterators of it using 
multi_range_begin(a,b) and multi_range_end(a,b).  It would be simple to 
create such a concat view though.

Regards,
Adam

/////////////////////////////////////////////////////
////////////// example //////////////////////////////
/////////////////////////////////////////////////////

#include <stdext/multi-range-iterator.h>

#include <string>
#include <iostream>
#include <algorithm>
#include <iterator>

void addone( char& c )
{
   ++c;
}

int main()
{
   // some ranges
   std::string a("First");
   const char b[] = "Second";
   char c[] = "Third";

   // write the range [a,b] to stdout
   std::copy( stdext::multi_range_begin(a,b),
              stdext::multi_range_end(a,b),
              std::ostream_iterator<char>(std::cout) );
   std::cout << std::endl;

   // add one to each char in the range [a,c]
   std::for_each( stdext::multi_range_begin(a,c),
                  stdext::multi_range_end(a,c),
                  &addone );

   // add one to each char in the range [a,[c,a]])
   std::for_each( 
stdext::multi_range_begin(a,boost::make_iterator_range(stdext::multi_range_begin(c,a),stdext::multi_range_end(c,a))),
                  stdext::multi_range_end( 
a,boost::make_iterator_range(stdext::multi_range_begin(c,a),stdext::multi_range_end(c,a))),
                  &addone );

   // by now characters in 'a' have been incremented by 3
   // and characters in 'c' have been incremented by 2.

   // write the range [a,b] to stdout
   std::copy( stdext::multi_range_begin(a,b),
              stdext::multi_range_end(a,b),
              std::ostream_iterator<char>(std::cout) );
   std::cout << std::endl;

   // write the range [a,[b,c]] to stdout
   std::copy( 
stdext::multi_range_begin(a,boost::make_iterator_range(stdext::multi_range_begin(b,c),stdext::multi_range_end(b,c))),
              stdext::multi_range_end( 
a,boost::make_iterator_range(stdext::multi_range_begin(b,c),stdext::multi_range_end(b,c))),
              std::ostream_iterator<char>(std::cout) );
   std::cout << std::endl;
}

/////////////////////////////////////////////////////
////////////// utility //////////////////////////////
/////////////////////////////////////////////////////

#ifndef STDEXT_MULTI_RANGE_ITERATOR_H
#define STDEXT_MULTI_RANGE_ITERATOR_H

#include <boost/range.hpp>
#include <boost/type_traits/is_convertible.hpp>

#include <boost/mpl/if.hpp>
#include <boost/mpl/or.hpp>

namespace stdext {

namespace multi_range_detail
{
   struct mark_end {};
   template <typename FirstIt, typename SecondIt>
   struct iterator_tools;
}

/**
 * An iterator that traverses the two ranges as if they were one range
 * ordered FirstRange, SecondRange.  That is to say, the entire first
 * range is traversed, followed by the entire second range.  Note that
 * this iterator itself wraps three iterators; begin and end of
 * FirstRange, and begin of SecondRange.  Testing for end-of-range
 * should be made against end of SecondRange externally.
 */
template <typename FirstIt, typename SecondIt>
struct multi_range_forward_iterator : private boost::is_convertible< 
typename boost::iterator_value<FirstIt>::type
                                                                   , 
typename boost::iterator_value<SecondIt>::type >
{
   template <typename, typename>
   friend struct multi_range_detail::iterator_tools;

   typedef multi_range_detail::iterator_tools<FirstIt,SecondIt> 
iterator_tools;

   typedef std::forward_iterator_tag iterator_category;
   typedef typename boost::iterator_value<FirstIt>::type      value_type;
   typedef typename boost::iterator_difference<FirstIt>::type 
difference_type;
   typedef typename iterator_tools::reference                 reference;
   typedef typename boost::iterator_pointer<FirstIt>::type    pointer;

   multi_range_forward_iterator( FirstIt const&  begin_of_first,
                                 FirstIt const&  end_of_first,
                                 SecondIt const& begin_of_second )
      : begin1(begin_of_first)
      , end1(end_of_first)
      , begin2(begin_of_second)
   {
   }

   multi_range_forward_iterator( FirstIt const&  end_of_first,
                                 SecondIt const& end_of_second,
                                 multi_range_detail::mark_end )
      : begin1(end_of_first)
      , end1(end_of_first)
      , begin2(end_of_second)
   {
   }

   template <typename Iterator>
   bool operator== ( Iterator const& it ) const
   {
      return iterator_tools::compare_equal( this, it );
   }

   bool operator== ( multi_range_forward_iterator const& it ) const
   {
      return it.begin1 == begin1 && it.begin2 == begin2;
   }

   template <typename Iterator>
   bool operator!= ( Iterator const& it ) const
   {
      return !operator==(it);
   }

   multi_range_forward_iterator& operator++ ()
   {
      if( begin1 != end1 )
         ++begin1;
      else
         ++begin2;
      return *this;
   }

   multi_range_forward_iterator operator++ (int) const
   {
      multi_range_forward_iterator it(*this);
      ++it;
      return it;
   }

   reference operator* ()
   {
      if( begin1 != end1 )
         return *begin1;
      return *begin2;
   }

private:

   FirstIt  begin1, end1;
   SecondIt begin2;
};

namespace multi_range_detail
{
   using namespace boost::mpl;

   template <typename Ref1, typename Ref2, typename ValueType>
   struct common_reference
   {
      typedef typename boost::remove_reference<Ref1>::type without_ref1;
      typedef typename boost::remove_reference<Ref2>::type without_ref2;

      typedef typename
              if_< or_< boost::is_const<without_ref1>,
                        boost::is_const<without_ref2> >
                 , ValueType const&
                 , ValueType& >::type type;
   };

   template <typename FirstIt, typename SecondIt>
   struct iterator_tools
   {
      typedef multi_range_forward_iterator<FirstIt,SecondIt> owner_type;
 
      typedef typename multi_range_detail::
              common_reference< typename 
boost::iterator_reference<FirstIt>::type
                              , typename 
boost::iterator_reference<SecondIt>::type
                              , typename 
boost::iterator_value<SecondIt>::type >::type reference;
 
      inline bool compare_equal( owner_type* owner, const FirstIt& it )
      {
         return owner->begin1 == it;
      }
      static inline bool compare_equal( owner_type* owner, const SecondIt& 
it )
      {
         return owner->begin2 == it;
      }
   };
 
   template <typename CommonIt>
   struct iterator_tools<CommonIt,CommonIt>
   {
      typedef multi_range_forward_iterator<CommonIt,CommonIt> owner_type;

      typedef typename boost::iterator_reference<CommonIt>::type 
reference;

      static inline bool compare_equal( owner_type* owner, const CommonIt& 
it )
      {
         return owner->begin1 == it || owner->begin2 == it;
      }
   };
}

#define MULTI_RANGE_CONST const
#define MULTI_RANGE_NONCONST
#define DEFINE_MULTI_RANGE_BEGIN_END( const1, const2 )       \
    \
   template <typename FirstRange, typename SecondRange>           \
   multi_range_forward_iterator< typename boost::range_iterator<const1 
FirstRange>::type,      \
                                 typename boost::range_iterator<const2 
SecondRange>::type >      \
   multi_range_begin( const1 FirstRange& first, const2 SecondRange& second 
)  \
   {        \
      typedef typename boost::range_iterator<const1 FirstRange>::type 
first_iterator;      \
      typedef typename boost::range_iterator<const2 SecondRange>::type 
second_iterator;      \
      return multi_range_forward_iterator<first_iterator,second_iterator>( 
boost::begin(first), boost::end(first), boost::begin(second) );  \
   }        \
    \
   template <typename FirstRange, typename SecondRange>           \
   multi_range_forward_iterator< typename boost::range_iterator<const1 
FirstRange>::type,      \
                                 typename boost::range_iterator<const2 
SecondRange>::type >      \
   multi_range_end( const1 FirstRange& first, const2 SecondRange& second ) 
  \
   {        \
      typedef typename boost::range_iterator<const1 FirstRange>::type 
first_iterator;      \
      typedef typename boost::range_iterator<const2 SecondRange>::type 
second_iterator;      \
      return multi_range_forward_iterator<first_iterator,second_iterator>( 
boost::end(first), boost::end(second), multi_range_detail::mark_end() );  
\
   }        \

DEFINE_MULTI_RANGE_BEGIN_END( MULTI_RANGE_NONCONST, MULTI_RANGE_NONCONST )
DEFINE_MULTI_RANGE_BEGIN_END( MULTI_RANGE_NONCONST, MULTI_RANGE_CONST    )
DEFINE_MULTI_RANGE_BEGIN_END( MULTI_RANGE_CONST,    MULTI_RANGE_NONCONST )
DEFINE_MULTI_RANGE_BEGIN_END( MULTI_RANGE_CONST,    MULTI_RANGE_CONST    )

#undef DEFINE_MULTI_RANGE_BEGIN_END
#undef MULTI_RANGE_NONCONST
#undef MULTI_RANGE_CONST

} // stdext

#endif//STDEXT_MULTI_RANGE_ITERATOR_H

------------------------------------------------------------
This email and any attached files contains company confidential information which may be legally privileged. It is intended only for the person(s) or entity to which it is addressed and solely for the purposes set forth therein.  If you are not the intended recipient or have received this email in error please notify the sender by return, delete it from your system and destroy any local copies.  It is strictly forbidden to use the information in this email including any attachment or part thereof including copying, disclosing, distributing, amending or using for any other purpose.

In addition the sender excludes all liabilities (whether tortious or common law) for damage or breach arising or related to this email including but not limited to viruses and libel.
SELEX Communications Limited is a Private Limited Company registered in England and Wales under Company Number 964533 and whose Registered Office is Lambda House, Christopher Martin Rd, Basildon, SS14 3EL. England.