1 /*=============================================================================
2     Copyright (c) 2011 Eric Niebler
3 
4     Distributed under the Boost Software License, Version 1.0. (See accompanying
5     file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 ==============================================================================*/
7 #if !defined(BOOST_FUSION_SEGMENTED_FOLD_UNTIL_IMPL_HPP_INCLUDED)
8 #define BOOST_FUSION_SEGMENTED_FOLD_UNTIL_IMPL_HPP_INCLUDED
9 
10 #include <boost/fusion/support/config.hpp>
11 #include <boost/mpl/bool.hpp>
12 #include <boost/mpl/eval_if.hpp>
13 #include <boost/mpl/identity.hpp>
14 #include <boost/utility/result_of.hpp>
15 #include <boost/type_traits/add_const.hpp>
16 #include <boost/type_traits/remove_reference.hpp>
17 
18 #include <boost/fusion/support/void.hpp>
19 #include <boost/fusion/container/list/cons_fwd.hpp>
20 #include <boost/fusion/sequence/intrinsic_fwd.hpp>
21 #include <boost/fusion/iterator/equal_to.hpp>
22 #include <boost/fusion/iterator/deref.hpp>
23 #include <boost/fusion/iterator/next.hpp>
24 #include <boost/fusion/support/is_segmented.hpp>
25 #include <boost/fusion/sequence/intrinsic/segments.hpp>
26 
27 // fun(seq, state, context)
28 //  seq: a non-segmented range
29 //  state: the state of the fold so far
30 //  context: the path to the current range
31 //
32 // returns: (state', fcontinue)
33 
34 namespace boost { namespace fusion
35 {
36     template <typename First, typename Last>
37     struct iterator_range;
38 
39     template <typename Context>
40     struct segmented_iterator;
41 
42     namespace result_of
43     {
44         template <typename Cur, typename Context>
45         struct make_segmented_iterator
46         {
47             typedef
48                 iterator_range<
49                     Cur
50                   , typename result_of::end<
51                         typename remove_reference<
52                             typename add_const<
53                                 typename result_of::deref<
54                                     typename Context::car_type::begin_type
55                                 >::type
56                             >::type
57                         >::type
58                     >::type
59                 >
60             range_type;
61 
62             typedef
63                 segmented_iterator<cons<range_type, Context> >
64             type;
65         };
66     }
67 
68     template <typename Cur, typename Context>
69     BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
70     inline typename result_of::make_segmented_iterator<Cur, Context>::type
make_segmented_iterator(Cur const & cur,Context const & context)71     make_segmented_iterator(Cur const& cur, Context const& context)
72     {
73         typedef result_of::make_segmented_iterator<Cur, Context> impl_type;
74         typedef typename impl_type::type type;
75         typedef typename impl_type::range_type range_type;
76         return type(cons<range_type, Context>(range_type(cur, fusion::end(*context.car.first)), context));
77     }
78 
79     namespace detail
80     {
81         template <
82             typename Begin
83           , typename End
84           , typename State
85           , typename Context
86           , typename Fun
87           , bool IsEmpty
88         >
89         struct segmented_fold_until_iterate_skip_empty;
90 
91         template <
92             typename Begin
93           , typename End
94           , typename State
95           , typename Context
96           , typename Fun
97           , bool IsDone = result_of::equal_to<Begin, End>::type::value
98         >
99         struct segmented_fold_until_iterate;
100 
101         template <
102             typename Sequence
103           , typename State
104           , typename Context
105           , typename Fun
106           , bool IsSegmented = traits::is_segmented<Sequence>::type::value
107         >
108         struct segmented_fold_until_impl;
109 
110         template <typename Segments, typename State, typename Context, typename Fun>
111         struct segmented_fold_until_on_segments;
112 
113         //auto push_context(cur, end, context)
114         //{
115         //  return push_back(context, segment_sequence(iterator_range(cur, end)));
116         //}
117 
118         template <typename Cur, typename End, typename Context>
119         struct push_context
120         {
121             typedef iterator_range<Cur, End>    range_type;
122             typedef cons<range_type, Context>   type;
123 
124             BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
callboost::fusion::detail::push_context125             static type call(Cur const& cur, End const& end, Context const& context)
126             {
127                 return cons<range_type, Context>(range_type(cur, end), context);
128             }
129         };
130 
131         //auto make_segmented_iterator(cur, end, context)
132         //{
133         //  return segmented_iterator(push_context(cur, end, context));
134         //}
135         //
136         //auto segmented_fold_until_impl(seq, state, context, fun)
137         //{
138         //  if (is_segmented(seq))
139         //  {
140         //    segmented_fold_until_on_segments(segments(seq), state, context, fun);
141         //  }
142         //  else
143         //  {
144         //    return fun(seq, state, context);
145         //  }
146         //}
147 
148         template <
149             typename Sequence
150           , typename State
151           , typename Context
152           , typename Fun
153           , bool IsSegmented
154         >
155         struct segmented_fold_until_impl
156         {
157             typedef
158                 segmented_fold_until_on_segments<
159                     typename remove_reference<
160                         typename add_const<
161                             typename result_of::segments<Sequence>::type
162                         >::type
163                     >::type
164                   , State
165                   , Context
166                   , Fun
167                 >
168             impl;
169 
170             typedef typename impl::type type;
171             typedef typename impl::continue_type continue_type;
172 
173             BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
callboost::fusion::detail::segmented_fold_until_impl174             static type call(Sequence& seq, State const& state, Context const& context, Fun const& fun)
175             {
176                 return impl::call(fusion::segments(seq), state, context, fun);
177             }
178         };
179 
180         template <
181             typename Sequence
182           , typename State
183           , typename Context
184           , typename Fun
185         >
186         struct segmented_fold_until_impl<Sequence, State, Context, Fun, false>
187         {
188             typedef
189                 typename Fun::template apply<Sequence, State, Context>
190             apply_type;
191 
192             typedef typename apply_type::type type;
193             typedef typename apply_type::continue_type continue_type;
194 
195             BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
callboost::fusion::detail::segmented_fold_until_impl196             static type call(Sequence& seq, State const& state, Context const& context, Fun const& fun)
197             {
198                 return apply_type::call(seq, state, context, fun);
199             }
200         };
201 
202         //auto segmented_fold_until_on_segments(segs, state, context, fun)
203         //{
204         //  auto cur = begin(segs), end = end(segs);
205         //  for (; cur != end; ++cur)
206         //  {
207         //    if (empty(*cur))
208         //      continue;
209         //    auto context` = push_context(cur, end, context);
210         //    state = segmented_fold_until_impl(*cur, state, context`, fun);
211         //    if (!second(state))
212         //      return state;
213         //  }
214         //}
215 
216         template <typename Apply>
217         struct continue_wrap
218         {
219             typedef typename Apply::continue_type type;
220         };
221 
222         template <typename Begin, typename End, typename State, typename Context, typename Fun, bool IsEmpty>
223         struct segmented_fold_until_iterate_skip_empty
224         {
225             // begin != end and !empty(*begin)
226             typedef
227                 push_context<Begin, End, Context>
228             push_context_impl;
229 
230             typedef
231                 typename push_context_impl::type
232             next_context_type;
233 
234             typedef
235                 segmented_fold_until_impl<
236                     typename remove_reference<
237                         typename add_const<
238                             typename result_of::deref<Begin>::type
239                         >::type
240                     >::type
241                   , State
242                   , next_context_type
243                   , Fun
244                 >
245             fold_recurse_impl;
246 
247             typedef
248                 typename fold_recurse_impl::type
249             next_state_type;
250 
251             typedef
252                 segmented_fold_until_iterate<
253                     typename result_of::next<Begin>::type
254                   , End
255                   , next_state_type
256                   , Context
257                   , Fun
258                 >
259             next_iteration_impl;
260 
261             typedef
262                 typename mpl::eval_if<
263                     typename fold_recurse_impl::continue_type
264                   , next_iteration_impl
265                   , mpl::identity<next_state_type>
266                 >::type
267             type;
268 
269             typedef
270                 typename mpl::eval_if<
271                     typename fold_recurse_impl::continue_type
272                   , continue_wrap<next_iteration_impl>
273                   , mpl::identity<mpl::false_>
274                 >::type
275             continue_type;
276 
277             BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
callboost::fusion::detail::segmented_fold_until_iterate_skip_empty278             static type call(Begin const& beg, End const& end, State const& state
279                            , Context const& context, Fun const& fun)
280             {
281                 return call(beg, end, state, context, fun, typename fold_recurse_impl::continue_type());
282             }
283 
284             BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
callboost::fusion::detail::segmented_fold_until_iterate_skip_empty285             static type call(Begin const& beg, End const& end, State const& state
286                            , Context const& context, Fun const& fun, mpl::true_) // continue
287             {
288                 return next_iteration_impl::call(
289                     fusion::next(beg)
290                   , end
291                   , fold_recurse_impl::call(
292                         *beg
293                       , state
294                       , push_context_impl::call(beg, end, context)
295                       , fun)
296                   , context
297                   , fun);
298             }
299 
300             BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
callboost::fusion::detail::segmented_fold_until_iterate_skip_empty301             static type call(Begin const& beg, End const& end, State const& state
302                            , Context const& context, Fun const& fun, mpl::false_) // break
303             {
304                 return fold_recurse_impl::call(
305                     *beg
306                   , state
307                   , push_context_impl::call(beg, end, context)
308                   , fun);
309             }
310         };
311 
312         template <typename Begin, typename End, typename State, typename Context, typename Fun>
313         struct segmented_fold_until_iterate_skip_empty<Begin, End, State, Context, Fun, true>
314         {
315             typedef
316                 segmented_fold_until_iterate<
317                     typename result_of::next<Begin>::type
318                   , End
319                   , State
320                   , Context
321                   , Fun
322                 >
323             impl;
324 
325             typedef typename impl::type type;
326             typedef typename impl::continue_type continue_type;
327 
328             BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
callboost::fusion::detail::segmented_fold_until_iterate_skip_empty329             static type call(Begin const& beg, End const& end, State const& state
330                            , Context const& context, Fun const& fun)
331             {
332                 return impl::call(fusion::next(beg), end, state, context, fun);
333             }
334         };
335 
336         template <typename Begin, typename End, typename State, typename Context, typename Fun, bool IsDone>
337         struct segmented_fold_until_iterate
338         {
339             typedef
340                 typename result_of::empty<
341                     typename remove_reference<
342                         typename result_of::deref<Begin>::type
343                     >::type
344                 >::type
345             empty_type;
346 
347             typedef
348                 segmented_fold_until_iterate_skip_empty<Begin, End, State, Context, Fun, empty_type::value>
349             impl;
350 
351             typedef typename impl::type type;
352             typedef typename impl::continue_type continue_type;
353 
354             BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
callboost::fusion::detail::segmented_fold_until_iterate355             static type call(Begin const& beg, End const& end, State const& state
356                            , Context const& context, Fun const& fun)
357             {
358                 return impl::call(beg, end, state, context, fun);
359             }
360         };
361 
362         template <typename Begin, typename End, typename State, typename Context, typename Fun>
363         struct segmented_fold_until_iterate<Begin, End, State, Context, Fun, true>
364         {
365             typedef State type;
366             typedef mpl::true_ continue_type;
367 
368             BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
callboost::fusion::detail::segmented_fold_until_iterate369             static type call(Begin const&, End const&, State const& state
370                            , Context const&, Fun const&)
371             {
372                 return state;
373             }
374         };
375 
376         template <typename Segments, typename State, typename Context, typename Fun>
377         struct segmented_fold_until_on_segments
378         {
379             typedef
380                 segmented_fold_until_iterate<
381                     typename result_of::begin<Segments>::type
382                   , typename result_of::end<Segments>::type
383                   , State
384                   , Context
385                   , Fun
386                 >
387             impl;
388 
389             typedef typename impl::type type;
390             typedef typename impl::continue_type continue_type;
391 
392             BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
callboost::fusion::detail::segmented_fold_until_on_segments393             static type call(Segments& segs, State const& state, Context const& context, Fun const& fun)
394             {
395                 return impl::call(fusion::begin(segs), fusion::end(segs), state, context, fun);
396             }
397         };
398     }
399 }}
400 
401 #endif
402