v1/__algorithm/shuffle.h

0001 //===----------------------------------------------------------------------===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef _LIBCPP___ALGORITHM_SHUFFLE_H
0010 #define _LIBCPP___ALGORITHM_SHUFFLE_H
0011
0012 #include <__algorithm/iterator_operations.h>
0013 #include <__config>
0014 #include <__cstddef/ptrdiff_t.h>
0015 #include <__iterator/iterator_traits.h>
0016 #include <__random/uniform_int_distribution.h>
0017 #include <__utility/forward.h>
0018 #include <__utility/move.h>
0019 #include <__utility/swap.h>
0020 #include <cstdint>
0021
0022 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0023 #  pragma GCC system_header
0024 #endif
0025
0026 _LIBCPP_PUSH_MACROS
0027 #include <__undef_macros>
0028
0029 _LIBCPP_BEGIN_NAMESPACE_STD
0030
0031 class _LIBCPP_EXPORTED_FROM_ABI __libcpp_debug_randomizer {
0032 public:
0033   _LIBCPP_HIDE_FROM_ABI __libcpp_debug_randomizer() {
0034     __state_ = __seed();
0035     __inc_   = __state_ + 0xda3e39cb94b95bdbULL;
0036     __inc_   = (__inc_ << 1) | 1;
0037   }
0038   typedef uint_fast32_t result_type;
0039
0040   static const result_type _Min = 0;
0041   static const result_type _Max = 0xFFFFFFFF;
0042
0043   _LIBCPP_HIDE_FROM_ABI result_type operator()() {
0044     uint_fast64_t __oldstate = __state_;
0045     __state_                 = __oldstate * 6364136223846793005ULL + __inc_;
0046     return __oldstate >> 32;
0047   }
0048
0049   static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR result_type min() { return _Min; }
0050   static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR result_type max() { return _Max; }
0051
0052 private:
0053   uint_fast64_t __state_;
0054   uint_fast64_t __inc_;
0055   _LIBCPP_HIDE_FROM_ABI static uint_fast64_t __seed() {
0056 #ifdef _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY_SEED
0057     return _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY_SEED;
0058 #else
0059     static char __x;
0060     return reinterpret_cast<uintptr_t>(&__x);
0061 #endif
0062   }
0063 };
0064
0065 #if _LIBCPP_STD_VER <= 14 || defined(_LIBCPP_ENABLE_CXX17_REMOVED_RANDOM_SHUFFLE) || defined(_LIBCPP_BUILDING_LIBRARY)
0066 class _LIBCPP_EXPORTED_FROM_ABI __rs_default;
0067
0068 _LIBCPP_EXPORTED_FROM_ABI __rs_default __rs_get();
0069
0070 class _LIBCPP_EXPORTED_FROM_ABI __rs_default {
0071   static unsigned __c_;
0072
0073   __rs_default();
0074
0075 public:
0076   typedef uint_fast32_t result_type;
0077
0078   static const result_type _Min = 0;
0079   static const result_type _Max = 0xFFFFFFFF;
0080
0081   __rs_default(const __rs_default&);
0082   ~__rs_default();
0083
0084   result_type operator()();
0085
0086   static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR result_type min() { return _Min; }
0087   static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR result_type max() { return _Max; }
0088
0089   friend _LIBCPP_EXPORTED_FROM_ABI __rs_default __rs_get();
0090 };
0091
0092 _LIBCPP_EXPORTED_FROM_ABI __rs_default __rs_get();
0093
0094 template <class _RandomAccessIterator>
0095 _LIBCPP_HIDE_FROM_ABI _LIBCPP_DEPRECATED_IN_CXX14 void
0096 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last) {
0097   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
0098   typedef uniform_int_distribution<ptrdiff_t> _Dp;
0099   typedef typename _Dp::param_type _Pp;
0100   difference_type __d = __last - __first;
0101   if (__d > 1) {
0102     _Dp __uid;
0103     __rs_default __g = __rs_get();
0104     for (--__last, (void)--__d; __first < __last; ++__first, (void)--__d) {
0105       difference_type __i = __uid(__g, _Pp(0, __d));
0106       if (__i != difference_type(0))
0107         swap(*__first, *(__first + __i));
0108     }
0109   }
0110 }
0111
0112 template <class _RandomAccessIterator, class _RandomNumberGenerator>
0113 _LIBCPP_HIDE_FROM_ABI _LIBCPP_DEPRECATED_IN_CXX14 void
0114 random_shuffle(_RandomAccessIterator __first,
0115                _RandomAccessIterator __last,
0116 #  ifndef _LIBCPP_CXX03_LANG
0117                _RandomNumberGenerator&& __rand)
0118 #  else
0119                _RandomNumberGenerator& __rand)
0120 #  endif
0121 {
0122   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
0123   difference_type __d = __last - __first;
0124   if (__d > 1) {
0125     for (--__last; __first < __last; ++__first, (void)--__d) {
0126       difference_type __i = __rand(__d);
0127       if (__i != difference_type(0))
0128         swap(*__first, *(__first + __i));
0129     }
0130   }
0131 }
0132 #endif
0133
0134 template <class _AlgPolicy, class _RandomAccessIterator, class _Sentinel, class _UniformRandomNumberGenerator>
0135 _LIBCPP_HIDE_FROM_ABI _RandomAccessIterator
0136 __shuffle(_RandomAccessIterator __first, _Sentinel __last_sentinel, _UniformRandomNumberGenerator&& __g) {
0137   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
0138   typedef uniform_int_distribution<ptrdiff_t> _Dp;
0139   typedef typename _Dp::param_type _Pp;
0140
0141   auto __original_last = _IterOps<_AlgPolicy>::next(__first, __last_sentinel);
0142   auto __last          = __original_last;
0143   difference_type __d  = __last - __first;
0144   if (__d > 1) {
0145     _Dp __uid;
0146     for (--__last, (void)--__d; __first < __last; ++__first, (void)--__d) {
0147       difference_type __i = __uid(__g, _Pp(0, __d));
0148       if (__i != difference_type(0))
0149         _IterOps<_AlgPolicy>::iter_swap(__first, __first + __i);
0150     }
0151   }
0152
0153   return __original_last;
0154 }
0155
0156 template <class _RandomAccessIterator, class _UniformRandomNumberGenerator>
0157 _LIBCPP_HIDE_FROM_ABI void
0158 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, _UniformRandomNumberGenerator&& __g) {
0159   (void)std::__shuffle<_ClassicAlgPolicy>(
0160       std::move(__first), std::move(__last), std::forward<_UniformRandomNumberGenerator>(__g));
0161 }
0162
0163 _LIBCPP_END_NAMESPACE_STD
0164
0165 _LIBCPP_POP_MACROS
0166
0167 #endif // _LIBCPP___ALGORITHM_SHUFFLE_H