/*=============================================================================
   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_EAN_05032006_1027
#define FUSION_SEGMENTED_ITERATOR_EAN_05032006_1027

#include <boost/mpl/if.hpp>
#include <boost/mpl/int.hpp>
#include <boost/mpl/not.hpp>
#include <boost/mpl/assert.hpp>
#include <boost/mpl/next_prior.hpp>
#include <boost/mpl/placeholders.hpp>
#include <boost/type_traits/is_same.hpp>
#include <boost/type_traits/is_reference.hpp>
#include <boost/type_traits/remove_reference.hpp>
#include <boost/fusion/support/tag_of.hpp>
#include <boost/fusion/support/is_sequence.hpp>
#include <boost/fusion/view/filter_view.hpp>
#include <boost/fusion/container/list/cons.hpp> // for nil
#include <boost/fusion/container/generation/make_cons.hpp>
#include <boost/fusion/iterator/advance.hpp>
#include <boost/fusion/iterator/distance.hpp>
#include <boost/fusion/sequence/intrinsic/ext_/segments.hpp>
#include <boost/fusion/support/ext_/is_segmented.hpp>

namespace boost { namespace fusion
{
    struct fusion_sequence_tag;

    namespace detail
    {
        using mpl::_;
        using mpl::not_;

        ////////////////////////////////////////////////////////////////////////////
        template<typename Sequence>
        struct is_empty
          : result_of::equal_to<
                typename result_of::begin<Sequence>::type
              , typename result_of::end<Sequence>::type
            >
        {};

        template<typename Sequence>
        struct is_empty<Sequence &>
          : is_empty<Sequence>
        {};

        ////////////////////////////////////////////////////////////////////////////
        struct not_is_empty_pred
        {
            template<typename Sequence>
            struct apply
              : not_<is_empty<Sequence> >
            {};
        };

        struct segmented_range_tag;

        ////////////////////////////////////////////////////////////////////////////
        template<typename Sequence, typename Index, bool IsSegmented>
        struct segmented_range
          : sequence_base<segmented_range<Sequence, Index, IsSegmented> >
        {
            BOOST_MPL_ASSERT_NOT((is_reference<Sequence>));
            typedef mpl::bool_<IsSegmented> is_segmented;
            typedef segmented_range_tag fusion_tag;
            typedef fusion_sequence_tag tag; // this gets picked up by MPL
            typedef mpl::true_ is_view;

            // If this is a range of segments, skip over the empty ones
            typedef typename mpl::if_<
                is_segmented
              , filter_view<Sequence, not_is_empty_pred>
              , Sequence
            >::type sequence_non_ref_type;

            typedef typename mpl::if_<
                traits::is_view<sequence_non_ref_type>
              , sequence_non_ref_type
              , sequence_non_ref_type &
            >::type sequence_type;

            typedef
                typename fusion::result_of::advance<
                    typename fusion::result_of::begin<sequence_non_ref_type>::type
                  , Index
                >::type
            iterator_type;

            typedef typename traits::category_of<sequence_non_ref_type>::type category;

            explicit segmented_range(Sequence &sequence_)
              : sequence(sequence_type(sequence_))
            {}

            segmented_range(sequence_type sequence_, int)
              : sequence(sequence_)
            {}

            iterator_type where_() const
            {
                return fusion::advance<Index>(
                    fusion::begin(const_cast<sequence_non_ref_type &>(this->sequence))
                );
            }

            sequence_type sequence;

        private:
            segmented_range &operator =(segmented_range const &);
        };
    }

    namespace extension
    {
        template<>
        struct is_segmented_impl<detail::segmented_range_tag>
        {
            template<typename Sequence>
            struct apply
              : Sequence::is_segmented
            {};
        };

        template<>
        struct size_impl<detail::segmented_range_tag>
        {
            template<typename Sequence>
            struct apply
              : mpl::int_<
                    result_of::distance<
                        typename Sequence::iterator_type
                      , typename result_of::end<typename Sequence::sequence_non_ref_type>::type
                    >::value
                >
            {};
        };

        template<>
        struct segments_impl<detail::segmented_range_tag>
        {
            template<typename Sequence>
            struct apply
            {
                typedef Sequence &type;
                static type call(Sequence &seq)
                {
                    return seq;
                }
            };
        };

        template<>
        struct begin_impl<detail::segmented_range_tag>
        {
            template<typename Sequence>
            struct apply
            {
                typedef typename Sequence::iterator_type type;
                static type call(Sequence &seq)
                {
                    return seq.where_();
                }
            };
        };

        template<>
        struct end_impl<detail::segmented_range_tag>
        {
            template<typename Sequence>
            struct apply
            {
                typedef typename Sequence::sequence_non_ref_type sequence;
                typedef typename result_of::end<sequence>::type type;

                static type call(Sequence &seq)
                {
                    return fusion::end(seq.sequence);
                }
            };
        };
    }

    namespace detail
    {
        ///////////////////////////////////////////////////////////////////////
        template<typename Range>
        struct range_next;

        template<typename Sequence, typename Index, bool IsSegmented>
        struct range_next<segmented_range<Sequence, Index, IsSegmented> >
        {
            typedef typename mpl::next<Index>::type index_type;
            typedef segmented_range<Sequence, index_type, IsSegmented> type;

            static type call(segmented_range<Sequence, Index, IsSegmented> const &rng)
            {
                return type(rng.sequence, 0);
            }
        };

        ///////////////////////////////////////////////////////////////////////
        template<typename Cons>
        struct is_range_next_empty
          : is_empty<typename range_next<typename Cons::car_type>::type>
        {};

        template<>
        struct is_range_next_empty<nil>
          : mpl::true_
        {};

        ///////////////////////////////////////////////////////////////////////
        template<typename Sequence, bool IsSegmented = traits::is_segmented<Sequence>::value>
        struct as_segmented_range
        {
            typedef typename result_of::segments<Sequence>::type segments;
            typedef typename remove_reference<segments>::type sequence;
            typedef segmented_range<sequence, mpl::int_<0>, true> type;

            static type call(Sequence &seq)
            {
                segments segs(fusion::segments(seq));
                return type(segs);
            }
        };

        template<typename Sequence>
        struct as_segmented_range<Sequence, false>
        {
            typedef typename remove_reference<Sequence>::type sequence;
            typedef segmented_range<sequence, mpl::int_<0>, false> type;

            static type call(Sequence &seq)
            {
                return type(seq);
            }
        };

        template<typename Sequence, typename Index, bool IsSegmented>
        struct as_segmented_range<segmented_range<Sequence, Index, IsSegmented>, IsSegmented>
        {
            typedef segmented_range<Sequence, Index, IsSegmented> type;
            static type &call(type &seq)
            {
                return seq;
            }
        };

        ///////////////////////////////////////////////////////////////////////
        template<
            typename Sequence
          , typename State = nil
          , bool IsSegmented = traits::is_segmented<Sequence>::value
        >
        struct push_segments
        {
            typedef typename as_segmented_range<Sequence>::type range;
            typedef typename result_of::begin<range>::type begin;
            typedef typename result_of::deref<begin>::type next_ref;
            typedef typename remove_reference<next_ref>::type next;
            typedef push_segments<next, cons<range, State> > push;
            typedef typename push::type type;

            static type call(Sequence &seq, State const &state)
            {
                range rng(as_segmented_range<Sequence>::call(seq));
                next_ref nxt(*fusion::begin(rng));
                return push::call(nxt, fusion::make_cons(rng, state));
            }
        };

        template<typename Sequence, typename State>
        struct push_segments<Sequence, State, false>
        {
            typedef typename as_segmented_range<Sequence>::type range;
            typedef cons<range, State> type;

            static type call(Sequence &seq, State const &state)
            {
                range rng(as_segmented_range<Sequence>::call(seq));
                return fusion::make_cons(rng, state);
            }
        };

        ///////////////////////////////////////////////////////////////////////
        template<typename State, bool IsEmpty = is_range_next_empty<State>::value>
        struct pop_segments
        {
            typedef range_next<typename State::car_type> next;
            typedef push_segments<typename next::type, typename State::cdr_type> push;
            typedef typename push::type type;

            static type call(State const &state)
            {
                typename next::type rng(next::call(state.car));
                return push::call(rng, state.cdr);
            }
        };

        template<typename State>
        struct pop_segments<State, true>
        {
            typedef pop_segments<typename State::cdr_type> pop;
            typedef typename pop::type type;

            static type call(State const &state)
            {
                return pop::call(state.cdr);
            }
        };

        template<>
        struct pop_segments<nil, true>
        {
            typedef nil type;

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

    struct segmented_iterator_tag;

    ////////////////////////////////////////////////////////////////////////////
    template<typename Cons>
    struct segmented_iterator
      : fusion::iterator_base<segmented_iterator<Cons> >
    {
        typedef segmented_iterator_tag fusion_tag;
        typedef fusion::forward_traversal_tag category;

        typedef Cons cons_type;
        typedef typename Cons::car_type car_type;
        typedef typename Cons::cdr_type cdr_type;

        explicit segmented_iterator(Cons const &c)
          : cons_(c)
        {}

        cons_type const &cons() const { return this->cons_; };
        car_type const &car() const { return this->cons_.car; };
        cdr_type const &cdr() const { return this->cons_.cdr; };

    private:
        Cons cons_;
    };

    ///////////////////////////////////////////////////////////////////////////
    template<typename Sequence>
    struct segmented_begin
    {
        typedef typename detail::push_segments<Sequence> push;
        typedef segmented_iterator<typename push::type> type;

        static type call(Sequence &seq)
        {
            return type(push::call(seq, nil()));
        }
    };

    ///////////////////////////////////////////////////////////////////////////
    template<typename Sequence>
    struct segmented_end
    {
        typedef segmented_iterator<nil> type;

        static type call(Sequence &)
        {
            return type(nil());
        }
    };

    namespace extension
    {
        template<>
        struct value_of_impl<segmented_iterator_tag>
        {
            template<typename Iterator>
            struct apply
            {
                typedef typename result_of::begin<typename Iterator::car_type>::type begin;
                typedef typename result_of::value_of<begin>::type type;
            };
        };

        template<>
        struct deref_impl<segmented_iterator_tag>
        {
            template<typename Iterator>
            struct apply
            {
                typedef typename result_of::begin<typename Iterator::car_type>::type begin;
                typedef typename result_of::deref<begin>::type type;

                static type call(Iterator const &it)
                {
                    return *fusion::begin(it.car());
                }
            };
        };

        // discards the old head, expands the right child of the new head
        // and pushes the result to the head of the list.

        template<>
        struct next_impl<segmented_iterator_tag>
        {
            template<
                typename Iterator
              , bool IsSegmentDone = detail::is_range_next_empty<Iterator>::value
            >
            struct apply
            {
                typedef typename Iterator::cdr_type cdr_type;
                typedef detail::range_next<typename Iterator::car_type> next;
                typedef segmented_iterator<cons<typename next::type, cdr_type> > type;

                static type call(Iterator const &it)
                {
                    return type(fusion::make_cons(next::call(it.car()), it.cdr()));
                }
            };

            template<typename Iterator>
            struct apply<Iterator, true> // segment done, move to next segment
            {
                typedef typename Iterator::cdr_type cdr_type;
                typedef typename detail::pop_segments<cdr_type> pop;
                typedef segmented_iterator<typename pop::type> type;

                static type call(Iterator const &it)
                {
                    return type(pop::call(it.cdr()));
                }
            };
        };
    }
}} // namespace boost::fusion

#endif