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