Re: [boost] A C++ puzzler

13 Apr 2008

      Eric Niebler wrote:
...
I recently had a C++ problem and found an answer that tickled my brain. 
In the spirit of Car Talk on NPR, I thought I'd share it in the form of 
a puzzler.
OK, here's my solution. It's no better than some of the others I've seen 
posted here. Just a different way to skin the cat.

#include <boost/mpl/assert.hpp>
#include <boost/preprocessor.hpp>
#include <boost/type_traits/is_same.hpp>

#define M 10

struct Default {};
struct ignore { ignore(...); };

template<typename E>
struct nondeducable
{
     typedef nondeducable type;
     nondeducable(E*&);
     nondeducable(Default*&);
};

template<>
struct nondeducable<Default>
{
     typedef nondeducable type;
     nondeducable(Default*&);
};

template<int N, BOOST_PP_ENUM_PARAMS_WITH_A_DEFAULT(M, class A, void)>
struct select_nth
{
     BOOST_MPL_ASSERT_MSG((false), NO_COMMON_TYPE, (select_nth));
};

#define M0(Z, N, _)                                             \
template<BOOST_PP_ENUM_PARAMS_Z(Z, M, class A)>                 \
struct select_nth<N BOOST_PP_ENUM_TRAILING_PARAMS_Z(Z, M, A)>   \
{                                                               \
     typedef BOOST_PP_CAT(A, N) type;                            \
};
BOOST_PP_REPEAT(M, M0, ~)
#undef M0

template<BOOST_PP_ENUM_PARAMS_WITH_A_DEFAULT(M, class A, Default)>
struct common_type
{
     static char (&deducer(BOOST_PP_ENUM_PARAMS(M, ignore
         BOOST_PP_INTERCEPT)))[M+1];

     #define M0(Z, N, _)                                             \
     static BOOST_PP_CAT(A, N) *BOOST_PP_CAT(a, N);                  \
     template<typename T>                                            \
     static char (&deducer(                                          \
         BOOST_PP_ENUM_PARAMS_Z(Z, N, Default *& BOOST_PP_INTERCEPT) \
         BOOST_PP_COMMA_IF(N) T *&                                   \
         BOOST_PP_ENUM_TRAILING_PARAMS_Z(                            \
             Z                                                       \
           , BOOST_PP_DEC(BOOST_PP_SUB(M, N))                        \
           , typename nondeducable<T>::type BOOST_PP_INTERCEPT       \
         )                                                           \
     ))[N+1];
     BOOST_PP_REPEAT(M, M0, ~)
     #undef M0
     static int const value = sizeof(deducer(
         BOOST_PP_ENUM_PARAMS(M, a))) - 1;
     typedef typename select_nth<value
         BOOST_PP_ENUM_TRAILING_PARAMS(M, A)>::type type;
};

int main()
{
     using boost::is_same;
     BOOST_MPL_ASSERT((is_same<common_type<Default, Default, int,
         Default>::type, int>));
     BOOST_MPL_ASSERT((is_same<common_type<int, Default, int,
         Default>::type, int>));
     BOOST_MPL_ASSERT((is_same<common_type<int, int, int, int>::type,
         int>));
     BOOST_MPL_ASSERT((is_same<common_type<Default, Default,
         Default>::type, Default>));
     // MPL assertion failure
     //common_type<int, short, Default>::type t;
}

The gist is to build an overload set like:

deducer(T, Non<T>::type, Non<T>::type)
deducer(Default, T, Non<T>::type, Non<T>::type)
deducer(Default, Default, T, Non<T>::type)
deducer(Default, Default, Default, T)

Where both T and Default are convertible to Non<T>::type. The overload 
that gets selected has deduced T to be the common type. With decltype we 
could read it out directly. Instead I encode the index of T in the 
return type. There is one additional overload that gets selected only if 
there is no common type.

If a common type exists, we instantiate nondeducable<T>, possibly 
nondeducable<Default>, and a select_nth template. That's it.

-- 
Eric Niebler
Boost Consulting
www.boost-consulting.com