proto/transform/fold_tree.hpp

0001 ///////////////////////////////////////////////////////////////////////////////
0002 /// \file fold_tree.hpp
0003 /// Contains definition of the fold_tree<> and reverse_fold_tree<> 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_TREE_HPP_EAN_11_05_2007
0010 #define BOOST_PROTO_TRANSFORM_FOLD_TREE_HPP_EAN_11_05_2007
0011
0012 #include <boost/type_traits/is_same.hpp>
0013 #include <boost/proto/proto_fwd.hpp>
0014 #include <boost/proto/traits.hpp>
0015 #include <boost/proto/matches.hpp>
0016 #include <boost/proto/transform/fold.hpp>
0017 #include <boost/proto/transform/impl.hpp>
0018
0019 namespace boost { namespace proto
0020 {
0021     namespace detail
0022     {
0023         template<typename Tag>
0024         struct has_tag
0025         {
0026             template<typename Expr, typename State, typename Data, typename EnableIf = Tag>
0027             struct impl
0028             {
0029                 typedef mpl::false_ result_type;
0030             };
0031
0032             template<typename Expr, typename State, typename Data>
0033             struct impl<Expr, State, Data, typename Expr::proto_tag>
0034             {
0035                 typedef mpl::true_ result_type;
0036             };
0037
0038             template<typename Expr, typename State, typename Data>
0039             struct impl<Expr &, State, Data, typename Expr::proto_tag>
0040             {
0041                 typedef mpl::true_ result_type;
0042             };
0043         };
0044
0045         template<typename Tag, typename Fun>
0046         struct fold_tree_
0047           : if_<has_tag<Tag>, fold<_, _state, fold_tree_<Tag, Fun> >, Fun>
0048         {};
0049
0050         template<typename Tag, typename Fun>
0051         struct reverse_fold_tree_
0052           : if_<has_tag<Tag>, reverse_fold<_, _state, reverse_fold_tree_<Tag, Fun> >, Fun>
0053         {};
0054     }
0055
0056     /// \brief A PrimitiveTransform that recursively applies the
0057     /// <tt>fold\<\></tt> transform to sub-trees that all share a common
0058     /// tag type.
0059     ///
0060     /// <tt>fold_tree\<\></tt> is useful for flattening trees into lists;
0061     /// for example, you might use <tt>fold_tree\<\></tt> to flatten an
0062     /// expression tree like <tt>a | b | c</tt> into a Fusion list like
0063     /// <tt>cons(c, cons(b, cons(a)))</tt>.
0064     ///
0065     /// <tt>fold_tree\<\></tt> is easily understood in terms of a
0066     /// <tt>recurse_if_\<\></tt> helper, defined as follows:
0067     ///
0068     /// \code
0069     /// template<typename Tag, typename Fun>
0070     /// struct recurse_if_
0071     ///   : if_<
0072     ///         // If the current node has type "Tag" ...
0073     ///         is_same<tag_of<_>, Tag>()
0074     ///         // ... recurse, otherwise ...
0075     ///       , fold<_, _state, recurse_if_<Tag, Fun> >
0076     ///         // ... apply the Fun transform.
0077     ///       , Fun
0078     ///     >
0079     /// {};
0080     /// \endcode
0081     ///
0082     /// With <tt>recurse_if_\<\></tt> as defined above,
0083     /// <tt>fold_tree\<Sequence, State0, Fun\>()(e, s, d)</tt> is
0084     /// equivalent to
0085     /// <tt>fold<Sequence, State0, recurse_if_<Expr::proto_tag, Fun> >()(e, s, d).</tt>
0086     /// It has the effect of folding a tree front-to-back, recursing into
0087     /// child nodes that share a tag type with the parent node.
0088     template<typename Sequence, typename State0, typename Fun>
0089     struct fold_tree
0090       : transform<fold_tree<Sequence, State0, Fun> >
0091     {
0092         template<typename Expr, typename State, typename Data>
0093         struct impl
0094           : fold<
0095                 Sequence
0096               , State0
0097               , detail::fold_tree_<typename Expr::proto_tag, Fun>
0098             >::template impl<Expr, State, Data>
0099         {};
0100
0101         template<typename Expr, typename State, typename Data>
0102         struct impl<Expr &, State, Data>
0103           : fold<
0104                 Sequence
0105               , State0
0106               , detail::fold_tree_<typename Expr::proto_tag, Fun>
0107             >::template impl<Expr &, State, Data>
0108         {};
0109     };
0110
0111     /// \brief A PrimitiveTransform that recursively applies the
0112     /// <tt>reverse_fold\<\></tt> transform to sub-trees that all share
0113     /// a common tag type.
0114     ///
0115     /// <tt>reverse_fold_tree\<\></tt> is useful for flattening trees into
0116     /// lists; for example, you might use <tt>reverse_fold_tree\<\></tt> to
0117     /// flatten an expression tree like <tt>a | b | c</tt> into a Fusion list
0118     /// like <tt>cons(a, cons(b, cons(c)))</tt>.
0119     ///
0120     /// <tt>reverse_fold_tree\<\></tt> is easily understood in terms of a
0121     /// <tt>recurse_if_\<\></tt> helper, defined as follows:
0122     ///
0123     /// \code
0124     /// template<typename Tag, typename Fun>
0125     /// struct recurse_if_
0126     ///   : if_<
0127     ///         // If the current node has type "Tag" ...
0128     ///         is_same<tag_of<_>, Tag>()
0129     ///         // ... recurse, otherwise ...
0130     ///       , reverse_fold<_, _state, recurse_if_<Tag, Fun> >
0131     ///         // ... apply the Fun transform.
0132     ///       , Fun
0133     ///     >
0134     /// {};
0135     /// \endcode
0136     ///
0137     /// With <tt>recurse_if_\<\></tt> as defined above,
0138     /// <tt>reverse_fold_tree\<Sequence, State0, Fun\>()(e, s, d)</tt> is
0139     /// equivalent to
0140     /// <tt>reverse_fold<Sequence, State0, recurse_if_<Expr::proto_tag, Fun> >()(e, s, d).</tt>
0141     /// It has the effect of folding a tree back-to-front, recursing into
0142     /// child nodes that share a tag type with the parent node.
0143     template<typename Sequence, typename State0, typename Fun>
0144     struct reverse_fold_tree
0145       : transform<reverse_fold_tree<Sequence, State0, Fun> >
0146     {
0147         template<typename Expr, typename State, typename Data>
0148         struct impl
0149           : reverse_fold<
0150                 Sequence
0151               , State0
0152               , detail::reverse_fold_tree_<typename Expr::proto_tag, Fun>
0153             >::template impl<Expr, State, Data>
0154         {};
0155
0156         template<typename Expr, typename State, typename Data>
0157         struct impl<Expr &, State, Data>
0158           : reverse_fold<
0159                 Sequence
0160               , State0
0161               , detail::reverse_fold_tree_<typename Expr::proto_tag, Fun>
0162             >::template impl<Expr &, State, Data>
0163         {};
0164     };
0165
0166     /// INTERNAL ONLY
0167     ///
0168     template<typename Sequence, typename State0, typename Fun>
0169     struct is_callable<fold_tree<Sequence, State0, Fun> >
0170       : mpl::true_
0171     {};
0172
0173     /// INTERNAL ONLY
0174     ///
0175     template<typename Sequence, typename State0, typename Fun>
0176     struct is_callable<reverse_fold_tree<Sequence, State0, Fun> >
0177       : mpl::true_
0178     {};
0179
0180 }}
0181
0182 #endif