Re: [Boost-users] [mpl] Implementing includes_if

From: Tobias Schwinger (tschwinger_at_[hidden])
Date: 2007-03-17 19:31:57

Scott Meyers wrote:
> I want to implement this:
> 
> // returns whether Seq1 includes each of the elements in Seq2
> // using Pred to determine type equality
> template<typename Seq1,  // the putative superset
>           typename Seq2,  // the putative subset
>           typename Pred>  // whether T1 from Seq1 == T2 from Seq2
> struct includes_if;

OK.

> 
> My ultimate goal is to be able to determine whether every element in 
> Seq2 is either in Seq1 or has a base class in Seq1.  So the predicate 
> I'll be passing in is a metafunction class that invokes 
> std::tr1::is_base_of.
> 
> Here's my code, all but one line of which is supposed to be correct:
> 
> template<typename Seq1,  // the putative superset
>           typename Seq2,  // the putative subset
>           typename Pred>  // whether T1 from Seq1 == T2 from Seq2
> struct includes_if
> : boost::is_same<
>      typename mpl::find_if<
>        Seq2,
>        mpl::not_<mpl::contains_if<Seq1,
>                                   lambda(T) is_base_of<mpl::_1, T>  //!!
>                                   > >
>      >::type,
>      typename mpl::end<Seq2>::type
>    >
> {};
> 
> The line I don't know how to write is flagged, but the functionality I 
> want to express is shown.
> 
> In case it's relevant, here is the rest of my code:
> 
> // metafunction class for TR1-conforming is_base_of
> struct is_base_of {
>    template<typename T1, typename T2>
>    struct apply: std::tr1::is_base_of<T1, T2> {};
> };

Wouldn't it be nicer if 'is_base_of<_1,_2>' would just work for the 
predicate?

I'll add it to our requirements.

> // returns whether Seq contains an element satisfying Pred
> template<typename Seq, typename Pred>
> struct contains_if
> : mpl::not_<
>      boost::is_same<
>        typename mpl::find_if< Seq, mpl::apply<Pred, mpl::_1> >::type,
>        typename mpl::end<Seq>::type
>      >
>    >
> {};

This is a nice starting point. Let's simplify away the mpl::apply and 
just pass on the predicate. Let's also be 'using namespace boost::mpl' 
here for readability.

     template<typename Seq, typename Pred>
     struct contains_if
       : not_< is_same<typename find_if<Seq,Pred>::type,
             typename end<Seq>::type> >
     { };

     // test it
     typedef vector<int> v1;
     BOOST_MPL_ASSERT(( contains_if<v1,is_same<_1,int> > ));
     BOOST_MPL_ASSERT_NOT(( contains_if<v1,is_same<_1,char> > ));

Now, includes_if would look roughly like an earlier version you posted, 
with pseudo code portions, for now:

     template<typename SuperSeq, typename SubSeq, typename Pred>
     struct includes_if
       : not_< contains_if< SubSeq,
             not_< contains_if< SuperSeq, apply< PRED,
                 INNER_1, OUTER_1> > > > >
     { };

The problem comes down to that MPL can't know where one placeholder 
expression starts and where another one ends (denoted by uppercase 
identifiers, above):

1. how do we distinguish between the outer and inner '_1'?
2. 'Pred' should be allowed to be a placeholder expression,
    such as 'is_same<_1,_2>'

Let's introduce another class template that encapsulates above 
'contains_if' with a binary, partially bound predicate:

     namespace detail
     {
         template<typename S, typename T, typename Pred>
         struct contains_if_is
           : contains_if< S, bind<Pred,T,_1> >
         { };
     }

     template<typename SuperSeq, typename SubSeq, typename Pred>
     struct includes_if
       : not_< contains_if< SubSeq,
             not_< detail::contains_if_is<SuperSeq,_1,

Wait a minute! So far it solves problem 1. For problem 2 we have to 
remove the placeholders from the predicate by making sure it is a 
Metafunction Class using the lambda Metafunction.

                 typename lambda<Pred>::type > > > >
     { };

     // test it
     typedef vector<int> v1;
     typedef vector<int,char> v2;
     BOOST_MPL_ASSERT(( includes_if<v2, v1, is_same<_1,_2> > ));
     BOOST_MPL_ASSERT_NOT(( includes_if<v1, v2, is_same<_1,_2> > ));

That's it.

I've been toying with 'protect' to get everything done in one class 
template, but I couldn't quite figure it out. I remember several posts 
on this list with similar scenarios, but no one with a working answer. 
It seems 'protect' is exactly the right thing for these cases, but 
there's a "FIXME" comment in the reference, the description is very 
brief and trying things got me nowhere. So I'd be thankful if someone 
else would fill in this part (I'd be curious to know how 'protect' is 
supposed to be used even if it's not applicable in this particular case).

Regards,
Tobias