223 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef _LIBCPP___CXX03___RANDOM_SHUFFLE_ORDER_ENGINE_H10#define _LIBCPP___CXX03___RANDOM_SHUFFLE_ORDER_ENGINE_H11 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>22 23#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)24# pragma GCC system_header25#endif26 27_LIBCPP_PUSH_MACROS28#include <__cxx03/__undef_macros>29 30_LIBCPP_BEGIN_NAMESPACE_STD31 32template <uint64_t _Xp, uint64_t _Yp>33struct __ugcd {34 static const uint64_t value = __ugcd<_Yp, _Xp % _Yp>::value;35};36 37template <uint64_t _Xp>38struct __ugcd<_Xp, 0> {39 static const uint64_t value = _Xp;40};41 42template <uint64_t _Np, uint64_t _Dp>43class __uratio {44 static_assert(_Dp != 0, "__uratio divide by 0");45 static const uint64_t __gcd = __ugcd<_Np, _Dp>::value;46 47public:48 static const uint64_t num = _Np / __gcd;49 static const uint64_t den = _Dp / __gcd;50 51 typedef __uratio<num, den> type;52};53 54template <class _Engine, size_t __k>55class _LIBCPP_TEMPLATE_VIS shuffle_order_engine {56 static_assert(0 < __k, "shuffle_order_engine invalid parameters");57 58public:59 // types60 typedef typename _Engine::result_type result_type;61 62private:63 _Engine __e_;64 result_type __v_[__k];65 result_type __y_;66 67public:68 // engine characteristics69 static const size_t table_size = __k;70 71 static const result_type _Min = _Engine::_Min;72 static const result_type _Max = _Engine::_Max;73 static_assert(_Min < _Max, "shuffle_order_engine invalid parameters");74 _LIBCPP_HIDE_FROM_ABI static result_type min() { return _Min; }75 _LIBCPP_HIDE_FROM_ABI static result_type max() { return _Max; }76 77 static const unsigned long long _Rp = _Max - _Min + 1ull;78 79 // constructors and seeding functions80 _LIBCPP_HIDE_FROM_ABI shuffle_order_engine() { __init(); }81 _LIBCPP_HIDE_FROM_ABI explicit shuffle_order_engine(const _Engine& __e) : __e_(__e) { __init(); }82 _LIBCPP_HIDE_FROM_ABI explicit shuffle_order_engine(result_type __sd) : __e_(__sd) { __init(); }83 template <84 class _Sseq,85 __enable_if_t<__is_seed_sequence<_Sseq, shuffle_order_engine>::value && !is_convertible<_Sseq, _Engine>::value,86 int> = 0>87 _LIBCPP_HIDE_FROM_ABI explicit shuffle_order_engine(_Sseq& __q) : __e_(__q) {88 __init();89 }90 _LIBCPP_HIDE_FROM_ABI void seed() {91 __e_.seed();92 __init();93 }94 _LIBCPP_HIDE_FROM_ABI void seed(result_type __sd) {95 __e_.seed(__sd);96 __init();97 }98 template <class _Sseq, __enable_if_t<__is_seed_sequence<_Sseq, shuffle_order_engine>::value, int> = 0>99 _LIBCPP_HIDE_FROM_ABI void seed(_Sseq& __q) {100 __e_.seed(__q);101 __init();102 }103 104 // generating functions105 _LIBCPP_HIDE_FROM_ABI result_type operator()() { return __eval(integral_constant<bool, _Rp != 0>()); }106 _LIBCPP_HIDE_FROM_ABI void discard(unsigned long long __z) {107 for (; __z; --__z)108 operator()();109 }110 111 // property functions112 _LIBCPP_HIDE_FROM_ABI const _Engine& base() const _NOEXCEPT { return __e_; }113 114private:115 template <class _Eng, size_t _Kp>116 friend bool operator==(const shuffle_order_engine<_Eng, _Kp>& __x, const shuffle_order_engine<_Eng, _Kp>& __y);117 118 template <class _Eng, size_t _Kp>119 friend bool operator!=(const shuffle_order_engine<_Eng, _Kp>& __x, const shuffle_order_engine<_Eng, _Kp>& __y);120 121 template <class _CharT, class _Traits, class _Eng, size_t _Kp>122 friend basic_ostream<_CharT, _Traits>&123 operator<<(basic_ostream<_CharT, _Traits>& __os, const shuffle_order_engine<_Eng, _Kp>& __x);124 125 template <class _CharT, class _Traits, class _Eng, size_t _Kp>126 friend basic_istream<_CharT, _Traits>&127 operator>>(basic_istream<_CharT, _Traits>& __is, shuffle_order_engine<_Eng, _Kp>& __x);128 129 _LIBCPP_HIDE_FROM_ABI void __init() {130 for (size_t __i = 0; __i < __k; ++__i)131 __v_[__i] = __e_();132 __y_ = __e_();133 }134 135 _LIBCPP_HIDE_FROM_ABI result_type __eval(false_type) { return __eval2(integral_constant<bool, __k & 1>()); }136 _LIBCPP_HIDE_FROM_ABI result_type __eval(true_type) { return __eval(__uratio<__k, _Rp>()); }137 138 _LIBCPP_HIDE_FROM_ABI result_type __eval2(false_type) { return __eval(__uratio<__k / 2, 0x8000000000000000ull>()); }139 _LIBCPP_HIDE_FROM_ABI result_type __eval2(true_type) { return __evalf<__k, 0>(); }140 141 template <uint64_t _Np,142 uint64_t _Dp,143 __enable_if_t<(__uratio<_Np, _Dp>::num > 0xFFFFFFFFFFFFFFFFull / (_Max - _Min)), int> = 0>144 _LIBCPP_HIDE_FROM_ABI result_type __eval(__uratio<_Np, _Dp>) {145 return __evalf<__uratio<_Np, _Dp>::num, __uratio<_Np, _Dp>::den>();146 }147 148 template <uint64_t _Np,149 uint64_t _Dp,150 __enable_if_t<__uratio<_Np, _Dp>::num <= 0xFFFFFFFFFFFFFFFFull / (_Max - _Min), int> = 0>151 _LIBCPP_HIDE_FROM_ABI result_type __eval(__uratio<_Np, _Dp>) {152 const size_t __j = static_cast<size_t>(__uratio<_Np, _Dp>::num * (__y_ - _Min) / __uratio<_Np, _Dp>::den);153 __y_ = __v_[__j];154 __v_[__j] = __e_();155 return __y_;156 }157 158 template <uint64_t __n, uint64_t __d>159 _LIBCPP_HIDE_FROM_ABI result_type __evalf() {160 const double __fp = __d == 0 ? __n / (2. * 0x8000000000000000ull) : __n / (double)__d;161 const size_t __j = static_cast<size_t>(__fp * (__y_ - _Min));162 __y_ = __v_[__j];163 __v_[__j] = __e_();164 return __y_;165 }166};167 168template <class _Engine, size_t __k>169const size_t shuffle_order_engine<_Engine, __k>::table_size;170 171template <class _Eng, size_t _Kp>172_LIBCPP_HIDE_FROM_ABI bool173operator==(const shuffle_order_engine<_Eng, _Kp>& __x, const shuffle_order_engine<_Eng, _Kp>& __y) {174 return __x.__y_ == __y.__y_ && std::equal(__x.__v_, __x.__v_ + _Kp, __y.__v_) && __x.__e_ == __y.__e_;175}176 177template <class _Eng, size_t _Kp>178inline _LIBCPP_HIDE_FROM_ABI bool179operator!=(const shuffle_order_engine<_Eng, _Kp>& __x, const shuffle_order_engine<_Eng, _Kp>& __y) {180 return !(__x == __y);181}182 183template <class _CharT, class _Traits, class _Eng, size_t _Kp>184_LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&185operator<<(basic_ostream<_CharT, _Traits>& __os, const shuffle_order_engine<_Eng, _Kp>& __x) {186 __save_flags<_CharT, _Traits> __lx(__os);187 typedef basic_ostream<_CharT, _Traits> _Ostream;188 __os.flags(_Ostream::dec | _Ostream::left);189 _CharT __sp = __os.widen(' ');190 __os.fill(__sp);191 __os << __x.__e_ << __sp << __x.__v_[0];192 for (size_t __i = 1; __i < _Kp; ++__i)193 __os << __sp << __x.__v_[__i];194 return __os << __sp << __x.__y_;195}196 197template <class _CharT, class _Traits, class _Eng, size_t _Kp>198_LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&199operator>>(basic_istream<_CharT, _Traits>& __is, shuffle_order_engine<_Eng, _Kp>& __x) {200 typedef typename shuffle_order_engine<_Eng, _Kp>::result_type result_type;201 __save_flags<_CharT, _Traits> __lx(__is);202 typedef basic_istream<_CharT, _Traits> _Istream;203 __is.flags(_Istream::dec | _Istream::skipws);204 _Eng __e;205 result_type __vp[_Kp + 1];206 __is >> __e;207 for (size_t __i = 0; __i < _Kp + 1; ++__i)208 __is >> __vp[__i];209 if (!__is.fail()) {210 __x.__e_ = __e;211 for (size_t __i = 0; __i < _Kp; ++__i)212 __x.__v_[__i] = __vp[__i];213 __x.__y_ = __vp[_Kp];214 }215 return __is;216}217 218_LIBCPP_END_NAMESPACE_STD219 220_LIBCPP_POP_MACROS221 222#endif // _LIBCPP___CXX03___RANDOM_SHUFFLE_ORDER_ENGINE_H223