Re: [boost] combinations and permutations

Subject: Re: [boost] combinations and permutations
From: Howard Hinnant (howard.hinnant_at_[hidden])
Date: 2011-01-04 11:30:02

On Jan 4, 2011, at 11:01 AM, Dave Abrahams wrote:

> At Mon, 3 Jan 2011 22:40:25 -0500,
> Howard Hinnant wrote:
>> 
>> Warming this up for tr2:
>> 
>> http://home.roadrunner.com/~hinnant/combinations.html
>> 
>> Comments welcome.  Real world use welcome.
> 
> Hi Howard,
> 
> Neat stuff!  Was there a real-world use case driving this work, or are
> you just going all Knuth on us in your copious spare time?

One of my first applications of for_each_combination was for writing unit tests for rvalue reference overloading.  This was done in 2004 or 2005, and so those tests are now obsolete due to the language changes since then.  But in a nutshell I needed to write tests that covered every combination of passing an lvalue or rvalue, not-cv-qualified, const, volatile and const volatile qualified, to a set of overloaded set of functions each taking one parameter.  That one parameter was a cv-qaulified lvalue or rvalue reference (each combination).  And I needed to consider all combinations of that set of 8 overloaded functions 1 at a time, 2 at time, etc. up to 8 at a time.

Here is one file containing just 8 tests that considered all 8 overloads at once:

// I, Howard Hinnant, hereby place this code in the public domain.

// Test overload resolution among referece types

// { dg-do compile }
// { dg-options "-std=c++0x" }

template <bool> struct sa;
template <> struct sa<true> {};

struct one   {char x[1];};
struct two   {char x[2];};
struct three {char x[3];};
struct four  {char x[4];};
struct five  {char x[5];};
struct six   {char x[6];};
struct seven {char x[7];};
struct eight {char x[8];};

struct A
{
    A();
    A(const volatile A&&);
};

               A    source();
const          A  c_source();
      volatile A  v_source();
const volatile A cv_source();

// 8 at a time

one   sink_8_12345678(               A&);
two   sink_8_12345678(const          A&);
three sink_8_12345678(volatile       A&);
four  sink_8_12345678(const volatile A&);
five  sink_8_12345678(               A&&);
six   sink_8_12345678(const          A&&);
seven sink_8_12345678(volatile       A&&);
eight sink_8_12345678(const volatile A&&);

int test8_12345678()
{
                   A a;
    const          A ca = a;
          volatile A va;
    const volatile A cva = a;
    sa<sizeof(sink_8_12345678(a))           == 1> t1;
    sa<sizeof(sink_8_12345678(ca))          == 2> t2;
    sa<sizeof(sink_8_12345678(va))          == 3> t3;
    sa<sizeof(sink_8_12345678(cva))         == 4> t4;
    sa<sizeof(sink_8_12345678(source()))    == 5> t5;
    sa<sizeof(sink_8_12345678(c_source()))  == 6> t6;
    sa<sizeof(sink_8_12345678(v_source()))  == 7> t7;
    sa<sizeof(sink_8_12345678(cv_source())) == 8> t8;
    return 0;
}

int main()
{
    return test8_12345678();
}

If I'm not mistaken, the total number of tests that needed to be written was a little over 2000.  I used for_each_combination to semi-automate the writing of these tests.  This both saved manual effort, and ensured that the test suite covered every combination.

Since I wrote those rvalue-ref tests I lacked the time to refine and complete this set of algorithms.  I took it on as my pet project over the holidays.

-Howard