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
min()51 static _LIBCPP_CONSTEXPR result_type min() {return _Min;}
max()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
random_shuffle(_RandomAccessIterator __first,_RandomAccessIterator __last)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
random_shuffle(_RandomAccessIterator __first,_RandomAccessIterator __last,_RandomNumberGenerator && __rand)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>
shuffle(_RandomAccessIterator __first,_RandomAccessIterator __last,_UniformRandomNumberGenerator && __g)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