#include <boost/mpl/assert.hpp>
#include <boost/type_traits/is_same.hpp>
#include <boost/mpl/vector.hpp>
#include <boost/mpl/front.hpp>
#include <boost/mpl/push_front.hpp>
#include <boost/mpl/pop_front.hpp>
#include <boost/mpl/at.hpp>
#include <boost/mpl/contains.hpp>

using boost::is_same;
using boost::mpl::if_;
using boost::mpl::vector;
using boost::mpl::push_front;
using boost::mpl::pop_front;
using boost::mpl::front;
using boost::mpl::at_c;
using boost::mpl::contains;

struct not_a_domain
{
    typedef not_a_domain proto_super_domain;
};

template<typename Domain = not_a_domain>
struct domain
{
    typedef Domain proto_super_domain;
};

struct default_domain
  : domain<>
{};

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
{
};

template<typename D, typename Chain = vector<> >
struct get_relation_chain
{
   typedef typename push_front<Chain, D>::type NewChain;
   typedef typename get_relation_chain<typename D::proto_super_domain, NewChain>::type type;
};

template<typename Chain>
struct get_relation_chain<not_a_domain, Chain>
{
   typedef typename push_front<Chain, not_a_domain>::type type;
};

typedef boost::mpl::vector0<boost::mpl::na> empty_vector;

template<typename A0, typename A1>
struct same_until
{
   typedef typename pop_front<A0>::type NewA0;
   typedef typename pop_front<A1>::type NewA1;
   static const int value = boost::is_same<typename front<A0>::type, typename front<A1>::type>::value 
                                          ? 1 + same_until<NewA0, NewA1>::value 
                                          : 0;
};

template<typename A0>
struct same_until<A0, empty_vector>
{
   static const int value = 0;
};

template<typename A1>
struct same_until<empty_vector, A1>
{
   static const int value = 0;
};

template<>
struct same_until<empty_vector, empty_vector>
{
   static const int value = 0;
};

template<typename A0, typename A1, typename SuggestedType, bool A0FromDefault, bool A1FromDefault>
struct deduce_domain2_impl
{
   typedef typename if_<is_same<SuggestedType, default_domain>, not_a_domain, SuggestedType>::type type;
};

template<typename A0, typename SuggestedType>
struct deduce_domain2_impl<A0, default_domain, SuggestedType, true, true>
{
   typedef A0 type;
};

template<typename A1, typename SuggestedType>
struct deduce_domain2_impl<default_domain, A1, SuggestedType, true, true>
{
   typedef A1 type;
};

template<typename SuggestedType>
struct deduce_domain2_impl<default_domain, default_domain, SuggestedType, true, true>
{
   typedef default_domain type;
};

template<typename A0, typename A1, typename SuggestedType>
struct deduce_domain2_impl<A0, A1, SuggestedType, false, true>
{
   typedef A0 type;
};

template<typename A0, typename A1, typename SuggestedType>
struct deduce_domain2_impl<A0, A1, SuggestedType, true, false>
{
   typedef A1 type;
};

template<typename A0, typename A1>
struct deduce_domain2
{
   typedef typename get_relation_chain<A0>::type chain1;
   typedef typename get_relation_chain<A1>::type chain2;
   static const int common_length = same_until<chain1, chain2>::value;
   typedef typename at_c<chain1, common_length-1>::type suggested_type;
   typedef typename deduce_domain2_impl<A0, 
                                        A1, 
                                        suggested_type, 
                                        contains<chain1, default_domain>::type::value, 
                                        contains<chain2, default_domain>::type::value>::type type;
};

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

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