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 #if _LIBCPP_STD_VER <= 14 || defined(_LIBCPP_ENABLE_CXX17_REMOVED_RANDOM_SHUFFLE) \
29   || defined(_LIBCPP_BUILDING_LIBRARY)
30 class _LIBCPP_TYPE_VIS __rs_default;
31 
32 _LIBCPP_FUNC_VIS __rs_default __rs_get();
33 
34 class _LIBCPP_TYPE_VIS __rs_default
35 {
36     static unsigned __c_;
37 
38     __rs_default();
39 public:
40     typedef uint_fast32_t result_type;
41 
42     static const result_type _Min = 0;
43     static const result_type _Max = 0xFFFFFFFF;
44 
45     __rs_default(const __rs_default&);
46     ~__rs_default();
47 
48     result_type operator()();
49 
50     static _LIBCPP_CONSTEXPR result_type min() {return _Min;}
51     static _LIBCPP_CONSTEXPR result_type max() {return _Max;}
52 
53     friend _LIBCPP_FUNC_VIS __rs_default __rs_get();
54 };
55 
56 _LIBCPP_FUNC_VIS __rs_default __rs_get();
57 
58 template <class _RandomAccessIterator>
59 _LIBCPP_DEPRECATED_IN_CXX14 void
60 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
61 {
62     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
63     typedef uniform_int_distribution<ptrdiff_t> _Dp;
64     typedef typename _Dp::param_type _Pp;
65     difference_type __d = __last - __first;
66     if (__d > 1)
67     {
68         _Dp __uid;
69         __rs_default __g = __rs_get();
70         for (--__last, (void) --__d; __first < __last; ++__first, (void) --__d)
71         {
72             difference_type __i = __uid(__g, _Pp(0, __d));
73             if (__i != difference_type(0))
74                 swap(*__first, *(__first + __i));
75         }
76     }
77 }
78 
79 template <class _RandomAccessIterator, class _RandomNumberGenerator>
80 _LIBCPP_DEPRECATED_IN_CXX14 void
81 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
82 #ifndef _LIBCPP_CXX03_LANG
83                _RandomNumberGenerator&& __rand)
84 #else
85                _RandomNumberGenerator& __rand)
86 #endif
87 {
88     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
89     difference_type __d = __last - __first;
90     if (__d > 1)
91     {
92         for (--__last; __first < __last; ++__first, (void) --__d)
93         {
94             difference_type __i = __rand(__d);
95             if (__i != difference_type(0))
96               swap(*__first, *(__first + __i));
97         }
98     }
99 }
100 #endif
101 
102 template<class _RandomAccessIterator, class _UniformRandomNumberGenerator>
103     void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
104                  _UniformRandomNumberGenerator&& __g)
105 {
106     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
107     typedef uniform_int_distribution<ptrdiff_t> _Dp;
108     typedef typename _Dp::param_type _Pp;
109     difference_type __d = __last - __first;
110     if (__d > 1)
111     {
112         _Dp __uid;
113         for (--__last, (void) --__d; __first < __last; ++__first, (void) --__d)
114         {
115             difference_type __i = __uid(__g, _Pp(0, __d));
116             if (__i != difference_type(0))
117                 swap(*__first, *(__first + __i));
118         }
119     }
120 }
121 
122 _LIBCPP_END_NAMESPACE_STD
123 
124 _LIBCPP_POP_MACROS
125 
126 #endif // _LIBCPP___ALGORITHM_SHUFFLE_H
127