#include <boost/mpl/if.hpp>

// This metafunction computes how many inheritance steps Domain is away from
// the ultimate super-parent not_a_domain
template<typename Domain>
struct domain_range
{
  static const size_t value =
    1 + domain_range<typename Domain::proto_super_domain>::value;
};

template<>
struct domain_range<not_a_domain>
{
  static const size_t value = 0;
};

// This metafunction computes the nearest common superdomain of two domains A0,
// A1 given also their domain_ranges R0 and R1.  It is implemented via various
// partial specializations
template<
  size_t R0, size_t R1,
  typename A0, typename A1,
  int Compare = ( R0 < R1 ? -1 : ( R0 > R1 ? 1 : 0 ) )
>
struct deduce_domain2_impl;

// If A0 is further from the root than A1, go one step up on the A0 side
template<size_t R0, size_t R1, typename A0, typename A1>
struct deduce_domain2_impl<R0, R1, A0, A1, 1>
{
  typedef typename deduce_domain2_impl<
    R0-1, R1,
    typename A0::proto_super_domain, A1
  >::type type;
};

// If A1 further from A0, analagously
template<size_t R0, size_t R1, typename A0, typename A1>
struct deduce_domain2_impl<R0, R1, A0, A1, -1>
{
  typedef typename deduce_domain2_impl<
    R0, R1-1,
    A0, typename A1::proto_super_domain
  >::type type;
};

// When they are equidistant but unequal, take both parents
template<size_t R0, size_t R1, typename A0, typename A1>
struct deduce_domain2_impl<R0, R1, A0, A1, 0>
{
  typedef typename deduce_domain2_impl<
    R0-1, R1-1,
    typename A0::proto_super_domain, typename A1::proto_super_domain
  >::type type;
};

// When they are equidistant and equal, we are done
template<size_t R0, size_t R1, typename A>
struct deduce_domain2_impl<R0, R1, A, A, 0>
{ typedef A type; };

// And finally we need some special cases to get the right behaviour for
// default_domain.  To avoid ambiguous specializations we need to list all the
// possible values of Compare explicitly (there are two for each side in which
// default_domain can appear).
template<size_t R0, size_t R1, typename A>
struct deduce_domain2_impl<R0, R1, A, default_domain, 0>
{ typedef A type; };

template<size_t R0, size_t R1, typename A>
struct deduce_domain2_impl<R0, R1, A, default_domain, 1>
{ typedef A type; };

template<size_t R0, size_t R1, typename A>
struct deduce_domain2_impl<R0, R1, default_domain, A, 0>
{ typedef A type; };

template<size_t R0, size_t R1, typename A>
struct deduce_domain2_impl<R0, R1, default_domain, A, -1>
{ typedef A type; };

template<size_t R0, size_t R1>
struct deduce_domain2_impl<R0, R1, default_domain, default_domain, 0>
{ typedef default_domain type; };

// This metafunction computes the actual common domain for two arguments.  It
// forwards to the above metafunction (adding the ranges) but prohibits the
// answer being default_domain (because this indicates an ambiguous answer)
// *except* when both inputs were default_domain (explicit specialization
// below).
template<typename A0, typename A1>
struct deduce_domain2
{
  typedef typename deduce_domain2_impl<
    domain_range<A0>::value,
    domain_range<A1>::value,
    A0,
    A1
  >::type common_super_domain;
  typedef typename boost::mpl::if_<
    typename boost::is_same<common_super_domain, default_domain>::type,
    not_a_domain,
    common_super_domain
  >::type type;
};

template<>
struct deduce_domain2<default_domain, default_domain>
{
  typedef default_domain type;
};

// Three-argument version implemented in terms of the two-argument version
template<typename A0, typename A1, typename A2>
struct deduce_domain3
{
  typedef typename
    deduce_domain2<A0, typename deduce_domain2<A1, A2>::type>::type type;
};