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 <__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_constant_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_constant_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_constant_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_constant_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_constant_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_constant_distribution() {} 95 template<class _InputIteratorB, class _InputIteratorW> 96 _LIBCPP_INLINE_VISIBILITY 97 piecewise_constant_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_constant_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_constant_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_constant_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_constant_distribution& __x, 149 const piecewise_constant_distribution& __y) 150 {return __x.__p_ == __y.__p_;} 151 friend _LIBCPP_INLINE_VISIBILITY 152 bool operator!=(const piecewise_constant_distribution& __x, 153 const piecewise_constant_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_constant_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_constant_distribution<_RT>& __x); 167 }; 168 169 template<class _RealType> 170 typename piecewise_constant_distribution<_RealType>::param_type & 171 piecewise_constant_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 template<class _RealType> 187 void 188 piecewise_constant_distribution<_RealType>::param_type::__init() 189 { 190 // __densities_ contains non-normalized areas 191 result_type __total_area = _VSTD::accumulate(__densities_.begin(), 192 __densities_.end(), 193 result_type()); 194 for (size_t __i = 0; __i < __densities_.size(); ++__i) 195 __densities_[__i] /= __total_area; 196 // __densities_ contains normalized areas 197 __areas_.assign(__densities_.size(), result_type()); 198 _VSTD::partial_sum(__densities_.begin(), __densities_.end() - 1, 199 __areas_.begin() + 1); 200 // __areas_ contains partial sums of normalized areas: [0, __densities_ - 1] 201 __densities_.back() = 1 - __areas_.back(); // correct round off error 202 for (size_t __i = 0; __i < __densities_.size(); ++__i) 203 __densities_[__i] /= (__b_[__i+1] - __b_[__i]); 204 // __densities_ now contains __densities_ 205 } 206 207 template<class _RealType> 208 piecewise_constant_distribution<_RealType>::param_type::param_type() 209 : __b_(2), 210 __densities_(1, 1.0), 211 __areas_(1, 0.0) 212 { 213 __b_[1] = 1; 214 } 215 216 template<class _RealType> 217 template<class _InputIteratorB, class _InputIteratorW> 218 piecewise_constant_distribution<_RealType>::param_type::param_type( 219 _InputIteratorB __f_b, _InputIteratorB __l_b, _InputIteratorW __f_w) 220 : __b_(__f_b, __l_b) 221 { 222 if (__b_.size() < 2) 223 { 224 __b_.resize(2); 225 __b_[0] = 0; 226 __b_[1] = 1; 227 __densities_.assign(1, 1.0); 228 __areas_.assign(1, 0.0); 229 } 230 else 231 { 232 __densities_.reserve(__b_.size() - 1); 233 for (size_t __i = 0; __i < __b_.size() - 1; ++__i, ++__f_w) 234 __densities_.push_back(*__f_w); 235 __init(); 236 } 237 } 238 239 #ifndef _LIBCPP_CXX03_LANG 240 241 template<class _RealType> 242 template<class _UnaryOperation> 243 piecewise_constant_distribution<_RealType>::param_type::param_type( 244 initializer_list<result_type> __bl, _UnaryOperation __fw) 245 : __b_(__bl.begin(), __bl.end()) 246 { 247 if (__b_.size() < 2) 248 { 249 __b_.resize(2); 250 __b_[0] = 0; 251 __b_[1] = 1; 252 __densities_.assign(1, 1.0); 253 __areas_.assign(1, 0.0); 254 } 255 else 256 { 257 __densities_.reserve(__b_.size() - 1); 258 for (size_t __i = 0; __i < __b_.size() - 1; ++__i) 259 __densities_.push_back(__fw((__b_[__i+1] + __b_[__i])*.5)); 260 __init(); 261 } 262 } 263 264 #endif // _LIBCPP_CXX03_LANG 265 266 template<class _RealType> 267 template<class _UnaryOperation> 268 piecewise_constant_distribution<_RealType>::param_type::param_type( 269 size_t __nw, result_type __xmin, result_type __xmax, _UnaryOperation __fw) 270 : __b_(__nw == 0 ? 2 : __nw + 1) 271 { 272 size_t __n = __b_.size() - 1; 273 result_type __d = (__xmax - __xmin) / __n; 274 __densities_.reserve(__n); 275 for (size_t __i = 0; __i < __n; ++__i) 276 { 277 __b_[__i] = __xmin + __i * __d; 278 __densities_.push_back(__fw(__b_[__i] + __d*.5)); 279 } 280 __b_[__n] = __xmax; 281 __init(); 282 } 283 284 template<class _RealType> 285 template<class _URNG> 286 _RealType 287 piecewise_constant_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p) 288 { 289 static_assert(__libcpp_random_is_valid_urng<_URNG>::value, ""); 290 typedef uniform_real_distribution<result_type> _Gen; 291 result_type __u = _Gen()(__g); 292 ptrdiff_t __k = _VSTD::upper_bound(__p.__areas_.begin(), __p.__areas_.end(), 293 __u) - __p.__areas_.begin() - 1; 294 return (__u - __p.__areas_[__k]) / __p.__densities_[__k] + __p.__b_[__k]; 295 } 296 297 template <class _CharT, class _Traits, class _RT> 298 _LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>& 299 operator<<(basic_ostream<_CharT, _Traits>& __os, 300 const piecewise_constant_distribution<_RT>& __x) 301 { 302 __save_flags<_CharT, _Traits> __lx(__os); 303 typedef basic_ostream<_CharT, _Traits> _OStream; 304 __os.flags(_OStream::dec | _OStream::left | _OStream::fixed | 305 _OStream::scientific); 306 _CharT __sp = __os.widen(' '); 307 __os.fill(__sp); 308 size_t __n = __x.__p_.__b_.size(); 309 __os << __n; 310 for (size_t __i = 0; __i < __n; ++__i) 311 __os << __sp << __x.__p_.__b_[__i]; 312 __n = __x.__p_.__densities_.size(); 313 __os << __sp << __n; 314 for (size_t __i = 0; __i < __n; ++__i) 315 __os << __sp << __x.__p_.__densities_[__i]; 316 __n = __x.__p_.__areas_.size(); 317 __os << __sp << __n; 318 for (size_t __i = 0; __i < __n; ++__i) 319 __os << __sp << __x.__p_.__areas_[__i]; 320 return __os; 321 } 322 323 template <class _CharT, class _Traits, class _RT> 324 _LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>& 325 operator>>(basic_istream<_CharT, _Traits>& __is, 326 piecewise_constant_distribution<_RT>& __x) 327 { 328 typedef piecewise_constant_distribution<_RT> _Eng; 329 typedef typename _Eng::result_type result_type; 330 __save_flags<_CharT, _Traits> __lx(__is); 331 typedef basic_istream<_CharT, _Traits> _Istream; 332 __is.flags(_Istream::dec | _Istream::skipws); 333 size_t __n; 334 __is >> __n; 335 vector<result_type> __b(__n); 336 for (size_t __i = 0; __i < __n; ++__i) 337 __is >> __b[__i]; 338 __is >> __n; 339 vector<result_type> __densities(__n); 340 for (size_t __i = 0; __i < __n; ++__i) 341 __is >> __densities[__i]; 342 __is >> __n; 343 vector<result_type> __areas(__n); 344 for (size_t __i = 0; __i < __n; ++__i) 345 __is >> __areas[__i]; 346 if (!__is.fail()) 347 { 348 swap(__x.__p_.__b_, __b); 349 swap(__x.__p_.__densities_, __densities); 350 swap(__x.__p_.__areas_, __areas); 351 } 352 return __is; 353 } 354 355 _LIBCPP_END_NAMESPACE_STD 356 357 _LIBCPP_POP_MACROS 358 359 #endif // _LIBCPP___RANDOM_PIECEWISE_CONSTANT_DISTRIBUTION_H 360