Re: [boost] Interest in flat_iterator for nested containers?

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