proto/transform/fold.hpp

0001 ///////////////////////////////////////////////////////////////////////////////
0002 /// \file fold.hpp
0003 /// Contains definition of the fold<> and reverse_fold<> transforms.
0004 //
0005 //  Copyright 2008 Eric Niebler. Distributed under the Boost
0006 //  Software License, Version 1.0. (See accompanying file
0007 //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0008
0009 #ifndef BOOST_PROTO_TRANSFORM_FOLD_HPP_EAN_11_04_2007
0010 #define BOOST_PROTO_TRANSFORM_FOLD_HPP_EAN_11_04_2007
0011
0012 #include <boost/preprocessor/cat.hpp>
0013 #include <boost/preprocessor/iteration/iterate.hpp>
0014 #include <boost/preprocessor/arithmetic/inc.hpp>
0015 #include <boost/preprocessor/arithmetic/sub.hpp>
0016 #include <boost/preprocessor/repetition/repeat.hpp>
0017 #include <boost/fusion/include/fold.hpp>
0018 #include <boost/fusion/include/reverse_fold.hpp>
0019 #include <boost/proto/proto_fwd.hpp>
0020 #include <boost/proto/traits.hpp>
0021 #include <boost/proto/transform/impl.hpp>
0022 #include <boost/proto/transform/when.hpp>
0023
0024 namespace boost { namespace proto
0025 {
0026     namespace detail
0027     {
0028         template<typename Transform, typename Data>
0029         struct as_callable
0030         {
0031             as_callable(Data d)
0032               : d_(d)
0033             {}
0034
0035             template<typename Sig>
0036             struct result;
0037
0038             template<typename This, typename State, typename Expr>
0039             struct result<This(State, Expr)>
0040             {
0041                 typedef
0042                     typename when<_, Transform>::template impl<Expr, State, Data>::result_type
0043                 type;
0044             };
0045
0046             template<typename State, typename Expr>
0047             typename when<_, Transform>::template impl<Expr &, State const &, Data>::result_type
0048             operator ()(State const &s, Expr &e) const
0049             {
0050                 return typename when<_, Transform>::template impl<Expr &, State const &, Data>()(e, s, this->d_);
0051             }
0052
0053         private:
0054             Data d_;
0055         };
0056
0057         template<
0058             typename State0
0059           , typename Fun
0060           , typename Expr
0061           , typename State
0062           , typename Data
0063           , long Arity = arity_of<Expr>::value
0064         >
0065         struct fold_impl
0066         {};
0067
0068         template<
0069             typename State0
0070           , typename Fun
0071           , typename Expr
0072           , typename State
0073           , typename Data
0074           , long Arity = arity_of<Expr>::value
0075         >
0076         struct reverse_fold_impl
0077         {};
0078
0079         #include <boost/proto/transform/detail/fold_impl.hpp>
0080
0081     } // namespace detail
0082
0083     /// \brief A PrimitiveTransform that invokes the <tt>fusion::fold\<\></tt>
0084     /// algorithm to accumulate
0085     template<typename Sequence, typename State0, typename Fun>
0086     struct fold : transform<fold<Sequence, State0, Fun> >
0087     {
0088         template<typename Expr, typename State, typename Data>
0089         struct impl : transform_impl<Expr, State, Data>
0090         {
0091             /// \brief A Fusion sequence.
0092             typedef
0093                 typename remove_reference<
0094                     typename when<_, Sequence>::template impl<Expr, State, Data>::result_type
0095                 >::type
0096             sequence;
0097
0098             /// \brief An initial state for the fold.
0099             typedef
0100                 typename remove_reference<
0101                     typename when<_, State0>::template impl<Expr, State, Data>::result_type
0102                 >::type
0103             state0;
0104
0105             /// \brief <tt>fun(d)(e,s) == when\<_,Fun\>()(e,s,d)</tt>
0106             typedef
0107                 detail::as_callable<Fun, Data>
0108             fun;
0109
0110             typedef
0111                 typename fusion::result_of::fold<
0112                     sequence
0113                   , state0
0114                   , fun
0115                 >::type
0116             result_type;
0117
0118             /// Let \c seq be <tt>when\<_, Sequence\>()(e, s, d)</tt>, let
0119             /// \c state0 be <tt>when\<_, State0\>()(e, s, d)</tt>, and
0120             /// let \c fun(d) be an object such that <tt>fun(d)(e, s)</tt>
0121             /// is equivalent to <tt>when\<_, Fun\>()(e, s, d)</tt>. Then, this
0122             /// function returns <tt>fusion::fold(seq, state0, fun(d))</tt>.
0123             ///
0124             /// \param e The current expression
0125             /// \param s The current state
0126             /// \param d An arbitrary data
0127             result_type operator ()(
0128                 typename impl::expr_param   e
0129               , typename impl::state_param  s
0130               , typename impl::data_param   d
0131             ) const
0132             {
0133                 typename when<_, Sequence>::template impl<Expr, State, Data> seq;
0134                 detail::as_callable<Fun, Data> f(d);
0135                 return fusion::fold(
0136                     seq(e, s, d)
0137                   , typename when<_, State0>::template impl<Expr, State, Data>()(e, s, d)
0138                   , f
0139                 );
0140             }
0141         };
0142     };
0143
0144     /// \brief A PrimitiveTransform that is the same as the
0145     /// <tt>fold\<\></tt> transform, except that it folds
0146     /// back-to-front instead of front-to-back.
0147     template<typename Sequence, typename State0, typename Fun>
0148     struct reverse_fold  : transform<reverse_fold<Sequence, State0, Fun> >
0149     {
0150         template<typename Expr, typename State, typename Data>
0151         struct impl : transform_impl<Expr, State, Data>
0152         {
0153             /// \brief A Fusion sequence.
0154             typedef
0155                 typename remove_reference<
0156                     typename when<_, Sequence>::template impl<Expr, State, Data>::result_type
0157                 >::type
0158             sequence;
0159
0160             /// \brief An initial state for the fold.
0161             typedef
0162                 typename remove_reference<
0163                     typename when<_, State0>::template impl<Expr, State, Data>::result_type
0164                 >::type
0165             state0;
0166
0167             /// \brief <tt>fun(d)(e,s) == when\<_,Fun\>()(e,s,d)</tt>
0168             typedef
0169                 detail::as_callable<Fun, Data>
0170             fun;
0171
0172             typedef
0173                 typename fusion::result_of::reverse_fold<
0174                     sequence
0175                   , state0
0176                   , fun
0177                 >::type
0178             result_type;
0179
0180             /// Let \c seq be <tt>when\<_, Sequence\>()(e, s, d)</tt>, let
0181             /// \c state0 be <tt>when\<_, State0\>()(e, s, d)</tt>, and
0182             /// let \c fun(d) be an object such that <tt>fun(d)(e, s)</tt>
0183             /// is equivalent to <tt>when\<_, Fun\>()(e, s, d)</tt>. Then, this
0184             /// function returns <tt>fusion::fold(seq, state0, fun(d))</tt>.
0185             ///
0186             /// \param e The current expression
0187             /// \param s The current state
0188             /// \param d An arbitrary data
0189             result_type operator ()(
0190                 typename impl::expr_param   e
0191               , typename impl::state_param  s
0192               , typename impl::data_param   d
0193             ) const
0194             {
0195                 typename when<_, Sequence>::template impl<Expr, State, Data> seq;
0196                 detail::as_callable<Fun, Data> f(d);
0197                 return fusion::reverse_fold(
0198                     seq(e, s, d)
0199                   , typename when<_, State0>::template impl<Expr, State, Data>()(e, s, d)
0200                   , f
0201                 );
0202             }
0203         };
0204     };
0205
0206     // This specialization is only for improved compile-time performance
0207     // in the commom case when the Sequence transform is \c proto::_.
0208     //
0209     /// INTERNAL ONLY
0210     ///
0211     template<typename State0, typename Fun>
0212     struct fold<_, State0, Fun> : transform<fold<_, State0, Fun> >
0213     {
0214         template<typename Expr, typename State, typename Data>
0215         struct impl
0216           : detail::fold_impl<State0, Fun, Expr, State, Data>
0217         {};
0218     };
0219
0220     // This specialization is only for improved compile-time performance
0221     // in the commom case when the Sequence transform is \c proto::_.
0222     //
0223     /// INTERNAL ONLY
0224     ///
0225     template<typename State0, typename Fun>
0226     struct reverse_fold<_, State0, Fun> : transform<reverse_fold<_, State0, Fun> >
0227     {
0228         template<typename Expr, typename State, typename Data>
0229         struct impl
0230           : detail::reverse_fold_impl<State0, Fun, Expr, State, Data>
0231         {};
0232     };
0233
0234     /// INTERNAL ONLY
0235     ///
0236     template<typename Sequence, typename State, typename Fun>
0237     struct is_callable<fold<Sequence, State, Fun> >
0238       : mpl::true_
0239     {};
0240
0241     /// INTERNAL ONLY
0242     ///
0243     template<typename Sequence, typename State, typename Fun>
0244     struct is_callable<reverse_fold<Sequence, State, Fun> >
0245       : mpl::true_
0246     {};
0247
0248 }}
0249
0250 #endif