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 <__algorithm/iterator_operations.h>
13#include <__config>
14#include <__debug>
15#include <__iterator/iterator_traits.h>
16#include <__random/uniform_int_distribution.h>
17#include <__utility/forward.h>
18#include <__utility/move.h>
19#include <__utility/swap.h>
20#include <cstddef>
21#include <cstdint>
22
23#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
24#  pragma GCC system_header
25#endif
26
27_LIBCPP_PUSH_MACROS
28#include <__undef_macros>
29
30_LIBCPP_BEGIN_NAMESPACE_STD
31
32class _LIBCPP_TYPE_VIS __libcpp_debug_randomizer {
33public:
34  __libcpp_debug_randomizer() {
35    __state_ = __seed();
36    __inc_ = __state_ + 0xda3e39cb94b95bdbULL;
37    __inc_ = (__inc_ << 1) | 1;
38  }
39  typedef uint_fast32_t result_type;
40
41  static const result_type _Min = 0;
42  static const result_type _Max = 0xFFFFFFFF;
43
44  _LIBCPP_HIDE_FROM_ABI result_type operator()() {
45    uint_fast64_t __oldstate = __state_;
46    __state_ = __oldstate * 6364136223846793005ULL + __inc_;
47    return __oldstate >> 32;
48  }
49
50  static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR result_type min() { return _Min; }
51  static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR result_type max() { return _Max; }
52
53private:
54  uint_fast64_t __state_;
55  uint_fast64_t __inc_;
56  _LIBCPP_HIDE_FROM_ABI static uint_fast64_t __seed() {
57#ifdef _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY_SEED
58    return _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY_SEED;
59#else
60    static char __x;
61    return reinterpret_cast<uintptr_t>(&__x);
62#endif
63  }
64};
65
66#if _LIBCPP_STD_VER <= 14 || defined(_LIBCPP_ENABLE_CXX17_REMOVED_RANDOM_SHUFFLE) \
67  || defined(_LIBCPP_BUILDING_LIBRARY)
68class _LIBCPP_TYPE_VIS __rs_default;
69
70_LIBCPP_FUNC_VIS __rs_default __rs_get();
71
72class _LIBCPP_TYPE_VIS __rs_default
73{
74    static unsigned __c_;
75
76    __rs_default();
77public:
78    typedef uint_fast32_t result_type;
79
80    static const result_type _Min = 0;
81    static const result_type _Max = 0xFFFFFFFF;
82
83    __rs_default(const __rs_default&);
84    ~__rs_default();
85
86    result_type operator()();
87
88    static _LIBCPP_CONSTEXPR result_type min() {return _Min;}
89    static _LIBCPP_CONSTEXPR result_type max() {return _Max;}
90
91    friend _LIBCPP_FUNC_VIS __rs_default __rs_get();
92};
93
94_LIBCPP_FUNC_VIS __rs_default __rs_get();
95
96template <class _RandomAccessIterator>
97_LIBCPP_HIDE_FROM_ABI _LIBCPP_DEPRECATED_IN_CXX14 void
98random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
99{
100    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
101    typedef uniform_int_distribution<ptrdiff_t> _Dp;
102    typedef typename _Dp::param_type _Pp;
103    difference_type __d = __last - __first;
104    if (__d > 1)
105    {
106        _Dp __uid;
107        __rs_default __g = __rs_get();
108        for (--__last, (void) --__d; __first < __last; ++__first, (void) --__d)
109        {
110            difference_type __i = __uid(__g, _Pp(0, __d));
111            if (__i != difference_type(0))
112                swap(*__first, *(__first + __i));
113        }
114    }
115}
116
117template <class _RandomAccessIterator, class _RandomNumberGenerator>
118_LIBCPP_HIDE_FROM_ABI _LIBCPP_DEPRECATED_IN_CXX14 void
119random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
120#ifndef _LIBCPP_CXX03_LANG
121               _RandomNumberGenerator&& __rand)
122#else
123               _RandomNumberGenerator& __rand)
124#endif
125{
126    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
127    difference_type __d = __last - __first;
128    if (__d > 1)
129    {
130        for (--__last; __first < __last; ++__first, (void) --__d)
131        {
132            difference_type __i = __rand(__d);
133            if (__i != difference_type(0))
134              swap(*__first, *(__first + __i));
135        }
136    }
137}
138#endif
139
140template <class _AlgPolicy, class _RandomAccessIterator, class _Sentinel, class _UniformRandomNumberGenerator>
141_LIBCPP_HIDE_FROM_ABI _RandomAccessIterator __shuffle(
142    _RandomAccessIterator __first, _Sentinel __last_sentinel, _UniformRandomNumberGenerator&& __g) {
143    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
144    typedef uniform_int_distribution<ptrdiff_t> _Dp;
145    typedef typename _Dp::param_type _Pp;
146
147    auto __original_last = _IterOps<_AlgPolicy>::next(__first, __last_sentinel);
148    auto __last = __original_last;
149    difference_type __d = __last - __first;
150    if (__d > 1)
151    {
152        _Dp __uid;
153        for (--__last, (void) --__d; __first < __last; ++__first, (void) --__d)
154        {
155            difference_type __i = __uid(__g, _Pp(0, __d));
156            if (__i != difference_type(0))
157                _IterOps<_AlgPolicy>::iter_swap(__first, __first + __i);
158        }
159    }
160
161    return __original_last;
162}
163
164template <class _RandomAccessIterator, class _UniformRandomNumberGenerator>
165_LIBCPP_HIDE_FROM_ABI void
166shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, _UniformRandomNumberGenerator&& __g) {
167  (void)std::__shuffle<_ClassicAlgPolicy>(
168      std::move(__first), std::move(__last), std::forward<_UniformRandomNumberGenerator>(__g));
169}
170
171_LIBCPP_END_NAMESPACE_STD
172
173_LIBCPP_POP_MACROS
174
175#endif // _LIBCPP___ALGORITHM_SHUFFLE_H
176