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/mpl/assert.hpp>
11 #include <boost/type_traits/add_const.hpp>
12 #include <boost/type_traits/remove_reference.hpp>
13 #include <boost/fusion/support/tag_of.hpp>
14 #include <boost/fusion/sequence/intrinsic/begin.hpp>
15 #include <boost/fusion/sequence/intrinsic/end.hpp>
16 #include <boost/fusion/iterator/next.hpp>
17 #include <boost/fusion/iterator/deref.hpp>
18 #include <boost/fusion/sequence/intrinsic/segments.hpp>
19 #include <boost/fusion/algorithm/transformation/push_back.hpp>
20 #include <boost/fusion/algorithm/transformation/push_front.hpp>
21 #include <boost/fusion/iterator/equal_to.hpp>
22 #include <boost/fusion/container/list/detail/reverse_cons.hpp>
23 #include <boost/fusion/iterator/detail/segment_sequence.hpp>
24 #include <boost/fusion/support/is_sequence.hpp>
25 #include <boost/utility/enable_if.hpp>
28 // - Each segmented iterator has a stack
29 // - Each value in the stack is an iterator range
30 // - The range at the top of the stack points to values
31 // - All other ranges point to ranges
32 // - The front of each range in the stack (besides the
33 // topmost) is the range above it
35 namespace boost { namespace fusion
37 template <typename First, typename Last>
38 struct iterator_range;
42 template <typename Sequence, typename T>
45 template <typename Sequence, typename T>
49 template <typename Sequence, typename T>
52 traits::is_sequence<Sequence>
53 , result_of::push_back<Sequence const, T>
55 push_back(Sequence const& seq, T const& x);
57 template <typename Sequence, typename T>
60 traits::is_sequence<Sequence>
61 , result_of::push_front<Sequence const, T>
63 push_front(Sequence const& seq, T const& x);
66 namespace boost { namespace fusion { namespace detail
68 //auto make_segment_sequence_front(stack_begin)
70 // switch (size(stack_begin))
75 // // car(cdr(stack_begin)) is a range over values.
76 // assert(end(front(car(stack_begin))) == end(car(cdr(stack_begin))));
77 // return iterator_range(begin(car(cdr(stack_begin))), end(front(car(stack_begin))));
79 // // car(cdr(stack_begin)) is a range over segments. We replace the
80 // // front with a view that is restricted.
81 // assert(end(segments(front(car(stack_begin)))) == end(car(cdr(stack_begin))));
82 // return segment_sequence(
84 // // The following could be a segment_sequence. It then gets wrapped
85 // // in a single_view, and push_front puts it in a join_view with the
86 // // following iterator_range.
87 // iterator_range(next(begin(car(cdr(stack_begin)))), end(segments(front(car(stack_begin))))),
88 // make_segment_sequence_front(cdr(stack_begin))));
92 template <typename Stack, std::size_t Size = Stack::size::value>
93 struct make_segment_sequence_front
95 // assert(end(segments(front(car(stack_begin)))) == end(car(cdr(stack_begin))));
98 typename result_of::end<
99 typename remove_reference<
101 typename result_of::segments<
102 typename remove_reference<
104 typename result_of::deref<
105 typename Stack::car_type::begin_type
113 , typename Stack::cdr_type::car_type::end_type
118 typename result_of::next<
119 typename Stack::cdr_type::car_type::begin_type
121 , typename result_of::end<
122 typename remove_reference<
124 typename result_of::segments<
125 typename remove_reference<
127 typename result_of::deref<
128 typename Stack::car_type::begin_type
140 make_segment_sequence_front<typename Stack::cdr_type>
145 typename result_of::push_front<
147 , typename recurse::type
152 static type call(Stack const& stack)
154 //return segment_sequence(
156 // iterator_range(next(begin(car(cdr(stack_begin)))), end(segments(front(car(stack_begin))))),
157 // make_segment_sequence_front(cdr(stack_begin))));
160 rest_type(fusion::next(stack.cdr.car.first), fusion::end(fusion::segments(*stack.car.first)))
161 , recurse::call(stack.cdr)));
165 template <typename Stack>
166 struct make_segment_sequence_front<Stack, 2>
168 // assert(end(front(car(stack_begin))) == end(car(cdr(stack_begin))));
171 typename result_of::end<
172 typename remove_reference<
174 typename result_of::deref<
175 typename Stack::car_type::begin_type
180 , typename Stack::cdr_type::car_type::end_type
185 typename Stack::cdr_type::car_type::begin_type
186 , typename result_of::end<
187 typename remove_reference<
189 typename result_of::deref<
190 typename Stack::car_type::begin_type
198 static type call(Stack const& stack)
200 // return iterator_range(begin(car(cdr(stack_begin))), end(front(car(stack_begin))));
201 return type(stack.cdr.car.first, fusion::end(*stack.car.first));
205 template <typename Stack>
206 struct make_segment_sequence_front<Stack, 1>
208 typedef typename Stack::cdr_type type; // nil_
210 static type call(Stack const &stack)
216 //auto make_segment_sequence_back(stack_end)
218 // switch (size(stack_end))
223 // // car(cdr(stack_back)) is a range over values.
224 // assert(end(front(car(stack_end))) == end(car(cdr(stack_end))));
225 // return iterator_range(begin(front(car(stack_end))), begin(car(cdr(stack_end))));
227 // // car(cdr(stack_begin)) is a range over segments. We replace the
228 // // back with a view that is restricted.
229 // assert(end(segments(front(car(stack_end)))) == end(car(cdr(stack_end))));
230 // return segment_sequence(
232 // iterator_range(begin(segments(front(car(stack_end)))), begin(car(cdr(stack_end)))),
233 // make_segment_sequence_back(cdr(stack_end))));
237 template <typename Stack, std::size_t Size = Stack::size::value>
238 struct make_segment_sequence_back
240 // assert(end(segments(front(car(stack_begin)))) == end(car(cdr(stack_begin))));
243 typename result_of::end<
244 typename remove_reference<
246 typename result_of::segments<
247 typename remove_reference<
249 typename result_of::deref<
250 typename Stack::car_type::begin_type
258 , typename Stack::cdr_type::car_type::end_type
263 typename result_of::begin<
264 typename remove_reference<
266 typename result_of::segments<
267 typename remove_reference<
269 typename result_of::deref<
270 typename Stack::car_type::begin_type
278 , typename Stack::cdr_type::car_type::begin_type
283 make_segment_sequence_back<typename Stack::cdr_type>
288 typename result_of::push_back<
290 , typename recurse::type
295 static type call(Stack const& stack)
297 // return segment_sequence(
299 // iterator_range(begin(segments(front(car(stack_end)))), begin(car(cdr(stack_end)))),
300 // make_segment_sequence_back(cdr(stack_end))));
303 rest_type(fusion::begin(fusion::segments(*stack.car.first)), stack.cdr.car.first)
304 , recurse::call(stack.cdr)));
308 template <typename Stack>
309 struct make_segment_sequence_back<Stack, 2>
311 // assert(end(front(car(stack_end))) == end(car(cdr(stack_end))));
314 typename result_of::end<
315 typename remove_reference<
317 typename result_of::deref<
318 typename Stack::car_type::begin_type
323 , typename Stack::cdr_type::car_type::end_type
328 typename result_of::begin<
329 typename remove_reference<
331 typename result_of::deref<
332 typename Stack::car_type::begin_type
337 , typename Stack::cdr_type::car_type::begin_type
341 static type call(Stack const& stack)
343 // return iterator_range(begin(front(car(stack_end))), begin(car(cdr(stack_end))));
344 return type(fusion::begin(*stack.car.first), stack.cdr.car.first);
348 template <typename Stack>
349 struct make_segment_sequence_back<Stack, 1>
351 typedef typename Stack::cdr_type type; // nil_
353 static type call(Stack const& stack)
359 //auto make_segmented_range_reduce(stack_begin, stack_end)
361 // if (size(stack_begin) == 1 && size(stack_end) == 1)
363 // return segment_sequence(
365 // iterator_range(begin(car(stack_begin)), begin(car(stack_end)))));
369 // // We are in the case where both begin_stack and/or end_stack have
370 // // more than one element. Throw away any part of the tree where
371 // // begin and end refer to the same segment.
372 // if (begin(car(stack_begin)) == begin(car(stack_end)))
374 // return make_segmented_range_reduce(cdr(stack_begin), cdr(stack_end));
378 // // We are in the case where begin_stack and end_stack (a) have
379 // // more than one element each, and (b) they point to different
380 // // segments. We must construct a segmented sequence.
381 // return segment_sequence(
385 // fusion::next(begin(car(stack_begin))),
386 // begin(car(stack_end))), // a range of (possibly segmented) ranges.
387 // make_segment_sequence_front(stack_begin)), // should be a (possibly segmented) range.
388 // make_segment_sequence_back(stack_end))); // should be a (possibly segmented) range.
396 , int StackBeginSize = StackBegin::size::value
397 , int StackEndSize = StackEnd::size::value>
398 struct make_segmented_range_reduce;
405 typename StackBegin::car_type::begin_type
406 , typename StackEnd::car_type::begin_type
408 struct make_segmented_range_reduce2
412 typename result_of::next<
413 typename StackBegin::car_type::begin_type
415 , typename StackEnd::car_type::begin_type
421 typename result_of::push_back<
422 typename result_of::push_front<
424 , typename make_segment_sequence_front<StackBegin>::type
426 , typename make_segment_sequence_back<StackEnd>::type
431 static type call(StackBegin stack_begin, StackEnd stack_end)
433 //return segment_sequence(
437 // fusion::next(begin(car(stack_begin))),
438 // begin(car(stack_end))), // a range of (possibly segmented) ranges.
439 // make_segment_sequence_front(stack_begin)), // should be a (possibly segmented) range.
440 // make_segment_sequence_back(stack_end))); // should be a (possibly segmented) range.
444 rest_type(fusion::next(stack_begin.car.first), stack_end.car.first)
445 , make_segment_sequence_front<StackBegin>::call(stack_begin))
446 , make_segment_sequence_back<StackEnd>::call(stack_end)));
450 template <typename StackBegin, typename StackEnd>
451 struct make_segmented_range_reduce2<StackBegin, StackEnd, true>
454 make_segmented_range_reduce<
455 typename StackBegin::cdr_type
456 , typename StackEnd::cdr_type
464 static type call(StackBegin stack_begin, StackEnd stack_end)
466 return impl::call(stack_begin.cdr, stack_end.cdr);
470 template <typename StackBegin, typename StackEnd, int StackBeginSize, int StackEndSize>
471 struct make_segmented_range_reduce
472 : make_segmented_range_reduce2<StackBegin, StackEnd>
475 template <typename StackBegin, typename StackEnd>
476 struct make_segmented_range_reduce<StackBegin, StackEnd, 1, 1>
480 typename StackBegin::car_type::begin_type
481 , typename StackEnd::car_type::begin_type
486 single_view<range_type>
490 segment_sequence<segment_type>
493 static type call(StackBegin stack_begin, StackEnd stack_end)
495 //return segment_sequence(
497 // iterator_range(begin(car(stack_begin)), begin(car(stack_end)))));
498 return type(segment_type(range_type(stack_begin.car.first, stack_end.car.first)));
502 //auto make_segmented_range(begin, end)
504 // return make_segmented_range_reduce(reverse(begin.context), reverse(end.context));
507 template <typename Begin, typename End>
508 struct make_segmented_range
510 typedef reverse_cons<typename Begin::context_type> reverse_begin_cons;
511 typedef reverse_cons<typename End::context_type> reverse_end_cons;
514 make_segmented_range_reduce<
515 typename reverse_begin_cons::type
516 , typename reverse_end_cons::type
520 typedef typename impl::type type;
522 static type call(Begin const& begin, End const& end)
525 reverse_begin_cons::call(begin.context)
526 , reverse_end_cons::call(end.context));