]>
Commit | Line | Data |
---|---|---|
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 | |
189 | 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 | |
197 | 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 | |
205 | 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 | |
214 | 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 | |
222 | 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 | |
231 | 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 | |
239 | 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 |