math/tools/mp.hpp

0001 //  Copyright Peter Dimov 2015-2021.
0002 //  Copyright Matt Borland 2021.
0003 //  Use, modification and distribution are subject to the
0004 //  Boost Software License, Version 1.0. (See accompanying file
0005 //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0006 //
0007 //  Template metaprogramming classes and functions to replace MPL
0008 //  Source: http://www.pdimov.com/cpp2/simple_cxx11_metaprogramming.html
0009 //  Source: https://github.com/boostorg/mp11/
0010
0011 #ifndef BOOST_MATH_TOOLS_MP
0012 #define BOOST_MATH_TOOLS_MP
0013
0014 #include <type_traits>
0015 #include <cstddef>
0016 #include <utility>
0017
0018 namespace boost { namespace math { namespace tools { namespace meta_programming {
0019
0020 // Types:
0021 // Typelist
0022 template<typename... T>
0023 struct mp_list {};
0024
0025 // Size_t
0026 template<std::size_t N>
0027 using mp_size_t = std::integral_constant<std::size_t, N>;
0028
0029 // Boolean
0030 template<bool B>
0031 using mp_bool = std::integral_constant<bool, B>;
0032
0033 // Identity
0034 template<typename T>
0035 struct mp_identity
0036 {
0037     using type = T;
0038 };
0039
0040 // Turns struct into quoted metafunction
0041 template<template<typename...> class F>
0042 struct mp_quote_trait
0043 {
0044     template<typename... T>
0045     using fn = typename F<T...>::type;
0046 };
0047
0048 namespace detail {
0049 // Size
0050 template<typename L>
0051 struct mp_size_impl {};
0052
0053 template<template<typename...> class L, typename... T> // Template template parameter must use class
0054 struct mp_size_impl<L<T...>>
0055 {
0056     using type = std::integral_constant<std::size_t, sizeof...(T)>;
0057 };
0058 }
0059
0060 template<typename T>
0061 using mp_size = typename detail::mp_size_impl<T>::type;
0062
0063 namespace detail {
0064 // Front
0065 template<typename L>
0066 struct mp_front_impl {};
0067
0068 template<template<typename...> class L, typename T1, typename... T>
0069 struct mp_front_impl<L<T1, T...>>
0070 {
0071     using type = T1;
0072 };
0073 }
0074
0075 template<typename T>
0076 using mp_front = typename detail::mp_front_impl<T>::type;
0077
0078 namespace detail {
0079 // At
0080 // TODO - Use tree based lookup for larger typelists
0081 // http://odinthenerd.blogspot.com/2017/04/tree-based-lookup-why-kvasirmpl-is.html
0082 template<typename L, std::size_t>
0083 struct mp_at_c {};
0084
0085 template<template<typename...> class L, typename T0, typename... T>
0086 struct mp_at_c<L<T0, T...>, 0>
0087 {
0088     using type = T0;
0089 };
0090
0091 template<template<typename...> class L, typename T0, typename T1, typename... T>
0092 struct mp_at_c<L<T0, T1, T...>, 1>
0093 {
0094     using type = T1;
0095 };
0096
0097 template<template<typename...> class L, typename T0, typename T1, typename T2, typename... T>
0098 struct mp_at_c<L<T0, T1, T2, T...>, 2>
0099 {
0100     using type = T2;
0101 };
0102
0103 template<template<typename...> class L, typename T0, typename T1, typename T2, typename T3, typename... T>
0104 struct mp_at_c<L<T0, T1, T2, T3, T...>, 3>
0105 {
0106     using type = T3;
0107 };
0108
0109 template<template<typename...> class L, typename T0, typename T1, typename T2, typename T3, typename T4, typename... T>
0110 struct mp_at_c<L<T0, T1, T2, T3, T4, T...>, 4>
0111 {
0112     using type = T4;
0113 };
0114
0115 template<template<typename...> class L, typename T0, typename T1, typename T2, typename T3, typename T4, typename T5, typename... T>
0116 struct mp_at_c<L<T0, T1, T2, T3, T4, T5, T...>, 5>
0117 {
0118     using type = T5;
0119 };
0120
0121 template<template<typename...> class L, typename T0, typename T1, typename T2, typename T3, typename T4, typename T5, typename T6,
0122          typename... T>
0123 struct mp_at_c<L<T0, T1, T2, T3, T4, T5, T6, T...>, 6>
0124 {
0125     using type = T6;
0126 };
0127
0128 template<template<typename...> class L, typename T0, typename T1, typename T2, typename T3, typename T4, typename T5, typename T6,
0129          typename T7, typename... T>
0130 struct mp_at_c<L<T0, T1, T2, T3, T4, T5, T6, T7, T...>, 7>
0131 {
0132     using type = T7;
0133 };
0134
0135 template<template<typename...> class L, typename T0, typename T1, typename T2, typename T3, typename T4, typename T5, typename T6,
0136          typename T7, typename T8, typename... T>
0137 struct mp_at_c<L<T0, T1, T2, T3, T4, T5, T6, T7, T8, T...>, 8>
0138 {
0139     using type = T8;
0140 };
0141
0142 template<template<typename...> class L, typename T0, typename T1, typename T2, typename T3, typename T4, typename T5, typename T6,
0143          typename T7, typename T8, typename T9, typename... T>
0144 struct mp_at_c<L<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9, T...>, 9>
0145 {
0146     using type = T9;
0147 };
0148
0149 template<template<typename...> class L, typename T0, typename T1, typename T2, typename T3, typename T4, typename T5, typename T6,
0150          typename T7, typename T8, typename T9, typename T10, typename... T>
0151 struct mp_at_c<L<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T...>, 10>
0152 {
0153     using type = T10;
0154 };
0155
0156 template<template<typename...> class L, typename T0, typename T1, typename T2, typename T3, typename T4, typename T5, typename T6,
0157          typename T7, typename T8, typename T9, typename T10, typename T11, typename... T>
0158 struct mp_at_c<L<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T...>, 11>
0159 {
0160     using type = T11;
0161 };
0162
0163 template<template<typename...> class L, typename T0, typename T1, typename T2, typename T3, typename T4, typename T5, typename T6,
0164          typename T7, typename T8, typename T9, typename T10, typename T11, typename T12, typename... T>
0165 struct mp_at_c<L<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T...>, 12>
0166 {
0167     using type = T12;
0168 };
0169 }
0170
0171 template<typename L, std::size_t I>
0172 using mp_at_c = typename detail::mp_at_c<L, I>::type;
0173
0174 template<typename L, typename I>
0175 using mp_at = typename detail::mp_at_c<L, I::value>::type;
0176
0177 // Back
0178 template<typename L>
0179 using mp_back = mp_at_c<L, mp_size<L>::value - 1>;
0180
0181 namespace detail {
0182 // Push back
0183 template<typename L, typename... T>
0184 struct mp_push_back_impl {};
0185
0186 template<template<typename...> class L, typename... U, typename... T>
0187 struct mp_push_back_impl<L<U...>, T...>
0188 {
0189     using type = L<U..., T...>;
0190 };
0191 }
0192
0193 template<typename L, typename... T>
0194 using mp_push_back = typename detail::mp_push_back_impl<L, T...>::type;
0195
0196 namespace detail {
0197 // Push front
0198 template<typename L, typename... T>
0199 struct mp_push_front_impl {};
0200
0201 template<template<typename...> class L, typename... U, typename... T>
0202 struct mp_push_front_impl<L<U...>, T...>
0203 {
0204     using type = L<T..., U...>;
0205 };
0206 }
0207
0208 template<typename L, typename... T>
0209 using mp_push_front = typename detail::mp_push_front_impl<L, T...>::type;
0210
0211 namespace detail{
0212 // If
0213 template<bool C, typename T, typename... E>
0214 struct mp_if_c_impl{};
0215
0216 template<typename T, typename... E>
0217 struct mp_if_c_impl<true, T, E...>
0218 {
0219     using type = T;
0220 };
0221
0222 template<typename T, typename E>
0223 struct mp_if_c_impl<false, T, E>
0224 {
0225     using type = E;
0226 };
0227 }
0228
0229 template<bool C, typename T, typename... E>
0230 using mp_if_c = typename detail::mp_if_c_impl<C, T, E...>::type;
0231
0232 template<typename C, typename T, typename... E>
0233 using mp_if = typename detail::mp_if_c_impl<static_cast<bool>(C::value), T, E...>::type;
0234
0235 namespace detail {
0236 // Find if
0237 template<typename L, template<typename...> class P>
0238 struct mp_find_if_impl {};
0239
0240 template<template<typename...> class L, template<typename...> class P>
0241 struct mp_find_if_impl<L<>, P>
0242 {
0243     using type = mp_size_t<0>;
0244 };
0245
0246 template<typename L, template<typename...> class P>
0247 struct mp_find_if_impl_2
0248 {
0249     using r = typename mp_find_if_impl<L, P>::type;
0250     using type = mp_size_t<1 + r::value>;
0251 };
0252
0253 template<template<typename...> class L, typename T1, typename... T, template<typename...> class P>
0254 struct mp_find_if_impl<L<T1, T...>, P>
0255 {
0256     using type = typename mp_if<P<T1>, mp_identity<mp_size_t<0>>, mp_find_if_impl_2<mp_list<T...>, P>>::type;
0257 };
0258 }
0259
0260 template<typename L, template<typename...> class P>
0261 using mp_find_if = typename detail::mp_find_if_impl<L, P>::type;
0262
0263 template<typename L, typename Q>
0264 using mp_find_if_q = mp_find_if<L, Q::template fn>;
0265
0266 namespace detail {
0267 // Append
0268 template<typename... L>
0269 struct mp_append_impl {};
0270
0271 template<>
0272 struct mp_append_impl<>
0273 {
0274     using type = mp_list<>;
0275 };
0276
0277 template<template<typename...> class L, typename... T>
0278 struct mp_append_impl<L<T...>>
0279 {
0280     using type = L<T...>;
0281 };
0282
0283 template<template<typename...> class L1, typename... T1, template<typename...> class L2, typename... T2>
0284 struct mp_append_impl<L1<T1...>, L2<T2...>>
0285 {
0286     using type = L1<T1..., T2...>;
0287 };
0288
0289 template<template<typename...> class L1, typename... T1, template<typename...> class L2, typename... T2,
0290          template<typename...> class L3, typename... T3>
0291 struct mp_append_impl<L1<T1...>, L2<T2...>, L3<T3...>>
0292 {
0293     using type = L1<T1..., T2..., T3...>;
0294 };
0295
0296 template<template<typename...> class L1, typename... T1, template<typename...> class L2, typename... T2,
0297          template<typename...> class L3, typename... T3, template<typename...> class L4, typename... T4>
0298 struct mp_append_impl<L1<T1...>, L2<T2...>, L3<T3...>, L4<T4...>>
0299 {
0300     using type = L1<T1..., T2..., T3..., T4...>;
0301 };
0302
0303 template<template<typename...> class L1, typename... T1, template<typename...> class L2, typename... T2,
0304          template<typename...> class L3, typename... T3, template<typename...> class L4, typename... T4,
0305          template<typename...> class L5, typename... T5, typename... Lr>
0306 struct mp_append_impl<L1<T1...>, L2<T2...>, L3<T3...>, L4<T4...>, L5<T5...>, Lr...>
0307 {
0308     using type = typename mp_append_impl<L1<T1..., T2..., T3..., T4..., T5...>, Lr...>::type;
0309 };
0310 }
0311
0312 template<typename... L>
0313 using mp_append = typename detail::mp_append_impl<L...>::type;
0314
0315 namespace detail {
0316 // Remove if
0317 template<typename L, template<typename...> class P>
0318 struct mp_remove_if_impl{};
0319
0320 template<template<typename...> class L, typename... T, template<typename...> class P>
0321 struct mp_remove_if_impl<L<T...>, P>
0322 {
0323     template<typename U>
0324     struct _f
0325     {
0326         using type = mp_if<P<U>, mp_list<>, mp_list<U>>;
0327     };
0328
0329     using type = mp_append<L<>, typename _f<T>::type...>;
0330 };
0331 }
0332
0333 template<typename L, template<class...> class P>
0334 using mp_remove_if = typename detail::mp_remove_if_impl<L, P>::type;
0335
0336 template<typename L, typename Q>
0337 using mp_remove_if_q = mp_remove_if<L, Q::template fn>;
0338
0339 // Index sequence
0340 // Use C++14 index sequence if available
0341 #if defined(__cpp_lib_integer_sequence) && (__cpp_lib_integer_sequence >= 201304)
0342 template<std::size_t... I>
0343 using index_sequence = std::index_sequence<I...>;
0344
0345 template<std::size_t N>
0346 using make_index_sequence = std::make_index_sequence<N>;
0347
0348 template<typename... T>
0349 using index_sequence_for = std::index_sequence_for<T...>;
0350
0351 #else
0352
0353 template<typename T, T... I>
0354 struct integer_sequence {};
0355
0356 template<std::size_t... I>
0357 using index_sequence = integer_sequence<std::size_t, I...>;
0358
0359 namespace detail {
0360
0361 template<bool C, typename T, typename E>
0362 struct iseq_if_c_impl {};
0363
0364 template<typename T, typename F>
0365 struct iseq_if_c_impl<true, T, F>
0366 {
0367     using type = T;
0368 };
0369
0370 template<typename T, typename F>
0371 struct iseq_if_c_impl<false, T, F>
0372 {
0373     using type = F;
0374 };
0375
0376 template<bool C, typename T, typename F>
0377 using iseq_if_c = typename iseq_if_c_impl<C, T, F>::type;
0378
0379 template<typename T>
0380 struct iseq_identity
0381 {
0382     using type = T;
0383 };
0384
0385 template<typename T1, typename T2>
0386 struct append_integer_sequence {};
0387
0388 template<typename T, T... I, T... J>
0389 struct append_integer_sequence<integer_sequence<T, I...>, integer_sequence<T, J...>>
0390 {
0391     using type = integer_sequence<T, I..., (J + sizeof...(I))...>;
0392 };
0393
0394 template<typename T, T N>
0395 struct make_integer_sequence_impl;
0396
0397 template<typename T, T N>
0398 class make_integer_sequence_impl_
0399 {
0400 private:
0401     static_assert(N >= 0, "N must not be negative");
0402
0403     static constexpr T M = N / 2;
0404     static constexpr T R = N % 2;
0405
0406     using seq1 = typename make_integer_sequence_impl<T, M>::type;
0407     using seq2 = typename append_integer_sequence<seq1, seq1>::type;
0408     using seq3 = typename make_integer_sequence_impl<T, R>::type;
0409     using seq4 = typename append_integer_sequence<seq2, seq3>::type;
0410
0411 public:
0412     using type = seq4;
0413 };
0414
0415 template<typename T, T N>
0416 struct make_integer_sequence_impl
0417 {
0418     using type = typename iseq_if_c<N == 0,
0419                                     iseq_identity<integer_sequence<T>>,
0420                                     iseq_if_c<N == 1, iseq_identity<integer_sequence<T, 0>>,
0421                                     make_integer_sequence_impl_<T, N>>>::type;
0422 };
0423
0424 } // namespace detail
0425
0426 template<typename T, T N>
0427 using make_integer_sequence = typename detail::make_integer_sequence_impl<T, N>::type;
0428
0429 template<std::size_t N>
0430 using make_index_sequence = make_integer_sequence<std::size_t, N>;
0431
0432 template<typename... T>
0433 using index_sequence_for = make_integer_sequence<std::size_t, sizeof...(T)>;
0434
0435 #endif
0436
0437 }}}} // namespaces
0438
0439 #endif // BOOST_MATH_TOOLS_MP