1 //===----------------------------------------------------------------------===//
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
7 //===----------------------------------------------------------------------===//
9 #ifndef _LIBCPP___CXX03___RANDOM_SHUFFLE_ORDER_ENGINE_H
10 #define _LIBCPP___CXX03___RANDOM_SHUFFLE_ORDER_ENGINE_H
12 #include <__cxx03/__algorithm/equal.h>
13 #include <__cxx03/__config>
14 #include <__cxx03/__random/is_seed_sequence.h>
15 #include <__cxx03/__type_traits/enable_if.h>
16 #include <__cxx03/__type_traits/integral_constant.h>
17 #include <__cxx03/__type_traits/is_convertible.h>
18 #include <__cxx03/__utility/move.h>
19 #include <__cxx03/cstddef>
20 #include <__cxx03/cstdint>
21 #include <__cxx03/iosfwd>
23 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
24 # pragma GCC system_header
28 #include <__cxx03/__undef_macros>
30 _LIBCPP_BEGIN_NAMESPACE_STD
32 template <uint64_t _Xp
, uint64_t _Yp
>
34 static _LIBCPP_CONSTEXPR
const uint64_t value
= __ugcd
<_Yp
, _Xp
% _Yp
>::value
;
37 template <uint64_t _Xp
>
38 struct __ugcd
<_Xp
, 0> {
39 static _LIBCPP_CONSTEXPR
const uint64_t value
= _Xp
;
42 template <uint64_t _Np
, uint64_t _Dp
>
44 static_assert(_Dp
!= 0, "__uratio divide by 0");
45 static _LIBCPP_CONSTEXPR
const uint64_t __gcd
= __ugcd
<_Np
, _Dp
>::value
;
48 static _LIBCPP_CONSTEXPR
const uint64_t num
= _Np
/ __gcd
;
49 static _LIBCPP_CONSTEXPR
const uint64_t den
= _Dp
/ __gcd
;
51 typedef __uratio
<num
, den
> type
;
54 template <class _Engine
, size_t __k
>
55 class _LIBCPP_TEMPLATE_VIS shuffle_order_engine
{
56 static_assert(0 < __k
, "shuffle_order_engine invalid parameters");
60 typedef typename
_Engine::result_type result_type
;
64 result_type __v_
[__k
];
68 // engine characteristics
69 static _LIBCPP_CONSTEXPR
const size_t table_size
= __k
;
71 #ifdef _LIBCPP_CXX03_LANG
72 static const result_type _Min
= _Engine::_Min
;
73 static const result_type _Max
= _Engine::_Max
;
75 static _LIBCPP_CONSTEXPR
const result_type _Min
= _Engine::min();
76 static _LIBCPP_CONSTEXPR
const result_type _Max
= _Engine::max();
78 static_assert(_Min
< _Max
, "shuffle_order_engine invalid parameters");
79 _LIBCPP_HIDE_FROM_ABI
static _LIBCPP_CONSTEXPR result_type
min() { return _Min
; }
80 _LIBCPP_HIDE_FROM_ABI
static _LIBCPP_CONSTEXPR result_type
max() { return _Max
; }
82 static _LIBCPP_CONSTEXPR
const unsigned long long _Rp
= _Max
- _Min
+ 1ull;
84 // constructors and seeding functions
85 _LIBCPP_HIDE_FROM_ABI
shuffle_order_engine() { __init(); }
86 _LIBCPP_HIDE_FROM_ABI
explicit shuffle_order_engine(const _Engine
& __e
) : __e_(__e
) { __init(); }
87 #ifndef _LIBCPP_CXX03_LANG
88 _LIBCPP_HIDE_FROM_ABI
explicit shuffle_order_engine(_Engine
&& __e
) : __e_(std::move(__e
)) { __init(); }
89 #endif // _LIBCPP_CXX03_LANG
90 _LIBCPP_HIDE_FROM_ABI
explicit shuffle_order_engine(result_type __sd
) : __e_(__sd
) { __init(); }
93 __enable_if_t
<__is_seed_sequence
<_Sseq
, shuffle_order_engine
>::value
&& !is_convertible
<_Sseq
, _Engine
>::value
,
95 _LIBCPP_HIDE_FROM_ABI
explicit shuffle_order_engine(_Sseq
& __q
) : __e_(__q
) {
98 _LIBCPP_HIDE_FROM_ABI
void seed() {
102 _LIBCPP_HIDE_FROM_ABI
void seed(result_type __sd
) {
106 template <class _Sseq
, __enable_if_t
<__is_seed_sequence
<_Sseq
, shuffle_order_engine
>::value
, int> = 0>
107 _LIBCPP_HIDE_FROM_ABI
void seed(_Sseq
& __q
) {
112 // generating functions
113 _LIBCPP_HIDE_FROM_ABI result_type
operator()() { return __eval(integral_constant
<bool, _Rp
!= 0>()); }
114 _LIBCPP_HIDE_FROM_ABI
void discard(unsigned long long __z
) {
119 // property functions
120 _LIBCPP_HIDE_FROM_ABI
const _Engine
& base() const _NOEXCEPT
{ return __e_
; }
123 template <class _Eng
, size_t _Kp
>
124 friend bool operator==(const shuffle_order_engine
<_Eng
, _Kp
>& __x
, const shuffle_order_engine
<_Eng
, _Kp
>& __y
);
126 template <class _Eng
, size_t _Kp
>
127 friend bool operator!=(const shuffle_order_engine
<_Eng
, _Kp
>& __x
, const shuffle_order_engine
<_Eng
, _Kp
>& __y
);
129 template <class _CharT
, class _Traits
, class _Eng
, size_t _Kp
>
130 friend basic_ostream
<_CharT
, _Traits
>&
131 operator<<(basic_ostream
<_CharT
, _Traits
>& __os
, const shuffle_order_engine
<_Eng
, _Kp
>& __x
);
133 template <class _CharT
, class _Traits
, class _Eng
, size_t _Kp
>
134 friend basic_istream
<_CharT
, _Traits
>&
135 operator>>(basic_istream
<_CharT
, _Traits
>& __is
, shuffle_order_engine
<_Eng
, _Kp
>& __x
);
137 _LIBCPP_HIDE_FROM_ABI
void __init() {
138 for (size_t __i
= 0; __i
< __k
; ++__i
)
143 _LIBCPP_HIDE_FROM_ABI result_type
__eval(false_type
) { return __eval2(integral_constant
<bool, __k
& 1>()); }
144 _LIBCPP_HIDE_FROM_ABI result_type
__eval(true_type
) { return __eval(__uratio
<__k
, _Rp
>()); }
146 _LIBCPP_HIDE_FROM_ABI result_type
__eval2(false_type
) { return __eval(__uratio
<__k
/ 2, 0x8000000000000000ull
>()); }
147 _LIBCPP_HIDE_FROM_ABI result_type
__eval2(true_type
) { return __evalf
<__k
, 0>(); }
149 template <uint64_t _Np
,
151 __enable_if_t
<(__uratio
<_Np
, _Dp
>::num
> 0xFFFFFFFFFFFFFFFFull
/ (_Max
- _Min
)), int> = 0>
152 _LIBCPP_HIDE_FROM_ABI result_type
__eval(__uratio
<_Np
, _Dp
>) {
153 return __evalf
<__uratio
<_Np
, _Dp
>::num
, __uratio
<_Np
, _Dp
>::den
>();
156 template <uint64_t _Np
,
158 __enable_if_t
<__uratio
<_Np
, _Dp
>::num
<= 0xFFFFFFFFFFFFFFFFull
/ (_Max
- _Min
), int> = 0>
159 _LIBCPP_HIDE_FROM_ABI result_type
__eval(__uratio
<_Np
, _Dp
>) {
160 const size_t __j
= static_cast<size_t>(__uratio
<_Np
, _Dp
>::num
* (__y_
- _Min
) / __uratio
<_Np
, _Dp
>::den
);
166 template <uint64_t __n
, uint64_t __d
>
167 _LIBCPP_HIDE_FROM_ABI result_type
__evalf() {
168 const double __fp
= __d
== 0 ? __n
/ (2. * 0x8000000000000000ull
) : __n
/ (double)__d
;
169 const size_t __j
= static_cast<size_t>(__fp
* (__y_
- _Min
));
176 template <class _Engine
, size_t __k
>
177 _LIBCPP_CONSTEXPR
const size_t shuffle_order_engine
<_Engine
, __k
>::table_size
;
179 template <class _Eng
, size_t _Kp
>
180 _LIBCPP_HIDE_FROM_ABI
bool
181 operator==(const shuffle_order_engine
<_Eng
, _Kp
>& __x
, const shuffle_order_engine
<_Eng
, _Kp
>& __y
) {
182 return __x
.__y_
== __y
.__y_
&& std::equal(__x
.__v_
, __x
.__v_
+ _Kp
, __y
.__v_
) && __x
.__e_
== __y
.__e_
;
185 template <class _Eng
, size_t _Kp
>
186 inline _LIBCPP_HIDE_FROM_ABI
bool
187 operator!=(const shuffle_order_engine
<_Eng
, _Kp
>& __x
, const shuffle_order_engine
<_Eng
, _Kp
>& __y
) {
188 return !(__x
== __y
);
191 template <class _CharT
, class _Traits
, class _Eng
, size_t _Kp
>
192 _LIBCPP_HIDE_FROM_ABI basic_ostream
<_CharT
, _Traits
>&
193 operator<<(basic_ostream
<_CharT
, _Traits
>& __os
, const shuffle_order_engine
<_Eng
, _Kp
>& __x
) {
194 __save_flags
<_CharT
, _Traits
> __lx(__os
);
195 typedef basic_ostream
<_CharT
, _Traits
> _Ostream
;
196 __os
.flags(_Ostream::dec
| _Ostream::left
);
197 _CharT __sp
= __os
.widen(' ');
199 __os
<< __x
.__e_
<< __sp
<< __x
.__v_
[0];
200 for (size_t __i
= 1; __i
< _Kp
; ++__i
)
201 __os
<< __sp
<< __x
.__v_
[__i
];
202 return __os
<< __sp
<< __x
.__y_
;
205 template <class _CharT
, class _Traits
, class _Eng
, size_t _Kp
>
206 _LIBCPP_HIDE_FROM_ABI basic_istream
<_CharT
, _Traits
>&
207 operator>>(basic_istream
<_CharT
, _Traits
>& __is
, shuffle_order_engine
<_Eng
, _Kp
>& __x
) {
208 typedef typename shuffle_order_engine
<_Eng
, _Kp
>::result_type result_type
;
209 __save_flags
<_CharT
, _Traits
> __lx(__is
);
210 typedef basic_istream
<_CharT
, _Traits
> _Istream
;
211 __is
.flags(_Istream::dec
| _Istream::skipws
);
213 result_type __vp
[_Kp
+ 1];
215 for (size_t __i
= 0; __i
< _Kp
+ 1; ++__i
)
219 for (size_t __i
= 0; __i
< _Kp
; ++__i
)
220 __x
.__v_
[__i
] = __vp
[__i
];
221 __x
.__y_
= __vp
[_Kp
];
226 _LIBCPP_END_NAMESPACE_STD
230 #endif // _LIBCPP___CXX03___RANDOM_SHUFFLE_ORDER_ENGINE_H