ceph/src/boost/libs/proto/include/boost/proto/transform/fold_tree.hpp

   1 ///////////////////////////////////////////////////////////////////////////////
   2 /// \file fold_tree.hpp
   3 /// Contains definition of the fold_tree<> and reverse_fold_tree<> transforms.
   4 //
   5 //  Copyright 2008 Eric Niebler. Distributed under the Boost
   6 //  Software License, Version 1.0. (See accompanying file
   7 //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   8
   9 #ifndef BOOST_PROTO_TRANSFORM_FOLD_TREE_HPP_EAN_11_05_2007
  10 #define BOOST_PROTO_TRANSFORM_FOLD_TREE_HPP_EAN_11_05_2007
  11
  12 #include <boost/type_traits/is_same.hpp>
  13 #include <boost/proto/proto_fwd.hpp>
  14 #include <boost/proto/traits.hpp>
  15 #include <boost/proto/matches.hpp>
  16 #include <boost/proto/transform/fold.hpp>
  17 #include <boost/proto/transform/impl.hpp>
  18
  19 namespace boost { namespace proto
  20 {
  21     namespace detail
  22     {
  23         template<typename Tag>
  24         struct has_tag
  25         {
  26             template<typename Expr, typename State, typename Data, typename EnableIf = Tag>
  27             struct impl
  28             {
  29                 typedef mpl::false_ result_type;
  30             };
  31
  32             template<typename Expr, typename State, typename Data>
  33             struct impl<Expr, State, Data, typename Expr::proto_tag>
  34             {
  35                 typedef mpl::true_ result_type;
  36             };
  37
  38             template<typename Expr, typename State, typename Data>
  39             struct impl<Expr &, State, Data, typename Expr::proto_tag>
  40             {
  41                 typedef mpl::true_ result_type;
  42             };
  43         };
  44
  45         template<typename Tag, typename Fun>
  46         struct fold_tree_
  47           : if_<has_tag<Tag>, fold<_, _state, fold_tree_<Tag, Fun> >, Fun>
  48         {};
  49
  50         template<typename Tag, typename Fun>
  51         struct reverse_fold_tree_
  52           : if_<has_tag<Tag>, reverse_fold<_, _state, reverse_fold_tree_<Tag, Fun> >, Fun>
  53         {};
  54     }
  55
  56     /// \brief A PrimitiveTransform that recursively applies the
  57     /// <tt>fold\<\></tt> transform to sub-trees that all share a common
  58     /// tag type.
  59     ///
  60     /// <tt>fold_tree\<\></tt> is useful for flattening trees into lists;
  61     /// for example, you might use <tt>fold_tree\<\></tt> to flatten an
  62     /// expression tree like <tt>a | b | c</tt> into a Fusion list like
  63     /// <tt>cons(c, cons(b, cons(a)))</tt>.
  64     ///
  65     /// <tt>fold_tree\<\></tt> is easily understood in terms of a
  66     /// <tt>recurse_if_\<\></tt> helper, defined as follows:
  67     ///
  68     /// \code
  69     /// template<typename Tag, typename Fun>
  70     /// struct recurse_if_
  71     ///   : if_<
  72     ///         // If the current node has type "Tag" ...
  73     ///         is_same<tag_of<_>, Tag>()
  74     ///         // ... recurse, otherwise ...
  75     ///       , fold<_, _state, recurse_if_<Tag, Fun> >
  76     ///         // ... apply the Fun transform.
  77     ///       , Fun
  78     ///     >
  79     /// {};
  80     /// \endcode
  81     ///
  82     /// With <tt>recurse_if_\<\></tt> as defined above,
  83     /// <tt>fold_tree\<Sequence, State0, Fun\>()(e, s, d)</tt> is
  84     /// equivalent to
  85     /// <tt>fold<Sequence, State0, recurse_if_<Expr::proto_tag, Fun> >()(e, s, d).</tt>
  86     /// It has the effect of folding a tree front-to-back, recursing into
  87     /// child nodes that share a tag type with the parent node.
  88     template<typename Sequence, typename State0, typename Fun>
  89     struct fold_tree
  90       : transform<fold_tree<Sequence, State0, Fun> >
  91     {
  92         template<typename Expr, typename State, typename Data>
  93         struct impl
  94           : fold<
  95                 Sequence
  96               , State0
  97               , detail::fold_tree_<typename Expr::proto_tag, Fun>
  98             >::template impl<Expr, State, Data>
  99         {};
 100
 101         template<typename Expr, typename State, typename Data>
 102         struct impl<Expr &, State, Data>
 103           : fold<
 104                 Sequence
 105               , State0
 106               , detail::fold_tree_<typename Expr::proto_tag, Fun>
 107             >::template impl<Expr &, State, Data>
 108         {};
 109     };
 110
 111     /// \brief A PrimitiveTransform that recursively applies the
 112     /// <tt>reverse_fold\<\></tt> transform to sub-trees that all share
 113     /// a common tag type.
 114     ///
 115     /// <tt>reverse_fold_tree\<\></tt> is useful for flattening trees into
 116     /// lists; for example, you might use <tt>reverse_fold_tree\<\></tt> to
 117     /// flatten an expression tree like <tt>a | b | c</tt> into a Fusion list
 118     /// like <tt>cons(a, cons(b, cons(c)))</tt>.
 119     ///
 120     /// <tt>reverse_fold_tree\<\></tt> is easily understood in terms of a
 121     /// <tt>recurse_if_\<\></tt> helper, defined as follows:
 122     ///
 123     /// \code
 124     /// template<typename Tag, typename Fun>
 125     /// struct recurse_if_
 126     ///   : if_<
 127     ///         // If the current node has type "Tag" ...
 128     ///         is_same<tag_of<_>, Tag>()
 129     ///         // ... recurse, otherwise ...
 130     ///       , reverse_fold<_, _state, recurse_if_<Tag, Fun> >
 131     ///         // ... apply the Fun transform.
 132     ///       , Fun
 133     ///     >
 134     /// {};
 135     /// \endcode
 136     ///
 137     /// With <tt>recurse_if_\<\></tt> as defined above,
 138     /// <tt>reverse_fold_tree\<Sequence, State0, Fun\>()(e, s, d)</tt> is
 139     /// equivalent to
 140     /// <tt>reverse_fold<Sequence, State0, recurse_if_<Expr::proto_tag, Fun> >()(e, s, d).</tt>
 141     /// It has the effect of folding a tree back-to-front, recursing into
 142     /// child nodes that share a tag type with the parent node.
 143     template<typename Sequence, typename State0, typename Fun>
 144     struct reverse_fold_tree
 145       : transform<reverse_fold_tree<Sequence, State0, Fun> >
 146     {
 147         template<typename Expr, typename State, typename Data>
 148         struct impl
 149           : reverse_fold<
 150                 Sequence
 151               , State0
 152               , detail::reverse_fold_tree_<typename Expr::proto_tag, Fun>
 153             >::template impl<Expr, State, Data>
 154         {};
 155
 156         template<typename Expr, typename State, typename Data>
 157         struct impl<Expr &, State, Data>
 158           : reverse_fold<
 159                 Sequence
 160               , State0
 161               , detail::reverse_fold_tree_<typename Expr::proto_tag, Fun>
 162             >::template impl<Expr &, State, Data>
 163         {};
 164     };
 165
 166     /// INTERNAL ONLY
 167     ///
 168     template<typename Sequence, typename State0, typename Fun>
 169     struct is_callable<fold_tree<Sequence, State0, Fun> >
 170       : mpl::true_
 171     {};
 172
 173     /// INTERNAL ONLY
 174     ///
 175     template<typename Sequence, typename State0, typename Fun>
 176     struct is_callable<reverse_fold_tree<Sequence, State0, Fun> >
 177       : mpl::true_
 178     {};
 179
 180 }}
 181
 182 #endif