Christoph Heindl wrote:
out of curiosity I've implemented the 'widest convertible' meta-function as reformulated greatest common divisor problem (called it widest_convertible_traversal_cat as you suggested though :). It works by declaring a bidirectional mapping from category to id and vice versa. If ids are chosen to be the powers of two then the widest convertible traversal category is the greatest common divisor of both category ids.
Clever! Though in this instance, the minimum is identical to the gcd, at which point you could just assign the traversal tags to consecutive integers ;) But this is something I'll have to keep in mind for any fixed class hierarchy, as the gcd could provide a nice way to compute the "least common ancestor". The widest_convertible metafunction I have is slower than one specialized for a linear hiearchy (O(n^2) instead of O(n)), and based on boost::is_convertible. See below.
The code consists of a few lines of code (reusing boost::math::static_gcd) and should be quite fast as far as compile time is concerned (assuming euclids gcd algorithm is used it takes a single iteration). It might be the fastest solution, but a quite elegant one (I think) :)
Please find my code with complete test suite attached.
Do you think that piece of code might be of general interest?
It would be much more useful if it were variadic, either taking a variable number of template parameters or (my preference) accepting a Boost.MPL sequence of traversal tags. -------- #include <boost/mpl/begin_end.hpp> #include <boost/mpl/deref.hpp> #include <boost/mpl/find_if.hpp> #include <boost/mpl/not.hpp> #include <boost/mpl/placeholders.hpp> #include <boost/type_traits/is_convertible.hpp> #include <boost/type_traits/is_same.hpp> namespace detail_widest_convertible { template< class Sequence, class T > struct all_are_convertible : boost_ext::mpl::satisfies_all< Sequence, boost::is_convertible< boost::mpl::_1, T > > { }; } // namespace detail_widest_convertible template< class Sequence > struct has_widest_convertible : boost::mpl::not_< boost::is_same< typename boost::mpl::end< Sequence >::type, typename boost::mpl::find_if< Sequence, detail_widest_convertible::all_are_convertible< Sequence, boost::mpl::_1 > >::type > > { }; template< class Sequence > struct widest_convertible : boost::mpl::deref< typename boost::mpl::find_if< Sequence, detail_widest_convertible::all_are_convertible< Sequence, boost::mpl::_1 > >::type > { }; -------- where satisfies_all is a Boost.MPL metafunction defined as follows: -------- #include <boost/mpl/begin_end.hpp> #include <boost/mpl/bind.hpp> #include <boost/mpl/find_if.hpp> #include <boost/mpl/lambda.hpp> #include <boost/mpl/not.hpp> #include <boost/mpl/placeholders.hpp> #include <boost/mpl/quote.hpp> #include <boost/type_traits/is_same.hpp> namespace boost_ext { namespace mpl { template< class Sequence, class Pred > struct satisfies_all : boost::is_same< typename boost::mpl::find_if< Sequence, boost::mpl::bind< boost::mpl::quote1< boost::mpl::not_ >, boost::mpl::bind< typename boost::mpl::lambda< Pred >::type, boost::mpl::_1 > > >::type, typename boost::mpl::end< Sequence >::type > { }; } // namespace mpl } // namespace boost_ext -------- - Jeff