generate structs with all combinations of members from a given struct
Hello, struct params { double field1; double field2; double field3; double fiedl4; }; I would like to generate all the types that hold any combination of the members of params. struct params_field1 { double field1; }; struct params_field2 { double field2; }; struct params_field3 { double field3; }; struct params_field4 { double field4; }; struct params_field1_field2 { double field1; double field2; }; struct params_field1_field3 { double field1; double field3; }; struct params_field1_field4 { double field1; double field4; }; struct params_field2_field3 { double field2; double field3; }; struct params_field2_field4 { double field2; double field4; }; struct params_field3_field4 { double field3; double field4; }; struct params_field1_field2_field3 { double field1; double field2; double field3; }; struct params_field1_field2_field4 { double field1; double field2; double field4; }; struct params_field1_field3_field4 { double field1; double field3; double field4; }; struct params_field2_field3_field4 { double field2; double field3; double field4; }; struct params_field1_field2_field3_field4 { double field1; double field2; double field3; double field4; }; There are 15 of these, which is 2^4 -1, where 4 is the number of members in params. Assuming params is adapted as a fusion sequence, this looks doable with PP? Should I be looking at BOOST_PP_LIST_FOLD_xxx macros? regards,
Hicham Mouline wrote:
Hello,
struct params { double field1; double field2; double field3; double fiedl4; };
I would like to generate all the types that hold any combination of the members of params.
Can't you like generate a fusion vector out of combination enumeration ? like having make_combo< params, vector_c<1,3,4> > ? sounds "sounder" than the macro. -- ___________________________________________ Joel Falcou - Assistant Professor PARALL Team - LRI - Universite Paris Sud XI Tel : (+33)1 69 15 66 35
On Fri, Jan 29, 2010 at 11:57 PM, joel falcou <joel.falcou@lri.fr> wrote:
Hicham Mouline wrote:
Hello, struct params { double field1; double field2; double field3; double fiedl4; }; I would like to generate all the types that hold any combination of the members of params.
Can't you like generate a fusion vector out of combination enumeration ?
like having make_combo< params, vector_c<1,3,4> >
?
sounds "sounder" than the macro.
Or make a fusion function called like permutation or so?
OvermindDL1 wrote:
Or make a fusion function called like permutation or so?
It's more than permuttion, it's combination but yeah that's the idea. -- ___________________________________________ Joel Falcou - Assistant Professor PARALL Team - LRI - Universite Paris Sud XI Tel : (+33)1 69 15 66 35
On Sat, Jan 30, 2010 at 12:35 AM, joel falcou <joel.falcou@lri.fr> wrote:
OvermindDL1 wrote:
Or make a fusion function called like permutation or so?
It's more than permuttion, it's combination but yeah that's the idea.
Er, yeah, whatever the word was, I have been up for near 24 hours. >.>
On 01/30/10 01:41, OvermindDL1 wrote:
On Sat, Jan 30, 2010 at 12:35 AM, joel falcou <joel.falcou@lri.fr> wrote:
OvermindDL1 wrote:
Or make a fusion function called like permutation or so?
It's more than permuttion, it's combination but yeah that's the idea.
Er, yeah, whatever the word was, I have been up for near 24 hours. >.>
The OP said:
There are 15 of these, which is 2^4 -1, where 4 is the number of members in params.
Isn't 2^4 - 1 the number of non-empty subsets of: {field1, field2, field3. field4} ? Now, for r fields, the number of combinations of r fields from a set of n fields is: C(n,r) = (n!/(r!(n-r)!) Summing up for r=1..n gives: C(n,1)+C(n,2)+...+C(n,n) which is 2^n-1 (according to a textbook of mine), as the OP claimed.
On 30 January 2010 06:57, joel falcou <joel.falcou@lri.fr> wrote:
Hicham Mouline wrote:
Hello, struct params { double field1; double field2; double field3; double fiedl4; }; I would like to generate all the types that hold any combination of the members of params.
Can't you like generate a fusion vector out of combination enumeration ?
like having make_combo< params, vector_c<1,3,4> >
You'd want a map, at least. Consider: template <typename T> void foo(T const& x) { x.field3 *= 2; } How would you translate that to take a vector, if 'field3' could be in different positions? But I've never used a fusion map so I don't know how you'd go about that. Here is are some macros to generate the necessary subsets. The main loop could be implement using a fold, but as there can't be more than 8 iterations it seemed easier to hard code it. Daniel #include <boost/preprocessor.hpp> #define SUBSETS(size, values) \ BOOST_PP_CAT(SUBSETS_, size) values #define SUBSETS_1(a1) ((a1)) #define SUBSETS_2(a1,a2) \ SUBSETS_COMBINE(a2, SUBSETS_1(a1)) #define SUBSETS_3(a1,a2,a3) \ SUBSETS_COMBINE(a3, SUBSETS_2(a1,a2)) #define SUBSETS_4(a1,a2,a3,a4) \ SUBSETS_COMBINE(a4, SUBSETS_3(a1,a2,a3)) #define SUBSETS_5(a1,a2,a3,a4,a5) \ SUBSETS_COMBINE(a5, SUBSETS_4(a1,a2,a3,a4)) #define SUBSETS_6(a1,a2,a3,a4,a5,a6) \ SUBSETS_COMBINE(a6, SUBSETS_5(a1,a2,a3,a4,a5)) #define SUBSETS_7(a1,a2,a3,a4,a5,a6,a7) \ SUBSETS_COMBINE(a7, SUBSETS_6(a1,a2,a3,a4,a5,a6)) #define SUBSETS_8(a1,a2,a3,a4,a5,a6,a7,a8) \ SUBSETS_COMBINE(a8, SUBSETS_7(a1,a2,a3,a4,a5,a6,a7)) #define SUBSETS_COMBINE(x, seq_seq) \ seq_seq \ ((x)) \ BOOST_PP_SEQ_FOR_EACH(SUBSETS_COMBINE_IMPL, x, seq_seq) #define SUBSETS_COMBINE_IMPL(r, elem, seq) \ (seq (elem)) // Example of use: SUBSETS(5, (field1, field2, field3, field4, field5))
On 01/30/10 00:37, Hicham Mouline wrote:
Hello,
struct params { double field1; double field2; double field3; double fiedl4; };
I would like to generate all the types that hold any combination of the members of params.
struct params_field1 { double field1; }; struct params_field2 { double field2; }; struct params_field3 { double field3; }; struct params_field4 { double field4; }; struct params_field1_field2 { double field1; double field2; }; struct params_field1_field3 { double field1; double field3; }; struct params_field1_field4 { double field1; double field4; }; struct params_field2_field3 { double field2; double field3; }; struct params_field2_field4 { double field2; double field4; }; struct params_field3_field4 { double field3; double field4; }; struct params_field1_field2_field3 { double field1; double field2; double field3; }; struct params_field1_field2_field4 { double field1; double field2; double field4; }; struct params_field1_field3_field4 { double field1; double field3; double field4; }; struct params_field2_field3_field4 { double field2; double field3; double field4; }; struct params_field1_field2_field3_field4 { double field1; double field2; double field3; double field4; };
There are 15 of these, which is 2^4 -1, where 4 is the number of members in params.
Assuming params is adapted as a fusion sequence, this looks doable with PP? Should I be looking at BOOST_PP_LIST_FOLD_xxx macros?
I think the following might work: step1: create sequence of fields: seq=(field1,field2,...,fieldn) step2: create a sequence of a sequence of fields by fold with pop_back: seq_fold= ( (field1,field2,....,fieldn) , (field1,field2,...,fieldn-1) ... , (field1) ) step3 form the cross product of seq_fold using code posted here: http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?CPPTM_Answers... or, if using variadic templates compiler is OK for you, in list_comprehension.cpp here: http://www.boostpro.com/vault/index.php?&directory=variadic_templates WARNING. I haven't tried this at all. but it seems it should work. HTH. -Larry
On 01/30/10 07:35, Larry Evans wrote: [snip]
I think the following might work:
step1: create sequence of fields: seq=(field1,field2,...,fieldn) step2: create a sequence of a sequence of fields by fold with pop_back: seq_fold= ( (field1,field2,....,fieldn) , (field1,field2,...,fieldn-1) ... , (field1) ) step3 form the cross product of seq_fold using code posted here:
[snip] Nope, it wouldn't work since the number of generated elements would be 4!, not the 2^4-1 required in the OP. Sorry for noise. -Larry
On 01/30/10 00:37, Hicham Mouline wrote:
Hello,
struct params { double field1; double field2; double field3; double fiedl4; };
I would like to generate all the types that hold any combination of the members of params. [snip]
Step1: Create cross-product of void and {field1,field2,...}. This will produce a sequence of pairs: no_yes = ( (void,field1) , (void,field2) ... , (void,fieldn) ) Step2: Create the crosss product of all rows in no_yes. cross_no_yes = ( (void,void,..void) , (field1,void,...void) , (void,field2,void...,void) ... , (field1,field2,...fieldn) ) step3: remove all the voids in all the rows of cross_no_yes. Since the size<no_yes> == n and each element in that row is size 2, the cross_no_yes size would be 2^n. Then simply rm the all void row. Not tested.
On 01/30/10 13:35, Larry Evans wrote:
On 01/30/10 00:37, Hicham Mouline wrote:
Hello,
struct params { double field1; double field2; double field3; double fiedl4; };
I would like to generate all the types that hold any combination of the members of params. [snip]
Step1: Create cross-product of void and {field1,field2,...}. This will produce a sequence of pairs:
no_yes = ( (void,field1) , (void,field2) ... , (void,fieldn) )
Step2:
Create the crosss product of all rows in no_yes.
cross_no_yes = ( (void,void,..void) , (field1,void,...void) , (void,field2,void...,void) ... , (field1,field2,...fieldn) )
step3:
remove all the voids in all the rows of cross_no_yes.
Since the size<no_yes> == n and each element in that row is size 2, the cross_no_yes size would be 2^n. Then simply rm the all void row.
Not tested. Now tested. The attached produces:
/home/evansl/prog_dev/boost-svn/ro/trunk/sandbox-local/build/gcc4_4v/sandbox/variadic_templates/libs/mpl/sandbox/list_comprehension~subsets.exe absent_fields_seq= ( Absent=9000, Field=9001) ( Absent=9000, Field=9002) ( Absent=9000, Field=9003) size<select_fields_seq>::value=8 select_fields_seq= { 9000, 9000, 9000} { 9000, 9000, 9003} { 9000, 9002, 9000} { 9000, 9002, 9003} { 9001, 9000, 9000} { 9001, 9000, 9003} { 9001, 9002, 9000} { 9001, 9002, 9003} Compilation finished at Sat Jan 30 18:17:41 9000 indicates absence of a field. 900I, for I>0, indicates presence of the I-th field. HTH. -regards, Larry
----- Original Message ----- From: "Larry Evans" <cppljevans@suddenlink.net> To: <boost-users@lists.boost.org> Sent: Sunday, January 31, 2010 2:35 AM Subject: Re: [Boost-users] generate structs with all combinations of members from a given struct
On 01/30/10 00:37, Hicham Mouline wrote:
Hello, struct params { double field1; double field2; double field3; double fiedl4; }; I would like to generate all the types that hold any combination of the members of params. [snip]
Step1: Create cross-product of void and {field1,field2,...}. This will produce a sequence of pairs:
no_yes = ( (void,field1) , (void,field2) ... , (void,fieldn) )
Step2:
Create the crosss product of all rows in no_yes.
cross_no_yes = ( (void,void,..void) , (field1,void,...void) , (void,field2,void...,void) ... , (field1,field2,...fieldn) )
step3:
remove all the voids in all the rows of cross_no_yes.
Since the size<no_yes> == n and each element in that row is size 2, the cross_no_yes size would be 2^n. Then simply rm the all void row.
Not tested. I will try this thanks very much.
I will make all these types derived from a base struct with a virtual dtor. Then I will move this base type around various translation units (so they only need to know about the base struct), and then the last translation unit will have access to the same list of types and then dynamic cast the base struct to each of these generated structs and work with the actual type. I thought of generation a fusion vector as well but the resulting vector would look like this: vector< vector<double>, vector<double>, vector<double>, vector<double>, vector<double,double>, ...
Because all the members of params are double, there is no way to differentiate between different the 1st and 2nd vector<double> while with PP, I could name the types params_field1 and params_field2, regards,
On 01/31/10 07:20, Hicham Mouline wrote: [snip]
Step1: Create cross-product of void and {field1,field2,...}. This will produce a sequence of pairs:
no_yes = ( (void,field1) , (void,field2) ... , (void,fieldn) )
Step2:
Create the crosss product of all rows in no_yes.
cross_no_yes = ( (void,void,..void) , (field1,void,...void) , (void,field2,void...,void) ... , (field1,field2,...fieldn) )
step3:
remove all the voids in all the rows of cross_no_yes.
Since the size<no_yes> == n and each element in that row is size 2, the cross_no_yes size would be 2^n. Then simply rm the all void row.
Not tested. [snip]
My previous attachment could be simplified by using: template < typename Domains
struct cross_product_fold : fold < Domains , cross_prod_nil , cross_product<arg<1>, arg<2> >
{ }; typedef cross_product_fold < package<absent_t,fields_t>
::type absent_fields_seq ; typedef cross_product_fold < absent_fields_seq ::type select_fields_seq ; I will try this thanks very much.
I will make all these types derived from a base struct with a virtual dtor. Then I will move this base type around various translation units (so they only need to know about the base struct), and then the last translation unit will have access to the same list of types and then dynamic cast the base struct to each of these generated structs and work with the actual type.
I thought of generation a fusion vector as well but the resulting vector would look like this:
vector< vector<double>, vector<double>, vector<double>, vector<double>, vector<double,double>, ...
Because all the members of params are double, there is no way to differentiate between different the 1st and 2nd vector<double>
Yes; however, Couldn't you, pair each type with it's index? IOW, you have, instead of: typedef package_c<int,9001,9002,9003>::pkg_type fields_t ; from my earlier attachment, you have: enum field_names { field_1 , field_2 ... , field_n }; typedef package < pair<integral_c<field_names,field_1>, vector<double> > , pair<integral_c<field_names,field_2>, vector<double> > ... , pair<integral_c<field_names,field_I>, vector<double,double> > ... > fields_t ; Then, the resulting cross_product would be a sequence of pairs from which you could generate a fusion map.
while with PP, I could name the types params_field1 and params_field2,
The aforementioned fusion map would have keys like integral_c<field_names,field_I>, for I=1,N. You could always write a short template: template<field_names FieldName> obvious_type_from_map_meta_function? get_field(afore_mentioned_map) ; to more conveniently access the named field. HTH. Larry
On 01/31/10 08:12, Larry Evans wrote:
On 01/31/10 07:20, Hicham Mouline wrote: [snip]
Because all the members of params are double, there is no way to differentiate between different the 1st and 2nd vector<double>
Yes; however, Couldn't you, pair each type with it's index? IOW, you have, instead of:
typedef package_c<int,9001,9002,9003>::pkg_type fields_t ;
from my earlier attachment, you have:
enum field_names { field_1 , field_2 ... , field_n }; typedef package < pair<integral_c<field_names,field_1>, vector<double> > , pair<integral_c<field_names,field_2>, vector<double> > ... , pair<integral_c<field_names,field_I>, vector<double,double> > ... > fields_t ;
Then, the resulting cross_product would be a sequence of pairs from which you could generate a fusion map. [snip]
Such a sequence of sequence of fusion::pair's is generated by the attached. Generating a fusion map from a sequence of fusion::pairs has not been done. I didn't see any hint here: http://www.boost.org/doc/libs/1_41_0/libs/fusion/doc/html/fusion/container/g... about how to do that. Output from attached is: --{--output-- absent_fields_seq= ( name=1, type=1) ( name=2, type=2) ( name=3, type=1) size<select_fields_seq>::value=8 select_fields_seq= { absent , absent , absent } { absent , absent , ( name= 3, type= 1) } { absent , ( name= 2, type= 2) , absent } { absent , ( name= 2, type= 2) , ( name= 3, type= 1) } { ( name= 1, type= 1) , absent , absent } { ( name= 1, type= 1) , absent , ( name= 3, type= 1) } { ( name= 1, type= 1) , ( name= 2, type= 2) , absent } { ( name= 1, type= 1) , ( name= 2, type= 2) , ( name= 3, type= 1) } rm_absent_seq= { } { ( name= 3, type= 1) } { ( name= 2, type= 2) } { ( name= 2, type= 2) , ( name= 3, type= 1) } { ( name= 1, type= 1) } { ( name= 1, type= 1) , ( name= 3, type= 1) } { ( name= 1, type= 1) , ( name= 2, type= 2) } { ( name= 1, type= 1) , ( name= 2, type= 2) , ( name= 3, type= 1) } --}--output--
----- Original Message ----- From: "Larry Evans" <cppljevans@suddenlink.net> To: <boost-users@lists.boost.org> Sent: Monday, February 01, 2010 1:03 AM Subject: Re: [Boost-users] generate structs with all combinations of members from a given struct Hello, Larry thanks for all the answers. I have a little trouble following your trail of thoughts, especially step 2, but let me reread your posts a couple of times more to get it right. I think your solution is rather build more solutions than required then remove those which are not a "combination" in the mathematical sense. It may cause problems when my structs have more than 15 members in which case we may be working with 15! to get back to 2^15 -1 again, let me reread your posts first. In the meantime, I have written the pure runtime version of the problem which is in fact like a tree recursive descent problem.(I think), this builds and runs correctly but doesn't deal with the identical types and member names. #include <iostream> #include <list> typedef std::list< std::list<size_t> > main_list_t; void combinations(main_list_t& m, const size_t* arr, size_t arrsize) { if (arrsize==0) return; if (m.empty()) { std::list<size_t> l; l.push_back( arr[0] ); m.push_back(l); } else { std::list<size_t> l( m.back() ); l.push_back( arr[0] ); m.push_back( l ); } combinations(m, arr+1, arrsize-1); } int main() { const size_t arr[] = { 1, 2, 3, 4, 5 }; const size_t arrsize = sizeof(arr)/sizeof(size_t); main_list_t m[arrsize]; for (size_t s=0; s<arrsize; ++s) combinations(m[s], &arr[s], arrsize-s); main_list_t mm; for (size_t s=0; s<arrsize; ++s) mm.insert(mm.end(), m[s].begin(), m[s].end()); for (main_list_t::const_iterator i = mm.begin(); i!=mm.end(); ++i) { const std::list<size_t>& l = *i; for (std::list<size_t>::const_iterator ii = l.begin(); ii!=l.end(); ++ii) { std::cout<< *ii << '\t'; } std::cout<<std::endl; } } I will try to build a Boost.PP version of this runtime, with PP lists I think, and finally I will have your mpl version to compare the 2. Unfortunately, I'll have to use MSVC2008 so I don't think variadic templates are usable, but I'm sure your solution can work without variadic templates. Again, thank you very much,
-----Original Message----- From: boost-users-bounces@lists.boost.org [mailto:boost-users- bounces@lists.boost.org] On Behalf Of Larry Evans Sent: 31 January 2010 18:04 To: boost-users@lists.boost.org Subject: Re: [Boost-users] generate structs with all combinations of members from a given struct
[snip]
Because all the members of params are double, there is no way to differentiate between different the 1st and 2nd vector<double>
Yes; however, Couldn't you, pair each type with it's index? IOW, you have, instead of:
typedef package_c<int,9001,9002,9003>::pkg_type fields_t ;
Larry, I have finally reached a Boost.PP based solution which I describe below. I will then go back to your fusion-based solution. My point is to compare compile-time, memory requirement of the compiler and ease of use of the generated types. Here is my solution (the attached files compiles and preprocesses at least under g++4.4 with: g++ -E -c structcombos.cpp). With struct S { int m1; double m2; double m3; }; the user is required to define the macro #define struct_members_seq ((int,m1))((double,m2))((double,m3)) then calls the macro STRUCT_MEMBERS_COMBINATIONS_SEQ(struct_members_seq) This expands to struct params_m3 { double m3; }; struct params_m2 { double m2; }; struct params_m2_m3 { double m2; double m3; }; struct params_m1 { int m1; }; struct params_m1_m3 { int m1; double m3; }; struct params_m1_m2 { int m1; double m2; }; struct params_m1_m2_m3 { int m1; double m2; double m3; }; Questions: 1. It takes a little while to preprocess. Are there optimizations that are visible in the attached file? 2. How do I obtain some vertical appearance that is easier to read? Can I generate the newline somehow? Regards,
Hicham Mouline wrote:
Questions: 1. It takes a little while to preprocess. Are there optimizations that are visible in the attached file? 2. How do I obtain some vertical appearance that is easier to read? Can I generate the newline somehow?
Look at BOOST_PP_ITERATE. It'll give you the "vertical" feeling and may end up a bit faster. -- ___________________________________________ Joel Falcou - Assistant Professor PARALL Team - LRI - Universite Paris Sud XI Tel : (+33)1 69 15 66 35
-----Original Message----- From: boost-users-bounces@lists.boost.org [mailto:boost-users- bounces@lists.boost.org] On Behalf Of Daniel James Sent: 06 February 2010 18:36 To: boost-users@lists.boost.org Subject: Re: [Boost-users] generate structs with all combinations of members from a given struct
On 6 February 2010 18:06, Hicham Mouline <hicham@mouline.org> wrote:
Questions: 1. It takes a little while to preprocess. Are there optimizations that
are
visible in the attached file?
You forgot to attach it.
Daniel Indeed :-) Apologies. Attached now,
Thanks,
On 6 February 2010 19:42, Hicham Mouline <hicham@mouline.org> wrote:
Attached now,
The code I posted for getting the subsets before should be faster, here it is adapted for sequences: #include <boost/preprocessor.hpp> ///////////////////////////////////////////////////////////////////// // Generates the non-empty subsets of a sequence #define SUBSETS(values) \ SUBSETS2(BOOST_PP_SEQ_SIZE(values), \ BOOST_PP_SEQ_TO_TUPLE(values)) #define SUBSETS2(size, values) \ BOOST_PP_CAT(SUBSETS_, size) values #define SUBSETS_1(a1) ((a1)) #define SUBSETS_2(a1,a2) \ SUBSETS_COMBINE(a2, SUBSETS_1(a1)) #define SUBSETS_3(a1,a2,a3) \ SUBSETS_COMBINE(a3, SUBSETS_2(a1,a2)) #define SUBSETS_4(a1,a2,a3,a4) \ SUBSETS_COMBINE(a4, SUBSETS_3(a1,a2,a3)) #define SUBSETS_5(a1,a2,a3,a4,a5) \ SUBSETS_COMBINE(a5, SUBSETS_4(a1,a2,a3,a4)) #define SUBSETS_6(a1,a2,a3,a4,a5,a6) \ SUBSETS_COMBINE(a6, SUBSETS_5(a1,a2,a3,a4,a5)) #define SUBSETS_7(a1,a2,a3,a4,a5,a6,a7) \ SUBSETS_COMBINE(a7, SUBSETS_6(a1,a2,a3,a4,a5,a6)) #define SUBSETS_8(a1,a2,a3,a4,a5,a6,a7,a8) \ SUBSETS_COMBINE(a8, SUBSETS_7(a1,a2,a3,a4,a5,a6,a7)) #define SUBSETS_COMBINE(x, seq_seq) \ seq_seq \ ((x)) \ BOOST_PP_SEQ_FOR_EACH(SUBSETS_COMBINE_IMPL, x, seq_seq) #define SUBSETS_COMBINE_IMPL(r, elem, seq) \ (seq (elem)) ///////////////////////////////////////////////////////////////////// // Example of use: SUBSETS( ((char, field1)) ((float, field2)) ((std::string, field3)) ((int, field4)) )
-----Original Message----- From: boost-users-bounces@lists.boost.org [mailto:boost-users- bounces@lists.boost.org] On Behalf Of Daniel James Sent: 06 February 2010 20:51 To: boost-users@lists.boost.org Subject: Re: [Boost-users] generate structs with all combinations of members from a given struct
On 6 February 2010 19:42, Hicham Mouline <hicham@mouline.org> wrote:
Attached now,
The code I posted for getting the subsets before should be faster, here it is adapted for sequences:
Brilliant! Your code is a lot faster. I adapted it to generate the structs. #include <boost/preprocessor.hpp> ///////////////////////////////////////////////////////////////////// // Generates the non-empty subsets of a sequence #define STATEMENT_FROM_PAIR(pair) BOOST_PP_TUPLE_ELEM(2,0,pair) BOOST_PP_TUPLE_ELEM(2,1,pair); #define PRED(r,state) BOOST_PP_SEQ_SIZE(state) #define OP(r,state) BOOST_PP_SEQ_POP_FRONT(state) #define MACRO(r,state) STATEMENT_FROM_PAIR(BOOST_PP_SEQ_HEAD(state)) #define PRED1(r,state) BOOST_PP_SEQ_SIZE(BOOST_PP_TUPLE_ELEM(2,0,state)) #define OP1(r,state) (BOOST_PP_SEQ_POP_FRONT(BOOST_PP_TUPLE_ELEM(2,0,state)),\ BOOST_PP_CAT(\ BOOST_PP_TUPLE_ELEM(2,1,state),\ BOOST_PP_CAT(\ _,\ BOOST_PP_TUPLE_ELEM(2,1,\ BOOST_PP_SEQ_HEAD(BOOST_PP_TUPLE_ELEM(2,0,state))\ )\ )\ )\ ) #define MAKE_STRUCT(r,data,elem) struct BOOST_PP_TUPLE_ELEM(2,1,BOOST_PP_WHILE(PRED1,OP1,(elem,data))) \ { BOOST_PP_FOR(elem, PRED, OP, MACRO) }; #define SUBSETS(struct_name,values) BOOST_PP_SEQ_FOR_EACH(MAKE_STRUCT, struct_name, SUBSETS2(BOOST_PP_SEQ_SIZE(values), BOOST_PP_SEQ_TO_TUPLE(values))) #define SUBSETS2(size, values) BOOST_PP_CAT(SUBSETS_, size) values #define SUBSETS_1(a1) ((a1)) #define SUBSETS_2(a1,a2) SUBSETS_COMBINE(a2, SUBSETS_1(a1)) #define SUBSETS_3(a1,a2,a3) SUBSETS_COMBINE(a3, SUBSETS_2(a1,a2)) #define SUBSETS_4(a1,a2,a3,a4) SUBSETS_COMBINE(a4, SUBSETS_3(a1,a2,a3)) #define SUBSETS_5(a1,a2,a3,a4,a5) SUBSETS_COMBINE(a5, SUBSETS_4(a1,a2,a3,a4)) #define SUBSETS_6(a1,a2,a3,a4,a5,a6) SUBSETS_COMBINE(a6, SUBSETS_5(a1,a2,a3,a4,a5)) #define SUBSETS_7(a1,a2,a3,a4,a5,a6,a7) SUBSETS_COMBINE(a7, SUBSETS_6(a1,a2,a3,a4,a5,a6)) #define SUBSETS_8(a1,a2,a3,a4,a5,a6,a7,a8) SUBSETS_COMBINE(a8, SUBSETS_7(a1,a2,a3,a4,a5,a6,a7)) #define SUBSETS_COMBINE(x, seq_seq) \ seq_seq \ ((x)) \ BOOST_PP_SEQ_FOR_EACH(SUBSETS_COMBINE_IMPL, x, seq_seq) #define SUBSETS_COMBINE_IMPL(r, elem, seq) (seq (elem)) ///////////////////////////////////////////////////////////////////// // Example of use: SUBSETS( params, ((char, field1)) ((float, field2)) ((std::string, field3)) ((int, field4)) ) ///generates this /// struct params_field1 { char field1; }; struct params_field2 { float field2; }; struct params_field1_field2 { char field1; float field2; }; struct params_field3 { std::string field3; }; struct params_field1_field3 { char field1; std::string field3; }; struct params_field2_field3 { float field2; std::string field3; }; struct params_field1_field2_field3 { char field1; float field2; std::string field3; }; struct params_field4 { int field4; }; struct params_field1_field4 { char field1; int field4; }; struct params_field2_field4 { float field2; int field4; }; struct params_field1_field2_field4 { char field1; float field2; int field4; }; struct params_field3_field4 { std::string field3; int field4; }; struct params_field1_field3_field4 { char field1; std::string field3; int field4; }; struct params_field2_field3_field4 { float field2; std::string field3; int field4; }; struct params_field1_field2_field3_field4 { char field1; float field2; std::string field3; int field4; }; How do I use BOOST_PP_ITERATE to get vertical output of the structs, ie, each struct on a different line? Thanks,
On 02/06/10 12:06, Hicham Mouline wrote: [snip]
Larry,
I have finally reached a Boost.PP based solution which I describe below. I will then go back to your fusion-based solution. My point is to compare compile-time, memory requirement of the compiler and ease of use of the generated types.
Here is my solution (the attached files compiles and preprocesses at least under g++4.4 with: g++ -E -c structcombos.cpp).
With
struct S { int m1; double m2; double m3; };
the user is required to define the macro
#define struct_members_seq ((int,m1))((double,m2))((double,m3))
then calls the macro
STRUCT_MEMBERS_COMBINATIONS_SEQ(struct_members_seq)
This expands to struct params_m3 { double m3; }; struct params_m2 { double m2; }; struct params_m2_m3 { double m2; double m3; }; struct params_m1 { int m1; }; struct params_m1_m3 { int m1; double m3; }; struct params_m1_m2 { int m1; double m2; }; struct params_m1_m2_m3 { int m1; double m2; double m3; };
My *intuition* as well as posts from others (e.g. Joel Guzman and Eric Niebler) and a proto webpage: http://www.boost.org/doc/libs/1_41_0/doc/html/proto/appendices.html#boost_pr... suggests this PP method would be faster than the fusion-based solution. However, I've been wondering how you would use this. I suspect it's related to spirit's permutation: m1_tok ^ m2_tok ^ m3_tok where, using the notation from: http://www.boost.org/doc/libs/1_41_0/libs/spirit/doc/html/spirit/qi/referenc... m1_tok:int, m2_tok:double, m3_tok:double --> (m1_tok^m2_tok^m3_tok):params_subset where: typedef tuple < optional<int> //corresponding to S::m1 , optional<double>//corresponding to S::m2 , optional<double>//corresponding to S::m3 > params_subset; and maybe you were planning on somehow converting the params_subset attribute to one of the structures generated by TRUCT_MEMBERS_COMBINATIONS_SEQ(struct_members_seq). Is that your aim?
Questions:
Sorry, I don't know enough to answer any of these questions :(.
-----Original Message----- From: boost-users-bounces@lists.boost.org [mailto:boost-users- bounces@lists.boost.org] On Behalf Of Larry Evans Sent: 06 February 2010 19:26 To: boost-users@lists.boost.org Subject: Re: [Boost-users] generate structs with all combinations of members from a given struct
On 02/06/10 12:06, Hicham Mouline wrote: [snip] My *intuition* as well as posts from others (e.g. Joel Guzman and Eric Niebler) and a proto webpage:
http://www.boost.org/doc/libs/1_41_0/doc/html/proto/appendices.html#boos t_proto.appendices.rationale
suggests this PP method would be faster than the fusion-based solution.
However, I've been wondering how you would use this.
Starting from struct S { type1 field1; ... typen fieldn; /// for now n=6 but may increase later }; all types are either int, unsigned int, long, double or bool. The PP code generates all the structs like struct S_field1_field5 { type1 field1; type5 field5; }; For each of these structs, we have the related type multi_array<S_field1_field5, M> an M-dimension array the elements of which are 1 of the generated structs. M can reach the order of 10, and the number of elements of the multi array can be quite large, therefore it is important to generate a multi_array that is as accurate as possible. The user selects at runtime which fields she is interested in, this then fills in a bitset<n>. At runtime we then select the multi_array we will work with. I will find a way to adapt all of the multi_arrays to be derived from a multi_array_base via some wrapper. struct multi_array_base { virtual ~ multi_array_base(); }; I have say 5 translation units tr1,tr2,tr3,tr4 and tr5. The specific multi_array is generated in tr1. It needs to pass via tr2,tr3 and tr4 to reach tr5. tr2,3 and 4 do not need to know what exact multi_array type it is, so they just deal with multi_array_base. tr5 then dynamic casts the multi_array_base ref to the appropriate multi_array with the appropriate S. pseudo_code tr1, itself geenrate switch( bitset.toulong() ) { case 1: some_function( multi_array_adapted_to_derive_from_base<appropriate_S, appropriate_M>& ); case 2: some_function( multi_array_adapted_to_derive_from_base<appropriate_S, appropriate_M>& ); .... case 63: some_function( multi_array_adapted_to_derive_from_base<appropriate_S, appropriate_M>& ); } This is still work in progress. Regards,
On 02/07/10 09:03, Hicham Mouline wrote:
-----Original Message----- From: boost-users-bounces@lists.boost.org [mailto:boost-users- bounces@lists.boost.org] On Behalf Of Larry Evans Sent: 06 February 2010 19:26 [snip]
However, I've been wondering how you would use this.
Starting from
struct S { type1 field1; ... typen fieldn; /// for now n=6 but may increase later }; [snip] The PP code generates all the structs like
struct S_field1_field5 { type1 field1; type5 field5; };
For each of these structs, we have the related type multi_array<S_field1_field5, M> an M-dimension array the elements of which are 1 of the generated structs. M can reach the order of 10, and the number of elements of the multi array can be quite large, therefore it is important to generate a multi_array that is as accurate as possible.
The user selects at runtime which fields she is interested in, this then fills in a bitset<n>. At runtime we then select the multi_array we will work with.
I will find a way to adapt all of the multi_arrays to be derived from a multi_array_base via some wrapper. struct multi_array_base { virtual ~ multi_array_base(); };
Hmmm. What about multi_array_base being the S_empty: struct S_empty{}; IOW, this would be the 32nd version of S. Your PP method now generates 31 versions, you could just add the 32 version be S_empty. This makes sense because each time a field is added, it's like a derived class. IOW, S_empty would be the base class, and all other classes would be derived from it. I vaguely remember reading about that somewhere, IOW, that adding a field to a class is sorta like restricting the class is sorta like deriving from that class.
I have say 5 translation units tr1,tr2,tr3,tr4 and tr5.
The specific multi_array is generated in tr1. It needs to pass via tr2,tr3 and tr4 to reach tr5. tr2,3 and 4 do not need to know what exact multi_array type it is, so they just deal with multi_array_base. tr5 then dynamic casts the multi_array_base ref to the appropriate multi_array with the appropriate S.
pseudo_code tr1, itself geenrate switch( bitset.toulong() ) { case 1: some_function( multi_array_adapted_to_derive_from_base<appropriate_S, appropriate_M>& ); case 2: some_function( multi_array_adapted_to_derive_from_base<appropriate_S, appropriate_M>& ); .... case 63: some_function( multi_array_adapted_to_derive_from_base<appropriate_S, appropriate_M>& ); }
This is still work in progress.
I'd be interesting in seeing this code when you're done with it. I'd like to try using: composite_tagged_seq < all_of_aligned , field_I1 , field_I2 ... , field_In
where field_I1...field_In is some subset of S::field1,...field5 and composite_tagged is from composite_tagged_seq.zip in the boost vault: http://www.boostpro.com/vault/index.php?&directory=Data Structures Then compare the compile-time and run-time performance. I've no doubt it would be slower than the PP version, but I'm just curious about how much. -regards, Larry
-----Original Message----- From: boost-users-bounces@lists.boost.org [mailto:boost-users- bounces@lists.boost.org] On Behalf Of Larry Evans Sent: 09 February 2010 18:11 To: boost-users@lists.boost.org Subject: Re: [Boost-users] generate structs with all combinations of members from a given struct
Hmmm. What about multi_array_base being the S_empty:
struct S_empty{};
IOW, this would be the 32nd version of S. Your PP method now generates 31 versions, you could just add the 32 version be S_empty.
This makes sense because each time a field is added, it's like a derived class. IOW, S_empty would be the base class, and all other classes would be derived from it. I vaguely remember reading about that somewhere, IOW, that adding a field to a class is sorta like restricting the class is sorta like deriving from that class. It's not the Ss themselves that I need to derive from a base class to transport through translation units. It's boost::multi_array<S_..., N> that I need to transport anonymously. And that is why I wrap the multi_array in a struct that derives from multi_array_base.
I have say 5 translation units tr1,tr2,tr3,tr4 and tr5.
The specific multi_array is generated in tr1. It needs to pass via tr2,tr3 and tr4 to reach tr5. tr2,3 and 4 do not need to know what exact multi_array type it is, so they just deal with multi_array_base. tr5 then dynamic casts the multi_array_base ref to the appropriate multi_array with the appropriate S.
pseudo_code tr1, itself geenrate switch( bitset.toulong() ) { case 1: some_function( multi_array_adapted_to_derive_from_base<appropriate_S, appropriate_M>& ); case 2: some_function( multi_array_adapted_to_derive_from_base<appropriate_S, appropriate_M>& ); .... case 63: some_function( multi_array_adapted_to_derive_from_base<appropriate_S, appropriate_M>& ); }
This is still work in progress.
I'd be interesting in seeing this code when you're done with it. I'd like to try using:
composite_tagged_seq < all_of_aligned , field_I1 , field_I2 ... , field_In
where field_I1...field_In is some subset of S::field1,...field5 and composite_tagged is from composite_tagged_seq.zip in the boost vault:
http://www.boostpro.com/vault/index.php?&directory=Data Structures
Then compare the compile-time and run-time performance. I've no doubt it would be slower than the PP version, but I'm just curious about how much.
-regards, Larry I will definitely compare as well once I understand what you mean.
I have another problem for now. PP processing is starting to be slow, I need help to optimize it. Attached in the PP code. Also, in the above, all the Ss need to be generated only once. However, in multi_array<S..., N>, the N depends on the translation unit. I will have like 100 translation units, each with a different N. If I were to include the PP code to generate the Ss in each of the 100 trs, it would repeat the preprocessing uselessly. I need to run the first part of the PP just once, then the 2nd part of the PP that generates the multi_arrays for each of the 100 tr units. Is this possible? Regards,
On 02/09/10 16:12, Hicham Mouline wrote: [snip]
I have another problem for now.
PP processing is starting to be slow, I need help to optimize it. Attached in the PP code.
Also, in the above, all the Ss need to be generated only once. However, in multi_array<S..., N>, the N depends on the translation unit. I will have like 100 translation units, each with a different N.
If I were to include the PP code to generate the Ss in each of the 100 trs, it would repeat the preprocessing uselessly. I need to run the first part of the PP just once, then the 2nd part of the PP that generates the multi_arrays for each of the 100 tr units.
Is this possible?
What about precompiled headers? Microsoft provides them: http://msdn.microsoft.com/en-us/library/szfdksca(VS.71).aspx as well as gcc: http://gcc.gnu.org/onlinedocs/gcc/Precompiled-Headers.html HTH. -Larry
-----Original Message----- From: boost-users-bounces@lists.boost.org [mailto:boost-users- bounces@lists.boost.org] On Behalf Of Larry Evans Sent: 10 February 2010 13:10 To: boost-users@lists.boost.org Subject: Re: [Boost-users] generate structs with all combinations of members from a given struct
On 02/09/10 16:12, Hicham Mouline wrote: [snip]
I have another problem for now.
What about precompiled headers? Microsoft provides them:
http://msdn.microsoft.com/en-us/library/szfdksca(VS.71).aspx
as well as gcc:
http://gcc.gnu.org/onlinedocs/gcc/Precompiled-Headers.html
HTH.
-Larry
Ah yes, I will look into that, gcc and msvc are the only 2 compilers I use anyways, thanks, Daniel, in the attached file in http://lists.boost.org/boost-users/2010/02/56100.php, in line 69, I am generating the struct name with a BOOST_PP_WHILE invocation, I then need to reuse the struct name to define a constructor for the struct, so I reinvoke the BOOST_PP_WHILE. Clearly, this is wasted reprocessing, but I don't see how to avoid it. Actually, it's not the struct constructor I need to write, but the assignment operator instead. The 2nd question is how to generate the struct definition including the operator= on multiple lines instead of just 1. Here is an example of the generation at work struct S { double d1; int i2; long l3; }; 1 of the 7 structs generated will look like struct S_i2_l3 { S_i2_l3& operator=( const S& rhs ) { i2 = rhs.i2; l3 = rhs.l3; } int i2; long l3; }; All the S_s should be generated just once ( I will look at precompiled headers for this ) Later on, I PP-generate these types typedef boost::multi_array<S_i2_l3, 5> multi_array_i2_l3; //// The 5 may be different for each of the 100 translation units because this multiarray may be very large (possibly millions of cells) it is useful to optimize the memory footprint. Had I indiscriminately used boost::multi_array<S,5>, and just filled/read from the S cells just the relevant fields, I would be wasting memory. Thanks,
On 02/09/10 16:12, Hicham Mouline wrote:
-----Original Message----- From: boost-users-bounces@lists.boost.org [mailto:boost-users- bounces@lists.boost.org] On Behalf Of Larry Evans Sent: 09 February 2010 18:11 To: boost-users@lists.boost.org Subject: Re: [Boost-users] generate structs with all combinations of members from a given struct [snip] I'd be interesting in seeing this code when you're done with it. I'd like to try using:
composite_tagged_seq < all_of_aligned , field_I1 , field_I2 ... , field_In
where field_I1...field_In is some subset of S::field1,...field5 and composite_tagged is from composite_tagged_seq.zip in the boost vault:
http://www.boostpro.com/vault/index.php?&directory=Data Structures
Then compare the compile-time and run-time performance. I've no doubt it would be slower than the PP version, but I'm just curious about how much.
The attached shows a test driver using composite_tagged_seq. The composite_tagged_seq used is a bit different than the one in vault. The one used modified layout to handle the case where the type was void. In this case, not project template function for a void member is produced. The fields_subsets_t time contains 32 members, 1 for each subset of 5 fields. However, as shown in the driver, you have to access the field with: field_subset_struct.project<FieldNum>(); The compile time was slow (maybe 10-20 secs) on my machine, but that sounds a lot faster than you PP method. If you think you can use this, I'll upload the code to the sandbox. -regards, Larry BTW, the output is: /home/evansl/prog_dev/boost-svn/ro/trunk/sandbox-local/build/gcc4_4v/sandbox/variadic_templates/libs/mpl/sandbox/composite_tagged~field_subsets~cross_product_pack.exe absent_fields_seq= package< absent_tag, type=1> package< absent_tag, type=2> package< absent_tag, type=3> package< absent_tag, type=4> package< absent_tag, type=5> size<select_fields_seq>::value=32 select_fields_seq= { absent , absent , absent , absent , absent } { absent , absent , absent , absent , ( type= 5) } { absent , absent , absent , ( type= 4) , absent } { absent , absent , absent , ( type= 4) , ( type= 5) } { absent , absent , ( type= 3) , absent , absent } { absent , absent , ( type= 3) , absent , ( type= 5) } { absent , absent , ( type= 3) , ( type= 4) , absent } { absent , absent , ( type= 3) , ( type= 4) , ( type= 5) } { absent , ( type= 2) , absent , absent , absent } { absent , ( type= 2) , absent , absent , ( type= 5) } { absent , ( type= 2) , absent , ( type= 4) , absent } { absent , ( type= 2) , absent , ( type= 4) , ( type= 5) } { absent , ( type= 2) , ( type= 3) , absent , absent } { absent , ( type= 2) , ( type= 3) , absent , ( type= 5) } { absent , ( type= 2) , ( type= 3) , ( type= 4) , absent } { absent , ( type= 2) , ( type= 3) , ( type= 4) , ( type= 5) } { ( type= 1) , absent , absent , absent , absent } { ( type= 1) , absent , absent , absent , ( type= 5) } { ( type= 1) , absent , absent , ( type= 4) , absent } { ( type= 1) , absent , absent , ( type= 4) , ( type= 5) } { ( type= 1) , absent , ( type= 3) , absent , absent } { ( type= 1) , absent , ( type= 3) , absent , ( type= 5) } { ( type= 1) , absent , ( type= 3) , ( type= 4) , absent } { ( type= 1) , absent , ( type= 3) , ( type= 4) , ( type= 5) } { ( type= 1) , ( type= 2) , absent , absent , absent } { ( type= 1) , ( type= 2) , absent , absent , ( type= 5) } { ( type= 1) , ( type= 2) , absent , ( type= 4) , absent } { ( type= 1) , ( type= 2) , absent , ( type= 4) , ( type= 5) } { ( type= 1) , ( type= 2) , ( type= 3) , absent , absent } { ( type= 1) , ( type= 2) , ( type= 3) , absent , ( type= 5) } { ( type= 1) , ( type= 2) , ( type= 3) , ( type= 4) , absent } { ( type= 1) , ( type= 2) , ( type= 3) , ( type= 4) , ( type= 5) } no_f1_v.F_2=field_type=2 no_f1_v.F_3=field_type=3 Compilation finished at Sun Feb 14 13:59:27
-----Original Message----- From: boost-users-bounces@lists.boost.org [mailto:boost-users- bounces@lists.boost.org] On Behalf Of Larry Evans Sent: 09 February 2010 18:11 To: boost-users@lists.boost.org Subject: Re: [Boost-users] generate structs with all combinations of members from a given struct
Hello I have finished the generate with PP the source that I want to compile. However, preprocessing takes 6 minutes for 1 cpp. Clearly, this is unacceptable. There are redundant expansions of the BOOST_PP_FOR and BOOST_PP_WHILE macros, but PP does not allow "storing" results of expansions somewhere for reuse. Can anything be done? I noted also that moving from a BOOST_PP_SEQ_FOR_EACH() expansion to the equivalent code that generates vertical repetition with LOCAL_ITERATE is much slower, but more readable. Can one get both vertical repetition and not slow? Regards,
participants (5)
-
Daniel James -
Hicham Mouline -
joel falcou -
Larry Evans -
OvermindDL1