1 //===----------------------------------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #ifndef _LIBCPP___ALGORITHM_SHUFFLE_H 10 #define _LIBCPP___ALGORITHM_SHUFFLE_H 11 12 #include <__config> 13 #include <__iterator/iterator_traits.h> 14 #include <__random/uniform_int_distribution.h> 15 #include <__utility/swap.h> 16 #include <cstddef> 17 #include <cstdint> 18 19 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 20 #pragma GCC system_header 21 #endif 22 23 _LIBCPP_PUSH_MACROS 24 #include <__undef_macros> 25 26 _LIBCPP_BEGIN_NAMESPACE_STD 27 28 29 #if _LIBCPP_STD_VER <= 14 || defined(_LIBCPP_ENABLE_CXX17_REMOVED_RANDOM_SHUFFLE) \ 30 || defined(_LIBCPP_BUILDING_LIBRARY) 31 class _LIBCPP_TYPE_VIS __rs_default; 32 33 _LIBCPP_FUNC_VIS __rs_default __rs_get(); 34 35 class _LIBCPP_TYPE_VIS __rs_default 36 { 37 static unsigned __c_; 38 39 __rs_default(); 40 public: 41 typedef uint_fast32_t result_type; 42 43 static const result_type _Min = 0; 44 static const result_type _Max = 0xFFFFFFFF; 45 46 __rs_default(const __rs_default&); 47 ~__rs_default(); 48 49 result_type operator()(); 50 51 static _LIBCPP_CONSTEXPR result_type min() {return _Min;} 52 static _LIBCPP_CONSTEXPR result_type max() {return _Max;} 53 54 friend _LIBCPP_FUNC_VIS __rs_default __rs_get(); 55 }; 56 57 _LIBCPP_FUNC_VIS __rs_default __rs_get(); 58 59 template <class _RandomAccessIterator> 60 _LIBCPP_DEPRECATED_IN_CXX14 void 61 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last) 62 { 63 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 64 typedef uniform_int_distribution<ptrdiff_t> _Dp; 65 typedef typename _Dp::param_type _Pp; 66 difference_type __d = __last - __first; 67 if (__d > 1) 68 { 69 _Dp __uid; 70 __rs_default __g = __rs_get(); 71 for (--__last, (void) --__d; __first < __last; ++__first, (void) --__d) 72 { 73 difference_type __i = __uid(__g, _Pp(0, __d)); 74 if (__i != difference_type(0)) 75 swap(*__first, *(__first + __i)); 76 } 77 } 78 } 79 80 template <class _RandomAccessIterator, class _RandomNumberGenerator> 81 _LIBCPP_DEPRECATED_IN_CXX14 void 82 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 83 #ifndef _LIBCPP_CXX03_LANG 84 _RandomNumberGenerator&& __rand) 85 #else 86 _RandomNumberGenerator& __rand) 87 #endif 88 { 89 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 90 difference_type __d = __last - __first; 91 if (__d > 1) 92 { 93 for (--__last; __first < __last; ++__first, (void) --__d) 94 { 95 difference_type __i = __rand(__d); 96 if (__i != difference_type(0)) 97 swap(*__first, *(__first + __i)); 98 } 99 } 100 } 101 #endif 102 103 template<class _RandomAccessIterator, class _UniformRandomNumberGenerator> 104 void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 105 _UniformRandomNumberGenerator&& __g) 106 { 107 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 108 typedef uniform_int_distribution<ptrdiff_t> _Dp; 109 typedef typename _Dp::param_type _Pp; 110 difference_type __d = __last - __first; 111 if (__d > 1) 112 { 113 _Dp __uid; 114 for (--__last, (void) --__d; __first < __last; ++__first, (void) --__d) 115 { 116 difference_type __i = __uid(__g, _Pp(0, __d)); 117 if (__i != difference_type(0)) 118 swap(*__first, *(__first + __i)); 119 } 120 } 121 } 122 123 _LIBCPP_END_NAMESPACE_STD 124 125 _LIBCPP_POP_MACROS 126 127 #endif // _LIBCPP___ALGORITHM_SHUFFLE_H 128