boost/mp11/algorithm.hpp

0001 #ifndef BOOST_MP11_ALGORITHM_HPP_INCLUDED
0002 #define BOOST_MP11_ALGORITHM_HPP_INCLUDED
0003
0004 //  Copyright 2015-2019 Peter Dimov
0005 //
0006 //  Distributed under the Boost Software License, Version 1.0.
0007 //
0008 //  See accompanying file LICENSE_1_0.txt or copy at
0009 //  http://www.boost.org/LICENSE_1_0.txt
0010
0011 #include <boost/mp11/list.hpp>
0012 #include <boost/mp11/set.hpp>
0013 #include <boost/mp11/integral.hpp>
0014 #include <boost/mp11/utility.hpp>
0015 #include <boost/mp11/function.hpp>
0016 #include <boost/mp11/detail/mp_count.hpp>
0017 #include <boost/mp11/detail/mp_plus.hpp>
0018 #include <boost/mp11/detail/mp_map_find.hpp>
0019 #include <boost/mp11/detail/mp_with_index.hpp>
0020 #include <boost/mp11/detail/mp_fold.hpp>
0021 #include <boost/mp11/detail/mp_min_element.hpp>
0022 #include <boost/mp11/detail/mp_copy_if.hpp>
0023 #include <boost/mp11/detail/mp_remove_if.hpp>
0024 #include <boost/mp11/detail/config.hpp>
0025 #include <boost/mp11/integer_sequence.hpp>
0026 #include <type_traits>
0027 #include <utility>
0028
0029 #if defined(_MSC_VER) || defined(__GNUC__)
0030 # pragma push_macro( "I" )
0031 # undef I
0032 #endif
0033
0034 namespace boost
0035 {
0036 namespace mp11
0037 {
0038
0039 // mp_transform<F, L...>
0040 namespace detail
0041 {
0042
0043 template<template<class...> class F, class... L> struct mp_transform_impl
0044 {
0045 };
0046
0047 template<template<class...> class F, template<class...> class L, class... T> struct mp_transform_impl<F, L<T...>>
0048 {
0049 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, < 1920 )
0050
0051     template<class... U> struct f { using type = F<U...>; };
0052
0053     using type = L<typename f<T>::type...>;
0054
0055 #else
0056
0057     using type = L<F<T>...>;
0058
0059 #endif
0060 };
0061
0062 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...>>
0063 {
0064 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, < 1920 )
0065
0066     template<class... U> struct f { using type = F<U...>; };
0067
0068     using type = L1<typename f<T1, T2>::type...>;
0069
0070 #else
0071
0072     using type = L1<F<T1,T2>...>;
0073
0074 #endif
0075 };
0076
0077 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...>>
0078 {
0079 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, < 1920 )
0080
0081     template<class... U> struct f { using type = F<U...>; };
0082
0083     using type = L1<typename f<T1, T2, T3>::type...>;
0084
0085 #else
0086
0087     using type = L1<F<T1,T2,T3>...>;
0088
0089 #endif
0090 };
0091
0092 #if defined(BOOST_MP11_HAS_TEMPLATE_AUTO)
0093
0094 template<template<class...> class F, template<auto...> class L, auto... A> struct mp_transform_impl<F, L<A...>>
0095 {
0096     using type = L< F< mp_value<A> >::value... >;
0097 };
0098
0099 template<template<class...> class F, template<auto...> class L1, auto... A1, template<auto...> class L2, auto... A2> struct mp_transform_impl<F, L1<A1...>, L2<A2...>>
0100 {
0101     using type = L1< F< mp_value<A1>, mp_value<A2> >::value... >;
0102 };
0103
0104 template<template<class...> class F, template<auto...> class L1, auto... A1, template<auto...> class L2, auto... A2, template<auto...> class L3, auto... A3> struct mp_transform_impl<F, L1<A1...>, L2<A2...>, L3<A3...>>
0105 {
0106     using type = L1< F< mp_value<A1>, mp_value<A2>, mp_value<A3> >::value... >;
0107 };
0108
0109 #endif
0110
0111 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, == 1900 ) || BOOST_MP11_WORKAROUND( BOOST_MP11_GCC, < 40800 )
0112
0113 template<class... L> using mp_same_size_1 = mp_same<mp_size<L>...>;
0114 template<class... L> struct mp_same_size_2: mp_defer<mp_same_size_1, L...> {};
0115
0116 #endif
0117
0118 struct list_size_mismatch
0119 {
0120 };
0121
0122 #if BOOST_MP11_WORKAROUND( BOOST_MP11_CUDA, >= 9000000 && BOOST_MP11_CUDA < 10000000 )
0123
0124 template<template<class...> class F, class... L> struct mp_transform_cuda_workaround
0125 {
0126     using type = mp_if<mp_same<mp_size<L>...>, detail::mp_transform_impl<F, L...>, detail::list_size_mismatch>;
0127 };
0128
0129 #endif
0130
0131 } // namespace detail
0132
0133 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, == 1900 ) || BOOST_MP11_WORKAROUND( BOOST_MP11_GCC, < 40800 )
0134
0135 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;
0136
0137 #else
0138
0139 #if BOOST_MP11_WORKAROUND( BOOST_MP11_CUDA, >= 9000000 && BOOST_MP11_CUDA < 10000000 )
0140
0141 template<template<class...> class F, class... L> using mp_transform = typename detail::mp_transform_cuda_workaround< F, L...>::type::type;
0142
0143 #else
0144
0145 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;
0146
0147 #endif
0148
0149 #endif
0150
0151 template<class Q, class... L> using mp_transform_q = mp_transform<Q::template fn, L...>;
0152
0153 namespace detail
0154 {
0155
0156 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...>
0157 {
0158     using A1 = L1<mp_list<T1, T2, T3, T4>...>;
0159
0160     template<class V, class T> using _f = mp_transform<mp_push_back, V, T>;
0161
0162     using A2 = mp_fold<mp_list<L...>, A1, _f>;
0163
0164     template<class T> using _g = mp_apply<F, T>;
0165
0166     using type = mp_transform<_g, A2>;
0167 };
0168
0169 } // namespace detail
0170
0171 // mp_transform_if<P, F, L...>
0172 namespace detail
0173 {
0174
0175 template<template<class...> class P, template<class...> class F, class... L> struct mp_transform_if_impl
0176 {
0177     // the stupid quote-unquote dance avoids "pack expansion used as argument for non-pack parameter of alias template"
0178
0179     using Qp = mp_quote<P>;
0180     using Qf = mp_quote<F>;
0181
0182 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, < 1920 )
0183
0184     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...>; };
0185     template<class... U> using _f = typename _f_<U...>::type;
0186
0187 #else
0188
0189     template<class... U> using _f = mp_eval_if_q<mp_not<mp_invoke_q<Qp, U...>>, mp_first<mp_list<U...>>, Qf, U...>;
0190
0191 #endif
0192
0193     using type = mp_transform<_f, L...>;
0194 };
0195
0196 } // namespace detail
0197
0198 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;
0199 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;
0200
0201 // mp_filter<P, L...>
0202 namespace detail
0203 {
0204
0205 template<template<class...> class P, class L1, class... L> struct mp_filter_impl
0206 {
0207     using Qp = mp_quote<P>;
0208
0209     template<class T1, class... T> using _f = mp_if< mp_invoke_q<Qp, T1, T...>, mp_list<T1>, mp_list<> >;
0210
0211     using _t1 = mp_transform<_f, L1, L...>;
0212     using _t2 = mp_apply<mp_append, _t1>;
0213
0214     using type = mp_assign<L1, _t2>;
0215 };
0216
0217 } // namespace detail
0218
0219 template<template<class...> class P, class... L> using mp_filter = typename detail::mp_filter_impl<P, L...>::type;
0220 template<class Q, class... L> using mp_filter_q = typename detail::mp_filter_impl<Q::template fn, L...>::type;
0221
0222 // mp_fill<L, V>
0223 namespace detail
0224 {
0225
0226 template<class L, class V> struct mp_fill_impl
0227 {
0228 // An error "no type named 'type'" here means that the L argument of mp_fill is not a list
0229 };
0230
0231 template<template<class...> class L, class... T, class V> struct mp_fill_impl<L<T...>, V>
0232 {
0233 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, <= 1900 )
0234
0235     template<class...> struct _f { using type = V; };
0236     using type = L<typename _f<T>::type...>;
0237
0238 #else
0239
0240     template<class...> using _f = V;
0241     using type = L<_f<T>...>;
0242
0243 #endif
0244 };
0245
0246 #if defined(BOOST_MP11_HAS_TEMPLATE_AUTO)
0247
0248 template<template<auto...> class L, auto... A, class V> struct mp_fill_impl<L<A...>, V>
0249 {
0250     using type = L<((void)A, V::value)...>;
0251 };
0252
0253 #endif
0254
0255 } // namespace detail
0256
0257 template<class L, class V> using mp_fill = typename detail::mp_fill_impl<L, V>::type;
0258
0259 // mp_contains<L, V>
0260 template<class L, class V> using mp_contains = mp_to_bool<mp_count<L, V>>;
0261
0262 // mp_repeat(_c)<L, N>
0263 namespace detail
0264 {
0265
0266 template<class L, std::size_t N> struct mp_repeat_c_impl
0267 {
0268     using _l1 = typename mp_repeat_c_impl<L, N/2>::type;
0269     using _l2 = typename mp_repeat_c_impl<L, N%2>::type;
0270
0271     using type = mp_append<_l1, _l1, _l2>;
0272 };
0273
0274 template<class L> struct mp_repeat_c_impl<L, 0>
0275 {
0276     using type = mp_clear<L>;
0277 };
0278
0279 template<class L> struct mp_repeat_c_impl<L, 1>
0280 {
0281     using type = L;
0282 };
0283
0284 } // namespace detail
0285
0286 template<class L, std::size_t N> using mp_repeat_c = typename detail::mp_repeat_c_impl<L, N>::type;
0287 template<class L, class N> using mp_repeat = typename detail::mp_repeat_c_impl<L, std::size_t{ N::value }>::type;
0288
0289 // mp_product<F, L...>
0290 namespace detail
0291 {
0292
0293 template<template<class...> class F, class P, class... L> struct mp_product_impl_2
0294 {
0295 };
0296
0297 template<template<class...> class F, class P> struct mp_product_impl_2<F, P>
0298 {
0299     using type = mp_list<mp_rename<P, F>>;
0300 };
0301
0302 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...>
0303 {
0304     using type = mp_append<typename mp_product_impl_2<F, mp_push_back<P, T1>, L...>::type...>;
0305 };
0306
0307 template<template<class...> class F, class... L> struct mp_product_impl
0308 {
0309 };
0310
0311 template<template<class...> class F> struct mp_product_impl<F>
0312 {
0313     using type = mp_list< F<> >;
0314 };
0315
0316 template<template<class...> class F, class L1, class... L> struct mp_product_impl<F, L1, L...>
0317 {
0318     using type = mp_assign<L1, typename mp_product_impl_2<F, mp_list<>, L1, L...>::type>;
0319 };
0320
0321 } // namespace detail
0322
0323 template<template<class...> class F, class... L> using mp_product = typename detail::mp_product_impl<F, L...>::type;
0324 template<class Q, class... L> using mp_product_q = typename detail::mp_product_impl<Q::template fn, L...>::type;
0325
0326 // mp_drop(_c)<L, N>
0327 namespace detail
0328 {
0329
0330 template<class L, class L2, class En> struct mp_drop_impl;
0331
0332 template<template<class...> class L, class... T, template<class...> class L2, class... U> struct mp_drop_impl<L<T...>, L2<U...>, mp_true>
0333 {
0334     template<class... W> static mp_identity<L<W...>> f( U*..., mp_identity<W>*... );
0335
0336     using R = decltype( f( static_cast<mp_identity<T>*>(0) ... ) );
0337
0338     using type = typename R::type;
0339 };
0340
0341 } // namespace detail
0342
0343 template<class L, std::size_t N> using mp_drop_c = mp_assign<L, typename detail::mp_drop_impl<mp_rename<L, mp_list>, mp_repeat_c<mp_list<void>, N>, mp_bool<N <= mp_size<L>::value>>::type>;
0344
0345 template<class L, class N> using mp_drop = mp_drop_c<L, std::size_t{ N::value }>;
0346
0347 // mp_from_sequence<S, F>
0348 namespace detail
0349 {
0350
0351 template<class S, class F, bool Z> struct mp_from_sequence_impl;
0352
0353 template<template<class T, T... I> class S, class U, U... J, class F> struct mp_from_sequence_impl<S<U, J...>, F, false>
0354 {
0355     using type = mp_list_c<U, (F::value + J)...>;
0356 };
0357
0358 template<template<class T, T... I> class S, class U, U... J, class F> struct mp_from_sequence_impl<S<U, J...>, F, true>
0359 {
0360     using type = mp_list_c<U, J...>;
0361 };
0362
0363 } // namespace detail
0364
0365 template<class S, class F = mp_int<0>> using mp_from_sequence = typename detail::mp_from_sequence_impl<S, F, (F::value == 0)>::type;
0366
0367 // mp_iota(_c)<N, F>
0368 template<std::size_t N, std::size_t F = 0> using mp_iota_c = mp_from_sequence<make_index_sequence<N>, mp_size_t<F>>;
0369 template<class N, class F = mp_int<0>> using mp_iota = mp_from_sequence<make_integer_sequence<typename std::remove_const<decltype(N::value)>::type, N::value>, F>;
0370
0371 // mp_at(_c)<L, I>
0372 namespace detail
0373 {
0374
0375 template<class L, std::size_t I> struct mp_at_c_impl;
0376
0377 #if defined(BOOST_MP11_HAS_TYPE_PACK_ELEMENT)
0378
0379 template<template<class...> class L, class... T, std::size_t I> struct mp_at_c_impl<L<T...>, I>
0380 {
0381     using type = __type_pack_element<I, T...>;
0382 };
0383
0384 #if defined(BOOST_MP11_HAS_TEMPLATE_AUTO)
0385
0386 template<template<auto...> class L, auto... A, std::size_t I> struct mp_at_c_impl<L<A...>, I>
0387 {
0388     using type = __type_pack_element<I, mp_value<A>...>;
0389 };
0390
0391 #endif
0392
0393 #else
0394
0395 template<class L, std::size_t I> struct mp_at_c_impl
0396 {
0397     using _map = mp_transform<mp_list, mp_iota<mp_size<L> >, mp_rename<L, mp_list>>;
0398     using type = mp_second<mp_map_find<_map, mp_size_t<I> > >;
0399 };
0400
0401 #endif
0402
0403 #if BOOST_MP11_WORKAROUND( BOOST_MP11_CUDA, >= 9000000 && BOOST_MP11_CUDA < 10000000 )
0404
0405 template<class L, std::size_t I> struct mp_at_c_cuda_workaround
0406 {
0407     using type = mp_if_c<(I < mp_size<L>::value), detail::mp_at_c_impl<L, I>, void>;
0408 };
0409
0410 #endif
0411
0412 } // namespace detail
0413
0414 #if BOOST_MP11_WORKAROUND( BOOST_MP11_CUDA, >= 9000000 && BOOST_MP11_CUDA < 10000000 )
0415
0416 template<class L, std::size_t I> using mp_at_c = typename detail::mp_at_c_cuda_workaround< L, I >::type::type;
0417
0418 #else
0419
0420 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;
0421
0422 #endif
0423
0424 template<class L, class I> using mp_at = mp_at_c<L, std::size_t{ I::value }>;
0425
0426 // mp_take(_c)<L, N>
0427 namespace detail
0428 {
0429
0430 template<std::size_t N, class L, class E = void> struct mp_take_c_impl
0431 {
0432 };
0433
0434 template<template<class...> class L, class... T>
0435 struct mp_take_c_impl<0, L<T...>>
0436 {
0437     using type = L<>;
0438 };
0439
0440 template<template<class...> class L, class T1, class... T>
0441 struct mp_take_c_impl<1, L<T1, T...>>
0442 {
0443     using type = L<T1>;
0444 };
0445
0446 template<template<class...> class L, class T1, class T2, class... T>
0447 struct mp_take_c_impl<2, L<T1, T2, T...>>
0448 {
0449     using type = L<T1, T2>;
0450 };
0451
0452 template<template<class...> class L, class T1, class T2, class T3, class... T>
0453 struct mp_take_c_impl<3, L<T1, T2, T3, T...>>
0454 {
0455     using type = L<T1, T2, T3>;
0456 };
0457
0458 template<template<class...> class L, class T1, class T2, class T3, class T4, class... T>
0459 struct mp_take_c_impl<4, L<T1, T2, T3, T4, T...>>
0460 {
0461     using type = L<T1, T2, T3, T4>;
0462 };
0463
0464 template<template<class...> class L, class T1, class T2, class T3, class T4, class T5, class... T>
0465 struct mp_take_c_impl<5, L<T1, T2, T3, T4, T5, T...>>
0466 {
0467     using type = L<T1, T2, T3, T4, T5>;
0468 };
0469
0470 template<template<class...> class L, class T1, class T2, class T3, class T4, class T5, class T6, class... T>
0471 struct mp_take_c_impl<6, L<T1, T2, T3, T4, T5, T6, T...>>
0472 {
0473     using type = L<T1, T2, T3, T4, T5, T6>;
0474 };
0475
0476 template<template<class...> class L, class T1, class T2, class T3, class T4, class T5, class T6, class T7, class... T>
0477 struct mp_take_c_impl<7, L<T1, T2, T3, T4, T5, T6, T7, T...>>
0478 {
0479     using type = L<T1, T2, T3, T4, T5, T6, T7>;
0480 };
0481
0482 template<template<class...> class L, class T1, class T2, class T3, class T4, class T5, class T6, class T7, class T8, class... T>
0483 struct mp_take_c_impl<8, L<T1, T2, T3, T4, T5, T6, T7, T8, T...>>
0484 {
0485     using type = L<T1, T2, T3, T4, T5, T6, T7, T8>;
0486 };
0487
0488 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>
0489 struct mp_take_c_impl<9, L<T1, T2, T3, T4, T5, T6, T7, T8, T9, T...>>
0490 {
0491     using type = L<T1, T2, T3, T4, T5, T6, T7, T8, T9>;
0492 };
0493
0494 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>
0495 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>
0496 {
0497     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>;
0498 };
0499
0500 } // namespace detail
0501
0502 template<class L, std::size_t N> using mp_take_c = mp_assign<L, typename detail::mp_take_c_impl<N, mp_rename<L, mp_list>>::type>;
0503 template<class L, class N> using mp_take = mp_take_c<L, std::size_t{ N::value }>;
0504
0505 // mp_slice(_c)<L, I, J>
0506 template<class L, std::size_t I, std::size_t J> using mp_slice_c = mp_drop_c< mp_take_c<L, J>, I >;
0507 template<class L, class I, class J> using mp_slice = mp_drop< mp_take<L, J>, I >;
0508
0509 // mp_back<L>
0510 template<class L> using mp_back = mp_at_c<L, mp_size<L>::value - 1>;
0511
0512 // mp_pop_back<L>
0513 template<class L> using mp_pop_back = mp_take_c<L, mp_size<L>::value - 1>;
0514
0515 // mp_replace<L, V, W>
0516 namespace detail
0517 {
0518
0519 template<class L, class V, class W> struct mp_replace_impl;
0520
0521 template<template<class...> class L, class... T, class V, class W> struct mp_replace_impl<L<T...>, V, W>
0522 {
0523 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, <= 1800 )
0524     template<class A> struct _f { using type = mp_if<std::is_same<A, V>, W, A>; };
0525     using type = L<typename _f<T>::type...>;
0526 #else
0527     template<class A> using _f = mp_if<std::is_same<A, V>, W, A>;
0528     using type = L<_f<T>...>;
0529 #endif
0530 };
0531
0532 } // namespace detail
0533
0534 template<class L, class V, class W> using mp_replace = typename detail::mp_replace_impl<L, V, W>::type;
0535
0536 // mp_replace_if<L, P, W>
0537 namespace detail
0538 {
0539
0540 template<class L, template<class...> class P, class W> struct mp_replace_if_impl;
0541
0542 template<template<class...> class L, class... T, template<class...> class P, class W> struct mp_replace_if_impl<L<T...>, P, W>
0543 {
0544 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, < 1920 )
0545     template<class U> struct _f { using type = mp_if<P<U>, W, U>; };
0546     using type = L<typename _f<T>::type...>;
0547 #else
0548     template<class U> using _f = mp_if<P<U>, W, U>;
0549     using type = L<_f<T>...>;
0550 #endif
0551 };
0552
0553 } // namespace detail
0554
0555 template<class L, template<class...> class P, class W> using mp_replace_if = typename detail::mp_replace_if_impl<L, P, W>::type;
0556 template<class L, class Q, class W> using mp_replace_if_q = mp_replace_if<L, Q::template fn, W>;
0557
0558 // mp_copy_if<L, P>
0559 //   in detail/mp_copy_if.hpp
0560
0561 // mp_remove<L, V>
0562 namespace detail
0563 {
0564
0565 template<class L, class V> struct mp_remove_impl;
0566
0567 template<template<class...> class L, class... T, class V> struct mp_remove_impl<L<T...>, V>
0568 {
0569 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, < 1920 )
0570     template<class U> struct _f { using type = mp_if<std::is_same<U, V>, mp_list<>, mp_list<U>>; };
0571     using type = mp_append<L<>, typename _f<T>::type...>;
0572 #else
0573     template<class U> using _f = mp_if<std::is_same<U, V>, mp_list<>, mp_list<U>>;
0574     using type = mp_append<L<>, _f<T>...>;
0575 #endif
0576 };
0577
0578 } // namespace detail
0579
0580 template<class L, class V> using mp_remove = typename detail::mp_remove_impl<L, V>::type;
0581
0582 // mp_remove_if<L, P>
0583 //   in detail/mp_remove_if.hpp
0584
0585 // mp_flatten<L, L2 = mp_clear<L>>
0586 namespace detail
0587 {
0588
0589 template<class L2> struct mp_flatten_impl
0590 {
0591     template<class T> using fn = mp_if<mp_similar<L2, T>, T, mp_list<T>>;
0592 };
0593
0594 } // namespace detail
0595
0596 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>>>;
0597
0598 // mp_partition<L, P>
0599 namespace detail
0600 {
0601
0602 template<class L, template<class...> class P> struct mp_partition_impl;
0603
0604 template<template<class...> class L, class... T, template<class...> class P> struct mp_partition_impl<L<T...>, P>
0605 {
0606     using type = L<mp_copy_if<L<T...>, P>, mp_remove_if<L<T...>, P>>;
0607 };
0608
0609 } // namespace detail
0610
0611 template<class L, template<class...> class P> using mp_partition = typename detail::mp_partition_impl<L, P>::type;
0612 template<class L, class Q> using mp_partition_q = mp_partition<L, Q::template fn>;
0613
0614 // mp_sort<L, P>
0615 namespace detail
0616 {
0617
0618 template<class L, template<class...> class P> struct mp_sort_impl;
0619
0620 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, <= 1800 )
0621
0622 template<template<class...> class L, class... T, template<class...> class P> struct mp_sort_impl<L<T...>, P>
0623 {
0624     static_assert( sizeof...(T) == 0, "T... must be empty" );
0625     using type = L<>;
0626 };
0627
0628 #else
0629
0630 template<template<class...> class L, template<class...> class P> struct mp_sort_impl<L<>, P>
0631 {
0632     using type = L<>;
0633 };
0634
0635 #endif
0636
0637 template<template<class...> class L, class T1, template<class...> class P> struct mp_sort_impl<L<T1>, P>
0638 {
0639     using type = L<T1>;
0640 };
0641
0642 template<template<class...> class L, class T1, class... T, template<class...> class P> struct mp_sort_impl<L<T1, T...>, P>
0643 {
0644     template<class U> using F = P<U, T1>;
0645
0646     using part = mp_partition<L<T...>, F>;
0647
0648     using S1 = typename mp_sort_impl<mp_first<part>, P>::type;
0649     using S2 = typename mp_sort_impl<mp_second<part>, P>::type;
0650
0651     using type = mp_append<mp_push_back<S1, T1>, S2>;
0652 };
0653
0654 } // namespace detail
0655
0656 template<class L, template<class...> class P> using mp_sort = typename detail::mp_sort_impl<L, P>::type;
0657 template<class L, class Q> using mp_sort_q = mp_sort<L, Q::template fn>;
0658
0659 // mp_nth_element(_c)<L, I, P>
0660 namespace detail
0661 {
0662
0663 template<class L, std::size_t I, template<class...> class P> struct mp_nth_element_impl;
0664
0665 template<template<class...> class L, class T1, std::size_t I, template<class...> class P> struct mp_nth_element_impl<L<T1>, I, P>
0666 {
0667     static_assert( I == 0, "mp_nth_element index out of range" );
0668     using type = T1;
0669 };
0670
0671 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>
0672 {
0673     static_assert( I < 1 + sizeof...(T), "mp_nth_element index out of range" );
0674
0675     template<class U> using F = P<U, T1>;
0676
0677     using part = mp_partition<L<T...>, F>;
0678
0679     using L1 = mp_first<part>;
0680     static std::size_t const N1 = mp_size<L1>::value;
0681
0682     using L2 = mp_second<part>;
0683
0684 #if BOOST_MP11_WORKAROUND( BOOST_MP11_CUDA, >= 9000000 && BOOST_MP11_CUDA < 10000000 )
0685
0686     struct detail
0687     {
0688         struct mp_nth_element_impl_cuda_workaround
0689         {
0690             using type = mp_cond<
0691
0692                 mp_bool<(I < N1)>, mp_nth_element_impl<L1, I, P>,
0693                 mp_bool<(I == N1)>, mp_identity<T1>,
0694                 mp_true, mp_nth_element_impl<L2, I - N1 - 1, P>
0695
0696             >;
0697         };
0698     };
0699
0700     using type = typename detail::mp_nth_element_impl_cuda_workaround::type::type;
0701
0702 #else
0703
0704     using type = typename mp_cond<
0705
0706         mp_bool<(I < N1)>, mp_nth_element_impl<L1, I, P>,
0707         mp_bool<(I == N1)>, mp_identity<T1>,
0708         mp_true, mp_nth_element_impl<L2, I - N1 - 1, P>
0709
0710     >::type;
0711
0712 #endif
0713 };
0714
0715 } // namespace detail
0716
0717 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;
0718 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;
0719 template<class L, class I, class Q> using mp_nth_element_q = mp_nth_element<L, I, Q::template fn>;
0720
0721 // mp_find<L, V>
0722 namespace detail
0723 {
0724
0725 template<class L, class V> struct mp_find_impl;
0726
0727 #if !defined( BOOST_MP11_NO_CONSTEXPR )
0728
0729 template<template<class...> class L, class V> struct mp_find_impl<L<>, V>
0730 {
0731     using type = mp_size_t<0>;
0732 };
0733
0734 #if defined( BOOST_MP11_HAS_CXX14_CONSTEXPR )
0735
0736 constexpr std::size_t cx_find_index( bool const * first, bool const * last )
0737 {
0738     std::size_t m = 0;
0739
0740     while( first != last && !*first )
0741     {
0742         ++m;
0743         ++first;
0744     }
0745
0746     return m;
0747 }
0748
0749 #else
0750
0751 constexpr std::size_t cx_find_index( bool const * first, bool const * last )
0752 {
0753     return first == last || *first? 0: 1 + cx_find_index( first + 1, last );
0754 }
0755
0756 #endif
0757
0758 template<template<class...> class L, class... T, class V> struct mp_find_impl<L<T...>, V>
0759 {
0760     static constexpr bool _v[] = { std::is_same<T, V>::value... };
0761     using type = mp_size_t< cx_find_index( _v, _v + sizeof...(T) ) >;
0762 };
0763
0764 #else
0765
0766 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, <= 1800 )
0767
0768 template<template<class...> class L, class... T, class V> struct mp_find_impl<L<T...>, V>
0769 {
0770     static_assert( sizeof...(T) == 0, "T... must be empty" );
0771     using type = mp_size_t<0>;
0772 };
0773
0774 #else
0775
0776 template<template<class...> class L, class V> struct mp_find_impl<L<>, V>
0777 {
0778     using type = mp_size_t<0>;
0779 };
0780
0781 #endif
0782
0783 template<template<class...> class L, class... T, class V> struct mp_find_impl<L<V, T...>, V>
0784 {
0785     using type = mp_size_t<0>;
0786 };
0787
0788 template<template<class...> class L, class T1, class... T, class V> struct mp_find_impl<L<T1, T...>, V>
0789 {
0790     using _r = typename mp_find_impl<mp_list<T...>, V>::type;
0791     using type = mp_size_t<1 + _r::value>;
0792 };
0793
0794 #endif
0795
0796 } // namespace detail
0797
0798 template<class L, class V> using mp_find = typename detail::mp_find_impl<L, V>::type;
0799
0800 // mp_find_if<L, P>
0801 namespace detail
0802 {
0803
0804 template<class L, template<class...> class P> struct mp_find_if_impl;
0805
0806 #if !defined( BOOST_MP11_NO_CONSTEXPR )
0807
0808 template<template<class...> class L, template<class...> class P> struct mp_find_if_impl<L<>, P>
0809 {
0810     using type = mp_size_t<0>;
0811 };
0812
0813 template<template<class...> class L, class... T, template<class...> class P> struct mp_find_if_impl<L<T...>, P>
0814 {
0815     static constexpr bool _v[] = { P<T>::value... };
0816     using type = mp_size_t< cx_find_index( _v, _v + sizeof...(T) ) >;
0817 };
0818
0819 #else
0820
0821 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, <= 1800 )
0822
0823 template<template<class...> class L, class... T, template<class...> class P> struct mp_find_if_impl<L<T...>, P>
0824 {
0825     static_assert( sizeof...(T) == 0, "T... must be empty" );
0826     using type = mp_size_t<0>;
0827 };
0828
0829 #else
0830
0831 template<template<class...> class L, template<class...> class P> struct mp_find_if_impl<L<>, P>
0832 {
0833     using type = mp_size_t<0>;
0834 };
0835
0836 #endif
0837
0838 template<class L, template<class...> class P> struct mp_find_if_impl_2
0839 {
0840     using _r = typename mp_find_if_impl<L, P>::type;
0841     using type = mp_size_t<1 + _r::value>;
0842 };
0843
0844 template<template<class...> class L, class T1, class... T, template<class...> class P> struct mp_find_if_impl<L<T1, T...>, P>
0845 {
0846     using type = typename mp_if<P<T1>, mp_identity<mp_size_t<0>>, mp_find_if_impl_2<mp_list<T...>, P>>::type;
0847 };
0848
0849 #endif
0850
0851 } // namespace detail
0852
0853 template<class L, template<class...> class P> using mp_find_if = typename detail::mp_find_if_impl<L, P>::type;
0854 template<class L, class Q> using mp_find_if_q = mp_find_if<L, Q::template fn>;
0855
0856 // mp_reverse<L>
0857 namespace detail
0858 {
0859
0860 template<class L> struct mp_reverse_impl;
0861
0862 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, <= 1800 )
0863
0864 template<template<class...> class L, class... T> struct mp_reverse_impl<L<T...>>
0865 {
0866     static_assert( sizeof...(T) == 0, "T... must be empty" );
0867     using type = L<>;
0868 };
0869
0870 #else
0871
0872 template<template<class...> class L> struct mp_reverse_impl<L<>>
0873 {
0874     using type = L<>;
0875 };
0876
0877 #endif
0878
0879 template<template<class...> class L, class T1> struct mp_reverse_impl<L<T1>>
0880 {
0881     using type = L<T1>;
0882 };
0883
0884 template<template<class...> class L, class T1, class T2> struct mp_reverse_impl<L<T1, T2>>
0885 {
0886     using type = L<T2, T1>;
0887 };
0888
0889 template<template<class...> class L, class T1, class T2, class T3> struct mp_reverse_impl<L<T1, T2, T3>>
0890 {
0891     using type = L<T3, T2, T1>;
0892 };
0893
0894 template<template<class...> class L, class T1, class T2, class T3, class T4> struct mp_reverse_impl<L<T1, T2, T3, T4>>
0895 {
0896     using type = L<T4, T3, T2, T1>;
0897 };
0898
0899 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>>
0900 {
0901     using type = L<T5, T4, T3, T2, T1>;
0902 };
0903
0904 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>>
0905 {
0906     using type = L<T6, T5, T4, T3, T2, T1>;
0907 };
0908
0909 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>>
0910 {
0911     using type = L<T7, T6, T5, T4, T3, T2, T1>;
0912 };
0913
0914 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>>
0915 {
0916     using type = L<T8, T7, T6, T5, T4, T3, T2, T1>;
0917 };
0918
0919 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>>
0920 {
0921     using type = L<T9, T8, T7, T6, T5, T4, T3, T2, T1>;
0922 };
0923
0924 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...>>
0925 {
0926     using type = mp_push_back<typename mp_reverse_impl<L<T...>>::type, T10, T9, T8, T7, T6, T5, T4, T3, T2, T1>;
0927 };
0928
0929 } // namespace detail
0930
0931 template<class L> using mp_reverse = typename detail::mp_reverse_impl<L>::type;
0932
0933 // mp_fold<L, V, F>
0934 //   in detail/mp_fold.hpp
0935
0936 // mp_reverse_fold<L, V, F>
0937 namespace detail
0938 {
0939
0940 template<class L, class V, template<class...> class F> struct mp_reverse_fold_impl;
0941
0942 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, <= 1800 )
0943
0944 template<template<class...> class L, class... T, class V, template<class...> class F> struct mp_reverse_fold_impl<L<T...>, V, F>
0945 {
0946     static_assert( sizeof...(T) == 0, "T... must be empty" );
0947     using type = V;
0948 };
0949
0950 #else
0951
0952 template<template<class...> class L, class V, template<class...> class F> struct mp_reverse_fold_impl<L<>, V, F>
0953 {
0954     using type = V;
0955 };
0956
0957 #endif
0958
0959 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>
0960 {
0961     using rest = typename mp_reverse_fold_impl<L<T...>, V, F>::type;
0962     using type = F<T1, rest>;
0963 };
0964
0965 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>
0966 {
0967     using rest = typename mp_reverse_fold_impl<L<T...>, V, F>::type;
0968     using type = F<T1, F<T2, F<T3, F<T4, F<T5, F<T6, F<T7, F<T8, F<T9, F<T10, rest> > > > > > > > > >;
0969 };
0970
0971 } // namespace detail
0972
0973 template<class L, class V, template<class...> class F> using mp_reverse_fold = typename detail::mp_reverse_fold_impl<L, V, F>::type;
0974 template<class L, class V, class Q> using mp_reverse_fold_q = mp_reverse_fold<L, V, Q::template fn>;
0975
0976 // mp_unique<L>
0977 namespace detail
0978 {
0979
0980 template<class L> struct mp_unique_impl;
0981
0982 template<template<class...> class L, class... T> struct mp_unique_impl<L<T...>>
0983 {
0984     using type = mp_set_push_back<L<>, T...>;
0985 };
0986
0987 } // namespace detail
0988
0989 template<class L> using mp_unique = typename detail::mp_unique_impl<L>::type;
0990
0991 // mp_unique_if<L, P>
0992 namespace detail
0993 {
0994
0995 template<template<class...> class P> struct mp_unique_if_push_back
0996 {
0997     template<class...> struct impl
0998     {
0999     };
1000
1001     template<template<class...> class L, class... Ts, class T>
1002     struct impl<L<Ts...>, T>
1003     {
1004         using type = mp_if<mp_any<P<Ts, T>...>, L<Ts...>, L<Ts..., T>>;
1005     };
1006
1007     template<class... T> using fn = typename impl<T...>::type;
1008 };
1009
1010 } // namespace detail
1011
1012 template<class L, template<class...> class P>
1013 using mp_unique_if = mp_fold_q<L, mp_clear<L>, detail::mp_unique_if_push_back<P>>;
1014
1015 template<class L, class Q> using mp_unique_if_q = mp_unique_if<L, Q::template fn>;
1016
1017 // mp_all_of<L, P>
1018 template<class L, template<class...> class P> using mp_all_of = mp_bool< mp_count_if<L, P>::value == mp_size<L>::value >;
1019 template<class L, class Q> using mp_all_of_q = mp_all_of<L, Q::template fn>;
1020
1021 // mp_none_of<L, P>
1022 template<class L, template<class...> class P> using mp_none_of = mp_bool< mp_count_if<L, P>::value == 0 >;
1023 template<class L, class Q> using mp_none_of_q = mp_none_of<L, Q::template fn>;
1024
1025 // mp_any_of<L, P>
1026 template<class L, template<class...> class P> using mp_any_of = mp_bool< mp_count_if<L, P>::value != 0 >;
1027 template<class L, class Q> using mp_any_of_q = mp_any_of<L, Q::template fn>;
1028
1029 // mp_replace_at_c<L, I, W>
1030 namespace detail
1031 {
1032
1033 template<class L, class I, class W> struct mp_replace_at_impl
1034 {
1035     static_assert( I::value >= 0, "mp_replace_at<L, I, W>: I must not be negative" );
1036
1037     template<class T1, class T2> using _p = std::is_same<T2, mp_size_t<I::value>>;
1038     template<class T1, class T2> using _f = W;
1039
1040     using type = mp_transform_if<_p, _f, L, mp_iota<mp_size<L> > >;
1041 };
1042
1043 } // namespace detail
1044
1045 template<class L, class I, class W> using mp_replace_at = typename detail::mp_replace_at_impl<L, I, W>::type;
1046 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;
1047
1048 //mp_for_each<L>(f)
1049 namespace detail
1050 {
1051
1052 template<class... T, class F> BOOST_MP11_CONSTEXPR F mp_for_each_impl( mp_list<T...>, F && f )
1053 {
1054     using A = int[sizeof...(T)];
1055     return (void)A{ ((void)f(T()), 0)... }, std::forward<F>(f);
1056 }
1057
1058 template<class F> BOOST_MP11_CONSTEXPR F mp_for_each_impl( mp_list<>, F && f )
1059 {
1060     return std::forward<F>(f);
1061 }
1062
1063 } // namespace detail
1064
1065 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, >= 1900 )
1066
1067 // msvc has a limit of 1024
1068
1069 template<class L, class F> BOOST_MP11_CONSTEXPR mp_if_c<mp_size<L>::value <= 1024, F> mp_for_each( F && f )
1070 {
1071     return detail::mp_for_each_impl( mp_rename<L, mp_list>(), std::forward<F>(f) );
1072 }
1073
1074 template<class L, class F> BOOST_MP11_CONSTEXPR mp_if_c<mp_size<L>::value >= 1025, F> mp_for_each( F && f )
1075 {
1076     using L2 = mp_rename<L, mp_list>;
1077
1078     using L3 = mp_take_c<L2, 1024>;
1079     using L4 = mp_drop_c<L2, 1024>;
1080
1081     return mp_for_each<L4>( mp_for_each<L3>( std::forward<F>(f) ) );
1082 }
1083
1084 #else
1085
1086 template<class L, class F> BOOST_MP11_CONSTEXPR F mp_for_each( F && f )
1087 {
1088     return detail::mp_for_each_impl( mp_rename<L, mp_list>(), std::forward<F>(f) );
1089 }
1090
1091 #endif
1092
1093 // mp_insert<L, I, T...>
1094 template<class L, class I, class... T> using mp_insert = mp_append<mp_take<L, I>, mp_push_front<mp_drop<L, I>, T...>>;
1095
1096 // mp_insert_c<L, I, T...>
1097 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...>>;
1098
1099 // mp_erase<L, I, J>
1100 template<class L, class I, class J> using mp_erase = mp_append<mp_take<L, I>, mp_drop<L, J>>;
1101
1102 // mp_erase_c<L, I, J>
1103 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>>;
1104
1105 // mp_starts_with<L1, L2>
1106 // contributed by Glen Joseph Fernandes (glenjofe@gmail.com)
1107 namespace detail {
1108
1109 template<class L1, class L2>
1110 struct mp_starts_with_impl { };
1111
1112 template<template<class...> class L1, class... T1, template<class...> class L2,
1113     class... T2>
1114 struct mp_starts_with_impl<L1<T1...>, L2<T2...> > {
1115     template<class L>
1116     static mp_false check(L);
1117
1118     template<class... T>
1119     static mp_true check(mp_list<T2..., T...>);
1120
1121     using type = decltype(check(mp_list<T1...>()));
1122 };
1123
1124 } // namespace detail
1125
1126 template<class L1, class L2>
1127 using mp_starts_with = typename detail::mp_starts_with_impl<L1, L2>::type;
1128
1129 // mp_rotate_left(_c)<L, N>
1130 namespace detail
1131 {
1132
1133 // limit divisor to 1 to avoid division by 0 and give a rotation of 0 for lists containing 0 or 1 elements
1134 template<std::size_t Ln, std::size_t N> using canonical_left_rotation = mp_size_t<N % (Ln == 0? 1: Ln)>;
1135
1136 // perform right rotation as a left rotation by inverting the number of elements to rotate
1137 template<std::size_t Ln, std::size_t N> using canonical_right_rotation = mp_size_t<Ln - N % (Ln == 0? 1: Ln)>;
1138
1139 // avoid errors when rotating fixed-sized lists by using mp_list for the transformation
1140 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> >>;
1141
1142 } // namespace detail
1143
1144 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>>;
1145 template<class L, class N> using mp_rotate_left = mp_rotate_left_c<L, std::size_t{ N::value }>;
1146
1147 // mp_rotate_right(_c)<L, N>
1148 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>>;
1149 template<class L, class N> using mp_rotate_right = mp_rotate_right_c<L, std::size_t{ N::value }>;
1150
1151 // mp_min_element<L, P>
1152 // mp_max_element<L, P>
1153 //   in detail/mp_min_element.hpp
1154
1155 // mp_power_set<L>
1156 namespace detail
1157 {
1158
1159 template<class L> struct mp_power_set_impl;
1160
1161 } // namespace detail
1162
1163 template<class L> using mp_power_set = typename detail::mp_power_set_impl<L>::type;
1164
1165 namespace detail
1166 {
1167
1168 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, <= 1800 )
1169
1170 template<template<class...> class L, class... T> struct mp_power_set_impl< L<T...> >
1171 {
1172     static_assert( sizeof...(T) == 0, "T... must be empty" );
1173     using type = L< L<> >;
1174 };
1175
1176 #else
1177
1178 template<template<class...> class L> struct mp_power_set_impl< L<> >
1179 {
1180     using type = L< L<> >;
1181 };
1182
1183 #endif
1184
1185 template<template<class...> class L, class T1, class... T> struct mp_power_set_impl< L<T1, T...> >
1186 {
1187     using S1 = mp_power_set< L<T...> >;
1188
1189     template<class L2> using _f = mp_push_front<L2, T1>;
1190
1191     using S2 = mp_transform<_f, S1>;
1192
1193     using type = mp_append< S1, S2 >;
1194 };
1195
1196 } // namespace detail
1197
1198 // mp_partial_sum<L, V, F>
1199 namespace detail
1200 {
1201
1202 template<template<class...> class F> struct mp_partial_sum_impl_f
1203 {
1204 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, <= 1900 )
1205
1206     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>> >;
1207
1208 #else
1209
1210     template<class V, class T, class N = F<mp_first<V>, T>> using fn = mp_list<N, mp_push_back<mp_second<V>, N>>;
1211
1212 #endif
1213 };
1214
1215 } // namespace detail
1216
1217 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>> >;
1218 template<class L, class V, class Q> using mp_partial_sum_q = mp_partial_sum<L, V, Q::template fn>;
1219
1220 // mp_iterate<V, F, R>
1221 namespace detail
1222 {
1223
1224 template<class V, template<class...> class F, template<class...> class R, class N> struct mp_iterate_impl;
1225
1226 } // namespace detail
1227
1228 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;
1229
1230 namespace detail
1231 {
1232
1233 template<class V, template<class...> class F, template<class...> class R> struct mp_iterate_impl<V, F, R, mp_false>
1234 {
1235     template<class X> using _f = mp_list<F<X>>;
1236     using type = mp_eval_or<mp_list<>, _f, V>;
1237 };
1238
1239 template<class V, template<class...> class F, template<class...> class R> struct mp_iterate_impl<V, F, R, mp_true>
1240 {
1241     using type = mp_push_front<mp_iterate<R<V>, F, R>, F<V>>;
1242 };
1243
1244 } // namespace detail
1245
1246 template<class V, class Qf, class Qr> using mp_iterate_q = mp_iterate<V, Qf::template fn, Qr::template fn>;
1247
1248 // mp_pairwise_fold<L, F>
1249 namespace detail
1250 {
1251
1252 template<class L, class Q> using mp_pairwise_fold_impl = mp_transform_q<Q, mp_pop_back<L>, mp_pop_front<L>>;
1253
1254 } // namespace detail
1255
1256 template<class L, class Q> using mp_pairwise_fold_q = mp_eval_if<mp_empty<L>, mp_clear<L>, detail::mp_pairwise_fold_impl, L, Q>;
1257 template<class L, template<class...> class F> using mp_pairwise_fold = mp_pairwise_fold_q<L, mp_quote<F>>;
1258
1259 // mp_sliding_fold<L, N, F>
1260 namespace detail
1261 {
1262
1263 template<class C, class L, class Q, class S> struct mp_sliding_fold_impl;
1264
1265 template<class L, class N, class Q> struct mp_sliding_fold_impl<mp_true, L, N, Q>
1266 {
1267     static const std::size_t M = mp_size<L>::value - N::value + 1;
1268
1269     template<class I> using F = mp_slice_c<L, I::value, I::value + M>;
1270
1271     using J = mp_transform<F, mp_iota<N>>;
1272
1273     using type = mp_apply<mp_transform_q, mp_push_front<J, Q>>;
1274 };
1275
1276 template<class L, class N, class Q> struct mp_sliding_fold_impl<mp_false, L, N, Q>
1277 {
1278     using type = mp_clear<L>;
1279 };
1280
1281 } // namespace detail
1282
1283 template<class L, class N, class Q> using mp_sliding_fold_q = typename detail::mp_sliding_fold_impl<mp_bool<(mp_size<L>::value >= N::value)>, L, N, Q>::type;
1284 template<class L, class N, template<class...> class F> using mp_sliding_fold = mp_sliding_fold_q<L, N, mp_quote<F>>;
1285
1286 // mp_intersperse<L, S>
1287 namespace detail
1288 {
1289
1290 template<class L, class S> struct mp_intersperse_impl
1291 {
1292 };
1293
1294 #if BOOST_MP11_WORKAROUND( BOOST_MP11_MSVC, <= 1800 )
1295
1296 template<template<class...> class L, class... T, class S> struct mp_intersperse_impl<L<T...>, S>
1297 {
1298     static_assert( sizeof...(T) == 0, "T... must be empty" );
1299     using type = L<>;
1300 };
1301
1302 #else
1303
1304 template<template<class...> class L, class S> struct mp_intersperse_impl<L<>, S>
1305 {
1306     using type = L<>;
1307 };
1308
1309 #endif
1310
1311 template<template<class...> class L, class T1, class... T, class S> struct mp_intersperse_impl<L<T1, T...>, S>
1312 {
1313     using type = mp_append<L<T1>, L<S, T>...>;
1314 };
1315
1316 } // namespace detail
1317
1318 template<class L, class S> using mp_intersperse = typename detail::mp_intersperse_impl<L, S>::type;
1319
1320 // mp_split<L, S>
1321 namespace detail
1322 {
1323
1324 template<class L, class S, class J> struct mp_split_impl;
1325
1326 } // namespace detail
1327
1328 template<class L, class S> using mp_split = typename detail::mp_split_impl<L, S, mp_find<L, S>>::type;
1329
1330 namespace detail
1331 {
1332
1333 template<class L, class S, class J> using mp_split_impl_ = mp_push_front<mp_split<mp_drop_c<L, J::value + 1>, S>, mp_take<L, J>>;
1334
1335 template<class L, class S, class J> struct mp_split_impl
1336 {
1337     using type = mp_eval_if_c<mp_size<L>::value == J::value, mp_push_back<mp_clear<L>, L>, mp_split_impl_, L, S, J>;
1338 };
1339
1340 } // namespace detail
1341
1342 // mp_join<L, S>
1343
1344 template<class L, class S> using mp_join = mp_apply<mp_append, mp_intersperse<L, mp_list<S>>>;
1345
1346 } // namespace mp11
1347 } // namespace boost
1348
1349 #if defined(_MSC_VER) || defined(__GNUC__)
1350 # pragma pop_macro( "I" )
1351 #endif
1352
1353 #endif // #ifndef BOOST_MP11_ALGORITHM_HPP_INCLUDED