Boost logo

Boost :

Subject: Re: [boost] Interest in flat_iterator for nested containers?
From: Jeffrey Hellrung (jhellrung_at_[hidden])
Date: 2009-09-28 14:05:11


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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk