v1/__random/discrete_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___RANDOM_DISCRETE_DISTRIBUTION_H
0010 #define _LIBCPP___RANDOM_DISCRETE_DISTRIBUTION_H
0011
0012 #include <__algorithm/upper_bound.h>
0013 #include <__config>
0014 #include <__random/is_valid.h>
0015 #include <__random/uniform_real_distribution.h>
0016 #include <__vector/vector.h>
0017 #include <initializer_list>
0018 #include <iosfwd>
0019 #include <numeric>
0020
0021 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0022 #  pragma GCC system_header
0023 #endif
0024
0025 _LIBCPP_PUSH_MACROS
0026 #include <__undef_macros>
0027
0028 _LIBCPP_BEGIN_NAMESPACE_STD
0029
0030 template <class _IntType = int>
0031 class _LIBCPP_TEMPLATE_VIS discrete_distribution {
0032   static_assert(__libcpp_random_is_valid_inttype<_IntType>::value, "IntType must be a supported integer type");
0033
0034 public:
0035   // types
0036   typedef _IntType result_type;
0037
0038   class _LIBCPP_TEMPLATE_VIS param_type {
0039     vector<double> __p_;
0040
0041   public:
0042     typedef discrete_distribution distribution_type;
0043
0044     _LIBCPP_HIDE_FROM_ABI param_type() {}
0045     template <class _InputIterator>
0046     _LIBCPP_HIDE_FROM_ABI param_type(_InputIterator __f, _InputIterator __l) : __p_(__f, __l) {
0047       __init();
0048     }
0049 #ifndef _LIBCPP_CXX03_LANG
0050     _LIBCPP_HIDE_FROM_ABI param_type(initializer_list<double> __wl) : __p_(__wl.begin(), __wl.end()) { __init(); }
0051 #endif // _LIBCPP_CXX03_LANG
0052     template <class _UnaryOperation>
0053     _LIBCPP_HIDE_FROM_ABI param_type(size_t __nw, double __xmin, double __xmax, _UnaryOperation __fw);
0054
0055     _LIBCPP_HIDE_FROM_ABI vector<double> probabilities() const;
0056
0057     friend _LIBCPP_HIDE_FROM_ABI bool operator==(const param_type& __x, const param_type& __y) {
0058       return __x.__p_ == __y.__p_;
0059     }
0060     friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const param_type& __x, const param_type& __y) { return !(__x == __y); }
0061
0062   private:
0063     _LIBCPP_HIDE_FROM_ABI void __init();
0064
0065     friend class discrete_distribution;
0066
0067     template <class _CharT, class _Traits, class _IT>
0068     friend basic_ostream<_CharT, _Traits>&
0069     operator<<(basic_ostream<_CharT, _Traits>& __os, const discrete_distribution<_IT>& __x);
0070
0071     template <class _CharT, class _Traits, class _IT>
0072     friend basic_istream<_CharT, _Traits>&
0073     operator>>(basic_istream<_CharT, _Traits>& __is, discrete_distribution<_IT>& __x);
0074   };
0075
0076 private:
0077   param_type __p_;
0078
0079 public:
0080   // constructor and reset functions
0081   _LIBCPP_HIDE_FROM_ABI discrete_distribution() {}
0082   template <class _InputIterator>
0083   _LIBCPP_HIDE_FROM_ABI discrete_distribution(_InputIterator __f, _InputIterator __l) : __p_(__f, __l) {}
0084 #ifndef _LIBCPP_CXX03_LANG
0085   _LIBCPP_HIDE_FROM_ABI discrete_distribution(initializer_list<double> __wl) : __p_(__wl) {}
0086 #endif // _LIBCPP_CXX03_LANG
0087   template <class _UnaryOperation>
0088   _LIBCPP_HIDE_FROM_ABI discrete_distribution(size_t __nw, double __xmin, double __xmax, _UnaryOperation __fw)
0089       : __p_(__nw, __xmin, __xmax, __fw) {}
0090   _LIBCPP_HIDE_FROM_ABI explicit discrete_distribution(const param_type& __p) : __p_(__p) {}
0091   _LIBCPP_HIDE_FROM_ABI void reset() {}
0092
0093   // generating functions
0094   template <class _URNG>
0095   _LIBCPP_HIDE_FROM_ABI result_type operator()(_URNG& __g) {
0096     return (*this)(__g, __p_);
0097   }
0098   template <class _URNG>
0099   _LIBCPP_HIDE_FROM_ABI result_type operator()(_URNG& __g, const param_type& __p);
0100
0101   // property functions
0102   _LIBCPP_HIDE_FROM_ABI vector<double> probabilities() const { return __p_.probabilities(); }
0103
0104   _LIBCPP_HIDE_FROM_ABI param_type param() const { return __p_; }
0105   _LIBCPP_HIDE_FROM_ABI void param(const param_type& __p) { __p_ = __p; }
0106
0107   _LIBCPP_HIDE_FROM_ABI result_type min() const { return 0; }
0108   _LIBCPP_HIDE_FROM_ABI result_type max() const { return __p_.__p_.size(); }
0109
0110   friend _LIBCPP_HIDE_FROM_ABI bool operator==(const discrete_distribution& __x, const discrete_distribution& __y) {
0111     return __x.__p_ == __y.__p_;
0112   }
0113   friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const discrete_distribution& __x, const discrete_distribution& __y) {
0114     return !(__x == __y);
0115   }
0116
0117   template <class _CharT, class _Traits, class _IT>
0118   friend basic_ostream<_CharT, _Traits>&
0119   operator<<(basic_ostream<_CharT, _Traits>& __os, const discrete_distribution<_IT>& __x);
0120
0121   template <class _CharT, class _Traits, class _IT>
0122   friend basic_istream<_CharT, _Traits>&
0123   operator>>(basic_istream<_CharT, _Traits>& __is, discrete_distribution<_IT>& __x);
0124 };
0125
0126 template <class _IntType>
0127 template <class _UnaryOperation>
0128 discrete_distribution<_IntType>::param_type::param_type(
0129     size_t __nw, double __xmin, double __xmax, _UnaryOperation __fw) {
0130   if (__nw > 1) {
0131     __p_.reserve(__nw - 1);
0132     double __d  = (__xmax - __xmin) / __nw;
0133     double __d2 = __d / 2;
0134     for (size_t __k = 0; __k < __nw; ++__k)
0135       __p_.push_back(__fw(__xmin + __k * __d + __d2));
0136     __init();
0137   }
0138 }
0139
0140 template <class _IntType>
0141 void discrete_distribution<_IntType>::param_type::__init() {
0142   if (!__p_.empty()) {
0143     if (__p_.size() > 1) {
0144       double __s = std::accumulate(__p_.begin(), __p_.end(), 0.0);
0145       for (vector<double>::iterator __i = __p_.begin(), __e = __p_.end(); __i < __e; ++__i)
0146         *__i /= __s;
0147       vector<double> __t(__p_.size() - 1);
0148       std::partial_sum(__p_.begin(), __p_.end() - 1, __t.begin());
0149       swap(__p_, __t);
0150     } else {
0151       __p_.clear();
0152       __p_.shrink_to_fit();
0153     }
0154   }
0155 }
0156
0157 template <class _IntType>
0158 vector<double> discrete_distribution<_IntType>::param_type::probabilities() const {
0159   size_t __n = __p_.size();
0160   vector<double> __p(__n + 1);
0161   std::adjacent_difference(__p_.begin(), __p_.end(), __p.begin());
0162   if (__n > 0)
0163     __p[__n] = 1 - __p_[__n - 1];
0164   else
0165     __p[0] = 1;
0166   return __p;
0167 }
0168
0169 template <class _IntType>
0170 template <class _URNG>
0171 _IntType discrete_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p) {
0172   static_assert(__libcpp_random_is_valid_urng<_URNG>::value, "");
0173   uniform_real_distribution<double> __gen;
0174   return static_cast<_IntType>(std::upper_bound(__p.__p_.begin(), __p.__p_.end(), __gen(__g)) - __p.__p_.begin());
0175 }
0176
0177 template <class _CharT, class _Traits, class _IT>
0178 _LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&
0179 operator<<(basic_ostream<_CharT, _Traits>& __os, const discrete_distribution<_IT>& __x) {
0180   __save_flags<_CharT, _Traits> __lx(__os);
0181   typedef basic_ostream<_CharT, _Traits> _OStream;
0182   __os.flags(_OStream::dec | _OStream::left | _OStream::fixed | _OStream::scientific);
0183   _CharT __sp = __os.widen(' ');
0184   __os.fill(__sp);
0185   size_t __n = __x.__p_.__p_.size();
0186   __os << __n;
0187   for (size_t __i = 0; __i < __n; ++__i)
0188     __os << __sp << __x.__p_.__p_[__i];
0189   return __os;
0190 }
0191
0192 template <class _CharT, class _Traits, class _IT>
0193 _LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&
0194 operator>>(basic_istream<_CharT, _Traits>& __is, discrete_distribution<_IT>& __x) {
0195   __save_flags<_CharT, _Traits> __lx(__is);
0196   typedef basic_istream<_CharT, _Traits> _Istream;
0197   __is.flags(_Istream::dec | _Istream::skipws);
0198   size_t __n;
0199   __is >> __n;
0200   vector<double> __p(__n);
0201   for (size_t __i = 0; __i < __n; ++__i)
0202     __is >> __p[__i];
0203   if (!__is.fail())
0204     swap(__x.__p_.__p_, __p);
0205   return __is;
0206 }
0207
0208 _LIBCPP_END_NAMESPACE_STD
0209
0210 _LIBCPP_POP_MACROS
0211
0212 #endif // _LIBCPP___RANDOM_DISCRETE_DISTRIBUTION_H