Gitiles
Code Review Sign In
gerrit-public.fairphone.software / platform / external / libcxx / ed2c2916b218361524764b6da427db2f2cb249f6 / . / include / random
blob: f3e6656c052f6d3a63fe06b17551d68fd2c5552f [file] [log] [blame]
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]1// -*- C++ -*-
2//===--------------------------- random -----------------------------------===//
3//
Howard Hinnantf5256e12010-05-11 21:36:01 +0000[diff] [blame]4// The LLVM Compiler Infrastructure
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]5//
6// This file is distributed under the University of Illinois Open Source
7// License. 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;
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;
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;
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;
Howard Hinnantd6d11712010-05-20 15:11:46 +0000[diff] [blame]374typedef minstd_rand default_random_engine;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]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;
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>
Howard Hinnant03aad812010-05-11 23:26:59 +0000[diff] [blame]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};
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]667
668template<class IntType = int>
Howard Hinnant34e8a572010-05-17 13:44:27 +0000[diff] [blame]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};
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]723
724template<class IntType = int>
Howard Hinnantf2fe5d52010-05-17 00:09:38 +0000[diff] [blame]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};
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]781
782template<class IntType = int>
Howard Hinnant4ff556c2010-05-14 21:38:54 +0000[diff] [blame]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};
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]837
838template<class RealType = double>
Howard Hinnant30a840f2010-05-12 17:08:57 +0000[diff] [blame]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
Howard Hinnanta64111c2010-05-12 21:02:31 +0000[diff] [blame]850 explicit param_type(result_type lambda = 1.0);
Howard Hinnant30a840f2010-05-12 17:08:57 +0000[diff] [blame]851
Howard Hinnanta64111c2010-05-12 21:02:31 +0000[diff] [blame]852 result_type lambda() const;
Howard Hinnant30a840f2010-05-12 17:08:57 +0000[diff] [blame]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
Howard Hinnanta64111c2010-05-12 21:02:31 +0000[diff] [blame]859 explicit exponential_distribution(result_type lambda = 1.0);
Howard Hinnant30a840f2010-05-12 17:08:57 +0000[diff] [blame]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
Howard Hinnanta64111c2010-05-12 21:02:31 +0000[diff] [blame]868 result_type lambda() const;
Howard Hinnant30a840f2010-05-12 17:08:57 +0000[diff] [blame]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};
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]893
894template<class RealType = double>
Howard Hinnantc7c49132010-05-13 17:58:28 +0000[diff] [blame]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};
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]951
952template<class RealType = double>
Howard Hinnant9de6e302010-05-16 01:09:02 +0000[diff] [blame]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
Howard Hinnant9de6e302010-05-16 01:09:02 +0000[diff] [blame]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};
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]1009
1010template<class RealType = double>
Howard Hinnantc2b0dc72010-05-17 16:21:56 +0000[diff] [blame]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};
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]1067
1068template<class RealType = double>
Howard Hinnanta64111c2010-05-12 21:02:31 +0000[diff] [blame]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};
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]1125
1126template<class RealType = double>
Howard Hinnant2bc36fc2010-05-17 18:31:53 +0000[diff] [blame]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};
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]1183
1184template<class RealType = double>
Howard Hinnant97dc2f32010-05-15 23:36:00 +0000[diff] [blame]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
Howard Hinnant97dc2f32010-05-15 23:36:00 +0000[diff] [blame]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};
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]1239
1240template<class RealType = double>
Howard Hinnantd7d01132010-05-17 21:55:46 +0000[diff] [blame]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};
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]1297
1298template<class RealType = double>
Howard Hinnantd8bc09b2010-05-18 17:32:30 +0000[diff] [blame]1299class fisher_f_distribution
1300{
1301public:
1302 // types
1303 typedef RealType result_type;
1304
1305 class param_type
1306 {
1307 public:
Howard Hinnant321b4bb2010-05-18 20:08:04 +0000[diff] [blame]1308 typedef fisher_f_distribution distribution_type;
Howard Hinnantd8bc09b2010-05-18 17:32:30 +0000[diff] [blame]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};
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]1355
1356template<class RealType = double>
Howard Hinnant321b4bb2010-05-18 20:08:04 +0000[diff] [blame]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};
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]1411
1412template<class IntType = int>
Howard Hinnant551d8e42010-05-19 01:53:57 +0000[diff] [blame]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};
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]1478
1479template<class RealType = double>
Howard Hinnantd6d11712010-05-20 15:11:46 +0000[diff] [blame]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<double> 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<double> 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};
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]1553
1554template<class RealType = double>
Howard Hinnant54305402010-05-25 00:27:34 +0000[diff] [blame]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<double> 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<double> 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};
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]1631
1632} // std
1633*/
1634
1635#include <__config>
1636#include <cstddef>
1637#include <type_traits>
1638#include <initializer_list>
1639#include <cstdint>
1640#include <limits>
1641#include <algorithm>
Howard Hinnant551d8e42010-05-19 01:53:57 +0000[diff] [blame]1642#include <numeric>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]1643#include <vector>
1644#include <string>
1645#include <istream>
1646#include <ostream>
Howard Hinnant30a840f2010-05-12 17:08:57 +0000[diff] [blame]1647#include <cmath>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]1648
1649#pragma GCC system_header
1650
1651_LIBCPP_BEGIN_NAMESPACE_STD
1652
1653// linear_congruential_engine
1654
1655template <unsigned long long __a, unsigned long long __c,
1656 unsigned long long __m, unsigned long long _M,
1657 bool _MightOverflow = (__a != 0 && __m != 0 && __m-1 > (_M-__c)/__a)>
1658struct __lce_ta;
1659
1660// 64
1661
1662template <unsigned long long __a, unsigned long long __c, unsigned long long __m>
1663struct __lce_ta<__a, __c, __m, (unsigned long long)(~0), true>
1664{
1665 typedef unsigned long long result_type;
1666 static result_type next(result_type __x)
1667 {
1668 // Schrage's algorithm
1669 const result_type __q = __m / __a;
1670 const result_type __r = __m % __a;
1671 const result_type __t0 = __a * (__x % __q);
1672 const result_type __t1 = __r * (__x / __q);
1673 __x = __t0 + (__t0 < __t1) * __m - __t1;
1674 __x += __c - (__x >= __m - __c) * __m;
1675 return __x;
1676 }
1677};
1678
1679template <unsigned long long __a, unsigned long long __m>
1680struct __lce_ta<__a, 0, __m, (unsigned long long)(~0), true>
1681{
1682 typedef unsigned long long result_type;
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 return __x;
1692 }
1693};
1694
1695template <unsigned long long __a, unsigned long long __c, unsigned long long __m>
1696struct __lce_ta<__a, __c, __m, (unsigned long long)(~0), false>
1697{
1698 typedef unsigned long long result_type;
1699 static result_type next(result_type __x)
1700 {
1701 return (__a * __x + __c) % __m;
1702 }
1703};
1704
1705template <unsigned long long __a, unsigned long long __c>
1706struct __lce_ta<__a, __c, 0, (unsigned long long)(~0), false>
1707{
1708 typedef unsigned long long result_type;
1709 static result_type next(result_type __x)
1710 {
1711 return __a * __x + __c;
1712 }
1713};
1714
1715// 32
1716
1717template <unsigned long long _A, unsigned long long _C, unsigned long long _M>
1718struct __lce_ta<_A, _C, _M, unsigned(~0), true>
1719{
1720 typedef unsigned result_type;
1721 static result_type next(result_type __x)
1722 {
1723 const result_type __a = static_cast<result_type>(_A);
1724 const result_type __c = static_cast<result_type>(_C);
1725 const result_type __m = static_cast<result_type>(_M);
1726 // Schrage's algorithm
1727 const result_type __q = __m / __a;
1728 const result_type __r = __m % __a;
1729 const result_type __t0 = __a * (__x % __q);
1730 const result_type __t1 = __r * (__x / __q);
1731 __x = __t0 + (__t0 < __t1) * __m - __t1;
1732 __x += __c - (__x >= __m - __c) * __m;
1733 return __x;
1734 }
1735};
1736
1737template <unsigned long long _A, unsigned long long _M>
1738struct __lce_ta<_A, 0, _M, unsigned(~0), true>
1739{
1740 typedef unsigned result_type;
1741 static result_type next(result_type __x)
1742 {
1743 const result_type __a = static_cast<result_type>(_A);
1744 const result_type __m = static_cast<result_type>(_M);
1745 // Schrage's algorithm
1746 const result_type __q = __m / __a;
1747 const result_type __r = __m % __a;
1748 const result_type __t0 = __a * (__x % __q);
1749 const result_type __t1 = __r * (__x / __q);
1750 __x = __t0 + (__t0 < __t1) * __m - __t1;
1751 return __x;
1752 }
1753};
1754
1755template <unsigned long long _A, unsigned long long _C, unsigned long long _M>
1756struct __lce_ta<_A, _C, _M, unsigned(~0), false>
1757{
1758 typedef unsigned result_type;
1759 static result_type next(result_type __x)
1760 {
1761 const result_type __a = static_cast<result_type>(_A);
1762 const result_type __c = static_cast<result_type>(_C);
1763 const result_type __m = static_cast<result_type>(_M);
1764 return (__a * __x + __c) % __m;
1765 }
1766};
1767
1768template <unsigned long long _A, unsigned long long _C>
1769struct __lce_ta<_A, _C, 0, unsigned(~0), false>
1770{
1771 typedef unsigned result_type;
1772 static result_type next(result_type __x)
1773 {
1774 const result_type __a = static_cast<result_type>(_A);
1775 const result_type __c = static_cast<result_type>(_C);
1776 return __a * __x + __c;
1777 }
1778};
1779
1780// 16
1781
1782template <unsigned long long __a, unsigned long long __c, unsigned long long __m, bool __b>
1783struct __lce_ta<__a, __c, __m, (unsigned short)(~0), __b>
1784{
1785 typedef unsigned short result_type;
1786 static result_type next(result_type __x)
1787 {
1788 return static_cast<result_type>(__lce_ta<__a, __c, __m, unsigned(~0)>::next(__x));
1789 }
1790};
1791
1792template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1793class linear_congruential_engine;
1794
1795template <class _CharT, class _Traits,
1796 class _U, _U _A, _U _C, _U _N>
1797basic_ostream<_CharT, _Traits>&
1798operator<<(basic_ostream<_CharT, _Traits>& __os,
1799 const linear_congruential_engine<_U, _A, _C, _N>&);
1800
1801template <class _CharT, class _Traits,
1802 class _U, _U _A, _U _C, _U _N>
1803basic_istream<_CharT, _Traits>&
1804operator>>(basic_istream<_CharT, _Traits>& __is,
1805 linear_congruential_engine<_U, _A, _C, _N>& __x);
1806
1807template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1808class linear_congruential_engine
1809{
1810public:
1811 // types
1812 typedef _UIntType result_type;
1813
1814private:
1815 result_type __x_;
1816
1817 static const result_type _M = result_type(~0);
1818
1819 static_assert(__m == 0 || __a < __m, "linear_congruential_engine invalid parameters");
1820 static_assert(__m == 0 || __c < __m, "linear_congruential_engine invalid parameters");
1821public:
1822 static const result_type _Min = __c == 0u ? 1u: 0u;
1823 static const result_type _Max = __m - 1u;
1824 static_assert(_Min < _Max, "linear_congruential_engine invalid parameters");
1825
1826 // engine characteristics
1827 static const/*expr*/ result_type multiplier = __a;
1828 static const/*expr*/ result_type increment = __c;
1829 static const/*expr*/ result_type modulus = __m;
1830 static const/*expr*/ result_type min() {return _Min;}
1831 static const/*expr*/ result_type max() {return _Max;}
1832 static const/*expr*/ result_type default_seed = 1u;
1833
1834 // constructors and seeding functions
1835 explicit linear_congruential_engine(result_type __s = default_seed)
1836 {seed(__s);}
1837 template<class _Sseq> explicit linear_congruential_engine(_Sseq& __q)
1838 {seed(__q);}
1839 void seed(result_type __s = default_seed)
1840 {seed(integral_constant<bool, __m == 0>(),
1841 integral_constant<bool, __c == 0>(), __s);}
1842 template<class _Sseq>
1843 typename enable_if
1844 <
1845 !is_convertible<_Sseq, result_type>::value,
1846 void
1847 >::type
1848 seed(_Sseq& __q)
1849 {__seed(__q, integral_constant<unsigned,
1850 1 + (__m == 0 ? (sizeof(result_type) * __CHAR_BIT__ - 1)/32
1851 : (__m-1) / 0x100000000ull)>());}
1852
1853 // generating functions
1854 result_type operator()()
1855 {return __x_ = static_cast<result_type>(__lce_ta<__a, __c, __m, _M>::next(__x_));}
1856 void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
1857
1858 friend bool operator==(const linear_congruential_engine& __x,
1859 const linear_congruential_engine& __y)
1860 {return __x.__x_ == __y.__x_;}
1861 friend bool operator!=(const linear_congruential_engine& __x,
1862 const linear_congruential_engine& __y)
1863 {return !(__x == __y);}
1864
1865private:
1866
1867 void seed(true_type, true_type, result_type __s) {__x_ = __s == 0 ? 1 : __s;}
1868 void seed(true_type, false_type, result_type __s) {__x_ = __s;}
1869 void seed(false_type, true_type, result_type __s) {__x_ = __s % __m == 0 ?
1870 1 : __s % __m;}
1871 void seed(false_type, false_type, result_type __s) {__x_ = __s % __m;}
1872
1873 template<class _Sseq>
1874 void __seed(_Sseq& __q, integral_constant<unsigned, 1>);
1875 template<class _Sseq>
1876 void __seed(_Sseq& __q, integral_constant<unsigned, 2>);
1877
1878 template <class _CharT, class _Traits,
1879 class _U, _U _A, _U _C, _U _N>
1880 friend
1881 basic_ostream<_CharT, _Traits>&
1882 operator<<(basic_ostream<_CharT, _Traits>& __os,
1883 const linear_congruential_engine<_U, _A, _C, _N>&);
1884
1885 template <class _CharT, class _Traits,
1886 class _U, _U _A, _U _C, _U _N>
1887 friend
1888 basic_istream<_CharT, _Traits>&
1889 operator>>(basic_istream<_CharT, _Traits>& __is,
1890 linear_congruential_engine<_U, _A, _C, _N>& __x);
1891};
1892
1893template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1894template<class _Sseq>
1895void
1896linear_congruential_engine<_UIntType, __a, __c, __m>::__seed(_Sseq& __q,
1897 integral_constant<unsigned, 1>)
1898{
1899 const unsigned __k = 1;
1900 uint32_t __ar[__k+3];
1901 __q.generate(__ar, __ar + __k + 3);
1902 result_type __s = static_cast<result_type>(__ar[3] % __m);
1903 __x_ = __c == 0 && __s == 0 ? result_type(1) : __s;
1904}
1905
1906template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1907template<class _Sseq>
1908void
1909linear_congruential_engine<_UIntType, __a, __c, __m>::__seed(_Sseq& __q,
1910 integral_constant<unsigned, 2>)
1911{
1912 const unsigned __k = 2;
1913 uint32_t __ar[__k+3];
1914 __q.generate(__ar, __ar + __k + 3);
1915 result_type __s = static_cast<result_type>((__ar[3] +
1916 (uint64_t)__ar[4] << 32) % __m);
1917 __x_ = __c == 0 && __s == 0 ? result_type(1) : __s;
1918}
1919
1920template <class _CharT, class _Traits>
1921class __save_flags
1922{
1923 typedef basic_ios<_CharT, _Traits> __stream_type;
1924 typedef typename __stream_type::fmtflags fmtflags;
1925
1926 __stream_type& __stream_;
1927 fmtflags __fmtflags_;
1928 _CharT __fill_;
1929
1930 __save_flags(const __save_flags&);
1931 __save_flags& operator=(const __save_flags&);
1932public:
1933 explicit __save_flags(__stream_type& __stream)
1934 : __stream_(__stream),
1935 __fmtflags_(__stream.flags()),
1936 __fill_(__stream.fill())
1937 {}
1938 ~__save_flags()
1939 {
1940 __stream_.flags(__fmtflags_);
1941 __stream_.fill(__fill_);
1942 }
1943};
1944
1945template <class _CharT, class _Traits,
1946 class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1947inline
1948basic_ostream<_CharT, _Traits>&
1949operator<<(basic_ostream<_CharT, _Traits>& __os,
1950 const linear_congruential_engine<_UIntType, __a, __c, __m>& __x)
1951{
1952 __save_flags<_CharT, _Traits> _(__os);
1953 __os.flags(ios_base::dec | ios_base::left);
1954 __os.fill(__os.widen(' '));
1955 return __os << __x.__x_;
1956}
1957
1958template <class _CharT, class _Traits,
1959 class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1960basic_istream<_CharT, _Traits>&
1961operator>>(basic_istream<_CharT, _Traits>& __is,
1962 linear_congruential_engine<_UIntType, __a, __c, __m>& __x)
1963{
1964 __save_flags<_CharT, _Traits> _(__is);
1965 __is.flags(ios_base::dec | ios_base::skipws);
1966 _UIntType __t;
1967 __is >> __t;
1968 if (!__is.fail())
1969 __x.__x_ = __t;
1970 return __is;
1971}
1972
1973typedef linear_congruential_engine<uint_fast32_t, 16807, 0, 2147483647>
1974 minstd_rand0;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]1975typedef linear_congruential_engine<uint_fast32_t, 48271, 0, 2147483647>
1976 minstd_rand;
Howard Hinnantd6d11712010-05-20 15:11:46 +0000[diff] [blame]1977typedef minstd_rand default_random_engine;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]1978// mersenne_twister_engine
1979
1980template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
1981 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
1982 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
1983class mersenne_twister_engine;
1984
1985template <class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
1986 _UI _A, size_t _U, _UI _D, size_t _S,
1987 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
1988bool
1989operator==(const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1990 _B, _T, _C, _L, _F>& __x,
1991 const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1992 _B, _T, _C, _L, _F>& __y);
1993
1994template <class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
1995 _UI _A, size_t _U, _UI _D, size_t _S,
1996 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
1997bool
1998operator!=(const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1999 _B, _T, _C, _L, _F>& __x,
2000 const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
2001 _B, _T, _C, _L, _F>& __y);
2002
2003template <class _CharT, class _Traits,
2004 class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
2005 _UI _A, size_t _U, _UI _D, size_t _S,
2006 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
2007basic_ostream<_CharT, _Traits>&
2008operator<<(basic_ostream<_CharT, _Traits>& __os,
2009 const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
2010 _B, _T, _C, _L, _F>& __x);
2011
2012template <class _CharT, class _Traits,
2013 class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
2014 _UI _A, size_t _U, _UI _D, size_t _S,
2015 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
2016basic_istream<_CharT, _Traits>&
2017operator>>(basic_istream<_CharT, _Traits>& __is,
2018 mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
2019 _B, _T, _C, _L, _F>& __x);
2020
2021template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2022 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2023 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2024class mersenne_twister_engine
2025{
2026public:
2027 // types
2028 typedef _UIntType result_type;
2029
2030private:
2031 result_type __x_[__n];
2032 size_t __i_;
2033
2034 static_assert( 0 < __m, "mersenne_twister_engine invalid parameters");
2035 static_assert(__m <= __n, "mersenne_twister_engine invalid parameters");
2036 static const result_type _Dt = numeric_limits<result_type>::digits;
2037 static_assert(__w <= _Dt, "mersenne_twister_engine invalid parameters");
2038 static_assert( 2 <= __w, "mersenne_twister_engine invalid parameters");
2039 static_assert(__r <= __w, "mersenne_twister_engine invalid parameters");
2040 static_assert(__u <= __w, "mersenne_twister_engine invalid parameters");
2041 static_assert(__s <= __w, "mersenne_twister_engine invalid parameters");
2042 static_assert(__t <= __w, "mersenne_twister_engine invalid parameters");
2043 static_assert(__l <= __w, "mersenne_twister_engine invalid parameters");
2044public:
2045 static const result_type _Min = 0;
2046 static const result_type _Max = __w == _Dt ? result_type(~0) :
2047 (result_type(1) << __w) - result_type(1);
2048 static_assert(_Min < _Max, "mersenne_twister_engine invalid parameters");
2049 static_assert(__a <= _Max, "mersenne_twister_engine invalid parameters");
2050 static_assert(__b <= _Max, "mersenne_twister_engine invalid parameters");
2051 static_assert(__c <= _Max, "mersenne_twister_engine invalid parameters");
2052 static_assert(__d <= _Max, "mersenne_twister_engine invalid parameters");
2053 static_assert(__f <= _Max, "mersenne_twister_engine invalid parameters");
2054
2055 // engine characteristics
2056 static const/*expr*/ size_t word_size = __w;
2057 static const/*expr*/ size_t state_size = __n;
2058 static const/*expr*/ size_t shift_size = __m;
2059 static const/*expr*/ size_t mask_bits = __r;
2060 static const/*expr*/ result_type xor_mask = __a;
2061 static const/*expr*/ size_t tempering_u = __u;
2062 static const/*expr*/ result_type tempering_d = __d;
2063 static const/*expr*/ size_t tempering_s = __s;
2064 static const/*expr*/ result_type tempering_b = __b;
2065 static const/*expr*/ size_t tempering_t = __t;
2066 static const/*expr*/ result_type tempering_c = __c;
2067 static const/*expr*/ size_t tempering_l = __l;
2068 static const/*expr*/ result_type initialization_multiplier = __f;
2069 static const/*expr*/ result_type min() { return _Min; }
2070 static const/*expr*/ result_type max() { return _Max; }
2071 static const/*expr*/ result_type default_seed = 5489u;
2072
2073 // constructors and seeding functions
2074 explicit mersenne_twister_engine(result_type __sd = default_seed)
2075 {seed(__sd);}
2076 template<class _Sseq> explicit mersenne_twister_engine(_Sseq& __q)
2077 {seed(__q);}
2078 void seed(result_type __sd = default_seed);
2079 template<class _Sseq>
2080 typename enable_if
2081 <
2082 !is_convertible<_Sseq, result_type>::value,
2083 void
2084 >::type
2085 seed(_Sseq& __q)
2086 {__seed(__q, integral_constant<unsigned, 1 + (__w - 1) / 32>());}
2087
2088 // generating functions
2089 result_type operator()();
2090 void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
2091
2092 template <class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
2093 _UI _A, size_t _U, _UI _D, size_t _S,
2094 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
2095 friend
2096 bool
2097 operator==(const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
2098 _B, _T, _C, _L, _F>& __x,
2099 const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
2100 _B, _T, _C, _L, _F>& __y);
2101
2102 template <class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
2103 _UI _A, size_t _U, _UI _D, size_t _S,
2104 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
2105 friend
2106 bool
2107 operator!=(const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
2108 _B, _T, _C, _L, _F>& __x,
2109 const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
2110 _B, _T, _C, _L, _F>& __y);
2111
2112 template <class _CharT, class _Traits,
2113 class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
2114 _UI _A, size_t _U, _UI _D, size_t _S,
2115 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
2116 friend
2117 basic_ostream<_CharT, _Traits>&
2118 operator<<(basic_ostream<_CharT, _Traits>& __os,
2119 const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
2120 _B, _T, _C, _L, _F>& __x);
2121
2122 template <class _CharT, class _Traits,
2123 class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
2124 _UI _A, size_t _U, _UI _D, size_t _S,
2125 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
2126 friend
2127 basic_istream<_CharT, _Traits>&
2128 operator>>(basic_istream<_CharT, _Traits>& __is,
2129 mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
2130 _B, _T, _C, _L, _F>& __x);
2131private:
2132
2133 template<class _Sseq>
2134 void __seed(_Sseq& __q, integral_constant<unsigned, 1>);
2135 template<class _Sseq>
2136 void __seed(_Sseq& __q, integral_constant<unsigned, 2>);
2137
2138 template <size_t __count>
2139 static
2140 typename enable_if
2141 <
2142 __count < __w,
2143 result_type
2144 >::type
2145 __lshift(result_type __x) {return (__x << __count) & _Max;}
2146
2147 template <size_t __count>
2148 static
2149 typename enable_if
2150 <
2151 (__count >= __w),
2152 result_type
2153 >::type
2154 __lshift(result_type __x) {return result_type(0);}
2155
2156 template <size_t __count>
2157 static
2158 typename enable_if
2159 <
2160 __count < _Dt,
2161 result_type
2162 >::type
2163 __rshift(result_type __x) {return __x >> __count;}
2164
2165 template <size_t __count>
2166 static
2167 typename enable_if
2168 <
2169 (__count >= _Dt),
2170 result_type
2171 >::type
2172 __rshift(result_type __x) {return result_type(0);}
2173};
2174
2175template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2176 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2177 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2178void
2179mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b,
2180 __t, __c, __l, __f>::seed(result_type __sd)
2181{ // __w >= 2
2182 __x_[0] = __sd & _Max;
2183 for (size_t __i = 1; __i < __n; ++__i)
2184 __x_[__i] = (__f * (__x_[__i-1] ^ __rshift<__w - 2>(__x_[__i-1])) + __i) & _Max;
2185 __i_ = 0;
2186}
2187
2188template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2189 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2190 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2191template<class _Sseq>
2192void
2193mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b,
2194 __t, __c, __l, __f>::__seed(_Sseq& __q, integral_constant<unsigned, 1>)
2195{
2196 const unsigned __k = 1;
2197 uint32_t __ar[__n * __k];
2198 __q.generate(__ar, __ar + __n * __k);
2199 for (size_t __i = 0; __i < __n; ++__i)
2200 __x_[__i] = static_cast<result_type>(__ar[__i] & _Max);
2201 const result_type __mask = __r == _Dt ? result_type(~0) :
2202 (result_type(1) << __r) - result_type(1);
2203 __i_ = 0;
2204 if ((__x_[0] & ~__mask) == 0)
2205 {
2206 for (size_t __i = 1; __i < __n; ++__i)
2207 if (__x_[__i] != 0)
2208 return;
2209 __x_[0] = _Max;
2210 }
2211}
2212
2213template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2214 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2215 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2216template<class _Sseq>
2217void
2218mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b,
2219 __t, __c, __l, __f>::__seed(_Sseq& __q, integral_constant<unsigned, 2>)
2220{
2221 const unsigned __k = 2;
2222 uint32_t __ar[__n * __k];
2223 __q.generate(__ar, __ar + __n * __k);
2224 for (size_t __i = 0; __i < __n; ++__i)
2225 __x_[__i] = static_cast<result_type>(
2226 (__ar[2 * __i] + ((uint64_t)__ar[2 * __i + 1] << 32)) & _Max);
2227 const result_type __mask = __r == _Dt ? result_type(~0) :
2228 (result_type(1) << __r) - result_type(1);
2229 __i_ = 0;
2230 if ((__x_[0] & ~__mask) == 0)
2231 {
2232 for (size_t __i = 1; __i < __n; ++__i)
2233 if (__x_[__i] != 0)
2234 return;
2235 __x_[0] = _Max;
2236 }
2237}
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_UIntType
2243mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b,
2244 __t, __c, __l, __f>::operator()()
2245{
2246 const size_t __j = (__i_ + 1) % __n;
2247 const result_type __mask = __r == _Dt ? result_type(~0) :
2248 (result_type(1) << __r) - result_type(1);
2249 const result_type _Y = (__x_[__i_] & ~__mask) | (__x_[__j] & __mask);
2250 const size_t __k = (__i_ + __m) % __n;
2251 __x_[__i_] = __x_[__k] ^ __rshift<1>(_Y) ^ (__a * (_Y & 1));
2252 result_type __z = __x_[__i_] ^ (__rshift<__u>(__x_[__i_]) & __d);
2253 __i_ = __j;
2254 __z ^= __lshift<__s>(__z) & __b;
2255 __z ^= __lshift<__t>(__z) & __c;
2256 return __z ^ __rshift<__l>(__z);
2257}
2258
2259template <class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
2260 _UI _A, size_t _U, _UI _D, size_t _S,
2261 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
2262bool
2263operator==(const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
2264 _B, _T, _C, _L, _F>& __x,
2265 const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
2266 _B, _T, _C, _L, _F>& __y)
2267{
2268 if (__x.__i_ == __y.__i_)
2269 return _STD::equal(__x.__x_, __x.__x_ + _N, __y.__x_);
2270 if (__x.__i_ == 0 || __y.__i_ == 0)
2271 {
2272 size_t __j = _STD::min(_N - __x.__i_, _N - __y.__i_);
2273 if (!_STD::equal(__x.__x_ + __x.__i_, __x.__x_ + __x.__i_ + __j,
2274 __y.__x_ + __y.__i_))
2275 return false;
2276 if (__x.__i_ == 0)
2277 return _STD::equal(__x.__x_ + __j, __x.__x_ + _N, __y.__x_);
2278 return _STD::equal(__x.__x_, __x.__x_ + (_N - __j), __y.__x_ + __j);
2279 }
2280 if (__x.__i_ < __y.__i_)
2281 {
2282 size_t __j = _N - __y.__i_;
2283 if (!_STD::equal(__x.__x_ + __x.__i_, __x.__x_ + (__x.__i_ + __j),
2284 __y.__x_ + __y.__i_))
2285 return false;
2286 if (!_STD::equal(__x.__x_ + (__x.__i_ + __j), __x.__x_ + _N,
2287 __y.__x_))
2288 return false;
2289 return _STD::equal(__x.__x_, __x.__x_ + __x.__i_,
2290 __y.__x_ + (_N - (__x.__i_ + __j)));
2291 }
2292 size_t __j = _N - __x.__i_;
2293 if (!_STD::equal(__y.__x_ + __y.__i_, __y.__x_ + (__y.__i_ + __j),
2294 __x.__x_ + __x.__i_))
2295 return false;
2296 if (!_STD::equal(__y.__x_ + (__y.__i_ + __j), __y.__x_ + _N,
2297 __x.__x_))
2298 return false;
2299 return _STD::equal(__y.__x_, __y.__x_ + __y.__i_,
2300 __x.__x_ + (_N - (__y.__i_ + __j)));
2301}
2302
2303template <class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
2304 _UI _A, size_t _U, _UI _D, size_t _S,
2305 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
2306inline
2307bool
2308operator!=(const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
2309 _B, _T, _C, _L, _F>& __x,
2310 const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
2311 _B, _T, _C, _L, _F>& __y)
2312{
2313 return !(__x == __y);
2314}
2315
2316template <class _CharT, class _Traits,
2317 class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
2318 _UI _A, size_t _U, _UI _D, size_t _S,
2319 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
2320basic_ostream<_CharT, _Traits>&
2321operator<<(basic_ostream<_CharT, _Traits>& __os,
2322 const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
2323 _B, _T, _C, _L, _F>& __x)
2324{
2325 __save_flags<_CharT, _Traits> _(__os);
2326 __os.flags(ios_base::dec | ios_base::left);
2327 _CharT __sp = __os.widen(' ');
2328 __os.fill(__sp);
2329 __os << __x.__x_[__x.__i_];
2330 for (size_t __j = __x.__i_ + 1; __j < _N; ++__j)
2331 __os << __sp << __x.__x_[__j];
2332 for (size_t __j = 0; __j < __x.__i_; ++__j)
2333 __os << __sp << __x.__x_[__j];
2334 return __os;
2335}
2336
2337template <class _CharT, class _Traits,
2338 class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
2339 _UI _A, size_t _U, _UI _D, size_t _S,
2340 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
2341basic_istream<_CharT, _Traits>&
2342operator>>(basic_istream<_CharT, _Traits>& __is,
2343 mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
2344 _B, _T, _C, _L, _F>& __x)
2345{
2346 __save_flags<_CharT, _Traits> _(__is);
2347 __is.flags(ios_base::dec | ios_base::skipws);
2348 _UI __t[_N];
2349 for (size_t __i = 0; __i < _N; ++__i)
2350 __is >> __t[__i];
2351 if (!__is.fail())
2352 {
2353 for (size_t __i = 0; __i < _N; ++__i)
2354 __x.__x_[__i] = __t[__i];
2355 __x.__i_ = 0;
2356 }
2357 return __is;
2358}
2359
2360typedef mersenne_twister_engine<uint_fast32_t, 32, 624, 397, 31,
2361 0x9908b0df, 11, 0xffffffff,
2362 7, 0x9d2c5680,
2363 15, 0xefc60000,
2364 18, 1812433253> mt19937;
2365typedef mersenne_twister_engine<uint_fast64_t, 64, 312, 156, 31,
2366 0xb5026f5aa96619e9ULL, 29, 0x5555555555555555ULL,
2367 17, 0x71d67fffeda60000ULL,
2368 37, 0xfff7eee000000000ULL,
2369 43, 6364136223846793005ULL> mt19937_64;
2370
2371// subtract_with_carry_engine
2372
2373template<class _UIntType, size_t __w, size_t __s, size_t __r>
2374class subtract_with_carry_engine;
2375
2376template<class _UI, size_t _W, size_t _S, size_t _R>
2377bool
2378operator==(
2379 const subtract_with_carry_engine<_UI, _W, _S, _R>& __x,
2380 const subtract_with_carry_engine<_UI, _W, _S, _R>& __y);
2381
2382template<class _UI, size_t _W, size_t _S, size_t _R>
2383bool
2384operator!=(
2385 const subtract_with_carry_engine<_UI, _W, _S, _R>& __x,
2386 const subtract_with_carry_engine<_UI, _W, _S, _R>& __y);
2387
2388template <class _CharT, class _Traits,
2389 class _UI, size_t _W, size_t _S, size_t _R>
2390basic_ostream<_CharT, _Traits>&
2391operator<<(basic_ostream<_CharT, _Traits>& __os,
2392 const subtract_with_carry_engine<_UI, _W, _S, _R>& __x);
2393
2394template <class _CharT, class _Traits,
2395 class _UI, size_t _W, size_t _S, size_t _R>
2396basic_istream<_CharT, _Traits>&
2397operator>>(basic_istream<_CharT, _Traits>& __is,
2398 subtract_with_carry_engine<_UI, _W, _S, _R>& __x);
2399
2400template<class _UIntType, size_t __w, size_t __s, size_t __r>
2401class subtract_with_carry_engine
2402{
2403public:
2404 // types
2405 typedef _UIntType result_type;
2406
2407private:
2408 result_type __x_[__r];
2409 result_type __c_;
2410 size_t __i_;
2411
2412 static const result_type _Dt = numeric_limits<result_type>::digits;
2413 static_assert( 0 < __w, "subtract_with_carry_engine invalid parameters");
2414 static_assert(__w <= _Dt, "subtract_with_carry_engine invalid parameters");
2415 static_assert( 0 < __s, "subtract_with_carry_engine invalid parameters");
2416 static_assert(__s < __r, "subtract_with_carry_engine invalid parameters");
2417public:
2418 static const result_type _Min = 0;
2419 static const result_type _Max = __w == _Dt ? result_type(~0) :
2420 (result_type(1) << __w) - result_type(1);
2421 static_assert(_Min < _Max, "subtract_with_carry_engine invalid parameters");
2422
2423 // engine characteristics
2424 static const/*expr*/ size_t word_size = __w;
2425 static const/*expr*/ size_t short_lag = __s;
2426 static const/*expr*/ size_t long_lag = __r;
2427 static const/*expr*/ result_type min() { return _Min; }
2428 static const/*expr*/ result_type max() { return _Max; }
2429 static const/*expr*/ result_type default_seed = 19780503u;
2430
2431 // constructors and seeding functions
2432 explicit subtract_with_carry_engine(result_type __sd = default_seed)
2433 {seed(__sd);}
2434 template<class _Sseq> explicit subtract_with_carry_engine(_Sseq& __q)
2435 {seed(__q);}
2436 void seed(result_type __sd = default_seed)
2437 {seed(__sd, integral_constant<unsigned, 1 + (__w - 1) / 32>());}
2438 template<class _Sseq>
2439 typename enable_if
2440 <
2441 !is_convertible<_Sseq, result_type>::value,
2442 void
2443 >::type
2444 seed(_Sseq& __q)
2445 {__seed(__q, integral_constant<unsigned, 1 + (__w - 1) / 32>());}
2446
2447 // generating functions
2448 result_type operator()();
2449 void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
2450
2451 template<class _UI, size_t _W, size_t _S, size_t _R>
2452 friend
2453 bool
2454 operator==(
2455 const subtract_with_carry_engine<_UI, _W, _S, _R>& __x,
2456 const subtract_with_carry_engine<_UI, _W, _S, _R>& __y);
2457
2458 template<class _UI, size_t _W, size_t _S, size_t _R>
2459 friend
2460 bool
2461 operator!=(
2462 const subtract_with_carry_engine<_UI, _W, _S, _R>& __x,
2463 const subtract_with_carry_engine<_UI, _W, _S, _R>& __y);
2464
2465 template <class _CharT, class _Traits,
2466 class _UI, size_t _W, size_t _S, size_t _R>
2467 friend
2468 basic_ostream<_CharT, _Traits>&
2469 operator<<(basic_ostream<_CharT, _Traits>& __os,
2470 const subtract_with_carry_engine<_UI, _W, _S, _R>& __x);
2471
2472 template <class _CharT, class _Traits,
2473 class _UI, size_t _W, size_t _S, size_t _R>
2474 friend
2475 basic_istream<_CharT, _Traits>&
2476 operator>>(basic_istream<_CharT, _Traits>& __is,
2477 subtract_with_carry_engine<_UI, _W, _S, _R>& __x);
2478
2479private:
2480
2481 void seed(result_type __sd, integral_constant<unsigned, 1>);
2482 void seed(result_type __sd, integral_constant<unsigned, 2>);
2483 template<class _Sseq>
2484 void __seed(_Sseq& __q, integral_constant<unsigned, 1>);
2485 template<class _Sseq>
2486 void __seed(_Sseq& __q, integral_constant<unsigned, 2>);
2487};
2488
2489template<class _UIntType, size_t __w, size_t __s, size_t __r>
2490void
2491subtract_with_carry_engine<_UIntType, __w, __s, __r>::seed(result_type __sd,
2492 integral_constant<unsigned, 1>)
2493{
2494 linear_congruential_engine<result_type, 40014u, 0u, 2147483563u>
2495 __e(__sd == 0u ? default_seed : __sd);
2496 for (size_t __i = 0; __i < __r; ++__i)
2497 __x_[__i] = static_cast<result_type>(__e() & _Max);
2498 __c_ = __x_[__r-1] == 0;
2499 __i_ = 0;
2500}
2501
2502template<class _UIntType, size_t __w, size_t __s, size_t __r>
2503void
2504subtract_with_carry_engine<_UIntType, __w, __s, __r>::seed(result_type __sd,
2505 integral_constant<unsigned, 2>)
2506{
2507 linear_congruential_engine<result_type, 40014u, 0u, 2147483563u>
2508 __e(__sd == 0u ? default_seed : __sd);
2509 for (size_t __i = 0; __i < __r; ++__i)
2510 __x_[__i] = static_cast<result_type>(
2511 (__e() + ((uint64_t)__e() << 32)) & _Max);
2512 __c_ = __x_[__r-1] == 0;
2513 __i_ = 0;
2514}
2515
2516template<class _UIntType, size_t __w, size_t __s, size_t __r>
2517template<class _Sseq>
2518void
2519subtract_with_carry_engine<_UIntType, __w, __s, __r>::__seed(_Sseq& __q,
2520 integral_constant<unsigned, 1>)
2521{
2522 const unsigned __k = 1;
2523 uint32_t __ar[__r * __k];
2524 __q.generate(__ar, __ar + __r * __k);
2525 for (size_t __i = 0; __i < __r; ++__i)
2526 __x_[__i] = static_cast<result_type>(__ar[__i] & _Max);
2527 __c_ = __x_[__r-1] == 0;
2528 __i_ = 0;
2529}
2530
2531template<class _UIntType, size_t __w, size_t __s, size_t __r>
2532template<class _Sseq>
2533void
2534subtract_with_carry_engine<_UIntType, __w, __s, __r>::__seed(_Sseq& __q,
2535 integral_constant<unsigned, 2>)
2536{
2537 const unsigned __k = 2;
2538 uint32_t __ar[__r * __k];
2539 __q.generate(__ar, __ar + __r * __k);
2540 for (size_t __i = 0; __i < __r; ++__i)
2541 __x_[__i] = static_cast<result_type>(
2542 (__ar[2 * __i] + ((uint64_t)__ar[2 * __i + 1] << 32)) & _Max);
2543 __c_ = __x_[__r-1] == 0;
2544 __i_ = 0;
2545}
2546
2547template<class _UIntType, size_t __w, size_t __s, size_t __r>
2548_UIntType
2549subtract_with_carry_engine<_UIntType, __w, __s, __r>::operator()()
2550{
2551 const result_type& __xs = __x_[(__i_ + (__r - __s)) % __r];
2552 result_type& __xr = __x_[__i_];
2553 result_type __new_c = __c_ == 0 ? __xs < __xr : __xs != 0 ? __xs <= __xr : 1;
2554 __xr = (__xs - __xr - __c_) & _Max;
2555 __c_ = __new_c;
2556 __i_ = (__i_ + 1) % __r;
2557 return __xr;
2558}
2559
2560template<class _UI, size_t _W, size_t _S, size_t _R>
2561bool
2562operator==(
2563 const subtract_with_carry_engine<_UI, _W, _S, _R>& __x,
2564 const subtract_with_carry_engine<_UI, _W, _S, _R>& __y)
2565{
2566 if (__x.__c_ != __y.__c_)
2567 return false;
2568 if (__x.__i_ == __y.__i_)
2569 return _STD::equal(__x.__x_, __x.__x_ + _R, __y.__x_);
2570 if (__x.__i_ == 0 || __y.__i_ == 0)
2571 {
2572 size_t __j = _STD::min(_R - __x.__i_, _R - __y.__i_);
2573 if (!_STD::equal(__x.__x_ + __x.__i_, __x.__x_ + __x.__i_ + __j,
2574 __y.__x_ + __y.__i_))
2575 return false;
2576 if (__x.__i_ == 0)
2577 return _STD::equal(__x.__x_ + __j, __x.__x_ + _R, __y.__x_);
2578 return _STD::equal(__x.__x_, __x.__x_ + (_R - __j), __y.__x_ + __j);
2579 }
2580 if (__x.__i_ < __y.__i_)
2581 {
2582 size_t __j = _R - __y.__i_;
2583 if (!_STD::equal(__x.__x_ + __x.__i_, __x.__x_ + (__x.__i_ + __j),
2584 __y.__x_ + __y.__i_))
2585 return false;
2586 if (!_STD::equal(__x.__x_ + (__x.__i_ + __j), __x.__x_ + _R,
2587 __y.__x_))
2588 return false;
2589 return _STD::equal(__x.__x_, __x.__x_ + __x.__i_,
2590 __y.__x_ + (_R - (__x.__i_ + __j)));
2591 }
2592 size_t __j = _R - __x.__i_;
2593 if (!_STD::equal(__y.__x_ + __y.__i_, __y.__x_ + (__y.__i_ + __j),
2594 __x.__x_ + __x.__i_))
2595 return false;
2596 if (!_STD::equal(__y.__x_ + (__y.__i_ + __j), __y.__x_ + _R,
2597 __x.__x_))
2598 return false;
2599 return _STD::equal(__y.__x_, __y.__x_ + __y.__i_,
2600 __x.__x_ + (_R - (__y.__i_ + __j)));
2601}
2602
2603template<class _UI, size_t _W, size_t _S, size_t _R>
2604inline
2605bool
2606operator!=(
2607 const subtract_with_carry_engine<_UI, _W, _S, _R>& __x,
2608 const subtract_with_carry_engine<_UI, _W, _S, _R>& __y)
2609{
2610 return !(__x == __y);
2611}
2612
2613template <class _CharT, class _Traits,
2614 class _UI, size_t _W, size_t _S, size_t _R>
2615basic_ostream<_CharT, _Traits>&
2616operator<<(basic_ostream<_CharT, _Traits>& __os,
2617 const subtract_with_carry_engine<_UI, _W, _S, _R>& __x)
2618{
2619 __save_flags<_CharT, _Traits> _(__os);
2620 __os.flags(ios_base::dec | ios_base::left);
2621 _CharT __sp = __os.widen(' ');
2622 __os.fill(__sp);
2623 __os << __x.__x_[__x.__i_];
2624 for (size_t __j = __x.__i_ + 1; __j < _R; ++__j)
2625 __os << __sp << __x.__x_[__j];
2626 for (size_t __j = 0; __j < __x.__i_; ++__j)
2627 __os << __sp << __x.__x_[__j];
2628 __os << __sp << __x.__c_;
2629 return __os;
2630}
2631
2632template <class _CharT, class _Traits,
2633 class _UI, size_t _W, size_t _S, size_t _R>
2634basic_istream<_CharT, _Traits>&
2635operator>>(basic_istream<_CharT, _Traits>& __is,
2636 subtract_with_carry_engine<_UI, _W, _S, _R>& __x)
2637{
2638 __save_flags<_CharT, _Traits> _(__is);
2639 __is.flags(ios_base::dec | ios_base::skipws);
2640 _UI __t[_R+1];
2641 for (size_t __i = 0; __i < _R+1; ++__i)
2642 __is >> __t[__i];
2643 if (!__is.fail())
2644 {
2645 for (size_t __i = 0; __i < _R; ++__i)
2646 __x.__x_[__i] = __t[__i];
2647 __x.__c_ = __t[_R];
2648 __x.__i_ = 0;
2649 }
2650 return __is;
2651}
2652
2653typedef subtract_with_carry_engine<uint_fast32_t, 24, 10, 24> ranlux24_base;
2654typedef subtract_with_carry_engine<uint_fast64_t, 48, 5, 12> ranlux48_base;
2655
2656// discard_block_engine
2657
2658template<class _Engine, size_t __p, size_t __r>
2659class discard_block_engine
2660{
2661 _Engine __e_;
2662 int __n_;
2663
2664 static_assert( 0 < __r, "discard_block_engine invalid parameters");
2665 static_assert(__r <= __p, "discard_block_engine invalid parameters");
2666public:
2667 // types
2668 typedef typename _Engine::result_type result_type;
2669
2670 // engine characteristics
2671 static const/*expr*/ size_t block_size = __p;
2672 static const/*expr*/ size_t used_block = __r;
2673
2674 // Temporary work around for lack of constexpr
2675 static const result_type _Min = _Engine::_Min;
2676 static const result_type _Max = _Engine::_Max;
2677
2678 static const/*expr*/ result_type min() { return _Engine::min(); }
2679 static const/*expr*/ result_type max() { return _Engine::max(); }
2680
2681 // constructors and seeding functions
2682 discard_block_engine() : __n_(0) {}
2683// explicit discard_block_engine(const _Engine& __e);
2684// explicit discard_block_engine(_Engine&& __e);
2685 explicit discard_block_engine(result_type __sd) : __e_(__sd), __n_(0) {}
2686 template<class _Sseq> explicit discard_block_engine(_Sseq& __q)
2687 : __e_(__q), __n_(0) {}
2688 void seed() {__e_.seed(); __n_ = 0;}
2689 void seed(result_type __sd) {__e_.seed(__sd); __n_ = 0;}
2690 template<class _Sseq> void seed(_Sseq& __q) {__e_.seed(__q); __n_ = 0;}
2691
2692 // generating functions
2693 result_type operator()();
2694 void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
2695
2696 // property functions
2697 const _Engine& base() const {return __e_;}
2698
2699 template<class _Eng, size_t _P, size_t _R>
2700 friend
2701 bool
2702 operator==(
2703 const discard_block_engine<_Eng, _P, _R>& __x,
2704 const discard_block_engine<_Eng, _P, _R>& __y);
2705
2706 template<class _Eng, size_t _P, size_t _R>
2707 friend
2708 bool
2709 operator!=(
2710 const discard_block_engine<_Eng, _P, _R>& __x,
2711 const discard_block_engine<_Eng, _P, _R>& __y);
2712
2713 template <class _CharT, class _Traits,
2714 class _Eng, size_t _P, size_t _R>
2715 friend
2716 basic_ostream<_CharT, _Traits>&
2717 operator<<(basic_ostream<_CharT, _Traits>& __os,
2718 const discard_block_engine<_Eng, _P, _R>& __x);
2719
2720 template <class _CharT, class _Traits,
2721 class _Eng, size_t _P, size_t _R>
2722 friend
2723 basic_istream<_CharT, _Traits>&
2724 operator>>(basic_istream<_CharT, _Traits>& __is,
2725 discard_block_engine<_Eng, _P, _R>& __x);
2726};
2727
2728template<class _Engine, size_t __p, size_t __r>
2729typename discard_block_engine<_Engine, __p, __r>::result_type
2730discard_block_engine<_Engine, __p, __r>::operator()()
2731{
2732 if (__n_ >= __r)
2733 {
2734 __e_.discard(__p - __r);
2735 __n_ = 0;
2736 }
2737 ++__n_;
2738 return __e_();
2739}
2740
2741template<class _Eng, size_t _P, size_t _R>
2742inline
2743bool
2744operator==(const discard_block_engine<_Eng, _P, _R>& __x,
2745 const discard_block_engine<_Eng, _P, _R>& __y)
2746{
2747 return __x.__n_ == __y.__n_ && __x.__e_ == __y.__e_;
2748}
2749
2750template<class _Eng, size_t _P, size_t _R>
2751inline
2752bool
2753operator!=(const discard_block_engine<_Eng, _P, _R>& __x,
2754 const discard_block_engine<_Eng, _P, _R>& __y)
2755{
2756 return !(__x == __y);
2757}
2758
2759template <class _CharT, class _Traits,
2760 class _Eng, size_t _P, size_t _R>
2761basic_ostream<_CharT, _Traits>&
2762operator<<(basic_ostream<_CharT, _Traits>& __os,
2763 const discard_block_engine<_Eng, _P, _R>& __x)
2764{
2765 __save_flags<_CharT, _Traits> _(__os);
2766 __os.flags(ios_base::dec | ios_base::left);
2767 _CharT __sp = __os.widen(' ');
2768 __os.fill(__sp);
2769 return __os << __x.__e_ << __sp << __x.__n_;
2770}
2771
2772template <class _CharT, class _Traits,
2773 class _Eng, size_t _P, size_t _R>
2774basic_istream<_CharT, _Traits>&
2775operator>>(basic_istream<_CharT, _Traits>& __is,
2776 discard_block_engine<_Eng, _P, _R>& __x)
2777{
2778 __save_flags<_CharT, _Traits> _(__is);
2779 __is.flags(ios_base::dec | ios_base::skipws);
2780 _Eng __e;
2781 int __n;
2782 __is >> __e >> __n;
2783 if (!__is.fail())
2784 {
2785 __x.__e_ = __e;
2786 __x.__n_ = __n;
2787 }
2788 return __is;
2789}
2790
2791typedef discard_block_engine<ranlux24_base, 223, 23> ranlux24;
2792typedef discard_block_engine<ranlux48_base, 389, 11> ranlux48;
2793
2794// independent_bits_engine
2795
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]2796template<class _Engine, size_t __w, class _UIntType>
2797class independent_bits_engine
2798{
2799 template <class _UI, _UI _R0, size_t _W, size_t _M>
2800 class __get_n
2801 {
2802 static const size_t _Dt = numeric_limits<_UI>::digits;
2803 static const size_t _N = _W / _M + (_W % _M != 0);
2804 static const size_t _W0 = _W / _N;
2805 static const _UI _Y0 = _W0 >= _Dt ? 0 : (_R0 >> _W0) << _W0;
2806 public:
2807 static const size_t value = _R0 - _Y0 > _Y0 / _N ? _N + 1 : _N;
2808 };
2809public:
2810 // types
2811 typedef _UIntType result_type;
2812
2813private:
2814 _Engine __e_;
2815
2816 static const result_type _Dt = numeric_limits<result_type>::digits;
2817 static_assert( 0 < __w, "independent_bits_engine invalid parameters");
2818 static_assert(__w <= _Dt, "independent_bits_engine invalid parameters");
2819
2820 typedef typename _Engine::result_type _Engine_result_type;
2821 typedef typename conditional
2822 <
2823 sizeof(_Engine_result_type) <= sizeof(result_type),
2824 result_type,
2825 _Engine_result_type
2826 >::type _Working_result_type;
2827 // Temporary work around for lack of constexpr
2828 static const _Working_result_type _R = _Engine::_Max - _Engine::_Min
2829 + _Working_result_type(1);
2830 static const size_t __m = __log2<_Working_result_type, _R>::value;
2831 static const size_t __n = __get_n<_Working_result_type, _R, __w, __m>::value;
2832 static const size_t __w0 = __w / __n;
2833 static const size_t __n0 = __n - __w % __n;
2834 static const size_t _WDt = numeric_limits<_Working_result_type>::digits;
2835 static const size_t _EDt = numeric_limits<_Engine_result_type>::digits;
2836 static const _Working_result_type __y0 = __w0 >= _WDt ? 0 :
2837 (_R >> __w0) << __w0;
2838 static const _Working_result_type __y1 = __w0 >= _WDt - 1 ? 0 :
2839 (_R >> (__w0+1)) << (__w0+1);
2840 static const _Engine_result_type __mask0 = __w0 > 0 ?
2841 _Engine_result_type(~0) >> (_EDt - __w0) :
2842 _Engine_result_type(0);
2843 static const _Engine_result_type __mask1 = __w0 < _EDt - 1 ?
2844 _Engine_result_type(~0) >> (_EDt - (__w0 + 1)) :
2845 _Engine_result_type(~0);
2846public:
2847 static const result_type _Min = 0;
2848 static const result_type _Max = __w == _Dt ? result_type(~0) :
2849 (result_type(1) << __w) - result_type(1);
2850 static_assert(_Min < _Max, "independent_bits_engine invalid parameters");
2851
2852 // engine characteristics
2853 static const/*expr*/ result_type min() { return _Min; }
2854 static const/*expr*/ result_type max() { return _Max; }
2855
2856 // constructors and seeding functions
2857 independent_bits_engine() {}
2858// explicit independent_bits_engine(const _Engine& __e);
2859// explicit independent_bits_engine(_Engine&& __e);
2860 explicit independent_bits_engine(result_type __sd) : __e_(__sd) {}
2861 template<class _Sseq> explicit independent_bits_engine(_Sseq& __q)
2862 : __e_(__q) {}
2863 void seed() {__e_.seed();}
2864 void seed(result_type __sd) {__e_.seed(__sd);}
2865 template<class _Sseq> void seed(_Sseq& __q) {__e_.seed(__q);}
2866
2867 // generating functions
2868 result_type operator()() {return __eval(integral_constant<bool, _R != 0>());}
2869 void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
2870
2871 // property functions
2872 const _Engine& base() const {return __e_;}
2873
2874 template<class _Eng, size_t _W, class _UI>
2875 friend
2876 bool
2877 operator==(
2878 const independent_bits_engine<_Eng, _W, _UI>& __x,
2879 const independent_bits_engine<_Eng, _W, _UI>& __y);
2880
2881 template<class _Eng, size_t _W, class _UI>
2882 friend
2883 bool
2884 operator!=(
2885 const independent_bits_engine<_Eng, _W, _UI>& __x,
2886 const independent_bits_engine<_Eng, _W, _UI>& __y);
2887
2888 template <class _CharT, class _Traits,
2889 class _Eng, size_t _W, class _UI>
2890 friend
2891 basic_ostream<_CharT, _Traits>&
2892 operator<<(basic_ostream<_CharT, _Traits>& __os,
2893 const independent_bits_engine<_Eng, _W, _UI>& __x);
2894
2895 template <class _CharT, class _Traits,
2896 class _Eng, size_t _W, class _UI>
2897 friend
2898 basic_istream<_CharT, _Traits>&
2899 operator>>(basic_istream<_CharT, _Traits>& __is,
2900 independent_bits_engine<_Eng, _W, _UI>& __x);
2901
2902private:
2903 result_type __eval(false_type);
2904 result_type __eval(true_type);
2905
2906 template <size_t __count>
2907 static
2908 typename enable_if
2909 <
2910 __count < _Dt,
2911 result_type
2912 >::type
2913 __lshift(result_type __x) {return __x << __count;}
2914
2915 template <size_t __count>
2916 static
2917 typename enable_if
2918 <
2919 (__count >= _Dt),
2920 result_type
2921 >::type
2922 __lshift(result_type __x) {return result_type(0);}
2923};
2924
2925template<class _Engine, size_t __w, class _UIntType>
2926inline
2927_UIntType
2928independent_bits_engine<_Engine, __w, _UIntType>::__eval(false_type)
2929{
2930 return static_cast<result_type>(__e_() & __mask0);
2931}
2932
2933template<class _Engine, size_t __w, class _UIntType>
2934_UIntType
2935independent_bits_engine<_Engine, __w, _UIntType>::__eval(true_type)
2936{
2937 result_type _S = 0;
2938 for (size_t __k = 0; __k < __n0; ++__k)
2939 {
2940 _Engine_result_type __u;
2941 do
2942 {
2943 __u = __e_() - _Engine::min();
2944 } while (__u >= __y0);
2945 _S = static_cast<result_type>(__lshift<__w0>(_S) + (__u & __mask0));
2946 }
2947 for (size_t __k = __n0; __k < __n; ++__k)
2948 {
2949 _Engine_result_type __u;
2950 do
2951 {
2952 __u = __e_() - _Engine::min();
2953 } while (__u >= __y1);
2954 _S = static_cast<result_type>(__lshift<__w0+1>(_S) + (__u & __mask1));
2955 }
2956 return _S;
2957}
2958
2959template<class _Eng, size_t _W, class _UI>
2960inline
2961bool
2962operator==(
2963 const independent_bits_engine<_Eng, _W, _UI>& __x,
2964 const independent_bits_engine<_Eng, _W, _UI>& __y)
2965{
2966 return __x.base() == __y.base();
2967}
2968
2969template<class _Eng, size_t _W, class _UI>
2970inline
2971bool
2972operator!=(
2973 const independent_bits_engine<_Eng, _W, _UI>& __x,
2974 const independent_bits_engine<_Eng, _W, _UI>& __y)
2975{
2976 return !(__x == __y);
2977}
2978
2979template <class _CharT, class _Traits,
2980 class _Eng, size_t _W, class _UI>
2981basic_ostream<_CharT, _Traits>&
2982operator<<(basic_ostream<_CharT, _Traits>& __os,
2983 const independent_bits_engine<_Eng, _W, _UI>& __x)
2984{
2985 return __os << __x.base();
2986}
2987
2988template <class _CharT, class _Traits,
2989 class _Eng, size_t _W, class _UI>
2990basic_istream<_CharT, _Traits>&
2991operator>>(basic_istream<_CharT, _Traits>& __is,
2992 independent_bits_engine<_Eng, _W, _UI>& __x)
2993{
2994 _Eng __e;
2995 __is >> __e;
2996 if (!__is.fail())
2997 __x.__e_ = __e;
2998 return __is;
2999}
3000
3001// shuffle_order_engine
3002
3003template <uint64_t _Xp, uint64_t _Yp>
3004struct __ugcd
3005{
3006 static const uint64_t value = __ugcd<_Yp, _Xp % _Yp>::value;
3007};
3008
3009template <uint64_t _Xp>
3010struct __ugcd<_Xp, 0>
3011{
3012 static const uint64_t value = _Xp;
3013};
3014
3015template <uint64_t _N, uint64_t _D>
3016class __uratio
3017{
3018 static_assert(_D != 0, "__uratio divide by 0");
3019 static const uint64_t __gcd = __ugcd<_N, _D>::value;
3020public:
3021 static const uint64_t num = _N / __gcd;
3022 static const uint64_t den = _D / __gcd;
3023
3024 typedef __uratio<num, den> type;
3025};
3026
3027template<class _Engine, size_t __k>
3028class shuffle_order_engine
3029{
3030 static_assert(0 < __k, "shuffle_order_engine invalid parameters");
3031public:
3032 // types
3033 typedef typename _Engine::result_type result_type;
3034
3035private:
3036 _Engine __e_;
3037 result_type _V_[__k];
3038 result_type _Y_;
3039
3040public:
3041 // engine characteristics
3042 static const/*expr*/ size_t table_size = __k;
3043
3044 static const result_type _Min = _Engine::_Min;
3045 static const result_type _Max = _Engine::_Max;
3046 static_assert(_Min < _Max, "shuffle_order_engine invalid parameters");
3047 static const/*expr*/ result_type min() { return _Min; }
3048 static const/*expr*/ result_type max() { return _Max; }
3049
3050 static const unsigned long long _R = _Max - _Min + 1ull;
3051
3052 // constructors and seeding functions
3053 shuffle_order_engine() {__init();}
3054// explicit shuffle_order_engine(const _Engine& __e);
3055// explicit shuffle_order_engine(_Engine&& e);
3056 explicit shuffle_order_engine(result_type __sd) : __e_(__sd) {__init();}
3057 template<class _Sseq> explicit shuffle_order_engine(_Sseq& __q)
3058 : __e_(__q) {__init();}
3059 void seed() {__e_.seed(); __init();}
3060 void seed(result_type __sd) {__e_.seed(__sd); __init();}
3061 template<class _Sseq> void seed(_Sseq& __q) {__e_.seed(__q); __init();}
3062
3063 // generating functions
3064 result_type operator()() {return __eval(integral_constant<bool, _R != 0>());}
3065 void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
3066
3067 // property functions
3068 const _Engine& base() const {return __e_;}
3069
3070private:
3071 template<class _Eng, size_t _K>
3072 friend
3073 bool
3074 operator==(
3075 const shuffle_order_engine<_Eng, _K>& __x,
3076 const shuffle_order_engine<_Eng, _K>& __y);
3077
3078 template<class _Eng, size_t _K>
3079 friend
3080 bool
3081 operator!=(
3082 const shuffle_order_engine<_Eng, _K>& __x,
3083 const shuffle_order_engine<_Eng, _K>& __y);
3084
3085 template <class _CharT, class _Traits,
3086 class _Eng, size_t _K>
3087 friend
3088 basic_ostream<_CharT, _Traits>&
3089 operator<<(basic_ostream<_CharT, _Traits>& __os,
3090 const shuffle_order_engine<_Eng, _K>& __x);
3091
3092 template <class _CharT, class _Traits,
3093 class _Eng, size_t _K>
3094 friend
3095 basic_istream<_CharT, _Traits>&
3096 operator>>(basic_istream<_CharT, _Traits>& __is,
3097 shuffle_order_engine<_Eng, _K>& __x);
3098
3099 void __init()
3100 {
3101 for (size_t __i = 0; __i < __k; ++__i)
3102 _V_[__i] = __e_();
3103 _Y_ = __e_();
3104 }
3105
3106 result_type __eval(false_type) {return __eval2(integral_constant<bool, __k & 1>());}
3107 result_type __eval(true_type) {return __eval(__uratio<__k, _R>());}
3108
3109 result_type __eval2(false_type) {return __eval(__uratio<__k/2, 0x8000000000000000ull>());}
3110 result_type __eval2(true_type) {return __evalf<__k, 0>();}
3111
3112 template <uint64_t _N, uint64_t _D>
3113 typename enable_if
3114 <
3115 (__uratio<_N, _D>::num > 0xFFFFFFFFFFFFFFFFull / (_Max - _Min)),
3116 result_type
3117 >::type
3118 __eval(__uratio<_N, _D>)
3119 {return __evalf<__uratio<_N, _D>::num, __uratio<_N, _D>::den>();}
3120
3121 template <uint64_t _N, uint64_t _D>
3122 typename enable_if
3123 <
3124 __uratio<_N, _D>::num <= 0xFFFFFFFFFFFFFFFFull / (_Max - _Min),
3125 result_type
3126 >::type
3127 __eval(__uratio<_N, _D>)
3128 {
3129 const size_t __j = static_cast<size_t>(__uratio<_N, _D>::num * (_Y_ - _Min)
3130 / __uratio<_N, _D>::den);
3131 _Y_ = _V_[__j];
3132 _V_[__j] = __e_();
3133 return _Y_;
3134 }
3135
3136 template <uint64_t __n, uint64_t __d>
3137 result_type __evalf()
3138 {
3139 const double _F = __d == 0 ?
3140 __n / (2. * 0x8000000000000000ull) :
3141 __n / (double)__d;
3142 const size_t __j = static_cast<size_t>(_F * (_Y_ - _Min));
3143 _Y_ = _V_[__j];
3144 _V_[__j] = __e_();
3145 return _Y_;
3146 }
3147};
3148
3149template<class _Eng, size_t _K>
3150bool
3151operator==(
3152 const shuffle_order_engine<_Eng, _K>& __x,
3153 const shuffle_order_engine<_Eng, _K>& __y)
3154{
3155 return __x._Y_ == __y._Y_ && _STD::equal(__x._V_, __x._V_ + _K, __y._V_) &&
3156 __x.__e_ == __y.__e_;
3157}
3158
3159template<class _Eng, size_t _K>
3160inline
3161bool
3162operator!=(
3163 const shuffle_order_engine<_Eng, _K>& __x,
3164 const shuffle_order_engine<_Eng, _K>& __y)
3165{
3166 return !(__x == __y);
3167}
3168
3169template <class _CharT, class _Traits,
3170 class _Eng, size_t _K>
3171basic_ostream<_CharT, _Traits>&
3172operator<<(basic_ostream<_CharT, _Traits>& __os,
3173 const shuffle_order_engine<_Eng, _K>& __x)
3174{
3175 __save_flags<_CharT, _Traits> _(__os);
3176 __os.flags(ios_base::dec | ios_base::left);
3177 _CharT __sp = __os.widen(' ');
3178 __os.fill(__sp);
3179 __os << __x.__e_ << __sp << __x._V_[0];
3180 for (size_t __i = 1; __i < _K; ++__i)
3181 __os << __sp << __x._V_[__i];
3182 return __os << __sp << __x._Y_;
3183}
3184
3185template <class _CharT, class _Traits,
3186 class _Eng, size_t _K>
3187basic_istream<_CharT, _Traits>&
3188operator>>(basic_istream<_CharT, _Traits>& __is,
3189 shuffle_order_engine<_Eng, _K>& __x)
3190{
3191 typedef typename shuffle_order_engine<_Eng, _K>::result_type result_type;
3192 __save_flags<_CharT, _Traits> _(__is);
3193 __is.flags(ios_base::dec | ios_base::skipws);
3194 _Eng __e;
3195 result_type _V[_K+1];
3196 __is >> __e;
3197 for (size_t __i = 0; __i < _K+1; ++__i)
3198 __is >> _V[__i];
3199 if (!__is.fail())
3200 {
3201 __x.__e_ = __e;
3202 for (size_t __i = 0; __i < _K; ++__i)
3203 __x._V_[__i] = _V[__i];
3204 __x._Y_ = _V[_K];
3205 }
3206 return __is;
3207}
3208
3209typedef shuffle_order_engine<minstd_rand0, 256> knuth_b;
3210
3211// random_device
3212
3213class random_device
3214{
3215 int __f_;
3216public:
3217 // types
3218 typedef unsigned result_type;
3219
3220 // generator characteristics
3221 static const result_type _Min = 0;
3222 static const result_type _Max = 0xFFFFFFFFu;
3223
3224 static const/*expr*/ result_type min() { return _Min;}
3225 static const/*expr*/ result_type max() { return _Max;}
3226
3227 // constructors
3228 explicit random_device(const string& __token = "/dev/urandom");
3229 ~random_device();
3230
3231 // generating functions
3232 result_type operator()();
3233
3234 // property functions
3235 double entropy() const;
3236
3237private:
3238 // no copy functions
3239 random_device(const random_device&); // = delete;
3240 random_device& operator=(const random_device&); // = delete;
3241};
3242
3243// seed_seq
3244
3245class seed_seq
3246{
3247public:
3248 // types
3249 typedef uint32_t result_type;
3250
3251private:
3252 vector<result_type> __v_;
3253
3254 template<class _InputIterator>
3255 void init(_InputIterator __first, _InputIterator __last);
3256public:
3257 // constructors
3258 seed_seq() {}
3259 template<class _Tp>
3260 seed_seq(initializer_list<_Tp> __il) {init(__il.begin(), __il.end());}
3261
3262 template<class _InputIterator>
3263 seed_seq(_InputIterator __first, _InputIterator __last)
3264 {init(__first, __last);}
3265
3266 // generating functions
3267 template<class _RandomAccessIterator>
3268 void generate(_RandomAccessIterator __first, _RandomAccessIterator __last);
3269
3270 // property functions
3271 size_t size() const {return __v_.size();}
3272 template<class _OutputIterator>
3273 void param(_OutputIterator __dest) const
3274 {_STD::copy(__v_.begin(), __v_.end(), __dest);}
3275
3276private:
3277 // no copy functions
3278 seed_seq(const seed_seq&); // = delete;
3279 void operator=(const seed_seq&); // = delete;
3280
3281 static result_type _T(result_type __x) {return __x ^ (__x >> 27);}
3282};
3283
3284template<class _InputIterator>
3285void
3286seed_seq::init(_InputIterator __first, _InputIterator __last)
3287{
3288 for (_InputIterator __s = __first; __s != __last; ++__s)
3289 __v_.push_back(*__s & 0xFFFFFFFF);
3290}
3291
3292template<class _RandomAccessIterator>
3293void
3294seed_seq::generate(_RandomAccessIterator __first, _RandomAccessIterator __last)
3295{
3296 if (__first != __last)
3297 {
3298 _STD::fill(__first, __last, 0x8b8b8b8b);
3299 const size_t __n = static_cast<size_t>(__last - __first);
3300 const size_t __s = __v_.size();
3301 const size_t __t = (__n >= 623) ? 11
3302 : (__n >= 68) ? 7
3303 : (__n >= 39) ? 5
3304 : (__n >= 7) ? 3
3305 : (__n - 1) / 2;
3306 const size_t __p = (__n - __t) / 2;
3307 const size_t __q = __p + __t;
3308 const size_t __m = _STD::max(__s + 1, __n);
3309 // __k = 0;
3310 {
3311 result_type __r = 1664525 * _T(__first[0] ^ __first[__p]
3312 ^ __first[__n - 1]);
3313 __first[__p] += __r;
3314 __r += __s;
3315 __first[__q] += __r;
3316 __first[0] = __r;
3317 }
3318 for (size_t __k = 1; __k <= __s; ++__k)
3319 {
3320 const size_t __kmodn = __k % __n;
3321 const size_t __kpmodn = (__k + __p) % __n;
3322 result_type __r = 1664525 * _T(__first[__kmodn] ^ __first[__kpmodn]
3323 ^ __first[(__k - 1) % __n]);
3324 __first[__kpmodn] += __r;
3325 __r += __kmodn + __v_[__k-1];
3326 __first[(__k + __q) % __n] += __r;
3327 __first[__kmodn] = __r;
3328 }
3329 for (size_t __k = __s + 1; __k < __m; ++__k)
3330 {
3331 const size_t __kmodn = __k % __n;
3332 const size_t __kpmodn = (__k + __p) % __n;
3333 result_type __r = 1664525 * _T(__first[__kmodn] ^ __first[__kpmodn]
3334 ^ __first[(__k - 1) % __n]);
3335 __first[__kpmodn] += __r;
3336 __r += __kmodn;
3337 __first[(__k + __q) % __n] += __r;
3338 __first[__kmodn] = __r;
3339 }
3340 for (size_t __k = __m; __k < __m + __n; ++__k)
3341 {
3342 const size_t __kmodn = __k % __n;
3343 const size_t __kpmodn = (__k + __p) % __n;
3344 result_type __r = 1566083941 * _T(__first[__kmodn] +
3345 __first[__kpmodn] +
3346 __first[(__k - 1) % __n]);
3347 __first[__kpmodn] ^= __r;
3348 __r -= __kmodn;
3349 __first[(__k + __q) % __n] ^= __r;
3350 __first[__kmodn] = __r;
3351 }
3352 }
3353}
3354
Howard Hinnant30a840f2010-05-12 17:08:57 +0000[diff] [blame]3355// generate_canonical
3356
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]3357template<class _RealType, size_t __bits, class _URNG>
3358_RealType
3359generate_canonical(_URNG& __g)
3360{
3361 const size_t _Dt = numeric_limits<_RealType>::digits;
3362 const size_t __b = _Dt < __bits ? _Dt : __bits;
3363 const size_t __logR = __log2<uint64_t, _URNG::_Max - _URNG::_Min + uint64_t(1)>::value;
3364 const size_t __k = __b / __logR + (__b % __logR != 0) + (__b == 0);
3365 const _RealType _R = _URNG::_Max - _URNG::_Min + _RealType(1);
3366 _RealType __base = _R;
3367 _RealType _S = __g() - _URNG::_Min;
3368 for (size_t __i = 1; __i < __k; ++__i, __base *= _R)
3369 _S += (__g() - _URNG::_Min) * __base;
3370 return _S / __base;
3371}
3372
Howard Hinnant30a840f2010-05-12 17:08:57 +0000[diff] [blame]3373// uniform_int_distribution
3374
Howard Hinnantc3267212010-05-26 17:49:34 +0000[diff] [blame]3375// in <algorithm>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]3376
3377template <class _CharT, class _Traits, class _IT>
3378basic_ostream<_CharT, _Traits>&
3379operator<<(basic_ostream<_CharT, _Traits>& __os,
3380 const uniform_int_distribution<_IT>& __x)
3381{
3382 __save_flags<_CharT, _Traits> _(__os);
3383 __os.flags(ios_base::dec | ios_base::left);
3384 _CharT __sp = __os.widen(' ');
3385 __os.fill(__sp);
3386 return __os << __x.a() << __sp << __x.b();
3387}
3388
3389template <class _CharT, class _Traits, class _IT>
3390basic_istream<_CharT, _Traits>&
3391operator>>(basic_istream<_CharT, _Traits>& __is,
3392 uniform_int_distribution<_IT>& __x)
3393{
3394 typedef uniform_int_distribution<_IT> _Eng;
3395 typedef typename _Eng::result_type result_type;
3396 typedef typename _Eng::param_type param_type;
3397 __save_flags<_CharT, _Traits> _(__is);
3398 __is.flags(ios_base::dec | ios_base::skipws);
3399 result_type __a;
3400 result_type __b;
3401 __is >> __a >> __b;
3402 if (!__is.fail())
3403 __x.param(param_type(__a, __b));
3404 return __is;
3405}
3406
Howard Hinnant30a840f2010-05-12 17:08:57 +0000[diff] [blame]3407// uniform_real_distribution
3408
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]3409template<class _RealType = double>
3410class uniform_real_distribution
3411{
3412public:
3413 // types
3414 typedef _RealType result_type;
3415
3416 class param_type
3417 {
3418 result_type __a_;
3419 result_type __b_;
3420 public:
3421 typedef uniform_real_distribution distribution_type;
3422
3423 explicit param_type(result_type __a = 0,
3424 result_type __b = 1)
3425 : __a_(__a), __b_(__b) {}
3426
3427 result_type a() const {return __a_;}
3428 result_type b() const {return __b_;}
3429
3430 friend bool operator==(const param_type& __x, const param_type& __y)
3431 {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
3432 friend bool operator!=(const param_type& __x, const param_type& __y)
3433 {return !(__x == __y);}
3434 };
3435
3436private:
3437 param_type __p_;
3438
3439public:
3440 // constructors and reset functions
3441 explicit uniform_real_distribution(result_type __a = 0, result_type __b = 1)
3442 : __p_(param_type(__a, __b)) {}
3443 explicit uniform_real_distribution(const param_type& __p) : __p_(__p) {}
3444 void reset() {}
3445
3446 // generating functions
3447 template<class _URNG> result_type operator()(_URNG& __g)
3448 {return (*this)(__g, __p_);}
3449 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
3450
3451 // property functions
3452 result_type a() const {return __p_.a();}
3453 result_type b() const {return __p_.b();}
3454
3455 param_type param() const {return __p_;}
3456 void param(const param_type& __p) {__p_ = __p;}
3457
3458 result_type min() const {return a();}
3459 result_type max() const {return b();}
3460
3461 friend bool operator==(const uniform_real_distribution& __x,
3462 const uniform_real_distribution& __y)
3463 {return __x.__p_ == __y.__p_;}
3464 friend bool operator!=(const uniform_real_distribution& __x,
3465 const uniform_real_distribution& __y)
3466 {return !(__x == __y);}
3467};
3468
3469template<class _RealType>
3470template<class _URNG>
3471inline
3472typename uniform_real_distribution<_RealType>::result_type
3473uniform_real_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
3474{
3475 return (__p.b() - __p.a())
3476 * _STD::generate_canonical<_RealType, numeric_limits<_RealType>::digits>(__g)
3477 + __p.a();
3478}
3479
3480template <class _CharT, class _Traits, class _RT>
3481basic_ostream<_CharT, _Traits>&
3482operator<<(basic_ostream<_CharT, _Traits>& __os,
3483 const uniform_real_distribution<_RT>& __x)
3484{
3485 __save_flags<_CharT, _Traits> _(__os);
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]3486 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
3487 ios_base::scientific);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]3488 _CharT __sp = __os.widen(' ');
3489 __os.fill(__sp);
3490 return __os << __x.a() << __sp << __x.b();
3491}
3492
3493template <class _CharT, class _Traits, class _RT>
3494basic_istream<_CharT, _Traits>&
3495operator>>(basic_istream<_CharT, _Traits>& __is,
3496 uniform_real_distribution<_RT>& __x)
3497{
3498 typedef uniform_real_distribution<_RT> _Eng;
3499 typedef typename _Eng::result_type result_type;
3500 typedef typename _Eng::param_type param_type;
3501 __save_flags<_CharT, _Traits> _(__is);
3502 __is.flags(ios_base::dec | ios_base::skipws);
3503 result_type __a;
3504 result_type __b;
3505 __is >> __a >> __b;
3506 if (!__is.fail())
3507 __x.param(param_type(__a, __b));
3508 return __is;
3509}
3510
Howard Hinnant30a840f2010-05-12 17:08:57 +0000[diff] [blame]3511// bernoulli_distribution
3512
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]3513class bernoulli_distribution
3514{
3515public:
3516 // types
3517 typedef bool result_type;
3518
3519 class param_type
3520 {
3521 double __p_;
3522 public:
3523 typedef bernoulli_distribution distribution_type;
3524
3525 explicit param_type(double __p = 0.5) : __p_(__p) {}
3526
3527 double p() const {return __p_;}
3528
3529 friend bool operator==(const param_type& __x, const param_type& __y)
3530 {return __x.__p_ == __y.__p_;}
3531 friend bool operator!=(const param_type& __x, const param_type& __y)
3532 {return !(__x == __y);}
3533 };
3534
3535private:
3536 param_type __p_;
3537
3538public:
3539 // constructors and reset functions
3540 explicit bernoulli_distribution(double __p = 0.5)
3541 : __p_(param_type(__p)) {}
3542 explicit bernoulli_distribution(const param_type& __p) : __p_(__p) {}
3543 void reset() {}
3544
3545 // generating functions
3546 template<class _URNG> result_type operator()(_URNG& __g)
3547 {return (*this)(__g, __p_);}
Howard Hinnant03aad812010-05-11 23:26:59 +0000[diff] [blame]3548 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]3549
3550 // property functions
3551 double p() const {return __p_.p();}
3552
3553 param_type param() const {return __p_;}
3554 void param(const param_type& __p) {__p_ = __p;}
3555
3556 result_type min() const {return false;}
3557 result_type max() const {return true;}
3558
3559 friend bool operator==(const bernoulli_distribution& __x,
3560 const bernoulli_distribution& __y)
3561 {return __x.__p_ == __y.__p_;}
3562 friend bool operator!=(const bernoulli_distribution& __x,
3563 const bernoulli_distribution& __y)
3564 {return !(__x == __y);}
3565};
3566
Howard Hinnant03aad812010-05-11 23:26:59 +0000[diff] [blame]3567template<class _URNG>
3568inline
3569bernoulli_distribution::result_type
3570bernoulli_distribution::operator()(_URNG& __g, const param_type& __p)
3571{
Howard Hinnantd6d11712010-05-20 15:11:46 +0000[diff] [blame]3572 uniform_real_distribution<double> __gen;
3573 return __gen(__g) < __p.p();
Howard Hinnant03aad812010-05-11 23:26:59 +0000[diff] [blame]3574}
3575
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]3576template <class _CharT, class _Traits>
3577basic_ostream<_CharT, _Traits>&
3578operator<<(basic_ostream<_CharT, _Traits>& __os, const bernoulli_distribution& __x)
3579{
3580 __save_flags<_CharT, _Traits> _(__os);
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]3581 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
3582 ios_base::scientific);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]3583 _CharT __sp = __os.widen(' ');
3584 __os.fill(__sp);
3585 return __os << __x.p();
3586}
3587
3588template <class _CharT, class _Traits>
3589basic_istream<_CharT, _Traits>&
3590operator>>(basic_istream<_CharT, _Traits>& __is, bernoulli_distribution& __x)
3591{
3592 typedef bernoulli_distribution _Eng;
3593 typedef typename _Eng::param_type param_type;
3594 __save_flags<_CharT, _Traits> _(__is);
3595 __is.flags(ios_base::dec | ios_base::skipws);
3596 double __p;
3597 __is >> __p;
3598 if (!__is.fail())
3599 __x.param(param_type(__p));
3600 return __is;
3601}
3602
Howard Hinnant30a840f2010-05-12 17:08:57 +0000[diff] [blame]3603// binomial_distribution
3604
Howard Hinnant03aad812010-05-11 23:26:59 +0000[diff] [blame]3605template<class _IntType = int>
3606class binomial_distribution
3607{
3608public:
3609 // types
3610 typedef _IntType result_type;
3611
3612 class param_type
3613 {
3614 result_type __t_;
3615 double __p_;
Howard Hinnant6add8dd2010-05-15 21:36:23 +0000[diff] [blame]3616 double __pr_;
3617 double __odds_ratio_;
3618 result_type __r0_;
Howard Hinnant03aad812010-05-11 23:26:59 +0000[diff] [blame]3619 public:
3620 typedef binomial_distribution distribution_type;
3621
Howard Hinnant6add8dd2010-05-15 21:36:23 +0000[diff] [blame]3622 explicit param_type(result_type __t = 1, double __p = 0.5);
Howard Hinnant03aad812010-05-11 23:26:59 +0000[diff] [blame]3623
3624 result_type t() const {return __t_;}
3625 double p() const {return __p_;}
3626
3627 friend bool operator==(const param_type& __x, const param_type& __y)
3628 {return __x.__t_ == __y.__t_ && __x.__p_ == __y.__p_;}
3629 friend bool operator!=(const param_type& __x, const param_type& __y)
3630 {return !(__x == __y);}
Howard Hinnant6add8dd2010-05-15 21:36:23 +0000[diff] [blame]3631
3632 friend class binomial_distribution;
Howard Hinnant03aad812010-05-11 23:26:59 +0000[diff] [blame]3633 };
3634
3635private:
3636 param_type __p_;
3637
3638public:
3639 // constructors and reset functions
3640 explicit binomial_distribution(result_type __t = 1, double __p = 0.5)
3641 : __p_(param_type(__t, __p)) {}
3642 explicit binomial_distribution(const param_type& __p) : __p_(__p) {}
3643 void reset() {}
3644
3645 // generating functions
3646 template<class _URNG> result_type operator()(_URNG& __g)
3647 {return (*this)(__g, __p_);}
3648 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
3649
3650 // property functions
3651 result_type t() const {return __p_.t();}
3652 double p() const {return __p_.p();}
3653
3654 param_type param() const {return __p_;}
3655 void param(const param_type& __p) {__p_ = __p;}
3656
3657 result_type min() const {return 0;}
3658 result_type max() const {return t();}
3659
3660 friend bool operator==(const binomial_distribution& __x,
3661 const binomial_distribution& __y)
3662 {return __x.__p_ == __y.__p_;}
3663 friend bool operator!=(const binomial_distribution& __x,
3664 const binomial_distribution& __y)
3665 {return !(__x == __y);}
3666};
3667
3668template<class _IntType>
Howard Hinnant6add8dd2010-05-15 21:36:23 +0000[diff] [blame]3669binomial_distribution<_IntType>::param_type::param_type(result_type __t, double __p)
3670 : __t_(__t), __p_(__p)
3671{
3672 if (0 < __p_ && __p_ < 1)
3673 {
3674 __r0_ = static_cast<result_type>((__t_ + 1) * __p_);
3675 __pr_ = _STD::exp(_STD::lgamma(__t_ + 1.) - _STD::lgamma(__r0_ + 1.) -
3676 _STD::lgamma(__t_ - __r0_ + 1.) + __r0_ * _STD::log(__p_) +
3677 (__t_ - __r0_) * _STD::log(1 - __p_));
3678 __odds_ratio_ = __p_ / (1 - __p_);
3679 }
3680}
3681
3682template<class _IntType>
Howard Hinnant03aad812010-05-11 23:26:59 +0000[diff] [blame]3683template<class _URNG>
3684_IntType
Howard Hinnant6add8dd2010-05-15 21:36:23 +0000[diff] [blame]3685binomial_distribution<_IntType>::operator()(_URNG& __g, const param_type& __pr)
Howard Hinnant03aad812010-05-11 23:26:59 +0000[diff] [blame]3686{
Howard Hinnant6add8dd2010-05-15 21:36:23 +0000[diff] [blame]3687 if (__pr.__t_ == 0 || __pr.__p_ == 0)
3688 return 0;
3689 if (__pr.__p_ == 1)
3690 return __pr.__t_;
3691 uniform_real_distribution<double> __gen;
3692 double __u = __gen(__g) - __pr.__pr_;
3693 if (__u < 0)
3694 return __pr.__r0_;
3695 double __pu = __pr.__pr_;
3696 double __pd = __pu;
3697 result_type __ru = __pr.__r0_;
3698 result_type __rd = __ru;
3699 while (true)
3700 {
3701 if (__rd >= 1)
3702 {
3703 __pd *= __rd / (__pr.__odds_ratio_ * (__pr.__t_ - __rd + 1));
3704 __u -= __pd;
3705 if (__u < 0)
3706 return __rd - 1;
3707 }
3708 --__rd;
3709 ++__ru;
3710 if (__ru <= __pr.__t_)
3711 {
3712 __pu *= (__pr.__t_ - __ru + 1) * __pr.__odds_ratio_ / __ru;
3713 __u -= __pu;
3714 if (__u < 0)
3715 return __ru;
3716 }
3717 }
Howard Hinnant03aad812010-05-11 23:26:59 +0000[diff] [blame]3718}
3719
3720template <class _CharT, class _Traits, class _IntType>
3721basic_ostream<_CharT, _Traits>&
3722operator<<(basic_ostream<_CharT, _Traits>& __os,
3723 const binomial_distribution<_IntType>& __x)
3724{
3725 __save_flags<_CharT, _Traits> _(__os);
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]3726 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
3727 ios_base::scientific);
Howard Hinnant03aad812010-05-11 23:26:59 +0000[diff] [blame]3728 _CharT __sp = __os.widen(' ');
3729 __os.fill(__sp);
3730 return __os << __x.t() << __sp << __x.p();
3731}
3732
3733template <class _CharT, class _Traits, class _IntType>
3734basic_istream<_CharT, _Traits>&
3735operator>>(basic_istream<_CharT, _Traits>& __is,
3736 binomial_distribution<_IntType>& __x)
3737{
3738 typedef binomial_distribution<_IntType> _Eng;
3739 typedef typename _Eng::result_type result_type;
3740 typedef typename _Eng::param_type param_type;
3741 __save_flags<_CharT, _Traits> _(__is);
3742 __is.flags(ios_base::dec | ios_base::skipws);
3743 result_type __t;
3744 double __p;
3745 __is >> __t >> __p;
3746 if (!__is.fail())
3747 __x.param(param_type(__t, __p));
3748 return __is;
3749}
3750
Howard Hinnant30a840f2010-05-12 17:08:57 +0000[diff] [blame]3751// exponential_distribution
3752
3753template<class _RealType = double>
3754class exponential_distribution
3755{
3756public:
3757 // types
3758 typedef _RealType result_type;
3759
3760 class param_type
3761 {
3762 result_type __lambda_;
3763 public:
3764 typedef exponential_distribution distribution_type;
3765
3766 explicit param_type(result_type __lambda = 1) : __lambda_(__lambda) {}
3767
3768 result_type lambda() const {return __lambda_;}
3769
3770 friend bool operator==(const param_type& __x, const param_type& __y)
3771 {return __x.__lambda_ == __y.__lambda_;}
3772 friend bool operator!=(const param_type& __x, const param_type& __y)
3773 {return !(__x == __y);}
3774 };
3775
3776private:
3777 param_type __p_;
3778
3779public:
3780 // constructors and reset functions
3781 explicit exponential_distribution(result_type __lambda = 1)
3782 : __p_(param_type(__lambda)) {}
3783 explicit exponential_distribution(const param_type& __p) : __p_(__p) {}
3784 void reset() {}
3785
3786 // generating functions
3787 template<class _URNG> result_type operator()(_URNG& __g)
3788 {return (*this)(__g, __p_);}
3789 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
3790
3791 // property functions
3792 result_type lambda() const {return __p_.lambda();}
3793
3794 param_type param() const {return __p_;}
3795 void param(const param_type& __p) {__p_ = __p;}
3796
3797 result_type min() const {return 0;}
Howard Hinnantdf40dc62010-05-16 17:56:20 +0000[diff] [blame]3798 result_type max() const {return numeric_limits<result_type>::infinity();}
Howard Hinnant30a840f2010-05-12 17:08:57 +0000[diff] [blame]3799
3800 friend bool operator==(const exponential_distribution& __x,
3801 const exponential_distribution& __y)
3802 {return __x.__p_ == __y.__p_;}
3803 friend bool operator!=(const exponential_distribution& __x,
3804 const exponential_distribution& __y)
3805 {return !(__x == __y);}
3806};
3807
3808template <class _RealType>
3809template<class _URNG>
3810_RealType
3811exponential_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
3812{
3813 return -_STD::log
3814 (
3815 result_type(1) -
3816 _STD::generate_canonical<result_type,
3817 numeric_limits<result_type>::digits>(__g)
3818 )
3819 / __p.lambda();
3820}
3821
3822template <class _CharT, class _Traits, class _RealType>
3823basic_ostream<_CharT, _Traits>&
3824operator<<(basic_ostream<_CharT, _Traits>& __os,
3825 const exponential_distribution<_RealType>& __x)
3826{
3827 __save_flags<_CharT, _Traits> _(__os);
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]3828 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
3829 ios_base::scientific);
Howard Hinnant30a840f2010-05-12 17:08:57 +0000[diff] [blame]3830 return __os << __x.lambda();
3831}
3832
3833template <class _CharT, class _Traits, class _RealType>
3834basic_istream<_CharT, _Traits>&
3835operator>>(basic_istream<_CharT, _Traits>& __is,
3836 exponential_distribution<_RealType>& __x)
3837{
3838 typedef exponential_distribution<_RealType> _Eng;
3839 typedef typename _Eng::result_type result_type;
3840 typedef typename _Eng::param_type param_type;
3841 __save_flags<_CharT, _Traits> _(__is);
3842 __is.flags(ios_base::dec | ios_base::skipws);
3843 result_type __lambda;
3844 __is >> __lambda;
3845 if (!__is.fail())
3846 __x.param(param_type(__lambda));
3847 return __is;
3848}
3849
Howard Hinnant6add8dd2010-05-15 21:36:23 +0000[diff] [blame]3850// normal_distribution
3851
3852template<class _RealType = double>
3853class normal_distribution
3854{
3855public:
3856 // types
3857 typedef _RealType result_type;
3858
3859 class param_type
3860 {
3861 result_type __mean_;
3862 result_type __stddev_;
3863 public:
3864 typedef normal_distribution distribution_type;
3865
3866 explicit param_type(result_type __mean = 0, result_type __stddev = 1)
3867 : __mean_(__mean), __stddev_(__stddev) {}
3868
3869 result_type mean() const {return __mean_;}
3870 result_type stddev() const {return __stddev_;}
3871
3872 friend bool operator==(const param_type& __x, const param_type& __y)
3873 {return __x.__mean_ == __y.__mean_ && __x.__stddev_ == __y.__stddev_;}
3874 friend bool operator!=(const param_type& __x, const param_type& __y)
3875 {return !(__x == __y);}
3876 };
3877
3878private:
3879 param_type __p_;
3880 result_type _V_;
3881 bool _V_hot_;
3882
3883public:
3884 // constructors and reset functions
3885 explicit normal_distribution(result_type __mean = 0, result_type __stddev = 1)
3886 : __p_(param_type(__mean, __stddev)), _V_hot_(false) {}
3887 explicit normal_distribution(const param_type& __p)
3888 : __p_(__p), _V_hot_(false) {}
3889 void reset() {_V_hot_ = false;}
3890
3891 // generating functions
3892 template<class _URNG> result_type operator()(_URNG& __g)
3893 {return (*this)(__g, __p_);}
3894 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
3895
3896 // property functions
3897 result_type mean() const {return __p_.mean();}
3898 result_type stddev() const {return __p_.stddev();}
3899
3900 param_type param() const {return __p_;}
3901 void param(const param_type& __p) {__p_ = __p;}
3902
3903 result_type min() const {return -numeric_limits<result_type>::infinity();}
3904 result_type max() const {return numeric_limits<result_type>::infinity();}
3905
3906 friend bool operator==(const normal_distribution& __x,
3907 const normal_distribution& __y)
3908 {return __x.__p_ == __y.__p_ && __x._V_hot_ == __y._V_hot_ &&
3909 (!__x._V_hot_ || __x._V_ == __y._V_);}
3910 friend bool operator!=(const normal_distribution& __x,
3911 const normal_distribution& __y)
3912 {return !(__x == __y);}
3913
3914 template <class _CharT, class _Traits, class _RT>
3915 friend
3916 basic_ostream<_CharT, _Traits>&
3917 operator<<(basic_ostream<_CharT, _Traits>& __os,
3918 const normal_distribution<_RT>& __x);
3919
3920 template <class _CharT, class _Traits, class _RT>
3921 friend
3922 basic_istream<_CharT, _Traits>&
3923 operator>>(basic_istream<_CharT, _Traits>& __is,
3924 normal_distribution<_RT>& __x);
3925};
3926
3927template <class _RealType>
3928template<class _URNG>
3929_RealType
3930normal_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
3931{
3932 result_type _U;
3933 if (_V_hot_)
3934 {
3935 _V_hot_ = false;
3936 _U = _V_;
3937 }
3938 else
3939 {
3940 uniform_real_distribution<result_type> _Uni(-1, 1);
3941 result_type __u;
3942 result_type __v;
3943 result_type __s;
3944 do
3945 {
3946 __u = _Uni(__g);
3947 __v = _Uni(__g);
3948 __s = __u * __u + __v * __v;
3949 } while (__s > 1 || __s == 0);
3950 result_type _F = _STD::sqrt(-2 * _STD::log(__s) / __s);
3951 _V_ = __v * _F;
3952 _V_hot_ = true;
3953 _U = __u * _F;
3954 }
3955 return _U * __p.stddev() + __p.mean();
3956}
3957
3958template <class _CharT, class _Traits, class _RT>
3959basic_ostream<_CharT, _Traits>&
3960operator<<(basic_ostream<_CharT, _Traits>& __os,
3961 const normal_distribution<_RT>& __x)
3962{
3963 __save_flags<_CharT, _Traits> _(__os);
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]3964 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
3965 ios_base::scientific);
Howard Hinnant6add8dd2010-05-15 21:36:23 +0000[diff] [blame]3966 _CharT __sp = __os.widen(' ');
3967 __os.fill(__sp);
3968 __os << __x.mean() << __sp << __x.stddev() << __sp << __x._V_hot_;
3969 if (__x._V_hot_)
3970 __os << __sp << __x._V_;
3971 return __os;
3972}
3973
3974template <class _CharT, class _Traits, class _RT>
3975basic_istream<_CharT, _Traits>&
3976operator>>(basic_istream<_CharT, _Traits>& __is,
3977 normal_distribution<_RT>& __x)
3978{
3979 typedef normal_distribution<_RT> _Eng;
3980 typedef typename _Eng::result_type result_type;
3981 typedef typename _Eng::param_type param_type;
3982 __save_flags<_CharT, _Traits> _(__is);
3983 __is.flags(ios_base::dec | ios_base::skipws);
3984 result_type __mean;
3985 result_type __stddev;
3986 result_type _V = 0;
3987 bool _V_hot = false;
3988 __is >> __mean >> __stddev >> _V_hot;
3989 if (_V_hot)
3990 __is >> _V;
3991 if (!__is.fail())
3992 {
3993 __x.param(param_type(__mean, __stddev));
3994 __x._V_hot_ = _V_hot;
3995 __x._V_ = _V;
3996 }
3997 return __is;
3998}
3999
Howard Hinnant2bc36fc2010-05-17 18:31:53 +0000[diff] [blame]4000// lognormal_distribution
4001
4002template<class _RealType = double>
4003class lognormal_distribution
4004{
4005public:
4006 // types
4007 typedef _RealType result_type;
4008
4009 class param_type
4010 {
4011 normal_distribution<result_type> __nd_;
4012 public:
4013 typedef lognormal_distribution distribution_type;
4014
4015 explicit param_type(result_type __m = 0, result_type __s = 1)
4016 : __nd_(__m, __s) {}
4017
4018 result_type m() const {return __nd_.mean();}
4019 result_type s() const {return __nd_.stddev();}
4020
4021 friend bool operator==(const param_type& __x, const param_type& __y)
4022 {return __x.__nd_ == __y.__nd_;}
4023 friend bool operator!=(const param_type& __x, const param_type& __y)
4024 {return !(__x == __y);}
4025 friend class lognormal_distribution;
4026
4027 template <class _CharT, class _Traits, class _RT>
4028 friend
4029 basic_ostream<_CharT, _Traits>&
4030 operator<<(basic_ostream<_CharT, _Traits>& __os,
4031 const lognormal_distribution<_RT>& __x);
4032
4033 template <class _CharT, class _Traits, class _RT>
4034 friend
4035 basic_istream<_CharT, _Traits>&
4036 operator>>(basic_istream<_CharT, _Traits>& __is,
4037 lognormal_distribution<_RT>& __x);
4038 };
4039
4040private:
4041 param_type __p_;
4042
4043public:
4044 // constructor and reset functions
4045 explicit lognormal_distribution(result_type __m = 0, result_type __s = 1)
4046 : __p_(param_type(__m, __s)) {}
4047 explicit lognormal_distribution(const param_type& __p)
4048 : __p_(__p) {}
4049 void reset() {__p_.__nd_.reset();}
4050
4051 // generating functions
4052 template<class _URNG> result_type operator()(_URNG& __g)
4053 {return (*this)(__g, __p_);}
4054 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p)
4055 {return _STD::exp(const_cast<normal_distribution<result_type>&>(__p.__nd_)(__g));}
4056
4057 // property functions
4058 result_type m() const {return __p_.m();}
4059 result_type s() const {return __p_.s();}
4060
4061 param_type param() const {return __p_;}
Howard Hinnant551d8e42010-05-19 01:53:57 +0000[diff] [blame]4062 void param(const param_type& __p) {__p_ = __p;}
Howard Hinnant2bc36fc2010-05-17 18:31:53 +0000[diff] [blame]4063
4064 result_type min() const {return 0;}
4065 result_type max() const {return numeric_limits<result_type>::infinity();}
4066
4067 friend bool operator==(const lognormal_distribution& __x,
4068 const lognormal_distribution& __y)
4069 {return __x.__p_ == __y.__p_;}
4070 friend bool operator!=(const lognormal_distribution& __x,
4071 const lognormal_distribution& __y)
4072 {return !(__x == __y);}
4073
4074 template <class _CharT, class _Traits, class _RT>
4075 friend
4076 basic_ostream<_CharT, _Traits>&
4077 operator<<(basic_ostream<_CharT, _Traits>& __os,
4078 const lognormal_distribution<_RT>& __x);
4079
4080 template <class _CharT, class _Traits, class _RT>
4081 friend
4082 basic_istream<_CharT, _Traits>&
4083 operator>>(basic_istream<_CharT, _Traits>& __is,
4084 lognormal_distribution<_RT>& __x);
4085};
4086
4087template <class _CharT, class _Traits, class _RT>
4088inline
4089basic_ostream<_CharT, _Traits>&
4090operator<<(basic_ostream<_CharT, _Traits>& __os,
4091 const lognormal_distribution<_RT>& __x)
4092{
4093 return __os << __x.__p_.__nd_;
4094}
4095
4096template <class _CharT, class _Traits, class _RT>
4097inline
4098basic_istream<_CharT, _Traits>&
4099operator>>(basic_istream<_CharT, _Traits>& __is,
4100 lognormal_distribution<_RT>& __x)
4101{
4102 return __is >> __x.__p_.__nd_;
4103}
4104
Howard Hinnant6add8dd2010-05-15 21:36:23 +0000[diff] [blame]4105// poisson_distribution
4106
4107template<class _IntType = int>
4108class poisson_distribution
4109{
4110public:
4111 // types
4112 typedef _IntType result_type;
4113
4114 class param_type
4115 {
4116 double __mean_;
4117 double __s_;
4118 double __d_;
4119 double __l_;
4120 double __omega_;
4121 double __c0_;
4122 double __c1_;
4123 double __c2_;
4124 double __c3_;
4125 double __c_;
4126
4127 public:
4128 typedef poisson_distribution distribution_type;
4129
4130 explicit param_type(double __mean = 1.0);
4131
4132 double mean() const {return __mean_;}
4133
4134 friend bool operator==(const param_type& __x, const param_type& __y)
4135 {return __x.__mean_ == __y.__mean_;}
4136 friend bool operator!=(const param_type& __x, const param_type& __y)
4137 {return !(__x == __y);}
4138
4139 friend class poisson_distribution;
4140 };
4141
4142private:
4143 param_type __p_;
4144
4145public:
4146 // constructors and reset functions
4147 explicit poisson_distribution(double __mean = 1.0) : __p_(__mean) {}
4148 explicit poisson_distribution(const param_type& __p) : __p_(__p) {}
4149 void reset() {}
4150
4151 // generating functions
4152 template<class _URNG> result_type operator()(_URNG& __g)
4153 {return (*this)(__g, __p_);}
4154 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
4155
4156 // property functions
4157 double mean() const {return __p_.mean();}
4158
4159 param_type param() const {return __p_;}
4160 void param(const param_type& __p) {__p_ = __p;}
4161
4162 result_type min() const {return 0;}
4163 result_type max() const {return numeric_limits<result_type>::max();}
4164
4165 friend bool operator==(const poisson_distribution& __x,
4166 const poisson_distribution& __y)
4167 {return __x.__p_ == __y.__p_;}
4168 friend bool operator!=(const poisson_distribution& __x,
4169 const poisson_distribution& __y)
4170 {return !(__x == __y);}
4171};
4172
4173template<class _IntType>
4174poisson_distribution<_IntType>::param_type::param_type(double __mean)
4175 : __mean_(__mean)
4176{
4177 if (__mean_ < 10)
4178 {
4179 __s_ = 0;
4180 __d_ = 0;
4181 __l_ = _STD::exp(-__mean_);
4182 __omega_ = 0;
4183 __c3_ = 0;
4184 __c2_ = 0;
4185 __c1_ = 0;
4186 __c0_ = 0;
4187 __c_ = 0;
4188 }
4189 else
4190 {
4191 __s_ = _STD::sqrt(__mean_);
4192 __d_ = 6 * __mean_ * __mean_;
4193 __l_ = static_cast<result_type>(__mean_ - 1.1484);
4194 __omega_ = .3989423 / __s_;
4195 double __b1_ = .4166667E-1 / __mean_;
4196 double __b2_ = .3 * __b1_ * __b1_;
4197 __c3_ = .1428571 * __b1_ * __b2_;
4198 __c2_ = __b2_ - 15. * __c3_;
4199 __c1_ = __b1_ - 6. * __b2_ + 45. * __c3_;
4200 __c0_ = 1. - __b1_ + 3. * __b2_ - 15. * __c3_;
4201 __c_ = .1069 / __mean_;
4202 }
4203}
4204
4205template <class _IntType>
4206template<class _URNG>
4207_IntType
4208poisson_distribution<_IntType>::operator()(_URNG& __urng, const param_type& __pr)
4209{
4210 result_type __x;
4211 uniform_real_distribution<double> __urd;
4212 if (__pr.__mean_ <= 10)
4213 {
4214 __x = 0;
4215 for (double __p = __urd(__urng); __p > __pr.__l_; ++__x)
4216 __p *= __urd(__urng);
4217 }
4218 else
4219 {
4220 double __difmuk;
4221 double __g = __pr.__mean_ + __pr.__s_ * normal_distribution<double>()(__urng);
4222 double __u;
4223 if (__g > 0)
4224 {
4225 __x = static_cast<result_type>(__g);
4226 if (__x >= __pr.__l_)
4227 return __x;
4228 __difmuk = __pr.__mean_ - __x;
4229 __u = __urd(__urng);
4230 if (__pr.__d_ * __u >= __difmuk * __difmuk * __difmuk)
4231 return __x;
4232 }
4233 exponential_distribution<double> __edist;
4234 for (bool __using_exp_dist = false; true; __using_exp_dist = true)
4235 {
4236 double __e;
4237 if (__using_exp_dist || __g < 0)
4238 {
4239 double __t;
4240 do
4241 {
4242 __e = __edist(__urng);
4243 __u = __urd(__urng);
4244 __u += __u - 1;
4245 __t = 1.8 + (__u < 0 ? -__e : __e);
4246 } while (__t <= -.6744);
4247 __x = __pr.__mean_ + __pr.__s_ * __t;
4248 __difmuk = __pr.__mean_ - __x;
4249 __using_exp_dist = true;
4250 }
4251 double __px;
4252 double __py;
4253 if (__x < 10)
4254 {
4255 const result_type __fac[] = {1, 1, 2, 6, 24, 120, 720, 5040,
4256 40320, 362880};
4257 __px = -__pr.__mean_;
4258 __py = _STD::pow(__pr.__mean_, (double)__x) / __fac[__x];
4259 }
4260 else
4261 {
4262 double __del = .8333333E-1 / __x;
4263 __del -= 4.8 * __del * __del * __del;
4264 double __v = __difmuk / __x;
4265 if (_STD::abs(__v) > 0.25)
4266 __px = __x * _STD::log(1 + __v) - __difmuk - __del;
4267 else
4268 __px = __x * __v * __v * (((((((.1250060 * __v + -.1384794) *
4269 __v + .1421878) * __v + -.1661269) * __v + .2000118) *
4270 __v + -.2500068) * __v + .3333333) * __v + -.5) - __del;
4271 __py = .3989423 / _STD::sqrt(__x);
4272 }
4273 double __r = (0.5 - __difmuk) / __pr.__s_;
4274 double __r2 = __r * __r;
4275 double __fx = -0.5 * __r2;
4276 double __fy = __pr.__omega_ * (((__pr.__c3_ * __r2 + __pr.__c2_) *
4277 __r2 + __pr.__c1_) * __r2 + __pr.__c0_);
4278 if (__using_exp_dist)
4279 {
4280 if (__pr.__c_ * _STD::abs(__u) <= __py * _STD::exp(__px + __e) -
4281 __fy * _STD::exp(__fx + __e))
4282 break;
4283 }
4284 else
4285 {
4286 if (__fy - __u * __fy <= __py * _STD::exp(__px - __fx))
4287 break;
4288 }
4289 }
4290 }
4291 return __x;
4292}
4293
4294template <class _CharT, class _Traits, class _IntType>
4295basic_ostream<_CharT, _Traits>&
4296operator<<(basic_ostream<_CharT, _Traits>& __os,
4297 const poisson_distribution<_IntType>& __x)
4298{
4299 __save_flags<_CharT, _Traits> _(__os);
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]4300 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
4301 ios_base::scientific);
Howard Hinnant6add8dd2010-05-15 21:36:23 +0000[diff] [blame]4302 return __os << __x.mean();
4303}
4304
4305template <class _CharT, class _Traits, class _IntType>
4306basic_istream<_CharT, _Traits>&
4307operator>>(basic_istream<_CharT, _Traits>& __is,
4308 poisson_distribution<_IntType>& __x)
4309{
4310 typedef poisson_distribution<_IntType> _Eng;
4311 typedef typename _Eng::param_type param_type;
4312 __save_flags<_CharT, _Traits> _(__is);
4313 __is.flags(ios_base::dec | ios_base::skipws);
4314 double __mean;
4315 __is >> __mean;
4316 if (!__is.fail())
4317 __x.param(param_type(__mean));
4318 return __is;
4319}
4320
Howard Hinnant9de6e302010-05-16 01:09:02 +0000[diff] [blame]4321// weibull_distribution
4322
4323template<class _RealType = double>
4324class weibull_distribution
4325{
4326public:
4327 // types
4328 typedef _RealType result_type;
4329
4330 class param_type
4331 {
4332 result_type __a_;
4333 result_type __b_;
4334 public:
4335 typedef weibull_distribution distribution_type;
4336
4337 explicit param_type(result_type __a = 1, result_type __b = 1)
4338 : __a_(__a), __b_(__b) {}
4339
4340 result_type a() const {return __a_;}
4341 result_type b() const {return __b_;}
4342
4343 friend bool operator==(const param_type& __x, const param_type& __y)
4344 {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
4345 friend bool operator!=(const param_type& __x, const param_type& __y)
4346 {return !(__x == __y);}
4347 };
4348
4349private:
4350 param_type __p_;
4351
4352public:
4353 // constructor and reset functions
4354 explicit weibull_distribution(result_type __a = 1, result_type __b = 1)
4355 : __p_(param_type(__a, __b)) {}
4356 explicit weibull_distribution(const param_type& __p)
4357 : __p_(__p) {}
4358 void reset() {}
4359
4360 // generating functions
4361 template<class _URNG> result_type operator()(_URNG& __g)
4362 {return (*this)(__g, __p_);}
4363 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p)
4364 {return __p.b() *
4365 _STD::pow(exponential_distribution<result_type>()(__g), 1/__p.a());}
4366
4367 // property functions
4368 result_type a() const {return __p_.a();}
4369 result_type b() const {return __p_.b();}
4370
4371 param_type param() const {return __p_;}
4372 void param(const param_type& __p) {__p_ = __p;}
4373
4374 result_type min() const {return 0;}
4375 result_type max() const {return numeric_limits<result_type>::infinity();}
4376
4377
4378 friend bool operator==(const weibull_distribution& __x,
4379 const weibull_distribution& __y)
4380 {return __x.__p_ == __y.__p_;}
4381 friend bool operator!=(const weibull_distribution& __x,
4382 const weibull_distribution& __y)
4383 {return !(__x == __y);}
4384};
4385
4386template <class _CharT, class _Traits, class _RT>
4387basic_ostream<_CharT, _Traits>&
4388operator<<(basic_ostream<_CharT, _Traits>& __os,
4389 const weibull_distribution<_RT>& __x)
4390{
4391 __save_flags<_CharT, _Traits> _(__os);
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]4392 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
4393 ios_base::scientific);
Howard Hinnant9de6e302010-05-16 01:09:02 +0000[diff] [blame]4394 _CharT __sp = __os.widen(' ');
4395 __os.fill(__sp);
4396 __os << __x.a() << __sp << __x.b();
4397 return __os;
4398}
4399
4400template <class _CharT, class _Traits, class _RT>
4401basic_istream<_CharT, _Traits>&
4402operator>>(basic_istream<_CharT, _Traits>& __is,
4403 weibull_distribution<_RT>& __x)
4404{
4405 typedef weibull_distribution<_RT> _Eng;
4406 typedef typename _Eng::result_type result_type;
4407 typedef typename _Eng::param_type param_type;
4408 __save_flags<_CharT, _Traits> _(__is);
4409 __is.flags(ios_base::dec | ios_base::skipws);
4410 result_type __a;
4411 result_type __b;
4412 __is >> __a >> __b;
4413 if (!__is.fail())
4414 __x.param(param_type(__a, __b));
4415 return __is;
4416}
4417
Howard Hinnantc2b0dc72010-05-17 16:21:56 +0000[diff] [blame]4418template<class _RealType = double>
4419class extreme_value_distribution
4420{
4421public:
4422 // types
4423 typedef _RealType result_type;
4424
4425 class param_type
4426 {
4427 result_type __a_;
4428 result_type __b_;
4429 public:
4430 typedef extreme_value_distribution distribution_type;
4431
4432 explicit param_type(result_type __a = 0, result_type __b = 1)
4433 : __a_(__a), __b_(__b) {}
4434
4435 result_type a() const {return __a_;}
4436 result_type b() const {return __b_;}
4437
4438 friend bool operator==(const param_type& __x, const param_type& __y)
4439 {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
4440 friend bool operator!=(const param_type& __x, const param_type& __y)
4441 {return !(__x == __y);}
4442 };
4443
4444private:
4445 param_type __p_;
4446
4447public:
4448 // constructor and reset functions
4449 explicit extreme_value_distribution(result_type __a = 0, result_type __b = 1)
4450 : __p_(param_type(__a, __b)) {}
4451 explicit extreme_value_distribution(const param_type& __p)
4452 : __p_(__p) {}
4453 void reset() {}
4454
4455 // generating functions
4456 template<class _URNG> result_type operator()(_URNG& __g)
4457 {return (*this)(__g, __p_);}
4458 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
4459
4460 // property functions
4461 result_type a() const {return __p_.a();}
4462 result_type b() const {return __p_.b();}
4463
4464 param_type param() const {return __p_;}
4465 void param(const param_type& __p) {__p_ = __p;}
4466
4467 result_type min() const {return -numeric_limits<result_type>::infinity();}
4468 result_type max() const {return numeric_limits<result_type>::infinity();}
4469
4470 friend bool operator==(const extreme_value_distribution& __x,
4471 const extreme_value_distribution& __y)
4472 {return __x.__p_ == __y.__p_;}
4473 friend bool operator!=(const extreme_value_distribution& __x,
4474 const extreme_value_distribution& __y)
4475 {return !(__x == __y);}
4476};
4477
4478template<class _RealType>
4479template<class _URNG>
4480_RealType
4481extreme_value_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
4482{
4483 return __p.a() - __p.b() *
4484 _STD::log(-_STD::log(1-uniform_real_distribution<result_type>()(__g)));
4485}
4486
4487template <class _CharT, class _Traits, class _RT>
4488basic_ostream<_CharT, _Traits>&
4489operator<<(basic_ostream<_CharT, _Traits>& __os,
4490 const extreme_value_distribution<_RT>& __x)
4491{
4492 __save_flags<_CharT, _Traits> _(__os);
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]4493 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
4494 ios_base::scientific);
Howard Hinnantc2b0dc72010-05-17 16:21:56 +0000[diff] [blame]4495 _CharT __sp = __os.widen(' ');
4496 __os.fill(__sp);
4497 __os << __x.a() << __sp << __x.b();
4498 return __os;
4499}
4500
4501template <class _CharT, class _Traits, class _RT>
4502basic_istream<_CharT, _Traits>&
4503operator>>(basic_istream<_CharT, _Traits>& __is,
4504 extreme_value_distribution<_RT>& __x)
4505{
4506 typedef extreme_value_distribution<_RT> _Eng;
4507 typedef typename _Eng::result_type result_type;
4508 typedef typename _Eng::param_type param_type;
4509 __save_flags<_CharT, _Traits> _(__is);
4510 __is.flags(ios_base::dec | ios_base::skipws);
4511 result_type __a;
4512 result_type __b;
4513 __is >> __a >> __b;
4514 if (!__is.fail())
4515 __x.param(param_type(__a, __b));
4516 return __is;
4517}
4518
Howard Hinnantc7c49132010-05-13 17:58:28 +0000[diff] [blame]4519// gamma_distribution
4520
4521template<class _RealType = double>
4522class gamma_distribution
4523{
4524public:
4525 // types
4526 typedef _RealType result_type;
4527
4528 class param_type
4529 {
4530 result_type __alpha_;
4531 result_type __beta_;
4532 public:
4533 typedef gamma_distribution distribution_type;
4534
4535 explicit param_type(result_type __alpha = 1, result_type __beta = 1)
4536 : __alpha_(__alpha), __beta_(__beta) {}
4537
4538 result_type alpha() const {return __alpha_;}
4539 result_type beta() const {return __beta_;}
4540
4541 friend bool operator==(const param_type& __x, const param_type& __y)
4542 {return __x.__alpha_ == __y.__alpha_ && __x.__beta_ == __y.__beta_;}
4543 friend bool operator!=(const param_type& __x, const param_type& __y)
4544 {return !(__x == __y);}
4545 };
4546
4547private:
4548 param_type __p_;
4549
4550public:
4551 // constructors and reset functions
4552 explicit gamma_distribution(result_type __alpha = 1, result_type __beta = 1)
4553 : __p_(param_type(__alpha, __beta)) {}
4554 explicit gamma_distribution(const param_type& __p)
4555 : __p_(__p) {}
4556 void reset() {}
4557
4558 // generating functions
4559 template<class _URNG> result_type operator()(_URNG& __g)
4560 {return (*this)(__g, __p_);}
4561 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
4562
4563 // property functions
4564 result_type alpha() const {return __p_.alpha();}
4565 result_type beta() const {return __p_.beta();}
4566
4567 param_type param() const {return __p_;}
4568 void param(const param_type& __p) {__p_ = __p;}
4569
4570 result_type min() const {return 0;}
4571 result_type max() const {return numeric_limits<result_type>::infinity();}
4572
4573 friend bool operator==(const gamma_distribution& __x,
4574 const gamma_distribution& __y)
4575 {return __x.__p_ == __y.__p_;}
4576 friend bool operator!=(const gamma_distribution& __x,
4577 const gamma_distribution& __y)
4578 {return !(__x == __y);}
4579};
4580
4581template <class _RealType>
4582template<class _URNG>
4583_RealType
4584gamma_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
4585{
Howard Hinnantf417abe2010-05-14 18:43:10 +0000[diff] [blame]4586 result_type __a = __p.alpha();
4587 uniform_real_distribution<result_type> __gen(0, 1);
4588 exponential_distribution<result_type> __egen;
4589 result_type __x;
Howard Hinnantc7c49132010-05-13 17:58:28 +0000[diff] [blame]4590 if (__a == 1)
Howard Hinnantf417abe2010-05-14 18:43:10 +0000[diff] [blame]4591 __x = __egen(__g);
Howard Hinnantc7c49132010-05-13 17:58:28 +0000[diff] [blame]4592 else if (__a > 1)
4593 {
4594 const result_type __b = __a - 1;
4595 const result_type __c = 3 * __a - result_type(0.75);
Howard Hinnantc7c49132010-05-13 17:58:28 +0000[diff] [blame]4596 while (true)
4597 {
4598 const result_type __u = __gen(__g);
4599 const result_type __v = __gen(__g);
4600 const result_type __w = __u * (1 - __u);
Howard Hinnantf417abe2010-05-14 18:43:10 +0000[diff] [blame]4601 if (__w != 0)
Howard Hinnantc7c49132010-05-13 17:58:28 +0000[diff] [blame]4602 {
4603 const result_type __y = _STD::sqrt(__c / __w) *
4604 (__u - result_type(0.5));
4605 __x = __b + __y;
4606 if (__x >= 0)
4607 {
4608 const result_type __z = 64 * __w * __w * __w * __v * __v;
4609 if (__z <= 1 - 2 * __y * __y / __x)
4610 break;
4611 if (_STD::log(__z) <= 2 * (__b * _STD::log(__x / __b) - __y))
4612 break;
4613 }
4614 }
4615 }
Howard Hinnantc7c49132010-05-13 17:58:28 +0000[diff] [blame]4616 }
Howard Hinnantf417abe2010-05-14 18:43:10 +0000[diff] [blame]4617 else // __a < 1
4618 {
4619 while (true)
4620 {
4621 const result_type __u = __gen(__g);
4622 const result_type __es = __egen(__g);
4623 if (__u <= 1 - __a)
4624 {
4625 __x = _STD::pow(__u, 1 / __a);
4626 if (__x <= __es)
4627 break;
4628 }
4629 else
4630 {
4631 const result_type __e = -_STD::log((1-__u)/__a);
4632 __x = _STD::pow(1 - __a + __a * __e, 1 / __a);
4633 if (__x <= __e + __es)
4634 break;
4635 }
4636 }
4637 }
4638 return __x * __p.beta();
Howard Hinnantc7c49132010-05-13 17:58:28 +0000[diff] [blame]4639}
4640
4641template <class _CharT, class _Traits, class _RT>
4642basic_ostream<_CharT, _Traits>&
4643operator<<(basic_ostream<_CharT, _Traits>& __os,
4644 const gamma_distribution<_RT>& __x)
4645{
4646 __save_flags<_CharT, _Traits> _(__os);
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]4647 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
4648 ios_base::scientific);
Howard Hinnantc7c49132010-05-13 17:58:28 +0000[diff] [blame]4649 _CharT __sp = __os.widen(' ');
4650 __os.fill(__sp);
4651 __os << __x.alpha() << __sp << __x.beta();
4652 return __os;
4653}
4654
4655template <class _CharT, class _Traits, class _RT>
4656basic_istream<_CharT, _Traits>&
4657operator>>(basic_istream<_CharT, _Traits>& __is,
4658 gamma_distribution<_RT>& __x)
4659{
4660 typedef gamma_distribution<_RT> _Eng;
4661 typedef typename _Eng::result_type result_type;
4662 typedef typename _Eng::param_type param_type;
4663 __save_flags<_CharT, _Traits> _(__is);
4664 __is.flags(ios_base::dec | ios_base::skipws);
4665 result_type __alpha;
4666 result_type __beta;
4667 __is >> __alpha >> __beta;
4668 if (!__is.fail())
4669 __x.param(param_type(__alpha, __beta));
4670 return __is;
4671}
Howard Hinnanta64111c2010-05-12 21:02:31 +0000[diff] [blame]4672
Howard Hinnantf2fe5d52010-05-17 00:09:38 +0000[diff] [blame]4673// negative_binomial_distribution
4674
4675template<class _IntType = int>
4676class negative_binomial_distribution
4677{
4678public:
4679 // types
4680 typedef _IntType result_type;
4681
4682 class param_type
4683 {
4684 result_type __k_;
4685 double __p_;
4686 public:
4687 typedef negative_binomial_distribution distribution_type;
4688
4689 explicit param_type(result_type __k = 1, double __p = 0.5)
4690 : __k_(__k), __p_(__p) {}
4691
4692 result_type k() const {return __k_;}
4693 double p() const {return __p_;}
4694
4695 friend bool operator==(const param_type& __x, const param_type& __y)
4696 {return __x.__k_ == __y.__k_ && __x.__p_ == __y.__p_;}
4697 friend bool operator!=(const param_type& __x, const param_type& __y)
4698 {return !(__x == __y);}
4699 };
4700
4701private:
4702 param_type __p_;
4703
4704public:
4705 // constructor and reset functions
4706 explicit negative_binomial_distribution(result_type __k = 1, double __p = 0.5)
4707 : __p_(__k, __p) {}
4708 explicit negative_binomial_distribution(const param_type& __p) : __p_(__p) {}
4709 void reset() {}
4710
4711 // generating functions
4712 template<class _URNG> result_type operator()(_URNG& __g)
4713 {return (*this)(__g, __p_);}
4714 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
4715
4716 // property functions
4717 result_type k() const {return __p_.k();}
4718 double p() const {return __p_.p();}
4719
4720 param_type param() const {return __p_;}
4721 void param(const param_type& __p) {__p_ = __p;}
4722
4723 result_type min() const {return 0;}
4724 result_type max() const {return numeric_limits<result_type>::max();}
4725
4726 friend bool operator==(const negative_binomial_distribution& __x,
4727 const negative_binomial_distribution& __y)
4728 {return __x.__p_ == __y.__p_;}
4729 friend bool operator!=(const negative_binomial_distribution& __x,
4730 const negative_binomial_distribution& __y)
4731 {return !(__x == __y);}
4732};
4733
4734template <class _IntType>
4735template<class _URNG>
4736_IntType
4737negative_binomial_distribution<_IntType>::operator()(_URNG& __urng, const param_type& __pr)
4738{
4739 result_type __k = __pr.k();
4740 double __p = __pr.p();
4741 if (__k <= 21 * __p)
4742 {
4743 bernoulli_distribution __gen(__p);
4744 result_type __f = 0;
4745 result_type __s = 0;
4746 while (__s < __k)
4747 {
4748 if (__gen(__urng))
4749 ++__s;
4750 else
4751 ++__f;
4752 }
4753 return __f;
4754 }
4755 return poisson_distribution<result_type>(gamma_distribution<double>
4756 (__k, (1-__p)/__p)(__urng))(__urng);
4757}
4758
4759template <class _CharT, class _Traits, class _IntType>
4760basic_ostream<_CharT, _Traits>&
4761operator<<(basic_ostream<_CharT, _Traits>& __os,
4762 const negative_binomial_distribution<_IntType>& __x)
4763{
4764 __save_flags<_CharT, _Traits> _(__os);
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]4765 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
4766 ios_base::scientific);
Howard Hinnantf2fe5d52010-05-17 00:09:38 +0000[diff] [blame]4767 _CharT __sp = __os.widen(' ');
4768 __os.fill(__sp);
4769 return __os << __x.k() << __sp << __x.p();
4770}
4771
4772template <class _CharT, class _Traits, class _IntType>
4773basic_istream<_CharT, _Traits>&
4774operator>>(basic_istream<_CharT, _Traits>& __is,
4775 negative_binomial_distribution<_IntType>& __x)
4776{
4777 typedef negative_binomial_distribution<_IntType> _Eng;
4778 typedef typename _Eng::result_type result_type;
4779 typedef typename _Eng::param_type param_type;
4780 __save_flags<_CharT, _Traits> _(__is);
4781 __is.flags(ios_base::dec | ios_base::skipws);
4782 result_type __k;
4783 double __p;
4784 __is >> __k >> __p;
4785 if (!__is.fail())
4786 __x.param(param_type(__k, __p));
4787 return __is;
4788}
4789
Howard Hinnant34e8a572010-05-17 13:44:27 +0000[diff] [blame]4790// geometric_distribution
4791
4792template<class _IntType = int>
4793class geometric_distribution
4794{
4795public:
4796 // types
4797 typedef _IntType result_type;
4798
4799 class param_type
4800 {
4801 double __p_;
4802 public:
4803 typedef geometric_distribution distribution_type;
4804
4805 explicit param_type(double __p = 0.5) : __p_(__p) {}
4806
4807 double p() const {return __p_;}
4808
4809 friend bool operator==(const param_type& __x, const param_type& __y)
4810 {return __x.__p_ == __y.__p_;}
4811 friend bool operator!=(const param_type& __x, const param_type& __y)
4812 {return !(__x == __y);}
4813 };
4814
4815private:
4816 param_type __p_;
4817
4818public:
4819 // constructors and reset functions
4820 explicit geometric_distribution(double __p = 0.5) : __p_(__p) {}
4821 explicit geometric_distribution(const param_type& __p) : __p_(__p) {}
4822 void reset() {}
4823
4824 // generating functions
4825 template<class _URNG> result_type operator()(_URNG& __g)
4826 {return (*this)(__g, __p_);}
4827 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p)
4828 {return negative_binomial_distribution<result_type>(1, __p.p())(__g);}
4829
4830 // property functions
4831 double p() const {return __p_.p();}
4832
4833 param_type param() const {return __p_;}
4834 void param(const param_type& __p) {__p_ = __p;}
4835
4836 result_type min() const {return 0;}
4837 result_type max() const {return numeric_limits<result_type>::max();}
4838
4839 friend bool operator==(const geometric_distribution& __x,
4840 const geometric_distribution& __y)
4841 {return __x.__p_ == __y.__p_;}
4842 friend bool operator!=(const geometric_distribution& __x,
4843 const geometric_distribution& __y)
4844 {return !(__x == __y);}
4845};
4846
4847template <class _CharT, class _Traits, class _IntType>
4848basic_ostream<_CharT, _Traits>&
4849operator<<(basic_ostream<_CharT, _Traits>& __os,
4850 const geometric_distribution<_IntType>& __x)
4851{
4852 __save_flags<_CharT, _Traits> _(__os);
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]4853 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
4854 ios_base::scientific);
Howard Hinnant34e8a572010-05-17 13:44:27 +0000[diff] [blame]4855 return __os << __x.p();
4856}
4857
4858template <class _CharT, class _Traits, class _IntType>
4859basic_istream<_CharT, _Traits>&
4860operator>>(basic_istream<_CharT, _Traits>& __is,
4861 geometric_distribution<_IntType>& __x)
4862{
4863 typedef geometric_distribution<_IntType> _Eng;
4864 typedef typename _Eng::param_type param_type;
4865 __save_flags<_CharT, _Traits> _(__is);
4866 __is.flags(ios_base::dec | ios_base::skipws);
4867 double __p;
4868 __is >> __p;
4869 if (!__is.fail())
4870 __x.param(param_type(__p));
4871 return __is;
4872}
4873
Howard Hinnant97dc2f32010-05-15 23:36:00 +0000[diff] [blame]4874// chi_squared_distribution
4875
4876template<class _RealType = double>
4877class chi_squared_distribution
4878{
4879public:
4880 // types
4881 typedef _RealType result_type;
4882
4883 class param_type
4884 {
4885 result_type __n_;
4886 public:
4887 typedef chi_squared_distribution distribution_type;
4888
4889 explicit param_type(result_type __n = 1) : __n_(__n) {}
4890
4891 result_type n() const {return __n_;}
4892
4893 friend bool operator==(const param_type& __x, const param_type& __y)
4894 {return __x.__n_ == __y.__n_;}
4895 friend bool operator!=(const param_type& __x, const param_type& __y)
4896 {return !(__x == __y);}
4897 };
4898
4899private:
4900 param_type __p_;
4901
4902public:
4903 // constructor and reset functions
4904 explicit chi_squared_distribution(result_type __n = 1)
4905 : __p_(param_type(__n)) {}
4906 explicit chi_squared_distribution(const param_type& __p)
4907 : __p_(__p) {}
4908 void reset() {}
4909
4910 // generating functions
4911 template<class _URNG> result_type operator()(_URNG& __g)
4912 {return (*this)(__g, __p_);}
4913 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p)
4914 {return gamma_distribution<result_type>(__p.n() / 2, 2)(__g);}
4915
4916 // property functions
4917 result_type n() const {return __p_.n();}
4918
4919 param_type param() const {return __p_;}
4920 void param(const param_type& __p) {__p_ = __p;}
4921
4922 result_type min() const {return 0;}
4923 result_type max() const {return numeric_limits<result_type>::infinity();}
4924
4925
4926 friend bool operator==(const chi_squared_distribution& __x,
4927 const chi_squared_distribution& __y)
4928 {return __x.__p_ == __y.__p_;}
4929 friend bool operator!=(const chi_squared_distribution& __x,
4930 const chi_squared_distribution& __y)
4931 {return !(__x == __y);}
4932};
4933
4934template <class _CharT, class _Traits, class _RT>
4935basic_ostream<_CharT, _Traits>&
4936operator<<(basic_ostream<_CharT, _Traits>& __os,
4937 const chi_squared_distribution<_RT>& __x)
4938{
4939 __save_flags<_CharT, _Traits> _(__os);
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]4940 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
4941 ios_base::scientific);
Howard Hinnant97dc2f32010-05-15 23:36:00 +0000[diff] [blame]4942 __os << __x.n();
4943 return __os;
4944}
4945
4946template <class _CharT, class _Traits, class _RT>
4947basic_istream<_CharT, _Traits>&
4948operator>>(basic_istream<_CharT, _Traits>& __is,
4949 chi_squared_distribution<_RT>& __x)
4950{
4951 typedef chi_squared_distribution<_RT> _Eng;
4952 typedef typename _Eng::result_type result_type;
4953 typedef typename _Eng::param_type param_type;
4954 __save_flags<_CharT, _Traits> _(__is);
4955 __is.flags(ios_base::dec | ios_base::skipws);
4956 result_type __n;
4957 __is >> __n;
4958 if (!__is.fail())
4959 __x.param(param_type(__n));
4960 return __is;
4961}
4962
Howard Hinnantd7d01132010-05-17 21:55:46 +0000[diff] [blame]4963// cauchy_distribution
4964
4965template<class _RealType = double>
4966class cauchy_distribution
4967{
4968public:
4969 // types
4970 typedef _RealType result_type;
4971
4972 class param_type
4973 {
4974 result_type __a_;
4975 result_type __b_;
4976 public:
4977 typedef cauchy_distribution distribution_type;
4978
4979 explicit param_type(result_type __a = 0, result_type __b = 1)
4980 : __a_(__a), __b_(__b) {}
4981
4982 result_type a() const {return __a_;}
4983 result_type b() const {return __b_;}
4984
4985 friend bool operator==(const param_type& __x, const param_type& __y)
4986 {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
4987 friend bool operator!=(const param_type& __x, const param_type& __y)
4988 {return !(__x == __y);}
4989 };
4990
4991private:
4992 param_type __p_;
4993
4994public:
4995 // constructor and reset functions
4996 explicit cauchy_distribution(result_type __a = 0, result_type __b = 1)
4997 : __p_(param_type(__a, __b)) {}
4998 explicit cauchy_distribution(const param_type& __p)
4999 : __p_(__p) {}
5000 void reset() {}
5001
5002 // generating functions
5003 template<class _URNG> result_type operator()(_URNG& __g)
5004 {return (*this)(__g, __p_);}
5005 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
5006
5007 // property functions
5008 result_type a() const {return __p_.a();}
5009 result_type b() const {return __p_.b();}
5010
5011 param_type param() const {return __p_;}
5012 void param(const param_type& __p) {__p_ = __p;}
5013
5014 result_type min() const {return -numeric_limits<result_type>::infinity();}
5015 result_type max() const {return numeric_limits<result_type>::infinity();}
5016
5017 friend bool operator==(const cauchy_distribution& __x,
5018 const cauchy_distribution& __y)
5019 {return __x.__p_ == __y.__p_;}
5020 friend bool operator!=(const cauchy_distribution& __x,
5021 const cauchy_distribution& __y)
5022 {return !(__x == __y);}
Howard Hinnantd7d01132010-05-17 21:55:46 +0000[diff] [blame]5023};
5024
5025template <class _RealType>
5026template<class _URNG>
5027inline
5028_RealType
5029cauchy_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
5030{
5031 uniform_real_distribution<result_type> __gen;
5032 // purposefully let tan arg get as close to pi/2 as it wants, tan will return a finite
5033 return __p.a() + __p.b() * _STD::tan(3.1415926535897932384626433832795 * __gen(__g));
5034}
5035
5036template <class _CharT, class _Traits, class _RT>
5037basic_ostream<_CharT, _Traits>&
5038operator<<(basic_ostream<_CharT, _Traits>& __os,
5039 const cauchy_distribution<_RT>& __x)
5040{
5041 __save_flags<_CharT, _Traits> _(__os);
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]5042 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
5043 ios_base::scientific);
Howard Hinnantd7d01132010-05-17 21:55:46 +0000[diff] [blame]5044 _CharT __sp = __os.widen(' ');
5045 __os.fill(__sp);
5046 __os << __x.a() << __sp << __x.b();
5047 return __os;
5048}
5049
5050template <class _CharT, class _Traits, class _RT>
5051basic_istream<_CharT, _Traits>&
5052operator>>(basic_istream<_CharT, _Traits>& __is,
5053 cauchy_distribution<_RT>& __x)
5054{
5055 typedef cauchy_distribution<_RT> _Eng;
5056 typedef typename _Eng::result_type result_type;
5057 typedef typename _Eng::param_type param_type;
5058 __save_flags<_CharT, _Traits> _(__is);
5059 __is.flags(ios_base::dec | ios_base::skipws);
5060 result_type __a;
5061 result_type __b;
5062 __is >> __a >> __b;
5063 if (!__is.fail())
5064 __x.param(param_type(__a, __b));
5065 return __is;
5066}
5067
Howard Hinnantd8bc09b2010-05-18 17:32:30 +0000[diff] [blame]5068// fisher_f_distribution
5069
5070template<class _RealType = double>
5071class fisher_f_distribution
5072{
5073public:
5074 // types
5075 typedef _RealType result_type;
5076
5077 class param_type
5078 {
5079 result_type __m_;
5080 result_type __n_;
5081 public:
5082 typedef fisher_f_distribution distribution_type;
5083
5084 explicit param_type(result_type __m = 1, result_type __n = 1)
5085 : __m_(__m), __n_(__n) {}
5086
5087 result_type m() const {return __m_;}
5088 result_type n() const {return __n_;}
5089
5090 friend bool operator==(const param_type& __x, const param_type& __y)
5091 {return __x.__m_ == __y.__m_ && __x.__n_ == __y.__n_;}
5092 friend bool operator!=(const param_type& __x, const param_type& __y)
5093 {return !(__x == __y);}
5094 };
5095
5096private:
5097 param_type __p_;
5098
5099public:
5100 // constructor and reset functions
5101 explicit fisher_f_distribution(result_type __m = 1, result_type __n = 1)
5102 : __p_(param_type(__m, __n)) {}
5103 explicit fisher_f_distribution(const param_type& __p)
5104 : __p_(__p) {}
5105 void reset() {}
5106
5107 // generating functions
5108 template<class _URNG> result_type operator()(_URNG& __g)
5109 {return (*this)(__g, __p_);}
5110 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
5111
5112 // property functions
5113 result_type m() const {return __p_.m();}
5114 result_type n() const {return __p_.n();}
5115
5116 param_type param() const {return __p_;}
5117 void param(const param_type& __p) {__p_ = __p;}
5118
5119 result_type min() const {return 0;}
5120 result_type max() const {return numeric_limits<result_type>::infinity();}
5121
5122 friend bool operator==(const fisher_f_distribution& __x,
5123 const fisher_f_distribution& __y)
5124 {return __x.__p_ == __y.__p_;}
5125 friend bool operator!=(const fisher_f_distribution& __x,
5126 const fisher_f_distribution& __y)
5127 {return !(__x == __y);}
5128};
5129
5130template <class _RealType>
5131template<class _URNG>
5132_RealType
5133fisher_f_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
5134{
5135 gamma_distribution<result_type> __gdm(__p.m() * result_type(.5));
5136 gamma_distribution<result_type> __gdn(__p.n() * result_type(.5));
5137 return __p.n() * __gdm(__g) / (__p.m() * __gdn(__g));
5138}
5139
5140template <class _CharT, class _Traits, class _RT>
5141basic_ostream<_CharT, _Traits>&
5142operator<<(basic_ostream<_CharT, _Traits>& __os,
5143 const fisher_f_distribution<_RT>& __x)
5144{
5145 __save_flags<_CharT, _Traits> _(__os);
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]5146 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
5147 ios_base::scientific);
Howard Hinnantd8bc09b2010-05-18 17:32:30 +0000[diff] [blame]5148 _CharT __sp = __os.widen(' ');
5149 __os.fill(__sp);
5150 __os << __x.m() << __sp << __x.n();
5151 return __os;
5152}
5153
5154template <class _CharT, class _Traits, class _RT>
5155basic_istream<_CharT, _Traits>&
5156operator>>(basic_istream<_CharT, _Traits>& __is,
5157 fisher_f_distribution<_RT>& __x)
5158{
5159 typedef fisher_f_distribution<_RT> _Eng;
5160 typedef typename _Eng::result_type result_type;
5161 typedef typename _Eng::param_type param_type;
5162 __save_flags<_CharT, _Traits> _(__is);
5163 __is.flags(ios_base::dec | ios_base::skipws);
5164 result_type __m;
5165 result_type __n;
5166 __is >> __m >> __n;
5167 if (!__is.fail())
5168 __x.param(param_type(__m, __n));
5169 return __is;
5170}
5171
Howard Hinnant551d8e42010-05-19 01:53:57 +0000[diff] [blame]5172// student_t_distribution
5173
Howard Hinnant321b4bb2010-05-18 20:08:04 +0000[diff] [blame]5174template<class _RealType = double>
5175class student_t_distribution
5176{
5177public:
5178 // types
5179 typedef _RealType result_type;
5180
5181 class param_type
5182 {
5183 result_type __n_;
5184 public:
5185 typedef student_t_distribution distribution_type;
5186
5187 explicit param_type(result_type __n = 1) : __n_(__n) {}
5188
5189 result_type n() const {return __n_;}
5190
5191 friend bool operator==(const param_type& __x, const param_type& __y)
5192 {return __x.__n_ == __y.__n_;}
5193 friend bool operator!=(const param_type& __x, const param_type& __y)
5194 {return !(__x == __y);}
5195 };
5196
5197private:
5198 param_type __p_;
5199 normal_distribution<result_type> __nd_;
5200
5201public:
5202 // constructor and reset functions
5203 explicit student_t_distribution(result_type __n = 1)
5204 : __p_(param_type(__n)) {}
5205 explicit student_t_distribution(const param_type& __p)
5206 : __p_(__p) {}
5207 void reset() {__nd_.reset();}
5208
5209 // generating functions
5210 template<class _URNG> result_type operator()(_URNG& __g)
5211 {return (*this)(__g, __p_);}
5212 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
5213
5214 // property functions
5215 result_type n() const {return __p_.n();}
5216
5217 param_type param() const {return __p_;}
Howard Hinnant551d8e42010-05-19 01:53:57 +0000[diff] [blame]5218 void param(const param_type& __p) {__p_ = __p;}
Howard Hinnant321b4bb2010-05-18 20:08:04 +0000[diff] [blame]5219
5220 result_type min() const {return -numeric_limits<result_type>::infinity();}
5221 result_type max() const {return numeric_limits<result_type>::infinity();}
5222
5223 friend bool operator==(const student_t_distribution& __x,
5224 const student_t_distribution& __y)
5225 {return __x.__p_ == __y.__p_;}
5226 friend bool operator!=(const student_t_distribution& __x,
5227 const student_t_distribution& __y)
5228 {return !(__x == __y);}
5229};
5230
5231template <class _RealType>
5232template<class _URNG>
5233_RealType
5234student_t_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
5235{
5236 gamma_distribution<result_type> __gd(__p.n() * .5, 2);
5237 return __nd_(__g) * _STD::sqrt(__p.n()/__gd(__g));
5238}
5239
5240template <class _CharT, class _Traits, class _RT>
5241basic_ostream<_CharT, _Traits>&
5242operator<<(basic_ostream<_CharT, _Traits>& __os,
5243 const student_t_distribution<_RT>& __x)
5244{
5245 __save_flags<_CharT, _Traits> _(__os);
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]5246 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
5247 ios_base::scientific);
Howard Hinnant321b4bb2010-05-18 20:08:04 +0000[diff] [blame]5248 __os << __x.n();
5249 return __os;
5250}
5251
5252template <class _CharT, class _Traits, class _RT>
5253basic_istream<_CharT, _Traits>&
5254operator>>(basic_istream<_CharT, _Traits>& __is,
5255 student_t_distribution<_RT>& __x)
5256{
5257 typedef student_t_distribution<_RT> _Eng;
5258 typedef typename _Eng::result_type result_type;
5259 typedef typename _Eng::param_type param_type;
5260 __save_flags<_CharT, _Traits> _(__is);
5261 __is.flags(ios_base::dec | ios_base::skipws);
5262 result_type __n;
5263 __is >> __n;
5264 if (!__is.fail())
5265 __x.param(param_type(__n));
5266 return __is;
5267}
5268
Howard Hinnant551d8e42010-05-19 01:53:57 +0000[diff] [blame]5269// discrete_distribution
5270
5271template<class _IntType = int>
5272class discrete_distribution
5273{
5274public:
5275 // types
5276 typedef _IntType result_type;
5277
5278 class param_type
5279 {
5280 vector<double> __p_;
5281 public:
5282 typedef discrete_distribution distribution_type;
5283
5284 param_type() {}
5285 template<class _InputIterator>
5286 param_type(_InputIterator __f, _InputIterator __l)
5287 : __p_(__f, __l) {__init();}
5288 param_type(initializer_list<double> __wl)
5289 : __p_(__wl.begin(), __wl.end()) {__init();}
5290 template<class _UnaryOperation>
5291 param_type(size_t __nw, double __xmin, double __xmax,
5292 _UnaryOperation __fw);
5293
5294 vector<double> probabilities() const;
5295
5296 friend bool operator==(const param_type& __x, const param_type& __y)
5297 {return __x.__p_ == __y.__p_;}
5298 friend bool operator!=(const param_type& __x, const param_type& __y)
5299 {return !(__x == __y);}
5300
5301 private:
5302 void __init();
5303
5304 friend class discrete_distribution;
5305
5306 template <class _CharT, class _Traits, class _IT>
5307 friend
5308 basic_ostream<_CharT, _Traits>&
5309 operator<<(basic_ostream<_CharT, _Traits>& __os,
5310 const discrete_distribution<_IT>& __x);
5311
5312 template <class _CharT, class _Traits, class _IT>
5313 friend
5314 basic_istream<_CharT, _Traits>&
5315 operator>>(basic_istream<_CharT, _Traits>& __is,
5316 discrete_distribution<_IT>& __x);
5317 };
5318
5319private:
5320 param_type __p_;
5321
5322public:
5323 // constructor and reset functions
5324 discrete_distribution() {}
5325 template<class _InputIterator>
5326 discrete_distribution(_InputIterator __f, _InputIterator __l)
5327 : __p_(__f, __l) {}
5328 discrete_distribution(initializer_list<double> __wl)
5329 : __p_(__wl) {}
5330 template<class _UnaryOperation>
5331 discrete_distribution(size_t __nw, double __xmin, double __xmax,
5332 _UnaryOperation __fw)
5333 : __p_(__nw, __xmin, __xmax, __fw) {}
5334 explicit discrete_distribution(const param_type& __p)
5335 : __p_(__p) {}
5336 void reset() {}
5337
5338 // generating functions
5339 template<class _URNG> result_type operator()(_URNG& __g)
5340 {return (*this)(__g, __p_);}
5341 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
5342
5343 // property functions
5344 vector<double> probabilities() const {return __p_.probabilities();}
5345
5346 param_type param() const {return __p_;}
5347 void param(const param_type& __p) {__p_ = __p;}
5348
5349 result_type min() const {return 0;}
5350 result_type max() const {return __p_.__p_.size();}
5351
5352 friend bool operator==(const discrete_distribution& __x,
5353 const discrete_distribution& __y)
5354 {return __x.__p_ == __y.__p_;}
5355 friend bool operator!=(const discrete_distribution& __x,
5356 const discrete_distribution& __y)
5357 {return !(__x == __y);}
5358
5359 template <class _CharT, class _Traits, class _IT>
5360 friend
5361 basic_ostream<_CharT, _Traits>&
5362 operator<<(basic_ostream<_CharT, _Traits>& __os,
5363 const discrete_distribution<_IT>& __x);
5364
5365 template <class _CharT, class _Traits, class _IT>
5366 friend
5367 basic_istream<_CharT, _Traits>&
5368 operator>>(basic_istream<_CharT, _Traits>& __is,
5369 discrete_distribution<_IT>& __x);
5370};
5371
5372template<class _IntType>
5373template<class _UnaryOperation>
5374discrete_distribution<_IntType>::param_type::param_type(size_t __nw,
5375 double __xmin,
5376 double __xmax,
5377 _UnaryOperation __fw)
5378{
5379 if (__nw > 1)
5380 {
5381 __p_.reserve(__nw - 1);
5382 double __d = (__xmax - __xmin) / __nw;
5383 double __d2 = __d / 2;
5384 for (size_t __k = 0; __k < __nw; ++__k)
5385 __p_.push_back(__fw(__xmin + __k * __d + __d2));
5386 __init();
5387 }
5388}
5389
5390template<class _IntType>
5391void
5392discrete_distribution<_IntType>::param_type::__init()
5393{
5394 if (!__p_.empty())
5395 {
5396 if (__p_.size() > 1)
5397 {
5398 double __s = _STD::accumulate(__p_.begin(), __p_.end(), 0.0);
5399 for (_STD::vector<double>::iterator __i = __p_.begin(), __e = __p_.end();
5400 __i < __e; ++__i)
5401 *__i /= __s;
5402 vector<double> __t(__p_.size() - 1);
5403 _STD::partial_sum(__p_.begin(), __p_.end() - 1, __t.begin());
5404 swap(__p_, __t);
5405 }
5406 else
5407 {
5408 __p_.clear();
5409 __p_.shrink_to_fit();
5410 }
5411 }
5412}
5413
5414template<class _IntType>
5415vector<double>
5416discrete_distribution<_IntType>::param_type::probabilities() const
5417{
5418 size_t __n = __p_.size();
5419 _STD::vector<double> __p(__n+1);
5420 _STD::adjacent_difference(__p_.begin(), __p_.end(), __p.begin());
5421 if (__n > 0)
5422 __p[__n] = 1 - __p_[__n-1];
5423 else
5424 __p[0] = 1;
5425 return __p;
5426}
5427
5428template<class _IntType>
5429template<class _URNG>
5430_IntType
5431discrete_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p)
5432{
5433 uniform_real_distribution<double> __gen;
5434 return static_cast<_IntType>(
5435 _STD::upper_bound(__p.__p_.begin(), __p.__p_.end(), __gen(__g)) -
5436 __p.__p_.begin());
5437}
5438
5439template <class _CharT, class _Traits, class _IT>
5440basic_ostream<_CharT, _Traits>&
5441operator<<(basic_ostream<_CharT, _Traits>& __os,
5442 const discrete_distribution<_IT>& __x)
5443{
5444 __save_flags<_CharT, _Traits> _(__os);
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]5445 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
5446 ios_base::scientific);
Howard Hinnant551d8e42010-05-19 01:53:57 +0000[diff] [blame]5447 _CharT __sp = __os.widen(' ');
5448 __os.fill(__sp);
5449 size_t __n = __x.__p_.__p_.size();
5450 __os << __n;
5451 for (size_t __i = 0; __i < __n; ++__i)
5452 __os << __sp << __x.__p_.__p_[__i];
5453 return __os;
5454}
5455
5456template <class _CharT, class _Traits, class _IT>
5457basic_istream<_CharT, _Traits>&
5458operator>>(basic_istream<_CharT, _Traits>& __is,
5459 discrete_distribution<_IT>& __x)
5460{
5461 typedef discrete_distribution<_IT> _Eng;
5462 typedef typename _Eng::result_type result_type;
5463 typedef typename _Eng::param_type param_type;
5464 __save_flags<_CharT, _Traits> _(__is);
5465 __is.flags(ios_base::dec | ios_base::skipws);
5466 size_t __n;
5467 __is >> __n;
Howard Hinnantd6d11712010-05-20 15:11:46 +0000[diff] [blame]5468 vector<double> __p(__n);
Howard Hinnant551d8e42010-05-19 01:53:57 +0000[diff] [blame]5469 for (size_t __i = 0; __i < __n; ++__i)
5470 __is >> __p[__i];
5471 if (!__is.fail())
5472 swap(__x.__p_.__p_, __p);
5473 return __is;
5474}
5475
Howard Hinnantd6d11712010-05-20 15:11:46 +0000[diff] [blame]5476// piecewise_constant_distribution
5477
5478template<class _RealType = double>
5479class piecewise_constant_distribution
5480{
5481public:
5482 // types
5483 typedef _RealType result_type;
5484
5485 class param_type
5486 {
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]5487 typedef typename common_type<double, result_type>::type __area_type;
Howard Hinnantd6d11712010-05-20 15:11:46 +0000[diff] [blame]5488 vector<result_type> __b_;
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]5489 vector<double> __densities_;
5490 vector<__area_type> __areas_;
Howard Hinnantd6d11712010-05-20 15:11:46 +0000[diff] [blame]5491 public:
5492 typedef piecewise_constant_distribution distribution_type;
5493
5494 param_type();
5495 template<class _InputIteratorB, class _InputIteratorW>
5496 param_type(_InputIteratorB __fB, _InputIteratorB __lB,
5497 _InputIteratorW __fW);
5498 template<class _UnaryOperation>
5499 param_type(initializer_list<result_type> __bl, _UnaryOperation __fw);
5500 template<class _UnaryOperation>
5501 param_type(size_t __nw, result_type __xmin, result_type __xmax,
5502 _UnaryOperation __fw);
5503
5504 vector<result_type> intervals() const {return __b_;}
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]5505 vector<double> densities() const {return __densities_;}
Howard Hinnantd6d11712010-05-20 15:11:46 +0000[diff] [blame]5506
5507 friend bool operator==(const param_type& __x, const param_type& __y)
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]5508 {return __x.__densities_ == __y.__densities_ && __x.__b_ == __y.__b_;}
Howard Hinnantd6d11712010-05-20 15:11:46 +0000[diff] [blame]5509 friend bool operator!=(const param_type& __x, const param_type& __y)
5510 {return !(__x == __y);}
5511
5512 private:
5513 void __init();
5514
5515 friend class piecewise_constant_distribution;
5516
5517 template <class _CharT, class _Traits, class _RT>
5518 friend
5519 basic_ostream<_CharT, _Traits>&
5520 operator<<(basic_ostream<_CharT, _Traits>& __os,
5521 const piecewise_constant_distribution<_RT>& __x);
5522
5523 template <class _CharT, class _Traits, class _RT>
5524 friend
5525 basic_istream<_CharT, _Traits>&
5526 operator>>(basic_istream<_CharT, _Traits>& __is,
5527 piecewise_constant_distribution<_RT>& __x);
5528 };
5529
5530private:
5531 param_type __p_;
5532
5533public:
5534 // constructor and reset functions
5535 piecewise_constant_distribution() {}
5536 template<class _InputIteratorB, class _InputIteratorW>
5537 piecewise_constant_distribution(_InputIteratorB __fB,
5538 _InputIteratorB __lB,
5539 _InputIteratorW __fW)
5540 : __p_(__fB, __lB, __fW) {}
5541
5542 template<class _UnaryOperation>
5543 piecewise_constant_distribution(initializer_list<result_type> __bl,
5544 _UnaryOperation __fw)
5545 : __p_(__bl, __fw) {}
5546
5547 template<class _UnaryOperation>
5548 piecewise_constant_distribution(size_t __nw, result_type __xmin,
5549 result_type __xmax, _UnaryOperation __fw)
5550 : __p_(__nw, __xmin, __xmax, __fw) {}
5551
5552 explicit piecewise_constant_distribution(const param_type& __p)
5553 : __p_(__p) {}
5554
5555 void reset() {}
5556
5557 // generating functions
5558 template<class _URNG> result_type operator()(_URNG& __g)
5559 {return (*this)(__g, __p_);}
5560 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
5561
5562 // property functions
5563 vector<result_type> intervals() const {return __p_.intervals();}
5564 vector<double> densities() const {return __p_.densities();}
5565
5566 param_type param() const {return __p_;}
5567 void param(const param_type& __p) {__p_ = __p;}
5568
5569 result_type min() const {return __p_.__b_.front();}
5570 result_type max() const {return __p_.__b_.back();}
5571
5572 friend bool operator==(const piecewise_constant_distribution& __x,
5573 const piecewise_constant_distribution& __y)
5574 {return __x.__p_ == __y.__p_;}
5575 friend bool operator!=(const piecewise_constant_distribution& __x,
5576 const piecewise_constant_distribution& __y)
5577 {return !(__x == __y);}
5578
5579 template <class _CharT, class _Traits, class _RT>
5580 friend
5581 basic_ostream<_CharT, _Traits>&
5582 operator<<(basic_ostream<_CharT, _Traits>& __os,
5583 const piecewise_constant_distribution<_RT>& __x);
5584
5585 template <class _CharT, class _Traits, class _RT>
5586 friend
5587 basic_istream<_CharT, _Traits>&
5588 operator>>(basic_istream<_CharT, _Traits>& __is,
5589 piecewise_constant_distribution<_RT>& __x);
5590};
5591
5592template<class _RealType>
5593void
5594piecewise_constant_distribution<_RealType>::param_type::__init()
5595{
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]5596 // __densities_ contains non-normalized areas
5597 __area_type __total_area = _STD::accumulate(__densities_.begin(),
5598 __densities_.end(),
5599 __area_type());
5600 for (size_t __i = 0; __i < __densities_.size(); ++__i)
5601 __densities_[__i] /= __total_area;
5602 // __densities_ contains normalized areas
5603 __areas_.assign(__densities_.size(), __area_type());
5604 _STD::partial_sum(__densities_.begin(), __densities_.end() - 1,
5605 __areas_.begin() + 1);
5606 // __areas_ contains partial sums of normalized areas: [0, __densities_ - 1]
5607 __densities_.back() = 1 - __areas_.back(); // correct round off error
5608 for (size_t __i = 0; __i < __densities_.size(); ++__i)
5609 __densities_[__i] /= (__b_[__i+1] - __b_[__i]);
5610 // __densities_ now contains __densities_
Howard Hinnantd6d11712010-05-20 15:11:46 +0000[diff] [blame]5611}
5612
5613template<class _RealType>
5614piecewise_constant_distribution<_RealType>::param_type::param_type()
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]5615 : __b_(2),
Howard Hinnant54305402010-05-25 00:27:34 +0000[diff] [blame]5616 __densities_(1, 1.0),
5617 __areas_(1, 0.0)
Howard Hinnantd6d11712010-05-20 15:11:46 +0000[diff] [blame]5618{
5619 __b_[1] = 1;
5620}
5621
5622template<class _RealType>
5623template<class _InputIteratorB, class _InputIteratorW>
5624piecewise_constant_distribution<_RealType>::param_type::param_type(
5625 _InputIteratorB __fB, _InputIteratorB __lB, _InputIteratorW __fW)
5626 : __b_(__fB, __lB)
5627{
5628 if (__b_.size() < 2)
5629 {
5630 __b_.resize(2);
5631 __b_[0] = 0;
5632 __b_[1] = 1;
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]5633 __densities_.assign(1, 1.0);
Howard Hinnant54305402010-05-25 00:27:34 +0000[diff] [blame]5634 __areas_.assign(1, 0.0);
Howard Hinnantd6d11712010-05-20 15:11:46 +0000[diff] [blame]5635 }
5636 else
5637 {
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]5638 __densities_.reserve(__b_.size() - 1);
Howard Hinnantd6d11712010-05-20 15:11:46 +0000[diff] [blame]5639 for (size_t __i = 0; __i < __b_.size() - 1; ++__i, ++__fW)
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]5640 __densities_.push_back(*__fW);
Howard Hinnantd6d11712010-05-20 15:11:46 +0000[diff] [blame]5641 __init();
5642 }
5643}
5644
5645template<class _RealType>
5646template<class _UnaryOperation>
5647piecewise_constant_distribution<_RealType>::param_type::param_type(
5648 initializer_list<result_type> __bl, _UnaryOperation __fw)
5649 : __b_(__bl.begin(), __bl.end())
5650{
5651 if (__b_.size() < 2)
5652 {
5653 __b_.resize(2);
5654 __b_[0] = 0;
5655 __b_[1] = 1;
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]5656 __densities_.assign(1, 1.0);
Howard Hinnant54305402010-05-25 00:27:34 +0000[diff] [blame]5657 __areas_.assign(1, 0.0);
Howard Hinnantd6d11712010-05-20 15:11:46 +0000[diff] [blame]5658 }
5659 else
5660 {
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]5661 __densities_.reserve(__b_.size() - 1);
Howard Hinnantd6d11712010-05-20 15:11:46 +0000[diff] [blame]5662 for (size_t __i = 0; __i < __b_.size() - 1; ++__i)
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]5663 __densities_.push_back(__fw((__b_[__i+1] + __b_[__i])*.5));
Howard Hinnantd6d11712010-05-20 15:11:46 +0000[diff] [blame]5664 __init();
5665 }
5666}
5667
5668template<class _RealType>
5669template<class _UnaryOperation>
5670piecewise_constant_distribution<_RealType>::param_type::param_type(
5671 size_t __nw, result_type __xmin, result_type __xmax, _UnaryOperation __fw)
5672 : __b_(__nw == 0 ? 2 : __nw + 1)
5673{
5674 size_t __n = __b_.size() - 1;
5675 result_type __d = (__xmax - __xmin) / __n;
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]5676 __densities_.reserve(__n);
Howard Hinnantd6d11712010-05-20 15:11:46 +0000[diff] [blame]5677 for (size_t __i = 0; __i < __n; ++__i)
5678 {
5679 __b_[__i] = __xmin + __i * __d;
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]5680 __densities_.push_back(__fw(__b_[__i] + __d*.5));
Howard Hinnantd6d11712010-05-20 15:11:46 +0000[diff] [blame]5681 }
5682 __b_[__n] = __xmax;
5683 __init();
5684}
5685
5686template<class _RealType>
Howard Hinnantd6d11712010-05-20 15:11:46 +0000[diff] [blame]5687template<class _URNG>
5688_RealType
5689piecewise_constant_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
5690{
5691 typedef uniform_real_distribution<result_type> _Gen;
Howard Hinnantd6d11712010-05-20 15:11:46 +0000[diff] [blame]5692 result_type __u = _Gen()(__g);
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]5693 ptrdiff_t __k = _STD::upper_bound(__p.__areas_.begin(), __p.__areas_.end(),
5694 static_cast<double>(__u)) - __p.__areas_.begin() - 1;
5695 return static_cast<result_type>((__u - __p.__areas_[__k]) / __p.__densities_[__k]
5696 + __p.__b_[__k]);
Howard Hinnantd6d11712010-05-20 15:11:46 +0000[diff] [blame]5697}
5698
5699template <class _CharT, class _Traits, class _RT>
5700basic_ostream<_CharT, _Traits>&
5701operator<<(basic_ostream<_CharT, _Traits>& __os,
5702 const piecewise_constant_distribution<_RT>& __x)
5703{
5704 __save_flags<_CharT, _Traits> _(__os);
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]5705 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
5706 ios_base::scientific);
Howard Hinnantd6d11712010-05-20 15:11:46 +0000[diff] [blame]5707 _CharT __sp = __os.widen(' ');
5708 __os.fill(__sp);
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]5709 size_t __n = __x.__p_.__b_.size();
Howard Hinnantd6d11712010-05-20 15:11:46 +0000[diff] [blame]5710 __os << __n;
5711 for (size_t __i = 0; __i < __n; ++__i)
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]5712 __os << __sp << __x.__p_.__b_[__i];
5713 __n = __x.__p_.__densities_.size();
Howard Hinnantd6d11712010-05-20 15:11:46 +0000[diff] [blame]5714 __os << __sp << __n;
5715 for (size_t __i = 0; __i < __n; ++__i)
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]5716 __os << __sp << __x.__p_.__densities_[__i];
5717 __n = __x.__p_.__areas_.size();
5718 __os << __sp << __n;
5719 for (size_t __i = 0; __i < __n; ++__i)
5720 __os << __sp << __x.__p_.__areas_[__i];
Howard Hinnantd6d11712010-05-20 15:11:46 +0000[diff] [blame]5721 return __os;
5722}
5723
5724template <class _CharT, class _Traits, class _RT>
5725basic_istream<_CharT, _Traits>&
5726operator>>(basic_istream<_CharT, _Traits>& __is,
5727 piecewise_constant_distribution<_RT>& __x)
5728{
5729 typedef piecewise_constant_distribution<_RT> _Eng;
5730 typedef typename _Eng::result_type result_type;
5731 typedef typename _Eng::param_type param_type;
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]5732 typedef typename param_type::__area_type __area_type;
Howard Hinnantd6d11712010-05-20 15:11:46 +0000[diff] [blame]5733 __save_flags<_CharT, _Traits> _(__is);
5734 __is.flags(ios_base::dec | ios_base::skipws);
5735 size_t __n;
5736 __is >> __n;
Howard Hinnantd6d11712010-05-20 15:11:46 +0000[diff] [blame]5737 vector<result_type> __b(__n);
5738 for (size_t __i = 0; __i < __n; ++__i)
5739 __is >> __b[__i];
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]5740 __is >> __n;
5741 vector<double> __densities(__n);
5742 for (size_t __i = 0; __i < __n; ++__i)
5743 __is >> __densities[__i];
5744 __is >> __n;
5745 vector<__area_type> __areas(__n);
5746 for (size_t __i = 0; __i < __n; ++__i)
5747 __is >> __areas[__i];
Howard Hinnantd6d11712010-05-20 15:11:46 +0000[diff] [blame]5748 if (!__is.fail())
5749 {
Howard Hinnantd6d11712010-05-20 15:11:46 +0000[diff] [blame]5750 swap(__x.__p_.__b_, __b);
Howard Hinnant2a592542010-05-24 00:35:40 +0000[diff] [blame]5751 swap(__x.__p_.__densities_, __densities);
5752 swap(__x.__p_.__areas_, __areas);
Howard Hinnantd6d11712010-05-20 15:11:46 +0000[diff] [blame]5753 }
5754 return __is;
5755}
5756
Howard Hinnant54305402010-05-25 00:27:34 +0000[diff] [blame]5757// piecewise_linear_distribution
5758
5759template<class _RealType = double>
5760class piecewise_linear_distribution
5761{
5762public:
5763 // types
5764 typedef _RealType result_type;
5765
5766 class param_type
5767 {
5768 typedef typename common_type<double, result_type>::type __area_type;
5769 vector<result_type> __b_;
5770 vector<double> __densities_;
5771 vector<__area_type> __areas_;
5772 public:
5773 typedef piecewise_linear_distribution distribution_type;
5774
5775 param_type();
5776 template<class _InputIteratorB, class _InputIteratorW>
5777 param_type(_InputIteratorB __fB, _InputIteratorB __lB,
5778 _InputIteratorW __fW);
5779 template<class _UnaryOperation>
5780 param_type(initializer_list<result_type> __bl, _UnaryOperation __fw);
5781 template<class _UnaryOperation>
5782 param_type(size_t __nw, result_type __xmin, result_type __xmax,
5783 _UnaryOperation __fw);
5784
5785 vector<result_type> intervals() const {return __b_;}
5786 vector<double> densities() const {return __densities_;}
5787
5788 friend bool operator==(const param_type& __x, const param_type& __y)
5789 {return __x.__densities_ == __y.__densities_ && __x.__b_ == __y.__b_;}
5790 friend bool operator!=(const param_type& __x, const param_type& __y)
5791 {return !(__x == __y);}
5792
5793 private:
5794 void __init();
5795
5796 friend class piecewise_linear_distribution;
5797
5798 template <class _CharT, class _Traits, class _RT>
5799 friend
5800 basic_ostream<_CharT, _Traits>&
5801 operator<<(basic_ostream<_CharT, _Traits>& __os,
5802 const piecewise_linear_distribution<_RT>& __x);
5803
5804 template <class _CharT, class _Traits, class _RT>
5805 friend
5806 basic_istream<_CharT, _Traits>&
5807 operator>>(basic_istream<_CharT, _Traits>& __is,
5808 piecewise_linear_distribution<_RT>& __x);
5809 };
5810
5811private:
5812 param_type __p_;
5813
5814public:
5815 // constructor and reset functions
5816 piecewise_linear_distribution() {}
5817 template<class _InputIteratorB, class _InputIteratorW>
5818 piecewise_linear_distribution(_InputIteratorB __fB,
5819 _InputIteratorB __lB,
5820 _InputIteratorW __fW)
5821 : __p_(__fB, __lB, __fW) {}
5822
5823 template<class _UnaryOperation>
5824 piecewise_linear_distribution(initializer_list<result_type> __bl,
5825 _UnaryOperation __fw)
5826 : __p_(__bl, __fw) {}
5827
5828 template<class _UnaryOperation>
5829 piecewise_linear_distribution(size_t __nw, result_type __xmin,
5830 result_type __xmax, _UnaryOperation __fw)
5831 : __p_(__nw, __xmin, __xmax, __fw) {}
5832
5833 explicit piecewise_linear_distribution(const param_type& __p)
5834 : __p_(__p) {}
5835
5836 void reset() {}
5837
5838 // generating functions
5839 template<class _URNG> result_type operator()(_URNG& __g)
5840 {return (*this)(__g, __p_);}
5841 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
5842
5843 // property functions
5844 vector<result_type> intervals() const {return __p_.intervals();}
5845 vector<double> densities() const {return __p_.densities();}
5846
5847 param_type param() const {return __p_;}
5848 void param(const param_type& __p) {__p_ = __p;}
5849
5850 result_type min() const {return __p_.__b_.front();}
5851 result_type max() const {return __p_.__b_.back();}
5852
5853 friend bool operator==(const piecewise_linear_distribution& __x,
5854 const piecewise_linear_distribution& __y)
5855 {return __x.__p_ == __y.__p_;}
5856 friend bool operator!=(const piecewise_linear_distribution& __x,
5857 const piecewise_linear_distribution& __y)
5858 {return !(__x == __y);}
5859
5860 template <class _CharT, class _Traits, class _RT>
5861 friend
5862 basic_ostream<_CharT, _Traits>&
5863 operator<<(basic_ostream<_CharT, _Traits>& __os,
5864 const piecewise_linear_distribution<_RT>& __x);
5865
5866 template <class _CharT, class _Traits, class _RT>
5867 friend
5868 basic_istream<_CharT, _Traits>&
5869 operator>>(basic_istream<_CharT, _Traits>& __is,
5870 piecewise_linear_distribution<_RT>& __x);
5871};
5872
5873template<class _RealType>
5874void
5875piecewise_linear_distribution<_RealType>::param_type::__init()
5876{
5877 __areas_.assign(__densities_.size() - 1, __area_type());
5878 __area_type _S = 0;
5879 for (size_t __i = 0; __i < __areas_.size(); ++__i)
5880 {
5881 __areas_[__i] = (__densities_[__i+1] + __densities_[__i]) *
5882 (__b_[__i+1] - __b_[__i]) * .5;
5883 _S += __areas_[__i];
5884 }
5885 for (size_t __i = __areas_.size(); __i > 1;)
5886 {
5887 --__i;
5888 __areas_[__i] = __areas_[__i-1] / _S;
5889 }
5890 __areas_[0] = 0;
5891 for (size_t __i = 1; __i < __areas_.size(); ++__i)
5892 __areas_[__i] += __areas_[__i-1];
5893 for (size_t __i = 0; __i < __densities_.size(); ++__i)
5894 __densities_[__i] /= _S;
5895}
5896
5897template<class _RealType>
5898piecewise_linear_distribution<_RealType>::param_type::param_type()
5899 : __b_(2),
5900 __densities_(2, 1.0),
5901 __areas_(1, 0.0)
5902{
5903 __b_[1] = 1;
5904}
5905
5906template<class _RealType>
5907template<class _InputIteratorB, class _InputIteratorW>
5908piecewise_linear_distribution<_RealType>::param_type::param_type(
5909 _InputIteratorB __fB, _InputIteratorB __lB, _InputIteratorW __fW)
5910 : __b_(__fB, __lB)
5911{
5912 if (__b_.size() < 2)
5913 {
5914 __b_.resize(2);
5915 __b_[0] = 0;
5916 __b_[1] = 1;
5917 __densities_.assign(2, 1.0);
5918 __areas_.assign(1, 0.0);
5919 }
5920 else
5921 {
5922 __densities_.reserve(__b_.size());
5923 for (size_t __i = 0; __i < __b_.size(); ++__i, ++__fW)
5924 __densities_.push_back(*__fW);
5925 __init();
5926 }
5927}
5928
5929template<class _RealType>
5930template<class _UnaryOperation>
5931piecewise_linear_distribution<_RealType>::param_type::param_type(
5932 initializer_list<result_type> __bl, _UnaryOperation __fw)
5933 : __b_(__bl.begin(), __bl.end())
5934{
5935 if (__b_.size() < 2)
5936 {
5937 __b_.resize(2);
5938 __b_[0] = 0;
5939 __b_[1] = 1;
5940 __densities_.assign(2, 1.0);
5941 __areas_.assign(1, 0.0);
5942 }
5943 else
5944 {
5945 __densities_.reserve(__b_.size());
5946 for (size_t __i = 0; __i < __b_.size(); ++__i)
5947 __densities_.push_back(__fw(__b_[__i]));
5948 __init();
5949 }
5950}
5951
5952template<class _RealType>
5953template<class _UnaryOperation>
5954piecewise_linear_distribution<_RealType>::param_type::param_type(
5955 size_t __nw, result_type __xmin, result_type __xmax, _UnaryOperation __fw)
5956 : __b_(__nw == 0 ? 2 : __nw + 1)
5957{
5958 size_t __n = __b_.size() - 1;
5959 result_type __d = (__xmax - __xmin) / __n;
5960 __densities_.reserve(__b_.size());
5961 for (size_t __i = 0; __i < __n; ++__i)
5962 {
5963 __b_[__i] = __xmin + __i * __d;
5964 __densities_.push_back(__fw(__b_[__i]));
5965 }
5966 __b_[__n] = __xmax;
5967 __densities_.push_back(__fw(__b_[__n]));
5968 __init();
5969}
5970
5971template<class _RealType>
5972template<class _URNG>
5973_RealType
5974piecewise_linear_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
5975{
5976 typedef uniform_real_distribution<result_type> _Gen;
5977 result_type __u = _Gen()(__g);
5978 ptrdiff_t __k = _STD::upper_bound(__p.__areas_.begin(), __p.__areas_.end(),
5979 static_cast<double>(__u)) - __p.__areas_.begin() - 1;
5980 __u -= __p.__areas_[__k];
5981 const double __dk = __p.__densities_[__k];
5982 const double __dk1 = __p.__densities_[__k+1];
5983 const double __deltad = __dk1 - __dk;
5984 const result_type __bk = __p.__b_[__k];
5985 if (__deltad == 0)
5986 return static_cast<result_type>(__u / __dk + __bk);
5987 const result_type __bk1 = __p.__b_[__k+1];
5988 const result_type __deltab = __bk1 - __bk;
5989 return static_cast<result_type>((__bk * __dk1 - __bk1 * __dk +
5990 _STD::sqrt(__deltab * (__deltab * __dk * __dk + 2 * __deltad * __u))) /
5991 __deltad);
5992}
5993
5994template <class _CharT, class _Traits, class _RT>
5995basic_ostream<_CharT, _Traits>&
5996operator<<(basic_ostream<_CharT, _Traits>& __os,
5997 const piecewise_linear_distribution<_RT>& __x)
5998{
5999 __save_flags<_CharT, _Traits> _(__os);
6000 __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
6001 ios_base::scientific);
6002 _CharT __sp = __os.widen(' ');
6003 __os.fill(__sp);
6004 size_t __n = __x.__p_.__b_.size();
6005 __os << __n;
6006 for (size_t __i = 0; __i < __n; ++__i)
6007 __os << __sp << __x.__p_.__b_[__i];
6008 __n = __x.__p_.__densities_.size();
6009 __os << __sp << __n;
6010 for (size_t __i = 0; __i < __n; ++__i)
6011 __os << __sp << __x.__p_.__densities_[__i];
6012 __n = __x.__p_.__areas_.size();
6013 __os << __sp << __n;
6014 for (size_t __i = 0; __i < __n; ++__i)
6015 __os << __sp << __x.__p_.__areas_[__i];
6016 return __os;
6017}
6018
6019template <class _CharT, class _Traits, class _RT>
6020basic_istream<_CharT, _Traits>&
6021operator>>(basic_istream<_CharT, _Traits>& __is,
6022 piecewise_linear_distribution<_RT>& __x)
6023{
6024 typedef piecewise_linear_distribution<_RT> _Eng;
6025 typedef typename _Eng::result_type result_type;
6026 typedef typename _Eng::param_type param_type;
6027 typedef typename param_type::__area_type __area_type;
6028 __save_flags<_CharT, _Traits> _(__is);
6029 __is.flags(ios_base::dec | ios_base::skipws);
6030 size_t __n;
6031 __is >> __n;
6032 vector<result_type> __b(__n);
6033 for (size_t __i = 0; __i < __n; ++__i)
6034 __is >> __b[__i];
6035 __is >> __n;
6036 vector<double> __densities(__n);
6037 for (size_t __i = 0; __i < __n; ++__i)
6038 __is >> __densities[__i];
6039 __is >> __n;
6040 vector<__area_type> __areas(__n);
6041 for (size_t __i = 0; __i < __n; ++__i)
6042 __is >> __areas[__i];
6043 if (!__is.fail())
6044 {
6045 swap(__x.__p_.__b_, __b);
6046 swap(__x.__p_.__densities_, __densities);
6047 swap(__x.__p_.__areas_, __areas);
6048 }
6049 return __is;
6050}
6051
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]6052_LIBCPP_END_NAMESPACE_STD
6053
6054#endif // _LIBCPP_RANDOM