// Everything above test code is:
//=======================================================================
// Copyright 2010 Trustees of Indiana University.
// Authors: Jeremiah Willcock, Andrew Lumsdaine
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================

#include <boost/type_traits/is_base_of.hpp>
#include <boost/type_traits/is_same.hpp>
#include <boost/static_assert.hpp>
#include <boost/config.hpp>
#include <boost/mpl/if.hpp>
#include <boost/mpl/eval_if.hpp>
#include <boost/mpl/identity.hpp>
#include <boost/mpl/assert.hpp>

// The usual yes_type/no_type thing; this can be replaced by an MPL version.
struct yes_type {char x;};
struct no_type {char x[2];};

BOOST_STATIC_ASSERT(sizeof(yes_type) != sizeof(no_type));

// Base for not_a_domain and default_domain; the special-casing of
// default_domain in deduce_domain2 should make sure this is never returned as
// a result
struct really_not_a_domain {
  // domain_check acts like a set of ancestor domains (a display in OO terms)
  // to the current one.  The no_type answer says that we hit the ... case (the
  // first parameter is just so the ... is allowed) and so the thing we're
  // querying isn't in the set.
  static no_type domain_check(int, ...) {}
  // rest is necessary here so the "typename B::rest" recursion doesn't fail,
  // but it should never be used.
  typedef void rest;
};

struct not_a_domain;

// The actual domain class; defaulting to not_a_domain gets the conflict cases
// right automatically.
template <typename T = not_a_domain>
struct domain: public T {
  // Append T to the set; T** is used to avoid derived-to-base conversions.
  using T::domain_check;
  static yes_type domain_check(int, T**) {}
  typedef T rest;
};

// The two base domains.  They are incomparable, but anything derived from
// default_domain is special-cased in deduce_domain2.
struct not_a_domain: domain<really_not_a_domain> {};
struct default_domain_dummy {}; // Hack to get is_base_of to recognize default_domain as a base of itself
struct default_domain: default_domain_dummy, domain<really_not_a_domain> {};

// The actual least common ancestor code.  Walks the ancestors of B, looking
// for the closest one that's in A's display (using domain_check).  The use of
// domain<A> rather than A is so that A itself will be in the set (since a
// domain doesn't inherit from anything that contains its own name).
template <typename A, typename B>
struct deduce_domain2_internal {
  typedef typename
    boost::mpl::eval_if_c<
      sizeof(domain<A>::domain_check(0, (B**)0)) == sizeof(yes_type),
      boost::mpl::identity<B>,
      deduce_domain2_internal<A, typename B::rest> >::type type;
};

// Dispatch on which arguments are derived from default_domain; don't use
// mpl::if_ to avoid extra template instantiations.
template <typename A, typename B, bool AIsDefault, bool BIsDefault, bool AIsUnderDefault, bool BIsUnderDefault>
struct deduce_domain2_cases;

template <typename A, typename B>
struct deduce_domain2_cases<A, B, false, false, false, false>: deduce_domain2_internal<A, B> {};

template <typename A, typename B, bool Y>
struct deduce_domain2_cases<A, B, false, Y, false, true> {typedef A type;};

template <typename A, typename B, bool X>
struct deduce_domain2_cases<A, B, X, false, true, false> {typedef B type;};

template <typename A, typename B>
struct deduce_domain2_cases<A, B, false, false, true, true> {
  typedef typename deduce_domain2_internal<A, B>::type type0;
  typedef typename boost::mpl::if_<boost::is_same<type0, default_domain>, not_a_domain, type0>::type type;
};

template <typename A, typename B>
struct deduce_domain2_cases<A, B, true, false, true, true> {typedef B type;};

template <typename A, typename B, bool X>
struct deduce_domain2_cases<A, B, X, true, true, true> {typedef A type;};

template <typename A, typename B>
struct deduce_domain2:
  deduce_domain2_cases<A, B, 
                       boost::is_same<default_domain, A>::value,
                       boost::is_same<default_domain, B>::value,
                       boost::is_base_of<default_domain_dummy, A>::value,
                       boost::is_base_of<default_domain_dummy, B>::value> {};

// All of the more-parameter cases should be able to be built just by applying
// the two-parameter case repeatedly; deduce_domain2 should be associative as
// well.
template <typename A, typename B, typename C>
struct deduce_domain3:
  deduce_domain2<typename deduce_domain2<A, B>::type, C> {};

// Stuff below this line is Eric's test code, not mine

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