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 183