Определить наименьшего общего предка во время компиляции
Есть множество вопросов о алгоритме наименьшего общего предка, но этот отличается, потому что я пытаюсь определить LCA во время компиляции, и мое дерево ни двоичный ни дерево поиска, хотя моя упрощенная версия может выглядеть так.
Предположим, у вас есть несколько структур, которые содержат член typedef parent, который является другой аналогичной структурой:
struct G
{
typedef G parent; // 'root' node has itself as parent
};
struct F
{
typedef G parent;
};
struct E
{
typedef G parent;
};
struct D
{
typedef F parent;
};
struct C
{
typedef F parent;
};
struct B
{
typedef E parent;
};
struct A
{
typedef E parent;
};
которые вместе составляют дерево, такое как
A B C D
\ / \ /
E F
\ /
\ /
\ /
G
ПРИМЕЧАНИЕ. Между структурами нет отношений наследования.
Что я хотел бы сделать, это создать черту типа least_common_ancestor такой что:
least_common_ancestor<A, B>::type; // E
least_common_ancestor<C, D>::type; // F
least_common_ancestor<A, E>::type; // E
least_common_ancestor<A, F>::type; // G
Какой лучший способ сделать это?
Меня не волнует алгоритмическая сложность, в частности, поскольку глубина дерева мала, скорее я ищу простейшую метапрограмму, которая поможет получить правильный ответ.
РЕДАКТИРОВАТЬ: Я должен быть в состоянии построить решение с msvc2013, среди других компиляторов, так что ответы без constexpr являются предпочтительными.
Решение
Возможно, это можно улучшить, но вы можете сначала вычислить глубину вашего типа, а затем использовать эту информацию для перехода вверх по одной ветви или другой:
template <typename U, typename = typename U::parent>
struct depth {
static const int value = depth<typename U::parent>::value + 1;
};
template <typename U>
struct depth<U, U> {
static const int value = 0;
};
Выше будет в основном вычислить глубина вашего типа в вашем дереве.
Тогда вы могли бы использовать std::enable_if:
template <typename U, typename V, typename Enabler = void>
struct least_common_ancestor;
template <typename U>
struct least_common_ancestor<U, U> {
using type = U;
};
template <typename U, typename V>
struct least_common_ancestor<U, V,
typename std::enable_if<(depth<U>::value < depth<V>::value)>::type> {
using type = typename least_common_ancestor<U, typename V::parent>::type;
};
template <typename U, typename V>
struct least_common_ancestor<U, V,
typename std::enable_if<(depth<V>::value < depth<U>::value)>::type> {
using type = typename least_common_ancestor<V, typename U::parent>::type;
};
template <typename U, typename V>
struct least_common_ancestor<U, V,
typename std::enable_if<!std::is_same<U, V>::value && (depth<V>::value == depth<U>::value)>::type> {
using type = typename least_common_ancestor<typename V::parent, typename U::parent>::type;
};
Выход:
int main(int, char *[]) {
std::cout << std::is_same<least_common_ancestor<A, B>::type, E>::value << std::endl;
std::cout << std::is_same<least_common_ancestor<C, D>::type, F>::value << std::endl;
std::cout << std::is_same<least_common_ancestor<A, E>::type, E>::value << std::endl;
std::cout << std::is_same<least_common_ancestor<A, F>::type, G>::value << std::endl;
std::cout << std::is_same<least_common_ancestor<A, A>::type, A>::value << std::endl;
return 0;
}
дает:
1 1 1 1 1
Возможно, это можно улучшить, но можно использовать в качестве отправной точки.
Другие решения
template <typename...> struct typelist {};
template <typename T, typename... Ts>
struct path : path<typename T::parent, T, Ts...> {};
template <typename T, typename... Ts>
struct path<T, T, Ts...> { using type = typelist<T, Ts...>; };
template <typename T, typename U>
struct least;
template <typename T, typename... Vs, typename... Us>
struct least<typelist<T, Vs...>, typelist<T, Us...>> { using type = T; };
template <typename T, typename W, typename... Vs, typename... Us>
struct least<typelist<T, W, Vs...>, typelist<T, W, Us...>>
: least<typelist<W, Vs...>, typelist<W, Us...>> {};
template <typename V, typename U>
using least_common_ancestor = least<typename path<V>::type, typename path<U>::type>;
-
Вверху вверх: формы путей (
path::type) от обоих узлов до корня посредством добавления списка типов на каждом уровне (path<?, T, Ts...>), до тех порparentравен текущему обработанному узлу (<T, T, ?...>). Перемещение вверх выполняется заменойTотT::parent, -
Сверху вниз: спускать два списка типов одновременно (
least), пока не будет несоответствия в соответствующих позициях (Vs..., Us...); если это так, последний общий узел является общим предком (T); иначе (<T, W, ?...>, <T, W, ?...>), удалите соответствующий узел (T) и шаг на один уровень вниз (сейчасWпоследний известный общий узел).
Это, вероятно, не самый алгоритмически эффективный подход, но он функционален.
Во-первых, мы собираемся создать списки из предков каждого типа. Таким образом, для A это было бы <A,E,G> и для G это было бы <G>:
template <class X>
using parent_t = typename X::parent;
template <class... > struct typelist {};
template <class T> struct tag_t { using type = T; };
template <class, class> struct concat;
template <class X, class Y> using concat_t = typename concat<X, Y>::type;
template <class... Xs, class... Ys>
struct concat<typelist<Xs...>, typelist<Ys...>>
: tag_t<typelist<Xs..., Ys...>>
{ };
template <class X, class = parent_t<X>>
struct ancestors
: tag_t<concat_t<typelist<X>, typename ancestors<parent_t<X>>::type>>
{ };
template <class X>
struct ancestors<X, X>
: tag_t<typelist<X>>
{ };
template <class X>
using ancestors_t = typename ancestors<X>::type;
Тогда наименее общий предок из двух узлов просто будет первым узлом в предках одного узла, который содержится в предках другого узла:
template <class X, class TL> struct contains;
template <class X, class TL> using contains_t = typename contains<X, TL>::type;
template <class X, class... Xs>
struct contains<X, typelist<X, Xs...>> : std::true_type { };
template <class X, class Y, class... Xs>
struct contains<X, typelist<Y, Xs...>> : contains_t<X, typelist<Xs...>> { };
template <class X>
struct contains<X, typelist<>> : std::false_type { };
template <class X, class Y>
struct lca_impl;
template <class X, class Y>
struct lca : lca_impl<ancestors_t<X>, ancestors_t<Y>> { };
template <class X, class... Xs, class TL>
struct lca_impl<typelist<X, Xs...>, TL>
: tag_t<
typename std::conditional_t<contains_t<X, TL>::value,
tag_t<X>,
lca_impl<typelist<Xs...>, TL>
>::type
>
{ };template <class X, class Y>
using lca_t = typename lca<X, Y>::type;
какое поведение вы ожидаете:
static_assert(std::is_same<lca_t<A, E>, E>{}, "!");
static_assert(std::is_same<lca_t<A, D>, G>{}, "!");