[boost] Re: Proposal: cartesian_product algorithm and a finite state machinetemplatelibrary

From: Marc Jacobs (marcja_at_[hidden])
Date: 2002-10-30 17:46:44

"Dirk Gerrits" <dirk_at_[hidden]> wrote in message
news:appjco$kql$1_at_main.gmane.org...
> Marc Jacobs wrote:
>
> > I'd like to offer two submissions to Boost.
> >
> > ----------------------------
> > The first is a straightforward implementation of a cartesian product
> > on two
> > ranges. That is, given iterators on two ranges, perform a binary
operation
> > on every combination of elements. Here is a pseudo-code example:
> >
> > r1 = { 'A', 'B', 'C' }
> > r2 = { 'D', 'E', 'F' }
> > // concat() is a binary functor that concatenates two characters into a
> > string
> > cartesian_product( r1.begin(), r1.end(), r2.begin(), r2.end(),
concat() )
> > // returns
> > // 'AD', 'AE', 'AF', 'BD', 'BE', 'BF', 'CD', 'CE', 'CF'
> >
> Wouldn't it be more STL like to take an output iterator parameter and
> return it after the function call? You know, like std::copy and such
> algorithms.

That's the way I implemented it. I just did a poor job of describing it sans
code in this thread. :)

Thanks for the input.
Marc

    /**
     * Performs a cartesian product, i.e. will perform __binary_op on every
combination of elements
     * between the first and second ranges.
     *
     * @param __first1          the beginning of the range for the left side
of the product
     * @param __last1           the end of the range for the left side of
the product
     * @param __first2          the beginning of the range for the right
side of the product
     * @param __last2           the end of the range for the left right of
the product
     * @param __binary_op       the binary operation to perform for each
pairing of the cartesian
     *                          product
     * @return                  an output iterator compatible with the
result of __binary_op
     */
    template< class _InputIter1, class _InputIter2, class _OutputIter, class
_BinaryOperation >
    _OutputIter cartesian_product(
        _InputIter1         __first1,
        _InputIter1         __last1,
        _InputIter2         __first2,
        _InputIter2         __last2,
        _OutputIter         __result,
        _BinaryOperation    __binary_op
    )
    {
        for( ; __first1 != __last1; ++__first1 )
            for( _InputIter2 __pos2 = __first2; __pos2 != __last2; ++__pos2,
++__result )
                *__result = __binary_op( *__first1, *__pos2 );

        return __result;
    }