c++ - Lowest common ancestor in a linear lineage of types -
intro
let's suppose have linear hierarchy of types following:
then want a mechanism return lowest common ancestor out of arbitrary number of types in lineage.
attempted code
template<typename...ts> struct lca; template<typename t1, typename t2, typename...ts> struct lca<t1, t2, ts...> { using base = typename std::conditional < std::is_base_of<t1, t2>::value, t1, typename std::conditional < std::is_base_of<t2, t1>::value, t2, void >::type >::type; using type = typename lca<base, ts...>::type; }; template<typename t> struct lca<t> { using type = t; }; use case
my use case rather typical: in making iterator tools want extract "most restrictive" iterator type, since there's (kind of) linear hierarchy in iterators should able ascent hierarchy as it's needed:
lca<bidirectional, randomaccess, randomaccess> -> bidirectional lca<randomaccess, input, forward> -> input questions
is there more concise / idiomatic way of handling of error case 2 or more types strangers hierarchy? current approach return
voidgive failure in contexts type used.is use of
basemember in first specialization problematic? should extract functionality in separate class , use inline intypemaintain uniformity?is there algorithm reduce number of instantiations? there better way pairwise comparisons, complexity of algorithm can reduced?
can scale non linear hierarchies , query depth hierarchy tree? "tie breaker" in case (for types in same level)?
1. technical aspect
i'd use derivation, because cleaner type definitions. here example code:
#include <iostream> #include <typeinfo> #include <type_traits> struct grandma {}; struct mom : grandma {}; struct daughter : mom {}; struct son : mom {}; struct grandchild : son {}; struct stranger {}; namespace detail { struct typeisnotpartofthehierarchy {}; template<typename t> struct typewrapper { static_assert(!std::is_same<typeisnotpartofthehierarchy, t>::value, "using types of different type hierarchies."); using type = t; }; } template<typename... ts> struct lca; template<typename t> struct lca<t>: detail::typewrapper<t> {}; template<typename t1, typename t2> struct lca<t1, t2>: std::conditional < std::is_base_of<t1, t2>::value, detail::typewrapper<t1>, typename std::conditional < std::is_base_of<t2, t1>::value, detail::typewrapper<t2>, detail::typewrapper<detail::typeisnotpartofthehierarchy> >::type >::type {}; template<typename t1, typename... ts> struct lca<t1, ts...>: lca<t1, typename lca<ts...>::type> {}; int main() { std::cout << typeid(lca<son, mom, grandchild, grandma, son, son>::type).name() << std::endl; std::cout << typeid(lca<son>::type).name() << std::endl; // error because daughter , son siblings. // std::cout << typeid(lca<son, daughter, son>::type).name() << std::endl; // error because son not related stranger. // std::cout << typeid(lca<son, stranger, son>::type).name() << std::endl; return 0; } technically use std::enable_if instead of std::condition, using std::enable_if mean, have derive if-true, if-false , if-types-not-compatible case. using std::condition imho more readable. type has wrapped once more have type, enabled conditions , deliver typedef using outside.
in order compilation error, statically asserting give nice message instead of difficult template errors in compiler output. free use void signalize error. recommend use type name error. improves readability.
2. base type
i think base member should hidden, because else reveal more needed users , may confuse them. use of type derivation solves issue.
3. complexity
i think, not possible improve complexity o(n). have check each type @ least once, if lca type. every type @ least once part of comparison.
4. other hierarchies (the beautiful part)
the implementation above (as yours too) makes no point on other hierarchies linear ones (e.g. lca<daughter, grandma, son> return grandma while lca<grandma, daughter, son>::type result in error, because neighbour types compared).
however there 2 types of "branching inheritance" in c++ possible (and mixing of course):
tree multiple roots:
struct dad {}; struct mom {}; struct son: dad, mom {}; for several cases lca undefined (e.g. lca<mom, dad>::type guess, mom , dad not share same parents). recommend drop case.
tree 1 root:
struct mom {}; struct son: mom {}; struct daughter: mom {}; i recommend, algorithm returns type, if there 1 type in list, types casted (e.g. lca<son, daughter>::type has no lca, because hope siblings). search type in list base type of others.
because neighbour types compared each other above, comparison has extended compare every type each other (sadly o(n^2)). basic idea check every type, if common ancestor other types. case lca. btw: solving way has advantage, because error in "multiple roots"-scenario, correct result, if multiple roots joining again in common root (that part of list).
we need first of functionality, determines whether 1 type base type of other or not:
template<typename stillcommonancestor, typename typetocheck, typename... ts> struct iscommonancestor; template<typename stillcommonancestor, typename typetocheck> struct iscommonancestor<stillcommonancestor, typetocheck> { static constexpr bool value = stillcommonancestor::value; }; template<typename stillcommonancestor, typename typetocheck, typename t1, typename... ts> struct iscommonancestor<stillcommonancestor, typetocheck, t1, ts...>: iscommonancestor < std::integral_constant < bool, std::conditional < std::is_base_of<typetocheck, t1>::value, std::true_type, std::false_type >::type::value && stillcommonancestor::value >, typetocheck, ts... > {}; to check whether type common ancestor of others, use iscommonancestor<std::true_type, mom, grandchild, daughter, son>::value (which here true, while iscommonancestor<std::true_type, grandchild, grandchild, daughter, son>::value false). note that, value false, if 1 type not part of type hierarchy.
then "facility" needed, iterate through types , catch one, iscommonancestor<...>::value true:
template<typename pack, typename... ts> struct lca; template<typename... packparams, typename t1> struct lca<std::tuple<packparams...>, t1>: std::conditional < iscommonancestor<std::true_type, t1, packparams...>::value, typewrapper<t1>, typewrapper<typeisnotpartofthehierarchy> >::type {}; template<typename... packparams, typename t1, typename... ts> struct lca<std::tuple<packparams...>, t1, ts...>: std::conditional < iscommonancestor<std::true_type, t1, packparams...>::value, typewrapper<t1>, lca<std::tuple<packparams...>, ts...> >::type {}; the lca compares every element whole template parameter pack. first base type of used. if last no base type of others, lca derives again typewrapper<typeisnotpartofthehierarchy>, raise typical static assertion.
this 1 inconvenient. wrapper fix this:
template<typename... ts> struct lca: detail::lca<std::tuple<ts...>, ts...> {}; complete code lca of tree available here: http://ideone.com/pyepyl
Comments
Post a Comment