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