--- /dev/null
+/*=============================================================================
+ 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
projects / rsem.git / blobdiff