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