Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: /// \file fold_tree.hpp
Chris@16: /// Contains definition of the fold_tree<> and reverse_fold_tree<> transforms.
Chris@16: //
Chris@16: //  Copyright 2008 Eric Niebler. Distributed under the Boost
Chris@16: //  Software License, Version 1.0. (See accompanying file
Chris@16: //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_PROTO_TRANSFORM_FOLD_TREE_HPP_EAN_11_05_2007
Chris@16: #define BOOST_PROTO_TRANSFORM_FOLD_TREE_HPP_EAN_11_05_2007
Chris@16: 
Chris@16: #include <boost/type_traits/is_same.hpp>
Chris@16: #include <boost/proto/proto_fwd.hpp>
Chris@16: #include <boost/proto/traits.hpp>
Chris@16: #include <boost/proto/matches.hpp>
Chris@16: #include <boost/proto/transform/fold.hpp>
Chris@16: #include <boost/proto/transform/impl.hpp>
Chris@16: 
Chris@16: namespace boost { namespace proto
Chris@16: {
Chris@16:     namespace detail
Chris@16:     {
Chris@16:         template<typename Tag>
Chris@16:         struct has_tag
Chris@16:         {
Chris@16:             template<typename Expr, typename State, typename Data, typename EnableIf = Tag>
Chris@16:             struct impl
Chris@16:             {
Chris@16:                 typedef mpl::false_ result_type;
Chris@16:             };
Chris@16: 
Chris@16:             template<typename Expr, typename State, typename Data>
Chris@16:             struct impl<Expr, State, Data, typename Expr::proto_tag>
Chris@16:             {
Chris@16:                 typedef mpl::true_ result_type;
Chris@16:             };
Chris@16: 
Chris@16:             template<typename Expr, typename State, typename Data>
Chris@16:             struct impl<Expr &, State, Data, typename Expr::proto_tag>
Chris@16:             {
Chris@16:                 typedef mpl::true_ result_type;
Chris@16:             };
Chris@16:         };
Chris@16: 
Chris@16:         template<typename Tag, typename Fun>
Chris@16:         struct fold_tree_
Chris@16:           : if_<has_tag<Tag>, fold<_, _state, fold_tree_<Tag, Fun> >, Fun>
Chris@16:         {};
Chris@16: 
Chris@16:         template<typename Tag, typename Fun>
Chris@16:         struct reverse_fold_tree_
Chris@16:           : if_<has_tag<Tag>, reverse_fold<_, _state, reverse_fold_tree_<Tag, Fun> >, Fun>
Chris@16:         {};
Chris@16:     }
Chris@16: 
Chris@16:     /// \brief A PrimitiveTransform that recursively applies the
Chris@16:     /// <tt>fold\<\></tt> transform to sub-trees that all share a common
Chris@16:     /// tag type.
Chris@16:     ///
Chris@16:     /// <tt>fold_tree\<\></tt> is useful for flattening trees into lists;
Chris@16:     /// for example, you might use <tt>fold_tree\<\></tt> to flatten an
Chris@16:     /// expression tree like <tt>a | b | c</tt> into a Fusion list like
Chris@16:     /// <tt>cons(c, cons(b, cons(a)))</tt>.
Chris@16:     ///
Chris@16:     /// <tt>fold_tree\<\></tt> is easily understood in terms of a
Chris@16:     /// <tt>recurse_if_\<\></tt> helper, defined as follows:
Chris@16:     ///
Chris@16:     /// \code
Chris@16:     /// template<typename Tag, typename Fun>
Chris@16:     /// struct recurse_if_
Chris@16:     ///   : if_<
Chris@16:     ///         // If the current node has type "Tag" ...
Chris@16:     ///         is_same<tag_of<_>, Tag>()
Chris@16:     ///         // ... recurse, otherwise ...
Chris@16:     ///       , fold<_, _state, recurse_if_<Tag, Fun> >
Chris@16:     ///         // ... apply the Fun transform.
Chris@16:     ///       , Fun
Chris@16:     ///     >
Chris@16:     /// {};
Chris@16:     /// \endcode
Chris@16:     ///
Chris@16:     /// With <tt>recurse_if_\<\></tt> as defined above,
Chris@16:     /// <tt>fold_tree\<Sequence, State0, Fun\>()(e, s, d)</tt> is
Chris@16:     /// equivalent to
Chris@16:     /// <tt>fold<Sequence, State0, recurse_if_<Expr::proto_tag, Fun> >()(e, s, d).</tt>
Chris@16:     /// It has the effect of folding a tree front-to-back, recursing into
Chris@16:     /// child nodes that share a tag type with the parent node.
Chris@16:     template<typename Sequence, typename State0, typename Fun>
Chris@16:     struct fold_tree
Chris@16:       : transform<fold_tree<Sequence, State0, Fun> >
Chris@16:     {
Chris@16:         template<typename Expr, typename State, typename Data>
Chris@16:         struct impl
Chris@16:           : fold<
Chris@16:                 Sequence
Chris@16:               , State0
Chris@16:               , detail::fold_tree_<typename Expr::proto_tag, Fun>
Chris@16:             >::template impl<Expr, State, Data>
Chris@16:         {};
Chris@16: 
Chris@16:         template<typename Expr, typename State, typename Data>
Chris@16:         struct impl<Expr &, State, Data>
Chris@16:           : fold<
Chris@16:                 Sequence
Chris@16:               , State0
Chris@16:               , detail::fold_tree_<typename Expr::proto_tag, Fun>
Chris@16:             >::template impl<Expr &, State, Data>
Chris@16:         {};
Chris@16:     };
Chris@16: 
Chris@16:     /// \brief A PrimitiveTransform that recursively applies the
Chris@16:     /// <tt>reverse_fold\<\></tt> transform to sub-trees that all share
Chris@16:     /// a common tag type.
Chris@16:     ///
Chris@16:     /// <tt>reverse_fold_tree\<\></tt> is useful for flattening trees into
Chris@16:     /// lists; for example, you might use <tt>reverse_fold_tree\<\></tt> to
Chris@16:     /// flatten an expression tree like <tt>a | b | c</tt> into a Fusion list
Chris@16:     /// like <tt>cons(a, cons(b, cons(c)))</tt>.
Chris@16:     ///
Chris@16:     /// <tt>reverse_fold_tree\<\></tt> is easily understood in terms of a
Chris@16:     /// <tt>recurse_if_\<\></tt> helper, defined as follows:
Chris@16:     ///
Chris@16:     /// \code
Chris@16:     /// template<typename Tag, typename Fun>
Chris@16:     /// struct recurse_if_
Chris@16:     ///   : if_<
Chris@16:     ///         // If the current node has type "Tag" ...
Chris@16:     ///         is_same<tag_of<_>, Tag>()
Chris@16:     ///         // ... recurse, otherwise ...
Chris@16:     ///       , reverse_fold<_, _state, recurse_if_<Tag, Fun> >
Chris@16:     ///         // ... apply the Fun transform.
Chris@16:     ///       , Fun
Chris@16:     ///     >
Chris@16:     /// {};
Chris@16:     /// \endcode
Chris@16:     ///
Chris@16:     /// With <tt>recurse_if_\<\></tt> as defined above,
Chris@16:     /// <tt>reverse_fold_tree\<Sequence, State0, Fun\>()(e, s, d)</tt> is
Chris@16:     /// equivalent to
Chris@16:     /// <tt>reverse_fold<Sequence, State0, recurse_if_<Expr::proto_tag, Fun> >()(e, s, d).</tt>
Chris@16:     /// It has the effect of folding a tree back-to-front, recursing into
Chris@16:     /// child nodes that share a tag type with the parent node.
Chris@16:     template<typename Sequence, typename State0, typename Fun>
Chris@16:     struct reverse_fold_tree
Chris@16:       : transform<reverse_fold_tree<Sequence, State0, Fun> >
Chris@16:     {
Chris@16:         template<typename Expr, typename State, typename Data>
Chris@16:         struct impl
Chris@16:           : reverse_fold<
Chris@16:                 Sequence
Chris@16:               , State0
Chris@16:               , detail::reverse_fold_tree_<typename Expr::proto_tag, Fun>
Chris@16:             >::template impl<Expr, State, Data>
Chris@16:         {};
Chris@16: 
Chris@16:         template<typename Expr, typename State, typename Data>
Chris@16:         struct impl<Expr &, State, Data>
Chris@16:           : reverse_fold<
Chris@16:                 Sequence
Chris@16:               , State0
Chris@16:               , detail::reverse_fold_tree_<typename Expr::proto_tag, Fun>
Chris@16:             >::template impl<Expr &, State, Data>
Chris@16:         {};
Chris@16:     };
Chris@16: 
Chris@16:     /// INTERNAL ONLY
Chris@16:     ///
Chris@16:     template<typename Sequence, typename State0, typename Fun>
Chris@16:     struct is_callable<fold_tree<Sequence, State0, Fun> >
Chris@16:       : mpl::true_
Chris@16:     {};
Chris@16: 
Chris@16:     /// INTERNAL ONLY
Chris@16:     ///
Chris@16:     template<typename Sequence, typename State0, typename Fun>
Chris@16:     struct is_callable<reverse_fold_tree<Sequence, State0, Fun> >
Chris@16:       : mpl::true_
Chris@16:     {};
Chris@16: 
Chris@16: }}
Chris@16: 
Chris@16: #endif