Boost logo

Boost :

From: David Abrahams (dave_at_[hidden])
Date: 2002-11-25 09:15:22


"vladimir josef sykora" <vladimir.sykora_at_[hidden]> writes:

> Hello,
> Is there a way to apply a binary operation over two sequences?
> For example, I have two sequences: LHSseq and RHSseq. I want now to
> construct the return type, which is a sequence that cointains the result
> types of applying a binary operation for every member of the sequences.
> Something like:
>
> template<
> typename BOOST_MPL_AUX_VOID_SPEC_PARAM(LhsSequence)
> , typename BOOST_MPL_AUX_VOID_SPEC_PARAM(RhsSequence)
> , typename BOOST_MPL_AUX_VOID_SPEC_PARAM(BinaryOperation)
> >
> struct transform{..};
>
> usage:
> typedef transform<LHSseq,RHSseq,someBinOp>::type result_type;
>
> Guarantees complexity O(n)?

Consider applying the fold algorithm to the first sequence, using an
adapted binary operation, something like:

// ***** Untested! ********

// A dummy iterator that prevents us running off the end of the RHS sequence
template <class T>
struct prefix_iter
{
    typedef T next;
};

template <class binop, class accum = mpl::push_back<mpl::_,mpl::_> >
struct zip_op
{
    template <class L, class ResultIterPair>
    struct apply
    {
        // pre-increment the rhs iterator
        typedef typename ResultIterPair::second_type::next rhs_iter;

        // Dereference the rhs iterator to get the rhs value
        typedef typename rhs_iter::type rhs;

        // x = binop(L,rhs)
        typedef typename mpl::apply2<binop,L,rhs>::type x;

        // Get the result of the previous step
        typedef typename ResultIterPair::first_type prev_result;

        // accumulate x with that result.
        typedef typename mpl::apply2<accum,prev_result,x>::type result;

        // Finally, the return type
        typedef std::pair<rhs_iter,result> type;
    };
};

typedef mpl::fold<LhsSequence, zip_op<BinaryOperation>
        , std::pair<mpl::begin<RhsSequence>::type,mpl::vector<>
>::type::second_type answer;

...

Well I hope that was all instructive, but it was probably way more
complicated than neccessary. I think it would actually be far superior
to build a solution around an mpl iterator adaptor like this one:

   template <class IteratorSeq> struct zip_iterator
   {
        typedef typename mpl::transform<
              IteratorSeq,mpl::apply0<mpl::_1>
>::type type;

        typedef zip_iterator<
            typename mpl::transform<
               IteratorSeq,mpl::next<mpl::_1>
>::type
> next;
   };

and an operator adaptor like this one (don't know how to generalize
this one to N arguments yet):

  template <class Op, class Seq>
  struct binop_adaptor
      : mpl::apply2<
           Op
           , typename mpl::begin<Seq>::type
           , typename mpl::next<mpl::begin<Seq>::type>::type
>
  {
  };

How about that?

-- 
                       David Abrahams
   dave_at_[hidden] * http://www.boost-consulting.com
Boost support, enhancements, training, and commercial distribution

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk