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

struct not_a_domain
{
    static not_a_domain deduce(...);
};

template<typename Domain = not_a_domain>
struct domain : Domain
{
    static Domain deduce(Domain*);
    using Domain::deduce;
};

struct default_domain
  : domain<>
{};

template <>
struct domain<default_domain> : default_domain
{};

template <int N>
struct sized_type
{
    char dummy[N];
};

sized_type<0> default_case(void*, void*);
sized_type<1> default_case(default_domain*, void*);
sized_type<2> default_case(void*, default_domain*);
sized_type<3> default_case(default_domain*, default_domain*);

template <
    class D0, class D1, int DefaultCase = sizeof(default_case((D0*)0, (D1*)0))
>
struct deduce_common
{
    typedef decltype(domain<D0>::deduce((D1*)0)) type;
};

template <class D0, class D1>
struct deduce_common<D0, D1, 1>
{
    typedef D1 type;
};

template <class D0, class D1>
struct deduce_common<D0, D1, 2>
{
    typedef D0 type;
};

template <>
struct deduce_common<default_domain, default_domain, 3>
{
    typedef default_domain type;
};

template <class D0>
struct deduce_common<D0, default_domain, 3>
{
    typedef D0 type;
};

template <class D1>
struct deduce_common<default_domain, D1, 3>
{
    typedef D1 type;
};

template<typename A0, typename A1, typename A2>
struct deduce_domain3
{
    typedef typename deduce_common<A0, A1>::type common0;
    typedef typename deduce_common<common0, A2>::type type;
};

struct D0 : domain<>
{
};

struct D1 : domain<D0> // a sub-domain of D0
{
};

struct D2 : domain<D0> // a sub-domain of D0
{
};

struct D3 : domain<>
{
};

struct DD0 : domain<default_domain> // a sub-domain of default_domain
{
};

struct DD1 : domain<default_domain> // a sub-domain of default_domain
{
};

struct DD2 : domain<default_domain> // a sub-domain of default_domain
{
};

struct DD3 : domain<DD2> // a sub-domain of DD2
{
};

int main()
{
    using boost::is_same;

    BOOST_MPL_ASSERT((is_same<deduce_domain3<D0, D0, D0>::type, D0>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<default_domain, D0, D0>::type, D0>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<D0, default_domain, D0>::type, D0>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<D0, D0, default_domain>::type, D0>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<D0, default_domain, default_domain>::type, D0>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<default_domain, D0, default_domain>::type, D0>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<default_domain, default_domain, D0>::type, D0>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<default_domain, default_domain, default_domain>::type, default_domain>));

    BOOST_MPL_ASSERT((is_same<deduce_domain3<DD0, D0, D0>::type, D0>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<D0, DD0, D0>::type, D0>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<D0, D0, DD0>::type, D0>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<D0, DD0, DD0>::type, D0>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<DD0, D0, DD0>::type, D0>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<DD0, DD0, D0>::type, D0>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<default_domain, DD0, DD0>::type, DD0>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<DD0, default_domain, DD0>::type, DD0>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<DD0, DD0, default_domain>::type, DD0>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<default_domain, default_domain, DD0>::type, DD0>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<default_domain, DD0, default_domain>::type, DD0>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<DD0, DD0, default_domain>::type, DD0>));

    BOOST_MPL_ASSERT((is_same<deduce_domain3<D0, D0, D1>::type, D0>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<D0, D1, D0>::type, D0>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<D0, D1, D1>::type, D0>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<D1, D0, D0>::type, D0>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<D1, D0, D1>::type, D0>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<D1, D1, D0>::type, D0>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<D1, D1, D1>::type, D1>));

    // Very tricky to get right
    BOOST_MPL_ASSERT((is_same<deduce_domain3<D2, D2, D1>::type, D0>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<D2, D1, D2>::type, D0>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<D2, D1, D1>::type, D0>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<D1, D2, D2>::type, D0>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<D1, D2, D1>::type, D0>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<D1, D1, D2>::type, D0>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<D1, D1, D1>::type, D1>));

    BOOST_MPL_ASSERT((is_same<deduce_domain3<D3, D0, D0>::type, not_a_domain>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<D0, D3, D0>::type, not_a_domain>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<D0, D0, D3>::type, not_a_domain>));

    BOOST_MPL_ASSERT((is_same<deduce_domain3<D3, D1, D0>::type, not_a_domain>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<D3, D0, D1>::type, not_a_domain>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<D1, D3, D0>::type, not_a_domain>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<D0, D3, D1>::type, not_a_domain>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<D0, D1, D3>::type, not_a_domain>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<D1, D0, D3>::type, not_a_domain>));

    BOOST_MPL_ASSERT((is_same<deduce_domain3<D3, D1, D2>::type, not_a_domain>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<D3, D2, D1>::type, not_a_domain>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<D1, D3, D2>::type, not_a_domain>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<D2, D3, D1>::type, not_a_domain>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<D2, D1, D3>::type, not_a_domain>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<D1, D2, D3>::type, not_a_domain>));

    BOOST_MPL_ASSERT((is_same<deduce_domain3<DD3, DD2, DD2>::type, DD2>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<DD2, DD3, DD2>::type, DD2>));
    BOOST_MPL_ASSERT((is_same<deduce_domain3<DD2, DD2, DD3>::type, DD2>));

    // 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>));
}