Re: [boost] combinations and permutations

Subject: Re: [boost] combinations and permutations
From: Howard Hinnant (howard.hinnant_at_[hidden])
Date: 2011-01-05 14:45:08

On Jan 5, 2011, at 7:20 AM, bernardH wrote:

> Hi,
> 
> Howard Hinnant <howard.hinnant <at> gmail.com> writes:
>> I'm not sure if it is desirable
>> though.  It is an awful lot of if-checking added to the algorithm.
>> All that checking would tend to penalize
>> those clients not wanting to break out early.
> 
> Couldn't the checks for early breaks be removed at
> compile-time by using callable returning
> a convertible to bool instead of a bool ?
> 
> At least it appears to do so when returning a 
> boost::mpl::bool_<false> with g++ at default optimization level.[*]
> 
> Best Regards,
> Bernard
> 
> [*] http://paste.debian.net/103792/

Thanks for the code sample.  That *always* helps.

In my current code my algorithm is recursive:

template <class BidirectionalIterator, class Function>
void
combine_discontinuous(BidirectionalIterator first1, BidirectionalIterator last1,
                      typename std::iterator_traits<BidirectionalIterator>::difference_type d1,
                      BidirectionalIterator first2, BidirectionalIterator last2,
                      typename std::iterator_traits<BidirectionalIterator>::difference_type d2,
                      Function& f,
                      typename std::iterator_traits<BidirectionalIterator>::difference_type d = 0)
{
    typedef typename std::iterator_traits<BidirectionalIterator>::difference_type D;
    using std::swap;
    if (d2 == 0)
        f();
    else
    {
        switch (d1)
        {
        case 0:
            return;
        case 1:
            for (BidirectionalIterator i2 = first2; i2 != last2; ++i2)
            {
                f();
                swap(*first1, *i2);
            }
            break;
        default:
            BidirectionalIterator f1p = std::next(first1);
            BidirectionalIterator i2 = first2;
            for (D d22 = d2; i2 != last2; ++i2, --d22)
            {
                combine_discontinuous(f1p, last1, d1-1, i2, last2, d22, f, d+1);
                swap(*first1, *i2);
            }
            break;
        }
        f();
        if (d != 0)
            rotate_discontinuous(first1, last1, d1, std::next(first2), last2, d2-1);
        else
            rotate_discontinuous(first1, last1, d1, first2, last2, d2);
    }
}

Transforming this to break out early:

template <class BidirectionalIterator, class Function>
bool
combine_discontinuous(BidirectionalIterator first1, BidirectionalIterator last1,
                      typename std::iterator_traits<BidirectionalIterator>::difference_type d1,
                      BidirectionalIterator first2, BidirectionalIterator last2,
                      typename std::iterator_traits<BidirectionalIterator>::difference_type d2,
                      Function& f,
                      typename std::iterator_traits<BidirectionalIterator>::difference_type d = 0)
{
    typedef typename std::iterator_traits<BidirectionalIterator>::difference_type D;
    using std::swap;
    if (d2 == 0)
    {
        if (f())
            return true;
    }
    else
    {
        switch (d1)
        {
        case 0:
            return false;
        case 1:
            for (BidirectionalIterator i2 = first2; i2 != last2; ++i2)
            {
                if (f())
                    return true;
                swap(*first1, *i2);
            }
            break;
        default:
            BidirectionalIterator f1p = std::next(first1);
            BidirectionalIterator i2 = first2;
            for (D d22 = d2; i2 != last2; ++i2, --d22)
            {
                if (combine_discontinuous(f1p, last1, d1-1, i2, last2, d22, f, d+1))
                    return true;
                swap(*first1, *i2);
            }
            break;
        }
        if (f())
            return true;
        if (d != 0)
            rotate_discontinuous(first1, last1, d1, std::next(first2), last2, d2-1);
        else
            rotate_discontinuous(first1, last1, d1, first2, last2, d2);
    }
    return false;
}

The problem is I can't return a compile-time constant because of the recursion.  To complicate things, in some of the algorithms I wrap the Function with an adaptor on the way down in order to fancier things like reversible_permutation.

That's the bad news.  Now since I went to the trouble to code this up to show you my problem, I figured I might as well test it.  ...  It doesn't seem to be any slower! :-)

Wouldn't be the first time the compiler is smarter than I give it credit for. ;-)

Now all I have to decide is if I like this break-out feature enough to require all user-supplied functors to follow the convention: return false if you don't want to break out of the loop, else return true when you want to break.

The answer might depend upon if we get an equally performant next_* going.  If we do, then I don't think the functor  should return a bool to break:  instead the client should use next_*.  If we don't, then putting in the break feature means, at least to me, that there is no reason to use the next_* variant since it is always slower (even if only by a little).

Thanks for furthering these algorithms.

-Howard