| /*============================================================================= | |
| Copyright (c) 2001-2006 Joel de Guzman | |
| Copyright (c) 2007 Dan Marsden | |
| Copyright (c) 2009 Christopher Schmidt | |
| 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/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, Iterator>::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 | |
| , Shifted | |
| >::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()); | |
| } | |
| }; | |
| }}} | |
| #endif |