CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 9 of 9
  1. #1
    Join Date
    Aug 2009
    Posts
    25

    [RESOLVED] Problems with writing a metaprogram

    Hi, I have an enum in my program named Stype like below
    Code:
    enum Stype { T1, T2, T3 };
    There is a template function compute which take two Stype as
    template parameter
    Code:
    template< Stype st1, Stype st2 >
    void compute(){
    COMPILE_TIME_ASSERT(st1<=st2);
    // do something
    }
    compute is symmetric so that compute<T1,T2>() == compute<T2,T1>()
    but I want to restrict user to be able to call compute onnly when st1<=st2 as
    forced by a compile-time assert in code.

    Now, there is a function compute_at_runtime which is passed two Stype t1, t2 and calls the
    correct compute function based on types of t1&t2. currently I have implemented it by hand like below
    Code:
    void compute_at_runtime( Stype t1, Stype t2 )
    {
    	if( t1==T1 ){
    		if( t2==T1 ){
    			compute<T1,T1>();
    		} else
    		if( t2==T2 ){
    			compute<T1,T2>();
    		} else
    		if( t2==T3 ){
    			compute<T1,T3>();
    		}
    	} else
    	if ( t1==T2 ){
    		if ( t2==T2 ){
    			compute<T2,T2>();
    		} else
    		if ( t2==T3 ){
    			compute<T2,T3>();
    		}
    	} else
    	if ( t1==T3 ){
    		if ( t2==T3 ){
    			compute<T3,T3>();
    		}
    	}
    }
    but I want to make it a metaprogram which generates the code automatically by
    recursive template instanciating (like Factorial<N> example) because the user
    must be able to extend Stype with new types ( e.g. T4,T5,... ) and it becomes
    vary cumbersome to take care of this function

    I have written some simple metaprograms, but this one is very hard for me.
    I would be very appreciated if anyone could help me with this
    Many Thanks

  2. #2
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Seattle, WA
    Posts
    10,895

    Re: Problems with writing a metaprogram

    You're trying to make a runtime decision using compile-time syntax. That's going to be tricky at best.

    One option might be to use a std::map from the pair of enum values to the appropriate function pointer. It might be possible to use metaprogramming to specify the map contents at compile time, in combination with Boost.Assignment.

  3. #3
    Join Date
    Aug 2009
    Posts
    25

    Re: Problems with writing a metaprogram

    Thanks I did not know about Boost.Assignment
    1- since the number of types T1,T2,... is limited (i'm sure it would be less than 10)
    the map search algorithm becomes a little inefficient compared to a simple search

    2- and also compute_runtime will be called in a loop it is important for me to make
    it as fast as possible, so I want to avoid using function pointers

    so what if I want to avoid std::map and function pointers and have the if/else statement
    to be generated by a metaprogram

    Thanks

  4. #4
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Seattle, WA
    Posts
    10,895

    Re: Problems with writing a metaprogram

    Quote Originally Posted by ar115 View Post
    1- since the number of types T1,T2,... is limited (i'm sure it would be less than 10)
    the map search algorithm becomes a little inefficient compared to a simple search
    I doubt very much that map's O(lg n) search would be less efficient than an exhaustive series of if/else statements. However, it's possible it might not provide good cache behavior; in that case, arranging to use a sorted vector of function pointers with std::lower_bound() will alleviate the problem.

    2- and also compute_runtime will be called in a loop it is important for me to make
    it as fast as possible, so I want to avoid using function pointers
    Now, that is interesting. Is it likely to be called with the same parameters every time, or will they change?

    I'm not good with metaprogramming so I can't offer much specific advice.

  5. #5
    Join Date
    Aug 2009
    Posts
    25

    Re: Problems with writing a metaprogram

    Quote Originally Posted by Lindley View Post
    I doubt very much that map's O(lg n) search would be less efficient than an exhaustive series of if/else statements. However, it's possible it might not provide good cache behavior; in that case, arranging to use a sorted vector of function pointers with std::lower_bound() will alleviate the problem.
    I think you are correct, map binary search is good, and I think it would be fastest if the series of
    left/right comparisons become unrolled at compile time ( again metaprogram! )

    Quote Originally Posted by Lindley View Post
    Now, that is interesting. Is it likely to be called with the same parameters every time, or will they change?
    I'm not good with metaprogramming so I can't offer much specific advice.
    in code it would be called like this
    Code:
    std::vector<Stype>  stype1;
    std::vector<Stype> stype2;
    for (int i=0; i<N; ++i){
          compute_at_runtime( stype1[i], stype2[i] );
    }
    So each time it would be called with different parameters
    Thanks

  6. #6
    Join Date
    Oct 2008
    Posts
    1,456

    Re: Problems with writing a metaprogram

    premising that I don't fully understand why are you doing so... you can use boost mpl for_each;

    first of all, you'll need to make your enum "iteratable" by writing "struct Stype{ enum type { T1, T2, T3, size }; };" ( or use an mpl sequence from the beginning ), then you'll need to build the set of "allowed" pairs, finally iterate over them. The produced code should be roughly equivalent to your hand written if's:

    Code:
    #include <boost/mpl/range_c.hpp>
    #include <boost/mpl/arithmetic.hpp>
    #include <boost/mpl/transform_view.hpp>
    #include <boost/mpl/filter_view.hpp>
    #include <boost/mpl/for_each.hpp>
    
    struct Stype{ enum type { T1, T2, T3, size }; };
    
    template< Stype::type st1, Stype::type st2 >
    void compute(){/*...*/}
    
    struct call_compute
    {
    	call_compute( Stype::type v1, Stype::type v2 )
    		: v1(v1), v2(v2) {}
    
    	template< typename T > void operator()( T )
    	{
    		using namespace boost::mpl;
    
    		static const Stype::type first_value = static_cast<Stype::type>( first<T>::type::value );
    		static const Stype::type second_value = static_cast<Stype::type>( second<T>::type::value );
    
    		if( v1 == first_value && v2 == second_value ) compute< first_value, second_value >();
    	}
    
    private:
    	Stype::type v1, v2;
    };
    
    void compute_at_runtime( Stype::type t1, Stype::type t2 )
    {
    	using namespace boost::mpl;
    
    	typedef range_c< int, 0, int(Stype::size)*int(Stype::size) - 1 >	basic_set;
    	typedef transform_view< basic_set, pair<
    			divides< _1, int_< Stype::size > >, modulus<_1, int_< Stype::size > >
    		> >::type 							pairs;
    	typedef filter_view< pairs, less_equal< first<_1>, second<_1> > >	ordered_pairs;
    
    	for_each< ordered_pairs >( call_compute(t1,t2) );
    }

  7. #7
    Join Date
    Aug 2009
    Posts
    25

    Re: Problems with writing a metaprogram

    excellent! I did not know we can do such thing with a few boost::mpl code!

    I added the int main() below to the code and wanted to compile it but i get errors
    Code:
    int main(){
    Stype::type ts1 = Stype::T1;
    Stype::type ts2 = Stype::T3;
    compute_at_runtime( ts1, ts2 );
    }
    the error is:
    Code:
    mpl.cpp: In function ‘void compute_at_runtime(Stype::type, Stype::type)’:
    mpl.cpp:39: error: ‘less_equal’ was not declared in this scope
    mpl.cpp:39: error: wrong number of template arguments (3, should be 2)
    /usr/local/include/boost/mpl/filter_view.hpp:28: error: provided for ‘template<class Sequence, class Predicate> struct boost::mpl::filter_view’
    mpl.cpp:39: error: expected unqualified-id before ‘>’ token
    mpl.cpp:41: error: ‘ordered_pairs’ was not declared in this scope
    mpl.cpp:41: error: no matching function for call to ‘for_each(call_compute)’

  8. #8
    Join Date
    Oct 2008
    Posts
    1,456

    Re: Problems with writing a metaprogram

    oh sorry, one of the most difficult thing with mpl is guessing the right headers

    add "#include <boost/mpl/comparison.hpp>" and it should compile ( at least I just tryed on VC++2008 and it works ok ).

  9. #9
    Join Date
    Aug 2009
    Posts
    25

    Re: Problems with writing a metaprogram

    Yes it compiles now!
    Many thanks
    I should go and learn some mpl!

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured