diff options
Diffstat (limited to '3rdParty/Boost/src/boost/fusion/view/iterator_range/detail/segmented_iterator_range.hpp')
-rw-r--r-- | 3rdParty/Boost/src/boost/fusion/view/iterator_range/detail/segmented_iterator_range.hpp | 532 |
1 files changed, 532 insertions, 0 deletions
diff --git a/3rdParty/Boost/src/boost/fusion/view/iterator_range/detail/segmented_iterator_range.hpp b/3rdParty/Boost/src/boost/fusion/view/iterator_range/detail/segmented_iterator_range.hpp new file mode 100644 index 0000000..9bf459c --- /dev/null +++ b/3rdParty/Boost/src/boost/fusion/view/iterator_range/detail/segmented_iterator_range.hpp @@ -0,0 +1,532 @@ +/*============================================================================= + 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/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> + 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> + 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; + + 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; + + 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 + + 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; + + 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; + + 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 + + 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; + + 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; + + 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; + + 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; + + 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 |