c++ - ver - visual studio 2017 no muestra los errores

Determine el antepasado menos común en tiempo de compilación

Question

Hay toneladas de preguntas sobre el algoritmo ancestral menos común, pero este es diferente porque estoy tratando de determinar el LCA en tiempo de compilación, y mi árbol no es binario ni un árbol de búsqueda , aunque mi versión simplificada pueda parecer uno.

Supongamos que tiene un montón de estructuras que contienen un miembro typedef parent , que es otra estructura similar:

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

que juntos hacen un árbol como

A    B    C    D
 /  /      /  /
  E         F
   /       /
    /     /
     /   /
       G

NOTA: No hay relación de herencia entre las estructuras.

Lo que me gustaría hacer es crear un rasgo de tipo least_common_ancestor tal que:

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

¿Cuál es la mejor manera de hacer esto?

No me preocupa la complejidad algorítmica, particularmente porque la profundidad del árbol es pequeña, sino que busco el meta-programa más simple que llegue a la respuesta correcta.

EDITAR: Necesito poder construir la solución con msvc2013, entre otros compiladores, por constexpr se prefieren las respuestas sin constexpr .

Answer 1

Es probable que esto se haya mejorado, pero primero podrías calcular la profundidad de tu tipo y luego usar esta información para subir una rama o la otra:

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

Lo anterior básicamente calculará la profundidad de su tipo en su árbol.

Entonces podrías usar 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;
};

Salida:

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

Da:

1 1 1 1 1

Probablemente esto podría mejorarse, pero podría usarse como un punto de partida.

Answer 2

Probablemente este no sea el enfoque más algorítmicamente eficiente, pero es funcional.

Primero, vamos a crear listas de los ancestros de cada tipo. Entonces para A esto sería <A,E,G> y para G sería <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;

Entonces, el ancestro menos común de dos nodos será el primer nodo en los ancestros de un nodo que está contenido en los ancestros del otro nodo:

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;

que tiene el comportamiento que cabría esperar:

static_assert(std::is_same<lca_t<A, E>, E>{}, "!");
static_assert(std::is_same<lca_t<A, D>, G>{}, "!");

Answer 3

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

DEMO

1. Abajo: Forme rutas ( path::type ) desde ambos nodos a la raíz mediante la preparación de una lista de tipos en cada nivel ( path<?, T, Ts...> ), hasta que el parent igual al nodo procesado actualmente ( <T, T, ?...> ). El movimiento hacia arriba se realiza reemplazando T por T::parent .

2. De arriba a abajo: descienda las dos listas de tipos simultáneamente ( least ), hasta que haya una falta de coincidencia en las posiciones correspondientes ( Vs..., Us... ); si es así, el último nodo común es el ancestro común ( T ); de lo contrario ( <T, W, ?...>, <T, W, ?...> ), elimine el nodo correspondiente ( T ) y el primer paso hacia abajo (ahora W es el último nodo común conocido).