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___RANDOM_SHUFFLE_ORDER_ENGINE_H
10 #define _LIBCPP___RANDOM_SHUFFLE_ORDER_ENGINE_H
11 
12 #include <__algorithm/equal.h>
13 #include <__config>
14 #include <__random/is_seed_sequence.h>
15 #include <__utility/move.h>
16 #include <cstdint>
17 #include <iosfwd>
18 #include <type_traits>
19 
20 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
21 #  pragma GCC system_header
22 #endif
23 
24 _LIBCPP_PUSH_MACROS
25 #include <__undef_macros>
26 
27 _LIBCPP_BEGIN_NAMESPACE_STD
28 
29 template <uint64_t _Xp, uint64_t _Yp>
30 struct __ugcd
31 {
32     static _LIBCPP_CONSTEXPR const uint64_t value = __ugcd<_Yp, _Xp % _Yp>::value;
33 };
34 
35 template <uint64_t _Xp>
36 struct __ugcd<_Xp, 0>
37 {
38     static _LIBCPP_CONSTEXPR const uint64_t value = _Xp;
39 };
40 
41 template <uint64_t _Np, uint64_t _Dp>
42 class __uratio
43 {
44     static_assert(_Dp != 0, "__uratio divide by 0");
45     static _LIBCPP_CONSTEXPR const uint64_t __gcd = __ugcd<_Np, _Dp>::value;
46 public:
47     static _LIBCPP_CONSTEXPR const uint64_t num = _Np / __gcd;
48     static _LIBCPP_CONSTEXPR const uint64_t den = _Dp / __gcd;
49 
50     typedef __uratio<num, den> type;
51 };
52 
53 template<class _Engine, size_t __k>
54 class _LIBCPP_TEMPLATE_VIS shuffle_order_engine
55 {
56     static_assert(0 < __k, "shuffle_order_engine invalid parameters");
57 public:
58     // types
59     typedef typename _Engine::result_type result_type;
60 
61 private:
62     _Engine __e_;
63     result_type __v_[__k];
64     result_type __y_;
65 
66 public:
67     // engine characteristics
68     static _LIBCPP_CONSTEXPR const size_t table_size = __k;
69 
70 #ifdef _LIBCPP_CXX03_LANG
71     static const result_type _Min = _Engine::_Min;
72     static const result_type _Max = _Engine::_Max;
73 #else
74     static _LIBCPP_CONSTEXPR const result_type _Min = _Engine::min();
75     static _LIBCPP_CONSTEXPR const result_type _Max = _Engine::max();
76 #endif
77     static_assert(_Min < _Max, "shuffle_order_engine invalid parameters");
78     _LIBCPP_INLINE_VISIBILITY
79     static _LIBCPP_CONSTEXPR result_type min() { return _Min; }
80     _LIBCPP_INLINE_VISIBILITY
81     static _LIBCPP_CONSTEXPR result_type max() { return _Max; }
82 
83     static _LIBCPP_CONSTEXPR const unsigned long long _Rp = _Max - _Min + 1ull;
84 
85     // constructors and seeding functions
86     _LIBCPP_INLINE_VISIBILITY
87     shuffle_order_engine() {__init();}
88     _LIBCPP_INLINE_VISIBILITY
89     explicit shuffle_order_engine(const _Engine& __e)
90         : __e_(__e) {__init();}
91 #ifndef _LIBCPP_CXX03_LANG
92     _LIBCPP_INLINE_VISIBILITY
93     explicit shuffle_order_engine(_Engine&& __e)
94         : __e_(_VSTD::move(__e)) {__init();}
95 #endif // _LIBCPP_CXX03_LANG
96     _LIBCPP_INLINE_VISIBILITY
97     explicit shuffle_order_engine(result_type __sd) : __e_(__sd) {__init();}
98     template<class _Sseq>
99         _LIBCPP_INLINE_VISIBILITY
100         explicit shuffle_order_engine(_Sseq& __q,
101         typename enable_if<__is_seed_sequence<_Sseq, shuffle_order_engine>::value &&
102                            !is_convertible<_Sseq, _Engine>::value>::type* = 0)
103          : __e_(__q) {__init();}
104     _LIBCPP_INLINE_VISIBILITY
105     void seed() {__e_.seed(); __init();}
106     _LIBCPP_INLINE_VISIBILITY
107     void seed(result_type __sd) {__e_.seed(__sd); __init();}
108     template<class _Sseq>
109         _LIBCPP_INLINE_VISIBILITY
110         typename enable_if
111         <
112             __is_seed_sequence<_Sseq, shuffle_order_engine>::value,
113             void
114         >::type
115         seed(_Sseq& __q) {__e_.seed(__q); __init();}
116 
117     // generating functions
118     _LIBCPP_INLINE_VISIBILITY
119     result_type operator()() {return __eval(integral_constant<bool, _Rp != 0>());}
120     _LIBCPP_INLINE_VISIBILITY
121     void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
122 
123     // property functions
124     _LIBCPP_INLINE_VISIBILITY
125     const _Engine& base() const _NOEXCEPT {return __e_;}
126 
127 private:
128     template<class _Eng, size_t _Kp>
129     friend
130     bool
131     operator==(
132         const shuffle_order_engine<_Eng, _Kp>& __x,
133         const shuffle_order_engine<_Eng, _Kp>& __y);
134 
135     template<class _Eng, size_t _Kp>
136     friend
137     bool
138     operator!=(
139         const shuffle_order_engine<_Eng, _Kp>& __x,
140         const shuffle_order_engine<_Eng, _Kp>& __y);
141 
142     template <class _CharT, class _Traits,
143               class _Eng, size_t _Kp>
144     friend
145     basic_ostream<_CharT, _Traits>&
146     operator<<(basic_ostream<_CharT, _Traits>& __os,
147                const shuffle_order_engine<_Eng, _Kp>& __x);
148 
149     template <class _CharT, class _Traits,
150               class _Eng, size_t _Kp>
151     friend
152     basic_istream<_CharT, _Traits>&
153     operator>>(basic_istream<_CharT, _Traits>& __is,
154                shuffle_order_engine<_Eng, _Kp>& __x);
155 
156     _LIBCPP_INLINE_VISIBILITY
157     void __init()
158     {
159         for (size_t __i = 0; __i < __k; ++__i)
160             __v_[__i] = __e_();
161         __y_ = __e_();
162     }
163 
164     _LIBCPP_INLINE_VISIBILITY
165     result_type __eval(false_type) {return __eval2(integral_constant<bool, __k & 1>());}
166     _LIBCPP_INLINE_VISIBILITY
167     result_type __eval(true_type) {return __eval(__uratio<__k, _Rp>());}
168 
169     _LIBCPP_INLINE_VISIBILITY
170     result_type __eval2(false_type) {return __eval(__uratio<__k/2, 0x8000000000000000ull>());}
171     _LIBCPP_INLINE_VISIBILITY
172     result_type __eval2(true_type) {return __evalf<__k, 0>();}
173 
174     template <uint64_t _Np, uint64_t _Dp>
175         _LIBCPP_INLINE_VISIBILITY
176         typename enable_if
177         <
178             (__uratio<_Np, _Dp>::num > 0xFFFFFFFFFFFFFFFFull / (_Max - _Min)),
179             result_type
180         >::type
181         __eval(__uratio<_Np, _Dp>)
182             {return __evalf<__uratio<_Np, _Dp>::num, __uratio<_Np, _Dp>::den>();}
183 
184     template <uint64_t _Np, uint64_t _Dp>
185         _LIBCPP_INLINE_VISIBILITY
186         typename enable_if
187         <
188             __uratio<_Np, _Dp>::num <= 0xFFFFFFFFFFFFFFFFull / (_Max - _Min),
189             result_type
190         >::type
191         __eval(__uratio<_Np, _Dp>)
192         {
193             const size_t __j = static_cast<size_t>(__uratio<_Np, _Dp>::num * (__y_ - _Min)
194                                                    / __uratio<_Np, _Dp>::den);
195             __y_ = __v_[__j];
196             __v_[__j] = __e_();
197             return __y_;
198         }
199 
200     template <uint64_t __n, uint64_t __d>
201         _LIBCPP_INLINE_VISIBILITY
202         result_type __evalf()
203         {
204             const double _Fp = __d == 0 ?
205                 __n / (2. * 0x8000000000000000ull) :
206                 __n / (double)__d;
207             const size_t __j = static_cast<size_t>(_Fp * (__y_ - _Min));
208             __y_ = __v_[__j];
209             __v_[__j] = __e_();
210             return __y_;
211         }
212 };
213 
214 template<class _Engine, size_t __k>
215     _LIBCPP_CONSTEXPR const size_t shuffle_order_engine<_Engine, __k>::table_size;
216 
217 template<class _Eng, size_t _Kp>
218 _LIBCPP_HIDE_FROM_ABI bool
219 operator==(
220     const shuffle_order_engine<_Eng, _Kp>& __x,
221     const shuffle_order_engine<_Eng, _Kp>& __y)
222 {
223     return __x.__y_ == __y.__y_ && _VSTD::equal(__x.__v_, __x.__v_ + _Kp, __y.__v_) &&
224            __x.__e_ == __y.__e_;
225 }
226 
227 template<class _Eng, size_t _Kp>
228 inline _LIBCPP_INLINE_VISIBILITY
229 bool
230 operator!=(
231     const shuffle_order_engine<_Eng, _Kp>& __x,
232     const shuffle_order_engine<_Eng, _Kp>& __y)
233 {
234     return !(__x == __y);
235 }
236 
237 template <class _CharT, class _Traits,
238           class _Eng, size_t _Kp>
239 _LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&
240 operator<<(basic_ostream<_CharT, _Traits>& __os,
241            const shuffle_order_engine<_Eng, _Kp>& __x)
242 {
243     __save_flags<_CharT, _Traits> __lx(__os);
244     typedef basic_ostream<_CharT, _Traits> _Ostream;
245     __os.flags(_Ostream::dec | _Ostream::left);
246     _CharT __sp = __os.widen(' ');
247     __os.fill(__sp);
248     __os << __x.__e_ << __sp << __x.__v_[0];
249     for (size_t __i = 1; __i < _Kp; ++__i)
250         __os << __sp << __x.__v_[__i];
251     return __os << __sp << __x.__y_;
252 }
253 
254 template <class _CharT, class _Traits,
255           class _Eng, size_t _Kp>
256 _LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&
257 operator>>(basic_istream<_CharT, _Traits>& __is,
258            shuffle_order_engine<_Eng, _Kp>& __x)
259 {
260     typedef typename shuffle_order_engine<_Eng, _Kp>::result_type result_type;
261     __save_flags<_CharT, _Traits> __lx(__is);
262     typedef basic_istream<_CharT, _Traits> _Istream;
263     __is.flags(_Istream::dec | _Istream::skipws);
264     _Eng __e;
265     result_type _Vp[_Kp+1];
266     __is >> __e;
267     for (size_t __i = 0; __i < _Kp+1; ++__i)
268         __is >> _Vp[__i];
269     if (!__is.fail())
270     {
271         __x.__e_ = __e;
272         for (size_t __i = 0; __i < _Kp; ++__i)
273             __x.__v_[__i] = _Vp[__i];
274         __x.__y_ = _Vp[_Kp];
275     }
276     return __is;
277 }
278 
279 _LIBCPP_END_NAMESPACE_STD
280 
281 _LIBCPP_POP_MACROS
282 
283 #endif // _LIBCPP___RANDOM_SHUFFLE_ORDER_ENGINE_H
284