compile-time tree search

tree_search.cc

#include <type_traits>

/// @brief Determines of a type is a specialization of a template
/// @see wg21.link/p2098
///@{
template <class T, template <class...> class Primary>
struct is_specialization_of : std::false_type {};

template <template <class...> class Primary, class... Args>
struct is_specialization_of<Primary<Args...>, Primary> : std::true_type {};
///@}

/// @brief Returns the type with the maximum value
///@{
template <class...>
struct max;

template <class V1>
struct max<V1> : V1 {};

template <class V1, class V2, class... Vn>
struct max<V1, V2, Vn...> : std::conditional_t<(V1::value > V2::value),
                                               max<V1, Vn...>, max<V2, Vn...>> {
};

template <class... Vn>
inline constexpr auto max_v = max<Vn...>::value;
///@}

/// @brief Obtains the number of elements in a type list
///@{
template <class TypeList>
struct list_size;

template <template <class...> class List, class... Types>
struct list_size<List<Types...>> {
  static constexpr std::size_t value = sizeof...(Types);
};

template <class TypeList>
inline constexpr auto list_size_v = list_size<TypeList>::value;
///@}

/// @brief Concatenates multiple type lists
///@{
template <class List1, class... Lists>
struct concat;

template <template <class...> class List, class... Types1, class... Types2>
struct concat<List<Types1...>, List<Types2...>> {
  using type = List<Types1..., Types2...>;
};

template <class List1, class List2, class... Lists>
struct concat<List1, List2, Lists...>
    : concat<typename concat<List1, List2>::type, Lists...> {};

template <class List1>
struct concat<List1> {
  using type = List1;
};

template <class... Lists>
using concat_t = typename concat<Lists...>::type;
///@}

/// @brief A container for types
template <class... Types>
struct type_list {
  using type = type_list;
};
template <class... Types>
using type_list_t = typename type_list<Types...>::type;

/// @brief A container for types where the first is a parent and the rest are
///     children
template <class Parent, class... Children>
struct type_tree {
  static_assert(sizeof...(Children) != 0);
  using type = type_tree;

  using parent_type = Parent;
  using children_types = type_list<Children...>;
};

template <class Parent, class... Children>
using type_tree_t = typename type_tree<Parent, Children...>::type;

/// @brief Returns the depth of a type_tree type
///@{
template <class T>
struct tree_depth {
  static constexpr std::size_t value = 0;
};
template <class Parent, class... Children>
struct tree_depth<type_tree<Parent, Children...>> {
  static constexpr std::size_t value = 1 + max_v<tree_depth<Children>...>;
};
template <class T>
inline constexpr auto tree_depth_v = tree_depth<T>::value;
///@}

/// @brief Obtains the path from the tree root to a leaf
///@{
template <class Leaf, class Tree, class = void>
struct leaf_path {
  using type = type_list<>;
};

template <class Leaf, class Tree>
using leaf_path_t = typename leaf_path<Leaf, Tree>::type;

template <class Leaf, class Parent, class... Children>
struct leaf_path<
    Leaf, type_tree<Parent, Children...>,
    std::enable_if_t<std::disjunction_v<std::is_same<Leaf, Children>...>>> {
  using type = type_list<Parent, Leaf>;
};

template <class Leaf, class Parent, class... Children>
struct leaf_path<
    Leaf, type_tree<Parent, Children...>,
    std::enable_if_t<
        std::disjunction_v<is_specialization_of<Children, type_tree>...> &&
        !std::disjunction_v<std::is_same<Leaf, Children>...>>> {
  using subtree_path = concat_t<leaf_path_t<Leaf, Children>...>;
  using type =
      std::conditional_t<list_size_v<subtree_path> == 0, type_list<>,
                         concat_t<type_list<Parent>, subtree_path>>;
};
///@}

int main() {
  struct A {};
  struct B {};
  struct C {};
  struct D {};
  struct E {};
  //
  //       A
  //     B  C
  //    D E
  //
  using Tree = type_tree<A, type_tree<B, D, E>, C>;

  static_assert(std::is_same_v<type_list<>, leaf_path_t<B, Tree>>);
  static_assert(std::is_same_v<type_list<A, C>, leaf_path_t<C, Tree>>);
  static_assert(std::is_same_v<type_list<A, B, D>, leaf_path_t<D, Tree>>);
  static_assert(std::is_same_v<type_list<A, B, E>, leaf_path_t<E, Tree>>);

  return tree_depth_v<Tree>;
}