hello.
I wrote this generator, and I think to submit to boost people.
Can you give me some feedback about it
it basically allows to collapse multidimensional loops to flat multi-index queue. Loop can be boost lambda expressions. Main reason for doing this is to make parallel loops easier and separate algorithm from controlling structure (my fieldwork is computational chemistry where deep loops are common)
1 #ifndef _GENERATOR_HPP_
2 #define _GENERATOR_HPP_
3
4 #include <boost/array.hpp>
5 #include <boost/lambda/lambda.hpp>
6 #include <boost/noncopyable.hpp>
7
8 #include <boost/mpl/bool.hpp>
9 #include <boost/mpl/int.hpp>
10 #include <boost/mpl/for_each.hpp>
11 #include <boost/mpl/range_c.hpp>
12 #include <boost/mpl/vector.hpp>
13 #include <boost/mpl/transform.hpp>
14 #include <boost/mpl/erase.hpp>
15
16 #include <boost/fusion/include/vector.hpp>
17 #include <boost/fusion/include/for_each.hpp>
18 #include <boost/fusion/include/at_c.hpp>
19 #include <boost/fusion/mpl.hpp>
20 #include <boost/fusion/include/as_vector.hpp>
21
22 #include <memory>
23
24 /**
25 for loop generator which can use lambda expressions.
26
27 For example:
28 @code
29 using namespace generator;
30 using namespace boost::lambda;
31 make_for(N, N, range(bind(std::max<int>, _1, _2), N), range(_2, _3+1));
32 // equivalent to pseudocode
33 // for l=0,N: for k=0,N: for j=max(l,k),N: for i=k,j
34 @endcode
35
36 If range is given as upper bound only,
37 lower bound is assumed to be default constructed
38 Lambda placeholders may only reference first three indices.
39 */
40
41 namespace generator {
42 namespace detail {
43
44 using boost::lambda::constant_type;
45 using boost::lambda::constant;
46
47 /// lambda expression identity
48 template<class E, class enable = void>
49 struct lambda {
50 typedef E type;
51 };
52
53 /// transform/construct constant lambda expression from non-lambda
54 template<class E>
55 struct lambda<E, typename boost::disable_if<
56 boost::lambda::is_lambda_functor<E> >::type>
57 {
58 struct constant : boost::lambda::constant_type<E>::type {
59 typedef typename boost::lambda::constant_type<E>::type base_type;
60 constant() : base_type(boost::lambda::constant(E())) {}
61 constant(const E &e) : base_type(boost::lambda::constant(e)) {}
62 };
63 typedef constant type;
64 };
65
66 /// range functor
67 template<class L, class U>
68 struct range_ {
69 typedef boost::array<int,4> index_type;
70 range_(U upper) : bounds_(typename lambda<L>::type(), upper) {}
71 range_(L lower, U upper) : bounds_(lower, upper) {}
72
73 template< typename T, size_t N>
74 T lower(const boost::array<T,N> &index) {
75 return bound<0>(index);
76 }
77
78 template< typename T, size_t N>
79 T upper(const boost::array<T,N> &index) {
80 return bound<1>(index);
81 }
82
83 private:
84 template<bool b, typename T>
85 T bound(const boost::array<T,1> &index) {
86 return (boost::fusion::at_c<b>(bounds_))(index[0]);
87 }
88
89 template<bool b, typename T>
90 T bound(const boost::array<T,2> &index) {
91 return (boost::fusion::at_c<b>(bounds_))(index[0], index[1]);
92 }
93
94 template<bool b, typename T, size_t N>
95 T bound(const boost::array<T,N> &index) {
96 using boost::fusion::at_c;
97 return (at_c<b>(bounds_))(index[0], index[1], index[2]);
98 }
99
100 boost::fusion::vector<typename lambda<L>::type,
101 typename lambda<U>::type> bounds_;
102 };
103
104 template<typename T, size_t N>
105 struct for_base {
106 typedef boost::array<T,N> value_type;
107 virtual ~for_base() {}
108 virtual value_type next() = 0;
109 };
110
111 /// N-index generator
112 template<typename T, size_t N, class R, class I>
113 struct for_ : for_base<T,N> {
114 typedef typename for_base<T,N>::value_type value_type;
115 typedef R range_tuple;
116 for_(const range_tuple &r) : r_(r), state_(true) {
117 boost::fusion::for_each(r_, initialize(index));
118 }
119 /// @return new generator
120 for_* new_() { return new for_(r_); }
121 /// @return next index value and increment
122 value_type next() {
123 value_type next;
124 using namespace boost::lambda;
125 typename value_type::iterator n = next.begin();
126 typename value_type::iterator i = index.begin();
127 boost::mpl::for_each<I>(*(var(n))++ = var(i)[_1]);
128
129 state_ = advance<N>(r_, index);
130 return next;
131 }
132 /// @return false if out of bounds, true otherwise
133 operator bool() { return state_; }
134
135 private:
136 /// initialize indices
137 struct initialize {
138 value_type &index_;
139 mutable size_t i_;
140 initialize(value_type &index) : index_(index), i_(0) {}
141 template<class R_> void operator()(R_& r) const {
142 index_[i_++] = r.lower(index_);
143 }
144 };
145
146 /// advance index[0:M)
147 template<size_t M>
148 struct advance {
149 /// stop recursion
150 struct stop {
151 stop(R r, value_type &index) {}
152 };
153 /// advance index
154 /// @param r range tuple
155 /// @param index index array
156 advance(R &r, value_type &index) : index_(index), i_(0) {
157 namespace fusion = boost::fusion;
158 index[M-1] += 1; // increment index
159 fusion::for_each(r, *this); // update indices
160 state_ = index[M-1] >= fusion::at_c<M-1>(r).upper(index);
161 if (state_) { // out of bounds
162 typename boost::mpl::if_c<(M > 1),
163 advance<M-1>, stop>::type(r, index);
164 }
165 }
166 /// apply lower bound of range to index
167 template<typename R_> void operator()(R_& r) const {
168 if (i_ >= M) index_[i_] = r.lower(index_);
169 ++i_;
170 }
171 /// @return false if out of bounds, true otherwise
172 operator bool() { return state_; }
173 private:
174 value_type &index_; ///< index array reference
175 mutable size_t i_; ///< running index
176 bool state_; ///< out of bounds state
177 };
178
179 value_type index;
180 range_tuple r_;
181 bool state_;
182 };
183
184
185 /// polymorphic generator template base
186 template<typename T,size_t N>
187 struct For : boost::noncopyable {
188 typedef boost::array<T,N> value_type;
189 /// @return next index value and increment
190 value_type next() { return for_->next(); }
191 /// @return false if out of bounds, true otherwise
192 operator bool() const { return for_; }
193 protected:
194 /// reset smart pointer
195 void reset(for_base<T,N> *f) { for_.reset(f); }
196 std::auto_ptr<for_base<T,N> > for_;
197 };
198
199 /// range [T,R) type
200 template<typename T, typename R>
201 struct range_type {
202 typedef range_<T,R> type;
203 };
204
205 /// range identity specialization
206 template<typename T, class L, class U>
207 struct range_type<T, range_<L,U> > {
208 typedef range_<L,U> type;
209 };
210
211 namespace fusion = boost::fusion;
212 namespace mpl = boost::mpl;
213
214 template<typename T, size_t N, class R1, class R2, class R3, class R4>
215 struct range_tuple {
216 // full range vector
217 typedef typename mpl::vector<R1,R2,R3,R4> v;
218 typedef typename mpl::end<v>::type end;
219 typedef typename mpl::advance_c<typename mpl::begin<v>::type, N>::type pos;
220 // [0:N) range vector
221 typedef typename mpl::erase<v, pos, end>::type t;
222 // transform into proper range fusion::vector
223 typedef typename fusion::result_of::as_vector<
224 typename mpl::transform<t,range_type<T, mpl::_1> >::type
225 >::type type;
226 };
227
228
229 template<typename T, size_t N,
230 class R1, class R2, class R3, class R4,
231 class O>
232 struct for_type {
233 typedef typename range_tuple<T,N,R1,R2,R3,R4>::type range_tuple;
234 typedef for_<T, N, range_tuple, O> type;
235 };
236
237 } // namespace detail
238
239
240 /// default index order, [0:N)
241 template<size_t N>
242 struct order {
243 typedef boost::mpl::range_c<size_t,0, N> type;
244 };
245
246 /// N-loop generator, 0 < N <= 5
247 /// @tparam T index type
248 /// @tparam N number of indices/loops
249 /// @tparam R1,... range types
250 /// @tparam O index order
251 template<typename T, size_t N,
252 class R1, class R2 = void, class R3 = void, class R4 = void,
253 class O = typename order<N>::type>
254 struct for_ : detail::for_type<T, N, R1, R2, R3, R4, O>::type {
255 typedef typename detail::for_type<T, N, R1, R2, R3, R4, O>::type base_type;
256 typedef typename base_type::range_tuple range_tuple;
257 for_(const range_tuple &range) : base_type(range) {}
258 };
259
260 /// loop range [L:U)
261 /// @tparam L lower bound type
262 /// @tparam U upper bound type
263 /// @return range
264 template<class L, class U>
265 detail::range_<L,U> range(L lower, U upper) {
266 return detail::range_<L,U>(lower, upper);
267 }
268
269 /// make 4-loop generator with specified index ordering
270 template<typename T, class R1, class R2, class R3, class R4, class O>
271 for_<T, 4, R1, R2, R3, R4, O>
272 make_for(R1 r1, R2 r2, R3 r3, R4 r4, const O&) {
273 typedef for_<T, 4, R1, R2, R3, R4, O> F;
274 return F(F::range_tuple(r1, r2, r3, r4));
275 }
276
277 /// polymorphic generator template forward declaration
278 template<typename T,size_t N>
279 struct For;
280
281 /// polymorphic 4-loop generator
282 template<typename T>
283 struct For<T,4> : detail::For<T,4> {
284 /// generator with default index ordering
285 template<class R1, class R2, class R3, class R4>
286 For(R1 r1, R2 r2, R3 r3, R4 r4) {
287 this->reset(make_for<T>(r1, r2, r3, r4).new_());
288 }
289 /// generator with specified index ordering
290 template<class R1, class R2, class R3, class R4, class O>
291 For(R1 r1, R2 r2, R3 r3, R4 r4, O o) {
292 this->reset(make_for<T>(r1, r2, r3, r4, o).new_());
293 }
294 };
295
296 }
297
298
299 #endif /* _GENERATOR_HPP_ */
