overby.me
this repo has no description
1// -*- C++ -*-
2//===--------------------------- random -----------------------------------===//
3//
4// The LLVM Compiler Infrastructure
5//
6// This file is dual licensed under the MIT and the University of Illinois Open
7// Source Licenses. See LICENSE.TXT for details.
8//
9//===----------------------------------------------------------------------===//
10
11#ifndef _LIBCPP_RANDOM
12#define _LIBCPP_RANDOM
13
14/*
15 random synopsis
16
17#include <initializer_list>
18
19namespace std
20{
21
22// Engines
23
24template <class UIntType, UIntType a, UIntType c, UIntType m>
25class linear_congruential_engine
26{
27public:
28 // types
29 typedef UIntType result_type;
30
31 // engine characteristics
32 static constexpr result_type multiplier = a;
33 static constexpr result_type increment = c;
34 static constexpr result_type modulus = m;
35 static constexpr result_type min() { return c == 0u ? 1u: 0u;}
36 static constexpr result_type max() { return m - 1u;}
37 static constexpr result_type default_seed = 1u;
38
39 // constructors and seeding functions
40 explicit linear_congruential_engine(result_type s = default_seed);
41 template<class Sseq> explicit linear_congruential_engine(Sseq& q);
42 void seed(result_type s = default_seed);
43 template<class Sseq> void seed(Sseq& q);
44
45 // generating functions
46 result_type operator()();
47 void discard(unsigned long long z);
48};
49
50template <class UIntType, UIntType a, UIntType c, UIntType m>
51bool
52operator==(const linear_congruential_engine<UIntType, a, c, m>& x,
53 const linear_congruential_engine<UIntType, a, c, m>& y);
54
55template <class UIntType, UIntType a, UIntType c, UIntType m>
56bool
57operator!=(const linear_congruential_engine<UIntType, a, c, m>& x,
58 const linear_congruential_engine<UIntType, a, c, m>& y);
59
60template <class charT, class traits,
61 class UIntType, UIntType a, UIntType c, UIntType m>
62basic_ostream<charT, traits>&
63operator<<(basic_ostream<charT, traits>& os,
64 const linear_congruential_engine<UIntType, a, c, m>& x);
65
66template <class charT, class traits,
67 class UIntType, UIntType a, UIntType c, UIntType m>
68basic_istream<charT, traits>&
69operator>>(basic_istream<charT, traits>& is,
70 linear_congruential_engine<UIntType, a, c, m>& x);
71
72template <class UIntType, size_t w, size_t n, size_t m, size_t r,
73 UIntType a, size_t u, UIntType d, size_t s,
74 UIntType b, size_t t, UIntType c, size_t l, UIntType f>
75class mersenne_twister_engine
76{
77public:
78 // types
79 typedef UIntType result_type;
80
81 // engine characteristics
82 static constexpr size_t word_size = w;
83 static constexpr size_t state_size = n;
84 static constexpr size_t shift_size = m;
85 static constexpr size_t mask_bits = r;
86 static constexpr result_type xor_mask = a;
87 static constexpr size_t tempering_u = u;
88 static constexpr result_type tempering_d = d;
89 static constexpr size_t tempering_s = s;
90 static constexpr result_type tempering_b = b;
91 static constexpr size_t tempering_t = t;
92 static constexpr result_type tempering_c = c;
93 static constexpr size_t tempering_l = l;
94 static constexpr result_type initialization_multiplier = f;
95 static constexpr result_type min () { return 0; }
96 static constexpr result_type max() { return 2^w - 1; }
97 static constexpr result_type default_seed = 5489u;
98
99 // constructors and seeding functions
100 explicit mersenne_twister_engine(result_type value = default_seed);
101 template<class Sseq> explicit mersenne_twister_engine(Sseq& q);
102 void seed(result_type value = default_seed);
103 template<class Sseq> void seed(Sseq& q);
104
105 // generating functions
106 result_type operator()();
107 void discard(unsigned long long z);
108};
109
110template <class UIntType, size_t w, size_t n, size_t m, size_t r,
111 UIntType a, size_t u, UIntType d, size_t s,
112 UIntType b, size_t t, UIntType c, size_t l, UIntType f>
113bool
114operator==(
115 const mersenne_twister_engine<UIntType, w, n, m, r, a, u, d, s, b, t, c, l, f>& x,
116 const mersenne_twister_engine<UIntType, w, n, m, r, a, u, d, s, b, t, c, l, f>& y);
117
118template <class UIntType, size_t w, size_t n, size_t m, size_t r,
119 UIntType a, size_t u, UIntType d, size_t s,
120 UIntType b, size_t t, UIntType c, size_t l, UIntType f>
121bool
122operator!=(
123 const mersenne_twister_engine<UIntType, w, n, m, r, a, u, d, s, b, t, c, l, f>& x,
124 const mersenne_twister_engine<UIntType, w, n, m, r, a, u, d, s, b, t, c, l, f>& y);
125
126template <class charT, class traits,
127 class UIntType, size_t w, size_t n, size_t m, size_t r,
128 UIntType a, size_t u, UIntType d, size_t s,
129 UIntType b, size_t t, UIntType c, size_t l, UIntType f>
130basic_ostream<charT, traits>&
131operator<<(basic_ostream<charT, traits>& os,
132 const mersenne_twister_engine<UIntType, w, n, m, r, a, u, d, s, b, t, c, l, f>& x);
133
134template <class charT, class traits,
135 class UIntType, size_t w, size_t n, size_t m, size_t r,
136 UIntType a, size_t u, UIntType d, size_t s,
137 UIntType b, size_t t, UIntType c, size_t l, UIntType f>
138basic_istream<charT, traits>&
139operator>>(basic_istream<charT, traits>& is,
140 mersenne_twister_engine<UIntType, w, n, m, r, a, u, d, s, b, t, c, l, f>& x);
141
142template<class UIntType, size_t w, size_t s, size_t r>
143class subtract_with_carry_engine
144{
145public:
146 // types
147 typedef UIntType result_type;
148
149 // engine characteristics
150 static constexpr size_t word_size = w;
151 static constexpr size_t short_lag = s;
152 static constexpr size_t long_lag = r;
153 static constexpr result_type min() { return 0; }
154 static constexpr result_type max() { return m-1; }
155 static constexpr result_type default_seed = 19780503u;
156
157 // constructors and seeding functions
158 explicit subtract_with_carry_engine(result_type value = default_seed);
159 template<class Sseq> explicit subtract_with_carry_engine(Sseq& q);
160 void seed(result_type value = default_seed);
161 template<class Sseq> void seed(Sseq& q);
162
163 // generating functions
164 result_type operator()();
165 void discard(unsigned long long z);
166};
167
168template<class UIntType, size_t w, size_t s, size_t r>
169bool
170operator==(
171 const subtract_with_carry_engine<UIntType, w, s, r>& x,
172 const subtract_with_carry_engine<UIntType, w, s, r>& y);
173
174template<class UIntType, size_t w, size_t s, size_t r>
175bool
176operator!=(
177 const subtract_with_carry_engine<UIntType, w, s, r>& x,
178 const subtract_with_carry_engine<UIntType, w, s, r>& y);
179
180template <class charT, class traits,
181 class UIntType, size_t w, size_t s, size_t r>
182basic_ostream<charT, traits>&
183operator<<(basic_ostream<charT, traits>& os,
184 const subtract_with_carry_engine<UIntType, w, s, r>& x);
185
186template <class charT, class traits,
187 class UIntType, size_t w, size_t s, size_t r>
188basic_istream<charT, traits>&
189operator>>(basic_istream<charT, traits>& is,
190 subtract_with_carry_engine<UIntType, w, s, r>& x);
191
192template<class Engine, size_t p, size_t r>
193class discard_block_engine
194{
195public:
196 // types
197 typedef typename Engine::result_type result_type;
198
199 // engine characteristics
200 static constexpr size_t block_size = p;
201 static constexpr size_t used_block = r;
202 static constexpr result_type min() { return Engine::min(); }
203 static constexpr result_type max() { return Engine::max(); }
204
205 // constructors and seeding functions
206 discard_block_engine();
207 explicit discard_block_engine(const Engine& e);
208 explicit discard_block_engine(Engine&& e);
209 explicit discard_block_engine(result_type s);
210 template<class Sseq> explicit discard_block_engine(Sseq& q);
211 void seed();
212 void seed(result_type s);
213 template<class Sseq> void seed(Sseq& q);
214
215 // generating functions
216 result_type operator()();
217 void discard(unsigned long long z);
218
219 // property functions
220 const Engine& base() const noexcept;
221};
222
223template<class Engine, size_t p, size_t r>
224bool
225operator==(
226 const discard_block_engine<Engine, p, r>& x,
227 const discard_block_engine<Engine, p, r>& y);
228
229template<class Engine, size_t p, size_t r>
230bool
231operator!=(
232 const discard_block_engine<Engine, p, r>& x,
233 const discard_block_engine<Engine, p, r>& y);
234
235template <class charT, class traits,
236 class Engine, size_t p, size_t r>
237basic_ostream<charT, traits>&
238operator<<(basic_ostream<charT, traits>& os,
239 const discard_block_engine<Engine, p, r>& x);
240
241template <class charT, class traits,
242 class Engine, size_t p, size_t r>
243basic_istream<charT, traits>&
244operator>>(basic_istream<charT, traits>& is,
245 discard_block_engine<Engine, p, r>& x);
246
247template<class Engine, size_t w, class UIntType>
248class independent_bits_engine
249{
250public:
251 // types
252 typedef UIntType result_type;
253
254 // engine characteristics
255 static constexpr result_type min() { return 0; }
256 static constexpr result_type max() { return 2^w - 1; }
257
258 // constructors and seeding functions
259 independent_bits_engine();
260 explicit independent_bits_engine(const Engine& e);
261 explicit independent_bits_engine(Engine&& e);
262 explicit independent_bits_engine(result_type s);
263 template<class Sseq> explicit independent_bits_engine(Sseq& q);
264 void seed();
265 void seed(result_type s);
266 template<class Sseq> void seed(Sseq& q);
267
268 // generating functions
269 result_type operator()(); void discard(unsigned long long z);
270
271 // property functions
272 const Engine& base() const noexcept;
273};
274
275template<class Engine, size_t w, class UIntType>
276bool
277operator==(
278 const independent_bits_engine<Engine, w, UIntType>& x,
279 const independent_bits_engine<Engine, w, UIntType>& y);
280
281template<class Engine, size_t w, class UIntType>
282bool
283operator!=(
284 const independent_bits_engine<Engine, w, UIntType>& x,
285 const independent_bits_engine<Engine, w, UIntType>& y);
286
287template <class charT, class traits,
288 class Engine, size_t w, class UIntType>
289basic_ostream<charT, traits>&
290operator<<(basic_ostream<charT, traits>& os,
291 const independent_bits_engine<Engine, w, UIntType>& x);
292
293template <class charT, class traits,
294 class Engine, size_t w, class UIntType>
295basic_istream<charT, traits>&
296operator>>(basic_istream<charT, traits>& is,
297 independent_bits_engine<Engine, w, UIntType>& x);
298
299template<class Engine, size_t k>
300class shuffle_order_engine
301{
302public:
303 // types
304 typedef typename Engine::result_type result_type;
305
306 // engine characteristics
307 static constexpr size_t table_size = k;
308 static constexpr result_type min() { return Engine::min; }
309 static constexpr result_type max() { return Engine::max; }
310
311 // constructors and seeding functions
312 shuffle_order_engine();
313 explicit shuffle_order_engine(const Engine& e);
314 explicit shuffle_order_engine(Engine&& e);
315 explicit shuffle_order_engine(result_type s);
316 template<class Sseq> explicit shuffle_order_engine(Sseq& q);
317 void seed();
318 void seed(result_type s);
319 template<class Sseq> void seed(Sseq& q);
320
321 // generating functions
322 result_type operator()();
323 void discard(unsigned long long z);
324
325 // property functions
326 const Engine& base() const noexcept;
327};
328
329template<class Engine, size_t k>
330bool
331operator==(
332 const shuffle_order_engine<Engine, k>& x,
333 const shuffle_order_engine<Engine, k>& y);
334
335template<class Engine, size_t k>
336bool
337operator!=(
338 const shuffle_order_engine<Engine, k>& x,
339 const shuffle_order_engine<Engine, k>& y);
340
341template <class charT, class traits,
342 class Engine, size_t k>
343basic_ostream<charT, traits>&
344operator<<(basic_ostream<charT, traits>& os,
345 const shuffle_order_engine<Engine, k>& x);
346
347template <class charT, class traits,
348 class Engine, size_t k>
349basic_istream<charT, traits>&
350operator>>(basic_istream<charT, traits>& is,
351 shuffle_order_engine<Engine, k>& x);
352
353typedef linear_congruential_engine<uint_fast32_t, 16807, 0, 2147483647>
354 minstd_rand0;
355typedef linear_congruential_engine<uint_fast32_t, 48271, 0, 2147483647>
356 minstd_rand;
357typedef mersenne_twister_engine<uint_fast32_t, 32, 624, 397, 31,
358 0x9908b0df,
359 11, 0xffffffff,
360 7, 0x9d2c5680,
361 15, 0xefc60000,
362 18, 1812433253> mt19937;
363typedef mersenne_twister_engine<uint_fast64_t, 64, 312, 156, 31,
364 0xb5026f5aa96619e9,
365 29, 0x5555555555555555,
366 17, 0x71d67fffeda60000,
367 37, 0xfff7eee000000000,
368 43, 6364136223846793005> mt19937_64;
369typedef subtract_with_carry_engine<uint_fast32_t, 24, 10, 24> ranlux24_base;
370typedef subtract_with_carry_engine<uint_fast64_t, 48, 5, 12> ranlux48_base;
371typedef discard_block_engine<ranlux24_base, 223, 23> ranlux24;
372typedef discard_block_engine<ranlux48_base, 389, 11> ranlux48;
373typedef shuffle_order_engine<minstd_rand0, 256> knuth_b;
374typedef minstd_rand default_random_engine;
375
376// Generators
377
378class random_device
379{
380public:
381 // types
382 typedef unsigned int result_type;
383
384 // generator characteristics
385 static constexpr result_type min() { return numeric_limits<result_type>::min(); }
386 static constexpr result_type max() { return numeric_limits<result_type>::max(); }
387
388 // constructors
389 explicit random_device(const string& token = "/dev/urandom");
390
391 // generating functions
392 result_type operator()();
393
394 // property functions
395 double entropy() const noexcept;
396
397 // no copy functions
398 random_device(const random_device& ) = delete;
399 void operator=(const random_device& ) = delete;
400};
401
402// Utilities
403
404class seed_seq
405{
406public:
407 // types
408 typedef uint_least32_t result_type;
409
410 // constructors
411 seed_seq();
412 template<class T>
413 seed_seq(initializer_list<T> il);
414 template<class InputIterator>
415 seed_seq(InputIterator begin, InputIterator end);
416
417 // generating functions
418 template<class RandomAccessIterator>
419 void generate(RandomAccessIterator begin, RandomAccessIterator end);
420
421 // property functions
422 size_t size() const;
423 template<class OutputIterator>
424 void param(OutputIterator dest) const;
425
426 // no copy functions
427 seed_seq(const seed_seq&) = delete;
428 void operator=(const seed_seq& ) = delete;
429};
430
431template<class RealType, size_t bits, class URNG>
432 RealType generate_canonical(URNG& g);
433
434// Distributions
435
436template<class IntType = int>
437class uniform_int_distribution
438{
439public:
440 // types
441 typedef IntType result_type;
442
443 class param_type
444 {
445 public:
446 typedef uniform_int_distribution distribution_type;
447
448 explicit param_type(IntType a = 0,
449 IntType b = numeric_limits<IntType>::max());
450
451 result_type a() const;
452 result_type b() const;
453
454 friend bool operator==(const param_type& x, const param_type& y);
455 friend bool operator!=(const param_type& x, const param_type& y);
456 };
457
458 // constructors and reset functions
459 explicit uniform_int_distribution(IntType a = 0,
460 IntType b = numeric_limits<IntType>::max());
461 explicit uniform_int_distribution(const param_type& parm);
462 void reset();
463
464 // generating functions
465 template<class URNG> result_type operator()(URNG& g);
466 template<class URNG> result_type operator()(URNG& g, const param_type& parm);
467
468 // property functions
469 result_type a() const;
470 result_type b() const;
471
472 param_type param() const;
473 void param(const param_type& parm);
474
475 result_type min() const;
476 result_type max() const;
477
478 friend bool operator==(const uniform_int_distribution& x,
479 const uniform_int_distribution& y);
480 friend bool operator!=(const uniform_int_distribution& x,
481 const uniform_int_distribution& y);
482
483 template <class charT, class traits>
484 friend
485 basic_ostream<charT, traits>&
486 operator<<(basic_ostream<charT, traits>& os,
487 const uniform_int_distribution& x);
488
489 template <class charT, class traits>
490 friend
491 basic_istream<charT, traits>&
492 operator>>(basic_istream<charT, traits>& is,
493 uniform_int_distribution& x);
494};
495
496template<class RealType = double>
497class uniform_real_distribution
498{
499public:
500 // types
501 typedef RealType result_type;
502
503 class param_type
504 {
505 public:
506 typedef uniform_real_distribution distribution_type;
507
508 explicit param_type(RealType a = 0,
509 RealType b = 1);
510
511 result_type a() const;
512 result_type b() const;
513
514 friend bool operator==(const param_type& x, const param_type& y);
515 friend bool operator!=(const param_type& x, const param_type& y);
516 };
517
518 // constructors and reset functions
519 explicit uniform_real_distribution(RealType a = 0.0, RealType b = 1.0);
520 explicit uniform_real_distribution(const param_type& parm);
521 void reset();
522
523 // generating functions
524 template<class URNG> result_type operator()(URNG& g);
525 template<class URNG> result_type operator()(URNG& g, const param_type& parm);
526
527 // property functions
528 result_type a() const;
529 result_type b() const;
530
531 param_type param() const;
532 void param(const param_type& parm);
533
534 result_type min() const;
535 result_type max() const;
536
537 friend bool operator==(const uniform_real_distribution& x,
538 const uniform_real_distribution& y);
539 friend bool operator!=(const uniform_real_distribution& x,
540 const uniform_real_distribution& y);
541
542 template <class charT, class traits>
543 friend
544 basic_ostream<charT, traits>&
545 operator<<(basic_ostream<charT, traits>& os,
546 const uniform_real_distribution& x);
547
548 template <class charT, class traits>
549 friend
550 basic_istream<charT, traits>&
551 operator>>(basic_istream<charT, traits>& is,
552 uniform_real_distribution& x);
553};
554
555class bernoulli_distribution
556{
557public:
558 // types
559 typedef bool result_type;
560
561 class param_type
562 {
563 public:
564 typedef bernoulli_distribution distribution_type;
565
566 explicit param_type(double p = 0.5);
567
568 double p() const;
569
570 friend bool operator==(const param_type& x, const param_type& y);
571 friend bool operator!=(const param_type& x, const param_type& y);
572 };
573
574 // constructors and reset functions
575 explicit bernoulli_distribution(double p = 0.5);
576 explicit bernoulli_distribution(const param_type& parm);
577 void reset();
578
579 // generating functions
580 template<class URNG> result_type operator()(URNG& g);
581 template<class URNG> result_type operator()(URNG& g, const param_type& parm);
582
583 // property functions
584 double p() const;
585
586 param_type param() const;
587 void param(const param_type& parm);
588
589 result_type min() const;
590 result_type max() const;
591
592 friend bool operator==(const bernoulli_distribution& x,
593 const bernoulli_distribution& y);
594 friend bool operator!=(const bernoulli_distribution& x,
595 const bernoulli_distribution& y);
596
597 template <class charT, class traits>
598 friend
599 basic_ostream<charT, traits>&
600 operator<<(basic_ostream<charT, traits>& os,
601 const bernoulli_distribution& x);
602
603 template <class charT, class traits>
604 friend
605 basic_istream<charT, traits>&
606 operator>>(basic_istream<charT, traits>& is,
607 bernoulli_distribution& x);
608};
609
610template<class IntType = int>
611class binomial_distribution
612{
613public:
614 // types
615 typedef IntType result_type;
616
617 class param_type
618 {
619 public:
620 typedef binomial_distribution distribution_type;
621
622 explicit param_type(IntType t = 1, double p = 0.5);
623
624 IntType t() const;
625 double p() const;
626
627 friend bool operator==(const param_type& x, const param_type& y);
628 friend bool operator!=(const param_type& x, const param_type& y);
629 };
630
631 // constructors and reset functions
632 explicit binomial_distribution(IntType t = 1, double p = 0.5);
633 explicit binomial_distribution(const param_type& parm);
634 void reset();
635
636 // generating functions
637 template<class URNG> result_type operator()(URNG& g);
638 template<class URNG> result_type operator()(URNG& g, const param_type& parm);
639
640 // property functions
641 IntType t() const;
642 double p() const;
643
644 param_type param() const;
645 void param(const param_type& parm);
646
647 result_type min() const;
648 result_type max() const;
649
650 friend bool operator==(const binomial_distribution& x,
651 const binomial_distribution& y);
652 friend bool operator!=(const binomial_distribution& x,
653 const binomial_distribution& y);
654
655 template <class charT, class traits>
656 friend
657 basic_ostream<charT, traits>&
658 operator<<(basic_ostream<charT, traits>& os,
659 const binomial_distribution& x);
660
661 template <class charT, class traits>
662 friend
663 basic_istream<charT, traits>&
664 operator>>(basic_istream<charT, traits>& is,
665 binomial_distribution& x);
666};
667
668template<class IntType = int>
669class geometric_distribution
670{
671public:
672 // types
673 typedef IntType result_type;
674
675 class param_type
676 {
677 public:
678 typedef geometric_distribution distribution_type;
679
680 explicit param_type(double p = 0.5);
681
682 double p() const;
683
684 friend bool operator==(const param_type& x, const param_type& y);
685 friend bool operator!=(const param_type& x, const param_type& y);
686 };
687
688 // constructors and reset functions
689 explicit geometric_distribution(double p = 0.5);
690 explicit geometric_distribution(const param_type& parm);
691 void reset();
692
693 // generating functions
694 template<class URNG> result_type operator()(URNG& g);
695 template<class URNG> result_type operator()(URNG& g, const param_type& parm);
696
697 // property functions
698 double p() const;
699
700 param_type param() const;
701 void param(const param_type& parm);
702
703 result_type min() const;
704 result_type max() const;
705
706 friend bool operator==(const geometric_distribution& x,
707 const geometric_distribution& y);
708 friend bool operator!=(const geometric_distribution& x,
709 const geometric_distribution& y);
710
711 template <class charT, class traits>
712 friend
713 basic_ostream<charT, traits>&
714 operator<<(basic_ostream<charT, traits>& os,
715 const geometric_distribution& x);
716
717 template <class charT, class traits>
718 friend
719 basic_istream<charT, traits>&
720 operator>>(basic_istream<charT, traits>& is,
721 geometric_distribution& x);
722};
723
724template<class IntType = int>
725class negative_binomial_distribution
726{
727public:
728 // types
729 typedef IntType result_type;
730
731 class param_type
732 {
733 public:
734 typedef negative_binomial_distribution distribution_type;
735
736 explicit param_type(result_type k = 1, double p = 0.5);
737
738 result_type k() const;
739 double p() const;
740
741 friend bool operator==(const param_type& x, const param_type& y);
742 friend bool operator!=(const param_type& x, const param_type& y);
743 };
744
745 // constructor and reset functions
746 explicit negative_binomial_distribution(result_type k = 1, double p = 0.5);
747 explicit negative_binomial_distribution(const param_type& parm);
748 void reset();
749
750 // generating functions
751 template<class URNG> result_type operator()(URNG& g);
752 template<class URNG> result_type operator()(URNG& g, const param_type& parm);
753
754 // property functions
755 result_type k() const;
756 double p() const;
757
758 param_type param() const;
759 void param(const param_type& parm);
760
761 result_type min() const;
762 result_type max() const;
763
764 friend bool operator==(const negative_binomial_distribution& x,
765 const negative_binomial_distribution& y);
766 friend bool operator!=(const negative_binomial_distribution& x,
767 const negative_binomial_distribution& y);
768
769 template <class charT, class traits>
770 friend
771 basic_ostream<charT, traits>&
772 operator<<(basic_ostream<charT, traits>& os,
773 const negative_binomial_distribution& x);
774
775 template <class charT, class traits>
776 friend
777 basic_istream<charT, traits>&
778 operator>>(basic_istream<charT, traits>& is,
779 negative_binomial_distribution& x);
780};
781
782template<class IntType = int>
783class poisson_distribution
784{
785public:
786 // types
787 typedef IntType result_type;
788
789 class param_type
790 {
791 public:
792 typedef poisson_distribution distribution_type;
793
794 explicit param_type(double mean = 1.0);
795
796 double mean() const;
797
798 friend bool operator==(const param_type& x, const param_type& y);
799 friend bool operator!=(const param_type& x, const param_type& y);
800 };
801
802 // constructors and reset functions
803 explicit poisson_distribution(double mean = 1.0);
804 explicit poisson_distribution(const param_type& parm);
805 void reset();
806
807 // generating functions
808 template<class URNG> result_type operator()(URNG& g);
809 template<class URNG> result_type operator()(URNG& g, const param_type& parm);
810
811 // property functions
812 double mean() const;
813
814 param_type param() const;
815 void param(const param_type& parm);
816
817 result_type min() const;
818 result_type max() const;
819
820 friend bool operator==(const poisson_distribution& x,
821 const poisson_distribution& y);
822 friend bool operator!=(const poisson_distribution& x,
823 const poisson_distribution& y);
824
825 template <class charT, class traits>
826 friend
827 basic_ostream<charT, traits>&
828 operator<<(basic_ostream<charT, traits>& os,
829 const poisson_distribution& x);
830
831 template <class charT, class traits>
832 friend
833 basic_istream<charT, traits>&
834 operator>>(basic_istream<charT, traits>& is,
835 poisson_distribution& x);
836};
837
838template<class RealType = double>
839class exponential_distribution
840{
841public:
842 // types
843 typedef RealType result_type;
844
845 class param_type
846 {
847 public:
848 typedef exponential_distribution distribution_type;
849
850 explicit param_type(result_type lambda = 1.0);
851
852 result_type lambda() const;
853
854 friend bool operator==(const param_type& x, const param_type& y);
855 friend bool operator!=(const param_type& x, const param_type& y);
856 };
857
858 // constructors and reset functions
859 explicit exponential_distribution(result_type lambda = 1.0);
860 explicit exponential_distribution(const param_type& parm);
861 void reset();
862
863 // generating functions
864 template<class URNG> result_type operator()(URNG& g);
865 template<class URNG> result_type operator()(URNG& g, const param_type& parm);
866
867 // property functions
868 result_type lambda() const;
869
870 param_type param() const;
871 void param(const param_type& parm);
872
873 result_type min() const;
874 result_type max() const;
875
876 friend bool operator==(const exponential_distribution& x,
877 const exponential_distribution& y);
878 friend bool operator!=(const exponential_distribution& x,
879 const exponential_distribution& y);
880
881 template <class charT, class traits>
882 friend
883 basic_ostream<charT, traits>&
884 operator<<(basic_ostream<charT, traits>& os,
885 const exponential_distribution& x);
886
887 template <class charT, class traits>
888 friend
889 basic_istream<charT, traits>&
890 operator>>(basic_istream<charT, traits>& is,
891 exponential_distribution& x);
892};
893
894template<class RealType = double>
895class gamma_distribution
896{
897public:
898 // types
899 typedef RealType result_type;
900
901 class param_type
902 {
903 public:
904 typedef gamma_distribution distribution_type;
905
906 explicit param_type(result_type alpha = 1, result_type beta = 1);
907
908 result_type alpha() const;
909 result_type beta() const;
910
911 friend bool operator==(const param_type& x, const param_type& y);
912 friend bool operator!=(const param_type& x, const param_type& y);
913 };
914
915 // constructors and reset functions
916 explicit gamma_distribution(result_type alpha = 1, result_type beta = 1);
917 explicit gamma_distribution(const param_type& parm);
918 void reset();
919
920 // generating functions
921 template<class URNG> result_type operator()(URNG& g);
922 template<class URNG> result_type operator()(URNG& g, const param_type& parm);
923
924 // property functions
925 result_type alpha() const;
926 result_type beta() const;
927
928 param_type param() const;
929 void param(const param_type& parm);
930
931 result_type min() const;
932 result_type max() const;
933
934 friend bool operator==(const gamma_distribution& x,
935 const gamma_distribution& y);
936 friend bool operator!=(const gamma_distribution& x,
937 const gamma_distribution& y);
938
939 template <class charT, class traits>
940 friend
941 basic_ostream<charT, traits>&
942 operator<<(basic_ostream<charT, traits>& os,
943 const gamma_distribution& x);
944
945 template <class charT, class traits>
946 friend
947 basic_istream<charT, traits>&
948 operator>>(basic_istream<charT, traits>& is,
949 gamma_distribution& x);
950};
951
952template<class RealType = double>
953class weibull_distribution
954{
955public:
956 // types
957 typedef RealType result_type;
958
959 class param_type
960 {
961 public:
962 typedef weibull_distribution distribution_type;
963
964 explicit param_type(result_type alpha = 1, result_type beta = 1);
965
966 result_type a() const;
967 result_type b() const;
968
969 friend bool operator==(const param_type& x, const param_type& y);
970 friend bool operator!=(const param_type& x, const param_type& y);
971 };
972
973 // constructor and reset functions
974 explicit weibull_distribution(result_type a = 1, result_type b = 1);
975 explicit weibull_distribution(const param_type& parm);
976 void reset();
977
978 // generating functions
979 template<class URNG> result_type operator()(URNG& g);
980 template<class URNG> result_type operator()(URNG& g, const param_type& parm);
981
982 // property functions
983 result_type a() const;
984 result_type b() const;
985
986 param_type param() const;
987 void param(const param_type& parm);
988
989 result_type min() const;
990 result_type max() const;
991
992 friend bool operator==(const weibull_distribution& x,
993 const weibull_distribution& y);
994 friend bool operator!=(const weibull_distribution& x,
995 const weibull_distribution& y);
996
997 template <class charT, class traits>
998 friend
999 basic_ostream<charT, traits>&
1000 operator<<(basic_ostream<charT, traits>& os,
1001 const weibull_distribution& x);
1002
1003 template <class charT, class traits>
1004 friend
1005 basic_istream<charT, traits>&
1006 operator>>(basic_istream<charT, traits>& is,
1007 weibull_distribution& x);
1008};
1009
1010template<class RealType = double>
1011class extreme_value_distribution
1012{
1013public:
1014 // types
1015 typedef RealType result_type;
1016
1017 class param_type
1018 {
1019 public:
1020 typedef extreme_value_distribution distribution_type;
1021
1022 explicit param_type(result_type a = 0, result_type b = 1);
1023
1024 result_type a() const;
1025 result_type b() const;
1026
1027 friend bool operator==(const param_type& x, const param_type& y);
1028 friend bool operator!=(const param_type& x, const param_type& y);
1029 };
1030
1031 // constructor and reset functions
1032 explicit extreme_value_distribution(result_type a = 0, result_type b = 1);
1033 explicit extreme_value_distribution(const param_type& parm);
1034 void reset();
1035
1036 // generating functions
1037 template<class URNG> result_type operator()(URNG& g);
1038 template<class URNG> result_type operator()(URNG& g, const param_type& parm);
1039
1040 // property functions
1041 result_type a() const;
1042 result_type b() const;
1043
1044 param_type param() const;
1045 void param(const param_type& parm);
1046
1047 result_type min() const;
1048 result_type max() const;
1049
1050 friend bool operator==(const extreme_value_distribution& x,
1051 const extreme_value_distribution& y);
1052 friend bool operator!=(const extreme_value_distribution& x,
1053 const extreme_value_distribution& y);
1054
1055 template <class charT, class traits>
1056 friend
1057 basic_ostream<charT, traits>&
1058 operator<<(basic_ostream<charT, traits>& os,
1059 const extreme_value_distribution& x);
1060
1061 template <class charT, class traits>
1062 friend
1063 basic_istream<charT, traits>&
1064 operator>>(basic_istream<charT, traits>& is,
1065 extreme_value_distribution& x);
1066};
1067
1068template<class RealType = double>
1069class normal_distribution
1070{
1071public:
1072 // types
1073 typedef RealType result_type;
1074
1075 class param_type
1076 {
1077 public:
1078 typedef normal_distribution distribution_type;
1079
1080 explicit param_type(result_type mean = 0, result_type stddev = 1);
1081
1082 result_type mean() const;
1083 result_type stddev() const;
1084
1085 friend bool operator==(const param_type& x, const param_type& y);
1086 friend bool operator!=(const param_type& x, const param_type& y);
1087 };
1088
1089 // constructors and reset functions
1090 explicit normal_distribution(result_type mean = 0, result_type stddev = 1);
1091 explicit normal_distribution(const param_type& parm);
1092 void reset();
1093
1094 // generating functions
1095 template<class URNG> result_type operator()(URNG& g);
1096 template<class URNG> result_type operator()(URNG& g, const param_type& parm);
1097
1098 // property functions
1099 result_type mean() const;
1100 result_type stddev() const;
1101
1102 param_type param() const;
1103 void param(const param_type& parm);
1104
1105 result_type min() const;
1106 result_type max() const;
1107
1108 friend bool operator==(const normal_distribution& x,
1109 const normal_distribution& y);
1110 friend bool operator!=(const normal_distribution& x,
1111 const normal_distribution& y);
1112
1113 template <class charT, class traits>
1114 friend
1115 basic_ostream<charT, traits>&
1116 operator<<(basic_ostream<charT, traits>& os,
1117 const normal_distribution& x);
1118
1119 template <class charT, class traits>
1120 friend
1121 basic_istream<charT, traits>&
1122 operator>>(basic_istream<charT, traits>& is,
1123 normal_distribution& x);
1124};
1125
1126template<class RealType = double>
1127class lognormal_distribution
1128{
1129public:
1130 // types
1131 typedef RealType result_type;
1132
1133 class param_type
1134 {
1135 public:
1136 typedef lognormal_distribution distribution_type;
1137
1138 explicit param_type(result_type m = 0, result_type s = 1);
1139
1140 result_type m() const;
1141 result_type s() const;
1142
1143 friend bool operator==(const param_type& x, const param_type& y);
1144 friend bool operator!=(const param_type& x, const param_type& y);
1145 };
1146
1147 // constructor and reset functions
1148 explicit lognormal_distribution(result_type m = 0, result_type s = 1);
1149 explicit lognormal_distribution(const param_type& parm);
1150 void reset();
1151
1152 // generating functions
1153 template<class URNG> result_type operator()(URNG& g);
1154 template<class URNG> result_type operator()(URNG& g, const param_type& parm);
1155
1156 // property functions
1157 result_type m() const;
1158 result_type s() const;
1159
1160 param_type param() const;
1161 void param(const param_type& parm);
1162
1163 result_type min() const;
1164 result_type max() const;
1165
1166 friend bool operator==(const lognormal_distribution& x,
1167 const lognormal_distribution& y);
1168 friend bool operator!=(const lognormal_distribution& x,
1169 const lognormal_distribution& y);
1170
1171 template <class charT, class traits>
1172 friend
1173 basic_ostream<charT, traits>&
1174 operator<<(basic_ostream<charT, traits>& os,
1175 const lognormal_distribution& x);
1176
1177 template <class charT, class traits>
1178 friend
1179 basic_istream<charT, traits>&
1180 operator>>(basic_istream<charT, traits>& is,
1181 lognormal_distribution& x);
1182};
1183
1184template<class RealType = double>
1185class chi_squared_distribution
1186{
1187public:
1188 // types
1189 typedef RealType result_type;
1190
1191 class param_type
1192 {
1193 public:
1194 typedef chi_squared_distribution distribution_type;
1195
1196 explicit param_type(result_type n = 1);
1197
1198 result_type n() const;
1199
1200 friend bool operator==(const param_type& x, const param_type& y);
1201 friend bool operator!=(const param_type& x, const param_type& y);
1202 };
1203
1204 // constructor and reset functions
1205 explicit chi_squared_distribution(result_type n = 1);
1206 explicit chi_squared_distribution(const param_type& parm);
1207 void reset();
1208
1209 // generating functions
1210 template<class URNG> result_type operator()(URNG& g);
1211 template<class URNG> result_type operator()(URNG& g, const param_type& parm);
1212
1213 // property functions
1214 result_type n() const;
1215
1216 param_type param() const;
1217 void param(const param_type& parm);
1218
1219 result_type min() const;
1220 result_type max() const;
1221
1222 friend bool operator==(const chi_squared_distribution& x,
1223 const chi_squared_distribution& y);
1224 friend bool operator!=(const chi_squared_distribution& x,
1225 const chi_squared_distribution& y);
1226
1227 template <class charT, class traits>
1228 friend
1229 basic_ostream<charT, traits>&
1230 operator<<(basic_ostream<charT, traits>& os,
1231 const chi_squared_distribution& x);
1232
1233 template <class charT, class traits>
1234 friend
1235 basic_istream<charT, traits>&
1236 operator>>(basic_istream<charT, traits>& is,
1237 chi_squared_distribution& x);
1238};
1239
1240template<class RealType = double>
1241class cauchy_distribution
1242{
1243public:
1244 // types
1245 typedef RealType result_type;
1246
1247 class param_type
1248 {
1249 public:
1250 typedef cauchy_distribution distribution_type;
1251
1252 explicit param_type(result_type a = 0, result_type b = 1);
1253
1254 result_type a() const;
1255 result_type b() const;
1256
1257 friend bool operator==(const param_type& x, const param_type& y);
1258 friend bool operator!=(const param_type& x, const param_type& y);
1259 };
1260
1261 // constructor and reset functions
1262 explicit cauchy_distribution(result_type a = 0, result_type b = 1);
1263 explicit cauchy_distribution(const param_type& parm);
1264 void reset();
1265
1266 // generating functions
1267 template<class URNG> result_type operator()(URNG& g);
1268 template<class URNG> result_type operator()(URNG& g, const param_type& parm);
1269
1270 // property functions
1271 result_type a() const;
1272 result_type b() const;
1273
1274 param_type param() const;
1275 void param(const param_type& parm);
1276
1277 result_type min() const;
1278 result_type max() const;
1279
1280 friend bool operator==(const cauchy_distribution& x,
1281 const cauchy_distribution& y);
1282 friend bool operator!=(const cauchy_distribution& x,
1283 const cauchy_distribution& y);
1284
1285 template <class charT, class traits>
1286 friend
1287 basic_ostream<charT, traits>&
1288 operator<<(basic_ostream<charT, traits>& os,
1289 const cauchy_distribution& x);
1290
1291 template <class charT, class traits>
1292 friend
1293 basic_istream<charT, traits>&
1294 operator>>(basic_istream<charT, traits>& is,
1295 cauchy_distribution& x);
1296};
1297
1298template<class RealType = double>
1299class fisher_f_distribution
1300{
1301public:
1302 // types
1303 typedef RealType result_type;
1304
1305 class param_type
1306 {
1307 public:
1308 typedef fisher_f_distribution distribution_type;
1309
1310 explicit param_type(result_type m = 1, result_type n = 1);
1311
1312 result_type m() const;
1313 result_type n() const;
1314
1315 friend bool operator==(const param_type& x, const param_type& y);
1316 friend bool operator!=(const param_type& x, const param_type& y);
1317 };
1318
1319 // constructor and reset functions
1320 explicit fisher_f_distribution(result_type m = 1, result_type n = 1);
1321 explicit fisher_f_distribution(const param_type& parm);
1322 void reset();
1323
1324 // generating functions
1325 template<class URNG> result_type operator()(URNG& g);
1326 template<class URNG> result_type operator()(URNG& g, const param_type& parm);
1327
1328 // property functions
1329 result_type m() const;
1330 result_type n() const;
1331
1332 param_type param() const;
1333 void param(const param_type& parm);
1334
1335 result_type min() const;
1336 result_type max() const;
1337
1338 friend bool operator==(const fisher_f_distribution& x,
1339 const fisher_f_distribution& y);
1340 friend bool operator!=(const fisher_f_distribution& x,
1341 const fisher_f_distribution& y);
1342
1343 template <class charT, class traits>
1344 friend
1345 basic_ostream<charT, traits>&
1346 operator<<(basic_ostream<charT, traits>& os,
1347 const fisher_f_distribution& x);
1348
1349 template <class charT, class traits>
1350 friend
1351 basic_istream<charT, traits>&
1352 operator>>(basic_istream<charT, traits>& is,
1353 fisher_f_distribution& x);
1354};
1355
1356template<class RealType = double>
1357class student_t_distribution
1358{
1359public:
1360 // types
1361 typedef RealType result_type;
1362
1363 class param_type
1364 {
1365 public:
1366 typedef student_t_distribution distribution_type;
1367
1368 explicit param_type(result_type n = 1);
1369
1370 result_type n() const;
1371
1372 friend bool operator==(const param_type& x, const param_type& y);
1373 friend bool operator!=(const param_type& x, const param_type& y);
1374 };
1375
1376 // constructor and reset functions
1377 explicit student_t_distribution(result_type n = 1);
1378 explicit student_t_distribution(const param_type& parm);
1379 void reset();
1380
1381 // generating functions
1382 template<class URNG> result_type operator()(URNG& g);
1383 template<class URNG> result_type operator()(URNG& g, const param_type& parm);
1384
1385 // property functions
1386 result_type n() const;
1387
1388 param_type param() const;
1389 void param(const param_type& parm);
1390
1391 result_type min() const;
1392 result_type max() const;
1393
1394 friend bool operator==(const student_t_distribution& x,
1395 const student_t_distribution& y);
1396 friend bool operator!=(const student_t_distribution& x,
1397 const student_t_distribution& y);
1398
1399 template <class charT, class traits>
1400 friend
1401 basic_ostream<charT, traits>&
1402 operator<<(basic_ostream<charT, traits>& os,
1403 const student_t_distribution& x);
1404
1405 template <class charT, class traits>
1406 friend
1407 basic_istream<charT, traits>&
1408 operator>>(basic_istream<charT, traits>& is,
1409 student_t_distribution& x);
1410};
1411
1412template<class IntType = int>
1413class discrete_distribution
1414{
1415public:
1416 // types
1417 typedef IntType result_type;
1418
1419 class param_type
1420 {
1421 public:
1422 typedef discrete_distribution distribution_type;
1423
1424 param_type();
1425 template<class InputIterator>
1426 param_type(InputIterator firstW, InputIterator lastW);
1427 param_type(initializer_list<double> wl);
1428 template<class UnaryOperation>
1429 param_type(size_t nw, double xmin, double xmax, UnaryOperation fw);
1430
1431 vector<double> probabilities() const;
1432
1433 friend bool operator==(const param_type& x, const param_type& y);
1434 friend bool operator!=(const param_type& x, const param_type& y);
1435 };
1436
1437 // constructor and reset functions
1438 discrete_distribution();
1439 template<class InputIterator>
1440 discrete_distribution(InputIterator firstW, InputIterator lastW);
1441 discrete_distribution(initializer_list<double> wl);
1442 template<class UnaryOperation>
1443 discrete_distribution(size_t nw, double xmin, double xmax,
1444 UnaryOperation fw);
1445 explicit discrete_distribution(const param_type& parm);
1446 void reset();
1447
1448 // generating functions
1449 template<class URNG> result_type operator()(URNG& g);
1450 template<class URNG> result_type operator()(URNG& g, const param_type& parm);
1451
1452 // property functions
1453 vector<double> probabilities() const;
1454
1455 param_type param() const;
1456 void param(const param_type& parm);
1457
1458 result_type min() const;
1459 result_type max() const;
1460
1461 friend bool operator==(const discrete_distribution& x,
1462 const discrete_distribution& y);
1463 friend bool operator!=(const discrete_distribution& x,
1464 const discrete_distribution& y);
1465
1466 template <class charT, class traits>
1467 friend
1468 basic_ostream<charT, traits>&
1469 operator<<(basic_ostream<charT, traits>& os,
1470 const discrete_distribution& x);
1471
1472 template <class charT, class traits>
1473 friend
1474 basic_istream<charT, traits>&
1475 operator>>(basic_istream<charT, traits>& is,
1476 discrete_distribution& x);
1477};
1478
1479template<class RealType = double>
1480class piecewise_constant_distribution
1481{
1482 // types
1483 typedef RealType result_type;
1484
1485 class param_type
1486 {
1487 public:
1488 typedef piecewise_constant_distribution distribution_type;
1489
1490 param_type();
1491 template<class InputIteratorB, class InputIteratorW>
1492 param_type(InputIteratorB firstB, InputIteratorB lastB,
1493 InputIteratorW firstW);
1494 template<class UnaryOperation>
1495 param_type(initializer_list<result_type> bl, UnaryOperation fw);
1496 template<class UnaryOperation>
1497 param_type(size_t nw, result_type xmin, result_type xmax,
1498 UnaryOperation fw);
1499
1500 vector<result_type> intervals() const;
1501 vector<result_type> densities() const;
1502
1503 friend bool operator==(const param_type& x, const param_type& y);
1504 friend bool operator!=(const param_type& x, const param_type& y);
1505 };
1506
1507 // constructor and reset functions
1508 piecewise_constant_distribution();
1509 template<class InputIteratorB, class InputIteratorW>
1510 piecewise_constant_distribution(InputIteratorB firstB,
1511 InputIteratorB lastB,
1512 InputIteratorW firstW);
1513 template<class UnaryOperation>
1514 piecewise_constant_distribution(initializer_list<result_type> bl,
1515 UnaryOperation fw);
1516 template<class UnaryOperation>
1517 piecewise_constant_distribution(size_t nw, result_type xmin,
1518 result_type xmax, UnaryOperation fw);
1519 explicit piecewise_constant_distribution(const param_type& parm);
1520 void reset();
1521
1522 // generating functions
1523 template<class URNG> result_type operator()(URNG& g);
1524 template<class URNG> result_type operator()(URNG& g, const param_type& parm);
1525
1526 // property functions
1527 vector<result_type> intervals() const;
1528 vector<result_type> densities() const;
1529
1530 param_type param() const;
1531 void param(const param_type& parm);
1532
1533 result_type min() const;
1534 result_type max() const;
1535
1536 friend bool operator==(const piecewise_constant_distribution& x,
1537 const piecewise_constant_distribution& y);
1538 friend bool operator!=(const piecewise_constant_distribution& x,
1539 const piecewise_constant_distribution& y);
1540
1541 template <class charT, class traits>
1542 friend
1543 basic_ostream<charT, traits>&
1544 operator<<(basic_ostream<charT, traits>& os,
1545 const piecewise_constant_distribution& x);
1546
1547 template <class charT, class traits>
1548 friend
1549 basic_istream<charT, traits>&
1550 operator>>(basic_istream<charT, traits>& is,
1551 piecewise_constant_distribution& x);
1552};
1553
1554template<class RealType = double>
1555class piecewise_linear_distribution
1556{
1557 // types
1558 typedef RealType result_type;
1559
1560 class param_type
1561 {
1562 public:
1563 typedef piecewise_linear_distribution distribution_type;
1564
1565 param_type();
1566 template<class InputIteratorB, class InputIteratorW>
1567 param_type(InputIteratorB firstB, InputIteratorB lastB,
1568 InputIteratorW firstW);
1569 template<class UnaryOperation>
1570 param_type(initializer_list<result_type> bl, UnaryOperation fw);
1571 template<class UnaryOperation>
1572 param_type(size_t nw, result_type xmin, result_type xmax,
1573 UnaryOperation fw);
1574
1575 vector<result_type> intervals() const;
1576 vector<result_type> densities() const;
1577
1578 friend bool operator==(const param_type& x, const param_type& y);
1579 friend bool operator!=(const param_type& x, const param_type& y);
1580 };
1581
1582 // constructor and reset functions
1583 piecewise_linear_distribution();
1584 template<class InputIteratorB, class InputIteratorW>
1585 piecewise_linear_distribution(InputIteratorB firstB,
1586 InputIteratorB lastB,
1587 InputIteratorW firstW);
1588
1589 template<class UnaryOperation>
1590 piecewise_linear_distribution(initializer_list<result_type> bl,
1591 UnaryOperation fw);
1592
1593 template<class UnaryOperation>
1594 piecewise_linear_distribution(size_t nw, result_type xmin,
1595 result_type xmax, UnaryOperation fw);
1596
1597 explicit piecewise_linear_distribution(const param_type& parm);
1598 void reset();
1599
1600 // generating functions
1601 template<class URNG> result_type operator()(URNG& g);
1602 template<class URNG> result_type operator()(URNG& g, const param_type& parm);
1603
1604 // property functions
1605 vector<result_type> intervals() const;
1606 vector<result_type> densities() const;
1607
1608 param_type param() const;
1609 void param(const param_type& parm);
1610
1611 result_type min() const;
1612 result_type max() const;
1613
1614 friend bool operator==(const piecewise_linear_distribution& x,
1615 const piecewise_linear_distribution& y);
1616 friend bool operator!=(const piecewise_linear_distribution& x,
1617 const piecewise_linear_distribution& y);
1618
1619 template <class charT, class traits>
1620 friend
1621 basic_ostream<charT, traits>&
1622 operator<<(basic_ostream<charT, traits>& os,
1623 const piecewise_linear_distribution& x);
1624
1625 template <class charT, class traits>
1626 friend
1627 basic_istream<charT, traits>&
1628 operator>>(basic_istream<charT, traits>& is,
1629 piecewise_linear_distribution& x);
1630};
1631
1632} // std
1633*/
1634
1635#include <__config>
1636#include <cstddef>
1637#include <cstdint>
1638#include <cmath>
1639#include <type_traits>
1640#include <initializer_list>
1641#include <limits>
1642#include <algorithm>
1643#include <numeric>
1644#include <vector>
1645#include <string>
1646#include <istream>
1647#include <ostream>
1648
1649#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
1650#pragma GCC system_header
1651#endif
1652
1653_LIBCPP_PUSH_MACROS
1654#include <__undef_macros>
1655
1656
1657_LIBCPP_BEGIN_NAMESPACE_STD
1658
1659// __is_seed_sequence
1660
1661template <class _Sseq, class _Engine>
1662struct __is_seed_sequence
1663{
1664 static _LIBCPP_CONSTEXPR const bool value =
1665 !is_convertible<_Sseq, typename _Engine::result_type>::value &&
1666 !is_same<typename remove_cv<_Sseq>::type, _Engine>::value;
1667};
1668
1669// linear_congruential_engine
1670
1671template <unsigned long long __a, unsigned long long __c,
1672 unsigned long long __m, unsigned long long _Mp,
1673 bool _MightOverflow = (__a != 0 && __m != 0 && __m-1 > (_Mp-__c)/__a)>
1674struct __lce_ta;
1675
1676// 64
1677
1678template <unsigned long long __a, unsigned long long __c, unsigned long long __m>
1679struct __lce_ta<__a, __c, __m, (unsigned long long)(~0), true>
1680{
1681 typedef unsigned long long result_type;
1682 _LIBCPP_INLINE_VISIBILITY
1683 static result_type next(result_type __x)
1684 {
1685 // Schrage's algorithm
1686 const result_type __q = __m / __a;
1687 const result_type __r = __m % __a;
1688 const result_type __t0 = __a * (__x % __q);
1689 const result_type __t1 = __r * (__x / __q);
1690 __x = __t0 + (__t0 < __t1) * __m - __t1;
1691 __x += __c - (__x >= __m - __c) * __m;
1692 return __x;
1693 }
1694};
1695
1696template <unsigned long long __a, unsigned long long __m>
1697struct __lce_ta<__a, 0, __m, (unsigned long long)(~0), true>
1698{
1699 typedef unsigned long long result_type;
1700 _LIBCPP_INLINE_VISIBILITY
1701 static result_type next(result_type __x)
1702 {
1703 // Schrage's algorithm
1704 const result_type __q = __m / __a;
1705 const result_type __r = __m % __a;
1706 const result_type __t0 = __a * (__x % __q);
1707 const result_type __t1 = __r * (__x / __q);
1708 __x = __t0 + (__t0 < __t1) * __m - __t1;
1709 return __x;
1710 }
1711};
1712
1713template <unsigned long long __a, unsigned long long __c, unsigned long long __m>
1714struct __lce_ta<__a, __c, __m, (unsigned long long)(~0), false>
1715{
1716 typedef unsigned long long result_type;
1717 _LIBCPP_INLINE_VISIBILITY
1718 static result_type next(result_type __x)
1719 {
1720 return (__a * __x + __c) % __m;
1721 }
1722};
1723
1724template <unsigned long long __a, unsigned long long __c>
1725struct __lce_ta<__a, __c, 0, (unsigned long long)(~0), false>
1726{
1727 typedef unsigned long long result_type;
1728 _LIBCPP_INLINE_VISIBILITY
1729 static result_type next(result_type __x)
1730 {
1731 return __a * __x + __c;
1732 }
1733};
1734
1735// 32
1736
1737template <unsigned long long _Ap, unsigned long long _Cp, unsigned long long _Mp>
1738struct __lce_ta<_Ap, _Cp, _Mp, unsigned(~0), true>
1739{
1740 typedef unsigned result_type;
1741 _LIBCPP_INLINE_VISIBILITY
1742 static result_type next(result_type __x)
1743 {
1744 const result_type __a = static_cast<result_type>(_Ap);
1745 const result_type __c = static_cast<result_type>(_Cp);
1746 const result_type __m = static_cast<result_type>(_Mp);
1747 // Schrage's algorithm
1748 const result_type __q = __m / __a;
1749 const result_type __r = __m % __a;
1750 const result_type __t0 = __a * (__x % __q);
1751 const result_type __t1 = __r * (__x / __q);
1752 __x = __t0 + (__t0 < __t1) * __m - __t1;
1753 __x += __c - (__x >= __m - __c) * __m;
1754 return __x;
1755 }
1756};
1757
1758template <unsigned long long _Ap, unsigned long long _Mp>
1759struct __lce_ta<_Ap, 0, _Mp, unsigned(~0), true>
1760{
1761 typedef unsigned result_type;
1762 _LIBCPP_INLINE_VISIBILITY
1763 static result_type next(result_type __x)
1764 {
1765 const result_type __a = static_cast<result_type>(_Ap);
1766 const result_type __m = static_cast<result_type>(_Mp);
1767 // Schrage's algorithm
1768 const result_type __q = __m / __a;
1769 const result_type __r = __m % __a;
1770 const result_type __t0 = __a * (__x % __q);
1771 const result_type __t1 = __r * (__x / __q);
1772 __x = __t0 + (__t0 < __t1) * __m - __t1;
1773 return __x;
1774 }
1775};
1776
1777template <unsigned long long _Ap, unsigned long long _Cp, unsigned long long _Mp>
1778struct __lce_ta<_Ap, _Cp, _Mp, unsigned(~0), false>
1779{
1780 typedef unsigned result_type;
1781 _LIBCPP_INLINE_VISIBILITY
1782 static result_type next(result_type __x)
1783 {
1784 const result_type __a = static_cast<result_type>(_Ap);
1785 const result_type __c = static_cast<result_type>(_Cp);
1786 const result_type __m = static_cast<result_type>(_Mp);
1787 return (__a * __x + __c) % __m;
1788 }
1789};
1790
1791template <unsigned long long _Ap, unsigned long long _Cp>
1792struct __lce_ta<_Ap, _Cp, 0, unsigned(~0), false>
1793{
1794 typedef unsigned result_type;
1795 _LIBCPP_INLINE_VISIBILITY
1796 static result_type next(result_type __x)
1797 {
1798 const result_type __a = static_cast<result_type>(_Ap);
1799 const result_type __c = static_cast<result_type>(_Cp);
1800 return __a * __x + __c;
1801 }
1802};
1803
1804// 16
1805
1806template <unsigned long long __a, unsigned long long __c, unsigned long long __m, bool __b>
1807struct __lce_ta<__a, __c, __m, (unsigned short)(~0), __b>
1808{
1809 typedef unsigned short result_type;
1810 _LIBCPP_INLINE_VISIBILITY
1811 static result_type next(result_type __x)
1812 {
1813 return static_cast<result_type>(__lce_ta<__a, __c, __m, unsigned(~0)>::next(__x));
1814 }
1815};
1816
1817template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1818class _LIBCPP_TEMPLATE_VIS linear_congruential_engine;
1819
1820template <class _CharT, class _Traits,
1821 class _Up, _Up _Ap, _Up _Cp, _Up _Np>
1822_LIBCPP_INLINE_VISIBILITY
1823basic_ostream<_CharT, _Traits>&
1824operator<<(basic_ostream<_CharT, _Traits>& __os,
1825 const linear_congruential_engine<_Up, _Ap, _Cp, _Np>&);
1826
1827template <class _CharT, class _Traits,
1828 class _Up, _Up _Ap, _Up _Cp, _Up _Np>
1829basic_istream<_CharT, _Traits>&
1830operator>>(basic_istream<_CharT, _Traits>& __is,
1831 linear_congruential_engine<_Up, _Ap, _Cp, _Np>& __x);
1832
1833template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1834class _LIBCPP_TEMPLATE_VIS linear_congruential_engine
1835{
1836public:
1837 // types
1838 typedef _UIntType result_type;
1839
1840private:
1841 result_type __x_;
1842
1843 static _LIBCPP_CONSTEXPR const result_type _Mp = result_type(~0);
1844
1845 static_assert(__m == 0 || __a < __m, "linear_congruential_engine invalid parameters");
1846 static_assert(__m == 0 || __c < __m, "linear_congruential_engine invalid parameters");
1847public:
1848 static _LIBCPP_CONSTEXPR const result_type _Min = __c == 0u ? 1u: 0u;
1849 static _LIBCPP_CONSTEXPR const result_type _Max = __m - 1u;
1850 static_assert(_Min < _Max, "linear_congruential_engine invalid parameters");
1851
1852 // engine characteristics
1853 static _LIBCPP_CONSTEXPR const result_type multiplier = __a;
1854 static _LIBCPP_CONSTEXPR const result_type increment = __c;
1855 static _LIBCPP_CONSTEXPR const result_type modulus = __m;
1856 _LIBCPP_INLINE_VISIBILITY
1857 static _LIBCPP_CONSTEXPR result_type min() {return _Min;}
1858 _LIBCPP_INLINE_VISIBILITY
1859 static _LIBCPP_CONSTEXPR result_type max() {return _Max;}
1860 static _LIBCPP_CONSTEXPR const result_type default_seed = 1u;
1861
1862 // constructors and seeding functions
1863 _LIBCPP_INLINE_VISIBILITY
1864 explicit linear_congruential_engine(result_type __s = default_seed)
1865 {seed(__s);}
1866 template<class _Sseq>
1867 _LIBCPP_INLINE_VISIBILITY
1868 explicit linear_congruential_engine(_Sseq& __q,
1869 typename enable_if<__is_seed_sequence<_Sseq, linear_congruential_engine>::value>::type* = 0)
1870 {seed(__q);}
1871 _LIBCPP_INLINE_VISIBILITY
1872 void seed(result_type __s = default_seed)
1873 {seed(integral_constant<bool, __m == 0>(),
1874 integral_constant<bool, __c == 0>(), __s);}
1875 template<class _Sseq>
1876 _LIBCPP_INLINE_VISIBILITY
1877 typename enable_if
1878 <
1879 __is_seed_sequence<_Sseq, linear_congruential_engine>::value,
1880 void
1881 >::type
1882 seed(_Sseq& __q)
1883 {__seed(__q, integral_constant<unsigned,
1884 1 + (__m == 0 ? (sizeof(result_type) * __CHAR_BIT__ - 1)/32
1885 : (__m > 0x100000000ull))>());}
1886
1887 // generating functions
1888 _LIBCPP_INLINE_VISIBILITY
1889 result_type operator()()
1890 {return __x_ = static_cast<result_type>(__lce_ta<__a, __c, __m, _Mp>::next(__x_));}
1891 _LIBCPP_INLINE_VISIBILITY
1892 void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
1893
1894 friend _LIBCPP_INLINE_VISIBILITY
1895 bool operator==(const linear_congruential_engine& __x,
1896 const linear_congruential_engine& __y)
1897 {return __x.__x_ == __y.__x_;}
1898 friend _LIBCPP_INLINE_VISIBILITY
1899 bool operator!=(const linear_congruential_engine& __x,
1900 const linear_congruential_engine& __y)
1901 {return !(__x == __y);}
1902
1903private:
1904
1905 _LIBCPP_INLINE_VISIBILITY
1906 void seed(true_type, true_type, result_type __s) {__x_ = __s == 0 ? 1 : __s;}
1907 _LIBCPP_INLINE_VISIBILITY
1908 void seed(true_type, false_type, result_type __s) {__x_ = __s;}
1909 _LIBCPP_INLINE_VISIBILITY
1910 void seed(false_type, true_type, result_type __s) {__x_ = __s % __m == 0 ?
1911 1 : __s % __m;}
1912 _LIBCPP_INLINE_VISIBILITY
1913 void seed(false_type, false_type, result_type __s) {__x_ = __s % __m;}
1914
1915 template<class _Sseq>
1916 void __seed(_Sseq& __q, integral_constant<unsigned, 1>);
1917 template<class _Sseq>
1918 void __seed(_Sseq& __q, integral_constant<unsigned, 2>);
1919
1920 template <class _CharT, class _Traits,
1921 class _Up, _Up _Ap, _Up _Cp, _Up _Np>
1922 friend
1923 basic_ostream<_CharT, _Traits>&
1924 operator<<(basic_ostream<_CharT, _Traits>& __os,
1925 const linear_congruential_engine<_Up, _Ap, _Cp, _Np>&);
1926
1927 template <class _CharT, class _Traits,
1928 class _Up, _Up _Ap, _Up _Cp, _Up _Np>
1929 friend
1930 basic_istream<_CharT, _Traits>&
1931 operator>>(basic_istream<_CharT, _Traits>& __is,
1932 linear_congruential_engine<_Up, _Ap, _Cp, _Np>& __x);
1933};
1934
1935template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1936 _LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type
1937 linear_congruential_engine<_UIntType, __a, __c, __m>::multiplier;
1938
1939template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1940 _LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type
1941 linear_congruential_engine<_UIntType, __a, __c, __m>::increment;
1942
1943template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1944 _LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type
1945 linear_congruential_engine<_UIntType, __a, __c, __m>::modulus;
1946
1947template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1948 _LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type
1949 linear_congruential_engine<_UIntType, __a, __c, __m>::default_seed;
1950
1951template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1952template<class _Sseq>
1953void
1954linear_congruential_engine<_UIntType, __a, __c, __m>::__seed(_Sseq& __q,
1955 integral_constant<unsigned, 1>)
1956{
1957 const unsigned __k = 1;
1958 uint32_t __ar[__k+3];
1959 __q.generate(__ar, __ar + __k + 3);
1960 result_type __s = static_cast<result_type>(__ar[3] % __m);
1961 __x_ = __c == 0 && __s == 0 ? result_type(1) : __s;
1962}
1963
1964template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1965template<class _Sseq>
1966void
1967linear_congruential_engine<_UIntType, __a, __c, __m>::__seed(_Sseq& __q,
1968 integral_constant<unsigned, 2>)
1969{
1970 const unsigned __k = 2;
1971 uint32_t __ar[__k+3];
1972 __q.generate(__ar, __ar + __k + 3);
1973 result_type __s = static_cast<result_type>((__ar[3] +
1974 ((uint64_t)__ar[4] << 32)) % __m);
1975 __x_ = __c == 0 && __s == 0 ? result_type(1) : __s;
1976}
1977
1978template <class _CharT, class _Traits,
1979 class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1980inline _LIBCPP_INLINE_VISIBILITY
1981basic_ostream<_CharT, _Traits>&
1982operator<<(basic_ostream<_CharT, _Traits>& __os,
1983 const linear_congruential_engine<_UIntType, __a, __c, __m>& __x)
1984{
1985 __save_flags<_CharT, _Traits> __lx(__os);
1986 __os.flags(ios_base::dec | ios_base::left);
1987 __os.fill(__os.widen(' '));
1988 return __os << __x.__x_;
1989}
1990
1991template <class _CharT, class _Traits,
1992 class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1993basic_istream<_CharT, _Traits>&
1994operator>>(basic_istream<_CharT, _Traits>& __is,
1995 linear_congruential_engine<_UIntType, __a, __c, __m>& __x)
1996{
1997 __save_flags<_CharT, _Traits> __lx(__is);
1998 __is.flags(ios_base::dec | ios_base::skipws);
1999 _UIntType __t;
2000 __is >> __t;
2001 if (!__is.fail())
2002 __x.__x_ = __t;
2003 return __is;
2004}
2005
2006typedef linear_congruential_engine<uint_fast32_t, 16807, 0, 2147483647>
2007 minstd_rand0;
2008typedef linear_congruential_engine<uint_fast32_t, 48271, 0, 2147483647>
2009 minstd_rand;
2010typedef minstd_rand default_random_engine;
2011// mersenne_twister_engine
2012
2013template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2014 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2015 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2016class _LIBCPP_TEMPLATE_VIS mersenne_twister_engine;
2017
2018template <class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
2019 _UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
2020 _UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
2021bool
2022operator==(const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2023 _Bp, _Tp, _Cp, _Lp, _Fp>& __x,
2024 const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2025 _Bp, _Tp, _Cp, _Lp, _Fp>& __y);
2026
2027template <class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
2028 _UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
2029 _UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
2030_LIBCPP_INLINE_VISIBILITY
2031bool
2032operator!=(const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2033 _Bp, _Tp, _Cp, _Lp, _Fp>& __x,
2034 const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2035 _Bp, _Tp, _Cp, _Lp, _Fp>& __y);
2036
2037template <class _CharT, class _Traits,
2038 class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
2039 _UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
2040 _UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
2041basic_ostream<_CharT, _Traits>&
2042operator<<(basic_ostream<_CharT, _Traits>& __os,
2043 const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2044 _Bp, _Tp, _Cp, _Lp, _Fp>& __x);
2045
2046template <class _CharT, class _Traits,
2047 class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
2048 _UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
2049 _UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
2050basic_istream<_CharT, _Traits>&
2051operator>>(basic_istream<_CharT, _Traits>& __is,
2052 mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2053 _Bp, _Tp, _Cp, _Lp, _Fp>& __x);
2054
2055template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2056 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2057 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2058class _LIBCPP_TEMPLATE_VIS mersenne_twister_engine
2059{
2060public:
2061 // types
2062 typedef _UIntType result_type;
2063
2064private:
2065 result_type __x_[__n];
2066 size_t __i_;
2067
2068 static_assert( 0 < __m, "mersenne_twister_engine invalid parameters");
2069 static_assert(__m <= __n, "mersenne_twister_engine invalid parameters");
2070 static _LIBCPP_CONSTEXPR const result_type _Dt = numeric_limits<result_type>::digits;
2071 static_assert(__w <= _Dt, "mersenne_twister_engine invalid parameters");
2072 static_assert( 2 <= __w, "mersenne_twister_engine invalid parameters");
2073 static_assert(__r <= __w, "mersenne_twister_engine invalid parameters");
2074 static_assert(__u <= __w, "mersenne_twister_engine invalid parameters");
2075 static_assert(__s <= __w, "mersenne_twister_engine invalid parameters");
2076 static_assert(__t <= __w, "mersenne_twister_engine invalid parameters");
2077 static_assert(__l <= __w, "mersenne_twister_engine invalid parameters");
2078public:
2079 static _LIBCPP_CONSTEXPR const result_type _Min = 0;
2080 static _LIBCPP_CONSTEXPR const result_type _Max = __w == _Dt ? result_type(~0) :
2081 (result_type(1) << __w) - result_type(1);
2082 static_assert(_Min < _Max, "mersenne_twister_engine invalid parameters");
2083 static_assert(__a <= _Max, "mersenne_twister_engine invalid parameters");
2084 static_assert(__b <= _Max, "mersenne_twister_engine invalid parameters");
2085 static_assert(__c <= _Max, "mersenne_twister_engine invalid parameters");
2086 static_assert(__d <= _Max, "mersenne_twister_engine invalid parameters");
2087 static_assert(__f <= _Max, "mersenne_twister_engine invalid parameters");
2088
2089 // engine characteristics
2090 static _LIBCPP_CONSTEXPR const size_t word_size = __w;
2091 static _LIBCPP_CONSTEXPR const size_t state_size = __n;
2092 static _LIBCPP_CONSTEXPR const size_t shift_size = __m;
2093 static _LIBCPP_CONSTEXPR const size_t mask_bits = __r;
2094 static _LIBCPP_CONSTEXPR const result_type xor_mask = __a;
2095 static _LIBCPP_CONSTEXPR const size_t tempering_u = __u;
2096 static _LIBCPP_CONSTEXPR const result_type tempering_d = __d;
2097 static _LIBCPP_CONSTEXPR const size_t tempering_s = __s;
2098 static _LIBCPP_CONSTEXPR const result_type tempering_b = __b;
2099 static _LIBCPP_CONSTEXPR const size_t tempering_t = __t;
2100 static _LIBCPP_CONSTEXPR const result_type tempering_c = __c;
2101 static _LIBCPP_CONSTEXPR const size_t tempering_l = __l;
2102 static _LIBCPP_CONSTEXPR const result_type initialization_multiplier = __f;
2103 _LIBCPP_INLINE_VISIBILITY
2104 static _LIBCPP_CONSTEXPR result_type min() { return _Min; }
2105 _LIBCPP_INLINE_VISIBILITY
2106 static _LIBCPP_CONSTEXPR result_type max() { return _Max; }
2107 static _LIBCPP_CONSTEXPR const result_type default_seed = 5489u;
2108
2109 // constructors and seeding functions
2110 _LIBCPP_INLINE_VISIBILITY
2111 explicit mersenne_twister_engine(result_type __sd = default_seed)
2112 {seed(__sd);}
2113 template<class _Sseq>
2114 _LIBCPP_INLINE_VISIBILITY
2115 explicit mersenne_twister_engine(_Sseq& __q,
2116 typename enable_if<__is_seed_sequence<_Sseq, mersenne_twister_engine>::value>::type* = 0)
2117 {seed(__q);}
2118 void seed(result_type __sd = default_seed);
2119 template<class _Sseq>
2120 _LIBCPP_INLINE_VISIBILITY
2121 typename enable_if
2122 <
2123 __is_seed_sequence<_Sseq, mersenne_twister_engine>::value,
2124 void
2125 >::type
2126 seed(_Sseq& __q)
2127 {__seed(__q, integral_constant<unsigned, 1 + (__w - 1) / 32>());}
2128
2129 // generating functions
2130 result_type operator()();
2131 _LIBCPP_INLINE_VISIBILITY
2132 void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
2133
2134 template <class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
2135 _UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
2136 _UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
2137 friend
2138 bool
2139 operator==(const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2140 _Bp, _Tp, _Cp, _Lp, _Fp>& __x,
2141 const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2142 _Bp, _Tp, _Cp, _Lp, _Fp>& __y);
2143
2144 template <class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
2145 _UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
2146 _UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
2147 friend
2148 bool
2149 operator!=(const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2150 _Bp, _Tp, _Cp, _Lp, _Fp>& __x,
2151 const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2152 _Bp, _Tp, _Cp, _Lp, _Fp>& __y);
2153
2154 template <class _CharT, class _Traits,
2155 class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
2156 _UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
2157 _UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
2158 friend
2159 basic_ostream<_CharT, _Traits>&
2160 operator<<(basic_ostream<_CharT, _Traits>& __os,
2161 const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2162 _Bp, _Tp, _Cp, _Lp, _Fp>& __x);
2163
2164 template <class _CharT, class _Traits,
2165 class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
2166 _UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
2167 _UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
2168 friend
2169 basic_istream<_CharT, _Traits>&
2170 operator>>(basic_istream<_CharT, _Traits>& __is,
2171 mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2172 _Bp, _Tp, _Cp, _Lp, _Fp>& __x);
2173private:
2174
2175 template<class _Sseq>
2176 void __seed(_Sseq& __q, integral_constant<unsigned, 1>);
2177 template<class _Sseq>
2178 void __seed(_Sseq& __q, integral_constant<unsigned, 2>);
2179
2180 template <size_t __count>
2181 _LIBCPP_INLINE_VISIBILITY
2182 static
2183 typename enable_if
2184 <
2185 __count < __w,
2186 result_type
2187 >::type
2188 __lshift(result_type __x) {return (__x << __count) & _Max;}
2189
2190 template <size_t __count>
2191 _LIBCPP_INLINE_VISIBILITY
2192 static
2193 typename enable_if
2194 <
2195 (__count >= __w),
2196 result_type
2197 >::type
2198 __lshift(result_type) {return result_type(0);}
2199
2200 template <size_t __count>
2201 _LIBCPP_INLINE_VISIBILITY
2202 static
2203 typename enable_if
2204 <
2205 __count < _Dt,
2206 result_type
2207 >::type
2208 __rshift(result_type __x) {return __x >> __count;}
2209
2210 template <size_t __count>
2211 _LIBCPP_INLINE_VISIBILITY
2212 static
2213 typename enable_if
2214 <
2215 (__count >= _Dt),
2216 result_type
2217 >::type
2218 __rshift(result_type) {return result_type(0);}
2219};
2220
2221template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2222 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2223 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2224 _LIBCPP_CONSTEXPR const size_t
2225 mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::word_size;
2226
2227template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2228 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2229 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2230 _LIBCPP_CONSTEXPR const size_t
2231 mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::state_size;
2232
2233template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2234 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2235 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2236 _LIBCPP_CONSTEXPR const size_t
2237 mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::shift_size;
2238
2239template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2240 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2241 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2242 _LIBCPP_CONSTEXPR const size_t
2243 mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::mask_bits;
2244
2245template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2246 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2247 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2248 _LIBCPP_CONSTEXPR const typename mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::result_type
2249 mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::xor_mask;
2250
2251template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2252 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2253 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2254 _LIBCPP_CONSTEXPR const size_t
2255 mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::tempering_u;
2256
2257template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2258 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2259 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2260 _LIBCPP_CONSTEXPR const typename mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::result_type
2261 mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::tempering_d;
2262
2263template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2264 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2265 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2266 _LIBCPP_CONSTEXPR const size_t
2267 mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::tempering_s;
2268
2269template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2270 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2271 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2272 _LIBCPP_CONSTEXPR const typename mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::result_type
2273 mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::tempering_b;
2274
2275template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2276 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2277 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2278 _LIBCPP_CONSTEXPR const size_t
2279 mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::tempering_t;
2280
2281template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2282 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2283 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2284 _LIBCPP_CONSTEXPR const typename mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::result_type
2285 mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::tempering_c;
2286
2287template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2288 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2289 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2290 _LIBCPP_CONSTEXPR const size_t
2291 mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::tempering_l;
2292
2293template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2294 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2295 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2296 _LIBCPP_CONSTEXPR const typename mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::result_type
2297 mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::initialization_multiplier;
2298
2299template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2300 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2301 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2302 _LIBCPP_CONSTEXPR const typename mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::result_type
2303 mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::default_seed;
2304
2305template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2306 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2307 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2308void
2309mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b,
2310 __t, __c, __l, __f>::seed(result_type __sd)
2311 _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
2312{ // __w >= 2
2313 __x_[0] = __sd & _Max;
2314 for (size_t __i = 1; __i < __n; ++__i)
2315 __x_[__i] = (__f * (__x_[__i-1] ^ __rshift<__w - 2>(__x_[__i-1])) + __i) & _Max;
2316 __i_ = 0;
2317}
2318
2319template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2320 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2321 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2322template<class _Sseq>
2323void
2324mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b,
2325 __t, __c, __l, __f>::__seed(_Sseq& __q, integral_constant<unsigned, 1>)
2326{
2327 const unsigned __k = 1;
2328 uint32_t __ar[__n * __k];
2329 __q.generate(__ar, __ar + __n * __k);
2330 for (size_t __i = 0; __i < __n; ++__i)
2331 __x_[__i] = static_cast<result_type>(__ar[__i] & _Max);
2332 const result_type __mask = __r == _Dt ? result_type(~0) :
2333 (result_type(1) << __r) - result_type(1);
2334 __i_ = 0;
2335 if ((__x_[0] & ~__mask) == 0)
2336 {
2337 for (size_t __i = 1; __i < __n; ++__i)
2338 if (__x_[__i] != 0)
2339 return;
2340 __x_[0] = _Max;
2341 }
2342}
2343
2344template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2345 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2346 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2347template<class _Sseq>
2348void
2349mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b,
2350 __t, __c, __l, __f>::__seed(_Sseq& __q, integral_constant<unsigned, 2>)
2351{
2352 const unsigned __k = 2;
2353 uint32_t __ar[__n * __k];
2354 __q.generate(__ar, __ar + __n * __k);
2355 for (size_t __i = 0; __i < __n; ++__i)
2356 __x_[__i] = static_cast<result_type>(
2357 (__ar[2 * __i] + ((uint64_t)__ar[2 * __i + 1] << 32)) & _Max);
2358 const result_type __mask = __r == _Dt ? result_type(~0) :
2359 (result_type(1) << __r) - result_type(1);
2360 __i_ = 0;
2361 if ((__x_[0] & ~__mask) == 0)
2362 {
2363 for (size_t __i = 1; __i < __n; ++__i)
2364 if (__x_[__i] != 0)
2365 return;
2366 __x_[0] = _Max;
2367 }
2368}
2369
2370template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2371 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2372 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2373_UIntType
2374mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b,
2375 __t, __c, __l, __f>::operator()()
2376{
2377 const size_t __j = (__i_ + 1) % __n;
2378 const result_type __mask = __r == _Dt ? result_type(~0) :
2379 (result_type(1) << __r) - result_type(1);
2380 const result_type _Yp = (__x_[__i_] & ~__mask) | (__x_[__j] & __mask);
2381 const size_t __k = (__i_ + __m) % __n;
2382 __x_[__i_] = __x_[__k] ^ __rshift<1>(_Yp) ^ (__a * (_Yp & 1));
2383 result_type __z = __x_[__i_] ^ (__rshift<__u>(__x_[__i_]) & __d);
2384 __i_ = __j;
2385 __z ^= __lshift<__s>(__z) & __b;
2386 __z ^= __lshift<__t>(__z) & __c;
2387 return __z ^ __rshift<__l>(__z);
2388}
2389
2390template <class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
2391 _UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
2392 _UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
2393bool
2394operator==(const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2395 _Bp, _Tp, _Cp, _Lp, _Fp>& __x,
2396 const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2397 _Bp, _Tp, _Cp, _Lp, _Fp>& __y)
2398{
2399 if (__x.__i_ == __y.__i_)
2400 return _VSTD::equal(__x.__x_, __x.__x_ + _Np, __y.__x_);
2401 if (__x.__i_ == 0 || __y.__i_ == 0)
2402 {
2403 size_t __j = _VSTD::min(_Np - __x.__i_, _Np - __y.__i_);
2404 if (!_VSTD::equal(__x.__x_ + __x.__i_, __x.__x_ + __x.__i_ + __j,
2405 __y.__x_ + __y.__i_))
2406 return false;
2407 if (__x.__i_ == 0)
2408 return _VSTD::equal(__x.__x_ + __j, __x.__x_ + _Np, __y.__x_);
2409 return _VSTD::equal(__x.__x_, __x.__x_ + (_Np - __j), __y.__x_ + __j);
2410 }
2411 if (__x.__i_ < __y.__i_)
2412 {
2413 size_t __j = _Np - __y.__i_;
2414 if (!_VSTD::equal(__x.__x_ + __x.__i_, __x.__x_ + (__x.__i_ + __j),
2415 __y.__x_ + __y.__i_))
2416 return false;
2417 if (!_VSTD::equal(__x.__x_ + (__x.__i_ + __j), __x.__x_ + _Np,
2418 __y.__x_))
2419 return false;
2420 return _VSTD::equal(__x.__x_, __x.__x_ + __x.__i_,
2421 __y.__x_ + (_Np - (__x.__i_ + __j)));
2422 }
2423 size_t __j = _Np - __x.__i_;
2424 if (!_VSTD::equal(__y.__x_ + __y.__i_, __y.__x_ + (__y.__i_ + __j),
2425 __x.__x_ + __x.__i_))
2426 return false;
2427 if (!_VSTD::equal(__y.__x_ + (__y.__i_ + __j), __y.__x_ + _Np,
2428 __x.__x_))
2429 return false;
2430 return _VSTD::equal(__y.__x_, __y.__x_ + __y.__i_,
2431 __x.__x_ + (_Np - (__y.__i_ + __j)));
2432}
2433
2434template <class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
2435 _UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
2436 _UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
2437inline _LIBCPP_INLINE_VISIBILITY
2438bool
2439operator!=(const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2440 _Bp, _Tp, _Cp, _Lp, _Fp>& __x,
2441 const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2442 _Bp, _Tp, _Cp, _Lp, _Fp>& __y)
2443{
2444 return !(__x == __y);
2445}
2446
2447template <class _CharT, class _Traits,
2448 class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
2449 _UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
2450 _UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
2451basic_ostream<_CharT, _Traits>&
2452operator<<(basic_ostream<_CharT, _Traits>& __os,
2453 const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2454 _Bp, _Tp, _Cp, _Lp, _Fp>& __x)
2455{
2456 __save_flags<_CharT, _Traits> __lx(__os);
2457 __os.flags(ios_base::dec | ios_base::left);
2458 _CharT __sp = __os.widen(' ');
2459 __os.fill(__sp);
2460 __os << __x.__x_[__x.__i_];
2461 for (size_t __j = __x.__i_ + 1; __j < _Np; ++__j)
2462 __os << __sp << __x.__x_[__j];
2463 for (size_t __j = 0; __j < __x.__i_; ++__j)
2464 __os << __sp << __x.__x_[__j];
2465 return __os;
2466}
2467
2468template <class _CharT, class _Traits,
2469 class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
2470 _UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
2471 _UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
2472basic_istream<_CharT, _Traits>&
2473operator>>(basic_istream<_CharT, _Traits>& __is,
2474 mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2475 _Bp, _Tp, _Cp, _Lp, _Fp>& __x)
2476{
2477 __save_flags<_CharT, _Traits> __lx(__is);
2478 __is.flags(ios_base::dec | ios_base::skipws);
2479 _UInt __t[_Np];
2480 for (size_t __i = 0; __i < _Np; ++__i)
2481 __is >> __t[__i];
2482 if (!__is.fail())
2483 {
2484 for (size_t __i = 0; __i < _Np; ++__i)
2485 __x.__x_[__i] = __t[__i];
2486 __x.__i_ = 0;
2487 }
2488 return __is;
2489}
2490
2491typedef mersenne_twister_engine<uint_fast32_t, 32, 624, 397, 31,
2492 0x9908b0df, 11, 0xffffffff,
2493 7, 0x9d2c5680,
2494 15, 0xefc60000,
2495 18, 1812433253> mt19937;
2496typedef mersenne_twister_engine<uint_fast64_t, 64, 312, 156, 31,
2497 0xb5026f5aa96619e9ULL, 29, 0x5555555555555555ULL,
2498 17, 0x71d67fffeda60000ULL,
2499 37, 0xfff7eee000000000ULL,
2500 43, 6364136223846793005ULL> mt19937_64;
2501
2502// subtract_with_carry_engine
2503
2504template<class _UIntType, size_t __w, size_t __s, size_t __r>
2505class _LIBCPP_TEMPLATE_VIS subtract_with_carry_engine;
2506
2507template<class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
2508bool
2509operator==(
2510 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
2511 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y);
2512
2513template<class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
2514_LIBCPP_INLINE_VISIBILITY
2515bool
2516operator!=(
2517 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
2518 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y);
2519
2520template <class _CharT, class _Traits,
2521 class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
2522basic_ostream<_CharT, _Traits>&
2523operator<<(basic_ostream<_CharT, _Traits>& __os,
2524 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x);
2525
2526template <class _CharT, class _Traits,
2527 class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
2528basic_istream<_CharT, _Traits>&
2529operator>>(basic_istream<_CharT, _Traits>& __is,
2530 subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x);
2531
2532template<class _UIntType, size_t __w, size_t __s, size_t __r>
2533class _LIBCPP_TEMPLATE_VIS subtract_with_carry_engine
2534{
2535public:
2536 // types
2537 typedef _UIntType result_type;
2538
2539private:
2540 result_type __x_[__r];
2541 result_type __c_;
2542 size_t __i_;
2543
2544 static _LIBCPP_CONSTEXPR const result_type _Dt = numeric_limits<result_type>::digits;
2545 static_assert( 0 < __w, "subtract_with_carry_engine invalid parameters");
2546 static_assert(__w <= _Dt, "subtract_with_carry_engine invalid parameters");
2547 static_assert( 0 < __s, "subtract_with_carry_engine invalid parameters");
2548 static_assert(__s < __r, "subtract_with_carry_engine invalid parameters");
2549public:
2550 static _LIBCPP_CONSTEXPR const result_type _Min = 0;
2551 static _LIBCPP_CONSTEXPR const result_type _Max = __w == _Dt ? result_type(~0) :
2552 (result_type(1) << __w) - result_type(1);
2553 static_assert(_Min < _Max, "subtract_with_carry_engine invalid parameters");
2554
2555 // engine characteristics
2556 static _LIBCPP_CONSTEXPR const size_t word_size = __w;
2557 static _LIBCPP_CONSTEXPR const size_t short_lag = __s;
2558 static _LIBCPP_CONSTEXPR const size_t long_lag = __r;
2559 _LIBCPP_INLINE_VISIBILITY
2560 static _LIBCPP_CONSTEXPR result_type min() { return _Min; }
2561 _LIBCPP_INLINE_VISIBILITY
2562 static _LIBCPP_CONSTEXPR result_type max() { return _Max; }
2563 static _LIBCPP_CONSTEXPR const result_type default_seed = 19780503u;
2564
2565 // constructors and seeding functions
2566 _LIBCPP_INLINE_VISIBILITY
2567 explicit subtract_with_carry_engine(result_type __sd = default_seed)
2568 {seed(__sd);}
2569 template<class _Sseq>
2570 _LIBCPP_INLINE_VISIBILITY
2571 explicit subtract_with_carry_engine(_Sseq& __q,
2572 typename enable_if<__is_seed_sequence<_Sseq, subtract_with_carry_engine>::value>::type* = 0)
2573 {seed(__q);}
2574 _LIBCPP_INLINE_VISIBILITY
2575 void seed(result_type __sd = default_seed)
2576 {seed(__sd, integral_constant<unsigned, 1 + (__w - 1) / 32>());}
2577 template<class _Sseq>
2578 _LIBCPP_INLINE_VISIBILITY
2579 typename enable_if
2580 <
2581 __is_seed_sequence<_Sseq, subtract_with_carry_engine>::value,
2582 void
2583 >::type
2584 seed(_Sseq& __q)
2585 {__seed(__q, integral_constant<unsigned, 1 + (__w - 1) / 32>());}
2586
2587 // generating functions
2588 result_type operator()();
2589 _LIBCPP_INLINE_VISIBILITY
2590 void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
2591
2592 template<class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
2593 friend
2594 bool
2595 operator==(
2596 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
2597 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y);
2598
2599 template<class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
2600 friend
2601 bool
2602 operator!=(
2603 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
2604 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y);
2605
2606 template <class _CharT, class _Traits,
2607 class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
2608 friend
2609 basic_ostream<_CharT, _Traits>&
2610 operator<<(basic_ostream<_CharT, _Traits>& __os,
2611 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x);
2612
2613 template <class _CharT, class _Traits,
2614 class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
2615 friend
2616 basic_istream<_CharT, _Traits>&
2617 operator>>(basic_istream<_CharT, _Traits>& __is,
2618 subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x);
2619
2620private:
2621
2622 void seed(result_type __sd, integral_constant<unsigned, 1>);
2623 void seed(result_type __sd, integral_constant<unsigned, 2>);
2624 template<class _Sseq>
2625 void __seed(_Sseq& __q, integral_constant<unsigned, 1>);
2626 template<class _Sseq>
2627 void __seed(_Sseq& __q, integral_constant<unsigned, 2>);
2628};
2629
2630template<class _UIntType, size_t __w, size_t __s, size_t __r>
2631 _LIBCPP_CONSTEXPR const size_t subtract_with_carry_engine<_UIntType, __w, __s, __r>::word_size;
2632
2633template<class _UIntType, size_t __w, size_t __s, size_t __r>
2634 _LIBCPP_CONSTEXPR const size_t subtract_with_carry_engine<_UIntType, __w, __s, __r>::short_lag;
2635
2636template<class _UIntType, size_t __w, size_t __s, size_t __r>
2637 _LIBCPP_CONSTEXPR const size_t subtract_with_carry_engine<_UIntType, __w, __s, __r>::long_lag;
2638
2639template<class _UIntType, size_t __w, size_t __s, size_t __r>
2640 _LIBCPP_CONSTEXPR const typename subtract_with_carry_engine<_UIntType, __w, __s, __r>::result_type
2641 subtract_with_carry_engine<_UIntType, __w, __s, __r>::default_seed;
2642
2643template<class _UIntType, size_t __w, size_t __s, size_t __r>
2644void
2645subtract_with_carry_engine<_UIntType, __w, __s, __r>::seed(result_type __sd,
2646 integral_constant<unsigned, 1>)
2647{
2648 linear_congruential_engine<result_type, 40014u, 0u, 2147483563u>
2649 __e(__sd == 0u ? default_seed : __sd);
2650 for (size_t __i = 0; __i < __r; ++__i)
2651 __x_[__i] = static_cast<result_type>(__e() & _Max);
2652 __c_ = __x_[__r-1] == 0;
2653 __i_ = 0;
2654}
2655
2656template<class _UIntType, size_t __w, size_t __s, size_t __r>
2657void
2658subtract_with_carry_engine<_UIntType, __w, __s, __r>::seed(result_type __sd,
2659 integral_constant<unsigned, 2>)
2660{
2661 linear_congruential_engine<result_type, 40014u, 0u, 2147483563u>
2662 __e(__sd == 0u ? default_seed : __sd);
2663 for (size_t __i = 0; __i < __r; ++__i)
2664 {
2665 result_type __e0 = __e();
2666 __x_[__i] = static_cast<result_type>(
2667 (__e0 + ((uint64_t)__e() << 32)) & _Max);
2668 }
2669 __c_ = __x_[__r-1] == 0;
2670 __i_ = 0;
2671}
2672
2673template<class _UIntType, size_t __w, size_t __s, size_t __r>
2674template<class _Sseq>
2675void
2676subtract_with_carry_engine<_UIntType, __w, __s, __r>::__seed(_Sseq& __q,
2677 integral_constant<unsigned, 1>)
2678{
2679 const unsigned __k = 1;
2680 uint32_t __ar[__r * __k];
2681 __q.generate(__ar, __ar + __r * __k);
2682 for (size_t __i = 0; __i < __r; ++__i)
2683 __x_[__i] = static_cast<result_type>(__ar[__i] & _Max);
2684 __c_ = __x_[__r-1] == 0;
2685 __i_ = 0;
2686}
2687
2688template<class _UIntType, size_t __w, size_t __s, size_t __r>
2689template<class _Sseq>
2690void
2691subtract_with_carry_engine<_UIntType, __w, __s, __r>::__seed(_Sseq& __q,
2692 integral_constant<unsigned, 2>)
2693{
2694 const unsigned __k = 2;
2695 uint32_t __ar[__r * __k];
2696 __q.generate(__ar, __ar + __r * __k);
2697 for (size_t __i = 0; __i < __r; ++__i)
2698 __x_[__i] = static_cast<result_type>(
2699 (__ar[2 * __i] + ((uint64_t)__ar[2 * __i + 1] << 32)) & _Max);
2700 __c_ = __x_[__r-1] == 0;
2701 __i_ = 0;
2702}
2703
2704template<class _UIntType, size_t __w, size_t __s, size_t __r>
2705_UIntType
2706subtract_with_carry_engine<_UIntType, __w, __s, __r>::operator()()
2707{
2708 const result_type& __xs = __x_[(__i_ + (__r - __s)) % __r];
2709 result_type& __xr = __x_[__i_];
2710 result_type __new_c = __c_ == 0 ? __xs < __xr : __xs != 0 ? __xs <= __xr : 1;
2711 __xr = (__xs - __xr - __c_) & _Max;
2712 __c_ = __new_c;
2713 __i_ = (__i_ + 1) % __r;
2714 return __xr;
2715}
2716
2717template<class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
2718bool
2719operator==(
2720 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
2721 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y)
2722{
2723 if (__x.__c_ != __y.__c_)
2724 return false;
2725 if (__x.__i_ == __y.__i_)
2726 return _VSTD::equal(__x.__x_, __x.__x_ + _Rp, __y.__x_);
2727 if (__x.__i_ == 0 || __y.__i_ == 0)
2728 {
2729 size_t __j = _VSTD::min(_Rp - __x.__i_, _Rp - __y.__i_);
2730 if (!_VSTD::equal(__x.__x_ + __x.__i_, __x.__x_ + __x.__i_ + __j,
2731 __y.__x_ + __y.__i_))
2732 return false;
2733 if (__x.__i_ == 0)
2734 return _VSTD::equal(__x.__x_ + __j, __x.__x_ + _Rp, __y.__x_);
2735 return _VSTD::equal(__x.__x_, __x.__x_ + (_Rp - __j), __y.__x_ + __j);
2736 }
2737 if (__x.__i_ < __y.__i_)
2738 {
2739 size_t __j = _Rp - __y.__i_;
2740 if (!_VSTD::equal(__x.__x_ + __x.__i_, __x.__x_ + (__x.__i_ + __j),
2741 __y.__x_ + __y.__i_))
2742 return false;
2743 if (!_VSTD::equal(__x.__x_ + (__x.__i_ + __j), __x.__x_ + _Rp,
2744 __y.__x_))
2745 return false;
2746 return _VSTD::equal(__x.__x_, __x.__x_ + __x.__i_,
2747 __y.__x_ + (_Rp - (__x.__i_ + __j)));
2748 }
2749 size_t __j = _Rp - __x.__i_;
2750 if (!_VSTD::equal(__y.__x_ + __y.__i_, __y.__x_ + (__y.__i_ + __j),
2751 __x.__x_ + __x.__i_))
2752 return false;
2753 if (!_VSTD::equal(__y.__x_ + (__y.__i_ + __j), __y.__x_ + _Rp,
2754 __x.__x_))
2755 return false;
2756 return _VSTD::equal(__y.__x_, __y.__x_ + __y.__i_,
2757 __x.__x_ + (_Rp - (__y.__i_ + __j)));
2758}
2759
2760template<class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
2761inline _LIBCPP_INLINE_VISIBILITY
2762bool
2763operator!=(
2764 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
2765 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y)
2766{
2767 return !(__x == __y);
2768}
2769
2770template <class _CharT, class _Traits,
2771 class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
2772basic_ostream<_CharT, _Traits>&
2773operator<<(basic_ostream<_CharT, _Traits>& __os,
2774 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x)
2775{
2776 __save_flags<_CharT, _Traits> __lx(__os);
2777 __os.flags(ios_base::dec | ios_base::left);
2778 _CharT __sp = __os.widen(' ');
2779 __os.fill(__sp);
2780 __os << __x.__x_[__x.__i_];
2781 for (size_t __j = __x.__i_ + 1; __j < _Rp; ++__j)
2782 __os << __sp << __x.__x_[__j];
2783 for (size_t __j = 0; __j < __x.__i_; ++__j)
2784 __os << __sp << __x.__x_[__j];
2785 __os << __sp << __x.__c_;
2786 return __os;
2787}
2788
2789template <class _CharT, class _Traits,
2790 class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
2791basic_istream<_CharT, _Traits>&
2792operator>>(basic_istream<_CharT, _Traits>& __is,
2793 subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x)
2794{
2795 __save_flags<_CharT, _Traits> __lx(__is);
2796 __is.flags(ios_base::dec | ios_base::skipws);
2797 _UInt __t[_Rp+1];
2798 for (size_t __i = 0; __i < _Rp+1; ++__i)
2799 __is >> __t[__i];
2800 if (!__is.fail())
2801 {
2802 for (size_t __i = 0; __i < _Rp; ++__i)
2803 __x.__x_[__i] = __t[__i];
2804 __x.__c_ = __t[_Rp];
2805 __x.__i_ = 0;
2806 }
2807 return __is;
2808}
2809
2810typedef subtract_with_carry_engine<uint_fast32_t, 24, 10, 24> ranlux24_base;
2811typedef subtract_with_carry_engine<uint_fast64_t, 48, 5, 12> ranlux48_base;
2812
2813// discard_block_engine
2814
2815template<class _Engine, size_t __p, size_t __r>
2816class _LIBCPP_TEMPLATE_VIS discard_block_engine
2817{
2818 _Engine __e_;
2819 int __n_;
2820
2821 static_assert( 0 < __r, "discard_block_engine invalid parameters");
2822 static_assert(__r <= __p, "discard_block_engine invalid parameters");
2823 static_assert(__r <= INT_MAX, "discard_block_engine invalid parameters");
2824public:
2825 // types
2826 typedef typename _Engine::result_type result_type;
2827
2828 // engine characteristics
2829 static _LIBCPP_CONSTEXPR const size_t block_size = __p;
2830 static _LIBCPP_CONSTEXPR const size_t used_block = __r;
2831
2832#ifdef _LIBCPP_CXX03_LANG
2833 static const result_type _Min = _Engine::_Min;
2834 static const result_type _Max = _Engine::_Max;
2835#else
2836 static _LIBCPP_CONSTEXPR const result_type _Min = _Engine::min();
2837 static _LIBCPP_CONSTEXPR const result_type _Max = _Engine::max();
2838#endif
2839
2840 _LIBCPP_INLINE_VISIBILITY
2841 static _LIBCPP_CONSTEXPR result_type min() { return _Engine::min(); }
2842 _LIBCPP_INLINE_VISIBILITY
2843 static _LIBCPP_CONSTEXPR result_type max() { return _Engine::max(); }
2844
2845 // constructors and seeding functions
2846 _LIBCPP_INLINE_VISIBILITY
2847 discard_block_engine() : __n_(0) {}
2848 _LIBCPP_INLINE_VISIBILITY
2849 explicit discard_block_engine(const _Engine& __e)
2850 : __e_(__e), __n_(0) {}
2851#ifndef _LIBCPP_CXX03_LANG
2852 _LIBCPP_INLINE_VISIBILITY
2853 explicit discard_block_engine(_Engine&& __e)
2854 : __e_(_VSTD::move(__e)), __n_(0) {}
2855#endif // _LIBCPP_CXX03_LANG
2856 _LIBCPP_INLINE_VISIBILITY
2857 explicit discard_block_engine(result_type __sd) : __e_(__sd), __n_(0) {}
2858 template<class _Sseq>
2859 _LIBCPP_INLINE_VISIBILITY
2860 explicit discard_block_engine(_Sseq& __q,
2861 typename enable_if<__is_seed_sequence<_Sseq, discard_block_engine>::value &&
2862 !is_convertible<_Sseq, _Engine>::value>::type* = 0)
2863 : __e_(__q), __n_(0) {}
2864 _LIBCPP_INLINE_VISIBILITY
2865 void seed() {__e_.seed(); __n_ = 0;}
2866 _LIBCPP_INLINE_VISIBILITY
2867 void seed(result_type __sd) {__e_.seed(__sd); __n_ = 0;}
2868 template<class _Sseq>
2869 _LIBCPP_INLINE_VISIBILITY
2870 typename enable_if
2871 <
2872 __is_seed_sequence<_Sseq, discard_block_engine>::value,
2873 void
2874 >::type
2875 seed(_Sseq& __q) {__e_.seed(__q); __n_ = 0;}
2876
2877 // generating functions
2878 result_type operator()();
2879 _LIBCPP_INLINE_VISIBILITY
2880 void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
2881
2882 // property functions
2883 _LIBCPP_INLINE_VISIBILITY
2884 const _Engine& base() const _NOEXCEPT {return __e_;}
2885
2886 template<class _Eng, size_t _Pp, size_t _Rp>
2887 friend
2888 bool
2889 operator==(
2890 const discard_block_engine<_Eng, _Pp, _Rp>& __x,
2891 const discard_block_engine<_Eng, _Pp, _Rp>& __y);
2892
2893 template<class _Eng, size_t _Pp, size_t _Rp>
2894 friend
2895 bool
2896 operator!=(
2897 const discard_block_engine<_Eng, _Pp, _Rp>& __x,
2898 const discard_block_engine<_Eng, _Pp, _Rp>& __y);
2899
2900 template <class _CharT, class _Traits,
2901 class _Eng, size_t _Pp, size_t _Rp>
2902 friend
2903 basic_ostream<_CharT, _Traits>&
2904 operator<<(basic_ostream<_CharT, _Traits>& __os,
2905 const discard_block_engine<_Eng, _Pp, _Rp>& __x);
2906
2907 template <class _CharT, class _Traits,
2908 class _Eng, size_t _Pp, size_t _Rp>
2909 friend
2910 basic_istream<_CharT, _Traits>&
2911 operator>>(basic_istream<_CharT, _Traits>& __is,
2912 discard_block_engine<_Eng, _Pp, _Rp>& __x);
2913};
2914
2915template<class _Engine, size_t __p, size_t __r>
2916 _LIBCPP_CONSTEXPR const size_t discard_block_engine<_Engine, __p, __r>::block_size;
2917
2918template<class _Engine, size_t __p, size_t __r>
2919 _LIBCPP_CONSTEXPR const size_t discard_block_engine<_Engine, __p, __r>::used_block;
2920
2921template<class _Engine, size_t __p, size_t __r>
2922typename discard_block_engine<_Engine, __p, __r>::result_type
2923discard_block_engine<_Engine, __p, __r>::operator()()
2924{
2925 if (__n_ >= static_cast<int>(__r))
2926 {
2927 __e_.discard(__p - __r);
2928 __n_ = 0;
2929 }
2930 ++__n_;
2931 return __e_();
2932}
2933
2934template<class _Eng, size_t _Pp, size_t _Rp>
2935inline _LIBCPP_INLINE_VISIBILITY
2936bool
2937operator==(const discard_block_engine<_Eng, _Pp, _Rp>& __x,
2938 const discard_block_engine<_Eng, _Pp, _Rp>& __y)
2939{
2940 return __x.__n_ == __y.__n_ && __x.__e_ == __y.__e_;
2941}
2942
2943template<class _Eng, size_t _Pp, size_t _Rp>
2944inline _LIBCPP_INLINE_VISIBILITY
2945bool
2946operator!=(const discard_block_engine<_Eng, _Pp, _Rp>& __x,
2947 const discard_block_engine<_Eng, _Pp, _Rp>& __y)
2948{
2949 return !(__x == __y);
2950}
2951
2952template <class _CharT, class _Traits,
2953 class _Eng, size_t _Pp, size_t _Rp>
2954basic_ostream<_CharT, _Traits>&
2955operator<<(basic_ostream<_CharT, _Traits>& __os,
2956 const discard_block_engine<_Eng, _Pp, _Rp>& __x)
2957{
2958 __save_flags<_CharT, _Traits> __lx(__os);
2959 __os.flags(ios_base::dec | ios_base::left);
2960 _CharT __sp = __os.widen(' ');
2961 __os.fill(__sp);
2962 return __os << __x.__e_ << __sp << __x.__n_;
2963}
2964
2965template <class _CharT, class _Traits,
2966 class _Eng, size_t _Pp, size_t _Rp>
2967basic_istream<_CharT, _Traits>&
2968operator>>(basic_istream<_CharT, _Traits>& __is,
2969 discard_block_engine<_Eng, _Pp, _Rp>& __x)
2970{
2971 __save_flags<_CharT, _Traits> __lx(__is);
2972 __is.flags(ios_base::dec | ios_base::skipws);
2973 _Eng __e;
2974 int __n;
2975 __is >> __e >> __n;
2976 if (!__is.fail())
2977 {
2978 __x.__e_ = __e;
2979 __x.__n_ = __n;
2980 }
2981 return __is;
2982}
2983
2984typedef discard_block_engine<ranlux24_base, 223, 23> ranlux24;
2985typedef discard_block_engine<ranlux48_base, 389, 11> ranlux48;
2986
2987// independent_bits_engine
2988
2989template<class _Engine, size_t __w, class _UIntType>
2990class _LIBCPP_TEMPLATE_VIS independent_bits_engine
2991{
2992 template <class _UInt, _UInt _R0, size_t _Wp, size_t _Mp>
2993 class __get_n
2994 {
2995 static _LIBCPP_CONSTEXPR const size_t _Dt = numeric_limits<_UInt>::digits;
2996 static _LIBCPP_CONSTEXPR const size_t _Np = _Wp / _Mp + (_Wp % _Mp != 0);
2997 static _LIBCPP_CONSTEXPR const size_t _W0 = _Wp / _Np;
2998 static _LIBCPP_CONSTEXPR const _UInt _Y0 = _W0 >= _Dt ? 0 : (_R0 >> _W0) << _W0;
2999 public:
3000 static _LIBCPP_CONSTEXPR const size_t value = _R0 - _Y0 > _Y0 / _Np ? _Np + 1 : _Np;
3001 };
3002public:
3003 // types
3004 typedef _UIntType result_type;
3005
3006private:
3007 _Engine __e_;
3008
3009 static _LIBCPP_CONSTEXPR const result_type _Dt = numeric_limits<result_type>::digits;
3010 static_assert( 0 < __w, "independent_bits_engine invalid parameters");
3011 static_assert(__w <= _Dt, "independent_bits_engine invalid parameters");
3012
3013 typedef typename _Engine::result_type _Engine_result_type;
3014 typedef typename conditional
3015 <
3016 sizeof(_Engine_result_type) <= sizeof(result_type),
3017 result_type,
3018 _Engine_result_type
3019 >::type _Working_result_type;
3020#ifdef _LIBCPP_CXX03_LANG
3021 static const _Working_result_type _Rp = _Engine::_Max - _Engine::_Min
3022 + _Working_result_type(1);
3023#else
3024 static _LIBCPP_CONSTEXPR const _Working_result_type _Rp = _Engine::max() - _Engine::min()
3025 + _Working_result_type(1);
3026#endif
3027 static _LIBCPP_CONSTEXPR const size_t __m = __log2<_Working_result_type, _Rp>::value;
3028 static _LIBCPP_CONSTEXPR const size_t __n = __get_n<_Working_result_type, _Rp, __w, __m>::value;
3029 static _LIBCPP_CONSTEXPR const size_t __w0 = __w / __n;
3030 static _LIBCPP_CONSTEXPR const size_t __n0 = __n - __w % __n;
3031 static _LIBCPP_CONSTEXPR const size_t _WDt = numeric_limits<_Working_result_type>::digits;
3032 static _LIBCPP_CONSTEXPR const size_t _EDt = numeric_limits<_Engine_result_type>::digits;
3033 static _LIBCPP_CONSTEXPR const _Working_result_type __y0 = __w0 >= _WDt ? 0 :
3034 (_Rp >> __w0) << __w0;
3035 static _LIBCPP_CONSTEXPR const _Working_result_type __y1 = __w0 >= _WDt - 1 ? 0 :
3036 (_Rp >> (__w0+1)) << (__w0+1);
3037 static _LIBCPP_CONSTEXPR const _Engine_result_type __mask0 = __w0 > 0 ?
3038 _Engine_result_type(~0) >> (_EDt - __w0) :
3039 _Engine_result_type(0);
3040 static _LIBCPP_CONSTEXPR const _Engine_result_type __mask1 = __w0 < _EDt - 1 ?
3041 _Engine_result_type(~0) >> (_EDt - (__w0 + 1)) :
3042 _Engine_result_type(~0);
3043public:
3044 static _LIBCPP_CONSTEXPR const result_type _Min = 0;
3045 static _LIBCPP_CONSTEXPR const result_type _Max = __w == _Dt ? result_type(~0) :
3046 (result_type(1) << __w) - result_type(1);
3047 static_assert(_Min < _Max, "independent_bits_engine invalid parameters");
3048
3049 // engine characteristics
3050 _LIBCPP_INLINE_VISIBILITY
3051 static _LIBCPP_CONSTEXPR result_type min() { return _Min; }
3052 _LIBCPP_INLINE_VISIBILITY
3053 static _LIBCPP_CONSTEXPR result_type max() { return _Max; }
3054
3055 // constructors and seeding functions
3056 _LIBCPP_INLINE_VISIBILITY
3057 independent_bits_engine() {}
3058 _LIBCPP_INLINE_VISIBILITY
3059 explicit independent_bits_engine(const _Engine& __e)
3060 : __e_(__e) {}
3061#ifndef _LIBCPP_CXX03_LANG
3062 _LIBCPP_INLINE_VISIBILITY
3063 explicit independent_bits_engine(_Engine&& __e)
3064 : __e_(_VSTD::move(__e)) {}
3065#endif // _LIBCPP_CXX03_LANG
3066 _LIBCPP_INLINE_VISIBILITY
3067 explicit independent_bits_engine(result_type __sd) : __e_(__sd) {}
3068 template<class _Sseq>
3069 _LIBCPP_INLINE_VISIBILITY
3070 explicit independent_bits_engine(_Sseq& __q,
3071 typename enable_if<__is_seed_sequence<_Sseq, independent_bits_engine>::value &&
3072 !is_convertible<_Sseq, _Engine>::value>::type* = 0)
3073 : __e_(__q) {}
3074 _LIBCPP_INLINE_VISIBILITY
3075 void seed() {__e_.seed();}
3076 _LIBCPP_INLINE_VISIBILITY
3077 void seed(result_type __sd) {__e_.seed(__sd);}
3078 template<class _Sseq>
3079 _LIBCPP_INLINE_VISIBILITY
3080 typename enable_if
3081 <
3082 __is_seed_sequence<_Sseq, independent_bits_engine>::value,
3083 void
3084 >::type
3085 seed(_Sseq& __q) {__e_.seed(__q);}
3086
3087 // generating functions
3088 _LIBCPP_INLINE_VISIBILITY
3089 result_type operator()() {return __eval(integral_constant<bool, _Rp != 0>());}
3090 _LIBCPP_INLINE_VISIBILITY
3091 void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
3092
3093 // property functions
3094 _LIBCPP_INLINE_VISIBILITY
3095 const _Engine& base() const _NOEXCEPT {return __e_;}
3096
3097 template<class _Eng, size_t _Wp, class _UInt>
3098 friend
3099 bool
3100 operator==(
3101 const independent_bits_engine<_Eng, _Wp, _UInt>& __x,
3102 const independent_bits_engine<_Eng, _Wp, _UInt>& __y);
3103
3104 template<class _Eng, size_t _Wp, class _UInt>
3105 friend
3106 bool
3107 operator!=(
3108 const independent_bits_engine<_Eng, _Wp, _UInt>& __x,
3109 const independent_bits_engine<_Eng, _Wp, _UInt>& __y);
3110
3111 template <class _CharT, class _Traits,
3112 class _Eng, size_t _Wp, class _UInt>
3113 friend
3114 basic_ostream<_CharT, _Traits>&
3115 operator<<(basic_ostream<_CharT, _Traits>& __os,
3116 const independent_bits_engine<_Eng, _Wp, _UInt>& __x);
3117
3118 template <class _CharT, class _Traits,
3119 class _Eng, size_t _Wp, class _UInt>
3120 friend
3121 basic_istream<_CharT, _Traits>&
3122 operator>>(basic_istream<_CharT, _Traits>& __is,
3123 independent_bits_engine<_Eng, _Wp, _UInt>& __x);
3124
3125private:
3126 _LIBCPP_INLINE_VISIBILITY
3127 result_type __eval(false_type);
3128 result_type __eval(true_type);
3129
3130 template <size_t __count>
3131 _LIBCPP_INLINE_VISIBILITY
3132 static
3133 typename enable_if
3134 <
3135 __count < _Dt,
3136 result_type
3137 >::type
3138 __lshift(result_type __x) {return __x << __count;}
3139
3140 template <size_t __count>
3141 _LIBCPP_INLINE_VISIBILITY
3142 static
3143 typename enable_if
3144 <
3145 (__count >= _Dt),
3146 result_type
3147 >::type
3148 __lshift(result_type) {return result_type(0);}
3149};
3150
3151template<class _Engine, size_t __w, class _UIntType>
3152inline
3153_UIntType
3154independent_bits_engine<_Engine, __w, _UIntType>::__eval(false_type)
3155{
3156 return static_cast<result_type>(__e_() & __mask0);
3157}
3158
3159template<class _Engine, size_t __w, class _UIntType>
3160_UIntType
3161independent_bits_engine<_Engine, __w, _UIntType>::__eval(true_type)
3162{
3163 result_type _Sp = 0;
3164 for (size_t __k = 0; __k < __n0; ++__k)
3165 {
3166 _Engine_result_type __u;
3167 do
3168 {
3169 __u = __e_() - _Engine::min();
3170 } while (__u >= __y0);
3171 _Sp = static_cast<result_type>(__lshift<__w0>(_Sp) + (__u & __mask0));
3172 }
3173 for (size_t __k = __n0; __k < __n; ++__k)
3174 {
3175 _Engine_result_type __u;
3176 do
3177 {
3178 __u = __e_() - _Engine::min();
3179 } while (__u >= __y1);
3180 _Sp = static_cast<result_type>(__lshift<__w0+1>(_Sp) + (__u & __mask1));
3181 }
3182 return _Sp;
3183}
3184
3185template<class _Eng, size_t _Wp, class _UInt>
3186inline _LIBCPP_INLINE_VISIBILITY
3187bool
3188operator==(
3189 const independent_bits_engine<_Eng, _Wp, _UInt>& __x,
3190 const independent_bits_engine<_Eng, _Wp, _UInt>& __y)
3191{
3192 return __x.base() == __y.base();
3193}
3194
3195template<class _Eng, size_t _Wp, class _UInt>
3196inline _LIBCPP_INLINE_VISIBILITY
3197bool
3198operator!=(
3199 const independent_bits_engine<_Eng, _Wp, _UInt>& __x,
3200 const independent_bits_engine<_Eng, _Wp, _UInt>& __y)
3201{
3202 return !(__x == __y);
3203}
3204
3205template <class _CharT, class _Traits,
3206 class _Eng, size_t _Wp, class _UInt>
3207basic_ostream<_CharT, _Traits>&
3208operator<<(basic_ostream<_CharT, _Traits>& __os,
3209 const independent_bits_engine<_Eng, _Wp, _UInt>& __x)
3210{
3211 return __os << __x.base();
3212}
3213
3214template <class _CharT, class _Traits,
3215 class _Eng, size_t _Wp, class _UInt>
3216basic_istream<_CharT, _Traits>&
3217operator>>(basic_istream<_CharT, _Traits>& __is,
3218 independent_bits_engine<_Eng, _Wp, _UInt>& __x)
3219{
3220 _Eng __e;
3221 __is >> __e;
3222 if (!__is.fail())
3223 __x.__e_ = __e;
3224 return __is;
3225}
3226
3227// shuffle_order_engine
3228
3229template <uint64_t _Xp, uint64_t _Yp>
3230struct __ugcd
3231{
3232 static _LIBCPP_CONSTEXPR const uint64_t value = __ugcd<_Yp, _Xp % _Yp>::value;
3233};
3234
3235template <uint64_t _Xp>
3236struct __ugcd<_Xp, 0>
3237{
3238 static _LIBCPP_CONSTEXPR const uint64_t value = _Xp;
3239};
3240
3241template <uint64_t _Np, uint64_t _Dp>
3242class __uratio
3243{
3244 static_assert(_Dp != 0, "__uratio divide by 0");
3245 static _LIBCPP_CONSTEXPR const uint64_t __gcd = __ugcd<_Np, _Dp>::value;
3246public:
3247 static _LIBCPP_CONSTEXPR const uint64_t num = _Np / __gcd;
3248 static _LIBCPP_CONSTEXPR const uint64_t den = _Dp / __gcd;
3249
3250 typedef __uratio<num, den> type;
3251};
3252
3253template<class _Engine, size_t __k>
3254class _LIBCPP_TEMPLATE_VIS shuffle_order_engine
3255{
3256 static_assert(0 < __k, "shuffle_order_engine invalid parameters");
3257public:
3258 // types
3259 typedef typename _Engine::result_type result_type;
3260
3261private:
3262 _Engine __e_;
3263 result_type _V_[__k];
3264 result_type _Y_;
3265
3266public:
3267 // engine characteristics
3268 static _LIBCPP_CONSTEXPR const size_t table_size = __k;
3269
3270#ifdef _LIBCPP_CXX03_LANG
3271 static const result_type _Min = _Engine::_Min;
3272 static const result_type _Max = _Engine::_Max;
3273#else
3274 static _LIBCPP_CONSTEXPR const result_type _Min = _Engine::min();
3275 static _LIBCPP_CONSTEXPR const result_type _Max = _Engine::max();
3276#endif
3277 static_assert(_Min < _Max, "shuffle_order_engine invalid parameters");
3278 _LIBCPP_INLINE_VISIBILITY
3279 static _LIBCPP_CONSTEXPR result_type min() { return _Min; }
3280 _LIBCPP_INLINE_VISIBILITY
3281 static _LIBCPP_CONSTEXPR result_type max() { return _Max; }
3282
3283 static _LIBCPP_CONSTEXPR const unsigned long long _Rp = _Max - _Min + 1ull;
3284
3285 // constructors and seeding functions
3286 _LIBCPP_INLINE_VISIBILITY
3287 shuffle_order_engine() {__init();}
3288 _LIBCPP_INLINE_VISIBILITY
3289 explicit shuffle_order_engine(const _Engine& __e)
3290 : __e_(__e) {__init();}
3291#ifndef _LIBCPP_CXX03_LANG
3292 _LIBCPP_INLINE_VISIBILITY
3293 explicit shuffle_order_engine(_Engine&& __e)
3294 : __e_(_VSTD::move(__e)) {__init();}
3295#endif // _LIBCPP_CXX03_LANG
3296 _LIBCPP_INLINE_VISIBILITY
3297 explicit shuffle_order_engine(result_type __sd) : __e_(__sd) {__init();}
3298 template<class _Sseq>
3299 _LIBCPP_INLINE_VISIBILITY
3300 explicit shuffle_order_engine(_Sseq& __q,
3301 typename enable_if<__is_seed_sequence<_Sseq, shuffle_order_engine>::value &&
3302 !is_convertible<_Sseq, _Engine>::value>::type* = 0)
3303 : __e_(__q) {__init();}
3304 _LIBCPP_INLINE_VISIBILITY
3305 void seed() {__e_.seed(); __init();}
3306 _LIBCPP_INLINE_VISIBILITY
3307 void seed(result_type __sd) {__e_.seed(__sd); __init();}
3308 template<class _Sseq>
3309 _LIBCPP_INLINE_VISIBILITY
3310 typename enable_if
3311 <
3312 __is_seed_sequence<_Sseq, shuffle_order_engine>::value,
3313 void
3314 >::type
3315 seed(_Sseq& __q) {__e_.seed(__q); __init();}
3316
3317 // generating functions
3318 _LIBCPP_INLINE_VISIBILITY
3319 result_type operator()() {return __eval(integral_constant<bool, _Rp != 0>());}
3320 _LIBCPP_INLINE_VISIBILITY
3321 void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
3322
3323 // property functions
3324 _LIBCPP_INLINE_VISIBILITY
3325 const _Engine& base() const _NOEXCEPT {return __e_;}
3326
3327private:
3328 template<class _Eng, size_t _Kp>
3329 friend
3330 bool
3331 operator==(
3332 const shuffle_order_engine<_Eng, _Kp>& __x,
3333 const shuffle_order_engine<_Eng, _Kp>& __y);
3334
3335 template<class _Eng, size_t _Kp>
3336 friend
3337 bool
3338 operator!=(
3339 const shuffle_order_engine<_Eng, _Kp>& __x,
3340 const shuffle_order_engine<_Eng, _Kp>& __y);
3341
3342 template <class _CharT, class _Traits,
3343 class _Eng, size_t _Kp>
3344 friend
3345 basic_ostream<_CharT, _Traits>&
3346 operator<<(basic_ostream<_CharT, _Traits>& __os,
3347 const shuffle_order_engine<_Eng, _Kp>& __x);
3348
3349 template <class _CharT, class _Traits,
3350 class _Eng, size_t _Kp>
3351 friend
3352 basic_istream<_CharT, _Traits>&
3353 operator>>(basic_istream<_CharT, _Traits>& __is,
3354 shuffle_order_engine<_Eng, _Kp>& __x);
3355
3356 _LIBCPP_INLINE_VISIBILITY
3357 void __init()
3358 {
3359 for (size_t __i = 0; __i < __k; ++__i)
3360 _V_[__i] = __e_();
3361 _Y_ = __e_();
3362 }
3363
3364 _LIBCPP_INLINE_VISIBILITY
3365 result_type __eval(false_type) {return __eval2(integral_constant<bool, __k & 1>());}
3366 _LIBCPP_INLINE_VISIBILITY
3367 result_type __eval(true_type) {return __eval(__uratio<__k, _Rp>());}
3368
3369 _LIBCPP_INLINE_VISIBILITY
3370 result_type __eval2(false_type) {return __eval(__uratio<__k/2, 0x8000000000000000ull>());}
3371 _LIBCPP_INLINE_VISIBILITY
3372 result_type __eval2(true_type) {return __evalf<__k, 0>();}
3373
3374 template <uint64_t _Np, uint64_t _Dp>
3375 _LIBCPP_INLINE_VISIBILITY
3376 typename enable_if
3377 <
3378 (__uratio<_Np, _Dp>::num > 0xFFFFFFFFFFFFFFFFull / (_Max - _Min)),
3379 result_type
3380 >::type
3381 __eval(__uratio<_Np, _Dp>)
3382 {return __evalf<__uratio<_Np, _Dp>::num, __uratio<_Np, _Dp>::den>();}
3383
3384 template <uint64_t _Np, uint64_t _Dp>
3385 _LIBCPP_INLINE_VISIBILITY
3386 typename enable_if
3387 <
3388 __uratio<_Np, _Dp>::num <= 0xFFFFFFFFFFFFFFFFull / (_Max - _Min),
3389 result_type
3390 >::type
3391 __eval(__uratio<_Np, _Dp>)
3392 {
3393 const size_t __j = static_cast<size_t>(__uratio<_Np, _Dp>::num * (_Y_ - _Min)
3394 / __uratio<_Np, _Dp>::den);
3395 _Y_ = _V_[__j];
3396 _V_[__j] = __e_();
3397 return _Y_;
3398 }
3399
3400 template <uint64_t __n, uint64_t __d>
3401 _LIBCPP_INLINE_VISIBILITY
3402 result_type __evalf()
3403 {
3404 const double _Fp = __d == 0 ?
3405 __n / (2. * 0x8000000000000000ull) :
3406 __n / (double)__d;
3407 const size_t __j = static_cast<size_t>(_Fp * (_Y_ - _Min));
3408 _Y_ = _V_[__j];
3409 _V_[__j] = __e_();
3410 return _Y_;
3411 }
3412};
3413
3414template<class _Engine, size_t __k>
3415 _LIBCPP_CONSTEXPR const size_t shuffle_order_engine<_Engine, __k>::table_size;
3416
3417template<class _Eng, size_t _Kp>
3418bool
3419operator==(
3420 const shuffle_order_engine<_Eng, _Kp>& __x,
3421 const shuffle_order_engine<_Eng, _Kp>& __y)
3422{
3423 return __x._Y_ == __y._Y_ && _VSTD::equal(__x._V_, __x._V_ + _Kp, __y._V_) &&
3424 __x.__e_ == __y.__e_;
3425}
3426
3427template<class _Eng, size_t _Kp>
3428inline _LIBCPP_INLINE_VISIBILITY
3429bool
3430operator!=(
3431 const shuffle_order_engine<_Eng, _Kp>& __x,
3432 const shuffle_order_engine<_Eng, _Kp>& __y)
3433{
3434 return !(__x == __y);
3435}
3436
3437template <class _CharT, class _Traits,
3438 class _Eng, size_t _Kp>
3439basic_ostream<_CharT, _Traits>&
3440operator<<(basic_ostream<_CharT, _Traits>& __os,
3441 const shuffle_order_engine<_Eng, _Kp>& __x)
3442{
3443 __save_flags<_CharT, _Traits> __lx(__os);
3444 __os.flags(ios_base::dec | ios_base::left);
3445 _CharT __sp = __os.widen(' ');
3446 __os.fill(__sp);
3447 __os << __x.__e_ << __sp << __x._V_[0];
3448 for (size_t __i = 1; __i < _Kp; ++__i)
3449 __os << __sp << __x._V_[__i];
3450 return __os << __sp << __x._Y_;
3451}
3452
3453template <class _CharT, class _Traits,
3454 class _Eng, size_t _Kp>
3455basic_istream<_CharT, _Traits>&
3456operator>>(basic_istream<_CharT, _Traits>& __is,
3457 shuffle_order_engine<_Eng, _Kp>& __x)
3458{
3459 typedef typename shuffle_order_engine<_Eng, _Kp>::result_type result_type;
3460 __save_flags<_CharT, _Traits> __lx(__is);
3461 __is.flags(ios_base::dec | ios_base::skipws);
3462 _Eng __e;
3463 result_type _Vp[_Kp+1];
3464 __is >> __e;
3465 for (size_t __i = 0; __i < _Kp+1; ++__i)
3466 __is >> _Vp[__i];
3467 if (!__is.fail())
3468 {
3469 __x.__e_ = __e;
3470 for (size_t __i = 0; __i < _Kp; ++__i)
3471 __x._V_[__i] = _Vp[__i];
3472 __x._Y_ = _Vp[_Kp];
3473 }
3474 return __is;
3475}
3476
3477typedef shuffle_order_engine<minstd_rand0, 256> knuth_b;
3478
3479// random_device
3480
3481class _LIBCPP_TYPE_VIS random_device
3482{
3483#ifdef _LIBCPP_USING_DEV_RANDOM
3484 int __f_;
3485#endif // defined(_LIBCPP_USING_DEV_RANDOM)
3486public:
3487 // types
3488 typedef unsigned result_type;
3489
3490 // generator characteristics
3491 static _LIBCPP_CONSTEXPR const result_type _Min = 0;
3492 static _LIBCPP_CONSTEXPR const result_type _Max = 0xFFFFFFFFu;
3493
3494 _LIBCPP_INLINE_VISIBILITY
3495 static _LIBCPP_CONSTEXPR result_type min() { return _Min;}
3496 _LIBCPP_INLINE_VISIBILITY
3497 static _LIBCPP_CONSTEXPR result_type max() { return _Max;}
3498
3499 // constructors
3500 explicit random_device(const string& __token = "/dev/urandom");
3501 ~random_device();
3502
3503 // generating functions
3504 result_type operator()();
3505
3506 // property functions
3507 double entropy() const _NOEXCEPT;
3508
3509private:
3510 // no copy functions
3511 random_device(const random_device&); // = delete;
3512 random_device& operator=(const random_device&); // = delete;
3513};
3514
3515// seed_seq
3516
3517class _LIBCPP_TEMPLATE_VIS seed_seq
3518{
3519public:
3520 // types
3521 typedef uint32_t result_type;
3522
3523private:
3524 vector<result_type> __v_;
3525
3526 template<class _InputIterator>
3527 void init(_InputIterator __first, _InputIterator __last);
3528public:
3529 // constructors
3530 _LIBCPP_INLINE_VISIBILITY
3531 seed_seq() _NOEXCEPT {}
3532#ifndef _LIBCPP_CXX03_LANG
3533 template<class _Tp>
3534 _LIBCPP_INLINE_VISIBILITY
3535 seed_seq(initializer_list<_Tp> __il) {init(__il.begin(), __il.end());}
3536#endif // _LIBCPP_CXX03_LANG
3537
3538 template<class _InputIterator>
3539 _LIBCPP_INLINE_VISIBILITY
3540 seed_seq(_InputIterator __first, _InputIterator __last)
3541 {init(__first, __last);}
3542
3543 // generating functions
3544 template<class _RandomAccessIterator>
3545 void generate(_RandomAccessIterator __first, _RandomAccessIterator __last);
3546
3547 // property functions
3548 _LIBCPP_INLINE_VISIBILITY
3549 size_t size() const _NOEXCEPT {return __v_.size();}
3550 template<class _OutputIterator>
3551 _LIBCPP_INLINE_VISIBILITY
3552 void param(_OutputIterator __dest) const
3553 {_VSTD::copy(__v_.begin(), __v_.end(), __dest);}
3554
3555private:
3556 // no copy functions
3557 seed_seq(const seed_seq&); // = delete;
3558 void operator=(const seed_seq&); // = delete;
3559
3560 _LIBCPP_INLINE_VISIBILITY
3561 static result_type _Tp(result_type __x) {return __x ^ (__x >> 27);}
3562};
3563
3564template<class _InputIterator>
3565void
3566seed_seq::init(_InputIterator __first, _InputIterator __last)
3567{
3568 for (_InputIterator __s = __first; __s != __last; ++__s)
3569 __v_.push_back(*__s & 0xFFFFFFFF);
3570}
3571
3572template<class _RandomAccessIterator>
3573void
3574seed_seq::generate(_RandomAccessIterator __first, _RandomAccessIterator __last)
3575{
3576 if (__first != __last)
3577 {
3578 _VSTD::fill(__first, __last, 0x8b8b8b8b);
3579 const size_t __n = static_cast<size_t>(__last - __first);
3580 const size_t __s = __v_.size();
3581 const size_t __t = (__n >= 623) ? 11
3582 : (__n >= 68) ? 7
3583 : (__n >= 39) ? 5
3584 : (__n >= 7) ? 3
3585 : (__n - 1) / 2;
3586 const size_t __p = (__n - __t) / 2;
3587 const size_t __q = __p + __t;
3588 const size_t __m = _VSTD::max(__s + 1, __n);
3589 // __k = 0;
3590 {
3591 result_type __r = 1664525 * _Tp(__first[0] ^ __first[__p]
3592 ^ __first[__n - 1]);
3593 __first[__p] += __r;
3594 __r += __s;
3595 __first[__q] += __r;
3596 __first[0] = __r;
3597 }
3598 for (size_t __k = 1; __k <= __s; ++__k)
3599 {
3600 const size_t __kmodn = __k % __n;
3601 const size_t __kpmodn = (__k + __p) % __n;
3602 result_type __r = 1664525 * _Tp(__first[__kmodn] ^ __first[__kpmodn]
3603 ^ __first[(__k - 1) % __n]);
3604 __first[__kpmodn] += __r;
3605 __r += __kmodn + __v_[__k-1];
3606 __first[(__k + __q) % __n] += __r;
3607 __first[__kmodn] = __r;
3608 }
3609 for (size_t __k = __s + 1; __k < __m; ++__k)
3610 {
3611 const size_t __kmodn = __k % __n;
3612 const size_t __kpmodn = (__k + __p) % __n;
3613 result_type __r = 1664525 * _Tp(__first[__kmodn] ^ __first[__kpmodn]
3614 ^ __first[(__k - 1) % __n]);
3615 __first[__kpmodn] += __r;
3616 __r += __kmodn;
3617 __first[(__k + __q) % __n] += __r;
3618 __first[__kmodn] = __r;
3619 }
3620 for (size_t __k = __m; __k < __m + __n; ++__k)
3621 {
3622 const size_t __kmodn = __k % __n;
3623 const size_t __kpmodn = (__k + __p) % __n;
3624 result_type __r = 1566083941 * _Tp(__first[__kmodn] +
3625 __first[__kpmodn] +
3626 __first[(__k - 1) % __n]);
3627 __first[__kpmodn] ^= __r;
3628 __r -= __kmodn;
3629 __first[(__k + __q) % __n] ^= __r;
3630 __first[__kmodn] = __r;
3631 }
3632 }
3633}
3634
3635// generate_canonical
3636
3637template<class _RealType, size_t __bits, class _URNG>
3638_RealType
3639generate_canonical(_URNG& __g)
3640{
3641 const size_t _Dt = numeric_limits<_RealType>::digits;
3642 const size_t __b = _Dt < __bits ? _Dt : __bits;
3643#ifdef _LIBCPP_CXX03_LANG
3644 const size_t __logR = __log2<uint64_t, _URNG::_Max - _URNG::_Min + uint64_t(1)>::value;
3645#else
3646 const size_t __logR = __log2<uint64_t, _URNG::max() - _URNG::min() + uint64_t(1)>::value;
3647#endif
3648 const size_t __k = __b / __logR + (__b % __logR != 0) + (__b == 0);
3649 const _RealType _Rp = _URNG::max() - _URNG::min() + _RealType(1);
3650 _RealType __base = _Rp;
3651 _RealType _Sp = __g() - _URNG::min();
3652 for (size_t __i = 1; __i < __k; ++__i, __base *= _Rp)
3653 _Sp += (__g() - _URNG::min()) * __base;
3654 return _Sp / __base;
3655}
3656
3657// uniform_int_distribution
3658
3659// in <algorithm>
3660
3661template <class _CharT, class _Traits, class _IT>
3662basic_ostream<_CharT, _Traits>&
3663operator<<(basic_ostream<_CharT, _Traits>& __os,
3664 const uniform_int_distribution<_IT>& __x)
3665{
3666 __save_flags<_CharT, _Traits> __lx(__os);
3667 __os.flags(ios_base::dec | ios_base::left);
3668 _CharT __sp = __os.widen(' ');
3669 __os.fill(__sp);
3670 return __os << __x.a() << __sp << __x.b();
3671}
3672
3673template <class _CharT, class _Traits, class _IT>
3674basic_istream<_CharT, _Traits>&
3675operator>>(basic_istream<_CharT, _Traits>& __is,
3676 uniform_int_distribution<_IT>& __x)
3677{
3678 typedef uniform_int_distribution<_IT> _Eng;
3679 typedef typename _Eng::result_type result_type;
3680 typedef typename _Eng::param_type param_type;
3681 __save_flags<_CharT, _Traits> __lx(__is);
3682 __is.flags(ios_base::dec | ios_base::skipws);
3683 result_type __a;
3684 result_type __b;
3685 __is >> __a >> __b;
3686 if (!__is.fail())
3687 __x.param(param_type(__a, __b));
3688 return __is;
3689}
3690
3691// uniform_real_distribution
3692
3693template<class _RealType = double>
3694class _LIBCPP_TEMPLATE_VIS uniform_real_distribution
3695{
3696public:
3697 // types
3698 typedef _RealType result_type;
3699
3700 class _LIBCPP_TEMPLATE_VIS param_type
3701 {
3702 result_type __a_;
3703 result_type __b_;
3704 public:
3705 typedef uniform_real_distribution distribution_type;
3706
3707 _LIBCPP_INLINE_VISIBILITY
3708 explicit param_type(result_type __a = 0,
3709 result_type __b = 1)
3710 : __a_(__a), __b_(__b) {}
3711
3712 _LIBCPP_INLINE_VISIBILITY
3713 result_type a() const {return __a_;}
3714 _LIBCPP_INLINE_VISIBILITY
3715 result_type b() const {return __b_;}
3716
3717 friend _LIBCPP_INLINE_VISIBILITY
3718 bool operator==(const param_type& __x, const param_type& __y)
3719 {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
3720 friend _LIBCPP_INLINE_VISIBILITY
3721 bool operator!=(const param_type& __x, const param_type& __y)
3722 {return !(__x == __y);}
3723 };
3724
3725private:
3726 param_type __p_;
3727
3728public:
3729 // constructors and reset functions
3730 _LIBCPP_INLINE_VISIBILITY
3731 explicit uniform_real_distribution(result_type __a = 0, result_type __b = 1)
3732 : __p_(param_type(__a, __b)) {}
3733 _LIBCPP_INLINE_VISIBILITY
3734 explicit uniform_real_distribution(const param_type& __p) : __p_(__p) {}
3735 _LIBCPP_INLINE_VISIBILITY
3736 void reset() {}
3737
3738 // generating functions
3739 template<class _URNG>
3740 _LIBCPP_INLINE_VISIBILITY
3741 result_type operator()(_URNG& __g)
3742 {return (*this)(__g, __p_);}
3743 template<class _URNG> _LIBCPP_INLINE_VISIBILITY result_type operator()(_URNG& __g, const param_type& __p);
3744
3745 // property functions
3746 _LIBCPP_INLINE_VISIBILITY
3747 result_type a() const {return __p_.a();}
3748 _LIBCPP_INLINE_VISIBILITY
3749 result_type b() const {return __p_.b();}
3750
3751 _LIBCPP_INLINE_VISIBILITY
3752 param_type param() const {return __p_;}
3753 _LIBCPP_INLINE_VISIBILITY
3754 void param(const param_type& __p) {__p_ = __p;}
3755
3756 _LIBCPP_INLINE_VISIBILITY
3757 result_type min() const {return a();}
3758 _LIBCPP_INLINE_VISIBILITY
3759 result_type max() const {return b();}
3760
3761 friend _LIBCPP_INLINE_VISIBILITY
3762 bool operator==(const uniform_real_distribution& __x,
3763 const uniform_real_distribution& __y)
3764 {return __x.__p_ == __y.__p_;}
3765 friend _LIBCPP_INLINE_VISIBILITY
3766 bool operator!=(const uniform_real_distribution& __x,
3767 const uniform_real_distribution& __y)
3768 {return !(__x == __y);}
3769};
3770
3771template<class _RealType>
3772template<class _URNG>
3773inline
3774typename uniform_real_distribution<_RealType>::result_type
3775uniform_real_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
3776{
3777 return (__p.b() - __p.a())
3778 * _VSTD::generate_canonical<_RealType, numeric_limits<_RealType>::digits>(__g)
3779 + __p.a();
3780}
3781
3782template <class _CharT, class _Traits, class _RT>
3783basic_ostream<_CharT, _Traits>&
3784operator<<(basic_ostream<_CharT, _Traits>& __os,
3785 const uniform_real_distribution<_RT>& __x)
3786{
3787 __save_flags<_CharT, _Traits> __lx(__os);
3788 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
3789 ios_base::scientific);
3790 _CharT __sp = __os.widen(' ');
3791 __os.fill(__sp);
3792 return __os << __x.a() << __sp << __x.b();
3793}
3794
3795template <class _CharT, class _Traits, class _RT>
3796basic_istream<_CharT, _Traits>&
3797operator>>(basic_istream<_CharT, _Traits>& __is,
3798 uniform_real_distribution<_RT>& __x)
3799{
3800 typedef uniform_real_distribution<_RT> _Eng;
3801 typedef typename _Eng::result_type result_type;
3802 typedef typename _Eng::param_type param_type;
3803 __save_flags<_CharT, _Traits> __lx(__is);
3804 __is.flags(ios_base::dec | ios_base::skipws);
3805 result_type __a;
3806 result_type __b;
3807 __is >> __a >> __b;
3808 if (!__is.fail())
3809 __x.param(param_type(__a, __b));
3810 return __is;
3811}
3812
3813// bernoulli_distribution
3814
3815class _LIBCPP_TEMPLATE_VIS bernoulli_distribution
3816{
3817public:
3818 // types
3819 typedef bool result_type;
3820
3821 class _LIBCPP_TEMPLATE_VIS param_type
3822 {
3823 double __p_;
3824 public:
3825 typedef bernoulli_distribution distribution_type;
3826
3827 _LIBCPP_INLINE_VISIBILITY
3828 explicit param_type(double __p = 0.5) : __p_(__p) {}
3829
3830 _LIBCPP_INLINE_VISIBILITY
3831 double p() const {return __p_;}
3832
3833 friend _LIBCPP_INLINE_VISIBILITY
3834 bool operator==(const param_type& __x, const param_type& __y)
3835 {return __x.__p_ == __y.__p_;}
3836 friend _LIBCPP_INLINE_VISIBILITY
3837 bool operator!=(const param_type& __x, const param_type& __y)
3838 {return !(__x == __y);}
3839 };
3840
3841private:
3842 param_type __p_;
3843
3844public:
3845 // constructors and reset functions
3846 _LIBCPP_INLINE_VISIBILITY
3847 explicit bernoulli_distribution(double __p = 0.5)
3848 : __p_(param_type(__p)) {}
3849 _LIBCPP_INLINE_VISIBILITY
3850 explicit bernoulli_distribution(const param_type& __p) : __p_(__p) {}
3851 _LIBCPP_INLINE_VISIBILITY
3852 void reset() {}
3853
3854 // generating functions
3855 template<class _URNG>
3856 _LIBCPP_INLINE_VISIBILITY
3857 result_type operator()(_URNG& __g)
3858 {return (*this)(__g, __p_);}
3859 template<class _URNG> _LIBCPP_INLINE_VISIBILITY result_type operator()(_URNG& __g, const param_type& __p);
3860
3861 // property functions
3862 _LIBCPP_INLINE_VISIBILITY
3863 double p() const {return __p_.p();}
3864
3865 _LIBCPP_INLINE_VISIBILITY
3866 param_type param() const {return __p_;}
3867 _LIBCPP_INLINE_VISIBILITY
3868 void param(const param_type& __p) {__p_ = __p;}
3869
3870 _LIBCPP_INLINE_VISIBILITY
3871 result_type min() const {return false;}
3872 _LIBCPP_INLINE_VISIBILITY
3873 result_type max() const {return true;}
3874
3875 friend _LIBCPP_INLINE_VISIBILITY
3876 bool operator==(const bernoulli_distribution& __x,
3877 const bernoulli_distribution& __y)
3878 {return __x.__p_ == __y.__p_;}
3879 friend _LIBCPP_INLINE_VISIBILITY
3880 bool operator!=(const bernoulli_distribution& __x,
3881 const bernoulli_distribution& __y)
3882 {return !(__x == __y);}
3883};
3884
3885template<class _URNG>
3886inline
3887bernoulli_distribution::result_type
3888bernoulli_distribution::operator()(_URNG& __g, const param_type& __p)
3889{
3890 uniform_real_distribution<double> __gen;
3891 return __gen(__g) < __p.p();
3892}
3893
3894template <class _CharT, class _Traits>
3895basic_ostream<_CharT, _Traits>&
3896operator<<(basic_ostream<_CharT, _Traits>& __os, const bernoulli_distribution& __x)
3897{
3898 __save_flags<_CharT, _Traits> __lx(__os);
3899 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
3900 ios_base::scientific);
3901 _CharT __sp = __os.widen(' ');
3902 __os.fill(__sp);
3903 return __os << __x.p();
3904}
3905
3906template <class _CharT, class _Traits>
3907basic_istream<_CharT, _Traits>&
3908operator>>(basic_istream<_CharT, _Traits>& __is, bernoulli_distribution& __x)
3909{
3910 typedef bernoulli_distribution _Eng;
3911 typedef typename _Eng::param_type param_type;
3912 __save_flags<_CharT, _Traits> __lx(__is);
3913 __is.flags(ios_base::dec | ios_base::skipws);
3914 double __p;
3915 __is >> __p;
3916 if (!__is.fail())
3917 __x.param(param_type(__p));
3918 return __is;
3919}
3920
3921// binomial_distribution
3922
3923template<class _IntType = int>
3924class _LIBCPP_TEMPLATE_VIS binomial_distribution
3925{
3926public:
3927 // types
3928 typedef _IntType result_type;
3929
3930 class _LIBCPP_TEMPLATE_VIS param_type
3931 {
3932 result_type __t_;
3933 double __p_;
3934 double __pr_;
3935 double __odds_ratio_;
3936 result_type __r0_;
3937 public:
3938 typedef binomial_distribution distribution_type;
3939
3940 explicit param_type(result_type __t = 1, double __p = 0.5);
3941
3942 _LIBCPP_INLINE_VISIBILITY
3943 result_type t() const {return __t_;}
3944 _LIBCPP_INLINE_VISIBILITY
3945 double p() const {return __p_;}
3946
3947 friend _LIBCPP_INLINE_VISIBILITY
3948 bool operator==(const param_type& __x, const param_type& __y)
3949 {return __x.__t_ == __y.__t_ && __x.__p_ == __y.__p_;}
3950 friend _LIBCPP_INLINE_VISIBILITY
3951 bool operator!=(const param_type& __x, const param_type& __y)
3952 {return !(__x == __y);}
3953
3954 friend class binomial_distribution;
3955 };
3956
3957private:
3958 param_type __p_;
3959
3960public:
3961 // constructors and reset functions
3962 _LIBCPP_INLINE_VISIBILITY
3963 explicit binomial_distribution(result_type __t = 1, double __p = 0.5)
3964 : __p_(param_type(__t, __p)) {}
3965 _LIBCPP_INLINE_VISIBILITY
3966 explicit binomial_distribution(const param_type& __p) : __p_(__p) {}
3967 _LIBCPP_INLINE_VISIBILITY
3968 void reset() {}
3969
3970 // generating functions
3971 template<class _URNG>
3972 _LIBCPP_INLINE_VISIBILITY
3973 result_type operator()(_URNG& __g)
3974 {return (*this)(__g, __p_);}
3975 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
3976
3977 // property functions
3978 _LIBCPP_INLINE_VISIBILITY
3979 result_type t() const {return __p_.t();}
3980 _LIBCPP_INLINE_VISIBILITY
3981 double p() const {return __p_.p();}
3982
3983 _LIBCPP_INLINE_VISIBILITY
3984 param_type param() const {return __p_;}
3985 _LIBCPP_INLINE_VISIBILITY
3986 void param(const param_type& __p) {__p_ = __p;}
3987
3988 _LIBCPP_INLINE_VISIBILITY
3989 result_type min() const {return 0;}
3990 _LIBCPP_INLINE_VISIBILITY
3991 result_type max() const {return t();}
3992
3993 friend _LIBCPP_INLINE_VISIBILITY
3994 bool operator==(const binomial_distribution& __x,
3995 const binomial_distribution& __y)
3996 {return __x.__p_ == __y.__p_;}
3997 friend _LIBCPP_INLINE_VISIBILITY
3998 bool operator!=(const binomial_distribution& __x,
3999 const binomial_distribution& __y)
4000 {return !(__x == __y);}
4001};
4002
4003#ifndef _LIBCPP_MSVCRT
4004extern "C" double lgamma_r(double, int *);
4005#endif
4006
4007inline _LIBCPP_INLINE_VISIBILITY double __libcpp_lgamma(double __d) {
4008#if defined(_LIBCPP_MSVCRT)
4009 return lgamma(__d);
4010#else
4011 int __sign;
4012 return lgamma_r(__d, &__sign);
4013#endif
4014}
4015
4016template<class _IntType>
4017binomial_distribution<_IntType>::param_type::param_type(const result_type __t, const double __p)
4018 : __t_(__t), __p_(__p)
4019{
4020 if (0 < __p_ && __p_ < 1)
4021 {
4022 __r0_ = static_cast<result_type>((__t_ + 1) * __p_);
4023 __pr_ = _VSTD::exp(__libcpp_lgamma(__t_ + 1.) -
4024 __libcpp_lgamma(__r0_ + 1.) -
4025 __libcpp_lgamma(__t_ - __r0_ + 1.) + __r0_ * _VSTD::log(__p_) +
4026 (__t_ - __r0_) * _VSTD::log(1 - __p_));
4027 __odds_ratio_ = __p_ / (1 - __p_);
4028 }
4029}
4030
4031// Reference: Kemp, C.D. (1986). `A modal method for generating binomial
4032// variables', Commun. Statist. - Theor. Meth. 15(3), 805-813.
4033template<class _IntType>
4034template<class _URNG>
4035_IntType
4036binomial_distribution<_IntType>::operator()(_URNG& __g, const param_type& __pr)
4037{
4038 if (__pr.__t_ == 0 || __pr.__p_ == 0)
4039 return 0;
4040 if (__pr.__p_ == 1)
4041 return __pr.__t_;
4042 uniform_real_distribution<double> __gen;
4043 double __u = __gen(__g) - __pr.__pr_;
4044 if (__u < 0)
4045 return __pr.__r0_;
4046 double __pu = __pr.__pr_;
4047 double __pd = __pu;
4048 result_type __ru = __pr.__r0_;
4049 result_type __rd = __ru;
4050 while (true)
4051 {
4052 if (__rd >= 1)
4053 {
4054 __pd *= __rd / (__pr.__odds_ratio_ * (__pr.__t_ - __rd + 1));
4055 __u -= __pd;
4056 if (__u < 0)
4057 return __rd - 1;
4058 }
4059 if ( __rd != 0 )
4060 --__rd;
4061 ++__ru;
4062 if (__ru <= __pr.__t_)
4063 {
4064 __pu *= (__pr.__t_ - __ru + 1) * __pr.__odds_ratio_ / __ru;
4065 __u -= __pu;
4066 if (__u < 0)
4067 return __ru;
4068 }
4069 }
4070}
4071
4072template <class _CharT, class _Traits, class _IntType>
4073basic_ostream<_CharT, _Traits>&
4074operator<<(basic_ostream<_CharT, _Traits>& __os,
4075 const binomial_distribution<_IntType>& __x)
4076{
4077 __save_flags<_CharT, _Traits> __lx(__os);
4078 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
4079 ios_base::scientific);
4080 _CharT __sp = __os.widen(' ');
4081 __os.fill(__sp);
4082 return __os << __x.t() << __sp << __x.p();
4083}
4084
4085template <class _CharT, class _Traits, class _IntType>
4086basic_istream<_CharT, _Traits>&
4087operator>>(basic_istream<_CharT, _Traits>& __is,
4088 binomial_distribution<_IntType>& __x)
4089{
4090 typedef binomial_distribution<_IntType> _Eng;
4091 typedef typename _Eng::result_type result_type;
4092 typedef typename _Eng::param_type param_type;
4093 __save_flags<_CharT, _Traits> __lx(__is);
4094 __is.flags(ios_base::dec | ios_base::skipws);
4095 result_type __t;
4096 double __p;
4097 __is >> __t >> __p;
4098 if (!__is.fail())
4099 __x.param(param_type(__t, __p));
4100 return __is;
4101}
4102
4103// exponential_distribution
4104
4105template<class _RealType = double>
4106class _LIBCPP_TEMPLATE_VIS exponential_distribution
4107{
4108public:
4109 // types
4110 typedef _RealType result_type;
4111
4112 class _LIBCPP_TEMPLATE_VIS param_type
4113 {
4114 result_type __lambda_;
4115 public:
4116 typedef exponential_distribution distribution_type;
4117
4118 _LIBCPP_INLINE_VISIBILITY
4119 explicit param_type(result_type __lambda = 1) : __lambda_(__lambda) {}
4120
4121 _LIBCPP_INLINE_VISIBILITY
4122 result_type lambda() const {return __lambda_;}
4123
4124 friend _LIBCPP_INLINE_VISIBILITY
4125 bool operator==(const param_type& __x, const param_type& __y)
4126 {return __x.__lambda_ == __y.__lambda_;}
4127 friend _LIBCPP_INLINE_VISIBILITY
4128 bool operator!=(const param_type& __x, const param_type& __y)
4129 {return !(__x == __y);}
4130 };
4131
4132private:
4133 param_type __p_;
4134
4135public:
4136 // constructors and reset functions
4137 _LIBCPP_INLINE_VISIBILITY
4138 explicit exponential_distribution(result_type __lambda = 1)
4139 : __p_(param_type(__lambda)) {}
4140 _LIBCPP_INLINE_VISIBILITY
4141 explicit exponential_distribution(const param_type& __p) : __p_(__p) {}
4142 _LIBCPP_INLINE_VISIBILITY
4143 void reset() {}
4144
4145 // generating functions
4146 template<class _URNG>
4147 _LIBCPP_INLINE_VISIBILITY
4148 result_type operator()(_URNG& __g)
4149 {return (*this)(__g, __p_);}
4150 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
4151
4152 // property functions
4153 _LIBCPP_INLINE_VISIBILITY
4154 result_type lambda() const {return __p_.lambda();}
4155
4156 _LIBCPP_INLINE_VISIBILITY
4157 param_type param() const {return __p_;}
4158 _LIBCPP_INLINE_VISIBILITY
4159 void param(const param_type& __p) {__p_ = __p;}
4160
4161 _LIBCPP_INLINE_VISIBILITY
4162 result_type min() const {return 0;}
4163 _LIBCPP_INLINE_VISIBILITY
4164 result_type max() const {return numeric_limits<result_type>::infinity();}
4165
4166 friend _LIBCPP_INLINE_VISIBILITY
4167 bool operator==(const exponential_distribution& __x,
4168 const exponential_distribution& __y)
4169 {return __x.__p_ == __y.__p_;}
4170 friend _LIBCPP_INLINE_VISIBILITY
4171 bool operator!=(const exponential_distribution& __x,
4172 const exponential_distribution& __y)
4173 {return !(__x == __y);}
4174};
4175
4176template <class _RealType>
4177template<class _URNG>
4178_RealType
4179exponential_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
4180{
4181 return -_VSTD::log
4182 (
4183 result_type(1) -
4184 _VSTD::generate_canonical<result_type,
4185 numeric_limits<result_type>::digits>(__g)
4186 )
4187 / __p.lambda();
4188}
4189
4190template <class _CharT, class _Traits, class _RealType>
4191basic_ostream<_CharT, _Traits>&
4192operator<<(basic_ostream<_CharT, _Traits>& __os,
4193 const exponential_distribution<_RealType>& __x)
4194{
4195 __save_flags<_CharT, _Traits> __lx(__os);
4196 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
4197 ios_base::scientific);
4198 return __os << __x.lambda();
4199}
4200
4201template <class _CharT, class _Traits, class _RealType>
4202basic_istream<_CharT, _Traits>&
4203operator>>(basic_istream<_CharT, _Traits>& __is,
4204 exponential_distribution<_RealType>& __x)
4205{
4206 typedef exponential_distribution<_RealType> _Eng;
4207 typedef typename _Eng::result_type result_type;
4208 typedef typename _Eng::param_type param_type;
4209 __save_flags<_CharT, _Traits> __lx(__is);
4210 __is.flags(ios_base::dec | ios_base::skipws);
4211 result_type __lambda;
4212 __is >> __lambda;
4213 if (!__is.fail())
4214 __x.param(param_type(__lambda));
4215 return __is;
4216}
4217
4218// normal_distribution
4219
4220template<class _RealType = double>
4221class _LIBCPP_TEMPLATE_VIS normal_distribution
4222{
4223public:
4224 // types
4225 typedef _RealType result_type;
4226
4227 class _LIBCPP_TEMPLATE_VIS param_type
4228 {
4229 result_type __mean_;
4230 result_type __stddev_;
4231 public:
4232 typedef normal_distribution distribution_type;
4233
4234 _LIBCPP_INLINE_VISIBILITY
4235 explicit param_type(result_type __mean = 0, result_type __stddev = 1)
4236 : __mean_(__mean), __stddev_(__stddev) {}
4237
4238 _LIBCPP_INLINE_VISIBILITY
4239 result_type mean() const {return __mean_;}
4240 _LIBCPP_INLINE_VISIBILITY
4241 result_type stddev() const {return __stddev_;}
4242
4243 friend _LIBCPP_INLINE_VISIBILITY
4244 bool operator==(const param_type& __x, const param_type& __y)
4245 {return __x.__mean_ == __y.__mean_ && __x.__stddev_ == __y.__stddev_;}
4246 friend _LIBCPP_INLINE_VISIBILITY
4247 bool operator!=(const param_type& __x, const param_type& __y)
4248 {return !(__x == __y);}
4249 };
4250
4251private:
4252 param_type __p_;
4253 result_type _V_;
4254 bool _V_hot_;
4255
4256public:
4257 // constructors and reset functions
4258 _LIBCPP_INLINE_VISIBILITY
4259 explicit normal_distribution(result_type __mean = 0, result_type __stddev = 1)
4260 : __p_(param_type(__mean, __stddev)), _V_hot_(false) {}
4261 _LIBCPP_INLINE_VISIBILITY
4262 explicit normal_distribution(const param_type& __p)
4263 : __p_(__p), _V_hot_(false) {}
4264 _LIBCPP_INLINE_VISIBILITY
4265 void reset() {_V_hot_ = false;}
4266
4267 // generating functions
4268 template<class _URNG>
4269 _LIBCPP_INLINE_VISIBILITY
4270 result_type operator()(_URNG& __g)
4271 {return (*this)(__g, __p_);}
4272 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
4273
4274 // property functions
4275 _LIBCPP_INLINE_VISIBILITY
4276 result_type mean() const {return __p_.mean();}
4277 _LIBCPP_INLINE_VISIBILITY
4278 result_type stddev() const {return __p_.stddev();}
4279
4280 _LIBCPP_INLINE_VISIBILITY
4281 param_type param() const {return __p_;}
4282 _LIBCPP_INLINE_VISIBILITY
4283 void param(const param_type& __p) {__p_ = __p;}
4284
4285 _LIBCPP_INLINE_VISIBILITY
4286 result_type min() const {return -numeric_limits<result_type>::infinity();}
4287 _LIBCPP_INLINE_VISIBILITY
4288 result_type max() const {return numeric_limits<result_type>::infinity();}
4289
4290 friend _LIBCPP_INLINE_VISIBILITY
4291 bool operator==(const normal_distribution& __x,
4292 const normal_distribution& __y)
4293 {return __x.__p_ == __y.__p_ && __x._V_hot_ == __y._V_hot_ &&
4294 (!__x._V_hot_ || __x._V_ == __y._V_);}
4295 friend _LIBCPP_INLINE_VISIBILITY
4296 bool operator!=(const normal_distribution& __x,
4297 const normal_distribution& __y)
4298 {return !(__x == __y);}
4299
4300 template <class _CharT, class _Traits, class _RT>
4301 friend
4302 basic_ostream<_CharT, _Traits>&
4303 operator<<(basic_ostream<_CharT, _Traits>& __os,
4304 const normal_distribution<_RT>& __x);
4305
4306 template <class _CharT, class _Traits, class _RT>
4307 friend
4308 basic_istream<_CharT, _Traits>&
4309 operator>>(basic_istream<_CharT, _Traits>& __is,
4310 normal_distribution<_RT>& __x);
4311};
4312
4313template <class _RealType>
4314template<class _URNG>
4315_RealType
4316normal_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
4317{
4318 result_type _Up;
4319 if (_V_hot_)
4320 {
4321 _V_hot_ = false;
4322 _Up = _V_;
4323 }
4324 else
4325 {
4326 uniform_real_distribution<result_type> _Uni(-1, 1);
4327 result_type __u;
4328 result_type __v;
4329 result_type __s;
4330 do
4331 {
4332 __u = _Uni(__g);
4333 __v = _Uni(__g);
4334 __s = __u * __u + __v * __v;
4335 } while (__s > 1 || __s == 0);
4336 result_type _Fp = _VSTD::sqrt(-2 * _VSTD::log(__s) / __s);
4337 _V_ = __v * _Fp;
4338 _V_hot_ = true;
4339 _Up = __u * _Fp;
4340 }
4341 return _Up * __p.stddev() + __p.mean();
4342}
4343
4344template <class _CharT, class _Traits, class _RT>
4345basic_ostream<_CharT, _Traits>&
4346operator<<(basic_ostream<_CharT, _Traits>& __os,
4347 const normal_distribution<_RT>& __x)
4348{
4349 __save_flags<_CharT, _Traits> __lx(__os);
4350 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
4351 ios_base::scientific);
4352 _CharT __sp = __os.widen(' ');
4353 __os.fill(__sp);
4354 __os << __x.mean() << __sp << __x.stddev() << __sp << __x._V_hot_;
4355 if (__x._V_hot_)
4356 __os << __sp << __x._V_;
4357 return __os;
4358}
4359
4360template <class _CharT, class _Traits, class _RT>
4361basic_istream<_CharT, _Traits>&
4362operator>>(basic_istream<_CharT, _Traits>& __is,
4363 normal_distribution<_RT>& __x)
4364{
4365 typedef normal_distribution<_RT> _Eng;
4366 typedef typename _Eng::result_type result_type;
4367 typedef typename _Eng::param_type param_type;
4368 __save_flags<_CharT, _Traits> __lx(__is);
4369 __is.flags(ios_base::dec | ios_base::skipws);
4370 result_type __mean;
4371 result_type __stddev;
4372 result_type _Vp = 0;
4373 bool _V_hot = false;
4374 __is >> __mean >> __stddev >> _V_hot;
4375 if (_V_hot)
4376 __is >> _Vp;
4377 if (!__is.fail())
4378 {
4379 __x.param(param_type(__mean, __stddev));
4380 __x._V_hot_ = _V_hot;
4381 __x._V_ = _Vp;
4382 }
4383 return __is;
4384}
4385
4386// lognormal_distribution
4387
4388template<class _RealType = double>
4389class _LIBCPP_TEMPLATE_VIS lognormal_distribution
4390{
4391public:
4392 // types
4393 typedef _RealType result_type;
4394
4395 class _LIBCPP_TEMPLATE_VIS param_type
4396 {
4397 normal_distribution<result_type> __nd_;
4398 public:
4399 typedef lognormal_distribution distribution_type;
4400
4401 _LIBCPP_INLINE_VISIBILITY
4402 explicit param_type(result_type __m = 0, result_type __s = 1)
4403 : __nd_(__m, __s) {}
4404
4405 _LIBCPP_INLINE_VISIBILITY
4406 result_type m() const {return __nd_.mean();}
4407 _LIBCPP_INLINE_VISIBILITY
4408 result_type s() const {return __nd_.stddev();}
4409
4410 friend _LIBCPP_INLINE_VISIBILITY
4411 bool operator==(const param_type& __x, const param_type& __y)
4412 {return __x.__nd_ == __y.__nd_;}
4413 friend _LIBCPP_INLINE_VISIBILITY
4414 bool operator!=(const param_type& __x, const param_type& __y)
4415 {return !(__x == __y);}
4416 friend class lognormal_distribution;
4417
4418 template <class _CharT, class _Traits, class _RT>
4419 friend
4420 basic_ostream<_CharT, _Traits>&
4421 operator<<(basic_ostream<_CharT, _Traits>& __os,
4422 const lognormal_distribution<_RT>& __x);
4423
4424 template <class _CharT, class _Traits, class _RT>
4425 friend
4426 basic_istream<_CharT, _Traits>&
4427 operator>>(basic_istream<_CharT, _Traits>& __is,
4428 lognormal_distribution<_RT>& __x);
4429 };
4430
4431private:
4432 param_type __p_;
4433
4434public:
4435 // constructor and reset functions
4436 _LIBCPP_INLINE_VISIBILITY
4437 explicit lognormal_distribution(result_type __m = 0, result_type __s = 1)
4438 : __p_(param_type(__m, __s)) {}
4439 _LIBCPP_INLINE_VISIBILITY
4440 explicit lognormal_distribution(const param_type& __p)
4441 : __p_(__p) {}
4442 _LIBCPP_INLINE_VISIBILITY
4443 void reset() {__p_.__nd_.reset();}
4444
4445 // generating functions
4446 template<class _URNG>
4447 _LIBCPP_INLINE_VISIBILITY
4448 result_type operator()(_URNG& __g)
4449 {return (*this)(__g, __p_);}
4450 template<class _URNG>
4451 _LIBCPP_INLINE_VISIBILITY
4452 result_type operator()(_URNG& __g, const param_type& __p)
4453 {return _VSTD::exp(const_cast<normal_distribution<result_type>&>(__p.__nd_)(__g));}
4454
4455 // property functions
4456 _LIBCPP_INLINE_VISIBILITY
4457 result_type m() const {return __p_.m();}
4458 _LIBCPP_INLINE_VISIBILITY
4459 result_type s() const {return __p_.s();}
4460
4461 _LIBCPP_INLINE_VISIBILITY
4462 param_type param() const {return __p_;}
4463 _LIBCPP_INLINE_VISIBILITY
4464 void param(const param_type& __p) {__p_ = __p;}
4465
4466 _LIBCPP_INLINE_VISIBILITY
4467 result_type min() const {return 0;}
4468 _LIBCPP_INLINE_VISIBILITY
4469 result_type max() const {return numeric_limits<result_type>::infinity();}
4470
4471 friend _LIBCPP_INLINE_VISIBILITY
4472 bool operator==(const lognormal_distribution& __x,
4473 const lognormal_distribution& __y)
4474 {return __x.__p_ == __y.__p_;}
4475 friend _LIBCPP_INLINE_VISIBILITY
4476 bool operator!=(const lognormal_distribution& __x,
4477 const lognormal_distribution& __y)
4478 {return !(__x == __y);}
4479
4480 template <class _CharT, class _Traits, class _RT>
4481 friend
4482 basic_ostream<_CharT, _Traits>&
4483 operator<<(basic_ostream<_CharT, _Traits>& __os,
4484 const lognormal_distribution<_RT>& __x);
4485
4486 template <class _CharT, class _Traits, class _RT>
4487 friend
4488 basic_istream<_CharT, _Traits>&
4489 operator>>(basic_istream<_CharT, _Traits>& __is,
4490 lognormal_distribution<_RT>& __x);
4491};
4492
4493template <class _CharT, class _Traits, class _RT>
4494inline _LIBCPP_INLINE_VISIBILITY
4495basic_ostream<_CharT, _Traits>&
4496operator<<(basic_ostream<_CharT, _Traits>& __os,
4497 const lognormal_distribution<_RT>& __x)
4498{
4499 return __os << __x.__p_.__nd_;
4500}
4501
4502template <class _CharT, class _Traits, class _RT>
4503inline _LIBCPP_INLINE_VISIBILITY
4504basic_istream<_CharT, _Traits>&
4505operator>>(basic_istream<_CharT, _Traits>& __is,
4506 lognormal_distribution<_RT>& __x)
4507{
4508 return __is >> __x.__p_.__nd_;
4509}
4510
4511// poisson_distribution
4512
4513template<class _IntType = int>
4514class _LIBCPP_TEMPLATE_VIS poisson_distribution
4515{
4516public:
4517 // types
4518 typedef _IntType result_type;
4519
4520 class _LIBCPP_TEMPLATE_VIS param_type
4521 {
4522 double __mean_;
4523 double __s_;
4524 double __d_;
4525 double __l_;
4526 double __omega_;
4527 double __c0_;
4528 double __c1_;
4529 double __c2_;
4530 double __c3_;
4531 double __c_;
4532
4533 public:
4534 typedef poisson_distribution distribution_type;
4535
4536 explicit param_type(double __mean = 1.0);
4537
4538 _LIBCPP_INLINE_VISIBILITY
4539 double mean() const {return __mean_;}
4540
4541 friend _LIBCPP_INLINE_VISIBILITY
4542 bool operator==(const param_type& __x, const param_type& __y)
4543 {return __x.__mean_ == __y.__mean_;}
4544 friend _LIBCPP_INLINE_VISIBILITY
4545 bool operator!=(const param_type& __x, const param_type& __y)
4546 {return !(__x == __y);}
4547
4548 friend class poisson_distribution;
4549 };
4550
4551private:
4552 param_type __p_;
4553
4554public:
4555 // constructors and reset functions
4556 _LIBCPP_INLINE_VISIBILITY
4557 explicit poisson_distribution(double __mean = 1.0) : __p_(__mean) {}
4558 _LIBCPP_INLINE_VISIBILITY
4559 explicit poisson_distribution(const param_type& __p) : __p_(__p) {}
4560 _LIBCPP_INLINE_VISIBILITY
4561 void reset() {}
4562
4563 // generating functions
4564 template<class _URNG>
4565 _LIBCPP_INLINE_VISIBILITY
4566 result_type operator()(_URNG& __g)
4567 {return (*this)(__g, __p_);}
4568 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
4569
4570 // property functions
4571 _LIBCPP_INLINE_VISIBILITY
4572 double mean() const {return __p_.mean();}
4573
4574 _LIBCPP_INLINE_VISIBILITY
4575 param_type param() const {return __p_;}
4576 _LIBCPP_INLINE_VISIBILITY
4577 void param(const param_type& __p) {__p_ = __p;}
4578
4579 _LIBCPP_INLINE_VISIBILITY
4580 result_type min() const {return 0;}
4581 _LIBCPP_INLINE_VISIBILITY
4582 result_type max() const {return numeric_limits<result_type>::max();}
4583
4584 friend _LIBCPP_INLINE_VISIBILITY
4585 bool operator==(const poisson_distribution& __x,
4586 const poisson_distribution& __y)
4587 {return __x.__p_ == __y.__p_;}
4588 friend _LIBCPP_INLINE_VISIBILITY
4589 bool operator!=(const poisson_distribution& __x,
4590 const poisson_distribution& __y)
4591 {return !(__x == __y);}
4592};
4593
4594template<class _IntType>
4595poisson_distribution<_IntType>::param_type::param_type(double __mean)
4596 : __mean_(__mean)
4597{
4598 if (__mean_ < 10)
4599 {
4600 __s_ = 0;
4601 __d_ = 0;
4602 __l_ = _VSTD::exp(-__mean_);
4603 __omega_ = 0;
4604 __c3_ = 0;
4605 __c2_ = 0;
4606 __c1_ = 0;
4607 __c0_ = 0;
4608 __c_ = 0;
4609 }
4610 else
4611 {
4612 __s_ = _VSTD::sqrt(__mean_);
4613 __d_ = 6 * __mean_ * __mean_;
4614 __l_ = static_cast<result_type>(__mean_ - 1.1484);
4615 __omega_ = .3989423 / __s_;
4616 double __b1_ = .4166667E-1 / __mean_;
4617 double __b2_ = .3 * __b1_ * __b1_;
4618 __c3_ = .1428571 * __b1_ * __b2_;
4619 __c2_ = __b2_ - 15. * __c3_;
4620 __c1_ = __b1_ - 6. * __b2_ + 45. * __c3_;
4621 __c0_ = 1. - __b1_ + 3. * __b2_ - 15. * __c3_;
4622 __c_ = .1069 / __mean_;
4623 }
4624}
4625
4626template <class _IntType>
4627template<class _URNG>
4628_IntType
4629poisson_distribution<_IntType>::operator()(_URNG& __urng, const param_type& __pr)
4630{
4631 result_type __x;
4632 uniform_real_distribution<double> __urd;
4633 if (__pr.__mean_ < 10)
4634 {
4635 __x = 0;
4636 for (double __p = __urd(__urng); __p > __pr.__l_; ++__x)
4637 __p *= __urd(__urng);
4638 }
4639 else
4640 {
4641 double __difmuk;
4642 double __g = __pr.__mean_ + __pr.__s_ * normal_distribution<double>()(__urng);
4643 double __u;
4644 if (__g > 0)
4645 {
4646 __x = static_cast<result_type>(__g);
4647 if (__x >= __pr.__l_)
4648 return __x;
4649 __difmuk = __pr.__mean_ - __x;
4650 __u = __urd(__urng);
4651 if (__pr.__d_ * __u >= __difmuk * __difmuk * __difmuk)
4652 return __x;
4653 }
4654 exponential_distribution<double> __edist;
4655 for (bool __using_exp_dist = false; true; __using_exp_dist = true)
4656 {
4657 double __e;
4658 if (__using_exp_dist || __g < 0)
4659 {
4660 double __t;
4661 do
4662 {
4663 __e = __edist(__urng);
4664 __u = __urd(__urng);
4665 __u += __u - 1;
4666 __t = 1.8 + (__u < 0 ? -__e : __e);
4667 } while (__t <= -.6744);
4668 __x = __pr.__mean_ + __pr.__s_ * __t;
4669 __difmuk = __pr.__mean_ - __x;
4670 __using_exp_dist = true;
4671 }
4672 double __px;
4673 double __py;
4674 if (__x < 10)
4675 {
4676 const result_type __fac[] = {1, 1, 2, 6, 24, 120, 720, 5040,
4677 40320, 362880};
4678 __px = -__pr.__mean_;
4679 __py = _VSTD::pow(__pr.__mean_, (double)__x) / __fac[__x];
4680 }
4681 else
4682 {
4683 double __del = .8333333E-1 / __x;
4684 __del -= 4.8 * __del * __del * __del;
4685 double __v = __difmuk / __x;
4686 if (_VSTD::abs(__v) > 0.25)
4687 __px = __x * _VSTD::log(1 + __v) - __difmuk - __del;
4688 else
4689 __px = __x * __v * __v * (((((((.1250060 * __v + -.1384794) *
4690 __v + .1421878) * __v + -.1661269) * __v + .2000118) *
4691 __v + -.2500068) * __v + .3333333) * __v + -.5) - __del;
4692 __py = .3989423 / _VSTD::sqrt(__x);
4693 }
4694 double __r = (0.5 - __difmuk) / __pr.__s_;
4695 double __r2 = __r * __r;
4696 double __fx = -0.5 * __r2;
4697 double __fy = __pr.__omega_ * (((__pr.__c3_ * __r2 + __pr.__c2_) *
4698 __r2 + __pr.__c1_) * __r2 + __pr.__c0_);
4699 if (__using_exp_dist)
4700 {
4701 if (__pr.__c_ * _VSTD::abs(__u) <= __py * _VSTD::exp(__px + __e) -
4702 __fy * _VSTD::exp(__fx + __e))
4703 break;
4704 }
4705 else
4706 {
4707 if (__fy - __u * __fy <= __py * _VSTD::exp(__px - __fx))
4708 break;
4709 }
4710 }
4711 }
4712 return __x;
4713}
4714
4715template <class _CharT, class _Traits, class _IntType>
4716basic_ostream<_CharT, _Traits>&
4717operator<<(basic_ostream<_CharT, _Traits>& __os,
4718 const poisson_distribution<_IntType>& __x)
4719{
4720 __save_flags<_CharT, _Traits> __lx(__os);
4721 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
4722 ios_base::scientific);
4723 return __os << __x.mean();
4724}
4725
4726template <class _CharT, class _Traits, class _IntType>
4727basic_istream<_CharT, _Traits>&
4728operator>>(basic_istream<_CharT, _Traits>& __is,
4729 poisson_distribution<_IntType>& __x)
4730{
4731 typedef poisson_distribution<_IntType> _Eng;
4732 typedef typename _Eng::param_type param_type;
4733 __save_flags<_CharT, _Traits> __lx(__is);
4734 __is.flags(ios_base::dec | ios_base::skipws);
4735 double __mean;
4736 __is >> __mean;
4737 if (!__is.fail())
4738 __x.param(param_type(__mean));
4739 return __is;
4740}
4741
4742// weibull_distribution
4743
4744template<class _RealType = double>
4745class _LIBCPP_TEMPLATE_VIS weibull_distribution
4746{
4747public:
4748 // types
4749 typedef _RealType result_type;
4750
4751 class _LIBCPP_TEMPLATE_VIS param_type
4752 {
4753 result_type __a_;
4754 result_type __b_;
4755 public:
4756 typedef weibull_distribution distribution_type;
4757
4758 _LIBCPP_INLINE_VISIBILITY
4759 explicit param_type(result_type __a = 1, result_type __b = 1)
4760 : __a_(__a), __b_(__b) {}
4761
4762 _LIBCPP_INLINE_VISIBILITY
4763 result_type a() const {return __a_;}
4764 _LIBCPP_INLINE_VISIBILITY
4765 result_type b() const {return __b_;}
4766
4767 friend _LIBCPP_INLINE_VISIBILITY
4768 bool operator==(const param_type& __x, const param_type& __y)
4769 {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
4770 friend _LIBCPP_INLINE_VISIBILITY
4771 bool operator!=(const param_type& __x, const param_type& __y)
4772 {return !(__x == __y);}
4773 };
4774
4775private:
4776 param_type __p_;
4777
4778public:
4779 // constructor and reset functions
4780 _LIBCPP_INLINE_VISIBILITY
4781 explicit weibull_distribution(result_type __a = 1, result_type __b = 1)
4782 : __p_(param_type(__a, __b)) {}
4783 _LIBCPP_INLINE_VISIBILITY
4784 explicit weibull_distribution(const param_type& __p)
4785 : __p_(__p) {}
4786 _LIBCPP_INLINE_VISIBILITY
4787 void reset() {}
4788
4789 // generating functions
4790 template<class _URNG>
4791 _LIBCPP_INLINE_VISIBILITY
4792 result_type operator()(_URNG& __g)
4793 {return (*this)(__g, __p_);}
4794 template<class _URNG>
4795 _LIBCPP_INLINE_VISIBILITY
4796 result_type operator()(_URNG& __g, const param_type& __p)
4797 {return __p.b() *
4798 _VSTD::pow(exponential_distribution<result_type>()(__g), 1/__p.a());}
4799
4800 // property functions
4801 _LIBCPP_INLINE_VISIBILITY
4802 result_type a() const {return __p_.a();}
4803 _LIBCPP_INLINE_VISIBILITY
4804 result_type b() const {return __p_.b();}
4805
4806 _LIBCPP_INLINE_VISIBILITY
4807 param_type param() const {return __p_;}
4808 _LIBCPP_INLINE_VISIBILITY
4809 void param(const param_type& __p) {__p_ = __p;}
4810
4811 _LIBCPP_INLINE_VISIBILITY
4812 result_type min() const {return 0;}
4813 _LIBCPP_INLINE_VISIBILITY
4814 result_type max() const {return numeric_limits<result_type>::infinity();}
4815
4816 friend _LIBCPP_INLINE_VISIBILITY
4817 bool operator==(const weibull_distribution& __x,
4818 const weibull_distribution& __y)
4819 {return __x.__p_ == __y.__p_;}
4820 friend _LIBCPP_INLINE_VISIBILITY
4821 bool operator!=(const weibull_distribution& __x,
4822 const weibull_distribution& __y)
4823 {return !(__x == __y);}
4824};
4825
4826template <class _CharT, class _Traits, class _RT>
4827basic_ostream<_CharT, _Traits>&
4828operator<<(basic_ostream<_CharT, _Traits>& __os,
4829 const weibull_distribution<_RT>& __x)
4830{
4831 __save_flags<_CharT, _Traits> __lx(__os);
4832 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
4833 ios_base::scientific);
4834 _CharT __sp = __os.widen(' ');
4835 __os.fill(__sp);
4836 __os << __x.a() << __sp << __x.b();
4837 return __os;
4838}
4839
4840template <class _CharT, class _Traits, class _RT>
4841basic_istream<_CharT, _Traits>&
4842operator>>(basic_istream<_CharT, _Traits>& __is,
4843 weibull_distribution<_RT>& __x)
4844{
4845 typedef weibull_distribution<_RT> _Eng;
4846 typedef typename _Eng::result_type result_type;
4847 typedef typename _Eng::param_type param_type;
4848 __save_flags<_CharT, _Traits> __lx(__is);
4849 __is.flags(ios_base::dec | ios_base::skipws);
4850 result_type __a;
4851 result_type __b;
4852 __is >> __a >> __b;
4853 if (!__is.fail())
4854 __x.param(param_type(__a, __b));
4855 return __is;
4856}
4857
4858template<class _RealType = double>
4859class _LIBCPP_TEMPLATE_VIS extreme_value_distribution
4860{
4861public:
4862 // types
4863 typedef _RealType result_type;
4864
4865 class _LIBCPP_TEMPLATE_VIS param_type
4866 {
4867 result_type __a_;
4868 result_type __b_;
4869 public:
4870 typedef extreme_value_distribution distribution_type;
4871
4872 _LIBCPP_INLINE_VISIBILITY
4873 explicit param_type(result_type __a = 0, result_type __b = 1)
4874 : __a_(__a), __b_(__b) {}
4875
4876 _LIBCPP_INLINE_VISIBILITY
4877 result_type a() const {return __a_;}
4878 _LIBCPP_INLINE_VISIBILITY
4879 result_type b() const {return __b_;}
4880
4881 friend _LIBCPP_INLINE_VISIBILITY
4882 bool operator==(const param_type& __x, const param_type& __y)
4883 {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
4884 friend _LIBCPP_INLINE_VISIBILITY
4885 bool operator!=(const param_type& __x, const param_type& __y)
4886 {return !(__x == __y);}
4887 };
4888
4889private:
4890 param_type __p_;
4891
4892public:
4893 // constructor and reset functions
4894 _LIBCPP_INLINE_VISIBILITY
4895 explicit extreme_value_distribution(result_type __a = 0, result_type __b = 1)
4896 : __p_(param_type(__a, __b)) {}
4897 _LIBCPP_INLINE_VISIBILITY
4898 explicit extreme_value_distribution(const param_type& __p)
4899 : __p_(__p) {}
4900 _LIBCPP_INLINE_VISIBILITY
4901 void reset() {}
4902
4903 // generating functions
4904 template<class _URNG>
4905 _LIBCPP_INLINE_VISIBILITY
4906 result_type operator()(_URNG& __g)
4907 {return (*this)(__g, __p_);}
4908 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
4909
4910 // property functions
4911 _LIBCPP_INLINE_VISIBILITY
4912 result_type a() const {return __p_.a();}
4913 _LIBCPP_INLINE_VISIBILITY
4914 result_type b() const {return __p_.b();}
4915
4916 _LIBCPP_INLINE_VISIBILITY
4917 param_type param() const {return __p_;}
4918 _LIBCPP_INLINE_VISIBILITY
4919 void param(const param_type& __p) {__p_ = __p;}
4920
4921 _LIBCPP_INLINE_VISIBILITY
4922 result_type min() const {return -numeric_limits<result_type>::infinity();}
4923 _LIBCPP_INLINE_VISIBILITY
4924 result_type max() const {return numeric_limits<result_type>::infinity();}
4925
4926 friend _LIBCPP_INLINE_VISIBILITY
4927 bool operator==(const extreme_value_distribution& __x,
4928 const extreme_value_distribution& __y)
4929 {return __x.__p_ == __y.__p_;}
4930 friend _LIBCPP_INLINE_VISIBILITY
4931 bool operator!=(const extreme_value_distribution& __x,
4932 const extreme_value_distribution& __y)
4933 {return !(__x == __y);}
4934};
4935
4936template<class _RealType>
4937template<class _URNG>
4938_RealType
4939extreme_value_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
4940{
4941 return __p.a() - __p.b() *
4942 _VSTD::log(-_VSTD::log(1-uniform_real_distribution<result_type>()(__g)));
4943}
4944
4945template <class _CharT, class _Traits, class _RT>
4946basic_ostream<_CharT, _Traits>&
4947operator<<(basic_ostream<_CharT, _Traits>& __os,
4948 const extreme_value_distribution<_RT>& __x)
4949{
4950 __save_flags<_CharT, _Traits> __lx(__os);
4951 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
4952 ios_base::scientific);
4953 _CharT __sp = __os.widen(' ');
4954 __os.fill(__sp);
4955 __os << __x.a() << __sp << __x.b();
4956 return __os;
4957}
4958
4959template <class _CharT, class _Traits, class _RT>
4960basic_istream<_CharT, _Traits>&
4961operator>>(basic_istream<_CharT, _Traits>& __is,
4962 extreme_value_distribution<_RT>& __x)
4963{
4964 typedef extreme_value_distribution<_RT> _Eng;
4965 typedef typename _Eng::result_type result_type;
4966 typedef typename _Eng::param_type param_type;
4967 __save_flags<_CharT, _Traits> __lx(__is);
4968 __is.flags(ios_base::dec | ios_base::skipws);
4969 result_type __a;
4970 result_type __b;
4971 __is >> __a >> __b;
4972 if (!__is.fail())
4973 __x.param(param_type(__a, __b));
4974 return __is;
4975}
4976
4977// gamma_distribution
4978
4979template<class _RealType = double>
4980class _LIBCPP_TEMPLATE_VIS gamma_distribution
4981{
4982public:
4983 // types
4984 typedef _RealType result_type;
4985
4986 class _LIBCPP_TEMPLATE_VIS param_type
4987 {
4988 result_type __alpha_;
4989 result_type __beta_;
4990 public:
4991 typedef gamma_distribution distribution_type;
4992
4993 _LIBCPP_INLINE_VISIBILITY
4994 explicit param_type(result_type __alpha = 1, result_type __beta = 1)
4995 : __alpha_(__alpha), __beta_(__beta) {}
4996
4997 _LIBCPP_INLINE_VISIBILITY
4998 result_type alpha() const {return __alpha_;}
4999 _LIBCPP_INLINE_VISIBILITY
5000 result_type beta() const {return __beta_;}
5001
5002 friend _LIBCPP_INLINE_VISIBILITY
5003 bool operator==(const param_type& __x, const param_type& __y)
5004 {return __x.__alpha_ == __y.__alpha_ && __x.__beta_ == __y.__beta_;}
5005 friend _LIBCPP_INLINE_VISIBILITY
5006 bool operator!=(const param_type& __x, const param_type& __y)
5007 {return !(__x == __y);}
5008 };
5009
5010private:
5011 param_type __p_;
5012
5013public:
5014 // constructors and reset functions
5015 _LIBCPP_INLINE_VISIBILITY
5016 explicit gamma_distribution(result_type __alpha = 1, result_type __beta = 1)
5017 : __p_(param_type(__alpha, __beta)) {}
5018 _LIBCPP_INLINE_VISIBILITY
5019 explicit gamma_distribution(const param_type& __p)
5020 : __p_(__p) {}
5021 _LIBCPP_INLINE_VISIBILITY
5022 void reset() {}
5023
5024 // generating functions
5025 template<class _URNG>
5026 _LIBCPP_INLINE_VISIBILITY
5027 result_type operator()(_URNG& __g)
5028 {return (*this)(__g, __p_);}
5029 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
5030
5031 // property functions
5032 _LIBCPP_INLINE_VISIBILITY
5033 result_type alpha() const {return __p_.alpha();}
5034 _LIBCPP_INLINE_VISIBILITY
5035 result_type beta() const {return __p_.beta();}
5036
5037 _LIBCPP_INLINE_VISIBILITY
5038 param_type param() const {return __p_;}
5039 _LIBCPP_INLINE_VISIBILITY
5040 void param(const param_type& __p) {__p_ = __p;}
5041
5042 _LIBCPP_INLINE_VISIBILITY
5043 result_type min() const {return 0;}
5044 _LIBCPP_INLINE_VISIBILITY
5045 result_type max() const {return numeric_limits<result_type>::infinity();}
5046
5047 friend _LIBCPP_INLINE_VISIBILITY
5048 bool operator==(const gamma_distribution& __x,
5049 const gamma_distribution& __y)
5050 {return __x.__p_ == __y.__p_;}
5051 friend _LIBCPP_INLINE_VISIBILITY
5052 bool operator!=(const gamma_distribution& __x,
5053 const gamma_distribution& __y)
5054 {return !(__x == __y);}
5055};
5056
5057template <class _RealType>
5058template<class _URNG>
5059_RealType
5060gamma_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
5061{
5062 result_type __a = __p.alpha();
5063 uniform_real_distribution<result_type> __gen(0, 1);
5064 exponential_distribution<result_type> __egen;
5065 result_type __x;
5066 if (__a == 1)
5067 __x = __egen(__g);
5068 else if (__a > 1)
5069 {
5070 const result_type __b = __a - 1;
5071 const result_type __c = 3 * __a - result_type(0.75);
5072 while (true)
5073 {
5074 const result_type __u = __gen(__g);
5075 const result_type __v = __gen(__g);
5076 const result_type __w = __u * (1 - __u);
5077 if (__w != 0)
5078 {
5079 const result_type __y = _VSTD::sqrt(__c / __w) *
5080 (__u - result_type(0.5));
5081 __x = __b + __y;
5082 if (__x >= 0)
5083 {
5084 const result_type __z = 64 * __w * __w * __w * __v * __v;
5085 if (__z <= 1 - 2 * __y * __y / __x)
5086 break;
5087 if (_VSTD::log(__z) <= 2 * (__b * _VSTD::log(__x / __b) - __y))
5088 break;
5089 }
5090 }
5091 }
5092 }
5093 else // __a < 1
5094 {
5095 while (true)
5096 {
5097 const result_type __u = __gen(__g);
5098 const result_type __es = __egen(__g);
5099 if (__u <= 1 - __a)
5100 {
5101 __x = _VSTD::pow(__u, 1 / __a);
5102 if (__x <= __es)
5103 break;
5104 }
5105 else
5106 {
5107 const result_type __e = -_VSTD::log((1-__u)/__a);
5108 __x = _VSTD::pow(1 - __a + __a * __e, 1 / __a);
5109 if (__x <= __e + __es)
5110 break;
5111 }
5112 }
5113 }
5114 return __x * __p.beta();
5115}
5116
5117template <class _CharT, class _Traits, class _RT>
5118basic_ostream<_CharT, _Traits>&
5119operator<<(basic_ostream<_CharT, _Traits>& __os,
5120 const gamma_distribution<_RT>& __x)
5121{
5122 __save_flags<_CharT, _Traits> __lx(__os);
5123 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
5124 ios_base::scientific);
5125 _CharT __sp = __os.widen(' ');
5126 __os.fill(__sp);
5127 __os << __x.alpha() << __sp << __x.beta();
5128 return __os;
5129}
5130
5131template <class _CharT, class _Traits, class _RT>
5132basic_istream<_CharT, _Traits>&
5133operator>>(basic_istream<_CharT, _Traits>& __is,
5134 gamma_distribution<_RT>& __x)
5135{
5136 typedef gamma_distribution<_RT> _Eng;
5137 typedef typename _Eng::result_type result_type;
5138 typedef typename _Eng::param_type param_type;
5139 __save_flags<_CharT, _Traits> __lx(__is);
5140 __is.flags(ios_base::dec | ios_base::skipws);
5141 result_type __alpha;
5142 result_type __beta;
5143 __is >> __alpha >> __beta;
5144 if (!__is.fail())
5145 __x.param(param_type(__alpha, __beta));
5146 return __is;
5147}
5148
5149// negative_binomial_distribution
5150
5151template<class _IntType = int>
5152class _LIBCPP_TEMPLATE_VIS negative_binomial_distribution
5153{
5154public:
5155 // types
5156 typedef _IntType result_type;
5157
5158 class _LIBCPP_TEMPLATE_VIS param_type
5159 {
5160 result_type __k_;
5161 double __p_;
5162 public:
5163 typedef negative_binomial_distribution distribution_type;
5164
5165 _LIBCPP_INLINE_VISIBILITY
5166 explicit param_type(result_type __k = 1, double __p = 0.5)
5167 : __k_(__k), __p_(__p) {}
5168
5169 _LIBCPP_INLINE_VISIBILITY
5170 result_type k() const {return __k_;}
5171 _LIBCPP_INLINE_VISIBILITY
5172 double p() const {return __p_;}
5173
5174 friend _LIBCPP_INLINE_VISIBILITY
5175 bool operator==(const param_type& __x, const param_type& __y)
5176 {return __x.__k_ == __y.__k_ && __x.__p_ == __y.__p_;}
5177 friend _LIBCPP_INLINE_VISIBILITY
5178 bool operator!=(const param_type& __x, const param_type& __y)
5179 {return !(__x == __y);}
5180 };
5181
5182private:
5183 param_type __p_;
5184
5185public:
5186 // constructor and reset functions
5187 _LIBCPP_INLINE_VISIBILITY
5188 explicit negative_binomial_distribution(result_type __k = 1, double __p = 0.5)
5189 : __p_(__k, __p) {}
5190 _LIBCPP_INLINE_VISIBILITY
5191 explicit negative_binomial_distribution(const param_type& __p) : __p_(__p) {}
5192 _LIBCPP_INLINE_VISIBILITY
5193 void reset() {}
5194
5195 // generating functions
5196 template<class _URNG>
5197 _LIBCPP_INLINE_VISIBILITY
5198 result_type operator()(_URNG& __g)
5199 {return (*this)(__g, __p_);}
5200 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
5201
5202 // property functions
5203 _LIBCPP_INLINE_VISIBILITY
5204 result_type k() const {return __p_.k();}
5205 _LIBCPP_INLINE_VISIBILITY
5206 double p() const {return __p_.p();}
5207
5208 _LIBCPP_INLINE_VISIBILITY
5209 param_type param() const {return __p_;}
5210 _LIBCPP_INLINE_VISIBILITY
5211 void param(const param_type& __p) {__p_ = __p;}
5212
5213 _LIBCPP_INLINE_VISIBILITY
5214 result_type min() const {return 0;}
5215 _LIBCPP_INLINE_VISIBILITY
5216 result_type max() const {return numeric_limits<result_type>::max();}
5217
5218 friend _LIBCPP_INLINE_VISIBILITY
5219 bool operator==(const negative_binomial_distribution& __x,
5220 const negative_binomial_distribution& __y)
5221 {return __x.__p_ == __y.__p_;}
5222 friend _LIBCPP_INLINE_VISIBILITY
5223 bool operator!=(const negative_binomial_distribution& __x,
5224 const negative_binomial_distribution& __y)
5225 {return !(__x == __y);}
5226};
5227
5228template <class _IntType>
5229template<class _URNG>
5230_IntType
5231negative_binomial_distribution<_IntType>::operator()(_URNG& __urng, const param_type& __pr)
5232{
5233 result_type __k = __pr.k();
5234 double __p = __pr.p();
5235 if (__k <= 21 * __p)
5236 {
5237 bernoulli_distribution __gen(__p);
5238 result_type __f = 0;
5239 result_type __s = 0;
5240 while (__s < __k)
5241 {
5242 if (__gen(__urng))
5243 ++__s;
5244 else
5245 ++__f;
5246 }
5247 return __f;
5248 }
5249 return poisson_distribution<result_type>(gamma_distribution<double>
5250 (__k, (1-__p)/__p)(__urng))(__urng);
5251}
5252
5253template <class _CharT, class _Traits, class _IntType>
5254basic_ostream<_CharT, _Traits>&
5255operator<<(basic_ostream<_CharT, _Traits>& __os,
5256 const negative_binomial_distribution<_IntType>& __x)
5257{
5258 __save_flags<_CharT, _Traits> __lx(__os);
5259 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
5260 ios_base::scientific);
5261 _CharT __sp = __os.widen(' ');
5262 __os.fill(__sp);
5263 return __os << __x.k() << __sp << __x.p();
5264}
5265
5266template <class _CharT, class _Traits, class _IntType>
5267basic_istream<_CharT, _Traits>&
5268operator>>(basic_istream<_CharT, _Traits>& __is,
5269 negative_binomial_distribution<_IntType>& __x)
5270{
5271 typedef negative_binomial_distribution<_IntType> _Eng;
5272 typedef typename _Eng::result_type result_type;
5273 typedef typename _Eng::param_type param_type;
5274 __save_flags<_CharT, _Traits> __lx(__is);
5275 __is.flags(ios_base::dec | ios_base::skipws);
5276 result_type __k;
5277 double __p;
5278 __is >> __k >> __p;
5279 if (!__is.fail())
5280 __x.param(param_type(__k, __p));
5281 return __is;
5282}
5283
5284// geometric_distribution
5285
5286template<class _IntType = int>
5287class _LIBCPP_TEMPLATE_VIS geometric_distribution
5288{
5289public:
5290 // types
5291 typedef _IntType result_type;
5292
5293 class _LIBCPP_TEMPLATE_VIS param_type
5294 {
5295 double __p_;
5296 public:
5297 typedef geometric_distribution distribution_type;
5298
5299 _LIBCPP_INLINE_VISIBILITY
5300 explicit param_type(double __p = 0.5) : __p_(__p) {}
5301
5302 _LIBCPP_INLINE_VISIBILITY
5303 double p() const {return __p_;}
5304
5305 friend _LIBCPP_INLINE_VISIBILITY
5306 bool operator==(const param_type& __x, const param_type& __y)
5307 {return __x.__p_ == __y.__p_;}
5308 friend _LIBCPP_INLINE_VISIBILITY
5309 bool operator!=(const param_type& __x, const param_type& __y)
5310 {return !(__x == __y);}
5311 };
5312
5313private:
5314 param_type __p_;
5315
5316public:
5317 // constructors and reset functions
5318 _LIBCPP_INLINE_VISIBILITY
5319 explicit geometric_distribution(double __p = 0.5) : __p_(__p) {}
5320 _LIBCPP_INLINE_VISIBILITY
5321 explicit geometric_distribution(const param_type& __p) : __p_(__p) {}
5322 _LIBCPP_INLINE_VISIBILITY
5323 void reset() {}
5324
5325 // generating functions
5326 template<class _URNG>
5327 _LIBCPP_INLINE_VISIBILITY
5328 result_type operator()(_URNG& __g)
5329 {return (*this)(__g, __p_);}
5330 template<class _URNG>
5331 _LIBCPP_INLINE_VISIBILITY
5332 result_type operator()(_URNG& __g, const param_type& __p)
5333 {return negative_binomial_distribution<result_type>(1, __p.p())(__g);}
5334
5335 // property functions
5336 _LIBCPP_INLINE_VISIBILITY
5337 double p() const {return __p_.p();}
5338
5339 _LIBCPP_INLINE_VISIBILITY
5340 param_type param() const {return __p_;}
5341 _LIBCPP_INLINE_VISIBILITY
5342 void param(const param_type& __p) {__p_ = __p;}
5343
5344 _LIBCPP_INLINE_VISIBILITY
5345 result_type min() const {return 0;}
5346 _LIBCPP_INLINE_VISIBILITY
5347 result_type max() const {return numeric_limits<result_type>::max();}
5348
5349 friend _LIBCPP_INLINE_VISIBILITY
5350 bool operator==(const geometric_distribution& __x,
5351 const geometric_distribution& __y)
5352 {return __x.__p_ == __y.__p_;}
5353 friend _LIBCPP_INLINE_VISIBILITY
5354 bool operator!=(const geometric_distribution& __x,
5355 const geometric_distribution& __y)
5356 {return !(__x == __y);}
5357};
5358
5359template <class _CharT, class _Traits, class _IntType>
5360basic_ostream<_CharT, _Traits>&
5361operator<<(basic_ostream<_CharT, _Traits>& __os,
5362 const geometric_distribution<_IntType>& __x)
5363{
5364 __save_flags<_CharT, _Traits> __lx(__os);
5365 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
5366 ios_base::scientific);
5367 return __os << __x.p();
5368}
5369
5370template <class _CharT, class _Traits, class _IntType>
5371basic_istream<_CharT, _Traits>&
5372operator>>(basic_istream<_CharT, _Traits>& __is,
5373 geometric_distribution<_IntType>& __x)
5374{
5375 typedef geometric_distribution<_IntType> _Eng;
5376 typedef typename _Eng::param_type param_type;
5377 __save_flags<_CharT, _Traits> __lx(__is);
5378 __is.flags(ios_base::dec | ios_base::skipws);
5379 double __p;
5380 __is >> __p;
5381 if (!__is.fail())
5382 __x.param(param_type(__p));
5383 return __is;
5384}
5385
5386// chi_squared_distribution
5387
5388template<class _RealType = double>
5389class _LIBCPP_TEMPLATE_VIS chi_squared_distribution
5390{
5391public:
5392 // types
5393 typedef _RealType result_type;
5394
5395 class _LIBCPP_TEMPLATE_VIS param_type
5396 {
5397 result_type __n_;
5398 public:
5399 typedef chi_squared_distribution distribution_type;
5400
5401 _LIBCPP_INLINE_VISIBILITY
5402 explicit param_type(result_type __n = 1) : __n_(__n) {}
5403
5404 _LIBCPP_INLINE_VISIBILITY
5405 result_type n() const {return __n_;}
5406
5407 friend _LIBCPP_INLINE_VISIBILITY
5408 bool operator==(const param_type& __x, const param_type& __y)
5409 {return __x.__n_ == __y.__n_;}
5410 friend _LIBCPP_INLINE_VISIBILITY
5411 bool operator!=(const param_type& __x, const param_type& __y)
5412 {return !(__x == __y);}
5413 };
5414
5415private:
5416 param_type __p_;
5417
5418public:
5419 // constructor and reset functions
5420 _LIBCPP_INLINE_VISIBILITY
5421 explicit chi_squared_distribution(result_type __n = 1)
5422 : __p_(param_type(__n)) {}
5423 _LIBCPP_INLINE_VISIBILITY
5424 explicit chi_squared_distribution(const param_type& __p)
5425 : __p_(__p) {}
5426 _LIBCPP_INLINE_VISIBILITY
5427 void reset() {}
5428
5429 // generating functions
5430 template<class _URNG>
5431 _LIBCPP_INLINE_VISIBILITY
5432 result_type operator()(_URNG& __g)
5433 {return (*this)(__g, __p_);}
5434 template<class _URNG>
5435 _LIBCPP_INLINE_VISIBILITY
5436 result_type operator()(_URNG& __g, const param_type& __p)
5437 {return gamma_distribution<result_type>(__p.n() / 2, 2)(__g);}
5438
5439 // property functions
5440 _LIBCPP_INLINE_VISIBILITY
5441 result_type n() const {return __p_.n();}
5442
5443 _LIBCPP_INLINE_VISIBILITY
5444 param_type param() const {return __p_;}
5445 _LIBCPP_INLINE_VISIBILITY
5446 void param(const param_type& __p) {__p_ = __p;}
5447
5448 _LIBCPP_INLINE_VISIBILITY
5449 result_type min() const {return 0;}
5450 _LIBCPP_INLINE_VISIBILITY
5451 result_type max() const {return numeric_limits<result_type>::infinity();}
5452
5453 friend _LIBCPP_INLINE_VISIBILITY
5454 bool operator==(const chi_squared_distribution& __x,
5455 const chi_squared_distribution& __y)
5456 {return __x.__p_ == __y.__p_;}
5457 friend _LIBCPP_INLINE_VISIBILITY
5458 bool operator!=(const chi_squared_distribution& __x,
5459 const chi_squared_distribution& __y)
5460 {return !(__x == __y);}
5461};
5462
5463template <class _CharT, class _Traits, class _RT>
5464basic_ostream<_CharT, _Traits>&
5465operator<<(basic_ostream<_CharT, _Traits>& __os,
5466 const chi_squared_distribution<_RT>& __x)
5467{
5468 __save_flags<_CharT, _Traits> __lx(__os);
5469 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
5470 ios_base::scientific);
5471 __os << __x.n();
5472 return __os;
5473}
5474
5475template <class _CharT, class _Traits, class _RT>
5476basic_istream<_CharT, _Traits>&
5477operator>>(basic_istream<_CharT, _Traits>& __is,
5478 chi_squared_distribution<_RT>& __x)
5479{
5480 typedef chi_squared_distribution<_RT> _Eng;
5481 typedef typename _Eng::result_type result_type;
5482 typedef typename _Eng::param_type param_type;
5483 __save_flags<_CharT, _Traits> __lx(__is);
5484 __is.flags(ios_base::dec | ios_base::skipws);
5485 result_type __n;
5486 __is >> __n;
5487 if (!__is.fail())
5488 __x.param(param_type(__n));
5489 return __is;
5490}
5491
5492// cauchy_distribution
5493
5494template<class _RealType = double>
5495class _LIBCPP_TEMPLATE_VIS cauchy_distribution
5496{
5497public:
5498 // types
5499 typedef _RealType result_type;
5500
5501 class _LIBCPP_TEMPLATE_VIS param_type
5502 {
5503 result_type __a_;
5504 result_type __b_;
5505 public:
5506 typedef cauchy_distribution distribution_type;
5507
5508 _LIBCPP_INLINE_VISIBILITY
5509 explicit param_type(result_type __a = 0, result_type __b = 1)
5510 : __a_(__a), __b_(__b) {}
5511
5512 _LIBCPP_INLINE_VISIBILITY
5513 result_type a() const {return __a_;}
5514 _LIBCPP_INLINE_VISIBILITY
5515 result_type b() const {return __b_;}
5516
5517 friend _LIBCPP_INLINE_VISIBILITY
5518 bool operator==(const param_type& __x, const param_type& __y)
5519 {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
5520 friend _LIBCPP_INLINE_VISIBILITY
5521 bool operator!=(const param_type& __x, const param_type& __y)
5522 {return !(__x == __y);}
5523 };
5524
5525private:
5526 param_type __p_;
5527
5528public:
5529 // constructor and reset functions
5530 _LIBCPP_INLINE_VISIBILITY
5531 explicit cauchy_distribution(result_type __a = 0, result_type __b = 1)
5532 : __p_(param_type(__a, __b)) {}
5533 _LIBCPP_INLINE_VISIBILITY
5534 explicit cauchy_distribution(const param_type& __p)
5535 : __p_(__p) {}
5536 _LIBCPP_INLINE_VISIBILITY
5537 void reset() {}
5538
5539 // generating functions
5540 template<class _URNG>
5541 _LIBCPP_INLINE_VISIBILITY
5542 result_type operator()(_URNG& __g)
5543 {return (*this)(__g, __p_);}
5544 template<class _URNG> _LIBCPP_INLINE_VISIBILITY result_type operator()(_URNG& __g, const param_type& __p);
5545
5546 // property functions
5547 _LIBCPP_INLINE_VISIBILITY
5548 result_type a() const {return __p_.a();}
5549 _LIBCPP_INLINE_VISIBILITY
5550 result_type b() const {return __p_.b();}
5551
5552 _LIBCPP_INLINE_VISIBILITY
5553 param_type param() const {return __p_;}
5554 _LIBCPP_INLINE_VISIBILITY
5555 void param(const param_type& __p) {__p_ = __p;}
5556
5557 _LIBCPP_INLINE_VISIBILITY
5558 result_type min() const {return -numeric_limits<result_type>::infinity();}
5559 _LIBCPP_INLINE_VISIBILITY
5560 result_type max() const {return numeric_limits<result_type>::infinity();}
5561
5562 friend _LIBCPP_INLINE_VISIBILITY
5563 bool operator==(const cauchy_distribution& __x,
5564 const cauchy_distribution& __y)
5565 {return __x.__p_ == __y.__p_;}
5566 friend _LIBCPP_INLINE_VISIBILITY
5567 bool operator!=(const cauchy_distribution& __x,
5568 const cauchy_distribution& __y)
5569 {return !(__x == __y);}
5570};
5571
5572template <class _RealType>
5573template<class _URNG>
5574inline
5575_RealType
5576cauchy_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
5577{
5578 uniform_real_distribution<result_type> __gen;
5579 // purposefully let tan arg get as close to pi/2 as it wants, tan will return a finite
5580 return __p.a() + __p.b() * _VSTD::tan(3.1415926535897932384626433832795 * __gen(__g));
5581}
5582
5583template <class _CharT, class _Traits, class _RT>
5584basic_ostream<_CharT, _Traits>&
5585operator<<(basic_ostream<_CharT, _Traits>& __os,
5586 const cauchy_distribution<_RT>& __x)
5587{
5588 __save_flags<_CharT, _Traits> __lx(__os);
5589 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
5590 ios_base::scientific);
5591 _CharT __sp = __os.widen(' ');
5592 __os.fill(__sp);
5593 __os << __x.a() << __sp << __x.b();
5594 return __os;
5595}
5596
5597template <class _CharT, class _Traits, class _RT>
5598basic_istream<_CharT, _Traits>&
5599operator>>(basic_istream<_CharT, _Traits>& __is,
5600 cauchy_distribution<_RT>& __x)
5601{
5602 typedef cauchy_distribution<_RT> _Eng;
5603 typedef typename _Eng::result_type result_type;
5604 typedef typename _Eng::param_type param_type;
5605 __save_flags<_CharT, _Traits> __lx(__is);
5606 __is.flags(ios_base::dec | ios_base::skipws);
5607 result_type __a;
5608 result_type __b;
5609 __is >> __a >> __b;
5610 if (!__is.fail())
5611 __x.param(param_type(__a, __b));
5612 return __is;
5613}
5614
5615// fisher_f_distribution
5616
5617template<class _RealType = double>
5618class _LIBCPP_TEMPLATE_VIS fisher_f_distribution
5619{
5620public:
5621 // types
5622 typedef _RealType result_type;
5623
5624 class _LIBCPP_TEMPLATE_VIS param_type
5625 {
5626 result_type __m_;
5627 result_type __n_;
5628 public:
5629 typedef fisher_f_distribution distribution_type;
5630
5631 _LIBCPP_INLINE_VISIBILITY
5632 explicit param_type(result_type __m = 1, result_type __n = 1)
5633 : __m_(__m), __n_(__n) {}
5634
5635 _LIBCPP_INLINE_VISIBILITY
5636 result_type m() const {return __m_;}
5637 _LIBCPP_INLINE_VISIBILITY
5638 result_type n() const {return __n_;}
5639
5640 friend _LIBCPP_INLINE_VISIBILITY
5641 bool operator==(const param_type& __x, const param_type& __y)
5642 {return __x.__m_ == __y.__m_ && __x.__n_ == __y.__n_;}
5643 friend _LIBCPP_INLINE_VISIBILITY
5644 bool operator!=(const param_type& __x, const param_type& __y)
5645 {return !(__x == __y);}
5646 };
5647
5648private:
5649 param_type __p_;
5650
5651public:
5652 // constructor and reset functions
5653 _LIBCPP_INLINE_VISIBILITY
5654 explicit fisher_f_distribution(result_type __m = 1, result_type __n = 1)
5655 : __p_(param_type(__m, __n)) {}
5656 _LIBCPP_INLINE_VISIBILITY
5657 explicit fisher_f_distribution(const param_type& __p)
5658 : __p_(__p) {}
5659 _LIBCPP_INLINE_VISIBILITY
5660 void reset() {}
5661
5662 // generating functions
5663 template<class _URNG>
5664 _LIBCPP_INLINE_VISIBILITY
5665 result_type operator()(_URNG& __g)
5666 {return (*this)(__g, __p_);}
5667 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
5668
5669 // property functions
5670 _LIBCPP_INLINE_VISIBILITY
5671 result_type m() const {return __p_.m();}
5672 _LIBCPP_INLINE_VISIBILITY
5673 result_type n() const {return __p_.n();}
5674
5675 _LIBCPP_INLINE_VISIBILITY
5676 param_type param() const {return __p_;}
5677 _LIBCPP_INLINE_VISIBILITY
5678 void param(const param_type& __p) {__p_ = __p;}
5679
5680 _LIBCPP_INLINE_VISIBILITY
5681 result_type min() const {return 0;}
5682 _LIBCPP_INLINE_VISIBILITY
5683 result_type max() const {return numeric_limits<result_type>::infinity();}
5684
5685 friend _LIBCPP_INLINE_VISIBILITY
5686 bool operator==(const fisher_f_distribution& __x,
5687 const fisher_f_distribution& __y)
5688 {return __x.__p_ == __y.__p_;}
5689 friend _LIBCPP_INLINE_VISIBILITY
5690 bool operator!=(const fisher_f_distribution& __x,
5691 const fisher_f_distribution& __y)
5692 {return !(__x == __y);}
5693};
5694
5695template <class _RealType>
5696template<class _URNG>
5697_RealType
5698fisher_f_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
5699{
5700 gamma_distribution<result_type> __gdm(__p.m() * result_type(.5));
5701 gamma_distribution<result_type> __gdn(__p.n() * result_type(.5));
5702 return __p.n() * __gdm(__g) / (__p.m() * __gdn(__g));
5703}
5704
5705template <class _CharT, class _Traits, class _RT>
5706basic_ostream<_CharT, _Traits>&
5707operator<<(basic_ostream<_CharT, _Traits>& __os,
5708 const fisher_f_distribution<_RT>& __x)
5709{
5710 __save_flags<_CharT, _Traits> __lx(__os);
5711 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
5712 ios_base::scientific);
5713 _CharT __sp = __os.widen(' ');
5714 __os.fill(__sp);
5715 __os << __x.m() << __sp << __x.n();
5716 return __os;
5717}
5718
5719template <class _CharT, class _Traits, class _RT>
5720basic_istream<_CharT, _Traits>&
5721operator>>(basic_istream<_CharT, _Traits>& __is,
5722 fisher_f_distribution<_RT>& __x)
5723{
5724 typedef fisher_f_distribution<_RT> _Eng;
5725 typedef typename _Eng::result_type result_type;
5726 typedef typename _Eng::param_type param_type;
5727 __save_flags<_CharT, _Traits> __lx(__is);
5728 __is.flags(ios_base::dec | ios_base::skipws);
5729 result_type __m;
5730 result_type __n;
5731 __is >> __m >> __n;
5732 if (!__is.fail())
5733 __x.param(param_type(__m, __n));
5734 return __is;
5735}
5736
5737// student_t_distribution
5738
5739template<class _RealType = double>
5740class _LIBCPP_TEMPLATE_VIS student_t_distribution
5741{
5742public:
5743 // types
5744 typedef _RealType result_type;
5745
5746 class _LIBCPP_TEMPLATE_VIS param_type
5747 {
5748 result_type __n_;
5749 public:
5750 typedef student_t_distribution distribution_type;
5751
5752 _LIBCPP_INLINE_VISIBILITY
5753 explicit param_type(result_type __n = 1) : __n_(__n) {}
5754
5755 _LIBCPP_INLINE_VISIBILITY
5756 result_type n() const {return __n_;}
5757
5758 friend _LIBCPP_INLINE_VISIBILITY
5759 bool operator==(const param_type& __x, const param_type& __y)
5760 {return __x.__n_ == __y.__n_;}
5761 friend _LIBCPP_INLINE_VISIBILITY
5762 bool operator!=(const param_type& __x, const param_type& __y)
5763 {return !(__x == __y);}
5764 };
5765
5766private:
5767 param_type __p_;
5768 normal_distribution<result_type> __nd_;
5769
5770public:
5771 // constructor and reset functions
5772 _LIBCPP_INLINE_VISIBILITY
5773 explicit student_t_distribution(result_type __n = 1)
5774 : __p_(param_type(__n)) {}
5775 _LIBCPP_INLINE_VISIBILITY
5776 explicit student_t_distribution(const param_type& __p)
5777 : __p_(__p) {}
5778 _LIBCPP_INLINE_VISIBILITY
5779 void reset() {__nd_.reset();}
5780
5781 // generating functions
5782 template<class _URNG>
5783 _LIBCPP_INLINE_VISIBILITY
5784 result_type operator()(_URNG& __g)
5785 {return (*this)(__g, __p_);}
5786 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
5787
5788 // property functions
5789 _LIBCPP_INLINE_VISIBILITY
5790 result_type n() const {return __p_.n();}
5791
5792 _LIBCPP_INLINE_VISIBILITY
5793 param_type param() const {return __p_;}
5794 _LIBCPP_INLINE_VISIBILITY
5795 void param(const param_type& __p) {__p_ = __p;}
5796
5797 _LIBCPP_INLINE_VISIBILITY
5798 result_type min() const {return -numeric_limits<result_type>::infinity();}
5799 _LIBCPP_INLINE_VISIBILITY
5800 result_type max() const {return numeric_limits<result_type>::infinity();}
5801
5802 friend _LIBCPP_INLINE_VISIBILITY
5803 bool operator==(const student_t_distribution& __x,
5804 const student_t_distribution& __y)
5805 {return __x.__p_ == __y.__p_;}
5806 friend _LIBCPP_INLINE_VISIBILITY
5807 bool operator!=(const student_t_distribution& __x,
5808 const student_t_distribution& __y)
5809 {return !(__x == __y);}
5810};
5811
5812template <class _RealType>
5813template<class _URNG>
5814_RealType
5815student_t_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
5816{
5817 gamma_distribution<result_type> __gd(__p.n() * .5, 2);
5818 return __nd_(__g) * _VSTD::sqrt(__p.n()/__gd(__g));
5819}
5820
5821template <class _CharT, class _Traits, class _RT>
5822basic_ostream<_CharT, _Traits>&
5823operator<<(basic_ostream<_CharT, _Traits>& __os,
5824 const student_t_distribution<_RT>& __x)
5825{
5826 __save_flags<_CharT, _Traits> __lx(__os);
5827 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
5828 ios_base::scientific);
5829 __os << __x.n();
5830 return __os;
5831}
5832
5833template <class _CharT, class _Traits, class _RT>
5834basic_istream<_CharT, _Traits>&
5835operator>>(basic_istream<_CharT, _Traits>& __is,
5836 student_t_distribution<_RT>& __x)
5837{
5838 typedef student_t_distribution<_RT> _Eng;
5839 typedef typename _Eng::result_type result_type;
5840 typedef typename _Eng::param_type param_type;
5841 __save_flags<_CharT, _Traits> __lx(__is);
5842 __is.flags(ios_base::dec | ios_base::skipws);
5843 result_type __n;
5844 __is >> __n;
5845 if (!__is.fail())
5846 __x.param(param_type(__n));
5847 return __is;
5848}
5849
5850// discrete_distribution
5851
5852template<class _IntType = int>
5853class _LIBCPP_TEMPLATE_VIS discrete_distribution
5854{
5855public:
5856 // types
5857 typedef _IntType result_type;
5858
5859 class _LIBCPP_TEMPLATE_VIS param_type
5860 {
5861 vector<double> __p_;
5862 public:
5863 typedef discrete_distribution distribution_type;
5864
5865 _LIBCPP_INLINE_VISIBILITY
5866 param_type() {}
5867 template<class _InputIterator>
5868 _LIBCPP_INLINE_VISIBILITY
5869 param_type(_InputIterator __f, _InputIterator __l)
5870 : __p_(__f, __l) {__init();}
5871#ifndef _LIBCPP_CXX03_LANG
5872 _LIBCPP_INLINE_VISIBILITY
5873 param_type(initializer_list<double> __wl)
5874 : __p_(__wl.begin(), __wl.end()) {__init();}
5875#endif // _LIBCPP_CXX03_LANG
5876 template<class _UnaryOperation>
5877 param_type(size_t __nw, double __xmin, double __xmax,
5878 _UnaryOperation __fw);
5879
5880 vector<double> probabilities() const;
5881
5882 friend _LIBCPP_INLINE_VISIBILITY
5883 bool operator==(const param_type& __x, const param_type& __y)
5884 {return __x.__p_ == __y.__p_;}
5885 friend _LIBCPP_INLINE_VISIBILITY
5886 bool operator!=(const param_type& __x, const param_type& __y)
5887 {return !(__x == __y);}
5888
5889 private:
5890 void __init();
5891
5892 friend class discrete_distribution;
5893
5894 template <class _CharT, class _Traits, class _IT>
5895 friend
5896 basic_ostream<_CharT, _Traits>&
5897 operator<<(basic_ostream<_CharT, _Traits>& __os,
5898 const discrete_distribution<_IT>& __x);
5899
5900 template <class _CharT, class _Traits, class _IT>
5901 friend
5902 basic_istream<_CharT, _Traits>&
5903 operator>>(basic_istream<_CharT, _Traits>& __is,
5904 discrete_distribution<_IT>& __x);
5905 };
5906
5907private:
5908 param_type __p_;
5909
5910public:
5911 // constructor and reset functions
5912 _LIBCPP_INLINE_VISIBILITY
5913 discrete_distribution() {}
5914 template<class _InputIterator>
5915 _LIBCPP_INLINE_VISIBILITY
5916 discrete_distribution(_InputIterator __f, _InputIterator __l)
5917 : __p_(__f, __l) {}
5918#ifndef _LIBCPP_CXX03_LANG
5919 _LIBCPP_INLINE_VISIBILITY
5920 discrete_distribution(initializer_list<double> __wl)
5921 : __p_(__wl) {}
5922#endif // _LIBCPP_CXX03_LANG
5923 template<class _UnaryOperation>
5924 _LIBCPP_INLINE_VISIBILITY
5925 discrete_distribution(size_t __nw, double __xmin, double __xmax,
5926 _UnaryOperation __fw)
5927 : __p_(__nw, __xmin, __xmax, __fw) {}
5928 _LIBCPP_INLINE_VISIBILITY
5929 explicit discrete_distribution(const param_type& __p)
5930 : __p_(__p) {}
5931 _LIBCPP_INLINE_VISIBILITY
5932 void reset() {}
5933
5934 // generating functions
5935 template<class _URNG>
5936 _LIBCPP_INLINE_VISIBILITY
5937 result_type operator()(_URNG& __g)
5938 {return (*this)(__g, __p_);}
5939 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
5940
5941 // property functions
5942 _LIBCPP_INLINE_VISIBILITY
5943 vector<double> probabilities() const {return __p_.probabilities();}
5944
5945 _LIBCPP_INLINE_VISIBILITY
5946 param_type param() const {return __p_;}
5947 _LIBCPP_INLINE_VISIBILITY
5948 void param(const param_type& __p) {__p_ = __p;}
5949
5950 _LIBCPP_INLINE_VISIBILITY
5951 result_type min() const {return 0;}
5952 _LIBCPP_INLINE_VISIBILITY
5953 result_type max() const {return __p_.__p_.size();}
5954
5955 friend _LIBCPP_INLINE_VISIBILITY
5956 bool operator==(const discrete_distribution& __x,
5957 const discrete_distribution& __y)
5958 {return __x.__p_ == __y.__p_;}
5959 friend _LIBCPP_INLINE_VISIBILITY
5960 bool operator!=(const discrete_distribution& __x,
5961 const discrete_distribution& __y)
5962 {return !(__x == __y);}
5963
5964 template <class _CharT, class _Traits, class _IT>
5965 friend
5966 basic_ostream<_CharT, _Traits>&
5967 operator<<(basic_ostream<_CharT, _Traits>& __os,
5968 const discrete_distribution<_IT>& __x);
5969
5970 template <class _CharT, class _Traits, class _IT>
5971 friend
5972 basic_istream<_CharT, _Traits>&
5973 operator>>(basic_istream<_CharT, _Traits>& __is,
5974 discrete_distribution<_IT>& __x);
5975};
5976
5977template<class _IntType>
5978template<class _UnaryOperation>
5979discrete_distribution<_IntType>::param_type::param_type(size_t __nw,
5980 double __xmin,
5981 double __xmax,
5982 _UnaryOperation __fw)
5983{
5984 if (__nw > 1)
5985 {
5986 __p_.reserve(__nw - 1);
5987 double __d = (__xmax - __xmin) / __nw;
5988 double __d2 = __d / 2;
5989 for (size_t __k = 0; __k < __nw; ++__k)
5990 __p_.push_back(__fw(__xmin + __k * __d + __d2));
5991 __init();
5992 }
5993}
5994
5995template<class _IntType>
5996void
5997discrete_distribution<_IntType>::param_type::__init()
5998{
5999 if (!__p_.empty())
6000 {
6001 if (__p_.size() > 1)
6002 {
6003 double __s = _VSTD::accumulate(__p_.begin(), __p_.end(), 0.0);
6004 for (_VSTD::vector<double>::iterator __i = __p_.begin(), __e = __p_.end();
6005 __i < __e; ++__i)
6006 *__i /= __s;
6007 vector<double> __t(__p_.size() - 1);
6008 _VSTD::partial_sum(__p_.begin(), __p_.end() - 1, __t.begin());
6009 swap(__p_, __t);
6010 }
6011 else
6012 {
6013 __p_.clear();
6014 __p_.shrink_to_fit();
6015 }
6016 }
6017}
6018
6019template<class _IntType>
6020vector<double>
6021discrete_distribution<_IntType>::param_type::probabilities() const
6022{
6023 size_t __n = __p_.size();
6024 _VSTD::vector<double> __p(__n+1);
6025 _VSTD::adjacent_difference(__p_.begin(), __p_.end(), __p.begin());
6026 if (__n > 0)
6027 __p[__n] = 1 - __p_[__n-1];
6028 else
6029 __p[0] = 1;
6030 return __p;
6031}
6032
6033template<class _IntType>
6034template<class _URNG>
6035_IntType
6036discrete_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p)
6037{
6038 uniform_real_distribution<double> __gen;
6039 return static_cast<_IntType>(
6040 _VSTD::upper_bound(__p.__p_.begin(), __p.__p_.end(), __gen(__g)) -
6041 __p.__p_.begin());
6042}
6043
6044template <class _CharT, class _Traits, class _IT>
6045basic_ostream<_CharT, _Traits>&
6046operator<<(basic_ostream<_CharT, _Traits>& __os,
6047 const discrete_distribution<_IT>& __x)
6048{
6049 __save_flags<_CharT, _Traits> __lx(__os);
6050 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
6051 ios_base::scientific);
6052 _CharT __sp = __os.widen(' ');
6053 __os.fill(__sp);
6054 size_t __n = __x.__p_.__p_.size();
6055 __os << __n;
6056 for (size_t __i = 0; __i < __n; ++__i)
6057 __os << __sp << __x.__p_.__p_[__i];
6058 return __os;
6059}
6060
6061template <class _CharT, class _Traits, class _IT>
6062basic_istream<_CharT, _Traits>&
6063operator>>(basic_istream<_CharT, _Traits>& __is,
6064 discrete_distribution<_IT>& __x)
6065{
6066 __save_flags<_CharT, _Traits> __lx(__is);
6067 __is.flags(ios_base::dec | ios_base::skipws);
6068 size_t __n;
6069 __is >> __n;
6070 vector<double> __p(__n);
6071 for (size_t __i = 0; __i < __n; ++__i)
6072 __is >> __p[__i];
6073 if (!__is.fail())
6074 swap(__x.__p_.__p_, __p);
6075 return __is;
6076}
6077
6078// piecewise_constant_distribution
6079
6080template<class _RealType = double>
6081class _LIBCPP_TEMPLATE_VIS piecewise_constant_distribution
6082{
6083public:
6084 // types
6085 typedef _RealType result_type;
6086
6087 class _LIBCPP_TEMPLATE_VIS param_type
6088 {
6089 vector<result_type> __b_;
6090 vector<result_type> __densities_;
6091 vector<result_type> __areas_;
6092 public:
6093 typedef piecewise_constant_distribution distribution_type;
6094
6095 param_type();
6096 template<class _InputIteratorB, class _InputIteratorW>
6097 param_type(_InputIteratorB __fB, _InputIteratorB __lB,
6098 _InputIteratorW __fW);
6099#ifndef _LIBCPP_CXX03_LANG
6100 template<class _UnaryOperation>
6101 param_type(initializer_list<result_type> __bl, _UnaryOperation __fw);
6102#endif // _LIBCPP_CXX03_LANG
6103 template<class _UnaryOperation>
6104 param_type(size_t __nw, result_type __xmin, result_type __xmax,
6105 _UnaryOperation __fw);
6106 param_type & operator=(const param_type& __rhs);
6107
6108 _LIBCPP_INLINE_VISIBILITY
6109 vector<result_type> intervals() const {return __b_;}
6110 _LIBCPP_INLINE_VISIBILITY
6111 vector<result_type> densities() const {return __densities_;}
6112
6113 friend _LIBCPP_INLINE_VISIBILITY
6114 bool operator==(const param_type& __x, const param_type& __y)
6115 {return __x.__densities_ == __y.__densities_ && __x.__b_ == __y.__b_;}
6116 friend _LIBCPP_INLINE_VISIBILITY
6117 bool operator!=(const param_type& __x, const param_type& __y)
6118 {return !(__x == __y);}
6119
6120 private:
6121 void __init();
6122
6123 friend class piecewise_constant_distribution;
6124
6125 template <class _CharT, class _Traits, class _RT>
6126 friend
6127 basic_ostream<_CharT, _Traits>&
6128 operator<<(basic_ostream<_CharT, _Traits>& __os,
6129 const piecewise_constant_distribution<_RT>& __x);
6130
6131 template <class _CharT, class _Traits, class _RT>
6132 friend
6133 basic_istream<_CharT, _Traits>&
6134 operator>>(basic_istream<_CharT, _Traits>& __is,
6135 piecewise_constant_distribution<_RT>& __x);
6136 };
6137
6138private:
6139 param_type __p_;
6140
6141public:
6142 // constructor and reset functions
6143 _LIBCPP_INLINE_VISIBILITY
6144 piecewise_constant_distribution() {}
6145 template<class _InputIteratorB, class _InputIteratorW>
6146 _LIBCPP_INLINE_VISIBILITY
6147 piecewise_constant_distribution(_InputIteratorB __fB,
6148 _InputIteratorB __lB,
6149 _InputIteratorW __fW)
6150 : __p_(__fB, __lB, __fW) {}
6151
6152#ifndef _LIBCPP_CXX03_LANG
6153 template<class _UnaryOperation>
6154 _LIBCPP_INLINE_VISIBILITY
6155 piecewise_constant_distribution(initializer_list<result_type> __bl,
6156 _UnaryOperation __fw)
6157 : __p_(__bl, __fw) {}
6158#endif // _LIBCPP_CXX03_LANG
6159
6160 template<class _UnaryOperation>
6161 _LIBCPP_INLINE_VISIBILITY
6162 piecewise_constant_distribution(size_t __nw, result_type __xmin,
6163 result_type __xmax, _UnaryOperation __fw)
6164 : __p_(__nw, __xmin, __xmax, __fw) {}
6165
6166 _LIBCPP_INLINE_VISIBILITY
6167 explicit piecewise_constant_distribution(const param_type& __p)
6168 : __p_(__p) {}
6169
6170 _LIBCPP_INLINE_VISIBILITY
6171 void reset() {}
6172
6173 // generating functions
6174 template<class _URNG>
6175 _LIBCPP_INLINE_VISIBILITY
6176 result_type operator()(_URNG& __g)
6177 {return (*this)(__g, __p_);}
6178 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
6179
6180 // property functions
6181 _LIBCPP_INLINE_VISIBILITY
6182 vector<result_type> intervals() const {return __p_.intervals();}
6183 _LIBCPP_INLINE_VISIBILITY
6184 vector<result_type> densities() const {return __p_.densities();}
6185
6186 _LIBCPP_INLINE_VISIBILITY
6187 param_type param() const {return __p_;}
6188 _LIBCPP_INLINE_VISIBILITY
6189 void param(const param_type& __p) {__p_ = __p;}
6190
6191 _LIBCPP_INLINE_VISIBILITY
6192 result_type min() const {return __p_.__b_.front();}
6193 _LIBCPP_INLINE_VISIBILITY
6194 result_type max() const {return __p_.__b_.back();}
6195
6196 friend _LIBCPP_INLINE_VISIBILITY
6197 bool operator==(const piecewise_constant_distribution& __x,
6198 const piecewise_constant_distribution& __y)
6199 {return __x.__p_ == __y.__p_;}
6200 friend _LIBCPP_INLINE_VISIBILITY
6201 bool operator!=(const piecewise_constant_distribution& __x,
6202 const piecewise_constant_distribution& __y)
6203 {return !(__x == __y);}
6204
6205 template <class _CharT, class _Traits, class _RT>
6206 friend
6207 basic_ostream<_CharT, _Traits>&
6208 operator<<(basic_ostream<_CharT, _Traits>& __os,
6209 const piecewise_constant_distribution<_RT>& __x);
6210
6211 template <class _CharT, class _Traits, class _RT>
6212 friend
6213 basic_istream<_CharT, _Traits>&
6214 operator>>(basic_istream<_CharT, _Traits>& __is,
6215 piecewise_constant_distribution<_RT>& __x);
6216};
6217
6218template<class _RealType>
6219typename piecewise_constant_distribution<_RealType>::param_type &
6220piecewise_constant_distribution<_RealType>::param_type::operator=
6221 (const param_type& __rhs)
6222{
6223// These can throw
6224 __b_.reserve (__rhs.__b_.size ());
6225 __densities_.reserve(__rhs.__densities_.size());
6226 __areas_.reserve (__rhs.__areas_.size());
6227
6228// These can not throw
6229 __b_ = __rhs.__b_;
6230 __densities_ = __rhs.__densities_;
6231 __areas_ = __rhs.__areas_;
6232 return *this;
6233}
6234
6235template<class _RealType>
6236void
6237piecewise_constant_distribution<_RealType>::param_type::__init()
6238{
6239 // __densities_ contains non-normalized areas
6240 result_type __total_area = _VSTD::accumulate(__densities_.begin(),
6241 __densities_.end(),
6242 result_type());
6243 for (size_t __i = 0; __i < __densities_.size(); ++__i)
6244 __densities_[__i] /= __total_area;
6245 // __densities_ contains normalized areas
6246 __areas_.assign(__densities_.size(), result_type());
6247 _VSTD::partial_sum(__densities_.begin(), __densities_.end() - 1,
6248 __areas_.begin() + 1);
6249 // __areas_ contains partial sums of normalized areas: [0, __densities_ - 1]
6250 __densities_.back() = 1 - __areas_.back(); // correct round off error
6251 for (size_t __i = 0; __i < __densities_.size(); ++__i)
6252 __densities_[__i] /= (__b_[__i+1] - __b_[__i]);
6253 // __densities_ now contains __densities_
6254}
6255
6256template<class _RealType>
6257piecewise_constant_distribution<_RealType>::param_type::param_type()
6258 : __b_(2),
6259 __densities_(1, 1.0),
6260 __areas_(1, 0.0)
6261{
6262 __b_[1] = 1;
6263}
6264
6265template<class _RealType>
6266template<class _InputIteratorB, class _InputIteratorW>
6267piecewise_constant_distribution<_RealType>::param_type::param_type(
6268 _InputIteratorB __fB, _InputIteratorB __lB, _InputIteratorW __fW)
6269 : __b_(__fB, __lB)
6270{
6271 if (__b_.size() < 2)
6272 {
6273 __b_.resize(2);
6274 __b_[0] = 0;
6275 __b_[1] = 1;
6276 __densities_.assign(1, 1.0);
6277 __areas_.assign(1, 0.0);
6278 }
6279 else
6280 {
6281 __densities_.reserve(__b_.size() - 1);
6282 for (size_t __i = 0; __i < __b_.size() - 1; ++__i, ++__fW)
6283 __densities_.push_back(*__fW);
6284 __init();
6285 }
6286}
6287
6288#ifndef _LIBCPP_CXX03_LANG
6289
6290template<class _RealType>
6291template<class _UnaryOperation>
6292piecewise_constant_distribution<_RealType>::param_type::param_type(
6293 initializer_list<result_type> __bl, _UnaryOperation __fw)
6294 : __b_(__bl.begin(), __bl.end())
6295{
6296 if (__b_.size() < 2)
6297 {
6298 __b_.resize(2);
6299 __b_[0] = 0;
6300 __b_[1] = 1;
6301 __densities_.assign(1, 1.0);
6302 __areas_.assign(1, 0.0);
6303 }
6304 else
6305 {
6306 __densities_.reserve(__b_.size() - 1);
6307 for (size_t __i = 0; __i < __b_.size() - 1; ++__i)
6308 __densities_.push_back(__fw((__b_[__i+1] + __b_[__i])*.5));
6309 __init();
6310 }
6311}
6312
6313#endif // _LIBCPP_CXX03_LANG
6314
6315template<class _RealType>
6316template<class _UnaryOperation>
6317piecewise_constant_distribution<_RealType>::param_type::param_type(
6318 size_t __nw, result_type __xmin, result_type __xmax, _UnaryOperation __fw)
6319 : __b_(__nw == 0 ? 2 : __nw + 1)
6320{
6321 size_t __n = __b_.size() - 1;
6322 result_type __d = (__xmax - __xmin) / __n;
6323 __densities_.reserve(__n);
6324 for (size_t __i = 0; __i < __n; ++__i)
6325 {
6326 __b_[__i] = __xmin + __i * __d;
6327 __densities_.push_back(__fw(__b_[__i] + __d*.5));
6328 }
6329 __b_[__n] = __xmax;
6330 __init();
6331}
6332
6333template<class _RealType>
6334template<class _URNG>
6335_RealType
6336piecewise_constant_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
6337{
6338 typedef uniform_real_distribution<result_type> _Gen;
6339 result_type __u = _Gen()(__g);
6340 ptrdiff_t __k = _VSTD::upper_bound(__p.__areas_.begin(), __p.__areas_.end(),
6341 __u) - __p.__areas_.begin() - 1;
6342 return (__u - __p.__areas_[__k]) / __p.__densities_[__k] + __p.__b_[__k];
6343}
6344
6345template <class _CharT, class _Traits, class _RT>
6346basic_ostream<_CharT, _Traits>&
6347operator<<(basic_ostream<_CharT, _Traits>& __os,
6348 const piecewise_constant_distribution<_RT>& __x)
6349{
6350 __save_flags<_CharT, _Traits> __lx(__os);
6351 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
6352 ios_base::scientific);
6353 _CharT __sp = __os.widen(' ');
6354 __os.fill(__sp);
6355 size_t __n = __x.__p_.__b_.size();
6356 __os << __n;
6357 for (size_t __i = 0; __i < __n; ++__i)
6358 __os << __sp << __x.__p_.__b_[__i];
6359 __n = __x.__p_.__densities_.size();
6360 __os << __sp << __n;
6361 for (size_t __i = 0; __i < __n; ++__i)
6362 __os << __sp << __x.__p_.__densities_[__i];
6363 __n = __x.__p_.__areas_.size();
6364 __os << __sp << __n;
6365 for (size_t __i = 0; __i < __n; ++__i)
6366 __os << __sp << __x.__p_.__areas_[__i];
6367 return __os;
6368}
6369
6370template <class _CharT, class _Traits, class _RT>
6371basic_istream<_CharT, _Traits>&
6372operator>>(basic_istream<_CharT, _Traits>& __is,
6373 piecewise_constant_distribution<_RT>& __x)
6374{
6375 typedef piecewise_constant_distribution<_RT> _Eng;
6376 typedef typename _Eng::result_type result_type;
6377 __save_flags<_CharT, _Traits> __lx(__is);
6378 __is.flags(ios_base::dec | ios_base::skipws);
6379 size_t __n;
6380 __is >> __n;
6381 vector<result_type> __b(__n);
6382 for (size_t __i = 0; __i < __n; ++__i)
6383 __is >> __b[__i];
6384 __is >> __n;
6385 vector<result_type> __densities(__n);
6386 for (size_t __i = 0; __i < __n; ++__i)
6387 __is >> __densities[__i];
6388 __is >> __n;
6389 vector<result_type> __areas(__n);
6390 for (size_t __i = 0; __i < __n; ++__i)
6391 __is >> __areas[__i];
6392 if (!__is.fail())
6393 {
6394 swap(__x.__p_.__b_, __b);
6395 swap(__x.__p_.__densities_, __densities);
6396 swap(__x.__p_.__areas_, __areas);
6397 }
6398 return __is;
6399}
6400
6401// piecewise_linear_distribution
6402
6403template<class _RealType = double>
6404class _LIBCPP_TEMPLATE_VIS piecewise_linear_distribution
6405{
6406public:
6407 // types
6408 typedef _RealType result_type;
6409
6410 class _LIBCPP_TEMPLATE_VIS param_type
6411 {
6412 vector<result_type> __b_;
6413 vector<result_type> __densities_;
6414 vector<result_type> __areas_;
6415 public:
6416 typedef piecewise_linear_distribution distribution_type;
6417
6418 param_type();
6419 template<class _InputIteratorB, class _InputIteratorW>
6420 param_type(_InputIteratorB __fB, _InputIteratorB __lB,
6421 _InputIteratorW __fW);
6422#ifndef _LIBCPP_CXX03_LANG
6423 template<class _UnaryOperation>
6424 param_type(initializer_list<result_type> __bl, _UnaryOperation __fw);
6425#endif // _LIBCPP_CXX03_LANG
6426 template<class _UnaryOperation>
6427 param_type(size_t __nw, result_type __xmin, result_type __xmax,
6428 _UnaryOperation __fw);
6429 param_type & operator=(const param_type& __rhs);
6430
6431 _LIBCPP_INLINE_VISIBILITY
6432 vector<result_type> intervals() const {return __b_;}
6433 _LIBCPP_INLINE_VISIBILITY
6434 vector<result_type> densities() const {return __densities_;}
6435
6436 friend _LIBCPP_INLINE_VISIBILITY
6437 bool operator==(const param_type& __x, const param_type& __y)
6438 {return __x.__densities_ == __y.__densities_ && __x.__b_ == __y.__b_;}
6439 friend _LIBCPP_INLINE_VISIBILITY
6440 bool operator!=(const param_type& __x, const param_type& __y)
6441 {return !(__x == __y);}
6442
6443 private:
6444 void __init();
6445
6446 friend class piecewise_linear_distribution;
6447
6448 template <class _CharT, class _Traits, class _RT>
6449 friend
6450 basic_ostream<_CharT, _Traits>&
6451 operator<<(basic_ostream<_CharT, _Traits>& __os,
6452 const piecewise_linear_distribution<_RT>& __x);
6453
6454 template <class _CharT, class _Traits, class _RT>
6455 friend
6456 basic_istream<_CharT, _Traits>&
6457 operator>>(basic_istream<_CharT, _Traits>& __is,
6458 piecewise_linear_distribution<_RT>& __x);
6459 };
6460
6461private:
6462 param_type __p_;
6463
6464public:
6465 // constructor and reset functions
6466 _LIBCPP_INLINE_VISIBILITY
6467 piecewise_linear_distribution() {}
6468 template<class _InputIteratorB, class _InputIteratorW>
6469 _LIBCPP_INLINE_VISIBILITY
6470 piecewise_linear_distribution(_InputIteratorB __fB,
6471 _InputIteratorB __lB,
6472 _InputIteratorW __fW)
6473 : __p_(__fB, __lB, __fW) {}
6474
6475#ifndef _LIBCPP_CXX03_LANG
6476 template<class _UnaryOperation>
6477 _LIBCPP_INLINE_VISIBILITY
6478 piecewise_linear_distribution(initializer_list<result_type> __bl,
6479 _UnaryOperation __fw)
6480 : __p_(__bl, __fw) {}
6481#endif // _LIBCPP_CXX03_LANG
6482
6483 template<class _UnaryOperation>
6484 _LIBCPP_INLINE_VISIBILITY
6485 piecewise_linear_distribution(size_t __nw, result_type __xmin,
6486 result_type __xmax, _UnaryOperation __fw)
6487 : __p_(__nw, __xmin, __xmax, __fw) {}
6488
6489 _LIBCPP_INLINE_VISIBILITY
6490 explicit piecewise_linear_distribution(const param_type& __p)
6491 : __p_(__p) {}
6492
6493 _LIBCPP_INLINE_VISIBILITY
6494 void reset() {}
6495
6496 // generating functions
6497 template<class _URNG>
6498 _LIBCPP_INLINE_VISIBILITY
6499 result_type operator()(_URNG& __g)
6500 {return (*this)(__g, __p_);}
6501 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
6502
6503 // property functions
6504 _LIBCPP_INLINE_VISIBILITY
6505 vector<result_type> intervals() const {return __p_.intervals();}
6506 _LIBCPP_INLINE_VISIBILITY
6507 vector<result_type> densities() const {return __p_.densities();}
6508
6509 _LIBCPP_INLINE_VISIBILITY
6510 param_type param() const {return __p_;}
6511 _LIBCPP_INLINE_VISIBILITY
6512 void param(const param_type& __p) {__p_ = __p;}
6513
6514 _LIBCPP_INLINE_VISIBILITY
6515 result_type min() const {return __p_.__b_.front();}
6516 _LIBCPP_INLINE_VISIBILITY
6517 result_type max() const {return __p_.__b_.back();}
6518
6519 friend _LIBCPP_INLINE_VISIBILITY
6520 bool operator==(const piecewise_linear_distribution& __x,
6521 const piecewise_linear_distribution& __y)
6522 {return __x.__p_ == __y.__p_;}
6523 friend _LIBCPP_INLINE_VISIBILITY
6524 bool operator!=(const piecewise_linear_distribution& __x,
6525 const piecewise_linear_distribution& __y)
6526 {return !(__x == __y);}
6527
6528 template <class _CharT, class _Traits, class _RT>
6529 friend
6530 basic_ostream<_CharT, _Traits>&
6531 operator<<(basic_ostream<_CharT, _Traits>& __os,
6532 const piecewise_linear_distribution<_RT>& __x);
6533
6534 template <class _CharT, class _Traits, class _RT>
6535 friend
6536 basic_istream<_CharT, _Traits>&
6537 operator>>(basic_istream<_CharT, _Traits>& __is,
6538 piecewise_linear_distribution<_RT>& __x);
6539};
6540
6541template<class _RealType>
6542typename piecewise_linear_distribution<_RealType>::param_type &
6543piecewise_linear_distribution<_RealType>::param_type::operator=
6544 (const param_type& __rhs)
6545{
6546// These can throw
6547 __b_.reserve (__rhs.__b_.size ());
6548 __densities_.reserve(__rhs.__densities_.size());
6549 __areas_.reserve (__rhs.__areas_.size());
6550
6551// These can not throw
6552 __b_ = __rhs.__b_;
6553 __densities_ = __rhs.__densities_;
6554 __areas_ = __rhs.__areas_;
6555 return *this;
6556}
6557
6558
6559template<class _RealType>
6560void
6561piecewise_linear_distribution<_RealType>::param_type::__init()
6562{
6563 __areas_.assign(__densities_.size() - 1, result_type());
6564 result_type _Sp = 0;
6565 for (size_t __i = 0; __i < __areas_.size(); ++__i)
6566 {
6567 __areas_[__i] = (__densities_[__i+1] + __densities_[__i]) *
6568 (__b_[__i+1] - __b_[__i]) * .5;
6569 _Sp += __areas_[__i];
6570 }
6571 for (size_t __i = __areas_.size(); __i > 1;)
6572 {
6573 --__i;
6574 __areas_[__i] = __areas_[__i-1] / _Sp;
6575 }
6576 __areas_[0] = 0;
6577 for (size_t __i = 1; __i < __areas_.size(); ++__i)
6578 __areas_[__i] += __areas_[__i-1];
6579 for (size_t __i = 0; __i < __densities_.size(); ++__i)
6580 __densities_[__i] /= _Sp;
6581}
6582
6583template<class _RealType>
6584piecewise_linear_distribution<_RealType>::param_type::param_type()
6585 : __b_(2),
6586 __densities_(2, 1.0),
6587 __areas_(1, 0.0)
6588{
6589 __b_[1] = 1;
6590}
6591
6592template<class _RealType>
6593template<class _InputIteratorB, class _InputIteratorW>
6594piecewise_linear_distribution<_RealType>::param_type::param_type(
6595 _InputIteratorB __fB, _InputIteratorB __lB, _InputIteratorW __fW)
6596 : __b_(__fB, __lB)
6597{
6598 if (__b_.size() < 2)
6599 {
6600 __b_.resize(2);
6601 __b_[0] = 0;
6602 __b_[1] = 1;
6603 __densities_.assign(2, 1.0);
6604 __areas_.assign(1, 0.0);
6605 }
6606 else
6607 {
6608 __densities_.reserve(__b_.size());
6609 for (size_t __i = 0; __i < __b_.size(); ++__i, ++__fW)
6610 __densities_.push_back(*__fW);
6611 __init();
6612 }
6613}
6614
6615#ifndef _LIBCPP_CXX03_LANG
6616
6617template<class _RealType>
6618template<class _UnaryOperation>
6619piecewise_linear_distribution<_RealType>::param_type::param_type(
6620 initializer_list<result_type> __bl, _UnaryOperation __fw)
6621 : __b_(__bl.begin(), __bl.end())
6622{
6623 if (__b_.size() < 2)
6624 {
6625 __b_.resize(2);
6626 __b_[0] = 0;
6627 __b_[1] = 1;
6628 __densities_.assign(2, 1.0);
6629 __areas_.assign(1, 0.0);
6630 }
6631 else
6632 {
6633 __densities_.reserve(__b_.size());
6634 for (size_t __i = 0; __i < __b_.size(); ++__i)
6635 __densities_.push_back(__fw(__b_[__i]));
6636 __init();
6637 }
6638}
6639
6640#endif // _LIBCPP_CXX03_LANG
6641
6642template<class _RealType>
6643template<class _UnaryOperation>
6644piecewise_linear_distribution<_RealType>::param_type::param_type(
6645 size_t __nw, result_type __xmin, result_type __xmax, _UnaryOperation __fw)
6646 : __b_(__nw == 0 ? 2 : __nw + 1)
6647{
6648 size_t __n = __b_.size() - 1;
6649 result_type __d = (__xmax - __xmin) / __n;
6650 __densities_.reserve(__b_.size());
6651 for (size_t __i = 0; __i < __n; ++__i)
6652 {
6653 __b_[__i] = __xmin + __i * __d;
6654 __densities_.push_back(__fw(__b_[__i]));
6655 }
6656 __b_[__n] = __xmax;
6657 __densities_.push_back(__fw(__b_[__n]));
6658 __init();
6659}
6660
6661template<class _RealType>
6662template<class _URNG>
6663_RealType
6664piecewise_linear_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
6665{
6666 typedef uniform_real_distribution<result_type> _Gen;
6667 result_type __u = _Gen()(__g);
6668 ptrdiff_t __k = _VSTD::upper_bound(__p.__areas_.begin(), __p.__areas_.end(),
6669 __u) - __p.__areas_.begin() - 1;
6670 __u -= __p.__areas_[__k];
6671 const result_type __dk = __p.__densities_[__k];
6672 const result_type __dk1 = __p.__densities_[__k+1];
6673 const result_type __deltad = __dk1 - __dk;
6674 const result_type __bk = __p.__b_[__k];
6675 if (__deltad == 0)
6676 return __u / __dk + __bk;
6677 const result_type __bk1 = __p.__b_[__k+1];
6678 const result_type __deltab = __bk1 - __bk;
6679 return (__bk * __dk1 - __bk1 * __dk +
6680 _VSTD::sqrt(__deltab * (__deltab * __dk * __dk + 2 * __deltad * __u))) /
6681 __deltad;
6682}
6683
6684template <class _CharT, class _Traits, class _RT>
6685basic_ostream<_CharT, _Traits>&
6686operator<<(basic_ostream<_CharT, _Traits>& __os,
6687 const piecewise_linear_distribution<_RT>& __x)
6688{
6689 __save_flags<_CharT, _Traits> __lx(__os);
6690 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
6691 ios_base::scientific);
6692 _CharT __sp = __os.widen(' ');
6693 __os.fill(__sp);
6694 size_t __n = __x.__p_.__b_.size();
6695 __os << __n;
6696 for (size_t __i = 0; __i < __n; ++__i)
6697 __os << __sp << __x.__p_.__b_[__i];
6698 __n = __x.__p_.__densities_.size();
6699 __os << __sp << __n;
6700 for (size_t __i = 0; __i < __n; ++__i)
6701 __os << __sp << __x.__p_.__densities_[__i];
6702 __n = __x.__p_.__areas_.size();
6703 __os << __sp << __n;
6704 for (size_t __i = 0; __i < __n; ++__i)
6705 __os << __sp << __x.__p_.__areas_[__i];
6706 return __os;
6707}
6708
6709template <class _CharT, class _Traits, class _RT>
6710basic_istream<_CharT, _Traits>&
6711operator>>(basic_istream<_CharT, _Traits>& __is,
6712 piecewise_linear_distribution<_RT>& __x)
6713{
6714 typedef piecewise_linear_distribution<_RT> _Eng;
6715 typedef typename _Eng::result_type result_type;
6716 __save_flags<_CharT, _Traits> __lx(__is);
6717 __is.flags(ios_base::dec | ios_base::skipws);
6718 size_t __n;
6719 __is >> __n;
6720 vector<result_type> __b(__n);
6721 for (size_t __i = 0; __i < __n; ++__i)
6722 __is >> __b[__i];
6723 __is >> __n;
6724 vector<result_type> __densities(__n);
6725 for (size_t __i = 0; __i < __n; ++__i)
6726 __is >> __densities[__i];
6727 __is >> __n;
6728 vector<result_type> __areas(__n);
6729 for (size_t __i = 0; __i < __n; ++__i)
6730 __is >> __areas[__i];
6731 if (!__is.fail())
6732 {
6733 swap(__x.__p_.__b_, __b);
6734 swap(__x.__p_.__densities_, __densities);
6735 swap(__x.__p_.__areas_, __areas);
6736 }
6737 return __is;
6738}
6739
6740_LIBCPP_END_NAMESPACE_STD
6741
6742_LIBCPP_POP_MACROS
6743
6744#endif // _LIBCPP_RANDOM