__cxx03/__random/piecewise_linear_distribution.h

0001 //===----------------------------------------------------------------------===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef _LIBCPP___CXX03___RANDOM_PIECEWISE_LINEAR_DISTRIBUTION_H
0010 #define _LIBCPP___CXX03___RANDOM_PIECEWISE_LINEAR_DISTRIBUTION_H
0011
0012 #include <__cxx03/__algorithm/upper_bound.h>
0013 #include <__cxx03/__config>
0014 #include <__cxx03/__random/is_valid.h>
0015 #include <__cxx03/__random/uniform_real_distribution.h>
0016 #include <__cxx03/cmath>
0017 #include <__cxx03/iosfwd>
0018 #include <__cxx03/vector>
0019
0020 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0021 #  pragma GCC system_header
0022 #endif
0023
0024 _LIBCPP_PUSH_MACROS
0025 #include <__cxx03/__undef_macros>
0026
0027 _LIBCPP_BEGIN_NAMESPACE_STD
0028
0029 template <class _RealType = double>
0030 class _LIBCPP_TEMPLATE_VIS piecewise_linear_distribution {
0031   static_assert(__libcpp_random_is_valid_realtype<_RealType>::value,
0032                 "RealType must be a supported floating-point type");
0033
0034 public:
0035   // types
0036   typedef _RealType result_type;
0037
0038   class _LIBCPP_TEMPLATE_VIS param_type {
0039     vector<result_type> __b_;
0040     vector<result_type> __densities_;
0041     vector<result_type> __areas_;
0042
0043   public:
0044     typedef piecewise_linear_distribution distribution_type;
0045
0046     _LIBCPP_HIDE_FROM_ABI param_type();
0047     template <class _InputIteratorB, class _InputIteratorW>
0048     _LIBCPP_HIDE_FROM_ABI param_type(_InputIteratorB __f_b, _InputIteratorB __l_b, _InputIteratorW __f_w);
0049 #ifndef _LIBCPP_CXX03_LANG
0050     template <class _UnaryOperation>
0051     _LIBCPP_HIDE_FROM_ABI param_type(initializer_list<result_type> __bl, _UnaryOperation __fw);
0052 #endif // _LIBCPP_CXX03_LANG
0053     template <class _UnaryOperation>
0054     _LIBCPP_HIDE_FROM_ABI param_type(size_t __nw, result_type __xmin, result_type __xmax, _UnaryOperation __fw);
0055     _LIBCPP_HIDE_FROM_ABI param_type(param_type const&) = default;
0056     _LIBCPP_HIDE_FROM_ABI param_type& operator=(const param_type& __rhs);
0057
0058     _LIBCPP_HIDE_FROM_ABI vector<result_type> intervals() const { return __b_; }
0059     _LIBCPP_HIDE_FROM_ABI vector<result_type> densities() const { return __densities_; }
0060
0061     friend _LIBCPP_HIDE_FROM_ABI bool operator==(const param_type& __x, const param_type& __y) {
0062       return __x.__densities_ == __y.__densities_ && __x.__b_ == __y.__b_;
0063     }
0064     friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const param_type& __x, const param_type& __y) { return !(__x == __y); }
0065
0066   private:
0067     _LIBCPP_HIDE_FROM_ABI void __init();
0068
0069     friend class piecewise_linear_distribution;
0070
0071     template <class _CharT, class _Traits, class _RT>
0072     friend basic_ostream<_CharT, _Traits>&
0073     operator<<(basic_ostream<_CharT, _Traits>& __os, const piecewise_linear_distribution<_RT>& __x);
0074
0075     template <class _CharT, class _Traits, class _RT>
0076     friend basic_istream<_CharT, _Traits>&
0077     operator>>(basic_istream<_CharT, _Traits>& __is, piecewise_linear_distribution<_RT>& __x);
0078   };
0079
0080 private:
0081   param_type __p_;
0082
0083 public:
0084   // constructor and reset functions
0085   _LIBCPP_HIDE_FROM_ABI piecewise_linear_distribution() {}
0086   template <class _InputIteratorB, class _InputIteratorW>
0087   _LIBCPP_HIDE_FROM_ABI
0088   piecewise_linear_distribution(_InputIteratorB __f_b, _InputIteratorB __l_b, _InputIteratorW __f_w)
0089       : __p_(__f_b, __l_b, __f_w) {}
0090
0091 #ifndef _LIBCPP_CXX03_LANG
0092   template <class _UnaryOperation>
0093   _LIBCPP_HIDE_FROM_ABI piecewise_linear_distribution(initializer_list<result_type> __bl, _UnaryOperation __fw)
0094       : __p_(__bl, __fw) {}
0095 #endif // _LIBCPP_CXX03_LANG
0096
0097   template <class _UnaryOperation>
0098   _LIBCPP_HIDE_FROM_ABI
0099   piecewise_linear_distribution(size_t __nw, result_type __xmin, result_type __xmax, _UnaryOperation __fw)
0100       : __p_(__nw, __xmin, __xmax, __fw) {}
0101
0102   _LIBCPP_HIDE_FROM_ABI explicit piecewise_linear_distribution(const param_type& __p) : __p_(__p) {}
0103
0104   _LIBCPP_HIDE_FROM_ABI void reset() {}
0105
0106   // generating functions
0107   template <class _URNG>
0108   _LIBCPP_HIDE_FROM_ABI result_type operator()(_URNG& __g) {
0109     return (*this)(__g, __p_);
0110   }
0111   template <class _URNG>
0112   _LIBCPP_HIDE_FROM_ABI result_type operator()(_URNG& __g, const param_type& __p);
0113
0114   // property functions
0115   _LIBCPP_HIDE_FROM_ABI vector<result_type> intervals() const { return __p_.intervals(); }
0116   _LIBCPP_HIDE_FROM_ABI vector<result_type> densities() const { return __p_.densities(); }
0117
0118   _LIBCPP_HIDE_FROM_ABI param_type param() const { return __p_; }
0119   _LIBCPP_HIDE_FROM_ABI void param(const param_type& __p) { __p_ = __p; }
0120
0121   _LIBCPP_HIDE_FROM_ABI result_type min() const { return __p_.__b_.front(); }
0122   _LIBCPP_HIDE_FROM_ABI result_type max() const { return __p_.__b_.back(); }
0123
0124   friend _LIBCPP_HIDE_FROM_ABI bool
0125   operator==(const piecewise_linear_distribution& __x, const piecewise_linear_distribution& __y) {
0126     return __x.__p_ == __y.__p_;
0127   }
0128   friend _LIBCPP_HIDE_FROM_ABI bool
0129   operator!=(const piecewise_linear_distribution& __x, const piecewise_linear_distribution& __y) {
0130     return !(__x == __y);
0131   }
0132
0133   template <class _CharT, class _Traits, class _RT>
0134   friend basic_ostream<_CharT, _Traits>&
0135   operator<<(basic_ostream<_CharT, _Traits>& __os, const piecewise_linear_distribution<_RT>& __x);
0136
0137   template <class _CharT, class _Traits, class _RT>
0138   friend basic_istream<_CharT, _Traits>&
0139   operator>>(basic_istream<_CharT, _Traits>& __is, piecewise_linear_distribution<_RT>& __x);
0140 };
0141
0142 template <class _RealType>
0143 typename piecewise_linear_distribution<_RealType>::param_type&
0144 piecewise_linear_distribution<_RealType>::param_type::operator=(const param_type& __rhs) {
0145   //  These can throw
0146   __b_.reserve(__rhs.__b_.size());
0147   __densities_.reserve(__rhs.__densities_.size());
0148   __areas_.reserve(__rhs.__areas_.size());
0149
0150   //  These can not throw
0151   __b_         = __rhs.__b_;
0152   __densities_ = __rhs.__densities_;
0153   __areas_     = __rhs.__areas_;
0154   return *this;
0155 }
0156
0157 template <class _RealType>
0158 void piecewise_linear_distribution<_RealType>::param_type::__init() {
0159   __areas_.assign(__densities_.size() - 1, result_type());
0160   result_type __sp = 0;
0161   for (size_t __i = 0; __i < __areas_.size(); ++__i) {
0162     __areas_[__i] = (__densities_[__i + 1] + __densities_[__i]) * (__b_[__i + 1] - __b_[__i]) * .5;
0163     __sp += __areas_[__i];
0164   }
0165   for (size_t __i = __areas_.size(); __i > 1;) {
0166     --__i;
0167     __areas_[__i] = __areas_[__i - 1] / __sp;
0168   }
0169   __areas_[0] = 0;
0170   for (size_t __i = 1; __i < __areas_.size(); ++__i)
0171     __areas_[__i] += __areas_[__i - 1];
0172   for (size_t __i = 0; __i < __densities_.size(); ++__i)
0173     __densities_[__i] /= __sp;
0174 }
0175
0176 template <class _RealType>
0177 piecewise_linear_distribution<_RealType>::param_type::param_type() : __b_(2), __densities_(2, 1.0), __areas_(1, 0.0) {
0178   __b_[1] = 1;
0179 }
0180
0181 template <class _RealType>
0182 template <class _InputIteratorB, class _InputIteratorW>
0183 piecewise_linear_distribution<_RealType>::param_type::param_type(
0184     _InputIteratorB __f_b, _InputIteratorB __l_b, _InputIteratorW __f_w)
0185     : __b_(__f_b, __l_b) {
0186   if (__b_.size() < 2) {
0187     __b_.resize(2);
0188     __b_[0] = 0;
0189     __b_[1] = 1;
0190     __densities_.assign(2, 1.0);
0191     __areas_.assign(1, 0.0);
0192   } else {
0193     __densities_.reserve(__b_.size());
0194     for (size_t __i = 0; __i < __b_.size(); ++__i, ++__f_w)
0195       __densities_.push_back(*__f_w);
0196     __init();
0197   }
0198 }
0199
0200 #ifndef _LIBCPP_CXX03_LANG
0201
0202 template <class _RealType>
0203 template <class _UnaryOperation>
0204 piecewise_linear_distribution<_RealType>::param_type::param_type(
0205     initializer_list<result_type> __bl, _UnaryOperation __fw)
0206     : __b_(__bl.begin(), __bl.end()) {
0207   if (__b_.size() < 2) {
0208     __b_.resize(2);
0209     __b_[0] = 0;
0210     __b_[1] = 1;
0211     __densities_.assign(2, 1.0);
0212     __areas_.assign(1, 0.0);
0213   } else {
0214     __densities_.reserve(__b_.size());
0215     for (size_t __i = 0; __i < __b_.size(); ++__i)
0216       __densities_.push_back(__fw(__b_[__i]));
0217     __init();
0218   }
0219 }
0220
0221 #endif // _LIBCPP_CXX03_LANG
0222
0223 template <class _RealType>
0224 template <class _UnaryOperation>
0225 piecewise_linear_distribution<_RealType>::param_type::param_type(
0226     size_t __nw, result_type __xmin, result_type __xmax, _UnaryOperation __fw)
0227     : __b_(__nw == 0 ? 2 : __nw + 1) {
0228   size_t __n      = __b_.size() - 1;
0229   result_type __d = (__xmax - __xmin) / __n;
0230   __densities_.reserve(__b_.size());
0231   for (size_t __i = 0; __i < __n; ++__i) {
0232     __b_[__i] = __xmin + __i * __d;
0233     __densities_.push_back(__fw(__b_[__i]));
0234   }
0235   __b_[__n] = __xmax;
0236   __densities_.push_back(__fw(__b_[__n]));
0237   __init();
0238 }
0239
0240 template <class _RealType>
0241 template <class _URNG>
0242 _RealType piecewise_linear_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p) {
0243   static_assert(__libcpp_random_is_valid_urng<_URNG>::value, "");
0244   typedef uniform_real_distribution<result_type> _Gen;
0245   result_type __u = _Gen()(__g);
0246   ptrdiff_t __k   = std::upper_bound(__p.__areas_.begin(), __p.__areas_.end(), __u) - __p.__areas_.begin() - 1;
0247   __u -= __p.__areas_[__k];
0248   const result_type __dk     = __p.__densities_[__k];
0249   const result_type __dk1    = __p.__densities_[__k + 1];
0250   const result_type __deltad = __dk1 - __dk;
0251   const result_type __bk     = __p.__b_[__k];
0252   if (__deltad == 0)
0253     return __u / __dk + __bk;
0254   const result_type __bk1    = __p.__b_[__k + 1];
0255   const result_type __deltab = __bk1 - __bk;
0256   return (__bk * __dk1 - __bk1 * __dk + std::sqrt(__deltab * (__deltab * __dk * __dk + 2 * __deltad * __u))) / __deltad;
0257 }
0258
0259 template <class _CharT, class _Traits, class _RT>
0260 _LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&
0261 operator<<(basic_ostream<_CharT, _Traits>& __os, const piecewise_linear_distribution<_RT>& __x) {
0262   __save_flags<_CharT, _Traits> __lx(__os);
0263   typedef basic_ostream<_CharT, _Traits> _OStream;
0264   __os.flags(_OStream::dec | _OStream::left | _OStream::fixed | _OStream::scientific);
0265   _CharT __sp = __os.widen(' ');
0266   __os.fill(__sp);
0267   size_t __n = __x.__p_.__b_.size();
0268   __os << __n;
0269   for (size_t __i = 0; __i < __n; ++__i)
0270     __os << __sp << __x.__p_.__b_[__i];
0271   __n = __x.__p_.__densities_.size();
0272   __os << __sp << __n;
0273   for (size_t __i = 0; __i < __n; ++__i)
0274     __os << __sp << __x.__p_.__densities_[__i];
0275   __n = __x.__p_.__areas_.size();
0276   __os << __sp << __n;
0277   for (size_t __i = 0; __i < __n; ++__i)
0278     __os << __sp << __x.__p_.__areas_[__i];
0279   return __os;
0280 }
0281
0282 template <class _CharT, class _Traits, class _RT>
0283 _LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&
0284 operator>>(basic_istream<_CharT, _Traits>& __is, piecewise_linear_distribution<_RT>& __x) {
0285   typedef piecewise_linear_distribution<_RT> _Eng;
0286   typedef typename _Eng::result_type result_type;
0287   __save_flags<_CharT, _Traits> __lx(__is);
0288   typedef basic_istream<_CharT, _Traits> _Istream;
0289   __is.flags(_Istream::dec | _Istream::skipws);
0290   size_t __n;
0291   __is >> __n;
0292   vector<result_type> __b(__n);
0293   for (size_t __i = 0; __i < __n; ++__i)
0294     __is >> __b[__i];
0295   __is >> __n;
0296   vector<result_type> __densities(__n);
0297   for (size_t __i = 0; __i < __n; ++__i)
0298     __is >> __densities[__i];
0299   __is >> __n;
0300   vector<result_type> __areas(__n);
0301   for (size_t __i = 0; __i < __n; ++__i)
0302     __is >> __areas[__i];
0303   if (!__is.fail()) {
0304     swap(__x.__p_.__b_, __b);
0305     swap(__x.__p_.__densities_, __densities);
0306     swap(__x.__p_.__areas_, __areas);
0307   }
0308   return __is;
0309 }
0310
0311 _LIBCPP_END_NAMESPACE_STD
0312
0313 _LIBCPP_POP_MACROS
0314
0315 #endif // _LIBCPP___CXX03___RANDOM_PIECEWISE_LINEAR_DISTRIBUTION_H