1 /*=============================================================================
2     Copyright (c) 2001-2011 Joel de Guzman
3     Copyright (c) 2007 Dan Marsden
4     Copyright (c) 2009 Christopher Schmidt
5 
6     Distributed under the Boost Software License, Version 1.0. (See accompanying
7     file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
8 ==============================================================================*/
9 #if !defined(FUSION_FIND_IF_05052005_1107)
10 #define FUSION_FIND_IF_05052005_1107
11 
12 #include <boost/fusion/support/config.hpp>
13 #include <boost/mpl/apply.hpp>
14 #include <boost/mpl/eval_if.hpp>
15 #include <boost/mpl/identity.hpp>
16 #include <boost/mpl/lambda.hpp>
17 #include <boost/mpl/or.hpp>
18 #include <boost/fusion/iterator/advance.hpp>
19 #include <boost/fusion/iterator/distance.hpp>
20 #include <boost/fusion/iterator/equal_to.hpp>
21 #include <boost/fusion/iterator/next.hpp>
22 #include <boost/fusion/sequence/intrinsic/begin.hpp>
23 #include <boost/fusion/sequence/intrinsic/end.hpp>
24 #include <boost/fusion/support/category_of.hpp>
25 
26 namespace boost { namespace fusion {
27     struct random_access_traversal_tag;
28 namespace detail
29 {
30     template <typename Iterator, typename Pred>
31     struct apply_filter
32     {
33         typedef typename mpl::apply1<
34             Pred, Iterator>::type type;
35         BOOST_STATIC_CONSTANT(int, value = type::value);
36     };
37 
38     template <typename First, typename Last, typename Pred>
39     struct main_find_if;
40 
41     template <typename First, typename Last, typename Pred>
42     struct recursive_find_if
43     {
44         typedef typename
45             main_find_if<
46                 typename result_of::next<First>::type, Last, Pred
47             >::type
48         type;
49     };
50 
51     template <typename First, typename Last, typename Pred>
52     struct main_find_if
53     {
54         typedef mpl::or_<
55             result_of::equal_to<First, Last>
56           , apply_filter<First, Pred> >
57         filter;
58 
59         typedef typename
60             mpl::eval_if<
61                 filter
62               , mpl::identity<First>
63               , recursive_find_if<First, Last, Pred>
64             >::type
65         type;
66     };
67 
68     template<
69         typename First, typename Last,
70         typename Pred, bool>
71     struct choose_find_if;
72 
73     template<typename First, typename Last, typename Pred>
74     struct choose_find_if<First, Last, Pred, false>
75         : main_find_if<First, Last, Pred>
76     {};
77 
78     template<typename Iter, typename Pred, int n, int unrolling>
79     struct unroll_again;
80 
81     template <typename Iter, typename Pred, int offset>
82     struct apply_offset_filter
83     {
84         typedef typename result_of::advance_c<Iter, offset>::type Shifted;
85         typedef typename
86             mpl::apply1<
87                 Pred
88               , Shifted
89             >::type
90         type;
91         BOOST_STATIC_CONSTANT(int, value = type::value);
92     };
93 
94     template<typename Iter, typename Pred, int n>
95     struct unrolled_find_if
96     {
97         typedef typename mpl::eval_if<
98             apply_filter<Iter, Pred>,
99             mpl::identity<Iter>,
100             mpl::eval_if<
101               apply_offset_filter<Iter, Pred, 1>,
102               result_of::advance_c<Iter, 1>,
103               mpl::eval_if<
104                 apply_offset_filter<Iter, Pred, 2>,
105                 result_of::advance_c<Iter, 2>,
106                 mpl::eval_if<
107                   apply_offset_filter<Iter, Pred, 3>,
108                   result_of::advance_c<Iter, 3>,
109                   unroll_again<
110                     Iter,
111                     Pred,
112                     n,
113                     4> > > > >::type type;
114     };
115 
116     template<typename Iter, typename Pred>
117     struct unrolled_find_if<Iter, Pred, 3>
118     {
119         typedef typename mpl::eval_if<
120             apply_filter<Iter, Pred>,
121             mpl::identity<Iter>,
122             mpl::eval_if<
123               apply_offset_filter<Iter, Pred, 1>,
124               result_of::advance_c<Iter, 1>,
125               mpl::eval_if<
126                 apply_offset_filter<Iter, Pred, 2>,
127                 result_of::advance_c<Iter, 2>,
128                 result_of::advance_c<Iter, 3> > > >::type type;
129     };
130 
131     template<typename Iter, typename Pred>
132     struct unrolled_find_if<Iter, Pred, 2>
133     {
134         typedef typename mpl::eval_if<
135             apply_filter<Iter, Pred>,
136             mpl::identity<Iter>,
137             mpl::eval_if<
138               apply_offset_filter<Iter, Pred, 1>,
139               result_of::advance_c<Iter, 1>,
140               result_of::advance_c<Iter, 2> > >::type type;
141     };
142 
143     template<typename Iter, typename Pred>
144     struct unrolled_find_if<Iter, Pred, 1>
145     {
146         typedef typename mpl::eval_if<
147             apply_filter<Iter, Pred>,
148             mpl::identity<Iter>,
149             result_of::advance_c<Iter, 1> >::type type;
150     };
151 
152     template<typename Iter, typename Pred, int n, int unrolling>
153     struct unroll_again
154     {
155         typedef typename unrolled_find_if<
156             typename result_of::advance_c<Iter, unrolling>::type,
157             Pred,
158             n-unrolling>::type type;
159     };
160 
161     template<typename Iter, typename Pred>
162     struct unrolled_find_if<Iter, Pred, 0>
163     {
164         typedef Iter type;
165     };
166 
167     template<typename First, typename Last, typename Pred>
168     struct choose_find_if<First, Last, Pred, true>
169     {
170         typedef typename result_of::distance<First, Last>::type N;
171         typedef typename unrolled_find_if<First, Pred, N::value>::type type;
172     };
173 
174     template <typename First, typename Last, typename Pred>
175     struct static_find_if
176     {
177         typedef typename
178             choose_find_if<
179                 First
180               , Last
181               , typename mpl::lambda<Pred>::type
182               , is_base_of<random_access_traversal_tag, typename traits::category_of<First>::type>::value
183             >::type
184         type;
185 
186         template <typename Iterator>
187         BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
188         static type
recursive_callboost::fusion::detail::static_find_if189         recursive_call(Iterator const& iter, mpl::true_)
190         {
191             return iter;
192         }
193 
194         template <typename Iterator>
195         BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
196         static type
recursive_callboost::fusion::detail::static_find_if197         recursive_call(Iterator const& iter, mpl::false_)
198         {
199             return recursive_call(fusion::next(iter));
200         }
201 
202         template <typename Iterator>
203         BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
204         static type
recursive_callboost::fusion::detail::static_find_if205         recursive_call(Iterator const& iter)
206         {
207             typedef result_of::equal_to<Iterator, type> found;
208             return recursive_call(iter, found());
209         }
210 
211         template <typename Iterator, typename Tag>
212         BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
213         static type
choose_callboost::fusion::detail::static_find_if214         choose_call(Iterator const& iter, Tag)
215         {
216             return recursive_call(iter);
217         }
218 
219         template <typename Iterator>
220         BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
221         static type
choose_callboost::fusion::detail::static_find_if222         choose_call(Iterator const& iter, random_access_traversal_tag)
223         {
224             typedef typename result_of::distance<Iterator, type>::type N;
225             return fusion::advance<N>(iter);
226         }
227 
228         template <typename Iterator>
229         BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
230         static type
iter_callboost::fusion::detail::static_find_if231         iter_call(Iterator const& iter)
232         {
233             return choose_call(iter, typename traits::category_of<Iterator>::type());
234         }
235 
236         template <typename Sequence>
237         BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
238         static type
callboost::fusion::detail::static_find_if239         call(Sequence& seq)
240         {
241             return iter_call(fusion::begin(seq));
242         }
243     };
244 
245     template <typename Sequence, typename Pred>
246     struct result_of_find_if
247     {
248         typedef
249             static_find_if<
250                 typename result_of::begin<Sequence>::type
251               , typename result_of::end<Sequence>::type
252               , Pred
253             >
254         filter;
255 
256         typedef typename filter::type type;
257     };
258 }}}
259 
260 #endif
261