//=======================================================================
// 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.hpp>
#include <boost/static_assert.hpp>
#include <boost/config.hpp>
#include <boost/mpl/if.hpp>
#include <boost/mpl/identity.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: 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>
struct deduce_domain2_cases;

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

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

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

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

template <typename A, typename B>
struct deduce_domain2:
  deduce_domain2_cases<A, B, 
                       boost::is_base_and_derived<default_domain, A>::value,
                       boost::is_base_and_derived<default_domain, 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> {};

// Testing code

// Make some domains.
struct c_a: domain<> {};
struct c_aa: domain<c_a> {};
struct c_ab: domain<c_a> {};
struct c_b: domain<> {};
struct c_ba: domain<c_b> {};
struct d_a: domain<default_domain> {};
struct d_aa: domain<d_a> {};
struct d_ab: domain<d_a> {};
struct d_b: domain<default_domain> {};

// A procedure that does a single test case; the Result** line is to get a
// better error message when the types don't match.
template <typename A, typename B, typename Result>
void test() {
  Result **x = (typename deduce_domain2<A, B>::type**)0;
  BOOST_STATIC_ASSERT((boost::is_same<typename deduce_domain2<A, B>::type, Result>::value));
}

int main(int, char**) {
  // All of the combinations of pairs of domains
  test<c_a, c_a, c_a>();
  test<c_a, c_aa, c_a>();
  test<c_a, c_ab, c_a>();
  test<c_a, c_b, not_a_domain>();
  test<c_a, c_ba, not_a_domain>();
  test<c_a, d_a, d_a>();
  test<c_a, d_aa, d_aa>();
  test<c_a, d_ab, d_ab>();
  test<c_a, d_b, d_b>();
  test<c_aa, c_a, c_a>();
  test<c_aa, c_aa, c_aa>();
  test<c_aa, c_ab, c_a>();
  test<c_aa, c_b, not_a_domain>();
  test<c_aa, c_ba, not_a_domain>();
  test<c_aa, d_a, d_a>();
  test<c_aa, d_aa, d_aa>();
  test<c_aa, d_ab, d_ab>();
  test<c_aa, d_b, d_b>();
  test<c_ab, c_a, c_a>();
  test<c_ab, c_aa, c_a>();
  test<c_ab, c_ab, c_ab>();
  test<c_ab, c_b, not_a_domain>();
  test<c_ab, c_ba, not_a_domain>();
  test<c_ab, d_a, d_a>();
  test<c_ab, d_aa, d_aa>();
  test<c_ab, d_ab, d_ab>();
  test<c_ab, d_b, d_b>();
  test<c_b, c_a, not_a_domain>();
  test<c_b, c_aa, not_a_domain>();
  test<c_b, c_ab, not_a_domain>();
  test<c_b, c_b, c_b>();
  test<c_b, c_ba, c_b>();
  test<c_b, d_a, d_a>();
  test<c_b, d_aa, d_aa>();
  test<c_b, d_ab, d_ab>();
  test<c_b, d_b, d_b>();
  test<c_ba, c_a, not_a_domain>();
  test<c_ba, c_aa, not_a_domain>();
  test<c_ba, c_ab, not_a_domain>();
  test<c_ba, c_b, c_b>();
  test<c_ba, c_ba, c_ba>();
  test<c_ba, d_a, d_a>();
  test<c_ba, d_aa, d_aa>();
  test<c_ba, d_ab, d_ab>();
  test<c_ba, d_b, d_b>();
  test<d_a, c_a, d_a>();
  test<d_a, c_aa, d_a>();
  test<d_a, c_ab, d_a>();
  test<d_a, c_b, d_a>();
  test<d_a, c_ba, d_a>();
  test<d_a, d_a, d_a>();
  test<d_a, d_aa, d_a>();
  test<d_a, d_ab, d_a>();
  test<d_a, d_b, default_domain>();
  test<d_aa, c_a, d_aa>();
  test<d_aa, c_aa, d_aa>();
  test<d_aa, c_ab, d_aa>();
  test<d_aa, c_b, d_aa>();
  test<d_aa, c_ba, d_aa>();
  test<d_aa, d_a, d_a>();
  test<d_aa, d_aa, d_aa>();
  test<d_aa, d_ab, d_a>();
  test<d_aa, d_b, default_domain>();
  test<d_ab, c_a, d_ab>();
  test<d_ab, c_aa, d_ab>();
  test<d_ab, c_ab, d_ab>();
  test<d_ab, c_b, d_ab>();
  test<d_ab, c_ba, d_ab>();
  test<d_ab, d_a, d_a>();
  test<d_ab, d_aa, d_a>();
  test<d_ab, d_ab, d_ab>();
  test<d_ab, d_b, default_domain>();
  test<d_b, c_a, d_b>();
  test<d_b, c_aa, d_b>();
  test<d_b, c_ab, d_b>();
  test<d_b, c_b, d_b>();
  test<d_b, c_ba, d_b>();
  test<d_b, d_a, default_domain>();
  test<d_b, d_aa, default_domain>();
  test<d_b, d_ab, default_domain>();
  test<d_b, d_b, d_b>();
  d_aa** x = (deduce_domain3<c_a, d_aa, c_ba>::type**)0;
  d_aa** y = (deduce_domain3<d_aa, c_a, c_ba>::type**)0;
  d_aa** z = (deduce_domain3<c_a, c_ba, d_aa>::type**)0;
  return 0;
}