1 #ifndef BOOST_MP11_ALGORITHM_HPP_INCLUDED
2 #define BOOST_MP11_ALGORITHM_HPP_INCLUDED
3
4 // Copyright 2015-2019 Peter Dimov
5 //
6 // Distributed under the Boost Software License, Version 1.0.
7 //
8 // See accompanying file LICENSE_1_0.txt or copy at
9 // http://www.boost.org/LICENSE_1_0.txt
10
11 #include <boost/mp11/list.hpp>
12 #include <boost/mp11/set.hpp>
13 #include <boost/mp11/integral.hpp>
14 #include <boost/mp11/utility.hpp>
15 #include <boost/mp11/function.hpp>
16 #include <boost/mp11/detail/mp_count.hpp>
17 #include <boost/mp11/detail/mp_plus.hpp>
18 #include <boost/mp11/detail/mp_map_find.hpp>
19 #include <boost/mp11/detail/mp_with_index.hpp>
20 #include <boost/mp11/detail/mp_fold.hpp>
21 #include <boost/mp11/detail/mp_min_element.hpp>
22 #include <boost/mp11/detail/mp_copy_if.hpp>
23 #include <boost/mp11/detail/mp_remove_if.hpp>
24 #include <boost/mp11/detail/config.hpp>
25 #include <boost/mp11/integer_sequence.hpp>
26 #include <type_traits>
27 #include <utility>
28
29 namespace boost
30 {
31 namespace mp11
32 {
33
34 // mp_transform<F, L...>
35 namespace detail
36 {
37
38 template<template<class...> class F, class... L> struct mp_transform_impl
39 {
40 };
41
42 template<template<class...> class F, template<class...> class L, class... T> struct mp_transform_impl<F, L<T...>>
43 {
44 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, < 1920 )
45
46 template<class... U> struct f { using type = F<U...>; };
47
48 using type = L<typename f<T>::type...>;
49
50 #else
51
52 using type = L<F<T>...>;
53
54 #endif
55 };
56
57 template<template<class...> class F, template<class...> class L1, class... T1, template<class...> class L2, class... T2> struct mp_transform_impl<F, L1<T1...>, L2<T2...>>
58 {
59 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, < 1920 )
60
61 template<class... U> struct f { using type = F<U...>; };
62
63 using type = L1<typename f<T1, T2>::type...>;
64
65 #else
66
67 using type = L1<F<T1,T2>...>;
68
69 #endif
70 };
71
72 template<template<class...> class F, template<class...> class L1, class... T1, template<class...> class L2, class... T2, template<class...> class L3, class... T3> struct mp_transform_impl<F, L1<T1...>, L2<T2...>, L3<T3...>>
73 {
74 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, < 1920 )
75
76 template<class... U> struct f { using type = F<U...>; };
77
78 using type = L1<typename f<T1, T2, T3>::type...>;
79
80 #else
81
82 using type = L1<F<T1,T2,T3>...>;
83
84 #endif
85 };
86
87 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, == 1900 ) || BOOST_MP11_WORKAROUND( BOOST_MP11_GCC, < 40800 )
88
89 template<class... L> using mp_same_size_1 = mp_same<mp_size<L>...>;
90 template<class... L> struct mp_same_size_2: mp_defer<mp_same_size_1, L...> {};
91
92 #endif
93
94 struct list_size_mismatch
95 {
96 };
97
98 #if BOOST_MP11_WORKAROUND( BOOST_MP11_CUDA, >= 9000000 && BOOST_MP11_CUDA < 10000000 )
99
100 template<template<class...> class F, class... L> struct mp_transform_cuda_workaround
101 {
102 using type = mp_if<mp_same<mp_size<L>...>, detail::mp_transform_impl<F, L...>, detail::list_size_mismatch>;
103 };
104
105 #endif
106
107 } // namespace detail
108
109 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, == 1900 ) || BOOST_MP11_WORKAROUND( BOOST_MP11_GCC, < 40800 )
110
111 template<template<class...> class F, class... L> using mp_transform = typename mp_if<typename detail::mp_same_size_2<L...>::type, detail::mp_transform_impl<F, L...>, detail::list_size_mismatch>::type;
112
113 #else
114
115 #if BOOST_MP11_WORKAROUND( BOOST_MP11_CUDA, >= 9000000 && BOOST_MP11_CUDA < 10000000 )
116
117 template<template<class...> class F, class... L> using mp_transform = typename detail::mp_transform_cuda_workaround< F, L...>::type::type;
118
119 #else
120
121 template<template<class...> class F, class... L> using mp_transform = typename mp_if<mp_same<mp_size<L>...>, detail::mp_transform_impl<F, L...>, detail::list_size_mismatch>::type;
122
123 #endif
124
125 #endif
126
127 template<class Q, class... L> using mp_transform_q = mp_transform<Q::template fn, L...>;
128
129 namespace detail
130 {
131
132 template<template<class...> class F, template<class...> class L1, class... T1, template<class...> class L2, class... T2, template<class...> class L3, class... T3, template<class...> class L4, class... T4, class... L> struct mp_transform_impl<F, L1<T1...>, L2<T2...>, L3<T3...>, L4<T4...>, L...>
133 {
134 using A1 = L1<mp_list<T1, T2, T3, T4>...>;
135
136 template<class V, class T> using _f = mp_transform<mp_push_back, V, T>;
137
138 using A2 = mp_fold<mp_list<L...>, A1, _f>;
139
140 template<class T> using _g = mp_apply<F, T>;
141
142 using type = mp_transform<_g, A2>;
143 };
144
145 } // namespace detail
146
147 // mp_transform_if<P, F, L...>
148 namespace detail
149 {
150
151 template<template<class...> class P, template<class...> class F, class... L> struct mp_transform_if_impl
152 {
153 // the stupid quote-unquote dance avoids "pack expansion used as argument for non-pack parameter of alias template"
154
155 using Qp = mp_quote<P>;
156 using Qf = mp_quote<F>;
157
158 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, < 1920 )
159
160 template<class... U> struct _f_ { using type = mp_eval_if_q<mp_not<mp_invoke_q<Qp, U...>>, mp_first<mp_list<U...>>, Qf, U...>; };
161 template<class... U> using _f = typename _f_<U...>::type;
162
163 #else
164
165 template<class... U> using _f = mp_eval_if_q<mp_not<mp_invoke_q<Qp, U...>>, mp_first<mp_list<U...>>, Qf, U...>;
166
167 #endif
168
169 using type = mp_transform<_f, L...>;
170 };
171
172 } // namespace detail
173
174 template<template<class...> class P, template<class...> class F, class... L> using mp_transform_if = typename detail::mp_transform_if_impl<P, F, L...>::type;
175 template<class Qp, class Qf, class... L> using mp_transform_if_q = typename detail::mp_transform_if_impl<Qp::template fn, Qf::template fn, L...>::type;
176
177 // mp_filter<P, L...>
178 namespace detail
179 {
180
181 template<template<class...> class P, class L1, class... L> struct mp_filter_impl
182 {
183 using Qp = mp_quote<P>;
184
185 template<class T1, class... T> using _f = mp_if< mp_invoke_q<Qp, T1, T...>, mp_list<T1>, mp_list<> >;
186
187 using _t1 = mp_transform<_f, L1, L...>;
188 using _t2 = mp_apply<mp_append, _t1>;
189
190 using type = mp_assign<L1, _t2>;
191 };
192
193 } // namespace detail
194
195 template<template<class...> class P, class... L> using mp_filter = typename detail::mp_filter_impl<P, L...>::type;
196 template<class Q, class... L> using mp_filter_q = typename detail::mp_filter_impl<Q::template fn, L...>::type;
197
198 // mp_fill<L, V>
199 namespace detail
200 {
201
202 template<class L, class V> struct mp_fill_impl;
203
204 template<template<class...> class L, class... T, class V> struct mp_fill_impl<L<T...>, V>
205 {
206 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, <= 1900 )
207
208 template<class...> struct _f { using type = V; };
209 using type = L<typename _f<T>::type...>;
210
211 #else
212
213 template<class...> using _f = V;
214 using type = L<_f<T>...>;
215
216 #endif
217 };
218
219 } // namespace detail
220
221 template<class L, class V> using mp_fill = typename detail::mp_fill_impl<L, V>::type;
222
223 // mp_contains<L, V>
224 template<class L, class V> using mp_contains = mp_to_bool<mp_count<L, V>>;
225
226 // mp_repeat(_c)<L, N>
227 namespace detail
228 {
229
230 template<class L, std::size_t N> struct mp_repeat_c_impl
231 {
232 using _l1 = typename mp_repeat_c_impl<L, N/2>::type;
233 using _l2 = typename mp_repeat_c_impl<L, N%2>::type;
234
235 using type = mp_append<_l1, _l1, _l2>;
236 };
237
238 template<class L> struct mp_repeat_c_impl<L, 0>
239 {
240 using type = mp_clear<L>;
241 };
242
243 template<class L> struct mp_repeat_c_impl<L, 1>
244 {
245 using type = L;
246 };
247
248 } // namespace detail
249
250 template<class L, std::size_t N> using mp_repeat_c = typename detail::mp_repeat_c_impl<L, N>::type;
251 template<class L, class N> using mp_repeat = typename detail::mp_repeat_c_impl<L, std::size_t{ N::value }>::type;
252
253 // mp_product<F, L...>
254 namespace detail
255 {
256
257 template<template<class...> class F, class P, class... L> struct mp_product_impl_2
258 {
259 };
260
261 template<template<class...> class F, class P> struct mp_product_impl_2<F, P>
262 {
263 using type = mp_list<mp_rename<P, F>>;
264 };
265
266 template<template<class...> class F, class P, template<class...> class L1, class... T1, class... L> struct mp_product_impl_2<F, P, L1<T1...>, L...>
267 {
268 using type = mp_append<typename mp_product_impl_2<F, mp_push_back<P, T1>, L...>::type...>;
269 };
270
271 template<template<class...> class F, class... L> struct mp_product_impl
272 {
273 };
274
275 template<template<class...> class F> struct mp_product_impl<F>
276 {
277 using type = mp_list< F<> >;
278 };
279
280 template<template<class...> class F, class L1, class... L> struct mp_product_impl<F, L1, L...>
281 {
282 using type = mp_assign<L1, typename mp_product_impl_2<F, mp_list<>, L1, L...>::type>;
283 };
284
285 } // namespace detail
286
287 template<template<class...> class F, class... L> using mp_product = typename detail::mp_product_impl<F, L...>::type;
288 template<class Q, class... L> using mp_product_q = typename detail::mp_product_impl<Q::template fn, L...>::type;
289
290 // mp_drop(_c)<L, N>
291 namespace detail
292 {
293
294 template<class L, class L2> struct mp_drop_impl;
295
296 template<template<class...> class L, class... T, template<class...> class L2, class... U> struct mp_drop_impl<L<T...>, L2<U...>>
297 {
298 template<class... W> static mp_identity<L<W...>> f( U*..., mp_identity<W>*... );
299
300 using R = decltype( f( (mp_identity<T>*)0 ... ) );
301
302 using type = typename R::type;
303 };
304
305 } // namespace detail
306
307 template<class L, std::size_t N> using mp_drop_c = typename detail::mp_drop_impl<L, mp_repeat_c<mp_list<void>, N>>::type;
308
309 template<class L, class N> using mp_drop = typename detail::mp_drop_impl<L, mp_repeat<mp_list<void>, N>>::type;
310
311 // mp_from_sequence<S>
312 namespace detail
313 {
314
315 template<class S> struct mp_from_sequence_impl;
316
317 template<template<class T, T... I> class S, class U, U... J> struct mp_from_sequence_impl<S<U, J...>>
318 {
319 using type = mp_list<std::integral_constant<U, J>...>;
320 };
321
322 } // namespace detail
323
324 template<class S> using mp_from_sequence = typename detail::mp_from_sequence_impl<S>::type;
325
326 // mp_iota(_c)<N>
327 template<std::size_t N> using mp_iota_c = mp_from_sequence<make_index_sequence<N>>;
328 template<class N> using mp_iota = mp_from_sequence<make_integer_sequence<typename std::remove_const<decltype(N::value)>::type, N::value>>;
329
330 // mp_at(_c)<L, I>
331 namespace detail
332 {
333
334 template<class L, std::size_t I> struct mp_at_c_impl;
335
336 #if defined(BOOST_MP11_HAS_TYPE_PACK_ELEMENT)
337
338 template<template<class...> class L, class... T, std::size_t I> struct mp_at_c_impl<L<T...>, I>
339 {
340 using type = __type_pack_element<I, T...>;
341 };
342
343 #else
344
345 template<class L, std::size_t I> struct mp_at_c_impl
346 {
347 using _map = mp_transform<mp_list, mp_iota<mp_size<L> >, L>;
348 using type = mp_second<mp_map_find<_map, mp_size_t<I> > >;
349 };
350
351 #endif
352
353 #if BOOST_MP11_WORKAROUND( BOOST_MP11_CUDA, >= 9000000 && BOOST_MP11_CUDA < 10000000 )
354
355 template<class L, std::size_t I> struct mp_at_c_cuda_workaround
356 {
357 using type = mp_if_c<(I < mp_size<L>::value), detail::mp_at_c_impl<L, I>, void>;
358 };
359
360 #endif
361
362 } // namespace detail
363
364 #if BOOST_MP11_WORKAROUND( BOOST_MP11_CUDA, >= 9000000 && BOOST_MP11_CUDA < 10000000 )
365
366 template<class L, std::size_t I> using mp_at_c = typename detail::mp_at_c_cuda_workaround< L, I >::type::type;
367
368 #else
369
370 template<class L, std::size_t I> using mp_at_c = typename mp_if_c<(I < mp_size<L>::value), detail::mp_at_c_impl<L, I>, void>::type;
371
372 #endif
373
374 template<class L, class I> using mp_at = mp_at_c<L, std::size_t{ I::value }>;
375
376 // mp_take(_c)<L, N>
377 namespace detail
378 {
379
380 template<std::size_t N, class L, class E = void> struct mp_take_c_impl
381 {
382 };
383
384 template<template<class...> class L, class... T>
385 struct mp_take_c_impl<0, L<T...>>
386 {
387 using type = L<>;
388 };
389
390 template<template<class...> class L, class T1, class... T>
391 struct mp_take_c_impl<1, L<T1, T...>>
392 {
393 using type = L<T1>;
394 };
395
396 template<template<class...> class L, class T1, class T2, class... T>
397 struct mp_take_c_impl<2, L<T1, T2, T...>>
398 {
399 using type = L<T1, T2>;
400 };
401
402 template<template<class...> class L, class T1, class T2, class T3, class... T>
403 struct mp_take_c_impl<3, L<T1, T2, T3, T...>>
404 {
405 using type = L<T1, T2, T3>;
406 };
407
408 template<template<class...> class L, class T1, class T2, class T3, class T4, class... T>
409 struct mp_take_c_impl<4, L<T1, T2, T3, T4, T...>>
410 {
411 using type = L<T1, T2, T3, T4>;
412 };
413
414 template<template<class...> class L, class T1, class T2, class T3, class T4, class T5, class... T>
415 struct mp_take_c_impl<5, L<T1, T2, T3, T4, T5, T...>>
416 {
417 using type = L<T1, T2, T3, T4, T5>;
418 };
419
420 template<template<class...> class L, class T1, class T2, class T3, class T4, class T5, class T6, class... T>
421 struct mp_take_c_impl<6, L<T1, T2, T3, T4, T5, T6, T...>>
422 {
423 using type = L<T1, T2, T3, T4, T5, T6>;
424 };
425
426 template<template<class...> class L, class T1, class T2, class T3, class T4, class T5, class T6, class T7, class... T>
427 struct mp_take_c_impl<7, L<T1, T2, T3, T4, T5, T6, T7, T...>>
428 {
429 using type = L<T1, T2, T3, T4, T5, T6, T7>;
430 };
431
432 template<template<class...> class L, class T1, class T2, class T3, class T4, class T5, class T6, class T7, class T8, class... T>
433 struct mp_take_c_impl<8, L<T1, T2, T3, T4, T5, T6, T7, T8, T...>>
434 {
435 using type = L<T1, T2, T3, T4, T5, T6, T7, T8>;
436 };
437
438 template<template<class...> class L, class T1, class T2, class T3, class T4, class T5, class T6, class T7, class T8, class T9, class... T>
439 struct mp_take_c_impl<9, L<T1, T2, T3, T4, T5, T6, T7, T8, T9, T...>>
440 {
441 using type = L<T1, T2, T3, T4, T5, T6, T7, T8, T9>;
442 };
443
444 template<template<class...> class L, class T1, class T2, class T3, class T4, class T5, class T6, class T7, class T8, class T9, class T10, class... T, std::size_t N>
445 struct mp_take_c_impl<N, L<T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T...>, typename std::enable_if<N >= 10>::type>
446 {
447 using type = mp_append<L<T1, T2, T3, T4, T5, T6, T7, T8, T9, T10>, typename mp_take_c_impl<N-10, L<T...>>::type>;
448 };
449
450 } // namespace detail
451
452 template<class L, std::size_t N> using mp_take_c = typename detail::mp_take_c_impl<N, L>::type;
453 template<class L, class N> using mp_take = typename detail::mp_take_c_impl<std::size_t{ N::value }, L>::type;
454
455 // mp_back<L>
456 template<class L> using mp_back = mp_at_c<L, mp_size<L>::value - 1>;
457
458 // mp_pop_back<L>
459 template<class L> using mp_pop_back = mp_take_c<L, mp_size<L>::value - 1>;
460
461 // mp_replace<L, V, W>
462 namespace detail
463 {
464
465 template<class L, class V, class W> struct mp_replace_impl;
466
467 template<template<class...> class L, class... T, class V, class W> struct mp_replace_impl<L<T...>, V, W>
468 {
469 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, <= 1800 )
470 template<class A> struct _f { using type = mp_if<std::is_same<A, V>, W, A>; };
471 using type = L<typename _f<T>::type...>;
472 #else
473 template<class A> using _f = mp_if<std::is_same<A, V>, W, A>;
474 using type = L<_f<T>...>;
475 #endif
476 };
477
478 } // namespace detail
479
480 template<class L, class V, class W> using mp_replace = typename detail::mp_replace_impl<L, V, W>::type;
481
482 // mp_replace_if<L, P, W>
483 namespace detail
484 {
485
486 template<class L, template<class...> class P, class W> struct mp_replace_if_impl;
487
488 template<template<class...> class L, class... T, template<class...> class P, class W> struct mp_replace_if_impl<L<T...>, P, W>
489 {
490 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, < 1920 )
491 template<class U> struct _f { using type = mp_if<P<U>, W, U>; };
492 using type = L<typename _f<T>::type...>;
493 #else
494 template<class U> using _f = mp_if<P<U>, W, U>;
495 using type = L<_f<T>...>;
496 #endif
497 };
498
499 } // namespace detail
500
501 template<class L, template<class...> class P, class W> using mp_replace_if = typename detail::mp_replace_if_impl<L, P, W>::type;
502 template<class L, class Q, class W> using mp_replace_if_q = mp_replace_if<L, Q::template fn, W>;
503
504 // mp_copy_if<L, P>
505 // in detail/mp_copy_if.hpp
506
507 // mp_remove<L, V>
508 namespace detail
509 {
510
511 template<class L, class V> struct mp_remove_impl;
512
513 template<template<class...> class L, class... T, class V> struct mp_remove_impl<L<T...>, V>
514 {
515 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, < 1920 )
516 template<class U> struct _f { using type = mp_if<std::is_same<U, V>, mp_list<>, mp_list<U>>; };
517 using type = mp_append<L<>, typename _f<T>::type...>;
518 #else
519 template<class U> using _f = mp_if<std::is_same<U, V>, mp_list<>, mp_list<U>>;
520 using type = mp_append<L<>, _f<T>...>;
521 #endif
522 };
523
524 } // namespace detail
525
526 template<class L, class V> using mp_remove = typename detail::mp_remove_impl<L, V>::type;
527
528 // mp_remove_if<L, P>
529 // in detail/mp_remove_if.hpp
530
531 // mp_flatten<L, L2 = mp_clear<L>>
532 namespace detail
533 {
534
535 template<class L2> struct mp_flatten_impl
536 {
537 template<class T> using fn = mp_if<mp_similar<L2, T>, T, mp_list<T>>;
538 };
539
540 } // namespace detail
541
542 template<class L, class L2 = mp_clear<L>> using mp_flatten = mp_apply<mp_append, mp_push_front<mp_transform_q<detail::mp_flatten_impl<L2>, L>, mp_clear<L>>>;
543
544 // mp_partition<L, P>
545 namespace detail
546 {
547
548 template<class L, template<class...> class P> struct mp_partition_impl;
549
550 template<template<class...> class L, class... T, template<class...> class P> struct mp_partition_impl<L<T...>, P>
551 {
552 using type = L<mp_copy_if<L<T...>, P>, mp_remove_if<L<T...>, P>>;
553 };
554
555 } // namespace detail
556
557 template<class L, template<class...> class P> using mp_partition = typename detail::mp_partition_impl<L, P>::type;
558 template<class L, class Q> using mp_partition_q = mp_partition<L, Q::template fn>;
559
560 // mp_sort<L, P>
561 namespace detail
562 {
563
564 template<class L, template<class...> class P> struct mp_sort_impl;
565
566 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, <= 1800 )
567
568 template<template<class...> class L, class... T, template<class...> class P> struct mp_sort_impl<L<T...>, P>
569 {
570 static_assert( sizeof...(T) == 0, "T... must be empty" );
571 using type = L<>;
572 };
573
574 #else
575
576 template<template<class...> class L, template<class...> class P> struct mp_sort_impl<L<>, P>
577 {
578 using type = L<>;
579 };
580
581 #endif
582
583 template<template<class...> class L, class T1, template<class...> class P> struct mp_sort_impl<L<T1>, P>
584 {
585 using type = L<T1>;
586 };
587
588 template<template<class...> class L, class T1, class... T, template<class...> class P> struct mp_sort_impl<L<T1, T...>, P>
589 {
590 template<class U> using F = P<U, T1>;
591
592 using part = mp_partition<L<T...>, F>;
593
594 using S1 = typename mp_sort_impl<mp_first<part>, P>::type;
595 using S2 = typename mp_sort_impl<mp_second<part>, P>::type;
596
597 using type = mp_append<mp_push_back<S1, T1>, S2>;
598 };
599
600 } // namespace detail
601
602 template<class L, template<class...> class P> using mp_sort = typename detail::mp_sort_impl<L, P>::type;
603 template<class L, class Q> using mp_sort_q = mp_sort<L, Q::template fn>;
604
605 // mp_nth_element(_c)<L, I, P>
606 namespace detail
607 {
608
609 template<class L, std::size_t I, template<class...> class P> struct mp_nth_element_impl;
610
611 template<template<class...> class L, class T1, std::size_t I, template<class...> class P> struct mp_nth_element_impl<L<T1>, I, P>
612 {
613 static_assert( I == 0, "mp_nth_element index out of range" );
614 using type = T1;
615 };
616
617 template<template<class...> class L, class T1, class... T, std::size_t I, template<class...> class P> struct mp_nth_element_impl<L<T1, T...>, I, P>
618 {
619 static_assert( I < 1 + sizeof...(T), "mp_nth_element index out of range" );
620
621 template<class U> using F = P<U, T1>;
622
623 using part = mp_partition<L<T...>, F>;
624
625 using L1 = mp_first<part>;
626 static std::size_t const N1 = mp_size<L1>::value;
627
628 using L2 = mp_second<part>;
629
630 #if BOOST_MP11_WORKAROUND( BOOST_MP11_CUDA, >= 9000000 && BOOST_MP11_CUDA < 10000000 )
631
632 struct detail
633 {
634 struct mp_nth_element_impl_cuda_workaround
635 {
636 using type = mp_cond<
637
638 mp_bool<(I < N1)>, mp_nth_element_impl<L1, I, P>,
639 mp_bool<(I == N1)>, mp_identity<T1>,
640 mp_true, mp_nth_element_impl<L2, I - N1 - 1, P>
641
642 >;
643 };
644 };
645
646 using type = typename detail::mp_nth_element_impl_cuda_workaround::type::type;
647
648 #else
649
650 using type = typename mp_cond<
651
652 mp_bool<(I < N1)>, mp_nth_element_impl<L1, I, P>,
653 mp_bool<(I == N1)>, mp_identity<T1>,
654 mp_true, mp_nth_element_impl<L2, I - N1 - 1, P>
655
656 >::type;
657
658 #endif
659 };
660
661 } // namespace detail
662
663 template<class L, std::size_t I, template<class...> class P> using mp_nth_element_c = typename detail::mp_nth_element_impl<L, I, P>::type;
664 template<class L, class I, template<class...> class P> using mp_nth_element = typename detail::mp_nth_element_impl<L, std::size_t{ I::value }, P>::type;
665 template<class L, class I, class Q> using mp_nth_element_q = mp_nth_element<L, I, Q::template fn>;
666
667 // mp_find<L, V>
668 namespace detail
669 {
670
671 template<class L, class V> struct mp_find_impl;
672
673 #if BOOST_MP11_CLANG && defined( BOOST_MP11_HAS_FOLD_EXPRESSIONS )
674
675 struct mp_index_holder
676 {
677 std::size_t i_;
678 bool f_;
679 };
680
operator +(mp_index_holder const & v,bool f)681 constexpr inline mp_index_holder operator+( mp_index_holder const & v, bool f )
682 {
683 if( v.f_ )
684 {
685 return v;
686 }
687 else if( f )
688 {
689 return { v.i_, true };
690 }
691 else
692 {
693 return { v.i_ + 1, false };
694 }
695 }
696
697 template<template<class...> class L, class... T, class V> struct mp_find_impl<L<T...>, V>
698 {
699 static constexpr mp_index_holder _v{ 0, false };
700 using type = mp_size_t< (_v + ... + std::is_same<T, V>::value).i_ >;
701 };
702
703 #elif !defined( BOOST_MP11_NO_CONSTEXPR )
704
705 template<template<class...> class L, class V> struct mp_find_impl<L<>, V>
706 {
707 using type = mp_size_t<0>;
708 };
709
710 #if defined( BOOST_MP11_HAS_CXX14_CONSTEXPR )
711
cx_find_index(bool const * first,bool const * last)712 constexpr std::size_t cx_find_index( bool const * first, bool const * last )
713 {
714 std::size_t m = 0;
715
716 while( first != last && !*first )
717 {
718 ++m;
719 ++first;
720 }
721
722 return m;
723 }
724
725 #else
726
cx_find_index(bool const * first,bool const * last)727 constexpr std::size_t cx_find_index( bool const * first, bool const * last )
728 {
729 return first == last || *first? 0: 1 + cx_find_index( first + 1, last );
730 }
731
732 #endif
733
734 template<template<class...> class L, class... T, class V> struct mp_find_impl<L<T...>, V>
735 {
736 static constexpr bool _v[] = { std::is_same<T, V>::value... };
737 using type = mp_size_t< cx_find_index( _v, _v + sizeof...(T) ) >;
738 };
739
740 #else
741
742 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, <= 1800 )
743
744 template<template<class...> class L, class... T, class V> struct mp_find_impl<L<T...>, V>
745 {
746 static_assert( sizeof...(T) == 0, "T... must be empty" );
747 using type = mp_size_t<0>;
748 };
749
750 #else
751
752 template<template<class...> class L, class V> struct mp_find_impl<L<>, V>
753 {
754 using type = mp_size_t<0>;
755 };
756
757 #endif
758
759 template<template<class...> class L, class... T, class V> struct mp_find_impl<L<V, T...>, V>
760 {
761 using type = mp_size_t<0>;
762 };
763
764 template<template<class...> class L, class T1, class... T, class V> struct mp_find_impl<L<T1, T...>, V>
765 {
766 using _r = typename mp_find_impl<mp_list<T...>, V>::type;
767 using type = mp_size_t<1 + _r::value>;
768 };
769
770 #endif
771
772 } // namespace detail
773
774 template<class L, class V> using mp_find = typename detail::mp_find_impl<L, V>::type;
775
776 // mp_find_if<L, P>
777 namespace detail
778 {
779
780 template<class L, template<class...> class P> struct mp_find_if_impl;
781
782 #if BOOST_MP11_CLANG && defined( BOOST_MP11_HAS_FOLD_EXPRESSIONS )
783
784 template<template<class...> class L, class... T, template<class...> class P> struct mp_find_if_impl<L<T...>, P>
785 {
786 static constexpr mp_index_holder _v{ 0, false };
787 using type = mp_size_t< (_v + ... + P<T>::value).i_ >;
788 };
789
790 #elif !defined( BOOST_MP11_NO_CONSTEXPR )
791
792 template<template<class...> class L, template<class...> class P> struct mp_find_if_impl<L<>, P>
793 {
794 using type = mp_size_t<0>;
795 };
796
797 template<template<class...> class L, class... T, template<class...> class P> struct mp_find_if_impl<L<T...>, P>
798 {
799 static constexpr bool _v[] = { P<T>::value... };
800 using type = mp_size_t< cx_find_index( _v, _v + sizeof...(T) ) >;
801 };
802
803 #else
804
805 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, <= 1800 )
806
807 template<template<class...> class L, class... T, template<class...> class P> struct mp_find_if_impl<L<T...>, P>
808 {
809 static_assert( sizeof...(T) == 0, "T... must be empty" );
810 using type = mp_size_t<0>;
811 };
812
813 #else
814
815 template<template<class...> class L, template<class...> class P> struct mp_find_if_impl<L<>, P>
816 {
817 using type = mp_size_t<0>;
818 };
819
820 #endif
821
822 template<class L, template<class...> class P> struct mp_find_if_impl_2
823 {
824 using _r = typename mp_find_if_impl<L, P>::type;
825 using type = mp_size_t<1 + _r::value>;
826 };
827
828 template<template<class...> class L, class T1, class... T, template<class...> class P> struct mp_find_if_impl<L<T1, T...>, P>
829 {
830 using type = typename mp_if<P<T1>, mp_identity<mp_size_t<0>>, mp_find_if_impl_2<mp_list<T...>, P>>::type;
831 };
832
833 #endif
834
835 } // namespace detail
836
837 template<class L, template<class...> class P> using mp_find_if = typename detail::mp_find_if_impl<L, P>::type;
838 template<class L, class Q> using mp_find_if_q = mp_find_if<L, Q::template fn>;
839
840 // mp_reverse<L>
841 namespace detail
842 {
843
844 template<class L> struct mp_reverse_impl;
845
846 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, <= 1800 )
847
848 template<template<class...> class L, class... T> struct mp_reverse_impl<L<T...>>
849 {
850 static_assert( sizeof...(T) == 0, "T... must be empty" );
851 using type = L<>;
852 };
853
854 #else
855
856 template<template<class...> class L> struct mp_reverse_impl<L<>>
857 {
858 using type = L<>;
859 };
860
861 #endif
862
863 template<template<class...> class L, class T1> struct mp_reverse_impl<L<T1>>
864 {
865 using type = L<T1>;
866 };
867
868 template<template<class...> class L, class T1, class T2> struct mp_reverse_impl<L<T1, T2>>
869 {
870 using type = L<T2, T1>;
871 };
872
873 template<template<class...> class L, class T1, class T2, class T3> struct mp_reverse_impl<L<T1, T2, T3>>
874 {
875 using type = L<T3, T2, T1>;
876 };
877
878 template<template<class...> class L, class T1, class T2, class T3, class T4> struct mp_reverse_impl<L<T1, T2, T3, T4>>
879 {
880 using type = L<T4, T3, T2, T1>;
881 };
882
883 template<template<class...> class L, class T1, class T2, class T3, class T4, class T5> struct mp_reverse_impl<L<T1, T2, T3, T4, T5>>
884 {
885 using type = L<T5, T4, T3, T2, T1>;
886 };
887
888 template<template<class...> class L, class T1, class T2, class T3, class T4, class T5, class T6> struct mp_reverse_impl<L<T1, T2, T3, T4, T5, T6>>
889 {
890 using type = L<T6, T5, T4, T3, T2, T1>;
891 };
892
893 template<template<class...> class L, class T1, class T2, class T3, class T4, class T5, class T6, class T7> struct mp_reverse_impl<L<T1, T2, T3, T4, T5, T6, T7>>
894 {
895 using type = L<T7, T6, T5, T4, T3, T2, T1>;
896 };
897
898 template<template<class...> class L, class T1, class T2, class T3, class T4, class T5, class T6, class T7, class T8> struct mp_reverse_impl<L<T1, T2, T3, T4, T5, T6, T7, T8>>
899 {
900 using type = L<T8, T7, T6, T5, T4, T3, T2, T1>;
901 };
902
903 template<template<class...> class L, class T1, class T2, class T3, class T4, class T5, class T6, class T7, class T8, class T9> struct mp_reverse_impl<L<T1, T2, T3, T4, T5, T6, T7, T8, T9>>
904 {
905 using type = L<T9, T8, T7, T6, T5, T4, T3, T2, T1>;
906 };
907
908 template<template<class...> class L, class T1, class T2, class T3, class T4, class T5, class T6, class T7, class T8, class T9, class T10, class... T> struct mp_reverse_impl<L<T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T...>>
909 {
910 using type = mp_push_back<typename mp_reverse_impl<L<T...>>::type, T10, T9, T8, T7, T6, T5, T4, T3, T2, T1>;
911 };
912
913 } // namespace detail
914
915 template<class L> using mp_reverse = typename detail::mp_reverse_impl<L>::type;
916
917 // mp_fold<L, V, F>
918 // in detail/mp_fold.hpp
919
920 // mp_reverse_fold<L, V, F>
921 namespace detail
922 {
923
924 template<class L, class V, template<class...> class F> struct mp_reverse_fold_impl;
925
926 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, <= 1800 )
927
928 template<template<class...> class L, class... T, class V, template<class...> class F> struct mp_reverse_fold_impl<L<T...>, V, F>
929 {
930 static_assert( sizeof...(T) == 0, "T... must be empty" );
931 using type = V;
932 };
933
934 #else
935
936 template<template<class...> class L, class V, template<class...> class F> struct mp_reverse_fold_impl<L<>, V, F>
937 {
938 using type = V;
939 };
940
941 #endif
942
943 template<template<class...> class L, class T1, class... T, class V, template<class...> class F> struct mp_reverse_fold_impl<L<T1, T...>, V, F>
944 {
945 using rest = typename mp_reverse_fold_impl<L<T...>, V, F>::type;
946 using type = F<T1, rest>;
947 };
948
949 template<template<class...> class L, class T1, class T2, class T3, class T4, class T5, class T6, class T7, class T8, class T9, class T10, class... T, class V, template<class...> class F> struct mp_reverse_fold_impl<L<T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T...>, V, F>
950 {
951 using rest = typename mp_reverse_fold_impl<L<T...>, V, F>::type;
952 using type = F<T1, F<T2, F<T3, F<T4, F<T5, F<T6, F<T7, F<T8, F<T9, F<T10, rest> > > > > > > > > >;
953 };
954
955 } // namespace detail
956
957 template<class L, class V, template<class...> class F> using mp_reverse_fold = typename detail::mp_reverse_fold_impl<L, V, F>::type;
958 template<class L, class V, class Q> using mp_reverse_fold_q = mp_reverse_fold<L, V, Q::template fn>;
959
960 // mp_unique<L>
961 namespace detail
962 {
963
964 template<class L> struct mp_unique_impl;
965
966 template<template<class...> class L, class... T> struct mp_unique_impl<L<T...>>
967 {
968 using type = mp_set_push_back<L<>, T...>;
969 };
970
971 } // namespace detail
972
973 template<class L> using mp_unique = typename detail::mp_unique_impl<L>::type;
974
975 // mp_unique_if<L, P>
976 namespace detail
977 {
978
979 template<template<class...> class P> struct mp_unique_if_push_back
980 {
981 template<class...> struct impl
982 {
983 };
984
985 template<template<class...> class L, class... Ts, class T>
986 struct impl<L<Ts...>, T>
987 {
988 using type = mp_if<mp_any<P<Ts, T>...>, L<Ts...>, L<Ts..., T>>;
989 };
990
991 template<class... T> using fn = typename impl<T...>::type;
992 };
993
994 } // namespace detail
995
996 template<class L, template<class...> class P>
997 using mp_unique_if = mp_fold_q<L, mp_clear<L>, detail::mp_unique_if_push_back<P>>;
998
999 template<class L, class Q> using mp_unique_if_q = mp_unique_if<L, Q::template fn>;
1000
1001 // mp_all_of<L, P>
1002 template<class L, template<class...> class P> using mp_all_of = mp_bool< mp_count_if<L, P>::value == mp_size<L>::value >;
1003 template<class L, class Q> using mp_all_of_q = mp_all_of<L, Q::template fn>;
1004
1005 // mp_none_of<L, P>
1006 template<class L, template<class...> class P> using mp_none_of = mp_bool< mp_count_if<L, P>::value == 0 >;
1007 template<class L, class Q> using mp_none_of_q = mp_none_of<L, Q::template fn>;
1008
1009 // mp_any_of<L, P>
1010 template<class L, template<class...> class P> using mp_any_of = mp_bool< mp_count_if<L, P>::value != 0 >;
1011 template<class L, class Q> using mp_any_of_q = mp_any_of<L, Q::template fn>;
1012
1013 // mp_replace_at_c<L, I, W>
1014 namespace detail
1015 {
1016
1017 template<class L, class I, class W> struct mp_replace_at_impl
1018 {
1019 static_assert( I::value >= 0, "mp_replace_at<L, I, W>: I must not be negative" );
1020
1021 template<class T1, class T2> using _p = std::is_same<T2, mp_size_t<I::value>>;
1022 template<class T1, class T2> using _f = W;
1023
1024 using type = mp_transform_if<_p, _f, L, mp_iota<mp_size<L> > >;
1025 };
1026
1027 } // namespace detail
1028
1029 template<class L, class I, class W> using mp_replace_at = typename detail::mp_replace_at_impl<L, I, W>::type;
1030 template<class L, std::size_t I, class W> using mp_replace_at_c = typename detail::mp_replace_at_impl<L, mp_size_t<I>, W>::type;
1031
1032 //mp_for_each<L>(f)
1033 namespace detail
1034 {
1035
mp_for_each_impl(mp_list<T...>,F && f)1036 template<class... T, class F> BOOST_MP11_CONSTEXPR F mp_for_each_impl( mp_list<T...>, F && f )
1037 {
1038 using A = int[sizeof...(T)];
1039 return (void)A{ ((void)f(T()), 0)... }, std::forward<F>(f);
1040 }
1041
mp_for_each_impl(mp_list<>,F && f)1042 template<class F> BOOST_MP11_CONSTEXPR F mp_for_each_impl( mp_list<>, F && f )
1043 {
1044 return std::forward<F>(f);
1045 }
1046
1047 } // namespace detail
1048
1049 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, >= 1900 )
1050
1051 // msvc has a limit of 1024
1052
mp_for_each(F && f)1053 template<class L, class F> BOOST_MP11_CONSTEXPR mp_if_c<mp_size<L>::value <= 1024, F> mp_for_each( F && f )
1054 {
1055 return detail::mp_for_each_impl( mp_rename<L, mp_list>(), std::forward<F>(f) );
1056 }
1057
1058 template<class L, class F> BOOST_MP11_CONSTEXPR mp_if_c<mp_size<L>::value >= 1025, F> mp_for_each( F && f )
1059 {
1060 using L2 = mp_rename<L, mp_list>;
1061
1062 using L3 = mp_take_c<L2, 1024>;
1063 using L4 = mp_drop_c<L2, 1024>;
1064
1065 return mp_for_each<L4>( mp_for_each<L3>( std::forward<F>(f) ) );
1066 }
1067
1068 #else
1069
mp_for_each(F && f)1070 template<class L, class F> BOOST_MP11_CONSTEXPR F mp_for_each( F && f )
1071 {
1072 return detail::mp_for_each_impl( mp_rename<L, mp_list>(), std::forward<F>(f) );
1073 }
1074
1075 #endif
1076
1077 // mp_insert<L, I, T...>
1078 template<class L, class I, class... T> using mp_insert = mp_append<mp_take<L, I>, mp_push_front<mp_drop<L, I>, T...>>;
1079
1080 // mp_insert_c<L, I, T...>
1081 template<class L, std::size_t I, class... T> using mp_insert_c = mp_append<mp_take_c<L, I>, mp_push_front<mp_drop_c<L, I>, T...>>;
1082
1083 // mp_erase<L, I, J>
1084 template<class L, class I, class J> using mp_erase = mp_append<mp_take<L, I>, mp_drop<L, J>>;
1085
1086 // mp_erase_c<L, I, J>
1087 template<class L, std::size_t I, std::size_t J> using mp_erase_c = mp_append<mp_take_c<L, I>, mp_drop_c<L, J>>;
1088
1089 // mp_starts_with<L1, L2>
1090 // contributed by Glen Joseph Fernandes (glenjofe@gmail.com)
1091 namespace detail {
1092
1093 template<class L1, class L2>
1094 struct mp_starts_with_impl { };
1095
1096 template<template<class...> class L1, class... T1, template<class...> class L2,
1097 class... T2>
1098 struct mp_starts_with_impl<L1<T1...>, L2<T2...> > {
1099 template<class L>
1100 static mp_false check(L);
1101
1102 template<class... T>
1103 static mp_true check(mp_list<T2..., T...>);
1104
1105 using type = decltype(check(mp_list<T1...>()));
1106 };
1107
1108 } // namespace detail
1109
1110 template<class L1, class L2>
1111 using mp_starts_with = typename detail::mp_starts_with_impl<L1, L2>::type;
1112
1113 // mp_rotate_left(_c)<L, N>
1114 namespace detail
1115 {
1116
1117 // limit divisor to 1 to avoid division by 0 and give a rotation of 0 for lists containing 0 or 1 elements
1118 template<std::size_t Ln, std::size_t N> using canonical_left_rotation = mp_size_t<N % (Ln == 0? 1: Ln)>;
1119
1120 // perform right rotation as a left rotation by inverting the number of elements to rotate
1121 template<std::size_t Ln, std::size_t N> using canonical_right_rotation = mp_size_t<Ln - N % (Ln == 0? 1: Ln)>;
1122
1123 // avoid errors when rotating fixed-sized lists by using mp_list for the transformation
1124 template<class L, class N, class L2 = mp_rename<L, mp_list>> using mp_rotate_impl = mp_assign<L, mp_append< mp_drop<L2, N>, mp_take<L2, N> >>;
1125
1126 } // namespace detail
1127
1128 template<class L, std::size_t N> using mp_rotate_left_c = detail::mp_rotate_impl<L, detail::canonical_left_rotation<mp_size<L>::value, N>>;
1129 template<class L, class N> using mp_rotate_left = mp_rotate_left_c<L, std::size_t{ N::value }>;
1130
1131 // mp_rotate_right(_c)<L, N>
1132 template<class L, std::size_t N> using mp_rotate_right_c = mp_rotate_left<L, detail::canonical_right_rotation<mp_size<L>::value, N>>;
1133 template<class L, class N> using mp_rotate_right = mp_rotate_right_c<L, std::size_t{ N::value }>;
1134
1135 // mp_min_element<L, P>
1136 // mp_max_element<L, P>
1137 // in detail/mp_min_element.hpp
1138
1139 // mp_power_set<L>
1140 namespace detail
1141 {
1142
1143 template<class L> struct mp_power_set_impl;
1144
1145 } // namespace detail
1146
1147 template<class L> using mp_power_set = typename detail::mp_power_set_impl<L>::type;
1148
1149 namespace detail
1150 {
1151
1152 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, <= 1800 )
1153
1154 template<template<class...> class L, class... T> struct mp_power_set_impl< L<T...> >
1155 {
1156 static_assert( sizeof...(T) == 0, "T... must be empty" );
1157 using type = L< L<> >;
1158 };
1159
1160 #else
1161
1162 template<template<class...> class L> struct mp_power_set_impl< L<> >
1163 {
1164 using type = L< L<> >;
1165 };
1166
1167 #endif
1168
1169 template<template<class...> class L, class T1, class... T> struct mp_power_set_impl< L<T1, T...> >
1170 {
1171 using S1 = mp_power_set< L<T...> >;
1172
1173 template<class L2> using _f = mp_push_front<L2, T1>;
1174
1175 using S2 = mp_transform<_f, S1>;
1176
1177 using type = mp_append< S1, S2 >;
1178 };
1179
1180 } // namespace detail
1181
1182 // mp_partial_sum<L, V, F>
1183 namespace detail
1184 {
1185
1186 template<template<class...> class F> struct mp_partial_sum_impl_f
1187 {
1188 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, <= 1900 )
1189
1190 template<class V, class T> using fn = mp_list<F<mp_first<V>, T>, mp_push_back<mp_second<V>, F<mp_first<V>, T>> >;
1191
1192 #else
1193
1194 template<class V, class T, class N = F<mp_first<V>, T>> using fn = mp_list<N, mp_push_back<mp_second<V>, N>>;
1195
1196 #endif
1197 };
1198
1199 } // namespace detail
1200
1201 template<class L, class V, template<class...> class F> using mp_partial_sum = mp_second<mp_fold_q<L, mp_list<V, mp_clear<L>>, detail::mp_partial_sum_impl_f<F>> >;
1202 template<class L, class V, class Q> using mp_partial_sum_q = mp_partial_sum<L, V, Q::template fn>;
1203
1204 // mp_iterate<V, F, R>
1205 namespace detail
1206 {
1207
1208 template<class V, template<class...> class F, template<class...> class R, class N> struct mp_iterate_impl;
1209
1210 } // namespace detail
1211
1212 template<class V, template<class...> class F, template<class...> class R> using mp_iterate = typename detail::mp_iterate_impl<V, F, R, mp_valid<R, V>>::type;
1213
1214 namespace detail
1215 {
1216
1217 template<class V, template<class...> class F, template<class...> class R> struct mp_iterate_impl<V, F, R, mp_false>
1218 {
1219 template<class X> using _f = mp_list<F<X>>;
1220 using type = mp_eval_or<mp_list<>, _f, V>;
1221 };
1222
1223 template<class V, template<class...> class F, template<class...> class R> struct mp_iterate_impl<V, F, R, mp_true>
1224 {
1225 using type = mp_push_front<mp_iterate<R<V>, F, R>, F<V>>;
1226 };
1227
1228 } // namespace detail
1229
1230 template<class V, class Qf, class Qr> using mp_iterate_q = mp_iterate<V, Qf::template fn, Qr::template fn>;
1231
1232 } // namespace mp11
1233 } // namespace boost
1234
1235 #endif // #ifndef BOOST_MP11_ALGORITHM_HPP_INCLUDED
1236