| /*============================================================================= |
| 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/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 = |
| result_of::equal_to< |
| typename StackBegin::car_type::begin_type |
| , typename StackEnd::car_type::begin_type |
| >::type::value> |
| 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> |
| {}; |
| |
| 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 |
