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