Re: [Boost-users] [Boost.MPL and Boost.Fusion] Combinatorial gamewith typelists

From: Tobias Schwinger (tschwinger_at_[hidden])
Date: 2008-01-04 11:18:44

dariomt_at_[hidden] wrote:
> Tobias Schwinger wrote:
> 
>  > Here's an MPL-based solution.
> Whoa! Thanks a lot!
> 
>  > compiles with GCC4
> For me it also works with VS2003

Good.

>  
> Right now I'm still scratching my head in astonishment ;)
> I'll definitely come back looking for some more help to understand your 
> solution.

The algorithm is quite easy -- the details around it take some time to
get used to :). Here's a runtime version of the metaprogram simulating
types with strings.

Regards,
Tobias


#include <vector>
#include <boost/assign/std/vector.hpp>

#include <string>
#include <iostream>

typedef std::string type;
typedef std::vector<type> type_vector;

class cursor
{
    type_vector::const_iterator here, start, end;
  public:

    cursor(type_vector const& l)
      : here(l.begin()), start(l.begin()), end(l.end())
    { }

    // A return value of true means: "We reached the end and reset the position
    // to the start" ('wrapped' member in compile time version).
    //
    // Note: We change the state of the cursor, here.
    // Compile time algorithms are strictly functional, so the 'next' and
    // 'wrap_around' metafunctions have to create new cursor types.
    bool wrapping_next()
    {
        if (++here == end) 
        {
            here = start;
            return true;
        }
        return false;
    }

    type deref() const
    {
        return *here;
    }
};

typedef std::vector<cursor> cursor_vector;

// Returns 'true' if all combinations (if any) have been processed.
bool nested_loops_step(cursor_vector& cursors)
{
    // Note: In compile time world we create a new sequence since types are
    // immutable -- once they are there we can't change them.
    for (cursor_vector::iterator i = cursors.begin(), e = cursors.end();
            i != e; ++i)
        if (! i->wrapping_next())
              return false;

    return true;
}

int main()
{
    using namespace boost::assign;

    type_vector l1; l1 += std::string("A1"), std::string("A2");
    type_vector l2; l2 += std::string("B1"), std::string("B2");
    type_vector l3; l3 += std::string("C1"), std::string("C2");

    cursor_vector cursors; cursors += cursor(l1), cursor(l2), cursor(l3);

    // Note: We use the algorithm to determine whether there is something
    // to do in the first place (just like the compile time version).
    // However, the runtime version works directly on mutable cursors, so
    // we copy the sequence to ignore its effect on the cursors.
    cursor_vector disposable_copy_of_cursors(cursors);
    if (! nested_loops_step(disposable_copy_of_cursors))
    {
        do
        {
            std::cout << cursors[0].deref() << ',' << cursors[1].deref() << ',' 
                << cursors[2].deref() << std::endl;

        } while (! nested_loops_step(cursors));
    }
}