1 /*=============================================================================
2 Copyright (c) 2011 Eric Niebler
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_ITERATOR_RANGE_HPP_INCLUDED)
8 #define BOOST_FUSION_SEGMENTED_ITERATOR_RANGE_HPP_INCLUDED
10 #include <boost/fusion/support/config.hpp>
11 #include <boost/detail/workaround.hpp>
12 #include <boost/mpl/assert.hpp>
13 #include <boost/type_traits/add_const.hpp>
14 #include <boost/type_traits/remove_reference.hpp>
15 #include <boost/fusion/support/tag_of.hpp>
16 #include <boost/fusion/sequence/intrinsic/begin.hpp>
17 #include <boost/fusion/sequence/intrinsic/end.hpp>
18 #include <boost/fusion/iterator/next.hpp>
19 #include <boost/fusion/iterator/deref.hpp>
20 #include <boost/fusion/sequence/intrinsic/segments.hpp>
21 #include <boost/fusion/algorithm/transformation/push_back.hpp>
22 #include <boost/fusion/algorithm/transformation/push_front.hpp>
23 #include <boost/fusion/iterator/equal_to.hpp>
24 #include <boost/fusion/container/list/detail/reverse_cons.hpp>
25 #include <boost/fusion/iterator/detail/segment_sequence.hpp>
26 #include <boost/fusion/support/is_sequence.hpp>
27 #include <boost/utility/enable_if.hpp>
30 // - Each segmented iterator has a stack
31 // - Each value in the stack is an iterator range
32 // - The range at the top of the stack points to values
33 // - All other ranges point to ranges
34 // - The front of each range in the stack (besides the
35 // topmost) is the range above it
37 namespace boost { namespace fusion
39 template <typename First, typename Last>
40 struct iterator_range;
44 template <typename Sequence, typename T>
47 template <typename Sequence, typename T>
51 template <typename Sequence, typename T>
52 BOOST_CXX14_CONSTEXPR BOOST_FUSION_GPU_ENABLED
55 traits::is_sequence<Sequence>
56 , result_of::push_back<Sequence const, T>
58 push_back(Sequence const& seq, T const& x);
60 template <typename Sequence, typename T>
61 BOOST_CXX14_CONSTEXPR BOOST_FUSION_GPU_ENABLED
64 traits::is_sequence<Sequence>
65 , result_of::push_front<Sequence const, T>
67 push_front(Sequence const& seq, T const& x);
70 namespace boost { namespace fusion { namespace detail
72 //auto make_segment_sequence_front(stack_begin)
74 // switch (size(stack_begin))
79 // // car(cdr(stack_begin)) is a range over values.
80 // assert(end(front(car(stack_begin))) == end(car(cdr(stack_begin))));
81 // return iterator_range(begin(car(cdr(stack_begin))), end(front(car(stack_begin))));
83 // // car(cdr(stack_begin)) is a range over segments. We replace the
84 // // front with a view that is restricted.
85 // assert(end(segments(front(car(stack_begin)))) == end(car(cdr(stack_begin))));
86 // return segment_sequence(
88 // // The following could be a segment_sequence. It then gets wrapped
89 // // in a single_view, and push_front puts it in a join_view with the
90 // // following iterator_range.
91 // iterator_range(next(begin(car(cdr(stack_begin)))), end(segments(front(car(stack_begin))))),
92 // make_segment_sequence_front(cdr(stack_begin))));
96 template <typename Stack, std::size_t Size = Stack::size::value>
97 struct make_segment_sequence_front
99 // assert(end(segments(front(car(stack_begin)))) == end(car(cdr(stack_begin))));
102 typename result_of::end<
103 typename remove_reference<
105 typename result_of::segments<
106 typename remove_reference<
108 typename result_of::deref<
109 typename Stack::car_type::begin_type
117 , typename Stack::cdr_type::car_type::end_type
122 typename result_of::next<
123 typename Stack::cdr_type::car_type::begin_type
125 , typename result_of::end<
126 typename remove_reference<
128 typename result_of::segments<
129 typename remove_reference<
131 typename result_of::deref<
132 typename Stack::car_type::begin_type
144 make_segment_sequence_front<typename Stack::cdr_type>
149 typename result_of::push_front<
151 , typename recurse::type
156 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
157 static type call(Stack const& stack)
159 //return segment_sequence(
161 // iterator_range(next(begin(car(cdr(stack_begin)))), end(segments(front(car(stack_begin))))),
162 // make_segment_sequence_front(cdr(stack_begin))));
165 rest_type(fusion::next(stack.cdr.car.first), fusion::end(fusion::segments(*stack.car.first)))
166 , recurse::call(stack.cdr)));
170 template <typename Stack>
171 struct make_segment_sequence_front<Stack, 2>
173 // assert(end(front(car(stack_begin))) == end(car(cdr(stack_begin))));
176 typename result_of::end<
177 typename remove_reference<
179 typename result_of::deref<
180 typename Stack::car_type::begin_type
185 , typename Stack::cdr_type::car_type::end_type
190 typename Stack::cdr_type::car_type::begin_type
191 , typename result_of::end<
192 typename remove_reference<
194 typename result_of::deref<
195 typename Stack::car_type::begin_type
203 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
204 static type call(Stack const& stack)
206 // return iterator_range(begin(car(cdr(stack_begin))), end(front(car(stack_begin))));
207 return type(stack.cdr.car.first, fusion::end(*stack.car.first));
211 template <typename Stack>
212 struct make_segment_sequence_front<Stack, 1>
214 typedef typename Stack::cdr_type type; // nil_
216 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
217 static type call(Stack const &stack)
223 //auto make_segment_sequence_back(stack_end)
225 // switch (size(stack_end))
230 // // car(cdr(stack_back)) is a range over values.
231 // assert(end(front(car(stack_end))) == end(car(cdr(stack_end))));
232 // return iterator_range(begin(front(car(stack_end))), begin(car(cdr(stack_end))));
234 // // car(cdr(stack_begin)) is a range over segments. We replace the
235 // // back with a view that is restricted.
236 // assert(end(segments(front(car(stack_end)))) == end(car(cdr(stack_end))));
237 // return segment_sequence(
239 // iterator_range(begin(segments(front(car(stack_end)))), begin(car(cdr(stack_end)))),
240 // make_segment_sequence_back(cdr(stack_end))));
244 template <typename Stack, std::size_t Size = Stack::size::value>
245 struct make_segment_sequence_back
247 // assert(end(segments(front(car(stack_begin)))) == end(car(cdr(stack_begin))));
250 typename result_of::end<
251 typename remove_reference<
253 typename result_of::segments<
254 typename remove_reference<
256 typename result_of::deref<
257 typename Stack::car_type::begin_type
265 , typename Stack::cdr_type::car_type::end_type
270 typename result_of::begin<
271 typename remove_reference<
273 typename result_of::segments<
274 typename remove_reference<
276 typename result_of::deref<
277 typename Stack::car_type::begin_type
285 , typename Stack::cdr_type::car_type::begin_type
290 make_segment_sequence_back<typename Stack::cdr_type>
295 typename result_of::push_back<
297 , typename recurse::type
302 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
303 static type call(Stack const& stack)
305 // return segment_sequence(
307 // iterator_range(begin(segments(front(car(stack_end)))), begin(car(cdr(stack_end)))),
308 // make_segment_sequence_back(cdr(stack_end))));
311 rest_type(fusion::begin(fusion::segments(*stack.car.first)), stack.cdr.car.first)
312 , recurse::call(stack.cdr)));
316 template <typename Stack>
317 struct make_segment_sequence_back<Stack, 2>
319 // assert(end(front(car(stack_end))) == end(car(cdr(stack_end))));
322 typename result_of::end<
323 typename remove_reference<
325 typename result_of::deref<
326 typename Stack::car_type::begin_type
331 , typename Stack::cdr_type::car_type::end_type
336 typename result_of::begin<
337 typename remove_reference<
339 typename result_of::deref<
340 typename Stack::car_type::begin_type
345 , typename Stack::cdr_type::car_type::begin_type
349 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
350 static type call(Stack const& stack)
352 // return iterator_range(begin(front(car(stack_end))), begin(car(cdr(stack_end))));
353 return type(fusion::begin(*stack.car.first), stack.cdr.car.first);
357 template <typename Stack>
358 struct make_segment_sequence_back<Stack, 1>
360 typedef typename Stack::cdr_type type; // nil_
362 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
363 static type call(Stack const& stack)
369 //auto make_segmented_range_reduce(stack_begin, stack_end)
371 // if (size(stack_begin) == 1 && size(stack_end) == 1)
373 // return segment_sequence(
375 // iterator_range(begin(car(stack_begin)), begin(car(stack_end)))));
379 // // We are in the case where both begin_stack and/or end_stack have
380 // // more than one element. Throw away any part of the tree where
381 // // begin and end refer to the same segment.
382 // if (begin(car(stack_begin)) == begin(car(stack_end)))
384 // return make_segmented_range_reduce(cdr(stack_begin), cdr(stack_end));
388 // // We are in the case where begin_stack and end_stack (a) have
389 // // more than one element each, and (b) they point to different
390 // // segments. We must construct a segmented sequence.
391 // return segment_sequence(
395 // fusion::next(begin(car(stack_begin))),
396 // begin(car(stack_end))), // a range of (possibly segmented) ranges.
397 // make_segment_sequence_front(stack_begin)), // should be a (possibly segmented) range.
398 // make_segment_sequence_back(stack_end))); // should be a (possibly segmented) range.
406 , int StackBeginSize = StackBegin::size::value
407 , int StackEndSize = StackEnd::size::value>
408 struct make_segmented_range_reduce;
414 #if !(BOOST_WORKAROUND(BOOST_GCC, >= 40000) && BOOST_WORKAROUND(BOOST_GCC, < 40200))
415 = result_of::equal_to<
416 typename StackBegin::car_type::begin_type
417 , typename StackEnd::car_type::begin_type
421 struct make_segmented_range_reduce2
425 typename result_of::next<
426 typename StackBegin::car_type::begin_type
428 , typename StackEnd::car_type::begin_type
434 typename result_of::push_back<
435 typename result_of::push_front<
437 , typename make_segment_sequence_front<StackBegin>::type
439 , typename make_segment_sequence_back<StackEnd>::type
444 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
445 static type call(StackBegin stack_begin, StackEnd stack_end)
447 //return segment_sequence(
451 // fusion::next(begin(car(stack_begin))),
452 // begin(car(stack_end))), // a range of (possibly segmented) ranges.
453 // make_segment_sequence_front(stack_begin)), // should be a (possibly segmented) range.
454 // make_segment_sequence_back(stack_end))); // should be a (possibly segmented) range.
458 rest_type(fusion::next(stack_begin.car.first), stack_end.car.first)
459 , make_segment_sequence_front<StackBegin>::call(stack_begin))
460 , make_segment_sequence_back<StackEnd>::call(stack_end)));
464 template <typename StackBegin, typename StackEnd>
465 struct make_segmented_range_reduce2<StackBegin, StackEnd, true>
468 make_segmented_range_reduce<
469 typename StackBegin::cdr_type
470 , typename StackEnd::cdr_type
478 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
479 static type call(StackBegin stack_begin, StackEnd stack_end)
481 return impl::call(stack_begin.cdr, stack_end.cdr);
485 template <typename StackBegin, typename StackEnd, int StackBeginSize, int StackEndSize>
486 struct make_segmented_range_reduce
487 : make_segmented_range_reduce2<StackBegin, StackEnd
488 #if BOOST_WORKAROUND(BOOST_GCC, >= 40000) && BOOST_WORKAROUND(BOOST_GCC, < 40200)
489 , result_of::equal_to<
490 typename StackBegin::car_type::begin_type
491 , typename StackEnd::car_type::begin_type
497 template <typename StackBegin, typename StackEnd>
498 struct make_segmented_range_reduce<StackBegin, StackEnd, 1, 1>
502 typename StackBegin::car_type::begin_type
503 , typename StackEnd::car_type::begin_type
508 single_view<range_type>
512 segment_sequence<segment_type>
515 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
516 static type call(StackBegin stack_begin, StackEnd stack_end)
518 //return segment_sequence(
520 // iterator_range(begin(car(stack_begin)), begin(car(stack_end)))));
521 return type(segment_type(range_type(stack_begin.car.first, stack_end.car.first)));
525 //auto make_segmented_range(begin, end)
527 // return make_segmented_range_reduce(reverse(begin.context), reverse(end.context));
530 template <typename Begin, typename End>
531 struct make_segmented_range
533 typedef reverse_cons<typename Begin::context_type> reverse_begin_cons;
534 typedef reverse_cons<typename End::context_type> reverse_end_cons;
537 make_segmented_range_reduce<
538 typename reverse_begin_cons::type
539 , typename reverse_end_cons::type
543 typedef typename impl::type type;
545 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
546 static type call(Begin const& begin, End const& end)
549 reverse_begin_cons::call(begin.context)
550 , reverse_end_cons::call(end.context));