Flatten a sequence of sequences (of sequences)

Question

I'm using boost::fusion.

Lets say I have something like the following:

make_vector(1, make_vector('b', 3, make_vector(4, 5.5), "six"), 7, 8)

I want to produce an function f such that

f(make_vector(1, make_vector('b', 3, make_vector(4, 5.5), "six"), 7, 8)) 
-> [1, 'b', 3, 4, 5.5, "six", 7, 8]

i.e. a flattened version of the sequence.

I don't mind if this is a view of the original sequence or an actual vector.

I don't mind a solution in C++0x if it can compile on GCC 4.5.1.

Note:

Whilst I'd prefer not to restrict the data elements, if it helps, feel free to require that the "data" elements all derive from a common base class.

i.e.

class DataBase {}

template <class T>
class Data : public DataBase
{
public:
  Data(const T& x) : m_x(x)
  T m_x;
}

template <class T>
T make_data(const T& x) { return Data<T>(x); }

Then

make_vector(
  make_data(1), 
  make_vector(
    make_data('b'), 
    make_data(3), 
    make_vector(
      make_data(4), 
      make_data(5.5)
    ), 
    make_data("six")
  ), 
  make_data(7), 
  make_data(8)
)

I figure then you can work out what the data elements are by using "is_base_of".

Answer 1

Here is one possible solution, that uses join recursively. Basically, it does the following (in pseudo-Haskell):

flatten []     = []
flatten x      = [x]
flatten (x:xs) = flatten x ++ flatten xs

Recursively, the flattened head is concatenated to the flattened tail.

This solution is very likely not the most efficient one since it constructs many views, even for single values; a better approach could be passing the resulting sequence as a parameter in recursive calls and directly add the individual elements in it, perhaps using fold.

Here is the code (disclaimer: I wrote this quite quickly, so the code could be filled with bugs and/or non-idiomatic ways of doing things):

namespace result_of
{
    template < typename Begin, typename End, class Enable = void >
    struct flatten_impl
    {
        typedef boost::fusion::single_view< typename 
            boost::fusion::result_of::value_of< Begin >::type 
        > flattenedHeadSequence;

        typedef typename 
            flatten_impl< typename
                boost::fusion::result_of::next< Begin >::type,
                End
            >::type flattenedTailSequence;

        typedef typename boost::fusion::result_of::join< const flattenedHeadSequence, const flattenedTailSequence >::type type;
    };


    template < typename Begin, typename End >
    struct flatten_impl< 
        Begin, 
        End, typename
        boost::enable_if< 
            boost::fusion::traits::is_sequence< typename
                boost::fusion::result_of::value_of< Begin >::type
            >
        >::type 
    >
    {
        typedef typename boost::fusion::result_of::value_of< Begin >::type headSequence;
        typedef typename 
            flatten_impl< typename
                boost::fusion::result_of::begin< headSequence >::type, typename
                boost::fusion::result_of::end< headSequence >::type 
            >::type flattenedHeadSequence;

        typedef typename 
            flatten_impl< typename
                boost::fusion::result_of::next< Begin >::type,
                End
            >::type flattenedTailSequence;

        typedef typename boost::fusion::result_of::join< const flattenedHeadSequence, const flattenedTailSequence >::type type;
    };


    template < typename End, typename Enable >
    struct flatten_impl< End, End, Enable >
    {
        typedef boost::fusion::vector< > type;
    };


    template < typename Sequence >
    struct flatten
    {
        typedef typename 
            flatten_impl< typename 
                boost::fusion::result_of::begin< Sequence >::type, typename 
                boost::fusion::result_of::end< Sequence >::type 
            >::type type;
    };    
}


template < typename Begin, typename End >
typename result_of::flatten_impl< Begin, End >::type 
flatten_impl( 
    const Begin & begin, 
    const End & end, typename 
    boost::disable_if<
        boost::fusion::traits::is_sequence< typename
            boost::fusion::result_of::value_of< Begin >::type
        >
    >::type * dummy = 0 )
{
    typedef result_of::flatten_impl< Begin, End > traits;
    typedef typename traits::flattenedHeadSequence headSequence;
    typedef typename traits::flattenedTailSequence tailSequence;

    return boost::fusion::join( 
        headSequence( boost::fusion::deref( begin ) ),
        flatten_impl( boost::fusion::next( begin ), end ) );
}


template < typename Begin, typename End >
typename result_of::flatten_impl< Begin, End >::type 
flatten_impl( 
    const Begin & begin, 
    const End & end, typename 
    boost::enable_if<
        boost::fusion::traits::is_sequence< typename
            boost::fusion::result_of::value_of< Begin >::type
        >
    >::type * dummy = 0 )
{
    typedef result_of::flatten_impl< Begin, End > traits;
    typedef typename traits::flattenedHeadSequence headSequence;
    typedef typename traits::flattenedTailSequence tailSequence;

    typedef typename boost::fusion::result_of::value_of< Begin >::type headType;

    const headType & head = boost::fusion::deref( begin );

    return boost::fusion::join(
        flatten_impl( boost::fusion::begin( head ), boost::fusion::end( head ) ),
        flatten_impl( boost::fusion::next( begin ), end ) );
}


template < typename End >
typename result_of::flatten_impl< End, End >::type
flatten_impl( const End &, const End &)
{
    return boost::fusion::make_vector( );
}


template < typename Sequence >
typename result_of::flatten< Sequence >::type 
flatten( const Sequence & seq )
{
    return flatten_impl( boost::fusion::begin( seq ), boost::fusion::end( seq ) );
}