ceph/src/boost/boost/mp11/algorithm.hpp

   1 #ifndef BOOST_MP11_ALGORITHM_HPP_INCLUDED
   2 #define BOOST_MP11_ALGORITHM_HPP_INCLUDED
   3
   4 //  Copyright 2015-2017 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/config.hpp>
  23 #include <boost/mp11/integer_sequence.hpp>
  24 #include <boost/config.hpp>
  25 #include <boost/detail/workaround.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_WORKAROUND( BOOST_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_WORKAROUND( BOOST_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_WORKAROUND( BOOST_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_WORKAROUND( BOOST_MSVC, == 1900 ) || BOOST_WORKAROUND( BOOST_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 } // namespace detail
  99
 100 #if BOOST_WORKAROUND( BOOST_MSVC, == 1900 ) || BOOST_WORKAROUND( BOOST_GCC, < 40800 )
 101
 102 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;
 103
 104 #else
 105
 106 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;
 107
 108 #endif
 109
 110 template<class Q, class... L> using mp_transform_q = mp_transform<Q::template fn, L...>;
 111
 112 namespace detail
 113 {
 114
 115 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...>
 116 {
 117     using A1 = L1<mp_list<T1, T2, T3, T4>...>;
 118
 119     template<class V, class T> using _f = mp_transform<mp_push_back, V, T>;
 120
 121     using A2 = mp_fold<mp_list<L...>, A1, _f>;
 122
 123     template<class T> using _g = mp_apply<F, T>;
 124
 125     using type = mp_transform<_g, A2>;
 126 };
 127
 128 } // namespace detail
 129
 130 // mp_transform_if<P, F, L...>
 131 namespace detail
 132 {
 133
 134 template<template<class...> class P, template<class...> class F, class... L> struct mp_transform_if_impl
 135 {
 136     // the stupid quote-unquote dance avoids "pack expansion used as argument for non-pack parameter of alias template"
 137
 138     using Qp = mp_quote<P>;
 139     using Qf = mp_quote<F>;
 140
 141 #if BOOST_WORKAROUND( BOOST_MSVC, < 1920 )
 142
 143     template<class... U> struct _f_ { using type = mp_eval_if_q<mp_not<mp_invoke<Qp, U...>>, mp_first<mp_list<U...>>, Qf, U...>; };
 144     template<class... U> using _f = typename _f_<U...>::type;
 145
 146 #else
 147
 148     template<class... U> using _f = mp_eval_if_q<mp_not<mp_invoke<Qp, U...>>, mp_first<mp_list<U...>>, Qf, U...>;
 149
 150 #endif
 151
 152     using type = mp_transform<_f, L...>;
 153 };
 154
 155 } // namespace detail
 156
 157 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;
 158 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;
 159
 160 // mp_fill<L, V>
 161 namespace detail
 162 {
 163
 164 template<class L, class V> struct mp_fill_impl;
 165
 166 template<template<class...> class L, class... T, class V> struct mp_fill_impl<L<T...>, V>
 167 {
 168 #if defined( BOOST_MSVC ) && BOOST_WORKAROUND( BOOST_MSVC, <= 1900 )
 169
 170     template<class...> struct _f { using type = V; };
 171     using type = L<typename _f<T>::type...>;
 172
 173 #else
 174
 175     template<class...> using _f = V;
 176     using type = L<_f<T>...>;
 177
 178 #endif
 179 };
 180
 181 } // namespace detail
 182
 183 template<class L, class V> using mp_fill = typename detail::mp_fill_impl<L, V>::type;
 184
 185 // mp_contains<L, V>
 186 template<class L, class V> using mp_contains = mp_to_bool<mp_count<L, V>>;
 187
 188 // mp_repeat(_c)<L, N>
 189 namespace detail
 190 {
 191
 192 template<class L, std::size_t N> struct mp_repeat_c_impl
 193 {
 194     using _l1 = typename mp_repeat_c_impl<L, N/2>::type;
 195     using _l2 = typename mp_repeat_c_impl<L, N%2>::type;
 196
 197     using type = mp_append<_l1, _l1, _l2>;
 198 };
 199
 200 template<class L> struct mp_repeat_c_impl<L, 0>
 201 {
 202     using type = mp_clear<L>;
 203 };
 204
 205 template<class L> struct mp_repeat_c_impl<L, 1>
 206 {
 207     using type = L;
 208 };
 209
 210 } // namespace detail
 211
 212 template<class L, std::size_t N> using mp_repeat_c = typename detail::mp_repeat_c_impl<L, N>::type;
 213 template<class L, class N> using mp_repeat = typename detail::mp_repeat_c_impl<L, std::size_t{ N::value }>::type;
 214
 215 // mp_product<F, L...>
 216 namespace detail
 217 {
 218
 219 template<template<class...> class F, class P, class... L> struct mp_product_impl_2;
 220
 221 template<template<class...> class F, class P> struct mp_product_impl_2<F, P>
 222 {
 223     using type = mp_list<mp_rename<P, F>>;
 224 };
 225
 226 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...>
 227 {
 228     using type = mp_append<typename mp_product_impl_2<F, mp_push_back<P, T1>, L...>::type...>;
 229 };
 230
 231 template<template<class...> class F, class... L> struct mp_product_impl;
 232
 233 template<template<class...> class F, class L1, class... L> struct mp_product_impl<F, L1, L...>
 234 {
 235     using type = mp_assign<L1, typename mp_product_impl_2<F, mp_list<>, L1, L...>::type>;
 236 };
 237
 238 } // namespace detail
 239
 240 template<template<class...> class F, class... L> using mp_product = typename detail::mp_product_impl<F, L...>::type;
 241 template<class Q, class... L> using mp_product_q = typename detail::mp_product_impl<Q::template fn, L...>::type;
 242
 243 // mp_drop(_c)<L, N>
 244 namespace detail
 245 {
 246
 247 template<class L, class L2> struct mp_drop_impl;
 248
 249 template<template<class...> class L, class... T, template<class...> class L2, class... U> struct mp_drop_impl<L<T...>, L2<U...>>
 250 {
 251     template<class... W> static mp_identity<L<W...>> f( U*..., mp_identity<W>*... );
 252
 253     using R = decltype( f( (mp_identity<T>*)0 ... ) );
 254
 255     using type = typename R::type;
 256 };
 257
 258 } // namespace detail
 259
 260 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;
 261
 262 template<class L, class N> using mp_drop = typename detail::mp_drop_impl<L, mp_repeat<mp_list<void>, N>>::type;
 263
 264 // mp_from_sequence<S>
 265 namespace detail
 266 {
 267
 268 template<class S> struct mp_from_sequence_impl;
 269
 270 template<template<class T, T... I> class S, class U, U... J> struct mp_from_sequence_impl<S<U, J...>>
 271 {
 272     using type = mp_list<std::integral_constant<U, J>...>;
 273 };
 274
 275 } // namespace detail
 276
 277 template<class S> using mp_from_sequence = typename detail::mp_from_sequence_impl<S>::type;
 278
 279 // mp_iota(_c)<N>
 280 template<std::size_t N> using mp_iota_c = mp_from_sequence<make_index_sequence<N>>;
 281 template<class N> using mp_iota = mp_from_sequence<make_integer_sequence<typename std::remove_const<decltype(N::value)>::type, N::value>>;
 282
 283 // mp_at(_c)<L, I>
 284 namespace detail
 285 {
 286
 287 template<class L, std::size_t I> struct mp_at_c_impl;
 288
 289 #if defined(BOOST_MP11_HAS_TYPE_PACK_ELEMENT)
 290
 291 template<template<class...> class L, class... T, std::size_t I> struct mp_at_c_impl<L<T...>, I>
 292 {
 293     using type = __type_pack_element<I, T...>;
 294 };
 295
 296 #else
 297
 298 template<class L, std::size_t I> struct mp_at_c_impl
 299 {
 300     using _map = mp_transform<mp_list, mp_iota<mp_size<L>>, L>;
 301     using type = mp_second<mp_map_find<_map, mp_size_t<I>>>;
 302 };
 303
 304 #endif
 305
 306 } // namespace detail
 307
 308 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;
 309 template<class L, class I> using mp_at = mp_at_c<L, std::size_t{ I::value }>;
 310
 311 // mp_take(_c)<L, N>
 312 namespace detail
 313 {
 314
 315 template<class L, std::size_t N, class E = void> struct mp_take_c_impl;
 316
 317 template<template<class...> class L, class... T> struct mp_take_c_impl<L<T...>, 0>
 318 {
 319     using type = L<>;
 320 };
 321
 322 template<template<class...> class L, class T1, class... T> struct mp_take_c_impl<L<T1, T...>, 1>
 323 {
 324     using type = L<T1>;
 325 };
 326
 327 template<template<class...> class L, class T1, class T2, class... T> struct mp_take_c_impl<L<T1, T2, T...>, 2>
 328 {
 329     using type = L<T1, T2>;
 330 };
 331
 332 template<template<class...> class L, class T1, class T2, class T3, class... T> struct mp_take_c_impl<L<T1, T2, T3, T...>, 3>
 333 {
 334     using type = L<T1, T2, T3>;
 335 };
 336
 337 template<template<class...> class L, class T1, class T2, class T3, class T4, class... T> struct mp_take_c_impl<L<T1, T2, T3, T4, T...>, 4>
 338 {
 339     using type = L<T1, T2, T3, T4>;
 340 };
 341
 342 template<template<class...> class L, class T1, class T2, class T3, class T4, class T5, class... T, std::size_t N> struct mp_take_c_impl<L<T1, T2, T3, T4, T5, T...>, N, typename std::enable_if<N >= 5>::type>
 343 {
 344     using type = mp_append<L<T1, T2, T3, T4, T5>, typename mp_take_c_impl<L<T...>, N-5>::type>;
 345 };
 346
 347 } // namespace detail
 348
 349 template<class L, std::size_t N> using mp_take_c = typename detail::mp_take_c_impl<L, N>::type;
 350 template<class L, class N> using mp_take = typename detail::mp_take_c_impl<L, std::size_t{ N::value }>::type;
 351
 352 // mp_replace<L, V, W>
 353 namespace detail
 354 {
 355
 356 template<class L, class V, class W> struct mp_replace_impl;
 357
 358 template<template<class...> class L, class... T, class V, class W> struct mp_replace_impl<L<T...>, V, W>
 359 {
 360 #if defined( BOOST_MSVC ) && BOOST_WORKAROUND( BOOST_MSVC, <= 1800 )
 361     template<class A> struct _f { using type = mp_if<std::is_same<A, V>, W, A>; };
 362     using type = L<typename _f<T>::type...>;
 363 #else
 364     template<class A> using _f = mp_if<std::is_same<A, V>, W, A>;
 365     using type = L<_f<T>...>;
 366 #endif
 367 };
 368
 369 } // namespace detail
 370
 371 template<class L, class V, class W> using mp_replace = typename detail::mp_replace_impl<L, V, W>::type;
 372
 373 // mp_replace_if<L, P, W>
 374 namespace detail
 375 {
 376
 377 template<class L, template<class...> class P, class W> struct mp_replace_if_impl;
 378
 379 template<template<class...> class L, class... T, template<class...> class P, class W> struct mp_replace_if_impl<L<T...>, P, W>
 380 {
 381 #if defined( BOOST_MSVC ) && BOOST_WORKAROUND( BOOST_MSVC, < 1920 )
 382     template<class U> struct _f { using type = mp_if<P<U>, W, U>; };
 383     using type = L<typename _f<T>::type...>;
 384 #else
 385     template<class U> using _f = mp_if<P<U>, W, U>;
 386     using type = L<_f<T>...>;
 387 #endif
 388 };
 389
 390 } // namespace detail
 391
 392 template<class L, template<class...> class P, class W> using mp_replace_if = typename detail::mp_replace_if_impl<L, P, W>::type;
 393 template<class L, class Q, class W> using mp_replace_if_q = mp_replace_if<L, Q::template fn, W>;
 394
 395 // mp_copy_if<L, P>
 396 namespace detail
 397 {
 398
 399 template<class L, template<class...> class P> struct mp_copy_if_impl;
 400
 401 template<template<class...> class L, class... T, template<class...> class P> struct mp_copy_if_impl<L<T...>, P>
 402 {
 403 #if defined( BOOST_MSVC ) && BOOST_WORKAROUND( BOOST_MSVC, < 1920 )
 404     template<class U> struct _f { using type = mp_if<P<U>, mp_list<U>, mp_list<>>; };
 405     using type = mp_append<L<>, typename _f<T>::type...>;
 406 #else
 407     template<class U> using _f = mp_if<P<U>, mp_list<U>, mp_list<>>;
 408     using type = mp_append<L<>, _f<T>...>;
 409 #endif
 410 };
 411
 412 } // namespace detail
 413
 414 template<class L, template<class...> class P> using mp_copy_if = typename detail::mp_copy_if_impl<L, P>::type;
 415 template<class L, class Q> using mp_copy_if_q = mp_copy_if<L, Q::template fn>;
 416
 417 // mp_remove<L, V>
 418 namespace detail
 419 {
 420
 421 template<class L, class V> struct mp_remove_impl;
 422
 423 template<template<class...> class L, class... T, class V> struct mp_remove_impl<L<T...>, V>
 424 {
 425 #if defined( BOOST_MSVC ) && BOOST_WORKAROUND( BOOST_MSVC, < 1920 )
 426     template<class U> struct _f { using type = mp_if<std::is_same<U, V>, mp_list<>, mp_list<U>>; };
 427     using type = mp_append<L<>, typename _f<T>::type...>;
 428 #else
 429     template<class U> using _f = mp_if<std::is_same<U, V>, mp_list<>, mp_list<U>>;
 430     using type = mp_append<L<>, _f<T>...>;
 431 #endif
 432 };
 433
 434 } // namespace detail
 435
 436 template<class L, class V> using mp_remove = typename detail::mp_remove_impl<L, V>::type;
 437
 438 // mp_remove_if<L, P>
 439 namespace detail
 440 {
 441
 442 template<class L, template<class...> class P> struct mp_remove_if_impl;
 443
 444 template<template<class...> class L, class... T, template<class...> class P> struct mp_remove_if_impl<L<T...>, P>
 445 {
 446 #if defined( BOOST_MSVC ) && BOOST_WORKAROUND( BOOST_MSVC, < 1920 )
 447     template<class U> struct _f { using type = mp_if<P<U>, mp_list<>, mp_list<U>>; };
 448     using type = mp_append<L<>, typename _f<T>::type...>;
 449 #else
 450     template<class U> using _f = mp_if<P<U>, mp_list<>, mp_list<U>>;
 451     using type = mp_append<L<>, _f<T>...>;
 452 #endif
 453 };
 454
 455 } // namespace detail
 456
 457 template<class L, template<class...> class P> using mp_remove_if = typename detail::mp_remove_if_impl<L, P>::type;
 458 template<class L, class Q> using mp_remove_if_q = mp_remove_if<L, Q::template fn>;
 459
 460 // mp_partition<L, P>
 461 namespace detail
 462 {
 463
 464 template<class L, template<class...> class P> struct mp_partition_impl;
 465
 466 template<template<class...> class L, class... T, template<class...> class P> struct mp_partition_impl<L<T...>, P>
 467 {
 468     using type = L<mp_copy_if<L<T...>, P>, mp_remove_if<L<T...>, P>>;
 469 };
 470
 471 } // namespace detail
 472
 473 template<class L, template<class...> class P> using mp_partition = typename detail::mp_partition_impl<L, P>::type;
 474 template<class L, class Q> using mp_partition_q = mp_partition<L, Q::template fn>;
 475
 476 // mp_sort<L, P>
 477 namespace detail
 478 {
 479
 480 template<class L, template<class...> class P> struct mp_sort_impl;
 481
 482 #if defined( BOOST_MSVC ) && BOOST_WORKAROUND( BOOST_MSVC, <= 1800 )
 483
 484 template<template<class...> class L, class... T, template<class...> class P> struct mp_sort_impl<L<T...>, P>
 485 {
 486     static_assert( sizeof...(T) == 0, "T... must be empty" );
 487     using type = L<>;
 488 };
 489
 490 #else
 491
 492 template<template<class...> class L, template<class...> class P> struct mp_sort_impl<L<>, P>
 493 {
 494     using type = L<>;
 495 };
 496
 497 #endif
 498
 499 template<template<class...> class L, class T1, template<class...> class P> struct mp_sort_impl<L<T1>, P>
 500 {
 501     using type = L<T1>;
 502 };
 503
 504 template<template<class...> class L, class T1, class... T, template<class...> class P> struct mp_sort_impl<L<T1, T...>, P>
 505 {
 506     template<class U> using F = P<U, T1>;
 507
 508     using part = mp_partition<L<T...>, F>;
 509
 510     using S1 = typename mp_sort_impl<mp_first<part>, P>::type;
 511     using S2 = typename mp_sort_impl<mp_second<part>, P>::type;
 512
 513     using type = mp_append<mp_push_back<S1, T1>, S2>;
 514 };
 515
 516 } // namespace detail
 517
 518 template<class L, template<class...> class P> using mp_sort = typename detail::mp_sort_impl<L, P>::type;
 519 template<class L, class Q> using mp_sort_q = mp_sort<L, Q::template fn>;
 520
 521 // mp_nth_element(_c)<L, I, P>
 522 namespace detail
 523 {
 524
 525 template<class L, std::size_t I, template<class...> class P> struct mp_nth_element_impl;
 526
 527 template<template<class...> class L, class T1, std::size_t I, template<class...> class P> struct mp_nth_element_impl<L<T1>, I, P>
 528 {
 529     static_assert( I == 0, "mp_nth_element index out of range" );
 530     using type = T1;
 531 };
 532
 533 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>
 534 {
 535     static_assert( I < 1 + sizeof...(T), "mp_nth_element index out of range" );
 536
 537     template<class U> using F = P<U, T1>;
 538
 539     using part = mp_partition<L<T...>, F>;
 540
 541     using L1 = mp_first<part>;
 542     static std::size_t const N1 = mp_size<L1>::value;
 543
 544     using L2 = mp_second<part>;
 545
 546     using type = typename mp_cond<
 547
 548         mp_bool<(I < N1)>, mp_nth_element_impl<L1, I, P>,
 549         mp_bool<(I == N1)>, mp_identity<T1>,
 550         mp_true, mp_nth_element_impl<L2, I - N1 - 1, P>
 551
 552     >::type;
 553 };
 554
 555 } // namespace detail
 556
 557 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;
 558 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;
 559 template<class L, class I, class Q> using mp_nth_element_q = mp_nth_element<L, I, Q::template fn>;
 560
 561 // mp_find<L, V>
 562 namespace detail
 563 {
 564
 565 template<class L, class V> struct mp_find_impl;
 566
 567 #if defined( BOOST_CLANG ) && defined( BOOST_MP11_HAS_FOLD_EXPRESSIONS )
 568
 569 struct mp_index_holder
 570 {
 571     std::size_t i_;
 572     bool f_;
 573 };
 574
 575 constexpr inline mp_index_holder operator+( mp_index_holder const & v, bool f )
 576 {
 577     if( v.f_ )
 578     {
 579         return v;
 580     }
 581     else if( f )
 582     {
 583         return { v.i_, true };
 584     }
 585     else
 586     {
 587         return { v.i_ + 1, false };
 588     }
 589 }
 590
 591 template<template<class...> class L, class... T, class V> struct mp_find_impl<L<T...>, V>
 592 {
 593     static constexpr mp_index_holder _v{ 0, false };
 594     using type = mp_size_t< (_v + ... + std::is_same<T, V>::value).i_ >;
 595 };
 596
 597 #elif !defined( BOOST_MP11_NO_CONSTEXPR )
 598
 599 template<template<class...> class L, class V> struct mp_find_impl<L<>, V>
 600 {
 601     using type = mp_size_t<0>;
 602 };
 603
 604 #if !defined( BOOST_NO_CXX14_CONSTEXPR )
 605
 606 constexpr std::size_t cx_find_index( bool const * first, bool const * last )
 607 {
 608     std::size_t m = 0;
 609
 610     while( first != last && !*first )
 611     {
 612         ++m;
 613         ++first;
 614     }
 615
 616     return m;
 617 }
 618
 619 #else
 620
 621 constexpr std::size_t cx_find_index( bool const * first, bool const * last )
 622 {
 623     return first == last || *first? 0: 1 + cx_find_index( first + 1, last );
 624 }
 625
 626 #endif
 627
 628 template<template<class...> class L, class... T, class V> struct mp_find_impl<L<T...>, V>
 629 {
 630     static constexpr bool _v[] = { std::is_same<T, V>::value... };
 631     using type = mp_size_t< cx_find_index( _v, _v + sizeof...(T) ) >;
 632 };
 633
 634 #else
 635
 636 #if defined( BOOST_MSVC ) && BOOST_WORKAROUND( BOOST_MSVC, <= 1800 )
 637
 638 template<template<class...> class L, class... T, class V> struct mp_find_impl<L<T...>, V>
 639 {
 640     static_assert( sizeof...(T) == 0, "T... must be empty" );
 641     using type = mp_size_t<0>;
 642 };
 643
 644 #else
 645
 646 template<template<class...> class L, class V> struct mp_find_impl<L<>, V>
 647 {
 648     using type = mp_size_t<0>;
 649 };
 650
 651 #endif
 652
 653 template<template<class...> class L, class... T, class V> struct mp_find_impl<L<V, T...>, V>
 654 {
 655     using type = mp_size_t<0>;
 656 };
 657
 658 template<template<class...> class L, class T1, class... T, class V> struct mp_find_impl<L<T1, T...>, V>
 659 {
 660     using _r = typename mp_find_impl<mp_list<T...>, V>::type;
 661     using type = mp_size_t<1 + _r::value>;
 662 };
 663
 664 #endif
 665
 666 } // namespace detail
 667
 668 template<class L, class V> using mp_find = typename detail::mp_find_impl<L, V>::type;
 669
 670 // mp_find_if<L, P>
 671 namespace detail
 672 {
 673
 674 template<class L, template<class...> class P> struct mp_find_if_impl;
 675
 676 #if defined( BOOST_CLANG ) && defined( BOOST_MP11_HAS_FOLD_EXPRESSIONS )
 677
 678 template<template<class...> class L, class... T, template<class...> class P> struct mp_find_if_impl<L<T...>, P>
 679 {
 680     static constexpr mp_index_holder _v{ 0, false };
 681     using type = mp_size_t< (_v + ... + P<T>::value).i_ >;
 682 };
 683
 684 #elif !defined( BOOST_MP11_NO_CONSTEXPR )
 685
 686 template<template<class...> class L, template<class...> class P> struct mp_find_if_impl<L<>, P>
 687 {
 688     using type = mp_size_t<0>;
 689 };
 690
 691 template<template<class...> class L, class... T, template<class...> class P> struct mp_find_if_impl<L<T...>, P>
 692 {
 693     static constexpr bool _v[] = { P<T>::value... };
 694     using type = mp_size_t< cx_find_index( _v, _v + sizeof...(T) ) >;
 695 };
 696
 697 #else
 698
 699 #if defined( BOOST_MSVC ) && BOOST_WORKAROUND( BOOST_MSVC, <= 1800 )
 700
 701 template<template<class...> class L, class... T, template<class...> class P> struct mp_find_if_impl<L<T...>, P>
 702 {
 703     static_assert( sizeof...(T) == 0, "T... must be empty" );
 704     using type = mp_size_t<0>;
 705 };
 706
 707 #else
 708
 709 template<template<class...> class L, template<class...> class P> struct mp_find_if_impl<L<>, P>
 710 {
 711     using type = mp_size_t<0>;
 712 };
 713
 714 #endif
 715
 716 template<class L, template<class...> class P> struct mp_find_if_impl_2
 717 {
 718     using _r = typename mp_find_if_impl<L, P>::type;
 719     using type = mp_size_t<1 + _r::value>;
 720 };
 721
 722 template<template<class...> class L, class T1, class... T, template<class...> class P> struct mp_find_if_impl<L<T1, T...>, P>
 723 {
 724     using type = typename mp_if<P<T1>, mp_identity<mp_size_t<0>>, mp_find_if_impl_2<mp_list<T...>, P>>::type;
 725 };
 726
 727 #endif
 728
 729 } // namespace detail
 730
 731 template<class L, template<class...> class P> using mp_find_if = typename detail::mp_find_if_impl<L, P>::type;
 732 template<class L, class Q> using mp_find_if_q = mp_find_if<L, Q::template fn>;
 733
 734 // mp_reverse<L>
 735 namespace detail
 736 {
 737
 738 template<class L> struct mp_reverse_impl;
 739
 740 #if defined( BOOST_MSVC ) && BOOST_WORKAROUND( BOOST_MSVC, <= 1800 )
 741
 742 template<template<class...> class L, class... T> struct mp_reverse_impl<L<T...>>
 743 {
 744     static_assert( sizeof...(T) == 0, "T... must be empty" );
 745     using type = L<>;
 746 };
 747
 748 #else
 749
 750 template<template<class...> class L> struct mp_reverse_impl<L<>>
 751 {
 752     using type = L<>;
 753 };
 754
 755 #endif
 756
 757 template<template<class...> class L, class T1> struct mp_reverse_impl<L<T1>>
 758 {
 759     using type = L<T1>;
 760 };
 761
 762 template<template<class...> class L, class T1, class T2> struct mp_reverse_impl<L<T1, T2>>
 763 {
 764     using type = L<T2, T1>;
 765 };
 766
 767 template<template<class...> class L, class T1, class T2, class T3> struct mp_reverse_impl<L<T1, T2, T3>>
 768 {
 769     using type = L<T3, T2, T1>;
 770 };
 771
 772 template<template<class...> class L, class T1, class T2, class T3, class T4> struct mp_reverse_impl<L<T1, T2, T3, T4>>
 773 {
 774     using type = L<T4, T3, T2, T1>;
 775 };
 776
 777 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>>
 778 {
 779     using type = L<T5, T4, T3, T2, T1>;
 780 };
 781
 782 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>>
 783 {
 784     using type = L<T6, T5, T4, T3, T2, T1>;
 785 };
 786
 787 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>>
 788 {
 789     using type = L<T7, T6, T5, T4, T3, T2, T1>;
 790 };
 791
 792 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>>
 793 {
 794     using type = L<T8, T7, T6, T5, T4, T3, T2, T1>;
 795 };
 796
 797 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>>
 798 {
 799     using type = L<T9, T8, T7, T6, T5, T4, T3, T2, T1>;
 800 };
 801
 802 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...>>
 803 {
 804     using type = mp_push_back<typename mp_reverse_impl<L<T...>>::type, T10, T9, T8, T7, T6, T5, T4, T3, T2, T1>;
 805 };
 806
 807 } // namespace detail
 808
 809 template<class L> using mp_reverse = typename detail::mp_reverse_impl<L>::type;
 810
 811 // mp_fold<L, V, F>
 812 //   in detail/mp_fold.hpp
 813
 814 // mp_reverse_fold<L, V, F>
 815 namespace detail
 816 {
 817
 818 template<class L, class V, template<class...> class F> struct mp_reverse_fold_impl;
 819
 820 #if defined( BOOST_MSVC ) && BOOST_WORKAROUND( BOOST_MSVC, <= 1800 )
 821
 822 template<template<class...> class L, class... T, class V, template<class...> class F> struct mp_reverse_fold_impl<L<T...>, V, F>
 823 {
 824     static_assert( sizeof...(T) == 0, "T... must be empty" );
 825     using type = V;
 826 };
 827
 828 #else
 829
 830 template<template<class...> class L, class V, template<class...> class F> struct mp_reverse_fold_impl<L<>, V, F>
 831 {
 832     using type = V;
 833 };
 834
 835 #endif
 836
 837 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>
 838 {
 839     using rest = typename mp_reverse_fold_impl<L<T...>, V, F>::type;
 840     using type = F<T1, rest>;
 841 };
 842
 843 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>
 844 {
 845     using rest = typename mp_reverse_fold_impl<L<T...>, V, F>::type;
 846     using type = F<T1, F<T2, F<T3, F<T4, F<T5, F<T6, F<T7, F<T8, F<T9, F<T10, rest>>>>>>>>>>;
 847 };
 848
 849 } // namespace detail
 850
 851 template<class L, class V, template<class...> class F> using mp_reverse_fold = typename detail::mp_reverse_fold_impl<L, V, F>::type;
 852 template<class L, class V, class Q> using mp_reverse_fold_q = mp_reverse_fold<L, V, Q::template fn>;
 853
 854 // mp_unique<L>
 855 namespace detail
 856 {
 857
 858 template<class L> struct mp_unique_impl;
 859
 860 template<template<class...> class L, class... T> struct mp_unique_impl<L<T...>>
 861 {
 862     using type = mp_set_push_back<L<>, T...>;
 863 };
 864
 865 } // namespace detail
 866
 867 template<class L> using mp_unique = typename detail::mp_unique_impl<L>::type;
 868
 869 // mp_all_of<L, P>
 870 template<class L, template<class...> class P> using mp_all_of = mp_bool< mp_count_if<L, P>::value == mp_size<L>::value >;
 871 template<class L, class Q> using mp_all_of_q = mp_all_of<L, Q::template fn>;
 872
 873 // mp_none_of<L, P>
 874 template<class L, template<class...> class P> using mp_none_of = mp_bool< mp_count_if<L, P>::value == 0 >;
 875 template<class L, class Q> using mp_none_of_q = mp_none_of<L, Q::template fn>;
 876
 877 // mp_any_of<L, P>
 878 template<class L, template<class...> class P> using mp_any_of = mp_bool< mp_count_if<L, P>::value != 0 >;
 879 template<class L, class Q> using mp_any_of_q = mp_any_of<L, Q::template fn>;
 880
 881 // mp_replace_at_c<L, I, W>
 882 namespace detail
 883 {
 884
 885 template<class L, class I, class W> struct mp_replace_at_impl
 886 {
 887     static_assert( I::value >= 0, "mp_replace_at<L, I, W>: I must not be negative" );
 888
 889     template<class T1, class T2> using _p = std::is_same<T2, mp_size_t<I::value>>;
 890     template<class T1, class T2> using _f = W;
 891
 892     using type = mp_transform_if<_p, _f, L, mp_iota<mp_size<L>>>;
 893 };
 894
 895 } // namespace detail
 896
 897 template<class L, class I, class W> using mp_replace_at = typename detail::mp_replace_at_impl<L, I, W>::type;
 898 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;
 899
 900 //mp_for_each<L>(f)
 901 namespace detail
 902 {
 903
 904 template<class... T, class F> BOOST_CONSTEXPR F mp_for_each_impl( mp_list<T...>, F && f )
 905 {
 906     using A = int[sizeof...(T)];
 907     return (void)A{ ((void)f(T()), 0)... }, std::forward<F>(f);
 908 }
 909
 910 #if BOOST_WORKAROUND( BOOST_MSVC, <= 1800 )
 911
 912 template<class F> BOOST_CONSTEXPR F mp_for_each_impl( mp_list<>, F && f )
 913 {
 914     return std::forward<F>(f);
 915 }
 916
 917 #endif
 918
 919 } // namespace detail
 920
 921 template<class L, class F> BOOST_CONSTEXPR F mp_for_each( F && f )
 922 {
 923     return detail::mp_for_each_impl( mp_rename<L, mp_list>(), std::forward<F>(f) );
 924 }
 925
 926 // mp_insert<L, I, T...>
 927 template<class L, class I, class... T> using mp_insert = mp_append<mp_take<L, I>, mp_push_front<mp_drop<L, I>, T...>>;
 928
 929 // mp_insert_c<L, I, T...>
 930 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...>>;
 931
 932 // mp_erase<L, I, J>
 933 template<class L, class I, class J> using mp_erase = mp_append<mp_take<L, I>, mp_drop<L, J>>;
 934
 935 // mp_erase_c<L, I, J>
 936 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>>;
 937
 938 // mp_min_element<L, P>
 939 // mp_max_element<L, P>
 940 //   in detail/mp_min_element.hpp
 941
 942 } // namespace mp11
 943 } // namespace boost
 944
 945 #endif // #ifndef BOOST_MP11_ALGORITHM_HPP_INCLUDED