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