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

source code of include/boost/fusion/algorithm/query/detail/find_if.hpp