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_PIECEWISE_CONSTANT_DISTRIBUTION_H 10 #define _LIBCPP___RANDOM_PIECEWISE_CONSTANT_DISTRIBUTION_H 11 12 #include <__algorithm/upper_bound.h> 13 #include <__config> 14 #include <__cstddef/ptrdiff_t.h> 15 #include <__random/is_valid.h> 16 #include <__random/uniform_real_distribution.h> 17 #include <__vector/vector.h> 18 #include <initializer_list> 19 #include <iosfwd> 20 #include <numeric> 21 22 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 23 # pragma GCC system_header 24 #endif 25 26 _LIBCPP_PUSH_MACROS 27 #include <__undef_macros> 28 29 _LIBCPP_BEGIN_NAMESPACE_STD 30 31 template <class _RealType = double> 32 class _LIBCPP_TEMPLATE_VIS piecewise_constant_distribution { 33 static_assert(__libcpp_random_is_valid_realtype<_RealType>::value, 34 "RealType must be a supported floating-point type"); 35 36 public: 37 // types 38 typedef _RealType result_type; 39 40 class _LIBCPP_TEMPLATE_VIS param_type { 41 vector<result_type> __b_; 42 vector<result_type> __densities_; 43 vector<result_type> __areas_; 44 45 public: 46 typedef piecewise_constant_distribution distribution_type; 47 48 _LIBCPP_HIDE_FROM_ABI param_type(); 49 template <class _InputIteratorB, class _InputIteratorW> 50 _LIBCPP_HIDE_FROM_ABI param_type(_InputIteratorB __f_b, _InputIteratorB __l_b, _InputIteratorW __f_w); 51 #ifndef _LIBCPP_CXX03_LANG 52 template <class _UnaryOperation> 53 _LIBCPP_HIDE_FROM_ABI param_type(initializer_list<result_type> __bl, _UnaryOperation __fw); 54 #endif // _LIBCPP_CXX03_LANG 55 template <class _UnaryOperation> 56 _LIBCPP_HIDE_FROM_ABI param_type(size_t __nw, result_type __xmin, result_type __xmax, _UnaryOperation __fw); 57 _LIBCPP_HIDE_FROM_ABI param_type(param_type const&) = default; 58 _LIBCPP_HIDE_FROM_ABI param_type& operator=(const param_type& __rhs); 59 60 _LIBCPP_HIDE_FROM_ABI vector<result_type> intervals() const { return __b_; } 61 _LIBCPP_HIDE_FROM_ABI vector<result_type> densities() const { return __densities_; } 62 63 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const param_type& __x, const param_type& __y) { 64 return __x.__densities_ == __y.__densities_ && __x.__b_ == __y.__b_; 65 } 66 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const param_type& __x, const param_type& __y) { return !(__x == __y); } 67 68 private: 69 _LIBCPP_HIDE_FROM_ABI void __init(); 70 71 friend class piecewise_constant_distribution; 72 73 template <class _CharT, class _Traits, class _RT> 74 friend basic_ostream<_CharT, _Traits>& 75 operator<<(basic_ostream<_CharT, _Traits>& __os, const piecewise_constant_distribution<_RT>& __x); 76 77 template <class _CharT, class _Traits, class _RT> 78 friend basic_istream<_CharT, _Traits>& 79 operator>>(basic_istream<_CharT, _Traits>& __is, piecewise_constant_distribution<_RT>& __x); 80 }; 81 82 private: 83 param_type __p_; 84 85 public: 86 // constructor and reset functions 87 _LIBCPP_HIDE_FROM_ABI piecewise_constant_distribution() {} 88 template <class _InputIteratorB, class _InputIteratorW> 89 _LIBCPP_HIDE_FROM_ABI 90 piecewise_constant_distribution(_InputIteratorB __f_b, _InputIteratorB __l_b, _InputIteratorW __f_w) 91 : __p_(__f_b, __l_b, __f_w) {} 92 93 #ifndef _LIBCPP_CXX03_LANG 94 template <class _UnaryOperation> 95 _LIBCPP_HIDE_FROM_ABI piecewise_constant_distribution(initializer_list<result_type> __bl, _UnaryOperation __fw) 96 : __p_(__bl, __fw) {} 97 #endif // _LIBCPP_CXX03_LANG 98 99 template <class _UnaryOperation> 100 _LIBCPP_HIDE_FROM_ABI 101 piecewise_constant_distribution(size_t __nw, result_type __xmin, result_type __xmax, _UnaryOperation __fw) 102 : __p_(__nw, __xmin, __xmax, __fw) {} 103 104 _LIBCPP_HIDE_FROM_ABI explicit piecewise_constant_distribution(const param_type& __p) : __p_(__p) {} 105 106 _LIBCPP_HIDE_FROM_ABI void reset() {} 107 108 // generating functions 109 template <class _URNG> 110 _LIBCPP_HIDE_FROM_ABI result_type operator()(_URNG& __g) { 111 return (*this)(__g, __p_); 112 } 113 template <class _URNG> 114 _LIBCPP_HIDE_FROM_ABI result_type operator()(_URNG& __g, const param_type& __p); 115 116 // property functions 117 _LIBCPP_HIDE_FROM_ABI vector<result_type> intervals() const { return __p_.intervals(); } 118 _LIBCPP_HIDE_FROM_ABI vector<result_type> densities() const { return __p_.densities(); } 119 120 _LIBCPP_HIDE_FROM_ABI param_type param() const { return __p_; } 121 _LIBCPP_HIDE_FROM_ABI void param(const param_type& __p) { __p_ = __p; } 122 123 _LIBCPP_HIDE_FROM_ABI result_type min() const { return __p_.__b_.front(); } 124 _LIBCPP_HIDE_FROM_ABI result_type max() const { return __p_.__b_.back(); } 125 126 friend _LIBCPP_HIDE_FROM_ABI bool 127 operator==(const piecewise_constant_distribution& __x, const piecewise_constant_distribution& __y) { 128 return __x.__p_ == __y.__p_; 129 } 130 friend _LIBCPP_HIDE_FROM_ABI bool 131 operator!=(const piecewise_constant_distribution& __x, const piecewise_constant_distribution& __y) { 132 return !(__x == __y); 133 } 134 135 template <class _CharT, class _Traits, class _RT> 136 friend basic_ostream<_CharT, _Traits>& 137 operator<<(basic_ostream<_CharT, _Traits>& __os, const piecewise_constant_distribution<_RT>& __x); 138 139 template <class _CharT, class _Traits, class _RT> 140 friend basic_istream<_CharT, _Traits>& 141 operator>>(basic_istream<_CharT, _Traits>& __is, piecewise_constant_distribution<_RT>& __x); 142 }; 143 144 template <class _RealType> 145 typename piecewise_constant_distribution<_RealType>::param_type& 146 piecewise_constant_distribution<_RealType>::param_type::operator=(const param_type& __rhs) { 147 // These can throw 148 __b_.reserve(__rhs.__b_.size()); 149 __densities_.reserve(__rhs.__densities_.size()); 150 __areas_.reserve(__rhs.__areas_.size()); 151 152 // These can not throw 153 __b_ = __rhs.__b_; 154 __densities_ = __rhs.__densities_; 155 __areas_ = __rhs.__areas_; 156 return *this; 157 } 158 159 template <class _RealType> 160 void piecewise_constant_distribution<_RealType>::param_type::__init() { 161 // __densities_ contains non-normalized areas 162 result_type __total_area = std::accumulate(__densities_.begin(), __densities_.end(), result_type()); 163 for (size_t __i = 0; __i < __densities_.size(); ++__i) 164 __densities_[__i] /= __total_area; 165 // __densities_ contains normalized areas 166 __areas_.assign(__densities_.size(), result_type()); 167 std::partial_sum(__densities_.begin(), __densities_.end() - 1, __areas_.begin() + 1); 168 // __areas_ contains partial sums of normalized areas: [0, __densities_ - 1] 169 __densities_.back() = 1 - __areas_.back(); // correct round off error 170 for (size_t __i = 0; __i < __densities_.size(); ++__i) 171 __densities_[__i] /= (__b_[__i + 1] - __b_[__i]); 172 // __densities_ now contains __densities_ 173 } 174 175 template <class _RealType> 176 piecewise_constant_distribution<_RealType>::param_type::param_type() : __b_(2), __densities_(1, 1.0), __areas_(1, 0.0) { 177 __b_[1] = 1; 178 } 179 180 template <class _RealType> 181 template <class _InputIteratorB, class _InputIteratorW> 182 piecewise_constant_distribution<_RealType>::param_type::param_type( 183 _InputIteratorB __f_b, _InputIteratorB __l_b, _InputIteratorW __f_w) 184 : __b_(__f_b, __l_b) { 185 if (__b_.size() < 2) { 186 __b_.resize(2); 187 __b_[0] = 0; 188 __b_[1] = 1; 189 __densities_.assign(1, 1.0); 190 __areas_.assign(1, 0.0); 191 } else { 192 __densities_.reserve(__b_.size() - 1); 193 for (size_t __i = 0; __i < __b_.size() - 1; ++__i, ++__f_w) 194 __densities_.push_back(*__f_w); 195 __init(); 196 } 197 } 198 199 #ifndef _LIBCPP_CXX03_LANG 200 201 template <class _RealType> 202 template <class _UnaryOperation> 203 piecewise_constant_distribution<_RealType>::param_type::param_type( 204 initializer_list<result_type> __bl, _UnaryOperation __fw) 205 : __b_(__bl.begin(), __bl.end()) { 206 if (__b_.size() < 2) { 207 __b_.resize(2); 208 __b_[0] = 0; 209 __b_[1] = 1; 210 __densities_.assign(1, 1.0); 211 __areas_.assign(1, 0.0); 212 } else { 213 __densities_.reserve(__b_.size() - 1); 214 for (size_t __i = 0; __i < __b_.size() - 1; ++__i) 215 __densities_.push_back(__fw((__b_[__i + 1] + __b_[__i]) * .5)); 216 __init(); 217 } 218 } 219 220 #endif // _LIBCPP_CXX03_LANG 221 222 template <class _RealType> 223 template <class _UnaryOperation> 224 piecewise_constant_distribution<_RealType>::param_type::param_type( 225 size_t __nw, result_type __xmin, result_type __xmax, _UnaryOperation __fw) 226 : __b_(__nw == 0 ? 2 : __nw + 1) { 227 size_t __n = __b_.size() - 1; 228 result_type __d = (__xmax - __xmin) / __n; 229 __densities_.reserve(__n); 230 for (size_t __i = 0; __i < __n; ++__i) { 231 __b_[__i] = __xmin + __i * __d; 232 __densities_.push_back(__fw(__b_[__i] + __d * .5)); 233 } 234 __b_[__n] = __xmax; 235 __init(); 236 } 237 238 template <class _RealType> 239 template <class _URNG> 240 _RealType piecewise_constant_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p) { 241 static_assert(__libcpp_random_is_valid_urng<_URNG>::value, ""); 242 typedef uniform_real_distribution<result_type> _Gen; 243 result_type __u = _Gen()(__g); 244 ptrdiff_t __k = std::upper_bound(__p.__areas_.begin(), __p.__areas_.end(), __u) - __p.__areas_.begin() - 1; 245 return (__u - __p.__areas_[__k]) / __p.__densities_[__k] + __p.__b_[__k]; 246 } 247 248 template <class _CharT, class _Traits, class _RT> 249 _LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>& 250 operator<<(basic_ostream<_CharT, _Traits>& __os, const piecewise_constant_distribution<_RT>& __x) { 251 __save_flags<_CharT, _Traits> __lx(__os); 252 typedef basic_ostream<_CharT, _Traits> _OStream; 253 __os.flags(_OStream::dec | _OStream::left | _OStream::fixed | _OStream::scientific); 254 _CharT __sp = __os.widen(' '); 255 __os.fill(__sp); 256 size_t __n = __x.__p_.__b_.size(); 257 __os << __n; 258 for (size_t __i = 0; __i < __n; ++__i) 259 __os << __sp << __x.__p_.__b_[__i]; 260 __n = __x.__p_.__densities_.size(); 261 __os << __sp << __n; 262 for (size_t __i = 0; __i < __n; ++__i) 263 __os << __sp << __x.__p_.__densities_[__i]; 264 __n = __x.__p_.__areas_.size(); 265 __os << __sp << __n; 266 for (size_t __i = 0; __i < __n; ++__i) 267 __os << __sp << __x.__p_.__areas_[__i]; 268 return __os; 269 } 270 271 template <class _CharT, class _Traits, class _RT> 272 _LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>& 273 operator>>(basic_istream<_CharT, _Traits>& __is, piecewise_constant_distribution<_RT>& __x) { 274 typedef piecewise_constant_distribution<_RT> _Eng; 275 typedef typename _Eng::result_type result_type; 276 __save_flags<_CharT, _Traits> __lx(__is); 277 typedef basic_istream<_CharT, _Traits> _Istream; 278 __is.flags(_Istream::dec | _Istream::skipws); 279 size_t __n; 280 __is >> __n; 281 vector<result_type> __b(__n); 282 for (size_t __i = 0; __i < __n; ++__i) 283 __is >> __b[__i]; 284 __is >> __n; 285 vector<result_type> __densities(__n); 286 for (size_t __i = 0; __i < __n; ++__i) 287 __is >> __densities[__i]; 288 __is >> __n; 289 vector<result_type> __areas(__n); 290 for (size_t __i = 0; __i < __n; ++__i) 291 __is >> __areas[__i]; 292 if (!__is.fail()) { 293 swap(__x.__p_.__b_, __b); 294 swap(__x.__p_.__densities_, __densities); 295 swap(__x.__p_.__areas_, __areas); 296 } 297 return __is; 298 } 299 300 _LIBCPP_END_NAMESPACE_STD 301 302 _LIBCPP_POP_MACROS 303 304 #endif // _LIBCPP___RANDOM_PIECEWISE_CONSTANT_DISTRIBUTION_H 305