/*=============================================================================

    Copyright (c) 2001-2006 Joel de Guzman

    Copyright (c) 2007 Dan Marsden



    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(FUSION_FIND_IF_05052005_1107)

#define FUSION_FIND_IF_05052005_1107



#include <boost/mpl/eval_if.hpp>

#include <boost/mpl/or.hpp>

#include <boost/mpl/lambda.hpp>

#include <boost/mpl/apply.hpp>

#include <boost/mpl/identity.hpp>

#include <boost/fusion/iterator/value_of.hpp>

#include <boost/fusion/iterator/equal_to.hpp>

#include <boost/fusion/iterator/next.hpp>

#include <boost/fusion/sequence/intrinsic/begin.hpp>

#include <boost/fusion/iterator/advance.hpp>

#include <boost/fusion/iterator/distance.hpp>

#include <boost/fusion/support/category_of.hpp>

#include <boost/mpl/eval_if.hpp>

#include <boost/mpl/identity.hpp>



namespace boost { namespace fusion { 

    struct random_access_traversal_tag;

namespace detail

{

    template <typename Iterator, typename Pred>

    struct apply_filter

    {

        typedef typename mpl::apply1<

            Pred, typename result_of::value_of<Iterator>::type>::type type;

        BOOST_STATIC_CONSTANT(int, value = type::value);

    };



    template <typename First, typename Last, typename Pred>

    struct main_find_if;



    template <typename First, typename Last, typename Pred>

    struct recursive_find_if

    {

        typedef typename

            main_find_if<

                typename result_of::next<First>::type, Last, Pred

            >::type

        type;

    };



    template <typename First, typename Last, typename Pred>

    struct main_find_if

    {

        typedef mpl::or_<

            result_of::equal_to<First, Last>

          , apply_filter<First, Pred> >

        filter;



        typedef typename

            mpl::eval_if<

                filter

              , mpl::identity<First>

              , recursive_find_if<First, Last, Pred>

            >::type

        type;

    };



    template<

        typename First, typename Last, 

        typename Pred, bool>

    struct choose_find_if;



    template<typename First, typename Last, typename Pred>

    struct choose_find_if<First, Last, Pred, false>

        : main_find_if<First, Last, Pred>

    {};



    template<typename Iter, typename Pred, int n, int unrolling>

    struct unroll_again;



    template <typename Iter, typename Pred, int offset>

    struct apply_offset_filter

    {

        typedef typename result_of::advance_c<Iter, offset>::type Shifted;

        typedef typename

            mpl::apply1<

                Pred

              , typename result_of::value_of<Shifted>::type

            >::type

        type;

        BOOST_STATIC_CONSTANT(int, value = type::value);

    };



    template<typename Iter, typename Pred, int n>

    struct unrolled_find_if

    {

        typedef typename mpl::eval_if<

            apply_filter<Iter, Pred>,

            mpl::identity<Iter>,

            mpl::eval_if<

              apply_offset_filter<Iter, Pred, 1>,

              result_of::advance_c<Iter, 1>,

              mpl::eval_if<

                apply_offset_filter<Iter, Pred, 2>,

                result_of::advance_c<Iter, 2>,

                mpl::eval_if<

                  apply_offset_filter<Iter, Pred, 3>,

                  result_of::advance_c<Iter, 3>,

                  unroll_again<

                    Iter,

                    Pred,

                    n,

                    4> > > > >::type type;

    };



    template<typename Iter, typename Pred>

    struct unrolled_find_if<Iter, Pred, 3>

    {

        typedef typename mpl::eval_if<

            apply_filter<Iter, Pred>,

            mpl::identity<Iter>,

            mpl::eval_if<

              apply_offset_filter<Iter, Pred, 1>,

              result_of::advance_c<Iter, 1>,

              mpl::eval_if<

                apply_offset_filter<Iter, Pred, 2>,

                result_of::advance_c<Iter, 2>,

                result_of::advance_c<Iter, 3> > > >::type type;

    };



    template<typename Iter, typename Pred>

    struct unrolled_find_if<Iter, Pred, 2>

    {

        typedef typename mpl::eval_if<

            apply_filter<Iter, Pred>,

            mpl::identity<Iter>,

            mpl::eval_if<

              apply_offset_filter<Iter, Pred, 1>,

              result_of::advance_c<Iter, 1>,

              result_of::advance_c<Iter, 2> > >::type type;

    };



    template<typename Iter, typename Pred>

    struct unrolled_find_if<Iter, Pred, 1>

    {

        typedef typename mpl::eval_if<

            apply_filter<Iter, Pred>,

            mpl::identity<Iter>,

            result_of::advance_c<Iter, 1> >::type type;

    };



    template<typename Iter, typename Pred, int n, int unrolling>

    struct unroll_again

    {

        typedef typename unrolled_find_if<

            typename result_of::advance_c<Iter, unrolling>::type,

            Pred,

            n-unrolling>::type type;

    };



    template<typename Iter, typename Pred>

    struct unrolled_find_if<Iter, Pred, 0>

    {

        typedef Iter type;

    };



    template<typename First, typename Last, typename Pred>

    struct choose_find_if<First, Last, Pred, true>

    {

        typedef typename result_of::distance<First, Last>::type N;

        typedef typename unrolled_find_if<First, Pred, N::value>::type type;

    };



    template <typename First, typename Last, typename Pred>

    struct static_find_if

    {

        typedef typename

            choose_find_if<

                First

              , Last

              , typename mpl::lambda<Pred>::type

              , is_base_of<random_access_traversal_tag, typename traits::category_of<First>::type>::value

            >::type

        type;



        template <typename Iterator>

        static type

        recursive_call(Iterator const& iter, mpl::true_)

        {

            return iter;

        }



        template <typename Iterator>

        static type

        recursive_call(Iterator const& iter, mpl::false_)

        {

            return recursive_call(fusion::next(iter));

        }



        template <typename Iterator>

        static type

        recursive_call(Iterator const& iter)

        {

            typedef result_of::equal_to<Iterator, type> found;

            return recursive_call(iter, found());

        }



        template <typename Iterator, typename Tag>

        static type

        choose_call(Iterator const& iter, Tag)

        {

            return recursive_call(iter);

        }



        template <typename Iterator>

        static type

        choose_call(Iterator const& iter, random_access_traversal_tag)

        {

            typedef typename result_of::distance<Iterator, type>::type N;

            return fusion::advance<N>(iter);

        }



        template <typename Iterator>

        static type

        call(Iterator const& iter)

        {

            return choose_call(iter, typename traits::category_of<Iterator>::type());

        }

    };



    template <typename First, typename Last, typename Pred>

    struct static_seq_find_if : static_find_if<First, Last, Pred>

    {

        typedef typename static_find_if<First, Last, Pred>::type type;



        template <typename Sequence>

        static type

        call(Sequence const& seq)

        {

            return static_find_if<First, Last, Pred>::call(fusion::begin(seq));

        }



        template <typename Sequence>

        static type

        call(Sequence& seq)

        {

            return static_find_if<First, Last, Pred>::call(fusion::begin(seq));

        }

    };

}}}



#endif

