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
19namespace 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