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