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, __enable_if_t<__is_seed_sequence<_Sseq, shuffle_order_engine>::value && 102 !is_convertible<_Sseq, _Engine>::value, int> = 0> 103 _LIBCPP_INLINE_VISIBILITY 104 explicit shuffle_order_engine(_Sseq& __q) 105 : __e_(__q) {__init();} 106 _LIBCPP_INLINE_VISIBILITY 107 void seed() {__e_.seed(); __init();} 108 _LIBCPP_INLINE_VISIBILITY 109 void seed(result_type __sd) {__e_.seed(__sd); __init();} 110 template<class _Sseq, __enable_if_t<__is_seed_sequence<_Sseq, shuffle_order_engine>::value, int> = 0> 111 _LIBCPP_INLINE_VISIBILITY 112 void 113 seed(_Sseq& __q) {__e_.seed(__q); __init();} 114 115 // generating functions 116 _LIBCPP_INLINE_VISIBILITY 117 result_type operator()() {return __eval(integral_constant<bool, _Rp != 0>());} 118 _LIBCPP_INLINE_VISIBILITY 119 void discard(unsigned long long __z) {for (; __z; --__z) operator()();} 120 121 // property functions 122 _LIBCPP_INLINE_VISIBILITY 123 const _Engine& base() const _NOEXCEPT {return __e_;} 124 125 private: 126 template<class _Eng, size_t _Kp> 127 friend 128 bool 129 operator==( 130 const shuffle_order_engine<_Eng, _Kp>& __x, 131 const shuffle_order_engine<_Eng, _Kp>& __y); 132 133 template<class _Eng, size_t _Kp> 134 friend 135 bool 136 operator!=( 137 const shuffle_order_engine<_Eng, _Kp>& __x, 138 const shuffle_order_engine<_Eng, _Kp>& __y); 139 140 template <class _CharT, class _Traits, 141 class _Eng, size_t _Kp> 142 friend 143 basic_ostream<_CharT, _Traits>& 144 operator<<(basic_ostream<_CharT, _Traits>& __os, 145 const shuffle_order_engine<_Eng, _Kp>& __x); 146 147 template <class _CharT, class _Traits, 148 class _Eng, size_t _Kp> 149 friend 150 basic_istream<_CharT, _Traits>& 151 operator>>(basic_istream<_CharT, _Traits>& __is, 152 shuffle_order_engine<_Eng, _Kp>& __x); 153 154 _LIBCPP_INLINE_VISIBILITY 155 void __init() 156 { 157 for (size_t __i = 0; __i < __k; ++__i) 158 __v_[__i] = __e_(); 159 __y_ = __e_(); 160 } 161 162 _LIBCPP_INLINE_VISIBILITY 163 result_type __eval(false_type) {return __eval2(integral_constant<bool, __k & 1>());} 164 _LIBCPP_INLINE_VISIBILITY 165 result_type __eval(true_type) {return __eval(__uratio<__k, _Rp>());} 166 167 _LIBCPP_INLINE_VISIBILITY 168 result_type __eval2(false_type) {return __eval(__uratio<__k/2, 0x8000000000000000ull>());} 169 _LIBCPP_INLINE_VISIBILITY 170 result_type __eval2(true_type) {return __evalf<__k, 0>();} 171 172 template <uint64_t _Np, uint64_t _Dp, __enable_if_t<(__uratio<_Np, _Dp>::num > 0xFFFFFFFFFFFFFFFFull / (_Max - _Min)), int> = 0> 173 _LIBCPP_INLINE_VISIBILITY 174 result_type 175 __eval(__uratio<_Np, _Dp>) 176 {return __evalf<__uratio<_Np, _Dp>::num, __uratio<_Np, _Dp>::den>();} 177 178 template <uint64_t _Np, uint64_t _Dp, __enable_if_t<__uratio<_Np, _Dp>::num <= 0xFFFFFFFFFFFFFFFFull / (_Max - _Min), int> = 0> 179 _LIBCPP_INLINE_VISIBILITY 180 result_type 181 __eval(__uratio<_Np, _Dp>) 182 { 183 const size_t __j = static_cast<size_t>(__uratio<_Np, _Dp>::num * (__y_ - _Min) 184 / __uratio<_Np, _Dp>::den); 185 __y_ = __v_[__j]; 186 __v_[__j] = __e_(); 187 return __y_; 188 } 189 190 template <uint64_t __n, uint64_t __d> 191 _LIBCPP_INLINE_VISIBILITY 192 result_type __evalf() 193 { 194 const double __fp = __d == 0 ? 195 __n / (2. * 0x8000000000000000ull) : 196 __n / (double)__d; 197 const size_t __j = static_cast<size_t>(__fp * (__y_ - _Min)); 198 __y_ = __v_[__j]; 199 __v_[__j] = __e_(); 200 return __y_; 201 } 202 }; 203 204 template<class _Engine, size_t __k> 205 _LIBCPP_CONSTEXPR const size_t shuffle_order_engine<_Engine, __k>::table_size; 206 207 template<class _Eng, size_t _Kp> 208 _LIBCPP_HIDE_FROM_ABI bool 209 operator==( 210 const shuffle_order_engine<_Eng, _Kp>& __x, 211 const shuffle_order_engine<_Eng, _Kp>& __y) 212 { 213 return __x.__y_ == __y.__y_ && _VSTD::equal(__x.__v_, __x.__v_ + _Kp, __y.__v_) && 214 __x.__e_ == __y.__e_; 215 } 216 217 template<class _Eng, size_t _Kp> 218 inline _LIBCPP_INLINE_VISIBILITY 219 bool 220 operator!=( 221 const shuffle_order_engine<_Eng, _Kp>& __x, 222 const shuffle_order_engine<_Eng, _Kp>& __y) 223 { 224 return !(__x == __y); 225 } 226 227 template <class _CharT, class _Traits, 228 class _Eng, size_t _Kp> 229 _LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>& 230 operator<<(basic_ostream<_CharT, _Traits>& __os, 231 const shuffle_order_engine<_Eng, _Kp>& __x) 232 { 233 __save_flags<_CharT, _Traits> __lx(__os); 234 typedef basic_ostream<_CharT, _Traits> _Ostream; 235 __os.flags(_Ostream::dec | _Ostream::left); 236 _CharT __sp = __os.widen(' '); 237 __os.fill(__sp); 238 __os << __x.__e_ << __sp << __x.__v_[0]; 239 for (size_t __i = 1; __i < _Kp; ++__i) 240 __os << __sp << __x.__v_[__i]; 241 return __os << __sp << __x.__y_; 242 } 243 244 template <class _CharT, class _Traits, 245 class _Eng, size_t _Kp> 246 _LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>& 247 operator>>(basic_istream<_CharT, _Traits>& __is, 248 shuffle_order_engine<_Eng, _Kp>& __x) 249 { 250 typedef typename shuffle_order_engine<_Eng, _Kp>::result_type result_type; 251 __save_flags<_CharT, _Traits> __lx(__is); 252 typedef basic_istream<_CharT, _Traits> _Istream; 253 __is.flags(_Istream::dec | _Istream::skipws); 254 _Eng __e; 255 result_type __vp[_Kp+1]; 256 __is >> __e; 257 for (size_t __i = 0; __i < _Kp+1; ++__i) 258 __is >> __vp[__i]; 259 if (!__is.fail()) 260 { 261 __x.__e_ = __e; 262 for (size_t __i = 0; __i < _Kp; ++__i) 263 __x.__v_[__i] = __vp[__i]; 264 __x.__y_ = __vp[_Kp]; 265 } 266 return __is; 267 } 268 269 _LIBCPP_END_NAMESPACE_STD 270 271 _LIBCPP_POP_MACROS 272 273 #endif // _LIBCPP___RANDOM_SHUFFLE_ORDER_ENGINE_H 274