X-Git-Url: https://git.donarmstrong.com/?p=rsem.git;a=blobdiff_plain;f=boost%2Ffusion%2Fview%2Fiterator_range%2Fdetail%2Fsegmented_iterator_range.hpp;fp=boost%2Ffusion%2Fview%2Fiterator_range%2Fdetail%2Fsegmented_iterator_range.hpp;h=2e4e0782155a08fd95c39f2dbaced9c0715aaca7;hp=0000000000000000000000000000000000000000;hb=2d71eb92104693ca9baa5a2e1c23eeca776d8fd3;hpb=da57529b92adbb7ae74a89861cb39fb35ac7c62d

diff --git a/boost/fusion/view/iterator_range/detail/segmented_iterator_range.hpp b/boost/fusion/view/iterator_range/detail/segmented_iterator_range.hpp
new file mode 100644
index 0000000..2e4e078
--- /dev/null
+++ b/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