/*=============================================================================
 Copyright (c) 2006 Eric Niebler

 Use, modification and distribution is subject to 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)
==============================================================================*/
#ifndef FUSION_SEGMENTED_ITERATOR_RANGE_EAN_05032006_1027
#define FUSION_SEGMENTED_ITERATOR_RANGE_EAN_05032006_1027

#include <boost/mpl/bool.hpp>
#include <boost/mpl/minus.hpp>
#include <boost/mpl/next_prior.hpp>
#include <boost/mpl/and.hpp>
#include <boost/type_traits/remove_cv.hpp>
#include <boost/type_traits/remove_reference.hpp>
#include <boost/fusion/iterator/mpl/convert_iterator.hpp>
#include <boost/fusion/container/list/cons.hpp>
#include <boost/fusion/view/joint_view.hpp>
#include <boost/fusion/view/single_view.hpp>
#include <boost/fusion/view/transform_view.hpp>
#include <boost/fusion/view/iterator_range.hpp>
#include <boost/fusion/view/ext_/multiple_view.hpp>
#include <boost/fusion/view/ext_/segmented_iterator.hpp>
#include <boost/fusion/adapted/mpl/mpl_iterator.hpp>

namespace boost { namespace fusion
{
    namespace detail
    {
        ////////////////////////////////////////////////////////////////////////////
        template<typename Cons, typename State = nil>
        struct reverse_cons;

        template<typename Car, typename Cdr, typename State>
        struct reverse_cons<cons<Car, Cdr>, State>
        {
            typedef reverse_cons<Cdr, cons<Car, State> > reverse;
            typedef typename reverse::type type;

            static type call(cons<Car, Cdr> const &cons, State const &state = State())
            {
                return reverse::call(cons.cdr, fusion::make_cons(cons.car, state));
            }
        };

        template<typename State>
        struct reverse_cons<nil, State>
        {
            typedef State type;

            static State const &call(nil const &, State const &state = State())
            {
                return state;
            }
        };

        ////////////////////////////////////////////////////////////////////////////
        // tags
        struct full_view {};
        struct left_view {};
        struct right_view {};
        struct center_view {};

        template<typename Tag>
        struct segmented_view_tag;

        ////////////////////////////////////////////////////////////////////////////
        // a segmented view of that includes all elements either to the
        // right or the left of a segmented iterator.
        template<typename Tag, typename Cons1, typename Cons2 = void_>
        struct segmented_view
          : sequence_base<segmented_view<Tag, Cons1, Cons2> >
        {
            typedef segmented_view_tag<Tag> fusion_tag;
            typedef fusion_sequence_tag tag; // this gets picked up by MPL
            typedef mpl::true_ is_view;
            typedef forward_traversal_tag category;

            explicit segmented_view(Cons1 const &cons)
              : cons(cons)
            {}

            typedef Cons1 cons_type;
            cons_type const &cons;
        };

        // a segmented view that contains all the elements in between
        // two segmented iterators
        template<typename Cons1, typename Cons2>
        struct segmented_view<center_view, Cons1, Cons2>
          : sequence_base<segmented_view<center_view, Cons1, Cons2> >
        {
            typedef segmented_view_tag<center_view> fusion_tag;
            typedef fusion_sequence_tag tag; // this gets picked up by MPL
            typedef mpl::true_ is_view;
            typedef forward_traversal_tag category;

            segmented_view(Cons1 const &lcons, Cons2 const &rcons)
              : left_cons(lcons)
              , right_cons(rcons)
            {}

            typedef Cons1 left_cons_type;
            typedef Cons2 right_cons_type;

            left_cons_type const &left_cons;
            right_cons_type const &right_cons;
        };

        ////////////////////////////////////////////////////////////////////////////
        // Used to transform a sequence of segments. The first segment is
        // bounded by RightCons, and the last segment is bounded by LeftCons
        // and all the others are passed through unchanged.
        template<typename RightCons, typename LeftCons = RightCons>
        struct segments_transform
        {
            explicit segments_transform(RightCons const &cons_)
              : right_cons(cons_)
              , left_cons(cons_)
            {}

            segments_transform(RightCons const &right_cons_, LeftCons const &left_cons_)
              : right_cons(right_cons_)
              , left_cons(left_cons_)
            {}

            template<typename First, typename Second>
            struct result_;

            template<typename Second>
            struct result_<right_view, Second>
            {
                typedef segmented_view<right_view, RightCons> type;
            };

            template<typename Second>
            struct result_<left_view, Second>
            {
                typedef segmented_view<left_view, LeftCons> type;
            };

            template<typename Second>
            struct result_<full_view, Second>
            {
                typedef Second type;
            };

            template<typename Sig>
            struct result;

            template<typename This, typename First, typename Second>
            struct result<This(First, Second)>
              : result_<
                    typename remove_cv<typename remove_reference<First>::type>::type
                  , typename remove_cv<typename remove_reference<Second>::type>::type
                >
            {};

            template<typename Second>
            segmented_view<right_view, RightCons> operator ()(right_view, Second &second) const
            {
                return segmented_view<right_view, RightCons>(this->right_cons);
            }

            template<typename Second>
            segmented_view<left_view, LeftCons> operator ()(left_view, Second &second) const
            {
                return segmented_view<left_view, LeftCons>(this->left_cons);
            }

            template<typename Second>
            Second &operator ()(full_view, Second &second) const
            {
                return second;
            }

        private:
            RightCons const &right_cons;
            LeftCons const &left_cons;
        };

    } // namespace detail

    namespace extension
    {
        ////////////////////////////////////////////////////////////////////////////
        template<typename Tag>
        struct is_segmented_impl<detail::segmented_view_tag<Tag> >
        {
            template<typename Sequence>
            struct apply
              : mpl::true_
            {};
        };

        ////////////////////////////////////////////////////////////////////////////
        template<>
        struct segments_impl<detail::segmented_view_tag<detail::right_view> >
        {
            template<
                typename Sequence
              , typename Cdr = typename Sequence::cons_type::cdr_type
            >
            struct apply
            {
                typedef typename Sequence::cons_type::car_type segmented_range;
                typedef typename result_of::size<segmented_range>::type size;
                typedef typename mpl::prior<size>::type size_minus_1;
                typedef detail::segments_transform<Cdr> tfx;
                typedef joint_view<
                    single_view<detail::right_view> const
                  , multiple_view<size_minus_1, detail::full_view> const
                > mask;
                typedef transform_view<mask const, segmented_range const, tfx> type;

                static type call(Sequence &seq)
                {
                    return type(
                        mask(
                            make_single_view(detail::right_view())
                          , make_multiple_view<size_minus_1>(detail::full_view())
                        )
                      , seq.cons.car
                      , tfx(seq.cons.cdr)
                    );
                }
            };

            template<typename Sequence>
            struct apply<Sequence, nil>
            {
                typedef typename Sequence::cons_type::car_type segmented_range;
                typedef typename segmented_range::iterator_type begin;
                typedef typename segmented_range::sequence_non_ref_type sequence_type;
                typedef typename result_of::end<sequence_type>::type end;
                typedef iterator_range<begin, end> range;
                typedef single_view<range> type;

                static type call(Sequence &seq)
                {
                    return type(range(seq.cons.car.where_, fusion::end(seq.cons.car.sequence)));
                }
            };
        };

        ////////////////////////////////////////////////////////////////////////////
        template<>
        struct segments_impl<detail::segmented_view_tag<detail::left_view> >
        {
            template<
                typename Sequence
              , typename Cdr = typename Sequence::cons_type::cdr_type
            >
            struct apply
            {
                typedef typename Sequence::cons_type::car_type right_segmented_range;
                typedef typename right_segmented_range::sequence_type sequence_type;
                typedef typename right_segmented_range::iterator_type iterator_type;

                typedef iterator_range<
                    typename result_of::begin<sequence_type>::type
                  , typename result_of::next<iterator_type>::type
                > segmented_range;

                typedef detail::segments_transform<Cdr> tfx;
                typedef typename result_of::size<segmented_range>::type size;
                typedef typename mpl::prior<size>::type size_minus_1;
                typedef joint_view<
                    multiple_view<size_minus_1, detail::full_view> const
                  , single_view<detail::left_view> const
                > mask;
                typedef transform_view<mask const, segmented_range const, tfx> type;

                static type call(Sequence &seq)
                {
                    return type(
                        mask(
                            make_multiple_view<size_minus_1>(detail::full_view())
                          , make_single_view(detail::left_view())
                        )
                      , segmented_range(fusion::begin(seq.cons.car.sequence), fusion::next(seq.cons.car.where_))
                      , tfx(seq.cons.cdr)
                    );
                }
            };

            template<typename Sequence>
            struct apply<Sequence, nil>
            {
                typedef typename Sequence::cons_type::car_type segmented_range;
                typedef typename segmented_range::sequence_non_ref_type sequence_type;
                typedef typename result_of::begin<sequence_type>::type begin;
                typedef typename segmented_range::iterator_type end;
                typedef iterator_range<begin, end> range;
                typedef single_view<range> type;

                static type call(Sequence &seq)
                {
                    return type(range(fusion::begin(seq.cons.car.sequence), seq.cons.car.where_));
                }
            };
        };

        ////////////////////////////////////////////////////////////////////////////
        template<>
        struct segments_impl<detail::segmented_view_tag<detail::center_view> >
        {
            template<typename Sequence>
            struct apply
            {
                typedef typename Sequence::right_cons_type right_cons_type;
                typedef typename Sequence::left_cons_type left_cons_type;
                typedef typename right_cons_type::car_type right_segmented_range;
                typedef typename left_cons_type::car_type left_segmented_range;

                typedef iterator_range<
                    typename result_of::begin<left_segmented_range>::type
                  , typename result_of::next<typename result_of::begin<right_segmented_range>::type>::type
                > segmented_range;

                typedef typename mpl::minus<
                    typename result_of::size<segmented_range>::type
                  , mpl::int_<2>
                >::type size_minus_2;

                BOOST_MPL_ASSERT_RELATION(0, <=, size_minus_2::value);

                typedef detail::segments_transform<
                    typename left_cons_type::cdr_type
                  , typename right_cons_type::cdr_type
                > tfx;

                typedef joint_view<
                    multiple_view<size_minus_2, detail::full_view> const
                  , single_view<detail::left_view> const
                > left_mask;

                typedef joint_view<
                    single_view<detail::right_view> const
                  , left_mask const
                > mask;

                typedef transform_view<mask const, segmented_range const, tfx> type;

                static type call(Sequence &seq)
                {
                    left_mask lmask(
                        make_multiple_view<size_minus_2>(detail::full_view())
                      , make_single_view(detail::left_view())
                    );
                    return type(
                        mask(make_single_view(detail::right_view()), lmask)
                      , segmented_range(fusion::begin(seq.left_cons.car), fusion::next(fusion::begin(seq.right_cons.car)))
                      , tfx(seq.left_cons.cdr, seq.right_cons.cdr)
                    );
                }
            };
        };
    }

    // specialize iterator_range for use with segmented iterators, so that
    // it presents a segmented view of the range.
    template<typename First, typename Last>
    struct iterator_range;

    template<typename First, typename Last>
    struct iterator_range<segmented_iterator<First>, segmented_iterator<Last> >
      : sequence_base<iterator_range<segmented_iterator<First>, segmented_iterator<Last> > >
    {
        typedef typename convert_iterator<segmented_iterator<First> >::type begin_type;
        typedef typename convert_iterator<segmented_iterator<Last> >::type end_type;
        typedef typename detail::reverse_cons<First>::type begin_cons_type;
        typedef typename detail::reverse_cons<Last>::type end_cons_type;
        typedef iterator_range_tag fusion_tag;
        typedef fusion_sequence_tag tag; // this gets picked up by MPL
        typedef typename traits::category_of<begin_type>::type category;
        typedef typename result_of::distance<begin_type, end_type>::type size;
        typedef mpl::true_ is_view;

        iterator_range(segmented_iterator<First> const& first_, segmented_iterator<Last> const& last_)
          : first(convert_iterator<segmented_iterator<First> >::call(first_))
          , last(convert_iterator<segmented_iterator<Last> >::call(last_))
          , first_cons(detail::reverse_cons<First>::call(first_.cons()))
          , last_cons(detail::reverse_cons<Last>::call(last_.cons()))
        {}

        begin_type first;
        end_type last;

        begin_cons_type first_cons;
        end_cons_type last_cons;
    };

    namespace detail
    {

        template<typename Cons1, typename Cons2>
        struct same_segment
          : mpl::false_
        {};

        template<typename Car1, typename Cdr1, typename Car2, typename Cdr2>
        struct same_segment<cons<Car1, Cdr1>, cons<Car2, Cdr2> >
          : mpl::and_<
                traits::is_segmented<Car1>
              , is_same<Car1, Car2>
            >
        {};

        ////////////////////////////////////////////////////////////////////////////
        template<typename Cons1, typename Cons2>
        struct segments_gen;

        ////////////////////////////////////////////////////////////////////////////
        template<typename Cons1, typename Cons2, bool SameSegment>
        struct segments_gen2
        {
            typedef segments_gen<typename Cons1::cdr_type, typename Cons2::cdr_type> gen;
            typedef typename gen::type type;

            static type call(Cons1 const &cons1, Cons2 const &cons2)
            {
                return gen::call(cons1.cdr, cons2.cdr);
            }
        };

        template<typename Cons1, typename Cons2>
        struct segments_gen2<Cons1, Cons2, false>
        {
            typedef segmented_view<center_view, Cons1, Cons2> view;
            typedef typename result_of::segments<view>::type type;

            static type call(Cons1 const &cons1, Cons2 const &cons2)
            {
                view v(cons1, cons2);
                return fusion::segments(v);
            }
        };

        template<typename Car1, typename Car2>
        struct segments_gen2<cons<Car1>, cons<Car2>, false>
        {
            typedef iterator_range<
                typename Car1::iterator_type
              , typename Car2::iterator_type
            > range;

            typedef single_view<range> type;

            static type call(cons<Car1> const &cons1, cons<Car2> const &cons2)
            {
                return type(range(cons1.car.where_, cons2.car.where_));
            }
        };

        ////////////////////////////////////////////////////////////////////////////
        template<typename Cons1, typename Cons2>
        struct segments_gen
          : segments_gen2<Cons1, Cons2, same_segment<Cons1, Cons2>::value>
        {};

        template<typename Car, typename Cdr>
        struct segments_gen<cons<Car, Cdr>, nil>
        {
            typedef segmented_view<right_view, cons<Car, Cdr> > view;
            typedef typename result_of::segments<view>::type type;

            static type call(cons<Car, Cdr> const &cons, nil const &)
            {
                view v(cons);
                return fusion::segments(v);
            }
        };

        template<>
        struct segments_gen<nil, nil>
        {
            typedef nil type;

            static type call(nil const &, nil const &)
            {
                return nil();
            }
        };
    } // namespace detail

    namespace extension
    {
        template<typename Tag>
        struct is_segmented_impl;

        // An iterator_range of segmented_iterators is segmented
        template<>
        struct is_segmented_impl<iterator_range_tag>
        {
            template<typename Iterator>
            struct is_segmented_iterator : mpl::false_ {};

            template<typename Cons>
            struct is_segmented_iterator<segmented_iterator<Cons> > : mpl::true_ {};

            template<typename Sequence>
            struct apply
              : mpl::and_<
                    is_segmented_iterator<typename Sequence::begin_type>
                  , is_segmented_iterator<typename Sequence::end_type>
                >
            {};
        };

        template<typename Sequence>
        struct segments_impl;

        template<>
        struct segments_impl<iterator_range_tag>
        {
            template<typename Sequence>
            struct apply
            {
                typedef typename Sequence::begin_cons_type begin_cons;
                typedef typename Sequence::end_cons_type end_cons;

                typedef detail::segments_gen<begin_cons, end_cons> gen;
                typedef typename gen::type type;

                static type call(Sequence &sequence)
                {
                    return gen::call(sequence.first_cons, sequence.last_cons);
                }
            };
        };
    }

}}

#endif