123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556 |
- /*=============================================================================
- Copyright (c) 2011 Eric Niebler
- Distributed under the Boost Software License, Version 1.0. (See accompanying
- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
- ==============================================================================*/
- #if !defined(BOOST_FUSION_SEGMENTED_ITERATOR_RANGE_HPP_INCLUDED)
- #define BOOST_FUSION_SEGMENTED_ITERATOR_RANGE_HPP_INCLUDED
- #include <boost/fusion/support/config.hpp>
- #include <boost/detail/workaround.hpp>
- #include <boost/mpl/assert.hpp>
- #include <boost/type_traits/add_const.hpp>
- #include <boost/type_traits/remove_reference.hpp>
- #include <boost/fusion/support/tag_of.hpp>
- #include <boost/fusion/sequence/intrinsic/begin.hpp>
- #include <boost/fusion/sequence/intrinsic/end.hpp>
- #include <boost/fusion/iterator/next.hpp>
- #include <boost/fusion/iterator/deref.hpp>
- #include <boost/fusion/sequence/intrinsic/segments.hpp>
- #include <boost/fusion/algorithm/transformation/push_back.hpp>
- #include <boost/fusion/algorithm/transformation/push_front.hpp>
- #include <boost/fusion/iterator/equal_to.hpp>
- #include <boost/fusion/container/list/detail/reverse_cons.hpp>
- #include <boost/fusion/iterator/detail/segment_sequence.hpp>
- #include <boost/fusion/support/is_sequence.hpp>
- #include <boost/utility/enable_if.hpp>
- // Invariants:
- // - Each segmented iterator has a stack
- // - Each value in the stack is an iterator range
- // - The range at the top of the stack points to values
- // - All other ranges point to ranges
- // - The front of each range in the stack (besides the
- // topmost) is the range above it
- namespace boost { namespace fusion
- {
- template <typename First, typename Last>
- struct iterator_range;
- namespace result_of
- {
- template <typename Sequence, typename T>
- struct push_back;
- template <typename Sequence, typename T>
- struct push_front;
- }
- template <typename Sequence, typename T>
- BOOST_CXX14_CONSTEXPR BOOST_FUSION_GPU_ENABLED
- inline typename
- lazy_enable_if<
- traits::is_sequence<Sequence>
- , result_of::push_back<Sequence const, T>
- >::type
- push_back(Sequence const& seq, T const& x);
- template <typename Sequence, typename T>
- BOOST_CXX14_CONSTEXPR BOOST_FUSION_GPU_ENABLED
- inline typename
- lazy_enable_if<
- traits::is_sequence<Sequence>
- , result_of::push_front<Sequence const, T>
- >::type
- push_front(Sequence const& seq, T const& x);
- }}
- namespace boost { namespace fusion { namespace detail
- {
- //auto make_segment_sequence_front(stack_begin)
- //{
- // switch (size(stack_begin))
- // {
- // case 1:
- // return nil_;
- // case 2:
- // // car(cdr(stack_begin)) is a range over values.
- // assert(end(front(car(stack_begin))) == end(car(cdr(stack_begin))));
- // return iterator_range(begin(car(cdr(stack_begin))), end(front(car(stack_begin))));
- // default:
- // // car(cdr(stack_begin)) is a range over segments. We replace the
- // // front with a view that is restricted.
- // assert(end(segments(front(car(stack_begin)))) == end(car(cdr(stack_begin))));
- // return segment_sequence(
- // push_front(
- // // The following could be a segment_sequence. It then gets wrapped
- // // in a single_view, and push_front puts it in a join_view with the
- // // following iterator_range.
- // iterator_range(next(begin(car(cdr(stack_begin)))), end(segments(front(car(stack_begin))))),
- // make_segment_sequence_front(cdr(stack_begin))));
- // }
- //}
- template <typename Stack, std::size_t Size = Stack::size::value>
- struct make_segment_sequence_front
- {
- // assert(end(segments(front(car(stack_begin)))) == end(car(cdr(stack_begin))));
- BOOST_MPL_ASSERT((
- result_of::equal_to<
- typename result_of::end<
- typename remove_reference<
- typename add_const<
- typename result_of::segments<
- typename remove_reference<
- typename add_const<
- typename result_of::deref<
- typename Stack::car_type::begin_type
- >::type
- >::type
- >::type
- >::type
- >::type
- >::type
- >::type
- , typename Stack::cdr_type::car_type::end_type
- >));
- typedef
- iterator_range<
- typename result_of::next<
- typename Stack::cdr_type::car_type::begin_type
- >::type
- , typename result_of::end<
- typename remove_reference<
- typename add_const<
- typename result_of::segments<
- typename remove_reference<
- typename add_const<
- typename result_of::deref<
- typename Stack::car_type::begin_type
- >::type
- >::type
- >::type
- >::type
- >::type
- >::type
- >::type
- >
- rest_type;
- typedef
- make_segment_sequence_front<typename Stack::cdr_type>
- recurse;
- typedef
- segment_sequence<
- typename result_of::push_front<
- rest_type const
- , typename recurse::type
- >::type
- >
- type;
- BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
- static type call(Stack const& stack)
- {
- //return segment_sequence(
- // push_front(
- // iterator_range(next(begin(car(cdr(stack_begin)))), end(segments(front(car(stack_begin))))),
- // make_segment_sequence_front(cdr(stack_begin))));
- return type(
- fusion::push_front(
- rest_type(fusion::next(stack.cdr.car.first), fusion::end(fusion::segments(*stack.car.first)))
- , recurse::call(stack.cdr)));
- }
- };
- template <typename Stack>
- struct make_segment_sequence_front<Stack, 2>
- {
- // assert(end(front(car(stack_begin))) == end(car(cdr(stack_begin))));
- BOOST_MPL_ASSERT((
- result_of::equal_to<
- typename result_of::end<
- typename remove_reference<
- typename add_const<
- typename result_of::deref<
- typename Stack::car_type::begin_type
- >::type
- >::type
- >::type
- >::type
- , typename Stack::cdr_type::car_type::end_type
- >));
- typedef
- iterator_range<
- typename Stack::cdr_type::car_type::begin_type
- , typename result_of::end<
- typename remove_reference<
- typename add_const<
- typename result_of::deref<
- typename Stack::car_type::begin_type
- >::type
- >::type
- >::type
- >::type
- >
- type;
- BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
- static type call(Stack const& stack)
- {
- // return iterator_range(begin(car(cdr(stack_begin))), end(front(car(stack_begin))));
- return type(stack.cdr.car.first, fusion::end(*stack.car.first));
- }
- };
- template <typename Stack>
- struct make_segment_sequence_front<Stack, 1>
- {
- typedef typename Stack::cdr_type type; // nil_
- BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
- static type call(Stack const &stack)
- {
- return stack.cdr;
- }
- };
- //auto make_segment_sequence_back(stack_end)
- //{
- // switch (size(stack_end))
- // {
- // case 1:
- // return nil_;
- // case 2:
- // // car(cdr(stack_back)) is a range over values.
- // assert(end(front(car(stack_end))) == end(car(cdr(stack_end))));
- // return iterator_range(begin(front(car(stack_end))), begin(car(cdr(stack_end))));
- // default:
- // // car(cdr(stack_begin)) is a range over segments. We replace the
- // // back with a view that is restricted.
- // assert(end(segments(front(car(stack_end)))) == end(car(cdr(stack_end))));
- // return segment_sequence(
- // push_back(
- // iterator_range(begin(segments(front(car(stack_end)))), begin(car(cdr(stack_end)))),
- // make_segment_sequence_back(cdr(stack_end))));
- // }
- //}
- template <typename Stack, std::size_t Size = Stack::size::value>
- struct make_segment_sequence_back
- {
- // assert(end(segments(front(car(stack_begin)))) == end(car(cdr(stack_begin))));
- BOOST_MPL_ASSERT((
- result_of::equal_to<
- typename result_of::end<
- typename remove_reference<
- typename add_const<
- typename result_of::segments<
- typename remove_reference<
- typename add_const<
- typename result_of::deref<
- typename Stack::car_type::begin_type
- >::type
- >::type
- >::type
- >::type
- >::type
- >::type
- >::type
- , typename Stack::cdr_type::car_type::end_type
- >));
- typedef
- iterator_range<
- typename result_of::begin<
- typename remove_reference<
- typename add_const<
- typename result_of::segments<
- typename remove_reference<
- typename add_const<
- typename result_of::deref<
- typename Stack::car_type::begin_type
- >::type
- >::type
- >::type
- >::type
- >::type
- >::type
- >::type
- , typename Stack::cdr_type::car_type::begin_type
- >
- rest_type;
- typedef
- make_segment_sequence_back<typename Stack::cdr_type>
- recurse;
- typedef
- segment_sequence<
- typename result_of::push_back<
- rest_type const
- , typename recurse::type
- >::type
- >
- type;
- BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
- static type call(Stack const& stack)
- {
- // return segment_sequence(
- // push_back(
- // iterator_range(begin(segments(front(car(stack_end)))), begin(car(cdr(stack_end)))),
- // make_segment_sequence_back(cdr(stack_end))));
- return type(
- fusion::push_back(
- rest_type(fusion::begin(fusion::segments(*stack.car.first)), stack.cdr.car.first)
- , recurse::call(stack.cdr)));
- }
- };
- template <typename Stack>
- struct make_segment_sequence_back<Stack, 2>
- {
- // assert(end(front(car(stack_end))) == end(car(cdr(stack_end))));
- BOOST_MPL_ASSERT((
- result_of::equal_to<
- typename result_of::end<
- typename remove_reference<
- typename add_const<
- typename result_of::deref<
- typename Stack::car_type::begin_type
- >::type
- >::type
- >::type
- >::type
- , typename Stack::cdr_type::car_type::end_type
- >));
- typedef
- iterator_range<
- typename result_of::begin<
- typename remove_reference<
- typename add_const<
- typename result_of::deref<
- typename Stack::car_type::begin_type
- >::type
- >::type
- >::type
- >::type
- , typename Stack::cdr_type::car_type::begin_type
- >
- type;
- BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
- static type call(Stack const& stack)
- {
- // return iterator_range(begin(front(car(stack_end))), begin(car(cdr(stack_end))));
- return type(fusion::begin(*stack.car.first), stack.cdr.car.first);
- }
- };
- template <typename Stack>
- struct make_segment_sequence_back<Stack, 1>
- {
- typedef typename Stack::cdr_type type; // nil_
- BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
- static type call(Stack const& stack)
- {
- return stack.cdr;
- }
- };
- //auto make_segmented_range_reduce(stack_begin, stack_end)
- //{
- // if (size(stack_begin) == 1 && size(stack_end) == 1)
- // {
- // return segment_sequence(
- // single_view(
- // iterator_range(begin(car(stack_begin)), begin(car(stack_end)))));
- // }
- // else
- // {
- // // We are in the case where both begin_stack and/or end_stack have
- // // more than one element. Throw away any part of the tree where
- // // begin and end refer to the same segment.
- // if (begin(car(stack_begin)) == begin(car(stack_end)))
- // {
- // return make_segmented_range_reduce(cdr(stack_begin), cdr(stack_end));
- // }
- // else
- // {
- // // We are in the case where begin_stack and end_stack (a) have
- // // more than one element each, and (b) they point to different
- // // segments. We must construct a segmented sequence.
- // return segment_sequence(
- // push_back(
- // push_front(
- // iterator_range(
- // fusion::next(begin(car(stack_begin))),
- // begin(car(stack_end))), // a range of (possibly segmented) ranges.
- // make_segment_sequence_front(stack_begin)), // should be a (possibly segmented) range.
- // make_segment_sequence_back(stack_end))); // should be a (possibly segmented) range.
- // }
- // }
- //}
- template <
- typename StackBegin
- , typename StackEnd
- , int StackBeginSize = StackBegin::size::value
- , int StackEndSize = StackEnd::size::value>
- struct make_segmented_range_reduce;
- template <
- typename StackBegin
- , typename StackEnd
- , bool SameSegment
- #if !(BOOST_WORKAROUND(BOOST_GCC, >= 40000) && BOOST_WORKAROUND(BOOST_GCC, < 40200))
- = result_of::equal_to<
- typename StackBegin::car_type::begin_type
- , typename StackEnd::car_type::begin_type
- >::type::value
- #endif
- >
- struct make_segmented_range_reduce2
- {
- typedef
- iterator_range<
- typename result_of::next<
- typename StackBegin::car_type::begin_type
- >::type
- , typename StackEnd::car_type::begin_type
- >
- rest_type;
- typedef
- segment_sequence<
- typename result_of::push_back<
- typename result_of::push_front<
- rest_type const
- , typename make_segment_sequence_front<StackBegin>::type
- >::type const
- , typename make_segment_sequence_back<StackEnd>::type
- >::type
- >
- type;
- BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
- static type call(StackBegin stack_begin, StackEnd stack_end)
- {
- //return segment_sequence(
- // push_back(
- // push_front(
- // iterator_range(
- // fusion::next(begin(car(stack_begin))),
- // begin(car(stack_end))), // a range of (possibly segmented) ranges.
- // make_segment_sequence_front(stack_begin)), // should be a (possibly segmented) range.
- // make_segment_sequence_back(stack_end))); // should be a (possibly segmented) range.
- return type(
- fusion::push_back(
- fusion::push_front(
- rest_type(fusion::next(stack_begin.car.first), stack_end.car.first)
- , make_segment_sequence_front<StackBegin>::call(stack_begin))
- , make_segment_sequence_back<StackEnd>::call(stack_end)));
- }
- };
- template <typename StackBegin, typename StackEnd>
- struct make_segmented_range_reduce2<StackBegin, StackEnd, true>
- {
- typedef
- make_segmented_range_reduce<
- typename StackBegin::cdr_type
- , typename StackEnd::cdr_type
- >
- impl;
- typedef
- typename impl::type
- type;
- BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
- static type call(StackBegin stack_begin, StackEnd stack_end)
- {
- return impl::call(stack_begin.cdr, stack_end.cdr);
- }
- };
- template <typename StackBegin, typename StackEnd, int StackBeginSize, int StackEndSize>
- struct make_segmented_range_reduce
- : make_segmented_range_reduce2<StackBegin, StackEnd
- #if BOOST_WORKAROUND(BOOST_GCC, >= 40000) && BOOST_WORKAROUND(BOOST_GCC, < 40200)
- , result_of::equal_to<
- typename StackBegin::car_type::begin_type
- , typename StackEnd::car_type::begin_type
- >::type::value
- #endif
- >
- {};
- template <typename StackBegin, typename StackEnd>
- struct make_segmented_range_reduce<StackBegin, StackEnd, 1, 1>
- {
- typedef
- iterator_range<
- typename StackBegin::car_type::begin_type
- , typename StackEnd::car_type::begin_type
- >
- range_type;
- typedef
- single_view<range_type>
- segment_type;
- typedef
- segment_sequence<segment_type>
- type;
- BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
- static type call(StackBegin stack_begin, StackEnd stack_end)
- {
- //return segment_sequence(
- // single_view(
- // iterator_range(begin(car(stack_begin)), begin(car(stack_end)))));
- return type(segment_type(range_type(stack_begin.car.first, stack_end.car.first)));
- }
- };
- //auto make_segmented_range(begin, end)
- //{
- // return make_segmented_range_reduce(reverse(begin.context), reverse(end.context));
- //}
- template <typename Begin, typename End>
- struct make_segmented_range
- {
- typedef reverse_cons<typename Begin::context_type> reverse_begin_cons;
- typedef reverse_cons<typename End::context_type> reverse_end_cons;
- typedef
- make_segmented_range_reduce<
- typename reverse_begin_cons::type
- , typename reverse_end_cons::type
- >
- impl;
- typedef typename impl::type type;
- BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
- static type call(Begin const& begin, End const& end)
- {
- return impl::call(
- reverse_begin_cons::call(begin.context)
- , reverse_end_cons::call(end.context));
- }
- };
- }}}
- #endif
|