Monthly Archives: October 2009

Cartesian Product with Boost.Preprocessor

Today is another exciting day as I finished the Preprocessor macro version of the Cartesian Product issue, unlike the template version, whose incarnation is a template class. This version is a switch-case structure.  Now that the infrastructure is ready, I’ll be able to concentrate on the concurrent studies again.

A great relief to several weeks of braining. and just in time for my holiday starting from tomorrow.

Code:

#ifndef CARTISIAN_PRODUCT_SWITCH_CASE_H

#define CARTISIAN_PRODUCT_SWITCH_CASE_H

#include <boost/preprocessor/seq/for_each_product.hpp>

#include <boost/preprocessor/seq/to_tuple.hpp>

/*

===========

Description:

===========

this macro construct a switch-case structrue by apply the Cartisian Product of

3-sequence to a clause that takes them as inputs.

i.e.

switch(NAME_OF_SWITCH_INDEX)

{

case ( COMPOSE_INDEX_FROM_SEQ): CLAUSE_FOR_EACH_CASE; break;

… …

case ( COMPOSE_INDEX_FROM_SEQ ): CLAUSE_FOR_EACH_CASE; break;

default: break;

}

for example:

Given 3 Sequences S1,S2,S3, if size(S1) =3,  size(S1) =2,  size(S1) =3,  the following something like

the following would be yielded:

switch(idx)

{

case ( ((0 & 0xF)<<8)| ((0 & 0xF)<<4)| ((0 & 0xF)) ): details::scanT<(0, 0, 0)>(); break;

case ( ((0 & 0xF)<<8)| ((0 & 0xF)<<4)| ((1 & 0xF)) ): details::scanT<(0, 0, 1)>(); break;

case ( ((0 & 0xF)<<8)| ((0 & 0xF)<<4)| ((2 & 0xF)) ): details::scanT<(0, 0, 2)>(); break;

case ( ((0 & 0xF)<<8)| ((1 & 0xF)<<4)| ((0 & 0xF)) ): details::scanT<(0, 1, 0)>(); break;

case ( ((0 & 0xF)<<8)| ((1 & 0xF)<<4)| ((1 & 0xF)) ): details::scanT<(0, 1, 1)>(); break;

case ( ((0 & 0xF)<<8)| ((1 & 0xF)<<4)| ((2 & 0xF)) ): details::scanT<(0, 1, 2)>(); break;

default: break;

}

===========

How to Use:

===========

// 1/2 change the following defines and call GENERATE_SWITCH_STRUCTURE_FOR_CARTISIAN_PRODUCTS

#define SIZE_OF_SEQ1 2

#define SIZE_OF_SEQ2 5

#define SIZE_OF_SEQ3 5

#define NAME_OF_SWITCH_INDEX g_method

#define CLAUSE_FOR_EACH_CASE(ONE_BOOST_PP_SEQ_TYPE_INSTANCE) \

details::scanT<ONE_BOOST_PP_SEQ_TYPE_INSTANCE>()

#define CLAUSE_FOR_DEFAULT_LABLE   std::wcout << L”this combination is not supported.”

// 2/2 run the macro

GENERATE_SWITCH_STRUCTURE_FOR_CARTISIAN_PRODUCTS

// ========       change this define if you prefer another algotithm         ========

// define variable name for switch

#ifndef NAME_OF_SWITCH_INDEX

#define NAME_OF_SWITCH_INDEX idx

#endif

//  define clause for case: label

#ifndef CLAUSE_FOR_EACH_CASE

#define CLAUSE_FOR_EACH_CASE(ONE_BOOST_PP_SEQ_TYPE_INSTANCE) ;

#endif

//  define clause for default: label

#ifndef CLAUSE_FOR_DEFAULT_LABLE

#define CLAUSE_FOR_DEFAULT_LABLE

#endif

*/

// Compose a 12-bit integer from 3-nibbles, which is represented by a BOOST_PP_TUPLE

//  i.e.    (X, Y, Z)    ==>     ( ((X & 0xF)<<8)| ((Y & 0xF)<<4)| ((Z & 0xF)) )

#define EXTRACT_FOUR_BIT_NIBBLE(N)  (N & 0xF)

#ifndef COMPOSE_INDEX_FROM_SEQ

#define COMPOSE_INDEX_FROM_SEQ(S) (\

(EXTRACT_FOUR_BIT_NIBBLE(BOOST_PP_SEQ_ELEM(0, S))<<8)|\

(EXTRACT_FOUR_BIT_NIBBLE(BOOST_PP_SEQ_ELEM(1, S))<<4)|\

(EXTRACT_FOUR_BIT_NIBBLE(BOOST_PP_SEQ_ELEM(2, S)))\

)

#endif

// ===== DO NOT CHANGE ANYTHING BELOW THIS LINE, UNLESS YOU KNOW WHAT YOU ARE DOING =====

// define all 3 parts of a switch-case block

#define BEGIN_SWITCH(METHOD_INDEX) switch(METHOD_INDEX) {

#define CASE(S) \

case COMPOSE_INDEX_FROM_SEQ(S):     \

CLAUSE_FOR_EACH_CASE(BOOST_PP_SEQ_ENUM(S)); break;

#define END_SWITCH \

default:    \

CLAUSE_FOR_DEFAULT_LABLE; }

// define 3 integer sequence  represented by a BOOST_PP_SEQUENCE

// i.e. N ==> (0) (1) (2)… (N-1) (N)

#define DECL_SELF(z, n, text) (n)

#define S1 BOOST_PP_REPEAT(SIZE_OF_SEQ1, DECL_SELF, UNUSED)

#define S2 BOOST_PP_REPEAT(SIZE_OF_SEQ2, DECL_SELF, UNUSED)

#define S3 BOOST_PP_REPEAT(SIZE_OF_SEQ3, DECL_SELF, UNUSED)

// apply macro CASE to each Cartisian product of (S1)(S2)(S3)

#define APPLY_ONE(r, product) CASE(product)

// run the macros    and  release all tokens used here

// example oupput:

/*

switch(idx)

{

case ( ((0 & 0xF)<<8)| ((0 & 0xF)<<4)| ((0 & 0xF)) ): details::scanT<(0, 0, 0)>(); break;

case ( ((0 & 0xF)<<8)| ((0 & 0xF)<<4)| ((1 & 0xF)) ): details::scanT<(0, 0, 1)>(); break;

case ( ((0 & 0xF)<<8)| ((0 & 0xF)<<4)| ((2 & 0xF)) ): details::scanT<(0, 0, 2)>(); break;

case ( ((0 & 0xF)<<8)| ((1 & 0xF)<<4)| ((0 & 0xF)) ): details::scanT<(0, 1, 0)>(); break;

case ( ((0 & 0xF)<<8)| ((1 & 0xF)<<4)| ((1 & 0xF)) ): details::scanT<(0, 1, 1)>(); break;

case ( ((0 & 0xF)<<8)| ((1 & 0xF)<<4)| ((2 & 0xF)) ): details::scanT<(0, 1, 2)>(); break;

default: break;

}

*/

#define GENERATE_SWITCH_STRUCTURE_FOR_CARTISIAN_PRODUCTS \

BEGIN_SWITCH(NAME_OF_SWITCH_INDEX) \

BOOST_PP_SEQ_FOR_EACH_PRODUCT(APPLY_ONE, (S1)(S2)(S3)) \

END_SWITCH

/*

#undef COMPOSE_INDEX

#undef BEGIN_SWITCH

#undef CASE

#undef END_SWITCH

#undef APPLY_ONE

#undef DECL_SELF

#undef S1

#undef S2

#undef S3

#undef SIZE_OF_SEQ1

#undef SIZE_OF_SEQ2

#undef SIZE_OF_SEQ3

#undef NAME_OF_SWITCH_INDEX

#undef CLAUSE_FOR_EACH_CASE

*/

#endif

A Day of Achievement – Cartesian Product with Boost.MPL

Today is a day worthy of celebration, as I finally solved a problem I’ve been working on for quite some time.  See it here.

Code:

#ifndef TRI_TYPE_CARTESIAN_PRODUCT_H
#define TRI_TYPE_CARTESIAN_PRODUCT_H

#include <boost/mpl/vector.hpp>

#include <typeinfo>

namespace recursive
{
    using boost::is_same;
    using boost::mpl::begin;
    using boost::mpl::end;
    using boost::mpl::next;        
    using boost::mpl::if_;  
    using boost::mpl::deref;    
    using boost::mpl::size;
    using boost::mpl::advance;  
    using boost::mpl::int_;  
    
    namespace detail
    {
        unsigned int total_recursions = 0;

        struct end_of_recursion_tag 
        {
            static void Run()
            {
                std::cout << "end of " 
                     << total_recursions 
                     << " recursions\n"
                    ;
                    
                total_recursions = 0;
            }
        };    
    }
    
    // generate a Cartesian Product of 3 type sequences and apply TestFunc on each generated type
    template <
        class UTypes,    // Forward Sequence, e.g. boost::mpl::vector
        class VTypes,    // Forward Sequence, e.g. boost::mpl::vector
        class WTypes,    // Forward Sequence, e.g. boost::mpl::vector
        class TestFunc  // class type that has a nested templated run() member function
    >
    struct CartesianProduct
    {
        // forward declaration
        template <
            class UIterator,
            class VIterator,
            class WIterator 
        >   
        class Generate;

        // this class implements recursion body 
        template <
            class UIterator,
            class VIterator,
            class WIterator
        >            
        struct Next
        {
            // u_begin is not necessary 😉
            // it would be cheaper not to pre-declare all of them since we force evaluation
            // however this dramatically increase the readability
            typedef typename begin<VTypes>::type v_begin;
            typedef typename begin<WTypes>::type w_begin;

            typedef typename end<UTypes>::type u_end;
            typedef typename end<VTypes>::type v_end;
            typedef typename end<WTypes>::type w_end;

            typedef typename next<UIterator>::type u_next;
            typedef typename next<VIterator>::type v_next;
            typedef typename next<WIterator>::type w_next;
        
            typedef typename if_< is_same<typename w_next, w_end>,
                                typename if_< is_same<v_next, v_end>,
                                    typename if_< is_same<u_next, u_end>,
                                        detail::end_of_recursion_tag,
                                        Generate< 
                                            u_next, 
                                            v_begin, 
                                            w_begin 
                                        >
                                    >::type,
                                    Generate< 
                                        UIterator, 
                                        v_next,
                                        w_begin 
                                    >
                                >::type,
                                Generate< 
                                    UIterator, 
                                    VIterator, 
                                    w_next
                                    >
                            >::type type;
        };
        
        //  this class run test on generated types in thos round and go to next*/
        template <
            class UIterator = typename begin<UTypes>::type,
            class VIterator = typename begin<VTypes>::type,
            class WIterator = typename begin<WTypes>::type
        >
        struct Generate
        {
            //  generate <<next>> target type         
            typedef typename Next<
                    UIterator, 
                    VIterator, 
                    WIterator 
                >::type next_type;

            static void Run()
            {
                // increment recursion counter                
                ++detail::total_recursions;
                
                // test on the generated types of this round of recursion
                TestFunc::run<
                     typename deref<UIterator>::type,
                     typename deref<VIterator>::type,
                     typename deref<WIterator>::type
                 >();

                // go to the next round of recursion
                next_type::Run();
            }
        };
    
        template <
            size_t UIndex = 0,
            size_t VIndex = 0,
            size_t WIndex = 0
        >
        struct GenerateByIndex
        {                
            static_assert(UIndex <= size<UTypes>::type::value, "too large stock container index");
            static_assert(VIndex <= size<VTypes>::type::value, "too large stock shrinker_group_number index");
            static_assert(WIndex <= size<WTypes>::type::value, "too large stock shrinker_group_size index");

            typedef typename begin<UTypes>::type u_begin;        
            typedef typename begin<VTypes>::type v_begin;
            typedef typename begin<WTypes>::type w_begin;         
    
            static void Run()
            {  
                Generate<
                    typename advance<u_begin, int_<UIndex> >::type,
                    typename advance<v_begin, int_<VIndex> >::type,
                    typename advance<w_begin, int_<WIndex> >::type                    
                >::Run();
            }
        };                
    };
    
    struct print_typeid
    {
        template<
            class U, 
            class V, 
            class W
        >
        static void run()
        {
            // print the typeinfo
            std::cout 
                <<  detail::total_recursions << ":"
                << typeid(U).name() << ","
                << typeid(V).name() << ","
                << typeid(W).name()
                << std::endl;  
        }            
    }; 
    
}//  namespace recursive_test

#endif