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_ITERATOR_RANGE_HPP_INCLUDED)
8#define BOOST_FUSION_SEGMENTED_ITERATOR_RANGE_HPP_INCLUDED
9
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>
28
29// Invariants:
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
36
37namespace boost { namespace fusion
38{
39 template <typename First, typename Last>
40 struct iterator_range;
41
42 namespace result_of
43 {
44 template <typename Sequence, typename T>
45 struct push_back;
46
47 template <typename Sequence, typename T>
48 struct push_front;
49 }
50
51 template <typename Sequence, typename T>
52 BOOST_CXX14_CONSTEXPR BOOST_FUSION_GPU_ENABLED
53 inline typename
54 lazy_enable_if<
55 traits::is_sequence<Sequence>
56 , result_of::push_back<Sequence const, T>
57 >::type
58 push_back(Sequence const& seq, T const& x);
59
60 template <typename Sequence, typename T>
61 BOOST_CXX14_CONSTEXPR BOOST_FUSION_GPU_ENABLED
62 inline typename
63 lazy_enable_if<
64 traits::is_sequence<Sequence>
65 , result_of::push_front<Sequence const, T>
66 >::type
67 push_front(Sequence const& seq, T const& x);
68}}
69
70namespace boost { namespace fusion { namespace detail
71{
72 //auto make_segment_sequence_front(stack_begin)
73 //{
74 // switch (size(stack_begin))
75 // {
76 // case 1:
77 // return nil_;
78 // case 2:
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))));
82 // default:
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(
87 // push_front(
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))));
93 // }
94 //}
95
96 template <typename Stack, std::size_t Size = Stack::size::value>
97 struct make_segment_sequence_front
98 {
99 // assert(end(segments(front(car(stack_begin)))) == end(car(cdr(stack_begin))));
100 BOOST_MPL_ASSERT((
101 result_of::equal_to<
102 typename result_of::end<
103 typename remove_reference<
104 typename add_const<
105 typename result_of::segments<
106 typename remove_reference<
107 typename add_const<
108 typename result_of::deref<
109 typename Stack::car_type::begin_type
110 >::type
111 >::type
112 >::type
113 >::type
114 >::type
115 >::type
116 >::type
117 , typename Stack::cdr_type::car_type::end_type
118 >));
119
120 typedef
121 iterator_range<
122 typename result_of::next<
123 typename Stack::cdr_type::car_type::begin_type
124 >::type
125 , typename result_of::end<
126 typename remove_reference<
127 typename add_const<
128 typename result_of::segments<
129 typename remove_reference<
130 typename add_const<
131 typename result_of::deref<
132 typename Stack::car_type::begin_type
133 >::type
134 >::type
135 >::type
136 >::type
137 >::type
138 >::type
139 >::type
140 >
141 rest_type;
142
143 typedef
144 make_segment_sequence_front<typename Stack::cdr_type>
145 recurse;
146
147 typedef
148 segment_sequence<
149 typename result_of::push_front<
150 rest_type const
151 , typename recurse::type
152 >::type
153 >
154 type;
155
156 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
157 static type call(Stack const& stack)
158 {
159 //return segment_sequence(
160 // push_front(
161 // iterator_range(next(begin(car(cdr(stack_begin)))), end(segments(front(car(stack_begin))))),
162 // make_segment_sequence_front(cdr(stack_begin))));
163 return type(
164 fusion::push_front(
165 rest_type(fusion::next(stack.cdr.car.first), fusion::end(fusion::segments(*stack.car.first)))
166 , recurse::call(stack.cdr)));
167 }
168 };
169
170 template <typename Stack>
171 struct make_segment_sequence_front<Stack, 2>
172 {
173 // assert(end(front(car(stack_begin))) == end(car(cdr(stack_begin))));
174 BOOST_MPL_ASSERT((
175 result_of::equal_to<
176 typename result_of::end<
177 typename remove_reference<
178 typename add_const<
179 typename result_of::deref<
180 typename Stack::car_type::begin_type
181 >::type
182 >::type
183 >::type
184 >::type
185 , typename Stack::cdr_type::car_type::end_type
186 >));
187
188 typedef
189 iterator_range<
190 typename Stack::cdr_type::car_type::begin_type
191 , typename result_of::end<
192 typename remove_reference<
193 typename add_const<
194 typename result_of::deref<
195 typename Stack::car_type::begin_type
196 >::type
197 >::type
198 >::type
199 >::type
200 >
201 type;
202
203 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
204 static type call(Stack const& stack)
205 {
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));
208 }
209 };
210
211 template <typename Stack>
212 struct make_segment_sequence_front<Stack, 1>
213 {
214 typedef typename Stack::cdr_type type; // nil_
215
216 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
217 static type call(Stack const &stack)
218 {
219 return stack.cdr;
220 }
221 };
222
223 //auto make_segment_sequence_back(stack_end)
224 //{
225 // switch (size(stack_end))
226 // {
227 // case 1:
228 // return nil_;
229 // case 2:
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))));
233 // default:
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(
238 // push_back(
239 // iterator_range(begin(segments(front(car(stack_end)))), begin(car(cdr(stack_end)))),
240 // make_segment_sequence_back(cdr(stack_end))));
241 // }
242 //}
243
244 template <typename Stack, std::size_t Size = Stack::size::value>
245 struct make_segment_sequence_back
246 {
247 // assert(end(segments(front(car(stack_begin)))) == end(car(cdr(stack_begin))));
248 BOOST_MPL_ASSERT((
249 result_of::equal_to<
250 typename result_of::end<
251 typename remove_reference<
252 typename add_const<
253 typename result_of::segments<
254 typename remove_reference<
255 typename add_const<
256 typename result_of::deref<
257 typename Stack::car_type::begin_type
258 >::type
259 >::type
260 >::type
261 >::type
262 >::type
263 >::type
264 >::type
265 , typename Stack::cdr_type::car_type::end_type
266 >));
267
268 typedef
269 iterator_range<
270 typename result_of::begin<
271 typename remove_reference<
272 typename add_const<
273 typename result_of::segments<
274 typename remove_reference<
275 typename add_const<
276 typename result_of::deref<
277 typename Stack::car_type::begin_type
278 >::type
279 >::type
280 >::type
281 >::type
282 >::type
283 >::type
284 >::type
285 , typename Stack::cdr_type::car_type::begin_type
286 >
287 rest_type;
288
289 typedef
290 make_segment_sequence_back<typename Stack::cdr_type>
291 recurse;
292
293 typedef
294 segment_sequence<
295 typename result_of::push_back<
296 rest_type const
297 , typename recurse::type
298 >::type
299 >
300 type;
301
302 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
303 static type call(Stack const& stack)
304 {
305 // return segment_sequence(
306 // push_back(
307 // iterator_range(begin(segments(front(car(stack_end)))), begin(car(cdr(stack_end)))),
308 // make_segment_sequence_back(cdr(stack_end))));
309 return type(
310 fusion::push_back(
311 rest_type(fusion::begin(fusion::segments(*stack.car.first)), stack.cdr.car.first)
312 , recurse::call(stack.cdr)));
313 }
314 };
315
316 template <typename Stack>
317 struct make_segment_sequence_back<Stack, 2>
318 {
319 // assert(end(front(car(stack_end))) == end(car(cdr(stack_end))));
320 BOOST_MPL_ASSERT((
321 result_of::equal_to<
322 typename result_of::end<
323 typename remove_reference<
324 typename add_const<
325 typename result_of::deref<
326 typename Stack::car_type::begin_type
327 >::type
328 >::type
329 >::type
330 >::type
331 , typename Stack::cdr_type::car_type::end_type
332 >));
333
334 typedef
335 iterator_range<
336 typename result_of::begin<
337 typename remove_reference<
338 typename add_const<
339 typename result_of::deref<
340 typename Stack::car_type::begin_type
341 >::type
342 >::type
343 >::type
344 >::type
345 , typename Stack::cdr_type::car_type::begin_type
346 >
347 type;
348
349 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
350 static type call(Stack const& stack)
351 {
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);
354 }
355 };
356
357 template <typename Stack>
358 struct make_segment_sequence_back<Stack, 1>
359 {
360 typedef typename Stack::cdr_type type; // nil_
361
362 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
363 static type call(Stack const& stack)
364 {
365 return stack.cdr;
366 }
367 };
368
369 //auto make_segmented_range_reduce(stack_begin, stack_end)
370 //{
371 // if (size(stack_begin) == 1 && size(stack_end) == 1)
372 // {
373 // return segment_sequence(
374 // single_view(
375 // iterator_range(begin(car(stack_begin)), begin(car(stack_end)))));
376 // }
377 // else
378 // {
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)))
383 // {
384 // return make_segmented_range_reduce(cdr(stack_begin), cdr(stack_end));
385 // }
386 // else
387 // {
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(
392 // push_back(
393 // push_front(
394 // iterator_range(
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.
399 // }
400 // }
401 //}
402
403 template <
404 typename StackBegin
405 , typename StackEnd
406 , int StackBeginSize = StackBegin::size::value
407 , int StackEndSize = StackEnd::size::value>
408 struct make_segmented_range_reduce;
409
410 template <
411 typename StackBegin
412 , typename StackEnd
413 , bool SameSegment
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
418 >::type::value
419#endif
420 >
421 struct make_segmented_range_reduce2
422 {
423 typedef
424 iterator_range<
425 typename result_of::next<
426 typename StackBegin::car_type::begin_type
427 >::type
428 , typename StackEnd::car_type::begin_type
429 >
430 rest_type;
431
432 typedef
433 segment_sequence<
434 typename result_of::push_back<
435 typename result_of::push_front<
436 rest_type const
437 , typename make_segment_sequence_front<StackBegin>::type
438 >::type const
439 , typename make_segment_sequence_back<StackEnd>::type
440 >::type
441 >
442 type;
443
444 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
445 static type call(StackBegin stack_begin, StackEnd stack_end)
446 {
447 //return segment_sequence(
448 // push_back(
449 // push_front(
450 // iterator_range(
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.
455 return type(
456 fusion::push_back(
457 fusion::push_front(
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)));
461 }
462 };
463
464 template <typename StackBegin, typename StackEnd>
465 struct make_segmented_range_reduce2<StackBegin, StackEnd, true>
466 {
467 typedef
468 make_segmented_range_reduce<
469 typename StackBegin::cdr_type
470 , typename StackEnd::cdr_type
471 >
472 impl;
473
474 typedef
475 typename impl::type
476 type;
477
478 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
479 static type call(StackBegin stack_begin, StackEnd stack_end)
480 {
481 return impl::call(stack_begin.cdr, stack_end.cdr);
482 }
483 };
484
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
492 >::type::value
493#endif
494 >
495 {};
496
497 template <typename StackBegin, typename StackEnd>
498 struct make_segmented_range_reduce<StackBegin, StackEnd, 1, 1>
499 {
500 typedef
501 iterator_range<
502 typename StackBegin::car_type::begin_type
503 , typename StackEnd::car_type::begin_type
504 >
505 range_type;
506
507 typedef
508 single_view<range_type>
509 segment_type;
510
511 typedef
512 segment_sequence<segment_type>
513 type;
514
515 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
516 static type call(StackBegin stack_begin, StackEnd stack_end)
517 {
518 //return segment_sequence(
519 // single_view(
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)));
522 }
523 };
524
525 //auto make_segmented_range(begin, end)
526 //{
527 // return make_segmented_range_reduce(reverse(begin.context), reverse(end.context));
528 //}
529
530 template <typename Begin, typename End>
531 struct make_segmented_range
532 {
533 typedef reverse_cons<typename Begin::context_type> reverse_begin_cons;
534 typedef reverse_cons<typename End::context_type> reverse_end_cons;
535
536 typedef
537 make_segmented_range_reduce<
538 typename reverse_begin_cons::type
539 , typename reverse_end_cons::type
540 >
541 impl;
542
543 typedef typename impl::type type;
544
545 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
546 static type call(Begin const& begin, End const& end)
547 {
548 return impl::call(
549 reverse_begin_cons::call(begin.context)
550 , reverse_end_cons::call(end.context));
551 }
552 };
553
554}}}
555
556#endif
557

source code of include/boost/fusion/view/iterator_range/detail/segmented_iterator_range.hpp