[challenge!] find a common domain
I recently solved a devilish C++ coding problem related to the new sub-domain feature of Proto. I don't care for my solution, so I thought I'd throw it out there and see if some smart person could do better. I'm sending along the skeleton of the solution and some tests that it needs to satisfy. The rest is up to you. The problem goes like this. Every Proto expression has a "domain", which is a type defined something like this: struct my_domain : domain<> {}; A domain can be a sub-domain of another domain, defined like this: struct my_sub_domain : domain<my_domain> {}; When combining sub-expressions into larger expressions, the new expression has some domain that depends on the domains of its children. This domain is calculated according to some rules. - Domains that share no common super-domain are incompatible with each other. The result should be not_a_domain. - A sub-domain is "stronger" than its super-domain. - For a set of domains, the common domain is the strongest domain that is a super-domain of every domain in the set. - default_domain is special; it is compatible with (and dominated by) all other domains. - A sub-domain of default_domain is stronger than default_domain and still compatible with and dominated by all other domains. Your job: implement the deduce_domain3 template that finds the common domain of 3 domains. You're allowed to use decltype, but you get bonus points for a solution that doesn't. Bonus also for instantiating fewest templates. The challenge is for the ternary case, but your solution should scale to N domains. If your solution is better than mine, I'll use it in Proto and credit you! Good luck. P.S. I haven't checked my solution in yet, so you can't look in trunk and cheat. ;-) -- Eric Niebler BoostPro Computing http://www.boostpro.com
On Tue, 18 May 2010, Eric Niebler wrote: (snip)
Your job: implement the deduce_domain3 template that finds the common domain of 3 domains. You're allowed to use decltype, but you get bonus points for a solution that doesn't. Bonus also for instantiating fewest templates. The challenge is for the ternary case, but your solution should scale to N domains. If your solution is better than mine, I'll use it in Proto and credit you!
My solution attempt is attached. It should be standard C++03 (no decltype). The ternary case is just built as a pair of applications of a binary deduce_domain2 template, so adding more parameters should be straightforward. -- Jeremiah Willcock
On 5/19/2010 11:52 AM, Jeremiah Willcock wrote:
On Tue, 18 May 2010, Eric Niebler wrote:
(snip)
Your job: implement the deduce_domain3 template that finds the common domain of 3 domains. You're allowed to use decltype, but you get bonus points for a solution that doesn't. Bonus also for instantiating fewest templates. The challenge is for the ternary case, but your solution should scale to N domains. If your solution is better than mine, I'll use it in Proto and credit you!
My solution attempt is attached. It should be standard C++03 (no decltype). The ternary case is just built as a pair of applications of a binary deduce_domain2 template, so adding more parameters should be straightforward.
That was fast! But does it work for all cases? I'll need to plug it back into my test harness and see. -- Eric Niebler BoostPro Computing http://www.boostpro.com
On Wed, 19 May 2010, Eric Niebler wrote:
On 5/19/2010 11:52 AM, Jeremiah Willcock wrote:
On Tue, 18 May 2010, Eric Niebler wrote:
(snip)
Your job: implement the deduce_domain3 template that finds the common domain of 3 domains. You're allowed to use decltype, but you get bonus points for a solution that doesn't. Bonus also for instantiating fewest templates. The challenge is for the ternary case, but your solution should scale to N domains. If your solution is better than mine, I'll use it in Proto and credit you!
My solution attempt is attached. It should be standard C++03 (no decltype). The ternary case is just built as a pair of applications of a binary deduce_domain2 template, so adding more parameters should be straightforward.
That was fast! But does it work for all cases? I'll need to plug it back into my test harness and see.
I hope it does; I think my tests handled all of the two-domain deductions correctly (but check my examples too to make sure my understanding of "correct answer" agrees with yours). -- Jeremiah Willcock
wow, i got a similar looking problem. May i use your code ? -- ___________________________________________ Joel Falcou - Assistant Professor PARALL Team - LRI - Universite Paris Sud XI Tel : (+33)1 69 15 66 35
On Wed, 19 May 2010, joel falcou wrote:
wow, i got a similar looking problem. May i use your code ?
Yes, that's fine. Or you might want to use Daniel's version if you have decltype (it's faster in that case; I haven't looked at his non-decltype version). -- Jeremiah Willcock
I am a bit surprised by: // These should be ambiguous. BOOST_MPL_ASSERT((is_same<deduce_domain3<DD1, DD0, DD0>::type, not_a_domain>)); BOOST_MPL_ASSERT((is_same<deduce_domain3<DD0, DD1, DD0>::type, not_a_domain>)); BOOST_MPL_ASSERT((is_same<deduce_domain3<DD0, DD0, DD1>::type, not_a_domain>)); I was expecting something like: BOOST_MPL_ASSERT((is_same<deduce_domain3<DD1, DD0, DD0>::type, default_domain)); Am I missing something ? -- Marco Cecchetti On Wed, 19 May 2010 08:02:56 +0200, Eric Niebler <eric@boostpro.com> wrote:
I recently solved a devilish C++ coding problem related to the new sub-domain feature of Proto. I don't care for my solution, so I thought I'd throw it out there and see if some smart person could do better. I'm sending along the skeleton of the solution and some tests that it needs to satisfy. The rest is up to you.
The problem goes like this. Every Proto expression has a "domain", which is a type defined something like this:
struct my_domain : domain<> {};
A domain can be a sub-domain of another domain, defined like this:
struct my_sub_domain : domain<my_domain> {};
When combining sub-expressions into larger expressions, the new expression has some domain that depends on the domains of its children. This domain is calculated according to some rules.
- Domains that share no common super-domain are incompatible with each other. The result should be not_a_domain. - A sub-domain is "stronger" than its super-domain. - For a set of domains, the common domain is the strongest domain that is a super-domain of every domain in the set. - default_domain is special; it is compatible with (and dominated by) all other domains. - A sub-domain of default_domain is stronger than default_domain and still compatible with and dominated by all other domains.
Your job: implement the deduce_domain3 template that finds the common domain of 3 domains. You're allowed to use decltype, but you get bonus points for a solution that doesn't. Bonus also for instantiating fewest templates. The challenge is for the ternary case, but your solution should scale to N domains. If your solution is better than mine, I'll use it in Proto and credit you!
Good luck.
P.S. I haven't checked my solution in yet, so you can't look in trunk and cheat. ;-)
-- Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
(Please don't top-post.) On 5/19/2010 2:08 PM, Marco wrote:
On Wed, 19 May 2010 08:02:56 +0200, Eric Niebler <eric@boostpro.com> wrote: <snip>
Your job: implement the deduce_domain3 template that finds the common domain of 3 domains. You're allowed to use decltype, but you get bonus points for a solution that doesn't. Bonus also for instantiating fewest templates. The challenge is for the ternary case, but your solution should scale to N domains. If your solution is better than mine, I'll use it in Proto and credit you!
Good luck.
P.S. I haven't checked my solution in yet, so you can't look in trunk and cheat. ;-)
I am a bit surprised by:
// These should be ambiguous. BOOST_MPL_ASSERT((is_same<deduce_domain3<DD1, DD0, DD0>::type, not_a_domain>)); BOOST_MPL_ASSERT((is_same<deduce_domain3<DD0, DD1, DD0>::type, not_a_domain>)); BOOST_MPL_ASSERT((is_same<deduce_domain3<DD0, DD0, DD1>::type, not_a_domain>));
I was expecting something like: BOOST_MPL_ASSERT((is_same<deduce_domain3<DD1, DD0, DD0>::type, default_domain));
Am I missing something ?
This is a tricky case, and to understand why I want that result, you need to know what proto uses domains for. In proto, you put an expression in a domain to give it certain domain-specific behaviors. (E.g. lambda expressions should have an operator() that evaluates the lambda.) However, there are no domain-specific behaviors to the default_domain. (E.g. "42" is in the default_domain. Obviously, it has no domain-specific behavior itself, but "lambda::_1 + 42" should be in the lambda domain.) If you combine two expressions in different domains, and the only super-domain they have in common is default_domain, then that would effectively strip all domain-specific behavior from the new expression. IMO, this would be surprising. Instead, I'd rather make this case ambiguous -- proto doesn't know what domain-specific behaviors to give the new expression so it gives up. I acknowledge that it is a special case and that this result doesn't follow naturally from the other rules. -- Eric Niebler BoostPro Computing http://www.boostpro.com
On Wed, 19 May 2010, Eric Niebler wrote:
(Please don't top-post.)
On 5/19/2010 2:08 PM, Marco wrote:
On Wed, 19 May 2010 08:02:56 +0200, Eric Niebler <eric@boostpro.com> wrote: <snip>
Your job: implement the deduce_domain3 template that finds the common domain of 3 domains. You're allowed to use decltype, but you get bonus points for a solution that doesn't. Bonus also for instantiating fewest templates. The challenge is for the ternary case, but your solution should scale to N domains. If your solution is better than mine, I'll use it in Proto and credit you!
Good luck.
P.S. I haven't checked my solution in yet, so you can't look in trunk and cheat. ;-)
I am a bit surprised by:
// These should be ambiguous. BOOST_MPL_ASSERT((is_same<deduce_domain3<DD1, DD0, DD0>::type, not_a_domain>)); BOOST_MPL_ASSERT((is_same<deduce_domain3<DD0, DD1, DD0>::type, not_a_domain>)); BOOST_MPL_ASSERT((is_same<deduce_domain3<DD0, DD0, DD1>::type, not_a_domain>));
I was expecting something like: BOOST_MPL_ASSERT((is_same<deduce_domain3<DD1, DD0, DD0>::type, default_domain));
Am I missing something ?
This is a tricky case, and to understand why I want that result, you need to know what proto uses domains for. In proto, you put an expression in a domain to give it certain domain-specific behaviors. (E.g. lambda expressions should have an operator() that evaluates the lambda.) However, there are no domain-specific behaviors to the default_domain. (E.g. "42" is in the default_domain. Obviously, it has no domain-specific behavior itself, but "lambda::_1 + 42" should be in the lambda domain.)
If you combine two expressions in different domains, and the only super-domain they have in common is default_domain, then that would effectively strip all domain-specific behavior from the new expression. IMO, this would be surprising. Instead, I'd rather make this case ambiguous -- proto doesn't know what domain-specific behaviors to give the new expression so it gives up.
I acknowledge that it is a special case and that this result doesn't follow naturally from the other rules.
How do the rules for default_domain (and domains derived from it) fit into that picture? Expressions from different domains not derived from default_domain produce not_a_domain in the case of conflicts, while a pair in which one element is derived from default_domain will always choose that element as the domain of the new expression. In my implementation, if both domains derive from default_domain but are otherwise incompatible, the result will be default_domain, but normal domains do not derive from default_domain and so end up with the not_a_domain behavior in the case of conflicts. -- Jeremiah Willcock
On 5/19/2010 2:25 PM, Jeremiah Willcock wrote:
On Wed, 19 May 2010, Eric Niebler wrote:
On 5/19/2010 2:08 PM, Marco wrote:
I am a bit surprised by:
// These should be ambiguous. BOOST_MPL_ASSERT((is_same<deduce_domain3<DD1, DD0, DD0>::type, not_a_domain>)); BOOST_MPL_ASSERT((is_same<deduce_domain3<DD0, DD1, DD0>::type, not_a_domain>)); BOOST_MPL_ASSERT((is_same<deduce_domain3<DD0, DD0, DD1>::type, not_a_domain>));
I was expecting something like: BOOST_MPL_ASSERT((is_same<deduce_domain3<DD1, DD0, DD0>::type, default_domain));
Am I missing something ?
This is a tricky case, and to understand why I want that result, you need to know what proto uses domains for. In proto, you put an expression in a domain to give it certain domain-specific behaviors. (E.g. lambda expressions should have an operator() that evaluates the lambda.) However, there are no domain-specific behaviors to the default_domain. (E.g. "42" is in the default_domain. Obviously, it has no domain-specific behavior itself, but "lambda::_1 + 42" should be in the lambda domain.)
If you combine two expressions in different domains, and the only super-domain they have in common is default_domain, then that would effectively strip all domain-specific behavior from the new expression. IMO, this would be surprising. Instead, I'd rather make this case ambiguous -- proto doesn't know what domain-specific behaviors to give the new expression so it gives up.
I acknowledge that it is a special case and that this result doesn't follow naturally from the other rules.
How do the rules for default_domain (and domains derived from it) fit into that picture? Expressions from different domains not derived from default_domain produce not_a_domain in the case of conflicts,
Right.
while a pair in which one element is derived from default_domain will always choose that element as the domain of the new expression.
Here, you mean "the other element" -- that is, the domain that is not a sub-domain of default_domain. The family of domains rooted at default_domain is weaker than all others. (I want this behavior for unified placeholders. Consider that _1 should be a lambda, but it should combine freely with expressions in other domains.)
In my implementation, if both domains derive from default_domain but are otherwise incompatible, the result will be default_domain,
That's not right for the reason I stated above. And that's the case that hung me up for a while.
but normal domains do not derive from default_domain and so end up with the not_a_domain behavior in the case of conflicts.
This part is right. -- Eric Niebler BoostPro Computing http://www.boostpro.com
On Wed, 19 May 2010, Eric Niebler wrote:
On 5/19/2010 2:25 PM, Jeremiah Willcock wrote:
On Wed, 19 May 2010, Eric Niebler wrote:
On 5/19/2010 2:08 PM, Marco wrote:
I am a bit surprised by:
// These should be ambiguous. BOOST_MPL_ASSERT((is_same<deduce_domain3<DD1, DD0, DD0>::type, not_a_domain>)); BOOST_MPL_ASSERT((is_same<deduce_domain3<DD0, DD1, DD0>::type, not_a_domain>)); BOOST_MPL_ASSERT((is_same<deduce_domain3<DD0, DD0, DD1>::type, not_a_domain>));
I was expecting something like: BOOST_MPL_ASSERT((is_same<deduce_domain3<DD1, DD0, DD0>::type, default_domain));
Am I missing something ?
This is a tricky case, and to understand why I want that result, you need to know what proto uses domains for. In proto, you put an expression in a domain to give it certain domain-specific behaviors. (E.g. lambda expressions should have an operator() that evaluates the lambda.) However, there are no domain-specific behaviors to the default_domain. (E.g. "42" is in the default_domain. Obviously, it has no domain-specific behavior itself, but "lambda::_1 + 42" should be in the lambda domain.)
If you combine two expressions in different domains, and the only super-domain they have in common is default_domain, then that would effectively strip all domain-specific behavior from the new expression. IMO, this would be surprising. Instead, I'd rather make this case ambiguous -- proto doesn't know what domain-specific behaviors to give the new expression so it gives up.
I acknowledge that it is a special case and that this result doesn't follow naturally from the other rules.
How do the rules for default_domain (and domains derived from it) fit into that picture? Expressions from different domains not derived from default_domain produce not_a_domain in the case of conflicts,
Right.
while a pair in which one element is derived from default_domain will always choose that element as the domain of the new expression.
Here, you mean "the other element" -- that is, the domain that is not a sub-domain of default_domain. The family of domains rooted at default_domain is weaker than all others.
OK. I implemented it the other way around -- choose the default_domain-derived domain if the other one isn't derived from that base. The two cases to flip to fix that are the second and third specializations of deduce_domain2_cases.
In my implementation, if both domains derive from default_domain but are otherwise incompatible, the result will be default_domain,
That's not right for the reason I stated above. And that's the case that hung me up for a while.
What do you want there? not_a_domain? Is default_domain itself a domain that's accessible to users (i.e., they can have an element with default_domain as its domain)? In that case, when do two domains that both derive from default_domain conflict? They have a common ancestor, namely default_domain. Or should default_domain be special in that regard, with a rule such as "if the merger of two domains is default_domain but one of them isn't default_domain, replace the result with not_a_domain"?
but normal domains do not derive from default_domain and so end up with the not_a_domain behavior in the case of conflicts.
This part is right.
OK. -- Jeremiah Willcock
On 5/19/2010 2:47 PM, Jeremiah Willcock wrote:
On Wed, 19 May 2010, Eric Niebler wrote:
On 5/19/2010 2:25 PM, Jeremiah Willcock wrote:
How do the rules for default_domain (and domains derived from it) fit into that picture? Expressions from different domains not derived from default_domain produce not_a_domain in the case of conflicts,
Right.
while a pair in which one element is derived from default_domain will always choose that element as the domain of the new expression.
Here, you mean "the other element" -- that is, the domain that is not a sub-domain of default_domain. The family of domains rooted at default_domain is weaker than all others.
OK. I implemented it the other way around -- choose the default_domain-derived domain if the other one isn't derived from that base. The two cases to flip to fix that are the second and third specializations of deduce_domain2_cases.
OK.
In my implementation, if both domains derive from default_domain but are otherwise incompatible, the result will be default_domain,
That's not right for the reason I stated above. And that's the case that hung me up for a while.
What do you want there? not_a_domain?
Yes.
Is default_domain itself a domain that's accessible to users (i.e., they can have an element with default_domain as its domain)?
Yes.
In that case, when do two domains that both derive from default_domain conflict? They have a common ancestor, namely default_domain. Or should default_domain be special in that regard, with a rule such as "if the merger of two domains is default_domain but one of them isn't default_domain, replace the result with not_a_domain"?
Close. Yes, default_domain is special. If the merger of two domains is default_domain and /neither of them/ is default_domain, the result is not_a_domain. Otherwise, the one that's not default_domain dominates. So, if lambda_domain is a sub-domain of default_domain, it is stronger than default_domain and should dominate. I.e., "_1 + 42" should be a lambda expression. default_domain should *never* be the answer when any domain is not default_domain. Gotta pass all the test cases I sent! :-)
but normal domains do not derive from default_domain and so end up with the not_a_domain behavior in the case of conflicts.
This part is right.
OK.
-- Eric Niebler BoostPro Computing http://www.boostpro.com
In that case, when do two domains that both derive from default_domain conflict? They have a common ancestor, namely default_domain. Or should default_domain be special in that regard, with a rule such as "if the merger of two domains is default_domain but one of them isn't default_domain, replace the result with not_a_domain"?
Close. Yes, default_domain is special. If the merger of two domains is default_domain and /neither of them/ is default_domain, the result is not_a_domain. Otherwise, the one that's not default_domain dominates. So, if lambda_domain is a sub-domain of default_domain, it is stronger than default_domain and should dominate. I.e., "_1 + 42" should be a lambda expression.
default_domain should *never* be the answer when any domain is not default_domain.
What about in the case of two different domains that both derive from default_domain but have no other ancestors in common? I see not_a_domain in your test cases. What about two different domains that each derive from DD0 (in your test case)? What should the result of combining them be? For non-default_domain domains I use the least common ancestor (which is what it seemed like you wanted). -- Jeremiah Willcock
On 5/19/2010 3:07 PM, Jeremiah Willcock wrote:
In that case, when do two domains that both derive from default_domain conflict? They have a common ancestor, namely default_domain. Or should default_domain be special in that regard, with a rule such as "if the merger of two domains is default_domain but one of them isn't default_domain, replace the result with not_a_domain"?
Close. Yes, default_domain is special. If the merger of two domains is default_domain and /neither of them/ is default_domain, the result is not_a_domain. Otherwise, the one that's not default_domain dominates. So, if lambda_domain is a sub-domain of default_domain, it is stronger than default_domain and should dominate. I.e., "_1 + 42" should be a lambda expression.
default_domain should *never* be the answer when any domain is not default_domain.
What about in the case of two different domains that both derive from default_domain but have no other ancestors in common?
Ambiguous. not_a_domain.
I see not_a_domain in your test cases. What about two different domains that each derive from DD0 (in your test case)? What should the result of combining them be?
DD0.
For non-default_domain domains I use the least common ancestor (which is what it seemed like you wanted).
That works. Something like it should also work for the family of domains rooted at default_domain, with a special case for when the result would be default_domain itself. -- Eric Niebler BoostPro Computing http://www.boostpro.com
On Wed, 19 May 2010, Eric Niebler wrote:
On 5/19/2010 3:07 PM, Jeremiah Willcock wrote:
In that case, when do two domains that both derive from default_domain conflict? They have a common ancestor, namely default_domain. Or should default_domain be special in that regard, with a rule such as "if the merger of two domains is default_domain but one of them isn't default_domain, replace the result with not_a_domain"?
Close. Yes, default_domain is special. If the merger of two domains is default_domain and /neither of them/ is default_domain, the result is not_a_domain. Otherwise, the one that's not default_domain dominates. So, if lambda_domain is a sub-domain of default_domain, it is stronger than default_domain and should dominate. I.e., "_1 + 42" should be a lambda expression.
default_domain should *never* be the answer when any domain is not default_domain.
What about in the case of two different domains that both derive from default_domain but have no other ancestors in common?
Ambiguous. not_a_domain.
I see not_a_domain in your test cases. What about two different domains that each derive from DD0 (in your test case)? What should the result of combining them be?
DD0.
For non-default_domain domains I use the least common ancestor (which is what it seemed like you wanted).
That works. Something like it should also work for the family of domains rooted at default_domain, with a special case for when the result would be default_domain itself.
What about DD2 and DD3 from your tests, though? You have that combination returning DD2, which is the opposite of what I would expect from your description (if X derives from default_domain, always pick X as the result). Or am I misunderstanding something? -- Jeremiah Willcock
On 5/19/2010 3:17 PM, Jeremiah Willcock wrote:
On Wed, 19 May 2010, Eric Niebler wrote:
On 5/19/2010 3:07 PM, Jeremiah Willcock wrote:
For non-default_domain domains I use the least common ancestor (which is what it seemed like you wanted).
That works. Something like it should also work for the family of domains rooted at default_domain, with a special case for when the result would be default_domain itself.
What about DD2 and DD3 from your tests, though? You have that combination returning DD2, which is the opposite of what I would expect from your description (if X derives from default_domain, always pick X as the result). Or am I misunderstanding something?
We have: default_domain ^ | DD2 ^ | DD3 That is, DD3 is a sub-domain of DD2, which is a sub-domain of default_domain. If you mix expressions from domains DD2 and DD3 (e.g., {DD2, DD3, DD2}), the resulting expression should be in domain DD2. It is the strongest domain that is a super-domain of all the domains in the set. If, however, we had something like this: default_domain my_domain ^ | DD2 ^ | DD3 The common domain of {DD2, DD3, my_domain} should be my_domain, because it dominates over all domains from the family rooted at default_domain. And this: default_domain ^ ^ | | DD2 my_domain ^ | DD3 Logically, you'd think that the common domain of {DD2, DD3, my_domain} should be default_domain, but I don't want that. It would strip all domain-specific behaviors from the resulting expression. By fiat, I say this is ambiguous. -- Eric Niebler BoostPro Computing http://www.boostpro.com
I have attached my new version that passes all of your test cases (which are at the bottom of the file). It instantiates more templates than Daniel Wallin's version, though, because of the explicit walk up the ancestors of one of the domains being merged; I don't know if removing decltype from his would change that. -- Jeremiah Willcock
On 5/19/2010 4:05 PM, Jeremiah Willcock wrote:
I have attached my new version that passes all of your test cases (which are at the bottom of the file). It instantiates more templates than Daniel Wallin's version, though, because of the explicit walk up the ancestors of one of the domains being merged; I don't know if removing decltype from his would change that.
Very cool. Yep, I'm sure removing decltype from Daniel's code will cause more template instantiations. I'll be giving that a shot once I have a moment. -- Eric Niebler BoostPro Computing http://www.boostpro.com
On Tue, May 18, 2010 at 11:02:56PM -0700, Eric Niebler wrote:
I recently solved a devilish C++ coding problem related to the new sub-domain feature of Proto. I don't care for my solution, so I thought I'd throw it out there and see if some smart person could do better. I'm sending along the skeleton of the solution and some tests that it needs to satisfy. The rest is up to you.
[...]
Your job: implement the deduce_domain3 template that finds the common domain of 3 domains. You're allowed to use decltype, but you get bonus points for a solution that doesn't. Bonus also for instantiating fewest templates. The challenge is for the ternary case, but your solution should scale to N domains.
Here's mine. It's decltype based, but I guess it could be sizeof based in C++03. Regards, -- Daniel Wallin BoostPro Computing http://www.boostpro.com
On 5/19/2010 3:29 PM, Daniel Wallin wrote:
On Tue, May 18, 2010 at 11:02:56PM -0700, Eric Niebler wrote:
Your job: implement the deduce_domain3 template that finds the common domain of 3 domains. You're allowed to use decltype, but you get bonus points for a solution that doesn't. Bonus also for instantiating fewest templates. The challenge is for the ternary case, but your solution should scale to N domains.
Here's mine. It's decltype based, but I guess it could be sizeof based in C++03.
Wow! SO much simpler than my solution. I'll need to study this in depth. I also specialized domain<default_domain> to insert an extra level in the inheritance tree like you did. That's a great simplification, but it took me a week to see that. Kudos. BTW, you're creating a zero-sized array in sized_type<0>. I just bumped all the integers by one and it works fine on msvc-10. This looks more efficient at compile-time, too. I'll be embarrassed to post my solution. :-O But not yet. Anybody care to eliminate decltype so I can use this in Proto? Anybody think they can instantiate fewer templates? (I think everybody who posts a solution will get a mention in Proto's docs and in the code. Fair's fair.) -- Eric Niebler BoostPro Computing http://www.boostpro.com
On Wed, May 19, 2010 at 03:54:29PM -0700, Eric Niebler wrote:
On 5/19/2010 3:29 PM, Daniel Wallin wrote:
On Tue, May 18, 2010 at 11:02:56PM -0700, Eric Niebler wrote:
Your job: implement the deduce_domain3 template that finds the common domain of 3 domains. You're allowed to use decltype, but you get bonus points for a solution that doesn't. Bonus also for instantiating fewest templates. The challenge is for the ternary case, but your solution should scale to N domains.
Here's mine. It's decltype based, but I guess it could be sizeof based in C++03.
Wow! SO much simpler than my solution. I'll need to study this in depth. I also specialized domain<default_domain> to insert an extra level in the inheritance tree like you did. That's a great simplification, but it took me a week to see that. Kudos.
Thanks. :)
BTW, you're creating a zero-sized array in sized_type<0>. I just bumped all the integers by one and it works fine on msvc-10.
Duh, good catch.
This looks more efficient at compile-time, too. I'll be embarrassed to post my solution. :-O But not yet. Anybody care to eliminate decltype so I can use this in Proto? Anybody think they can instantiate fewer templates?
Here's one without decltype. The changes needed were pretty minor. It might still be possible to reduce the number of instantiations. For instance, you could specialize nth_domain<> on some more indicies (I'm guessing the number of super domains should be fairly low), but I don't know what the cost of specialization compared to instantiation is. -- Daniel Wallin BoostPro Computing http://www.boostpro.com
On 19/05/10 07:02, Eric Niebler wrote: <snip>
Your job: implement the deduce_domain3 template that finds the common domain of 3 domains. You're allowed to use decltype, but you get bonus points for a solution that doesn't. Bonus also for instantiating fewest templates. The challenge is for the ternary case, but your solution should scale to N domains. If your solution is better than mine, I'll use it in Proto and credit you!
I attach my solution for completeness, though I think Daniel's is neater. I used a similar idea to him, but without the use of sizeof/decltype, and with the distance-to-not_a_domain implemented as a metafunction, rather than injected into the definition of domain. I think we use about the same number of instantiations, but Daniel's lends itself to unrolling much more than mine. I might argue that my implementation is a little easier to follow than his, but it would be a pretty feeble claim. (Bah, if only my NNTP client had been cooperating yesterday this would have looked a little more impressive :)) John Bytheway
On 5/20/2010 10:54 AM, John Bytheway wrote:
On 19/05/10 07:02, Eric Niebler wrote: <snip>
Your job: implement the deduce_domain3 template that finds the common domain of 3 domains. You're allowed to use decltype, but you get bonus points for a solution that doesn't. Bonus also for instantiating fewest templates. The challenge is for the ternary case, but your solution should scale to N domains. If your solution is better than mine, I'll use it in Proto and credit you!
I attach my solution for completeness, though I think Daniel's is neater. I used a similar idea to him, but without the use of sizeof/decltype, and with the distance-to-not_a_domain implemented as a metafunction, rather than injected into the definition of domain.
I think we use about the same number of instantiations, but Daniel's lends itself to unrolling much more than mine. I might argue that my implementation is a little easier to follow than his, but it would be a pretty feeble claim.
Thanks, John. I'll need to investigate more closely. Everybody's code is easy to follow when they wrote it! :-) Though I admit, Daniel's solution is subtle and had me scratching my head for a while. And for completeness, here is my (decltype-based) solution. I tried to make one giant expression that calculates the result in one shot. Like Daniel, I use inheritance and overloading, but I build a parallel hierarchy instead of reusing the domains. (For reasons that aren't relevant, I don't want domains to actually inherit from other domains in Proto.) -- Eric Niebler BoostPro Computing http://www.boostpro.com
I've downloaded Boost 1.43.0 and used bcp with the --namespace and --namespace-alias options to prevent link conflicts with other third-party libraries in our project at work. It does appear that some unwanted text substitution is happening (causing compile failures), after renaming the boost namespace. For example, in type_traits/integral_promotion.hpp, the original header guard is: #ifndef FILE_boost_type_traits_integral_promotion_hpp_INCLUDED #define FILE_boost_type_traits_integral_promotion_hpp_INCLUDED After running bcp, the header guard is: #ifndef FILE_boost_type_traits_integral_promotion_hpp_INCLUDED #define FILE_MyProj_Boost_type_traits_integral_promotion_hpp_INCLUDED "MyProj_Boost" is the namespace replacement option as supplied to bcp. There are three files in type_traits with this problem, all with : integral_promotion.hpp promote.hpp floating_point_promotion.hpp It looks like these three header files are the only ones with lower-case header guards (all with copyrights by Alexander Nasonov). I've never filed a trac bug report, but will be happy to, if requested. I assume the easy solution is to make the three type_traits files consistent with the other header files, but is this something that bcp should be handling? There's other compile failures I'm working through, but thought I would start with this one. As always, thanks. Cliff
On 5/19/2010 2:02 AM, Eric Niebler wrote:
Your job: implement the deduce_domain3 template that finds the common domain of 3 domains. You're allowed to use decltype, but you get bonus points for a solution that doesn't. Bonus also for instantiating fewest templates. The challenge is for the ternary case, but your solution should scale to N domains. If your solution is better than mine, I'll use it in Proto and credit you! <snip>
Thanks to all the folks who participated! Everybody loves a challenge. Yesterday, I checked in a solution based on Daniel's code. Everybody who submitted a solution got a mention both in the code and in the docs. Cheers, -- Eric Niebler BoostPro Computing http://www.boostpro.com
participants (8)
-
cliffg＠codewrangler.net -
Daniel Wallin -
daniel＠boostpro.com
-
Eric Niebler -
Jeremiah Willcock -
joel falcou -
John Bytheway -
Marco