blob: c1734146d1ec1b43b68589067128f0bb493ad186 [file] [log] [blame]
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001// -*- C++ -*-
2//===--------------------------- random -----------------------------------===//
3//
Howard Hinnantf5256e12010-05-11 21:36:01 +00004// The LLVM Compiler Infrastructure
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00005//
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;
374typedef minstd_rand0 default_random_engine;
375
376// Generators
377
378class random_device
379{
380public:
381 // types
382 typedef unsigned int result_type;
383
384 // generator characteristics
385 static constexpr result_type min() { return numeric_limits<result_type>::min(); }
386 static constexpr result_type max() { return numeric_limits<result_type>::max(); }
387
388 // constructors
389 explicit random_device(const string& token = "/dev/urandom");
390
391 // generating functions
392 result_type operator()();
393
394 // property functions
395 double entropy() const;
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 +0000611class 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 +0000667
668template<class IntType = int>
Howard Hinnant34e8a572010-05-17 13:44:27 +0000669class 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 +0000723
724template<class IntType = int>
Howard Hinnantf2fe5d52010-05-17 00:09:38 +0000725class 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 +0000781
782template<class IntType = int>
Howard Hinnant4ff556c2010-05-14 21:38:54 +0000783class 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 +0000837
838template<class RealType = double>
Howard Hinnant30a840f2010-05-12 17:08:57 +0000839class 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 +0000850 explicit param_type(result_type lambda = 1.0);
Howard Hinnant30a840f2010-05-12 17:08:57 +0000851
Howard Hinnanta64111c2010-05-12 21:02:31 +0000852 result_type lambda() const;
Howard Hinnant30a840f2010-05-12 17:08:57 +0000853
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 +0000859 explicit exponential_distribution(result_type lambda = 1.0);
Howard Hinnant30a840f2010-05-12 17:08:57 +0000860 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 +0000868 result_type lambda() const;
Howard Hinnant30a840f2010-05-12 17:08:57 +0000869
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 +0000893
894template<class RealType = double>
Howard Hinnantc7c49132010-05-13 17:58:28 +0000895class 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 +0000951
952template<class RealType = double>
Howard Hinnant9de6e302010-05-16 01:09:02 +0000953class 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 +0000992 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 +00001009
1010template<class RealType = double>
Howard Hinnantc2b0dc72010-05-17 16:21:56 +00001011class 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 +00001067
1068template<class RealType = double>
Howard Hinnanta64111c2010-05-12 21:02:31 +00001069class 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 +00001125
1126template<class RealType = double>
Howard Hinnant2bc36fc2010-05-17 18:31:53 +00001127class 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 +00001183
1184template<class RealType = double>
Howard Hinnant97dc2f32010-05-15 23:36:00 +00001185class 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 +00001222 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 +00001239
1240template<class RealType = double>
Howard Hinnantd7d01132010-05-17 21:55:46 +00001241class 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 +00001297
1298template<class RealType = double>
1299 class fisher_f_distribution;
1300
1301template<class RealType = double>
1302 class student_t_distribution;
1303
1304template<class IntType = int>
1305 class discrete_distribution;
1306
1307template<class RealType = double>
1308 class piecewise_constant_distribution;
1309
1310template<class RealType = double>
1311 class piecewise_linear_distribution;
1312
1313} // std
1314*/
1315
1316#include <__config>
1317#include <cstddef>
1318#include <type_traits>
1319#include <initializer_list>
1320#include <cstdint>
1321#include <limits>
1322#include <algorithm>
1323#include <vector>
1324#include <string>
1325#include <istream>
1326#include <ostream>
Howard Hinnant30a840f2010-05-12 17:08:57 +00001327#include <cmath>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001328
1329#pragma GCC system_header
1330
1331_LIBCPP_BEGIN_NAMESPACE_STD
1332
1333// linear_congruential_engine
1334
1335template <unsigned long long __a, unsigned long long __c,
1336 unsigned long long __m, unsigned long long _M,
1337 bool _MightOverflow = (__a != 0 && __m != 0 && __m-1 > (_M-__c)/__a)>
1338struct __lce_ta;
1339
1340// 64
1341
1342template <unsigned long long __a, unsigned long long __c, unsigned long long __m>
1343struct __lce_ta<__a, __c, __m, (unsigned long long)(~0), true>
1344{
1345 typedef unsigned long long result_type;
1346 static result_type next(result_type __x)
1347 {
1348 // Schrage's algorithm
1349 const result_type __q = __m / __a;
1350 const result_type __r = __m % __a;
1351 const result_type __t0 = __a * (__x % __q);
1352 const result_type __t1 = __r * (__x / __q);
1353 __x = __t0 + (__t0 < __t1) * __m - __t1;
1354 __x += __c - (__x >= __m - __c) * __m;
1355 return __x;
1356 }
1357};
1358
1359template <unsigned long long __a, unsigned long long __m>
1360struct __lce_ta<__a, 0, __m, (unsigned long long)(~0), true>
1361{
1362 typedef unsigned long long result_type;
1363 static result_type next(result_type __x)
1364 {
1365 // Schrage's algorithm
1366 const result_type __q = __m / __a;
1367 const result_type __r = __m % __a;
1368 const result_type __t0 = __a * (__x % __q);
1369 const result_type __t1 = __r * (__x / __q);
1370 __x = __t0 + (__t0 < __t1) * __m - __t1;
1371 return __x;
1372 }
1373};
1374
1375template <unsigned long long __a, unsigned long long __c, unsigned long long __m>
1376struct __lce_ta<__a, __c, __m, (unsigned long long)(~0), false>
1377{
1378 typedef unsigned long long result_type;
1379 static result_type next(result_type __x)
1380 {
1381 return (__a * __x + __c) % __m;
1382 }
1383};
1384
1385template <unsigned long long __a, unsigned long long __c>
1386struct __lce_ta<__a, __c, 0, (unsigned long long)(~0), false>
1387{
1388 typedef unsigned long long result_type;
1389 static result_type next(result_type __x)
1390 {
1391 return __a * __x + __c;
1392 }
1393};
1394
1395// 32
1396
1397template <unsigned long long _A, unsigned long long _C, unsigned long long _M>
1398struct __lce_ta<_A, _C, _M, unsigned(~0), true>
1399{
1400 typedef unsigned result_type;
1401 static result_type next(result_type __x)
1402 {
1403 const result_type __a = static_cast<result_type>(_A);
1404 const result_type __c = static_cast<result_type>(_C);
1405 const result_type __m = static_cast<result_type>(_M);
1406 // Schrage's algorithm
1407 const result_type __q = __m / __a;
1408 const result_type __r = __m % __a;
1409 const result_type __t0 = __a * (__x % __q);
1410 const result_type __t1 = __r * (__x / __q);
1411 __x = __t0 + (__t0 < __t1) * __m - __t1;
1412 __x += __c - (__x >= __m - __c) * __m;
1413 return __x;
1414 }
1415};
1416
1417template <unsigned long long _A, unsigned long long _M>
1418struct __lce_ta<_A, 0, _M, unsigned(~0), true>
1419{
1420 typedef unsigned result_type;
1421 static result_type next(result_type __x)
1422 {
1423 const result_type __a = static_cast<result_type>(_A);
1424 const result_type __m = static_cast<result_type>(_M);
1425 // Schrage's algorithm
1426 const result_type __q = __m / __a;
1427 const result_type __r = __m % __a;
1428 const result_type __t0 = __a * (__x % __q);
1429 const result_type __t1 = __r * (__x / __q);
1430 __x = __t0 + (__t0 < __t1) * __m - __t1;
1431 return __x;
1432 }
1433};
1434
1435template <unsigned long long _A, unsigned long long _C, unsigned long long _M>
1436struct __lce_ta<_A, _C, _M, unsigned(~0), false>
1437{
1438 typedef unsigned result_type;
1439 static result_type next(result_type __x)
1440 {
1441 const result_type __a = static_cast<result_type>(_A);
1442 const result_type __c = static_cast<result_type>(_C);
1443 const result_type __m = static_cast<result_type>(_M);
1444 return (__a * __x + __c) % __m;
1445 }
1446};
1447
1448template <unsigned long long _A, unsigned long long _C>
1449struct __lce_ta<_A, _C, 0, unsigned(~0), false>
1450{
1451 typedef unsigned result_type;
1452 static result_type next(result_type __x)
1453 {
1454 const result_type __a = static_cast<result_type>(_A);
1455 const result_type __c = static_cast<result_type>(_C);
1456 return __a * __x + __c;
1457 }
1458};
1459
1460// 16
1461
1462template <unsigned long long __a, unsigned long long __c, unsigned long long __m, bool __b>
1463struct __lce_ta<__a, __c, __m, (unsigned short)(~0), __b>
1464{
1465 typedef unsigned short result_type;
1466 static result_type next(result_type __x)
1467 {
1468 return static_cast<result_type>(__lce_ta<__a, __c, __m, unsigned(~0)>::next(__x));
1469 }
1470};
1471
1472template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1473class linear_congruential_engine;
1474
1475template <class _CharT, class _Traits,
1476 class _U, _U _A, _U _C, _U _N>
1477basic_ostream<_CharT, _Traits>&
1478operator<<(basic_ostream<_CharT, _Traits>& __os,
1479 const linear_congruential_engine<_U, _A, _C, _N>&);
1480
1481template <class _CharT, class _Traits,
1482 class _U, _U _A, _U _C, _U _N>
1483basic_istream<_CharT, _Traits>&
1484operator>>(basic_istream<_CharT, _Traits>& __is,
1485 linear_congruential_engine<_U, _A, _C, _N>& __x);
1486
1487template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1488class linear_congruential_engine
1489{
1490public:
1491 // types
1492 typedef _UIntType result_type;
1493
1494private:
1495 result_type __x_;
1496
1497 static const result_type _M = result_type(~0);
1498
1499 static_assert(__m == 0 || __a < __m, "linear_congruential_engine invalid parameters");
1500 static_assert(__m == 0 || __c < __m, "linear_congruential_engine invalid parameters");
1501public:
1502 static const result_type _Min = __c == 0u ? 1u: 0u;
1503 static const result_type _Max = __m - 1u;
1504 static_assert(_Min < _Max, "linear_congruential_engine invalid parameters");
1505
1506 // engine characteristics
1507 static const/*expr*/ result_type multiplier = __a;
1508 static const/*expr*/ result_type increment = __c;
1509 static const/*expr*/ result_type modulus = __m;
1510 static const/*expr*/ result_type min() {return _Min;}
1511 static const/*expr*/ result_type max() {return _Max;}
1512 static const/*expr*/ result_type default_seed = 1u;
1513
1514 // constructors and seeding functions
1515 explicit linear_congruential_engine(result_type __s = default_seed)
1516 {seed(__s);}
1517 template<class _Sseq> explicit linear_congruential_engine(_Sseq& __q)
1518 {seed(__q);}
1519 void seed(result_type __s = default_seed)
1520 {seed(integral_constant<bool, __m == 0>(),
1521 integral_constant<bool, __c == 0>(), __s);}
1522 template<class _Sseq>
1523 typename enable_if
1524 <
1525 !is_convertible<_Sseq, result_type>::value,
1526 void
1527 >::type
1528 seed(_Sseq& __q)
1529 {__seed(__q, integral_constant<unsigned,
1530 1 + (__m == 0 ? (sizeof(result_type) * __CHAR_BIT__ - 1)/32
1531 : (__m-1) / 0x100000000ull)>());}
1532
1533 // generating functions
1534 result_type operator()()
1535 {return __x_ = static_cast<result_type>(__lce_ta<__a, __c, __m, _M>::next(__x_));}
1536 void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
1537
1538 friend bool operator==(const linear_congruential_engine& __x,
1539 const linear_congruential_engine& __y)
1540 {return __x.__x_ == __y.__x_;}
1541 friend bool operator!=(const linear_congruential_engine& __x,
1542 const linear_congruential_engine& __y)
1543 {return !(__x == __y);}
1544
1545private:
1546
1547 void seed(true_type, true_type, result_type __s) {__x_ = __s == 0 ? 1 : __s;}
1548 void seed(true_type, false_type, result_type __s) {__x_ = __s;}
1549 void seed(false_type, true_type, result_type __s) {__x_ = __s % __m == 0 ?
1550 1 : __s % __m;}
1551 void seed(false_type, false_type, result_type __s) {__x_ = __s % __m;}
1552
1553 template<class _Sseq>
1554 void __seed(_Sseq& __q, integral_constant<unsigned, 1>);
1555 template<class _Sseq>
1556 void __seed(_Sseq& __q, integral_constant<unsigned, 2>);
1557
1558 template <class _CharT, class _Traits,
1559 class _U, _U _A, _U _C, _U _N>
1560 friend
1561 basic_ostream<_CharT, _Traits>&
1562 operator<<(basic_ostream<_CharT, _Traits>& __os,
1563 const linear_congruential_engine<_U, _A, _C, _N>&);
1564
1565 template <class _CharT, class _Traits,
1566 class _U, _U _A, _U _C, _U _N>
1567 friend
1568 basic_istream<_CharT, _Traits>&
1569 operator>>(basic_istream<_CharT, _Traits>& __is,
1570 linear_congruential_engine<_U, _A, _C, _N>& __x);
1571};
1572
1573template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1574template<class _Sseq>
1575void
1576linear_congruential_engine<_UIntType, __a, __c, __m>::__seed(_Sseq& __q,
1577 integral_constant<unsigned, 1>)
1578{
1579 const unsigned __k = 1;
1580 uint32_t __ar[__k+3];
1581 __q.generate(__ar, __ar + __k + 3);
1582 result_type __s = static_cast<result_type>(__ar[3] % __m);
1583 __x_ = __c == 0 && __s == 0 ? result_type(1) : __s;
1584}
1585
1586template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1587template<class _Sseq>
1588void
1589linear_congruential_engine<_UIntType, __a, __c, __m>::__seed(_Sseq& __q,
1590 integral_constant<unsigned, 2>)
1591{
1592 const unsigned __k = 2;
1593 uint32_t __ar[__k+3];
1594 __q.generate(__ar, __ar + __k + 3);
1595 result_type __s = static_cast<result_type>((__ar[3] +
1596 (uint64_t)__ar[4] << 32) % __m);
1597 __x_ = __c == 0 && __s == 0 ? result_type(1) : __s;
1598}
1599
1600template <class _CharT, class _Traits>
1601class __save_flags
1602{
1603 typedef basic_ios<_CharT, _Traits> __stream_type;
1604 typedef typename __stream_type::fmtflags fmtflags;
1605
1606 __stream_type& __stream_;
1607 fmtflags __fmtflags_;
1608 _CharT __fill_;
1609
1610 __save_flags(const __save_flags&);
1611 __save_flags& operator=(const __save_flags&);
1612public:
1613 explicit __save_flags(__stream_type& __stream)
1614 : __stream_(__stream),
1615 __fmtflags_(__stream.flags()),
1616 __fill_(__stream.fill())
1617 {}
1618 ~__save_flags()
1619 {
1620 __stream_.flags(__fmtflags_);
1621 __stream_.fill(__fill_);
1622 }
1623};
1624
1625template <class _CharT, class _Traits,
1626 class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1627inline
1628basic_ostream<_CharT, _Traits>&
1629operator<<(basic_ostream<_CharT, _Traits>& __os,
1630 const linear_congruential_engine<_UIntType, __a, __c, __m>& __x)
1631{
1632 __save_flags<_CharT, _Traits> _(__os);
1633 __os.flags(ios_base::dec | ios_base::left);
1634 __os.fill(__os.widen(' '));
1635 return __os << __x.__x_;
1636}
1637
1638template <class _CharT, class _Traits,
1639 class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1640basic_istream<_CharT, _Traits>&
1641operator>>(basic_istream<_CharT, _Traits>& __is,
1642 linear_congruential_engine<_UIntType, __a, __c, __m>& __x)
1643{
1644 __save_flags<_CharT, _Traits> _(__is);
1645 __is.flags(ios_base::dec | ios_base::skipws);
1646 _UIntType __t;
1647 __is >> __t;
1648 if (!__is.fail())
1649 __x.__x_ = __t;
1650 return __is;
1651}
1652
1653typedef linear_congruential_engine<uint_fast32_t, 16807, 0, 2147483647>
1654 minstd_rand0;
1655typedef minstd_rand0 default_random_engine;
1656typedef linear_congruential_engine<uint_fast32_t, 48271, 0, 2147483647>
1657 minstd_rand;
1658// mersenne_twister_engine
1659
1660template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
1661 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
1662 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
1663class mersenne_twister_engine;
1664
1665template <class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
1666 _UI _A, size_t _U, _UI _D, size_t _S,
1667 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
1668bool
1669operator==(const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1670 _B, _T, _C, _L, _F>& __x,
1671 const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1672 _B, _T, _C, _L, _F>& __y);
1673
1674template <class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
1675 _UI _A, size_t _U, _UI _D, size_t _S,
1676 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
1677bool
1678operator!=(const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1679 _B, _T, _C, _L, _F>& __x,
1680 const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1681 _B, _T, _C, _L, _F>& __y);
1682
1683template <class _CharT, class _Traits,
1684 class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
1685 _UI _A, size_t _U, _UI _D, size_t _S,
1686 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
1687basic_ostream<_CharT, _Traits>&
1688operator<<(basic_ostream<_CharT, _Traits>& __os,
1689 const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1690 _B, _T, _C, _L, _F>& __x);
1691
1692template <class _CharT, class _Traits,
1693 class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
1694 _UI _A, size_t _U, _UI _D, size_t _S,
1695 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
1696basic_istream<_CharT, _Traits>&
1697operator>>(basic_istream<_CharT, _Traits>& __is,
1698 mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1699 _B, _T, _C, _L, _F>& __x);
1700
1701template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
1702 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
1703 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
1704class mersenne_twister_engine
1705{
1706public:
1707 // types
1708 typedef _UIntType result_type;
1709
1710private:
1711 result_type __x_[__n];
1712 size_t __i_;
1713
1714 static_assert( 0 < __m, "mersenne_twister_engine invalid parameters");
1715 static_assert(__m <= __n, "mersenne_twister_engine invalid parameters");
1716 static const result_type _Dt = numeric_limits<result_type>::digits;
1717 static_assert(__w <= _Dt, "mersenne_twister_engine invalid parameters");
1718 static_assert( 2 <= __w, "mersenne_twister_engine invalid parameters");
1719 static_assert(__r <= __w, "mersenne_twister_engine invalid parameters");
1720 static_assert(__u <= __w, "mersenne_twister_engine invalid parameters");
1721 static_assert(__s <= __w, "mersenne_twister_engine invalid parameters");
1722 static_assert(__t <= __w, "mersenne_twister_engine invalid parameters");
1723 static_assert(__l <= __w, "mersenne_twister_engine invalid parameters");
1724public:
1725 static const result_type _Min = 0;
1726 static const result_type _Max = __w == _Dt ? result_type(~0) :
1727 (result_type(1) << __w) - result_type(1);
1728 static_assert(_Min < _Max, "mersenne_twister_engine invalid parameters");
1729 static_assert(__a <= _Max, "mersenne_twister_engine invalid parameters");
1730 static_assert(__b <= _Max, "mersenne_twister_engine invalid parameters");
1731 static_assert(__c <= _Max, "mersenne_twister_engine invalid parameters");
1732 static_assert(__d <= _Max, "mersenne_twister_engine invalid parameters");
1733 static_assert(__f <= _Max, "mersenne_twister_engine invalid parameters");
1734
1735 // engine characteristics
1736 static const/*expr*/ size_t word_size = __w;
1737 static const/*expr*/ size_t state_size = __n;
1738 static const/*expr*/ size_t shift_size = __m;
1739 static const/*expr*/ size_t mask_bits = __r;
1740 static const/*expr*/ result_type xor_mask = __a;
1741 static const/*expr*/ size_t tempering_u = __u;
1742 static const/*expr*/ result_type tempering_d = __d;
1743 static const/*expr*/ size_t tempering_s = __s;
1744 static const/*expr*/ result_type tempering_b = __b;
1745 static const/*expr*/ size_t tempering_t = __t;
1746 static const/*expr*/ result_type tempering_c = __c;
1747 static const/*expr*/ size_t tempering_l = __l;
1748 static const/*expr*/ result_type initialization_multiplier = __f;
1749 static const/*expr*/ result_type min() { return _Min; }
1750 static const/*expr*/ result_type max() { return _Max; }
1751 static const/*expr*/ result_type default_seed = 5489u;
1752
1753 // constructors and seeding functions
1754 explicit mersenne_twister_engine(result_type __sd = default_seed)
1755 {seed(__sd);}
1756 template<class _Sseq> explicit mersenne_twister_engine(_Sseq& __q)
1757 {seed(__q);}
1758 void seed(result_type __sd = default_seed);
1759 template<class _Sseq>
1760 typename enable_if
1761 <
1762 !is_convertible<_Sseq, result_type>::value,
1763 void
1764 >::type
1765 seed(_Sseq& __q)
1766 {__seed(__q, integral_constant<unsigned, 1 + (__w - 1) / 32>());}
1767
1768 // generating functions
1769 result_type operator()();
1770 void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
1771
1772 template <class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
1773 _UI _A, size_t _U, _UI _D, size_t _S,
1774 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
1775 friend
1776 bool
1777 operator==(const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1778 _B, _T, _C, _L, _F>& __x,
1779 const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1780 _B, _T, _C, _L, _F>& __y);
1781
1782 template <class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
1783 _UI _A, size_t _U, _UI _D, size_t _S,
1784 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
1785 friend
1786 bool
1787 operator!=(const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1788 _B, _T, _C, _L, _F>& __x,
1789 const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1790 _B, _T, _C, _L, _F>& __y);
1791
1792 template <class _CharT, class _Traits,
1793 class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
1794 _UI _A, size_t _U, _UI _D, size_t _S,
1795 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
1796 friend
1797 basic_ostream<_CharT, _Traits>&
1798 operator<<(basic_ostream<_CharT, _Traits>& __os,
1799 const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1800 _B, _T, _C, _L, _F>& __x);
1801
1802 template <class _CharT, class _Traits,
1803 class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
1804 _UI _A, size_t _U, _UI _D, size_t _S,
1805 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
1806 friend
1807 basic_istream<_CharT, _Traits>&
1808 operator>>(basic_istream<_CharT, _Traits>& __is,
1809 mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1810 _B, _T, _C, _L, _F>& __x);
1811private:
1812
1813 template<class _Sseq>
1814 void __seed(_Sseq& __q, integral_constant<unsigned, 1>);
1815 template<class _Sseq>
1816 void __seed(_Sseq& __q, integral_constant<unsigned, 2>);
1817
1818 template <size_t __count>
1819 static
1820 typename enable_if
1821 <
1822 __count < __w,
1823 result_type
1824 >::type
1825 __lshift(result_type __x) {return (__x << __count) & _Max;}
1826
1827 template <size_t __count>
1828 static
1829 typename enable_if
1830 <
1831 (__count >= __w),
1832 result_type
1833 >::type
1834 __lshift(result_type __x) {return result_type(0);}
1835
1836 template <size_t __count>
1837 static
1838 typename enable_if
1839 <
1840 __count < _Dt,
1841 result_type
1842 >::type
1843 __rshift(result_type __x) {return __x >> __count;}
1844
1845 template <size_t __count>
1846 static
1847 typename enable_if
1848 <
1849 (__count >= _Dt),
1850 result_type
1851 >::type
1852 __rshift(result_type __x) {return result_type(0);}
1853};
1854
1855template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
1856 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
1857 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
1858void
1859mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b,
1860 __t, __c, __l, __f>::seed(result_type __sd)
1861{ // __w >= 2
1862 __x_[0] = __sd & _Max;
1863 for (size_t __i = 1; __i < __n; ++__i)
1864 __x_[__i] = (__f * (__x_[__i-1] ^ __rshift<__w - 2>(__x_[__i-1])) + __i) & _Max;
1865 __i_ = 0;
1866}
1867
1868template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
1869 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
1870 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
1871template<class _Sseq>
1872void
1873mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b,
1874 __t, __c, __l, __f>::__seed(_Sseq& __q, integral_constant<unsigned, 1>)
1875{
1876 const unsigned __k = 1;
1877 uint32_t __ar[__n * __k];
1878 __q.generate(__ar, __ar + __n * __k);
1879 for (size_t __i = 0; __i < __n; ++__i)
1880 __x_[__i] = static_cast<result_type>(__ar[__i] & _Max);
1881 const result_type __mask = __r == _Dt ? result_type(~0) :
1882 (result_type(1) << __r) - result_type(1);
1883 __i_ = 0;
1884 if ((__x_[0] & ~__mask) == 0)
1885 {
1886 for (size_t __i = 1; __i < __n; ++__i)
1887 if (__x_[__i] != 0)
1888 return;
1889 __x_[0] = _Max;
1890 }
1891}
1892
1893template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
1894 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
1895 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
1896template<class _Sseq>
1897void
1898mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b,
1899 __t, __c, __l, __f>::__seed(_Sseq& __q, integral_constant<unsigned, 2>)
1900{
1901 const unsigned __k = 2;
1902 uint32_t __ar[__n * __k];
1903 __q.generate(__ar, __ar + __n * __k);
1904 for (size_t __i = 0; __i < __n; ++__i)
1905 __x_[__i] = static_cast<result_type>(
1906 (__ar[2 * __i] + ((uint64_t)__ar[2 * __i + 1] << 32)) & _Max);
1907 const result_type __mask = __r == _Dt ? result_type(~0) :
1908 (result_type(1) << __r) - result_type(1);
1909 __i_ = 0;
1910 if ((__x_[0] & ~__mask) == 0)
1911 {
1912 for (size_t __i = 1; __i < __n; ++__i)
1913 if (__x_[__i] != 0)
1914 return;
1915 __x_[0] = _Max;
1916 }
1917}
1918
1919template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
1920 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
1921 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
1922_UIntType
1923mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b,
1924 __t, __c, __l, __f>::operator()()
1925{
1926 const size_t __j = (__i_ + 1) % __n;
1927 const result_type __mask = __r == _Dt ? result_type(~0) :
1928 (result_type(1) << __r) - result_type(1);
1929 const result_type _Y = (__x_[__i_] & ~__mask) | (__x_[__j] & __mask);
1930 const size_t __k = (__i_ + __m) % __n;
1931 __x_[__i_] = __x_[__k] ^ __rshift<1>(_Y) ^ (__a * (_Y & 1));
1932 result_type __z = __x_[__i_] ^ (__rshift<__u>(__x_[__i_]) & __d);
1933 __i_ = __j;
1934 __z ^= __lshift<__s>(__z) & __b;
1935 __z ^= __lshift<__t>(__z) & __c;
1936 return __z ^ __rshift<__l>(__z);
1937}
1938
1939template <class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
1940 _UI _A, size_t _U, _UI _D, size_t _S,
1941 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
1942bool
1943operator==(const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1944 _B, _T, _C, _L, _F>& __x,
1945 const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1946 _B, _T, _C, _L, _F>& __y)
1947{
1948 if (__x.__i_ == __y.__i_)
1949 return _STD::equal(__x.__x_, __x.__x_ + _N, __y.__x_);
1950 if (__x.__i_ == 0 || __y.__i_ == 0)
1951 {
1952 size_t __j = _STD::min(_N - __x.__i_, _N - __y.__i_);
1953 if (!_STD::equal(__x.__x_ + __x.__i_, __x.__x_ + __x.__i_ + __j,
1954 __y.__x_ + __y.__i_))
1955 return false;
1956 if (__x.__i_ == 0)
1957 return _STD::equal(__x.__x_ + __j, __x.__x_ + _N, __y.__x_);
1958 return _STD::equal(__x.__x_, __x.__x_ + (_N - __j), __y.__x_ + __j);
1959 }
1960 if (__x.__i_ < __y.__i_)
1961 {
1962 size_t __j = _N - __y.__i_;
1963 if (!_STD::equal(__x.__x_ + __x.__i_, __x.__x_ + (__x.__i_ + __j),
1964 __y.__x_ + __y.__i_))
1965 return false;
1966 if (!_STD::equal(__x.__x_ + (__x.__i_ + __j), __x.__x_ + _N,
1967 __y.__x_))
1968 return false;
1969 return _STD::equal(__x.__x_, __x.__x_ + __x.__i_,
1970 __y.__x_ + (_N - (__x.__i_ + __j)));
1971 }
1972 size_t __j = _N - __x.__i_;
1973 if (!_STD::equal(__y.__x_ + __y.__i_, __y.__x_ + (__y.__i_ + __j),
1974 __x.__x_ + __x.__i_))
1975 return false;
1976 if (!_STD::equal(__y.__x_ + (__y.__i_ + __j), __y.__x_ + _N,
1977 __x.__x_))
1978 return false;
1979 return _STD::equal(__y.__x_, __y.__x_ + __y.__i_,
1980 __x.__x_ + (_N - (__y.__i_ + __j)));
1981}
1982
1983template <class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
1984 _UI _A, size_t _U, _UI _D, size_t _S,
1985 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
1986inline
1987bool
1988operator!=(const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1989 _B, _T, _C, _L, _F>& __x,
1990 const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1991 _B, _T, _C, _L, _F>& __y)
1992{
1993 return !(__x == __y);
1994}
1995
1996template <class _CharT, class _Traits,
1997 class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
1998 _UI _A, size_t _U, _UI _D, size_t _S,
1999 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
2000basic_ostream<_CharT, _Traits>&
2001operator<<(basic_ostream<_CharT, _Traits>& __os,
2002 const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
2003 _B, _T, _C, _L, _F>& __x)
2004{
2005 __save_flags<_CharT, _Traits> _(__os);
2006 __os.flags(ios_base::dec | ios_base::left);
2007 _CharT __sp = __os.widen(' ');
2008 __os.fill(__sp);
2009 __os << __x.__x_[__x.__i_];
2010 for (size_t __j = __x.__i_ + 1; __j < _N; ++__j)
2011 __os << __sp << __x.__x_[__j];
2012 for (size_t __j = 0; __j < __x.__i_; ++__j)
2013 __os << __sp << __x.__x_[__j];
2014 return __os;
2015}
2016
2017template <class _CharT, class _Traits,
2018 class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
2019 _UI _A, size_t _U, _UI _D, size_t _S,
2020 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
2021basic_istream<_CharT, _Traits>&
2022operator>>(basic_istream<_CharT, _Traits>& __is,
2023 mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
2024 _B, _T, _C, _L, _F>& __x)
2025{
2026 __save_flags<_CharT, _Traits> _(__is);
2027 __is.flags(ios_base::dec | ios_base::skipws);
2028 _UI __t[_N];
2029 for (size_t __i = 0; __i < _N; ++__i)
2030 __is >> __t[__i];
2031 if (!__is.fail())
2032 {
2033 for (size_t __i = 0; __i < _N; ++__i)
2034 __x.__x_[__i] = __t[__i];
2035 __x.__i_ = 0;
2036 }
2037 return __is;
2038}
2039
2040typedef mersenne_twister_engine<uint_fast32_t, 32, 624, 397, 31,
2041 0x9908b0df, 11, 0xffffffff,
2042 7, 0x9d2c5680,
2043 15, 0xefc60000,
2044 18, 1812433253> mt19937;
2045typedef mersenne_twister_engine<uint_fast64_t, 64, 312, 156, 31,
2046 0xb5026f5aa96619e9ULL, 29, 0x5555555555555555ULL,
2047 17, 0x71d67fffeda60000ULL,
2048 37, 0xfff7eee000000000ULL,
2049 43, 6364136223846793005ULL> mt19937_64;
2050
2051// subtract_with_carry_engine
2052
2053template<class _UIntType, size_t __w, size_t __s, size_t __r>
2054class subtract_with_carry_engine;
2055
2056template<class _UI, size_t _W, size_t _S, size_t _R>
2057bool
2058operator==(
2059 const subtract_with_carry_engine<_UI, _W, _S, _R>& __x,
2060 const subtract_with_carry_engine<_UI, _W, _S, _R>& __y);
2061
2062template<class _UI, size_t _W, size_t _S, size_t _R>
2063bool
2064operator!=(
2065 const subtract_with_carry_engine<_UI, _W, _S, _R>& __x,
2066 const subtract_with_carry_engine<_UI, _W, _S, _R>& __y);
2067
2068template <class _CharT, class _Traits,
2069 class _UI, size_t _W, size_t _S, size_t _R>
2070basic_ostream<_CharT, _Traits>&
2071operator<<(basic_ostream<_CharT, _Traits>& __os,
2072 const subtract_with_carry_engine<_UI, _W, _S, _R>& __x);
2073
2074template <class _CharT, class _Traits,
2075 class _UI, size_t _W, size_t _S, size_t _R>
2076basic_istream<_CharT, _Traits>&
2077operator>>(basic_istream<_CharT, _Traits>& __is,
2078 subtract_with_carry_engine<_UI, _W, _S, _R>& __x);
2079
2080template<class _UIntType, size_t __w, size_t __s, size_t __r>
2081class subtract_with_carry_engine
2082{
2083public:
2084 // types
2085 typedef _UIntType result_type;
2086
2087private:
2088 result_type __x_[__r];
2089 result_type __c_;
2090 size_t __i_;
2091
2092 static const result_type _Dt = numeric_limits<result_type>::digits;
2093 static_assert( 0 < __w, "subtract_with_carry_engine invalid parameters");
2094 static_assert(__w <= _Dt, "subtract_with_carry_engine invalid parameters");
2095 static_assert( 0 < __s, "subtract_with_carry_engine invalid parameters");
2096 static_assert(__s < __r, "subtract_with_carry_engine invalid parameters");
2097public:
2098 static const result_type _Min = 0;
2099 static const result_type _Max = __w == _Dt ? result_type(~0) :
2100 (result_type(1) << __w) - result_type(1);
2101 static_assert(_Min < _Max, "subtract_with_carry_engine invalid parameters");
2102
2103 // engine characteristics
2104 static const/*expr*/ size_t word_size = __w;
2105 static const/*expr*/ size_t short_lag = __s;
2106 static const/*expr*/ size_t long_lag = __r;
2107 static const/*expr*/ result_type min() { return _Min; }
2108 static const/*expr*/ result_type max() { return _Max; }
2109 static const/*expr*/ result_type default_seed = 19780503u;
2110
2111 // constructors and seeding functions
2112 explicit subtract_with_carry_engine(result_type __sd = default_seed)
2113 {seed(__sd);}
2114 template<class _Sseq> explicit subtract_with_carry_engine(_Sseq& __q)
2115 {seed(__q);}
2116 void seed(result_type __sd = default_seed)
2117 {seed(__sd, integral_constant<unsigned, 1 + (__w - 1) / 32>());}
2118 template<class _Sseq>
2119 typename enable_if
2120 <
2121 !is_convertible<_Sseq, result_type>::value,
2122 void
2123 >::type
2124 seed(_Sseq& __q)
2125 {__seed(__q, integral_constant<unsigned, 1 + (__w - 1) / 32>());}
2126
2127 // generating functions
2128 result_type operator()();
2129 void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
2130
2131 template<class _UI, size_t _W, size_t _S, size_t _R>
2132 friend
2133 bool
2134 operator==(
2135 const subtract_with_carry_engine<_UI, _W, _S, _R>& __x,
2136 const subtract_with_carry_engine<_UI, _W, _S, _R>& __y);
2137
2138 template<class _UI, size_t _W, size_t _S, size_t _R>
2139 friend
2140 bool
2141 operator!=(
2142 const subtract_with_carry_engine<_UI, _W, _S, _R>& __x,
2143 const subtract_with_carry_engine<_UI, _W, _S, _R>& __y);
2144
2145 template <class _CharT, class _Traits,
2146 class _UI, size_t _W, size_t _S, size_t _R>
2147 friend
2148 basic_ostream<_CharT, _Traits>&
2149 operator<<(basic_ostream<_CharT, _Traits>& __os,
2150 const subtract_with_carry_engine<_UI, _W, _S, _R>& __x);
2151
2152 template <class _CharT, class _Traits,
2153 class _UI, size_t _W, size_t _S, size_t _R>
2154 friend
2155 basic_istream<_CharT, _Traits>&
2156 operator>>(basic_istream<_CharT, _Traits>& __is,
2157 subtract_with_carry_engine<_UI, _W, _S, _R>& __x);
2158
2159private:
2160
2161 void seed(result_type __sd, integral_constant<unsigned, 1>);
2162 void seed(result_type __sd, integral_constant<unsigned, 2>);
2163 template<class _Sseq>
2164 void __seed(_Sseq& __q, integral_constant<unsigned, 1>);
2165 template<class _Sseq>
2166 void __seed(_Sseq& __q, integral_constant<unsigned, 2>);
2167};
2168
2169template<class _UIntType, size_t __w, size_t __s, size_t __r>
2170void
2171subtract_with_carry_engine<_UIntType, __w, __s, __r>::seed(result_type __sd,
2172 integral_constant<unsigned, 1>)
2173{
2174 linear_congruential_engine<result_type, 40014u, 0u, 2147483563u>
2175 __e(__sd == 0u ? default_seed : __sd);
2176 for (size_t __i = 0; __i < __r; ++__i)
2177 __x_[__i] = static_cast<result_type>(__e() & _Max);
2178 __c_ = __x_[__r-1] == 0;
2179 __i_ = 0;
2180}
2181
2182template<class _UIntType, size_t __w, size_t __s, size_t __r>
2183void
2184subtract_with_carry_engine<_UIntType, __w, __s, __r>::seed(result_type __sd,
2185 integral_constant<unsigned, 2>)
2186{
2187 linear_congruential_engine<result_type, 40014u, 0u, 2147483563u>
2188 __e(__sd == 0u ? default_seed : __sd);
2189 for (size_t __i = 0; __i < __r; ++__i)
2190 __x_[__i] = static_cast<result_type>(
2191 (__e() + ((uint64_t)__e() << 32)) & _Max);
2192 __c_ = __x_[__r-1] == 0;
2193 __i_ = 0;
2194}
2195
2196template<class _UIntType, size_t __w, size_t __s, size_t __r>
2197template<class _Sseq>
2198void
2199subtract_with_carry_engine<_UIntType, __w, __s, __r>::__seed(_Sseq& __q,
2200 integral_constant<unsigned, 1>)
2201{
2202 const unsigned __k = 1;
2203 uint32_t __ar[__r * __k];
2204 __q.generate(__ar, __ar + __r * __k);
2205 for (size_t __i = 0; __i < __r; ++__i)
2206 __x_[__i] = static_cast<result_type>(__ar[__i] & _Max);
2207 __c_ = __x_[__r-1] == 0;
2208 __i_ = 0;
2209}
2210
2211template<class _UIntType, size_t __w, size_t __s, size_t __r>
2212template<class _Sseq>
2213void
2214subtract_with_carry_engine<_UIntType, __w, __s, __r>::__seed(_Sseq& __q,
2215 integral_constant<unsigned, 2>)
2216{
2217 const unsigned __k = 2;
2218 uint32_t __ar[__r * __k];
2219 __q.generate(__ar, __ar + __r * __k);
2220 for (size_t __i = 0; __i < __r; ++__i)
2221 __x_[__i] = static_cast<result_type>(
2222 (__ar[2 * __i] + ((uint64_t)__ar[2 * __i + 1] << 32)) & _Max);
2223 __c_ = __x_[__r-1] == 0;
2224 __i_ = 0;
2225}
2226
2227template<class _UIntType, size_t __w, size_t __s, size_t __r>
2228_UIntType
2229subtract_with_carry_engine<_UIntType, __w, __s, __r>::operator()()
2230{
2231 const result_type& __xs = __x_[(__i_ + (__r - __s)) % __r];
2232 result_type& __xr = __x_[__i_];
2233 result_type __new_c = __c_ == 0 ? __xs < __xr : __xs != 0 ? __xs <= __xr : 1;
2234 __xr = (__xs - __xr - __c_) & _Max;
2235 __c_ = __new_c;
2236 __i_ = (__i_ + 1) % __r;
2237 return __xr;
2238}
2239
2240template<class _UI, size_t _W, size_t _S, size_t _R>
2241bool
2242operator==(
2243 const subtract_with_carry_engine<_UI, _W, _S, _R>& __x,
2244 const subtract_with_carry_engine<_UI, _W, _S, _R>& __y)
2245{
2246 if (__x.__c_ != __y.__c_)
2247 return false;
2248 if (__x.__i_ == __y.__i_)
2249 return _STD::equal(__x.__x_, __x.__x_ + _R, __y.__x_);
2250 if (__x.__i_ == 0 || __y.__i_ == 0)
2251 {
2252 size_t __j = _STD::min(_R - __x.__i_, _R - __y.__i_);
2253 if (!_STD::equal(__x.__x_ + __x.__i_, __x.__x_ + __x.__i_ + __j,
2254 __y.__x_ + __y.__i_))
2255 return false;
2256 if (__x.__i_ == 0)
2257 return _STD::equal(__x.__x_ + __j, __x.__x_ + _R, __y.__x_);
2258 return _STD::equal(__x.__x_, __x.__x_ + (_R - __j), __y.__x_ + __j);
2259 }
2260 if (__x.__i_ < __y.__i_)
2261 {
2262 size_t __j = _R - __y.__i_;
2263 if (!_STD::equal(__x.__x_ + __x.__i_, __x.__x_ + (__x.__i_ + __j),
2264 __y.__x_ + __y.__i_))
2265 return false;
2266 if (!_STD::equal(__x.__x_ + (__x.__i_ + __j), __x.__x_ + _R,
2267 __y.__x_))
2268 return false;
2269 return _STD::equal(__x.__x_, __x.__x_ + __x.__i_,
2270 __y.__x_ + (_R - (__x.__i_ + __j)));
2271 }
2272 size_t __j = _R - __x.__i_;
2273 if (!_STD::equal(__y.__x_ + __y.__i_, __y.__x_ + (__y.__i_ + __j),
2274 __x.__x_ + __x.__i_))
2275 return false;
2276 if (!_STD::equal(__y.__x_ + (__y.__i_ + __j), __y.__x_ + _R,
2277 __x.__x_))
2278 return false;
2279 return _STD::equal(__y.__x_, __y.__x_ + __y.__i_,
2280 __x.__x_ + (_R - (__y.__i_ + __j)));
2281}
2282
2283template<class _UI, size_t _W, size_t _S, size_t _R>
2284inline
2285bool
2286operator!=(
2287 const subtract_with_carry_engine<_UI, _W, _S, _R>& __x,
2288 const subtract_with_carry_engine<_UI, _W, _S, _R>& __y)
2289{
2290 return !(__x == __y);
2291}
2292
2293template <class _CharT, class _Traits,
2294 class _UI, size_t _W, size_t _S, size_t _R>
2295basic_ostream<_CharT, _Traits>&
2296operator<<(basic_ostream<_CharT, _Traits>& __os,
2297 const subtract_with_carry_engine<_UI, _W, _S, _R>& __x)
2298{
2299 __save_flags<_CharT, _Traits> _(__os);
2300 __os.flags(ios_base::dec | ios_base::left);
2301 _CharT __sp = __os.widen(' ');
2302 __os.fill(__sp);
2303 __os << __x.__x_[__x.__i_];
2304 for (size_t __j = __x.__i_ + 1; __j < _R; ++__j)
2305 __os << __sp << __x.__x_[__j];
2306 for (size_t __j = 0; __j < __x.__i_; ++__j)
2307 __os << __sp << __x.__x_[__j];
2308 __os << __sp << __x.__c_;
2309 return __os;
2310}
2311
2312template <class _CharT, class _Traits,
2313 class _UI, size_t _W, size_t _S, size_t _R>
2314basic_istream<_CharT, _Traits>&
2315operator>>(basic_istream<_CharT, _Traits>& __is,
2316 subtract_with_carry_engine<_UI, _W, _S, _R>& __x)
2317{
2318 __save_flags<_CharT, _Traits> _(__is);
2319 __is.flags(ios_base::dec | ios_base::skipws);
2320 _UI __t[_R+1];
2321 for (size_t __i = 0; __i < _R+1; ++__i)
2322 __is >> __t[__i];
2323 if (!__is.fail())
2324 {
2325 for (size_t __i = 0; __i < _R; ++__i)
2326 __x.__x_[__i] = __t[__i];
2327 __x.__c_ = __t[_R];
2328 __x.__i_ = 0;
2329 }
2330 return __is;
2331}
2332
2333typedef subtract_with_carry_engine<uint_fast32_t, 24, 10, 24> ranlux24_base;
2334typedef subtract_with_carry_engine<uint_fast64_t, 48, 5, 12> ranlux48_base;
2335
2336// discard_block_engine
2337
2338template<class _Engine, size_t __p, size_t __r>
2339class discard_block_engine
2340{
2341 _Engine __e_;
2342 int __n_;
2343
2344 static_assert( 0 < __r, "discard_block_engine invalid parameters");
2345 static_assert(__r <= __p, "discard_block_engine invalid parameters");
2346public:
2347 // types
2348 typedef typename _Engine::result_type result_type;
2349
2350 // engine characteristics
2351 static const/*expr*/ size_t block_size = __p;
2352 static const/*expr*/ size_t used_block = __r;
2353
2354 // Temporary work around for lack of constexpr
2355 static const result_type _Min = _Engine::_Min;
2356 static const result_type _Max = _Engine::_Max;
2357
2358 static const/*expr*/ result_type min() { return _Engine::min(); }
2359 static const/*expr*/ result_type max() { return _Engine::max(); }
2360
2361 // constructors and seeding functions
2362 discard_block_engine() : __n_(0) {}
2363// explicit discard_block_engine(const _Engine& __e);
2364// explicit discard_block_engine(_Engine&& __e);
2365 explicit discard_block_engine(result_type __sd) : __e_(__sd), __n_(0) {}
2366 template<class _Sseq> explicit discard_block_engine(_Sseq& __q)
2367 : __e_(__q), __n_(0) {}
2368 void seed() {__e_.seed(); __n_ = 0;}
2369 void seed(result_type __sd) {__e_.seed(__sd); __n_ = 0;}
2370 template<class _Sseq> void seed(_Sseq& __q) {__e_.seed(__q); __n_ = 0;}
2371
2372 // generating functions
2373 result_type operator()();
2374 void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
2375
2376 // property functions
2377 const _Engine& base() const {return __e_;}
2378
2379 template<class _Eng, size_t _P, size_t _R>
2380 friend
2381 bool
2382 operator==(
2383 const discard_block_engine<_Eng, _P, _R>& __x,
2384 const discard_block_engine<_Eng, _P, _R>& __y);
2385
2386 template<class _Eng, size_t _P, size_t _R>
2387 friend
2388 bool
2389 operator!=(
2390 const discard_block_engine<_Eng, _P, _R>& __x,
2391 const discard_block_engine<_Eng, _P, _R>& __y);
2392
2393 template <class _CharT, class _Traits,
2394 class _Eng, size_t _P, size_t _R>
2395 friend
2396 basic_ostream<_CharT, _Traits>&
2397 operator<<(basic_ostream<_CharT, _Traits>& __os,
2398 const discard_block_engine<_Eng, _P, _R>& __x);
2399
2400 template <class _CharT, class _Traits,
2401 class _Eng, size_t _P, size_t _R>
2402 friend
2403 basic_istream<_CharT, _Traits>&
2404 operator>>(basic_istream<_CharT, _Traits>& __is,
2405 discard_block_engine<_Eng, _P, _R>& __x);
2406};
2407
2408template<class _Engine, size_t __p, size_t __r>
2409typename discard_block_engine<_Engine, __p, __r>::result_type
2410discard_block_engine<_Engine, __p, __r>::operator()()
2411{
2412 if (__n_ >= __r)
2413 {
2414 __e_.discard(__p - __r);
2415 __n_ = 0;
2416 }
2417 ++__n_;
2418 return __e_();
2419}
2420
2421template<class _Eng, size_t _P, size_t _R>
2422inline
2423bool
2424operator==(const discard_block_engine<_Eng, _P, _R>& __x,
2425 const discard_block_engine<_Eng, _P, _R>& __y)
2426{
2427 return __x.__n_ == __y.__n_ && __x.__e_ == __y.__e_;
2428}
2429
2430template<class _Eng, size_t _P, size_t _R>
2431inline
2432bool
2433operator!=(const discard_block_engine<_Eng, _P, _R>& __x,
2434 const discard_block_engine<_Eng, _P, _R>& __y)
2435{
2436 return !(__x == __y);
2437}
2438
2439template <class _CharT, class _Traits,
2440 class _Eng, size_t _P, size_t _R>
2441basic_ostream<_CharT, _Traits>&
2442operator<<(basic_ostream<_CharT, _Traits>& __os,
2443 const discard_block_engine<_Eng, _P, _R>& __x)
2444{
2445 __save_flags<_CharT, _Traits> _(__os);
2446 __os.flags(ios_base::dec | ios_base::left);
2447 _CharT __sp = __os.widen(' ');
2448 __os.fill(__sp);
2449 return __os << __x.__e_ << __sp << __x.__n_;
2450}
2451
2452template <class _CharT, class _Traits,
2453 class _Eng, size_t _P, size_t _R>
2454basic_istream<_CharT, _Traits>&
2455operator>>(basic_istream<_CharT, _Traits>& __is,
2456 discard_block_engine<_Eng, _P, _R>& __x)
2457{
2458 __save_flags<_CharT, _Traits> _(__is);
2459 __is.flags(ios_base::dec | ios_base::skipws);
2460 _Eng __e;
2461 int __n;
2462 __is >> __e >> __n;
2463 if (!__is.fail())
2464 {
2465 __x.__e_ = __e;
2466 __x.__n_ = __n;
2467 }
2468 return __is;
2469}
2470
2471typedef discard_block_engine<ranlux24_base, 223, 23> ranlux24;
2472typedef discard_block_engine<ranlux48_base, 389, 11> ranlux48;
2473
2474// independent_bits_engine
2475
2476template <unsigned long long _X, size_t _R>
2477struct __log2_imp
2478{
2479 static const size_t value = _X & ((unsigned long long)(1) << _R) ? _R
2480 : __log2_imp<_X, _R - 1>::value;
2481};
2482
2483template <unsigned long long _X>
2484struct __log2_imp<_X, 0>
2485{
2486 static const size_t value = 0;
2487};
2488
2489template <size_t _R>
2490struct __log2_imp<0, _R>
2491{
2492 static const size_t value = _R + 1;
2493};
2494
2495template <class _UI, _UI _X>
2496struct __log2
2497{
2498 static const size_t value = __log2_imp<_X,
2499 sizeof(_UI) * __CHAR_BIT__ - 1>::value;
2500};
2501
2502template<class _Engine, size_t __w, class _UIntType>
2503class independent_bits_engine
2504{
2505 template <class _UI, _UI _R0, size_t _W, size_t _M>
2506 class __get_n
2507 {
2508 static const size_t _Dt = numeric_limits<_UI>::digits;
2509 static const size_t _N = _W / _M + (_W % _M != 0);
2510 static const size_t _W0 = _W / _N;
2511 static const _UI _Y0 = _W0 >= _Dt ? 0 : (_R0 >> _W0) << _W0;
2512 public:
2513 static const size_t value = _R0 - _Y0 > _Y0 / _N ? _N + 1 : _N;
2514 };
2515public:
2516 // types
2517 typedef _UIntType result_type;
2518
2519private:
2520 _Engine __e_;
2521
2522 static const result_type _Dt = numeric_limits<result_type>::digits;
2523 static_assert( 0 < __w, "independent_bits_engine invalid parameters");
2524 static_assert(__w <= _Dt, "independent_bits_engine invalid parameters");
2525
2526 typedef typename _Engine::result_type _Engine_result_type;
2527 typedef typename conditional
2528 <
2529 sizeof(_Engine_result_type) <= sizeof(result_type),
2530 result_type,
2531 _Engine_result_type
2532 >::type _Working_result_type;
2533 // Temporary work around for lack of constexpr
2534 static const _Working_result_type _R = _Engine::_Max - _Engine::_Min
2535 + _Working_result_type(1);
2536 static const size_t __m = __log2<_Working_result_type, _R>::value;
2537 static const size_t __n = __get_n<_Working_result_type, _R, __w, __m>::value;
2538 static const size_t __w0 = __w / __n;
2539 static const size_t __n0 = __n - __w % __n;
2540 static const size_t _WDt = numeric_limits<_Working_result_type>::digits;
2541 static const size_t _EDt = numeric_limits<_Engine_result_type>::digits;
2542 static const _Working_result_type __y0 = __w0 >= _WDt ? 0 :
2543 (_R >> __w0) << __w0;
2544 static const _Working_result_type __y1 = __w0 >= _WDt - 1 ? 0 :
2545 (_R >> (__w0+1)) << (__w0+1);
2546 static const _Engine_result_type __mask0 = __w0 > 0 ?
2547 _Engine_result_type(~0) >> (_EDt - __w0) :
2548 _Engine_result_type(0);
2549 static const _Engine_result_type __mask1 = __w0 < _EDt - 1 ?
2550 _Engine_result_type(~0) >> (_EDt - (__w0 + 1)) :
2551 _Engine_result_type(~0);
2552public:
2553 static const result_type _Min = 0;
2554 static const result_type _Max = __w == _Dt ? result_type(~0) :
2555 (result_type(1) << __w) - result_type(1);
2556 static_assert(_Min < _Max, "independent_bits_engine invalid parameters");
2557
2558 // engine characteristics
2559 static const/*expr*/ result_type min() { return _Min; }
2560 static const/*expr*/ result_type max() { return _Max; }
2561
2562 // constructors and seeding functions
2563 independent_bits_engine() {}
2564// explicit independent_bits_engine(const _Engine& __e);
2565// explicit independent_bits_engine(_Engine&& __e);
2566 explicit independent_bits_engine(result_type __sd) : __e_(__sd) {}
2567 template<class _Sseq> explicit independent_bits_engine(_Sseq& __q)
2568 : __e_(__q) {}
2569 void seed() {__e_.seed();}
2570 void seed(result_type __sd) {__e_.seed(__sd);}
2571 template<class _Sseq> void seed(_Sseq& __q) {__e_.seed(__q);}
2572
2573 // generating functions
2574 result_type operator()() {return __eval(integral_constant<bool, _R != 0>());}
2575 void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
2576
2577 // property functions
2578 const _Engine& base() const {return __e_;}
2579
2580 template<class _Eng, size_t _W, class _UI>
2581 friend
2582 bool
2583 operator==(
2584 const independent_bits_engine<_Eng, _W, _UI>& __x,
2585 const independent_bits_engine<_Eng, _W, _UI>& __y);
2586
2587 template<class _Eng, size_t _W, class _UI>
2588 friend
2589 bool
2590 operator!=(
2591 const independent_bits_engine<_Eng, _W, _UI>& __x,
2592 const independent_bits_engine<_Eng, _W, _UI>& __y);
2593
2594 template <class _CharT, class _Traits,
2595 class _Eng, size_t _W, class _UI>
2596 friend
2597 basic_ostream<_CharT, _Traits>&
2598 operator<<(basic_ostream<_CharT, _Traits>& __os,
2599 const independent_bits_engine<_Eng, _W, _UI>& __x);
2600
2601 template <class _CharT, class _Traits,
2602 class _Eng, size_t _W, class _UI>
2603 friend
2604 basic_istream<_CharT, _Traits>&
2605 operator>>(basic_istream<_CharT, _Traits>& __is,
2606 independent_bits_engine<_Eng, _W, _UI>& __x);
2607
2608private:
2609 result_type __eval(false_type);
2610 result_type __eval(true_type);
2611
2612 template <size_t __count>
2613 static
2614 typename enable_if
2615 <
2616 __count < _Dt,
2617 result_type
2618 >::type
2619 __lshift(result_type __x) {return __x << __count;}
2620
2621 template <size_t __count>
2622 static
2623 typename enable_if
2624 <
2625 (__count >= _Dt),
2626 result_type
2627 >::type
2628 __lshift(result_type __x) {return result_type(0);}
2629};
2630
2631template<class _Engine, size_t __w, class _UIntType>
2632inline
2633_UIntType
2634independent_bits_engine<_Engine, __w, _UIntType>::__eval(false_type)
2635{
2636 return static_cast<result_type>(__e_() & __mask0);
2637}
2638
2639template<class _Engine, size_t __w, class _UIntType>
2640_UIntType
2641independent_bits_engine<_Engine, __w, _UIntType>::__eval(true_type)
2642{
2643 result_type _S = 0;
2644 for (size_t __k = 0; __k < __n0; ++__k)
2645 {
2646 _Engine_result_type __u;
2647 do
2648 {
2649 __u = __e_() - _Engine::min();
2650 } while (__u >= __y0);
2651 _S = static_cast<result_type>(__lshift<__w0>(_S) + (__u & __mask0));
2652 }
2653 for (size_t __k = __n0; __k < __n; ++__k)
2654 {
2655 _Engine_result_type __u;
2656 do
2657 {
2658 __u = __e_() - _Engine::min();
2659 } while (__u >= __y1);
2660 _S = static_cast<result_type>(__lshift<__w0+1>(_S) + (__u & __mask1));
2661 }
2662 return _S;
2663}
2664
2665template<class _Eng, size_t _W, class _UI>
2666inline
2667bool
2668operator==(
2669 const independent_bits_engine<_Eng, _W, _UI>& __x,
2670 const independent_bits_engine<_Eng, _W, _UI>& __y)
2671{
2672 return __x.base() == __y.base();
2673}
2674
2675template<class _Eng, size_t _W, class _UI>
2676inline
2677bool
2678operator!=(
2679 const independent_bits_engine<_Eng, _W, _UI>& __x,
2680 const independent_bits_engine<_Eng, _W, _UI>& __y)
2681{
2682 return !(__x == __y);
2683}
2684
2685template <class _CharT, class _Traits,
2686 class _Eng, size_t _W, class _UI>
2687basic_ostream<_CharT, _Traits>&
2688operator<<(basic_ostream<_CharT, _Traits>& __os,
2689 const independent_bits_engine<_Eng, _W, _UI>& __x)
2690{
2691 return __os << __x.base();
2692}
2693
2694template <class _CharT, class _Traits,
2695 class _Eng, size_t _W, class _UI>
2696basic_istream<_CharT, _Traits>&
2697operator>>(basic_istream<_CharT, _Traits>& __is,
2698 independent_bits_engine<_Eng, _W, _UI>& __x)
2699{
2700 _Eng __e;
2701 __is >> __e;
2702 if (!__is.fail())
2703 __x.__e_ = __e;
2704 return __is;
2705}
2706
2707// shuffle_order_engine
2708
2709template <uint64_t _Xp, uint64_t _Yp>
2710struct __ugcd
2711{
2712 static const uint64_t value = __ugcd<_Yp, _Xp % _Yp>::value;
2713};
2714
2715template <uint64_t _Xp>
2716struct __ugcd<_Xp, 0>
2717{
2718 static const uint64_t value = _Xp;
2719};
2720
2721template <uint64_t _N, uint64_t _D>
2722class __uratio
2723{
2724 static_assert(_D != 0, "__uratio divide by 0");
2725 static const uint64_t __gcd = __ugcd<_N, _D>::value;
2726public:
2727 static const uint64_t num = _N / __gcd;
2728 static const uint64_t den = _D / __gcd;
2729
2730 typedef __uratio<num, den> type;
2731};
2732
2733template<class _Engine, size_t __k>
2734class shuffle_order_engine
2735{
2736 static_assert(0 < __k, "shuffle_order_engine invalid parameters");
2737public:
2738 // types
2739 typedef typename _Engine::result_type result_type;
2740
2741private:
2742 _Engine __e_;
2743 result_type _V_[__k];
2744 result_type _Y_;
2745
2746public:
2747 // engine characteristics
2748 static const/*expr*/ size_t table_size = __k;
2749
2750 static const result_type _Min = _Engine::_Min;
2751 static const result_type _Max = _Engine::_Max;
2752 static_assert(_Min < _Max, "shuffle_order_engine invalid parameters");
2753 static const/*expr*/ result_type min() { return _Min; }
2754 static const/*expr*/ result_type max() { return _Max; }
2755
2756 static const unsigned long long _R = _Max - _Min + 1ull;
2757
2758 // constructors and seeding functions
2759 shuffle_order_engine() {__init();}
2760// explicit shuffle_order_engine(const _Engine& __e);
2761// explicit shuffle_order_engine(_Engine&& e);
2762 explicit shuffle_order_engine(result_type __sd) : __e_(__sd) {__init();}
2763 template<class _Sseq> explicit shuffle_order_engine(_Sseq& __q)
2764 : __e_(__q) {__init();}
2765 void seed() {__e_.seed(); __init();}
2766 void seed(result_type __sd) {__e_.seed(__sd); __init();}
2767 template<class _Sseq> void seed(_Sseq& __q) {__e_.seed(__q); __init();}
2768
2769 // generating functions
2770 result_type operator()() {return __eval(integral_constant<bool, _R != 0>());}
2771 void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
2772
2773 // property functions
2774 const _Engine& base() const {return __e_;}
2775
2776private:
2777 template<class _Eng, size_t _K>
2778 friend
2779 bool
2780 operator==(
2781 const shuffle_order_engine<_Eng, _K>& __x,
2782 const shuffle_order_engine<_Eng, _K>& __y);
2783
2784 template<class _Eng, size_t _K>
2785 friend
2786 bool
2787 operator!=(
2788 const shuffle_order_engine<_Eng, _K>& __x,
2789 const shuffle_order_engine<_Eng, _K>& __y);
2790
2791 template <class _CharT, class _Traits,
2792 class _Eng, size_t _K>
2793 friend
2794 basic_ostream<_CharT, _Traits>&
2795 operator<<(basic_ostream<_CharT, _Traits>& __os,
2796 const shuffle_order_engine<_Eng, _K>& __x);
2797
2798 template <class _CharT, class _Traits,
2799 class _Eng, size_t _K>
2800 friend
2801 basic_istream<_CharT, _Traits>&
2802 operator>>(basic_istream<_CharT, _Traits>& __is,
2803 shuffle_order_engine<_Eng, _K>& __x);
2804
2805 void __init()
2806 {
2807 for (size_t __i = 0; __i < __k; ++__i)
2808 _V_[__i] = __e_();
2809 _Y_ = __e_();
2810 }
2811
2812 result_type __eval(false_type) {return __eval2(integral_constant<bool, __k & 1>());}
2813 result_type __eval(true_type) {return __eval(__uratio<__k, _R>());}
2814
2815 result_type __eval2(false_type) {return __eval(__uratio<__k/2, 0x8000000000000000ull>());}
2816 result_type __eval2(true_type) {return __evalf<__k, 0>();}
2817
2818 template <uint64_t _N, uint64_t _D>
2819 typename enable_if
2820 <
2821 (__uratio<_N, _D>::num > 0xFFFFFFFFFFFFFFFFull / (_Max - _Min)),
2822 result_type
2823 >::type
2824 __eval(__uratio<_N, _D>)
2825 {return __evalf<__uratio<_N, _D>::num, __uratio<_N, _D>::den>();}
2826
2827 template <uint64_t _N, uint64_t _D>
2828 typename enable_if
2829 <
2830 __uratio<_N, _D>::num <= 0xFFFFFFFFFFFFFFFFull / (_Max - _Min),
2831 result_type
2832 >::type
2833 __eval(__uratio<_N, _D>)
2834 {
2835 const size_t __j = static_cast<size_t>(__uratio<_N, _D>::num * (_Y_ - _Min)
2836 / __uratio<_N, _D>::den);
2837 _Y_ = _V_[__j];
2838 _V_[__j] = __e_();
2839 return _Y_;
2840 }
2841
2842 template <uint64_t __n, uint64_t __d>
2843 result_type __evalf()
2844 {
2845 const double _F = __d == 0 ?
2846 __n / (2. * 0x8000000000000000ull) :
2847 __n / (double)__d;
2848 const size_t __j = static_cast<size_t>(_F * (_Y_ - _Min));
2849 _Y_ = _V_[__j];
2850 _V_[__j] = __e_();
2851 return _Y_;
2852 }
2853};
2854
2855template<class _Eng, size_t _K>
2856bool
2857operator==(
2858 const shuffle_order_engine<_Eng, _K>& __x,
2859 const shuffle_order_engine<_Eng, _K>& __y)
2860{
2861 return __x._Y_ == __y._Y_ && _STD::equal(__x._V_, __x._V_ + _K, __y._V_) &&
2862 __x.__e_ == __y.__e_;
2863}
2864
2865template<class _Eng, size_t _K>
2866inline
2867bool
2868operator!=(
2869 const shuffle_order_engine<_Eng, _K>& __x,
2870 const shuffle_order_engine<_Eng, _K>& __y)
2871{
2872 return !(__x == __y);
2873}
2874
2875template <class _CharT, class _Traits,
2876 class _Eng, size_t _K>
2877basic_ostream<_CharT, _Traits>&
2878operator<<(basic_ostream<_CharT, _Traits>& __os,
2879 const shuffle_order_engine<_Eng, _K>& __x)
2880{
2881 __save_flags<_CharT, _Traits> _(__os);
2882 __os.flags(ios_base::dec | ios_base::left);
2883 _CharT __sp = __os.widen(' ');
2884 __os.fill(__sp);
2885 __os << __x.__e_ << __sp << __x._V_[0];
2886 for (size_t __i = 1; __i < _K; ++__i)
2887 __os << __sp << __x._V_[__i];
2888 return __os << __sp << __x._Y_;
2889}
2890
2891template <class _CharT, class _Traits,
2892 class _Eng, size_t _K>
2893basic_istream<_CharT, _Traits>&
2894operator>>(basic_istream<_CharT, _Traits>& __is,
2895 shuffle_order_engine<_Eng, _K>& __x)
2896{
2897 typedef typename shuffle_order_engine<_Eng, _K>::result_type result_type;
2898 __save_flags<_CharT, _Traits> _(__is);
2899 __is.flags(ios_base::dec | ios_base::skipws);
2900 _Eng __e;
2901 result_type _V[_K+1];
2902 __is >> __e;
2903 for (size_t __i = 0; __i < _K+1; ++__i)
2904 __is >> _V[__i];
2905 if (!__is.fail())
2906 {
2907 __x.__e_ = __e;
2908 for (size_t __i = 0; __i < _K; ++__i)
2909 __x._V_[__i] = _V[__i];
2910 __x._Y_ = _V[_K];
2911 }
2912 return __is;
2913}
2914
2915typedef shuffle_order_engine<minstd_rand0, 256> knuth_b;
2916
2917// random_device
2918
2919class random_device
2920{
2921 int __f_;
2922public:
2923 // types
2924 typedef unsigned result_type;
2925
2926 // generator characteristics
2927 static const result_type _Min = 0;
2928 static const result_type _Max = 0xFFFFFFFFu;
2929
2930 static const/*expr*/ result_type min() { return _Min;}
2931 static const/*expr*/ result_type max() { return _Max;}
2932
2933 // constructors
2934 explicit random_device(const string& __token = "/dev/urandom");
2935 ~random_device();
2936
2937 // generating functions
2938 result_type operator()();
2939
2940 // property functions
2941 double entropy() const;
2942
2943private:
2944 // no copy functions
2945 random_device(const random_device&); // = delete;
2946 random_device& operator=(const random_device&); // = delete;
2947};
2948
2949// seed_seq
2950
2951class seed_seq
2952{
2953public:
2954 // types
2955 typedef uint32_t result_type;
2956
2957private:
2958 vector<result_type> __v_;
2959
2960 template<class _InputIterator>
2961 void init(_InputIterator __first, _InputIterator __last);
2962public:
2963 // constructors
2964 seed_seq() {}
2965 template<class _Tp>
2966 seed_seq(initializer_list<_Tp> __il) {init(__il.begin(), __il.end());}
2967
2968 template<class _InputIterator>
2969 seed_seq(_InputIterator __first, _InputIterator __last)
2970 {init(__first, __last);}
2971
2972 // generating functions
2973 template<class _RandomAccessIterator>
2974 void generate(_RandomAccessIterator __first, _RandomAccessIterator __last);
2975
2976 // property functions
2977 size_t size() const {return __v_.size();}
2978 template<class _OutputIterator>
2979 void param(_OutputIterator __dest) const
2980 {_STD::copy(__v_.begin(), __v_.end(), __dest);}
2981
2982private:
2983 // no copy functions
2984 seed_seq(const seed_seq&); // = delete;
2985 void operator=(const seed_seq&); // = delete;
2986
2987 static result_type _T(result_type __x) {return __x ^ (__x >> 27);}
2988};
2989
2990template<class _InputIterator>
2991void
2992seed_seq::init(_InputIterator __first, _InputIterator __last)
2993{
2994 for (_InputIterator __s = __first; __s != __last; ++__s)
2995 __v_.push_back(*__s & 0xFFFFFFFF);
2996}
2997
2998template<class _RandomAccessIterator>
2999void
3000seed_seq::generate(_RandomAccessIterator __first, _RandomAccessIterator __last)
3001{
3002 if (__first != __last)
3003 {
3004 _STD::fill(__first, __last, 0x8b8b8b8b);
3005 const size_t __n = static_cast<size_t>(__last - __first);
3006 const size_t __s = __v_.size();
3007 const size_t __t = (__n >= 623) ? 11
3008 : (__n >= 68) ? 7
3009 : (__n >= 39) ? 5
3010 : (__n >= 7) ? 3
3011 : (__n - 1) / 2;
3012 const size_t __p = (__n - __t) / 2;
3013 const size_t __q = __p + __t;
3014 const size_t __m = _STD::max(__s + 1, __n);
3015 // __k = 0;
3016 {
3017 result_type __r = 1664525 * _T(__first[0] ^ __first[__p]
3018 ^ __first[__n - 1]);
3019 __first[__p] += __r;
3020 __r += __s;
3021 __first[__q] += __r;
3022 __first[0] = __r;
3023 }
3024 for (size_t __k = 1; __k <= __s; ++__k)
3025 {
3026 const size_t __kmodn = __k % __n;
3027 const size_t __kpmodn = (__k + __p) % __n;
3028 result_type __r = 1664525 * _T(__first[__kmodn] ^ __first[__kpmodn]
3029 ^ __first[(__k - 1) % __n]);
3030 __first[__kpmodn] += __r;
3031 __r += __kmodn + __v_[__k-1];
3032 __first[(__k + __q) % __n] += __r;
3033 __first[__kmodn] = __r;
3034 }
3035 for (size_t __k = __s + 1; __k < __m; ++__k)
3036 {
3037 const size_t __kmodn = __k % __n;
3038 const size_t __kpmodn = (__k + __p) % __n;
3039 result_type __r = 1664525 * _T(__first[__kmodn] ^ __first[__kpmodn]
3040 ^ __first[(__k - 1) % __n]);
3041 __first[__kpmodn] += __r;
3042 __r += __kmodn;
3043 __first[(__k + __q) % __n] += __r;
3044 __first[__kmodn] = __r;
3045 }
3046 for (size_t __k = __m; __k < __m + __n; ++__k)
3047 {
3048 const size_t __kmodn = __k % __n;
3049 const size_t __kpmodn = (__k + __p) % __n;
3050 result_type __r = 1566083941 * _T(__first[__kmodn] +
3051 __first[__kpmodn] +
3052 __first[(__k - 1) % __n]);
3053 __first[__kpmodn] ^= __r;
3054 __r -= __kmodn;
3055 __first[(__k + __q) % __n] ^= __r;
3056 __first[__kmodn] = __r;
3057 }
3058 }
3059}
3060
Howard Hinnant30a840f2010-05-12 17:08:57 +00003061// generate_canonical
3062
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003063template<class _RealType, size_t __bits, class _URNG>
3064_RealType
3065generate_canonical(_URNG& __g)
3066{
3067 const size_t _Dt = numeric_limits<_RealType>::digits;
3068 const size_t __b = _Dt < __bits ? _Dt : __bits;
3069 const size_t __logR = __log2<uint64_t, _URNG::_Max - _URNG::_Min + uint64_t(1)>::value;
3070 const size_t __k = __b / __logR + (__b % __logR != 0) + (__b == 0);
3071 const _RealType _R = _URNG::_Max - _URNG::_Min + _RealType(1);
3072 _RealType __base = _R;
3073 _RealType _S = __g() - _URNG::_Min;
3074 for (size_t __i = 1; __i < __k; ++__i, __base *= _R)
3075 _S += (__g() - _URNG::_Min) * __base;
3076 return _S / __base;
3077}
3078
3079// __independent_bits_engine
3080
3081template<class _Engine, class _UIntType>
3082class __independent_bits_engine
3083{
3084public:
3085 // types
3086 typedef _UIntType result_type;
3087
3088private:
3089 typedef typename _Engine::result_type _Engine_result_type;
3090 typedef typename conditional
3091 <
3092 sizeof(_Engine_result_type) <= sizeof(result_type),
3093 result_type,
3094 _Engine_result_type
3095 >::type _Working_result_type;
3096
3097 _Engine& __e_;
3098 size_t __w_;
3099 size_t __w0_;
3100 size_t __n_;
3101 size_t __n0_;
3102 _Working_result_type __y0_;
3103 _Working_result_type __y1_;
3104 _Engine_result_type __mask0_;
3105 _Engine_result_type __mask1_;
3106
3107 static const _Working_result_type _R = _Engine::_Max - _Engine::_Min
3108 + _Working_result_type(1);
3109 static const size_t __m = __log2<_Working_result_type, _R>::value;
3110 static const size_t _WDt = numeric_limits<_Working_result_type>::digits;
3111 static const size_t _EDt = numeric_limits<_Engine_result_type>::digits;
3112
3113public:
3114 // constructors and seeding functions
3115 __independent_bits_engine(_Engine& __e, size_t __w);
3116
3117 // generating functions
3118 result_type operator()() {return __eval(integral_constant<bool, _R != 0>());}
3119
3120private:
3121 result_type __eval(false_type);
3122 result_type __eval(true_type);
3123};
3124
3125template<class _Engine, class _UIntType>
3126__independent_bits_engine<_Engine, _UIntType>
3127 ::__independent_bits_engine(_Engine& __e, size_t __w)
3128 : __e_(__e),
3129 __w_(__w)
3130{
3131 __n_ = __w_ / __m + (__w_ % __m != 0);
3132 __w0_ = __w_ / __n_;
3133 if (_R == 0)
3134 __y0_ = _R;
3135 else if (__w0_ < _WDt)
3136 __y0_ = (_R >> __w0_) << __w0_;
3137 else
3138 __y0_ = 0;
3139 if (_R - __y0_ > __y0_ / __n_)
3140 {
3141 ++__n_;
3142 __w0_ = __w_ / __n_;
3143 if (__w0_ < _WDt)
3144 __y0_ = (_R >> __w0_) << __w0_;
3145 else
3146 __y0_ = 0;
3147 }
3148 __n0_ = __n_ - __w_ % __n_;
3149 if (__w0_ < _WDt - 1)
3150 __y1_ = (_R >> (__w0_ + 1)) << (__w0_ + 1);
3151 else
3152 __y1_ = 0;
3153 __mask0_ = __w0_ > 0 ? _Engine_result_type(~0) >> (_EDt - __w0_) :
3154 _Engine_result_type(0);
3155 __mask1_ = __w0_ < _EDt - 1 ?
3156 _Engine_result_type(~0) >> (_EDt - (__w0_ + 1)) :
3157 _Engine_result_type(~0);
3158}
3159
3160template<class _Engine, class _UIntType>
3161inline
3162_UIntType
3163__independent_bits_engine<_Engine, _UIntType>::__eval(false_type)
3164{
3165 return static_cast<result_type>(__e_() & __mask0_);
3166}
3167
3168template<class _Engine, class _UIntType>
3169_UIntType
3170__independent_bits_engine<_Engine, _UIntType>::__eval(true_type)
3171{
3172 result_type _S = 0;
3173 for (size_t __k = 0; __k < __n0_; ++__k)
3174 {
3175 _Engine_result_type __u;
3176 do
3177 {
3178 __u = __e_() - _Engine::min();
3179 } while (__u >= __y0_);
3180 if (__w0_ < _EDt)
3181 _S <<= __w0_;
3182 else
3183 _S = 0;
3184 _S += __u & __mask0_;
3185 }
3186 for (size_t __k = __n0_; __k < __n_; ++__k)
3187 {
3188 _Engine_result_type __u;
3189 do
3190 {
3191 __u = __e_() - _Engine::min();
3192 } while (__u >= __y1_);
3193 if (__w0_ < _EDt - 1)
3194 _S <<= __w0_ + 1;
3195 else
3196 _S = 0;
3197 _S += __u & __mask1_;
3198 }
3199 return _S;
3200}
3201
Howard Hinnant30a840f2010-05-12 17:08:57 +00003202// uniform_int_distribution
3203
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003204template<class _IntType = int>
3205class uniform_int_distribution
3206{
3207public:
3208 // types
3209 typedef _IntType result_type;
3210
3211 class param_type
3212 {
3213 result_type __a_;
3214 result_type __b_;
3215 public:
3216 typedef uniform_int_distribution distribution_type;
3217
3218 explicit param_type(result_type __a = 0,
3219 result_type __b = numeric_limits<result_type>::max())
3220 : __a_(__a), __b_(__b) {}
3221
3222 result_type a() const {return __a_;}
3223 result_type b() const {return __b_;}
3224
3225 friend bool operator==(const param_type& __x, const param_type& __y)
3226 {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
3227 friend bool operator!=(const param_type& __x, const param_type& __y)
3228 {return !(__x == __y);}
3229 };
3230
3231private:
3232 param_type __p_;
3233
3234public:
3235 // constructors and reset functions
3236 explicit uniform_int_distribution(result_type __a = 0,
3237 result_type __b = numeric_limits<result_type>::max())
3238 : __p_(param_type(__a, __b)) {}
3239 explicit uniform_int_distribution(const param_type& __p) : __p_(__p) {}
3240 void reset() {}
3241
3242 // generating functions
3243 template<class _URNG> result_type operator()(_URNG& __g)
3244 {return (*this)(__g, __p_);}
3245 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
3246
3247 // property functions
3248 result_type a() const {return __p_.a();}
3249 result_type b() const {return __p_.b();}
3250
3251 param_type param() const {return __p_;}
3252 void param(const param_type& __p) {__p_ = __p;}
3253
3254 result_type min() const {return a();}
3255 result_type max() const {return b();}
3256
3257 friend bool operator==(const uniform_int_distribution& __x,
3258 const uniform_int_distribution& __y)
3259 {return __x.__p_ == __y.__p_;}
3260 friend bool operator!=(const uniform_int_distribution& __x,
3261 const uniform_int_distribution& __y)
3262 {return !(__x == __y);}
3263};
3264
3265template<class _IntType>
3266template<class _URNG>
3267typename uniform_int_distribution<_IntType>::result_type
3268uniform_int_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p)
3269{
3270 typedef typename conditional<sizeof(result_type) <= sizeof(uint32_t),
3271 uint32_t, uint64_t>::type _UIntType;
3272 const _UIntType _R = __p.b() - __p.a() + _UIntType(1);
3273 if (_R == 1)
3274 return __p.a();
3275 const size_t _Dt = numeric_limits<_UIntType>::digits;
3276 typedef __independent_bits_engine<_URNG, _UIntType> _Eng;
3277 if (_R == 0)
3278 return static_cast<result_type>(_Eng(__g, _Dt)());
3279 size_t __w = _Dt - __clz(_R) - 1;
3280 if ((_R & (_UIntType(~0) >> (_Dt - __w))) != 0)
3281 ++__w;
3282 _Eng __e(__g, __w);
3283 _UIntType __u;
3284 do
3285 {
3286 __u = __e();
3287 } while (__u >= _R);
3288 return static_cast<result_type>(__u + __p.a());
3289}
3290
3291template <class _CharT, class _Traits, class _IT>
3292basic_ostream<_CharT, _Traits>&
3293operator<<(basic_ostream<_CharT, _Traits>& __os,
3294 const uniform_int_distribution<_IT>& __x)
3295{
3296 __save_flags<_CharT, _Traits> _(__os);
3297 __os.flags(ios_base::dec | ios_base::left);
3298 _CharT __sp = __os.widen(' ');
3299 __os.fill(__sp);
3300 return __os << __x.a() << __sp << __x.b();
3301}
3302
3303template <class _CharT, class _Traits, class _IT>
3304basic_istream<_CharT, _Traits>&
3305operator>>(basic_istream<_CharT, _Traits>& __is,
3306 uniform_int_distribution<_IT>& __x)
3307{
3308 typedef uniform_int_distribution<_IT> _Eng;
3309 typedef typename _Eng::result_type result_type;
3310 typedef typename _Eng::param_type param_type;
3311 __save_flags<_CharT, _Traits> _(__is);
3312 __is.flags(ios_base::dec | ios_base::skipws);
3313 result_type __a;
3314 result_type __b;
3315 __is >> __a >> __b;
3316 if (!__is.fail())
3317 __x.param(param_type(__a, __b));
3318 return __is;
3319}
3320
Howard Hinnant30a840f2010-05-12 17:08:57 +00003321// uniform_real_distribution
3322
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003323template<class _RealType = double>
3324class uniform_real_distribution
3325{
3326public:
3327 // types
3328 typedef _RealType result_type;
3329
3330 class param_type
3331 {
3332 result_type __a_;
3333 result_type __b_;
3334 public:
3335 typedef uniform_real_distribution distribution_type;
3336
3337 explicit param_type(result_type __a = 0,
3338 result_type __b = 1)
3339 : __a_(__a), __b_(__b) {}
3340
3341 result_type a() const {return __a_;}
3342 result_type b() const {return __b_;}
3343
3344 friend bool operator==(const param_type& __x, const param_type& __y)
3345 {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
3346 friend bool operator!=(const param_type& __x, const param_type& __y)
3347 {return !(__x == __y);}
3348 };
3349
3350private:
3351 param_type __p_;
3352
3353public:
3354 // constructors and reset functions
3355 explicit uniform_real_distribution(result_type __a = 0, result_type __b = 1)
3356 : __p_(param_type(__a, __b)) {}
3357 explicit uniform_real_distribution(const param_type& __p) : __p_(__p) {}
3358 void reset() {}
3359
3360 // generating functions
3361 template<class _URNG> result_type operator()(_URNG& __g)
3362 {return (*this)(__g, __p_);}
3363 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
3364
3365 // property functions
3366 result_type a() const {return __p_.a();}
3367 result_type b() const {return __p_.b();}
3368
3369 param_type param() const {return __p_;}
3370 void param(const param_type& __p) {__p_ = __p;}
3371
3372 result_type min() const {return a();}
3373 result_type max() const {return b();}
3374
3375 friend bool operator==(const uniform_real_distribution& __x,
3376 const uniform_real_distribution& __y)
3377 {return __x.__p_ == __y.__p_;}
3378 friend bool operator!=(const uniform_real_distribution& __x,
3379 const uniform_real_distribution& __y)
3380 {return !(__x == __y);}
3381};
3382
3383template<class _RealType>
3384template<class _URNG>
3385inline
3386typename uniform_real_distribution<_RealType>::result_type
3387uniform_real_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
3388{
3389 return (__p.b() - __p.a())
3390 * _STD::generate_canonical<_RealType, numeric_limits<_RealType>::digits>(__g)
3391 + __p.a();
3392}
3393
3394template <class _CharT, class _Traits, class _RT>
3395basic_ostream<_CharT, _Traits>&
3396operator<<(basic_ostream<_CharT, _Traits>& __os,
3397 const uniform_real_distribution<_RT>& __x)
3398{
3399 __save_flags<_CharT, _Traits> _(__os);
3400 __os.flags(ios_base::dec | ios_base::left);
3401 _CharT __sp = __os.widen(' ');
3402 __os.fill(__sp);
3403 return __os << __x.a() << __sp << __x.b();
3404}
3405
3406template <class _CharT, class _Traits, class _RT>
3407basic_istream<_CharT, _Traits>&
3408operator>>(basic_istream<_CharT, _Traits>& __is,
3409 uniform_real_distribution<_RT>& __x)
3410{
3411 typedef uniform_real_distribution<_RT> _Eng;
3412 typedef typename _Eng::result_type result_type;
3413 typedef typename _Eng::param_type param_type;
3414 __save_flags<_CharT, _Traits> _(__is);
3415 __is.flags(ios_base::dec | ios_base::skipws);
3416 result_type __a;
3417 result_type __b;
3418 __is >> __a >> __b;
3419 if (!__is.fail())
3420 __x.param(param_type(__a, __b));
3421 return __is;
3422}
3423
Howard Hinnant30a840f2010-05-12 17:08:57 +00003424// bernoulli_distribution
3425
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003426class bernoulli_distribution
3427{
3428public:
3429 // types
3430 typedef bool result_type;
3431
3432 class param_type
3433 {
3434 double __p_;
3435 public:
3436 typedef bernoulli_distribution distribution_type;
3437
3438 explicit param_type(double __p = 0.5) : __p_(__p) {}
3439
3440 double p() const {return __p_;}
3441
3442 friend bool operator==(const param_type& __x, const param_type& __y)
3443 {return __x.__p_ == __y.__p_;}
3444 friend bool operator!=(const param_type& __x, const param_type& __y)
3445 {return !(__x == __y);}
3446 };
3447
3448private:
3449 param_type __p_;
3450
3451public:
3452 // constructors and reset functions
3453 explicit bernoulli_distribution(double __p = 0.5)
3454 : __p_(param_type(__p)) {}
3455 explicit bernoulli_distribution(const param_type& __p) : __p_(__p) {}
3456 void reset() {}
3457
3458 // generating functions
3459 template<class _URNG> result_type operator()(_URNG& __g)
3460 {return (*this)(__g, __p_);}
Howard Hinnant03aad812010-05-11 23:26:59 +00003461 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003462
3463 // property functions
3464 double p() const {return __p_.p();}
3465
3466 param_type param() const {return __p_;}
3467 void param(const param_type& __p) {__p_ = __p;}
3468
3469 result_type min() const {return false;}
3470 result_type max() const {return true;}
3471
3472 friend bool operator==(const bernoulli_distribution& __x,
3473 const bernoulli_distribution& __y)
3474 {return __x.__p_ == __y.__p_;}
3475 friend bool operator!=(const bernoulli_distribution& __x,
3476 const bernoulli_distribution& __y)
3477 {return !(__x == __y);}
3478};
3479
Howard Hinnant03aad812010-05-11 23:26:59 +00003480template<class _URNG>
3481inline
3482bernoulli_distribution::result_type
3483bernoulli_distribution::operator()(_URNG& __g, const param_type& __p)
3484{
3485 return (__g() - __g.min()) < __p.p() * (__g.max() - __g.min() + 1.);
3486}
3487
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003488template <class _CharT, class _Traits>
3489basic_ostream<_CharT, _Traits>&
3490operator<<(basic_ostream<_CharT, _Traits>& __os, const bernoulli_distribution& __x)
3491{
3492 __save_flags<_CharT, _Traits> _(__os);
3493 __os.flags(ios_base::dec | ios_base::left);
3494 _CharT __sp = __os.widen(' ');
3495 __os.fill(__sp);
3496 return __os << __x.p();
3497}
3498
3499template <class _CharT, class _Traits>
3500basic_istream<_CharT, _Traits>&
3501operator>>(basic_istream<_CharT, _Traits>& __is, bernoulli_distribution& __x)
3502{
3503 typedef bernoulli_distribution _Eng;
3504 typedef typename _Eng::param_type param_type;
3505 __save_flags<_CharT, _Traits> _(__is);
3506 __is.flags(ios_base::dec | ios_base::skipws);
3507 double __p;
3508 __is >> __p;
3509 if (!__is.fail())
3510 __x.param(param_type(__p));
3511 return __is;
3512}
3513
Howard Hinnant30a840f2010-05-12 17:08:57 +00003514// binomial_distribution
3515
Howard Hinnant03aad812010-05-11 23:26:59 +00003516template<class _IntType = int>
3517class binomial_distribution
3518{
3519public:
3520 // types
3521 typedef _IntType result_type;
3522
3523 class param_type
3524 {
3525 result_type __t_;
3526 double __p_;
Howard Hinnant6add8dd2010-05-15 21:36:23 +00003527 double __pr_;
3528 double __odds_ratio_;
3529 result_type __r0_;
Howard Hinnant03aad812010-05-11 23:26:59 +00003530 public:
3531 typedef binomial_distribution distribution_type;
3532
Howard Hinnant6add8dd2010-05-15 21:36:23 +00003533 explicit param_type(result_type __t = 1, double __p = 0.5);
Howard Hinnant03aad812010-05-11 23:26:59 +00003534
3535 result_type t() const {return __t_;}
3536 double p() const {return __p_;}
3537
3538 friend bool operator==(const param_type& __x, const param_type& __y)
3539 {return __x.__t_ == __y.__t_ && __x.__p_ == __y.__p_;}
3540 friend bool operator!=(const param_type& __x, const param_type& __y)
3541 {return !(__x == __y);}
Howard Hinnant6add8dd2010-05-15 21:36:23 +00003542
3543 friend class binomial_distribution;
Howard Hinnant03aad812010-05-11 23:26:59 +00003544 };
3545
3546private:
3547 param_type __p_;
3548
3549public:
3550 // constructors and reset functions
3551 explicit binomial_distribution(result_type __t = 1, double __p = 0.5)
3552 : __p_(param_type(__t, __p)) {}
3553 explicit binomial_distribution(const param_type& __p) : __p_(__p) {}
3554 void reset() {}
3555
3556 // generating functions
3557 template<class _URNG> result_type operator()(_URNG& __g)
3558 {return (*this)(__g, __p_);}
3559 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
3560
3561 // property functions
3562 result_type t() const {return __p_.t();}
3563 double p() const {return __p_.p();}
3564
3565 param_type param() const {return __p_;}
3566 void param(const param_type& __p) {__p_ = __p;}
3567
3568 result_type min() const {return 0;}
3569 result_type max() const {return t();}
3570
3571 friend bool operator==(const binomial_distribution& __x,
3572 const binomial_distribution& __y)
3573 {return __x.__p_ == __y.__p_;}
3574 friend bool operator!=(const binomial_distribution& __x,
3575 const binomial_distribution& __y)
3576 {return !(__x == __y);}
3577};
3578
3579template<class _IntType>
Howard Hinnant6add8dd2010-05-15 21:36:23 +00003580binomial_distribution<_IntType>::param_type::param_type(result_type __t, double __p)
3581 : __t_(__t), __p_(__p)
3582{
3583 if (0 < __p_ && __p_ < 1)
3584 {
3585 __r0_ = static_cast<result_type>((__t_ + 1) * __p_);
3586 __pr_ = _STD::exp(_STD::lgamma(__t_ + 1.) - _STD::lgamma(__r0_ + 1.) -
3587 _STD::lgamma(__t_ - __r0_ + 1.) + __r0_ * _STD::log(__p_) +
3588 (__t_ - __r0_) * _STD::log(1 - __p_));
3589 __odds_ratio_ = __p_ / (1 - __p_);
3590 }
3591}
3592
3593template<class _IntType>
Howard Hinnant03aad812010-05-11 23:26:59 +00003594template<class _URNG>
3595_IntType
Howard Hinnant6add8dd2010-05-15 21:36:23 +00003596binomial_distribution<_IntType>::operator()(_URNG& __g, const param_type& __pr)
Howard Hinnant03aad812010-05-11 23:26:59 +00003597{
Howard Hinnant6add8dd2010-05-15 21:36:23 +00003598 if (__pr.__t_ == 0 || __pr.__p_ == 0)
3599 return 0;
3600 if (__pr.__p_ == 1)
3601 return __pr.__t_;
3602 uniform_real_distribution<double> __gen;
3603 double __u = __gen(__g) - __pr.__pr_;
3604 if (__u < 0)
3605 return __pr.__r0_;
3606 double __pu = __pr.__pr_;
3607 double __pd = __pu;
3608 result_type __ru = __pr.__r0_;
3609 result_type __rd = __ru;
3610 while (true)
3611 {
3612 if (__rd >= 1)
3613 {
3614 __pd *= __rd / (__pr.__odds_ratio_ * (__pr.__t_ - __rd + 1));
3615 __u -= __pd;
3616 if (__u < 0)
3617 return __rd - 1;
3618 }
3619 --__rd;
3620 ++__ru;
3621 if (__ru <= __pr.__t_)
3622 {
3623 __pu *= (__pr.__t_ - __ru + 1) * __pr.__odds_ratio_ / __ru;
3624 __u -= __pu;
3625 if (__u < 0)
3626 return __ru;
3627 }
3628 }
Howard Hinnant03aad812010-05-11 23:26:59 +00003629}
3630
3631template <class _CharT, class _Traits, class _IntType>
3632basic_ostream<_CharT, _Traits>&
3633operator<<(basic_ostream<_CharT, _Traits>& __os,
3634 const binomial_distribution<_IntType>& __x)
3635{
3636 __save_flags<_CharT, _Traits> _(__os);
3637 __os.flags(ios_base::dec | ios_base::left);
3638 _CharT __sp = __os.widen(' ');
3639 __os.fill(__sp);
3640 return __os << __x.t() << __sp << __x.p();
3641}
3642
3643template <class _CharT, class _Traits, class _IntType>
3644basic_istream<_CharT, _Traits>&
3645operator>>(basic_istream<_CharT, _Traits>& __is,
3646 binomial_distribution<_IntType>& __x)
3647{
3648 typedef binomial_distribution<_IntType> _Eng;
3649 typedef typename _Eng::result_type result_type;
3650 typedef typename _Eng::param_type param_type;
3651 __save_flags<_CharT, _Traits> _(__is);
3652 __is.flags(ios_base::dec | ios_base::skipws);
3653 result_type __t;
3654 double __p;
3655 __is >> __t >> __p;
3656 if (!__is.fail())
3657 __x.param(param_type(__t, __p));
3658 return __is;
3659}
3660
Howard Hinnant30a840f2010-05-12 17:08:57 +00003661// exponential_distribution
3662
3663template<class _RealType = double>
3664class exponential_distribution
3665{
3666public:
3667 // types
3668 typedef _RealType result_type;
3669
3670 class param_type
3671 {
3672 result_type __lambda_;
3673 public:
3674 typedef exponential_distribution distribution_type;
3675
3676 explicit param_type(result_type __lambda = 1) : __lambda_(__lambda) {}
3677
3678 result_type lambda() const {return __lambda_;}
3679
3680 friend bool operator==(const param_type& __x, const param_type& __y)
3681 {return __x.__lambda_ == __y.__lambda_;}
3682 friend bool operator!=(const param_type& __x, const param_type& __y)
3683 {return !(__x == __y);}
3684 };
3685
3686private:
3687 param_type __p_;
3688
3689public:
3690 // constructors and reset functions
3691 explicit exponential_distribution(result_type __lambda = 1)
3692 : __p_(param_type(__lambda)) {}
3693 explicit exponential_distribution(const param_type& __p) : __p_(__p) {}
3694 void reset() {}
3695
3696 // generating functions
3697 template<class _URNG> result_type operator()(_URNG& __g)
3698 {return (*this)(__g, __p_);}
3699 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
3700
3701 // property functions
3702 result_type lambda() const {return __p_.lambda();}
3703
3704 param_type param() const {return __p_;}
3705 void param(const param_type& __p) {__p_ = __p;}
3706
3707 result_type min() const {return 0;}
Howard Hinnantdf40dc62010-05-16 17:56:20 +00003708 result_type max() const {return numeric_limits<result_type>::infinity();}
Howard Hinnant30a840f2010-05-12 17:08:57 +00003709
3710 friend bool operator==(const exponential_distribution& __x,
3711 const exponential_distribution& __y)
3712 {return __x.__p_ == __y.__p_;}
3713 friend bool operator!=(const exponential_distribution& __x,
3714 const exponential_distribution& __y)
3715 {return !(__x == __y);}
3716};
3717
3718template <class _RealType>
3719template<class _URNG>
3720_RealType
3721exponential_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
3722{
3723 return -_STD::log
3724 (
3725 result_type(1) -
3726 _STD::generate_canonical<result_type,
3727 numeric_limits<result_type>::digits>(__g)
3728 )
3729 / __p.lambda();
3730}
3731
3732template <class _CharT, class _Traits, class _RealType>
3733basic_ostream<_CharT, _Traits>&
3734operator<<(basic_ostream<_CharT, _Traits>& __os,
3735 const exponential_distribution<_RealType>& __x)
3736{
3737 __save_flags<_CharT, _Traits> _(__os);
3738 __os.flags(ios_base::dec | ios_base::left);
3739 return __os << __x.lambda();
3740}
3741
3742template <class _CharT, class _Traits, class _RealType>
3743basic_istream<_CharT, _Traits>&
3744operator>>(basic_istream<_CharT, _Traits>& __is,
3745 exponential_distribution<_RealType>& __x)
3746{
3747 typedef exponential_distribution<_RealType> _Eng;
3748 typedef typename _Eng::result_type result_type;
3749 typedef typename _Eng::param_type param_type;
3750 __save_flags<_CharT, _Traits> _(__is);
3751 __is.flags(ios_base::dec | ios_base::skipws);
3752 result_type __lambda;
3753 __is >> __lambda;
3754 if (!__is.fail())
3755 __x.param(param_type(__lambda));
3756 return __is;
3757}
3758
Howard Hinnant6add8dd2010-05-15 21:36:23 +00003759// normal_distribution
3760
3761template<class _RealType = double>
3762class normal_distribution
3763{
3764public:
3765 // types
3766 typedef _RealType result_type;
3767
3768 class param_type
3769 {
3770 result_type __mean_;
3771 result_type __stddev_;
3772 public:
3773 typedef normal_distribution distribution_type;
3774
3775 explicit param_type(result_type __mean = 0, result_type __stddev = 1)
3776 : __mean_(__mean), __stddev_(__stddev) {}
3777
3778 result_type mean() const {return __mean_;}
3779 result_type stddev() const {return __stddev_;}
3780
3781 friend bool operator==(const param_type& __x, const param_type& __y)
3782 {return __x.__mean_ == __y.__mean_ && __x.__stddev_ == __y.__stddev_;}
3783 friend bool operator!=(const param_type& __x, const param_type& __y)
3784 {return !(__x == __y);}
3785 };
3786
3787private:
3788 param_type __p_;
3789 result_type _V_;
3790 bool _V_hot_;
3791
3792public:
3793 // constructors and reset functions
3794 explicit normal_distribution(result_type __mean = 0, result_type __stddev = 1)
3795 : __p_(param_type(__mean, __stddev)), _V_hot_(false) {}
3796 explicit normal_distribution(const param_type& __p)
3797 : __p_(__p), _V_hot_(false) {}
3798 void reset() {_V_hot_ = false;}
3799
3800 // generating functions
3801 template<class _URNG> result_type operator()(_URNG& __g)
3802 {return (*this)(__g, __p_);}
3803 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
3804
3805 // property functions
3806 result_type mean() const {return __p_.mean();}
3807 result_type stddev() const {return __p_.stddev();}
3808
3809 param_type param() const {return __p_;}
3810 void param(const param_type& __p) {__p_ = __p;}
3811
3812 result_type min() const {return -numeric_limits<result_type>::infinity();}
3813 result_type max() const {return numeric_limits<result_type>::infinity();}
3814
3815 friend bool operator==(const normal_distribution& __x,
3816 const normal_distribution& __y)
3817 {return __x.__p_ == __y.__p_ && __x._V_hot_ == __y._V_hot_ &&
3818 (!__x._V_hot_ || __x._V_ == __y._V_);}
3819 friend bool operator!=(const normal_distribution& __x,
3820 const normal_distribution& __y)
3821 {return !(__x == __y);}
3822
3823 template <class _CharT, class _Traits, class _RT>
3824 friend
3825 basic_ostream<_CharT, _Traits>&
3826 operator<<(basic_ostream<_CharT, _Traits>& __os,
3827 const normal_distribution<_RT>& __x);
3828
3829 template <class _CharT, class _Traits, class _RT>
3830 friend
3831 basic_istream<_CharT, _Traits>&
3832 operator>>(basic_istream<_CharT, _Traits>& __is,
3833 normal_distribution<_RT>& __x);
3834};
3835
3836template <class _RealType>
3837template<class _URNG>
3838_RealType
3839normal_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
3840{
3841 result_type _U;
3842 if (_V_hot_)
3843 {
3844 _V_hot_ = false;
3845 _U = _V_;
3846 }
3847 else
3848 {
3849 uniform_real_distribution<result_type> _Uni(-1, 1);
3850 result_type __u;
3851 result_type __v;
3852 result_type __s;
3853 do
3854 {
3855 __u = _Uni(__g);
3856 __v = _Uni(__g);
3857 __s = __u * __u + __v * __v;
3858 } while (__s > 1 || __s == 0);
3859 result_type _F = _STD::sqrt(-2 * _STD::log(__s) / __s);
3860 _V_ = __v * _F;
3861 _V_hot_ = true;
3862 _U = __u * _F;
3863 }
3864 return _U * __p.stddev() + __p.mean();
3865}
3866
3867template <class _CharT, class _Traits, class _RT>
3868basic_ostream<_CharT, _Traits>&
3869operator<<(basic_ostream<_CharT, _Traits>& __os,
3870 const normal_distribution<_RT>& __x)
3871{
3872 __save_flags<_CharT, _Traits> _(__os);
3873 __os.flags(ios_base::dec | ios_base::left);
3874 _CharT __sp = __os.widen(' ');
3875 __os.fill(__sp);
3876 __os << __x.mean() << __sp << __x.stddev() << __sp << __x._V_hot_;
3877 if (__x._V_hot_)
3878 __os << __sp << __x._V_;
3879 return __os;
3880}
3881
3882template <class _CharT, class _Traits, class _RT>
3883basic_istream<_CharT, _Traits>&
3884operator>>(basic_istream<_CharT, _Traits>& __is,
3885 normal_distribution<_RT>& __x)
3886{
3887 typedef normal_distribution<_RT> _Eng;
3888 typedef typename _Eng::result_type result_type;
3889 typedef typename _Eng::param_type param_type;
3890 __save_flags<_CharT, _Traits> _(__is);
3891 __is.flags(ios_base::dec | ios_base::skipws);
3892 result_type __mean;
3893 result_type __stddev;
3894 result_type _V = 0;
3895 bool _V_hot = false;
3896 __is >> __mean >> __stddev >> _V_hot;
3897 if (_V_hot)
3898 __is >> _V;
3899 if (!__is.fail())
3900 {
3901 __x.param(param_type(__mean, __stddev));
3902 __x._V_hot_ = _V_hot;
3903 __x._V_ = _V;
3904 }
3905 return __is;
3906}
3907
Howard Hinnant2bc36fc2010-05-17 18:31:53 +00003908// lognormal_distribution
3909
3910template<class _RealType = double>
3911class lognormal_distribution
3912{
3913public:
3914 // types
3915 typedef _RealType result_type;
3916
3917 class param_type
3918 {
3919 normal_distribution<result_type> __nd_;
3920 public:
3921 typedef lognormal_distribution distribution_type;
3922
3923 explicit param_type(result_type __m = 0, result_type __s = 1)
3924 : __nd_(__m, __s) {}
3925
3926 result_type m() const {return __nd_.mean();}
3927 result_type s() const {return __nd_.stddev();}
3928
3929 friend bool operator==(const param_type& __x, const param_type& __y)
3930 {return __x.__nd_ == __y.__nd_;}
3931 friend bool operator!=(const param_type& __x, const param_type& __y)
3932 {return !(__x == __y);}
3933 friend class lognormal_distribution;
3934
3935 template <class _CharT, class _Traits, class _RT>
3936 friend
3937 basic_ostream<_CharT, _Traits>&
3938 operator<<(basic_ostream<_CharT, _Traits>& __os,
3939 const lognormal_distribution<_RT>& __x);
3940
3941 template <class _CharT, class _Traits, class _RT>
3942 friend
3943 basic_istream<_CharT, _Traits>&
3944 operator>>(basic_istream<_CharT, _Traits>& __is,
3945 lognormal_distribution<_RT>& __x);
3946 };
3947
3948private:
3949 param_type __p_;
3950
3951public:
3952 // constructor and reset functions
3953 explicit lognormal_distribution(result_type __m = 0, result_type __s = 1)
3954 : __p_(param_type(__m, __s)) {}
3955 explicit lognormal_distribution(const param_type& __p)
3956 : __p_(__p) {}
3957 void reset() {__p_.__nd_.reset();}
3958
3959 // generating functions
3960 template<class _URNG> result_type operator()(_URNG& __g)
3961 {return (*this)(__g, __p_);}
3962 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p)
3963 {return _STD::exp(const_cast<normal_distribution<result_type>&>(__p.__nd_)(__g));}
3964
3965 // property functions
3966 result_type m() const {return __p_.m();}
3967 result_type s() const {return __p_.s();}
3968
3969 param_type param() const {return __p_;}
3970 void param(const param_type& __p) {return __p_ = __p;}
3971
3972 result_type min() const {return 0;}
3973 result_type max() const {return numeric_limits<result_type>::infinity();}
3974
3975 friend bool operator==(const lognormal_distribution& __x,
3976 const lognormal_distribution& __y)
3977 {return __x.__p_ == __y.__p_;}
3978 friend bool operator!=(const lognormal_distribution& __x,
3979 const lognormal_distribution& __y)
3980 {return !(__x == __y);}
3981
3982 template <class _CharT, class _Traits, class _RT>
3983 friend
3984 basic_ostream<_CharT, _Traits>&
3985 operator<<(basic_ostream<_CharT, _Traits>& __os,
3986 const lognormal_distribution<_RT>& __x);
3987
3988 template <class _CharT, class _Traits, class _RT>
3989 friend
3990 basic_istream<_CharT, _Traits>&
3991 operator>>(basic_istream<_CharT, _Traits>& __is,
3992 lognormal_distribution<_RT>& __x);
3993};
3994
3995template <class _CharT, class _Traits, class _RT>
3996inline
3997basic_ostream<_CharT, _Traits>&
3998operator<<(basic_ostream<_CharT, _Traits>& __os,
3999 const lognormal_distribution<_RT>& __x)
4000{
4001 return __os << __x.__p_.__nd_;
4002}
4003
4004template <class _CharT, class _Traits, class _RT>
4005inline
4006basic_istream<_CharT, _Traits>&
4007operator>>(basic_istream<_CharT, _Traits>& __is,
4008 lognormal_distribution<_RT>& __x)
4009{
4010 return __is >> __x.__p_.__nd_;
4011}
4012
Howard Hinnant6add8dd2010-05-15 21:36:23 +00004013// poisson_distribution
4014
4015template<class _IntType = int>
4016class poisson_distribution
4017{
4018public:
4019 // types
4020 typedef _IntType result_type;
4021
4022 class param_type
4023 {
4024 double __mean_;
4025 double __s_;
4026 double __d_;
4027 double __l_;
4028 double __omega_;
4029 double __c0_;
4030 double __c1_;
4031 double __c2_;
4032 double __c3_;
4033 double __c_;
4034
4035 public:
4036 typedef poisson_distribution distribution_type;
4037
4038 explicit param_type(double __mean = 1.0);
4039
4040 double mean() const {return __mean_;}
4041
4042 friend bool operator==(const param_type& __x, const param_type& __y)
4043 {return __x.__mean_ == __y.__mean_;}
4044 friend bool operator!=(const param_type& __x, const param_type& __y)
4045 {return !(__x == __y);}
4046
4047 friend class poisson_distribution;
4048 };
4049
4050private:
4051 param_type __p_;
4052
4053public:
4054 // constructors and reset functions
4055 explicit poisson_distribution(double __mean = 1.0) : __p_(__mean) {}
4056 explicit poisson_distribution(const param_type& __p) : __p_(__p) {}
4057 void reset() {}
4058
4059 // generating functions
4060 template<class _URNG> result_type operator()(_URNG& __g)
4061 {return (*this)(__g, __p_);}
4062 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
4063
4064 // property functions
4065 double mean() const {return __p_.mean();}
4066
4067 param_type param() const {return __p_;}
4068 void param(const param_type& __p) {__p_ = __p;}
4069
4070 result_type min() const {return 0;}
4071 result_type max() const {return numeric_limits<result_type>::max();}
4072
4073 friend bool operator==(const poisson_distribution& __x,
4074 const poisson_distribution& __y)
4075 {return __x.__p_ == __y.__p_;}
4076 friend bool operator!=(const poisson_distribution& __x,
4077 const poisson_distribution& __y)
4078 {return !(__x == __y);}
4079};
4080
4081template<class _IntType>
4082poisson_distribution<_IntType>::param_type::param_type(double __mean)
4083 : __mean_(__mean)
4084{
4085 if (__mean_ < 10)
4086 {
4087 __s_ = 0;
4088 __d_ = 0;
4089 __l_ = _STD::exp(-__mean_);
4090 __omega_ = 0;
4091 __c3_ = 0;
4092 __c2_ = 0;
4093 __c1_ = 0;
4094 __c0_ = 0;
4095 __c_ = 0;
4096 }
4097 else
4098 {
4099 __s_ = _STD::sqrt(__mean_);
4100 __d_ = 6 * __mean_ * __mean_;
4101 __l_ = static_cast<result_type>(__mean_ - 1.1484);
4102 __omega_ = .3989423 / __s_;
4103 double __b1_ = .4166667E-1 / __mean_;
4104 double __b2_ = .3 * __b1_ * __b1_;
4105 __c3_ = .1428571 * __b1_ * __b2_;
4106 __c2_ = __b2_ - 15. * __c3_;
4107 __c1_ = __b1_ - 6. * __b2_ + 45. * __c3_;
4108 __c0_ = 1. - __b1_ + 3. * __b2_ - 15. * __c3_;
4109 __c_ = .1069 / __mean_;
4110 }
4111}
4112
4113template <class _IntType>
4114template<class _URNG>
4115_IntType
4116poisson_distribution<_IntType>::operator()(_URNG& __urng, const param_type& __pr)
4117{
4118 result_type __x;
4119 uniform_real_distribution<double> __urd;
4120 if (__pr.__mean_ <= 10)
4121 {
4122 __x = 0;
4123 for (double __p = __urd(__urng); __p > __pr.__l_; ++__x)
4124 __p *= __urd(__urng);
4125 }
4126 else
4127 {
4128 double __difmuk;
4129 double __g = __pr.__mean_ + __pr.__s_ * normal_distribution<double>()(__urng);
4130 double __u;
4131 if (__g > 0)
4132 {
4133 __x = static_cast<result_type>(__g);
4134 if (__x >= __pr.__l_)
4135 return __x;
4136 __difmuk = __pr.__mean_ - __x;
4137 __u = __urd(__urng);
4138 if (__pr.__d_ * __u >= __difmuk * __difmuk * __difmuk)
4139 return __x;
4140 }
4141 exponential_distribution<double> __edist;
4142 for (bool __using_exp_dist = false; true; __using_exp_dist = true)
4143 {
4144 double __e;
4145 if (__using_exp_dist || __g < 0)
4146 {
4147 double __t;
4148 do
4149 {
4150 __e = __edist(__urng);
4151 __u = __urd(__urng);
4152 __u += __u - 1;
4153 __t = 1.8 + (__u < 0 ? -__e : __e);
4154 } while (__t <= -.6744);
4155 __x = __pr.__mean_ + __pr.__s_ * __t;
4156 __difmuk = __pr.__mean_ - __x;
4157 __using_exp_dist = true;
4158 }
4159 double __px;
4160 double __py;
4161 if (__x < 10)
4162 {
4163 const result_type __fac[] = {1, 1, 2, 6, 24, 120, 720, 5040,
4164 40320, 362880};
4165 __px = -__pr.__mean_;
4166 __py = _STD::pow(__pr.__mean_, (double)__x) / __fac[__x];
4167 }
4168 else
4169 {
4170 double __del = .8333333E-1 / __x;
4171 __del -= 4.8 * __del * __del * __del;
4172 double __v = __difmuk / __x;
4173 if (_STD::abs(__v) > 0.25)
4174 __px = __x * _STD::log(1 + __v) - __difmuk - __del;
4175 else
4176 __px = __x * __v * __v * (((((((.1250060 * __v + -.1384794) *
4177 __v + .1421878) * __v + -.1661269) * __v + .2000118) *
4178 __v + -.2500068) * __v + .3333333) * __v + -.5) - __del;
4179 __py = .3989423 / _STD::sqrt(__x);
4180 }
4181 double __r = (0.5 - __difmuk) / __pr.__s_;
4182 double __r2 = __r * __r;
4183 double __fx = -0.5 * __r2;
4184 double __fy = __pr.__omega_ * (((__pr.__c3_ * __r2 + __pr.__c2_) *
4185 __r2 + __pr.__c1_) * __r2 + __pr.__c0_);
4186 if (__using_exp_dist)
4187 {
4188 if (__pr.__c_ * _STD::abs(__u) <= __py * _STD::exp(__px + __e) -
4189 __fy * _STD::exp(__fx + __e))
4190 break;
4191 }
4192 else
4193 {
4194 if (__fy - __u * __fy <= __py * _STD::exp(__px - __fx))
4195 break;
4196 }
4197 }
4198 }
4199 return __x;
4200}
4201
4202template <class _CharT, class _Traits, class _IntType>
4203basic_ostream<_CharT, _Traits>&
4204operator<<(basic_ostream<_CharT, _Traits>& __os,
4205 const poisson_distribution<_IntType>& __x)
4206{
4207 __save_flags<_CharT, _Traits> _(__os);
4208 __os.flags(ios_base::dec | ios_base::left);
4209 return __os << __x.mean();
4210}
4211
4212template <class _CharT, class _Traits, class _IntType>
4213basic_istream<_CharT, _Traits>&
4214operator>>(basic_istream<_CharT, _Traits>& __is,
4215 poisson_distribution<_IntType>& __x)
4216{
4217 typedef poisson_distribution<_IntType> _Eng;
4218 typedef typename _Eng::param_type param_type;
4219 __save_flags<_CharT, _Traits> _(__is);
4220 __is.flags(ios_base::dec | ios_base::skipws);
4221 double __mean;
4222 __is >> __mean;
4223 if (!__is.fail())
4224 __x.param(param_type(__mean));
4225 return __is;
4226}
4227
Howard Hinnant9de6e302010-05-16 01:09:02 +00004228// weibull_distribution
4229
4230template<class _RealType = double>
4231class weibull_distribution
4232{
4233public:
4234 // types
4235 typedef _RealType result_type;
4236
4237 class param_type
4238 {
4239 result_type __a_;
4240 result_type __b_;
4241 public:
4242 typedef weibull_distribution distribution_type;
4243
4244 explicit param_type(result_type __a = 1, result_type __b = 1)
4245 : __a_(__a), __b_(__b) {}
4246
4247 result_type a() const {return __a_;}
4248 result_type b() const {return __b_;}
4249
4250 friend bool operator==(const param_type& __x, const param_type& __y)
4251 {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
4252 friend bool operator!=(const param_type& __x, const param_type& __y)
4253 {return !(__x == __y);}
4254 };
4255
4256private:
4257 param_type __p_;
4258
4259public:
4260 // constructor and reset functions
4261 explicit weibull_distribution(result_type __a = 1, result_type __b = 1)
4262 : __p_(param_type(__a, __b)) {}
4263 explicit weibull_distribution(const param_type& __p)
4264 : __p_(__p) {}
4265 void reset() {}
4266
4267 // generating functions
4268 template<class _URNG> result_type operator()(_URNG& __g)
4269 {return (*this)(__g, __p_);}
4270 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p)
4271 {return __p.b() *
4272 _STD::pow(exponential_distribution<result_type>()(__g), 1/__p.a());}
4273
4274 // property functions
4275 result_type a() const {return __p_.a();}
4276 result_type b() const {return __p_.b();}
4277
4278 param_type param() const {return __p_;}
4279 void param(const param_type& __p) {__p_ = __p;}
4280
4281 result_type min() const {return 0;}
4282 result_type max() const {return numeric_limits<result_type>::infinity();}
4283
4284
4285 friend bool operator==(const weibull_distribution& __x,
4286 const weibull_distribution& __y)
4287 {return __x.__p_ == __y.__p_;}
4288 friend bool operator!=(const weibull_distribution& __x,
4289 const weibull_distribution& __y)
4290 {return !(__x == __y);}
4291};
4292
4293template <class _CharT, class _Traits, class _RT>
4294basic_ostream<_CharT, _Traits>&
4295operator<<(basic_ostream<_CharT, _Traits>& __os,
4296 const weibull_distribution<_RT>& __x)
4297{
4298 __save_flags<_CharT, _Traits> _(__os);
4299 __os.flags(ios_base::dec | ios_base::left);
4300 _CharT __sp = __os.widen(' ');
4301 __os.fill(__sp);
4302 __os << __x.a() << __sp << __x.b();
4303 return __os;
4304}
4305
4306template <class _CharT, class _Traits, class _RT>
4307basic_istream<_CharT, _Traits>&
4308operator>>(basic_istream<_CharT, _Traits>& __is,
4309 weibull_distribution<_RT>& __x)
4310{
4311 typedef weibull_distribution<_RT> _Eng;
4312 typedef typename _Eng::result_type result_type;
4313 typedef typename _Eng::param_type param_type;
4314 __save_flags<_CharT, _Traits> _(__is);
4315 __is.flags(ios_base::dec | ios_base::skipws);
4316 result_type __a;
4317 result_type __b;
4318 __is >> __a >> __b;
4319 if (!__is.fail())
4320 __x.param(param_type(__a, __b));
4321 return __is;
4322}
4323
Howard Hinnantc2b0dc72010-05-17 16:21:56 +00004324template<class _RealType = double>
4325class extreme_value_distribution
4326{
4327public:
4328 // types
4329 typedef _RealType result_type;
4330
4331 class param_type
4332 {
4333 result_type __a_;
4334 result_type __b_;
4335 public:
4336 typedef extreme_value_distribution distribution_type;
4337
4338 explicit param_type(result_type __a = 0, result_type __b = 1)
4339 : __a_(__a), __b_(__b) {}
4340
4341 result_type a() const {return __a_;}
4342 result_type b() const {return __b_;}
4343
4344 friend bool operator==(const param_type& __x, const param_type& __y)
4345 {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
4346 friend bool operator!=(const param_type& __x, const param_type& __y)
4347 {return !(__x == __y);}
4348 };
4349
4350private:
4351 param_type __p_;
4352
4353public:
4354 // constructor and reset functions
4355 explicit extreme_value_distribution(result_type __a = 0, result_type __b = 1)
4356 : __p_(param_type(__a, __b)) {}
4357 explicit extreme_value_distribution(const param_type& __p)
4358 : __p_(__p) {}
4359 void reset() {}
4360
4361 // generating functions
4362 template<class _URNG> result_type operator()(_URNG& __g)
4363 {return (*this)(__g, __p_);}
4364 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
4365
4366 // property functions
4367 result_type a() const {return __p_.a();}
4368 result_type b() const {return __p_.b();}
4369
4370 param_type param() const {return __p_;}
4371 void param(const param_type& __p) {__p_ = __p;}
4372
4373 result_type min() const {return -numeric_limits<result_type>::infinity();}
4374 result_type max() const {return numeric_limits<result_type>::infinity();}
4375
4376 friend bool operator==(const extreme_value_distribution& __x,
4377 const extreme_value_distribution& __y)
4378 {return __x.__p_ == __y.__p_;}
4379 friend bool operator!=(const extreme_value_distribution& __x,
4380 const extreme_value_distribution& __y)
4381 {return !(__x == __y);}
4382};
4383
4384template<class _RealType>
4385template<class _URNG>
4386_RealType
4387extreme_value_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
4388{
4389 return __p.a() - __p.b() *
4390 _STD::log(-_STD::log(1-uniform_real_distribution<result_type>()(__g)));
4391}
4392
4393template <class _CharT, class _Traits, class _RT>
4394basic_ostream<_CharT, _Traits>&
4395operator<<(basic_ostream<_CharT, _Traits>& __os,
4396 const extreme_value_distribution<_RT>& __x)
4397{
4398 __save_flags<_CharT, _Traits> _(__os);
4399 __os.flags(ios_base::dec | ios_base::left);
4400 _CharT __sp = __os.widen(' ');
4401 __os.fill(__sp);
4402 __os << __x.a() << __sp << __x.b();
4403 return __os;
4404}
4405
4406template <class _CharT, class _Traits, class _RT>
4407basic_istream<_CharT, _Traits>&
4408operator>>(basic_istream<_CharT, _Traits>& __is,
4409 extreme_value_distribution<_RT>& __x)
4410{
4411 typedef extreme_value_distribution<_RT> _Eng;
4412 typedef typename _Eng::result_type result_type;
4413 typedef typename _Eng::param_type param_type;
4414 __save_flags<_CharT, _Traits> _(__is);
4415 __is.flags(ios_base::dec | ios_base::skipws);
4416 result_type __a;
4417 result_type __b;
4418 __is >> __a >> __b;
4419 if (!__is.fail())
4420 __x.param(param_type(__a, __b));
4421 return __is;
4422}
4423
Howard Hinnantc7c49132010-05-13 17:58:28 +00004424// gamma_distribution
4425
4426template<class _RealType = double>
4427class gamma_distribution
4428{
4429public:
4430 // types
4431 typedef _RealType result_type;
4432
4433 class param_type
4434 {
4435 result_type __alpha_;
4436 result_type __beta_;
4437 public:
4438 typedef gamma_distribution distribution_type;
4439
4440 explicit param_type(result_type __alpha = 1, result_type __beta = 1)
4441 : __alpha_(__alpha), __beta_(__beta) {}
4442
4443 result_type alpha() const {return __alpha_;}
4444 result_type beta() const {return __beta_;}
4445
4446 friend bool operator==(const param_type& __x, const param_type& __y)
4447 {return __x.__alpha_ == __y.__alpha_ && __x.__beta_ == __y.__beta_;}
4448 friend bool operator!=(const param_type& __x, const param_type& __y)
4449 {return !(__x == __y);}
4450 };
4451
4452private:
4453 param_type __p_;
4454
4455public:
4456 // constructors and reset functions
4457 explicit gamma_distribution(result_type __alpha = 1, result_type __beta = 1)
4458 : __p_(param_type(__alpha, __beta)) {}
4459 explicit gamma_distribution(const param_type& __p)
4460 : __p_(__p) {}
4461 void reset() {}
4462
4463 // generating functions
4464 template<class _URNG> result_type operator()(_URNG& __g)
4465 {return (*this)(__g, __p_);}
4466 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
4467
4468 // property functions
4469 result_type alpha() const {return __p_.alpha();}
4470 result_type beta() const {return __p_.beta();}
4471
4472 param_type param() const {return __p_;}
4473 void param(const param_type& __p) {__p_ = __p;}
4474
4475 result_type min() const {return 0;}
4476 result_type max() const {return numeric_limits<result_type>::infinity();}
4477
4478 friend bool operator==(const gamma_distribution& __x,
4479 const gamma_distribution& __y)
4480 {return __x.__p_ == __y.__p_;}
4481 friend bool operator!=(const gamma_distribution& __x,
4482 const gamma_distribution& __y)
4483 {return !(__x == __y);}
4484};
4485
4486template <class _RealType>
4487template<class _URNG>
4488_RealType
4489gamma_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
4490{
Howard Hinnantf417abe2010-05-14 18:43:10 +00004491 result_type __a = __p.alpha();
4492 uniform_real_distribution<result_type> __gen(0, 1);
4493 exponential_distribution<result_type> __egen;
4494 result_type __x;
Howard Hinnantc7c49132010-05-13 17:58:28 +00004495 if (__a == 1)
Howard Hinnantf417abe2010-05-14 18:43:10 +00004496 __x = __egen(__g);
Howard Hinnantc7c49132010-05-13 17:58:28 +00004497 else if (__a > 1)
4498 {
4499 const result_type __b = __a - 1;
4500 const result_type __c = 3 * __a - result_type(0.75);
Howard Hinnantc7c49132010-05-13 17:58:28 +00004501 while (true)
4502 {
4503 const result_type __u = __gen(__g);
4504 const result_type __v = __gen(__g);
4505 const result_type __w = __u * (1 - __u);
Howard Hinnantf417abe2010-05-14 18:43:10 +00004506 if (__w != 0)
Howard Hinnantc7c49132010-05-13 17:58:28 +00004507 {
4508 const result_type __y = _STD::sqrt(__c / __w) *
4509 (__u - result_type(0.5));
4510 __x = __b + __y;
4511 if (__x >= 0)
4512 {
4513 const result_type __z = 64 * __w * __w * __w * __v * __v;
4514 if (__z <= 1 - 2 * __y * __y / __x)
4515 break;
4516 if (_STD::log(__z) <= 2 * (__b * _STD::log(__x / __b) - __y))
4517 break;
4518 }
4519 }
4520 }
Howard Hinnantc7c49132010-05-13 17:58:28 +00004521 }
Howard Hinnantf417abe2010-05-14 18:43:10 +00004522 else // __a < 1
4523 {
4524 while (true)
4525 {
4526 const result_type __u = __gen(__g);
4527 const result_type __es = __egen(__g);
4528 if (__u <= 1 - __a)
4529 {
4530 __x = _STD::pow(__u, 1 / __a);
4531 if (__x <= __es)
4532 break;
4533 }
4534 else
4535 {
4536 const result_type __e = -_STD::log((1-__u)/__a);
4537 __x = _STD::pow(1 - __a + __a * __e, 1 / __a);
4538 if (__x <= __e + __es)
4539 break;
4540 }
4541 }
4542 }
4543 return __x * __p.beta();
Howard Hinnantc7c49132010-05-13 17:58:28 +00004544}
4545
4546template <class _CharT, class _Traits, class _RT>
4547basic_ostream<_CharT, _Traits>&
4548operator<<(basic_ostream<_CharT, _Traits>& __os,
4549 const gamma_distribution<_RT>& __x)
4550{
4551 __save_flags<_CharT, _Traits> _(__os);
4552 __os.flags(ios_base::dec | ios_base::left);
4553 _CharT __sp = __os.widen(' ');
4554 __os.fill(__sp);
4555 __os << __x.alpha() << __sp << __x.beta();
4556 return __os;
4557}
4558
4559template <class _CharT, class _Traits, class _RT>
4560basic_istream<_CharT, _Traits>&
4561operator>>(basic_istream<_CharT, _Traits>& __is,
4562 gamma_distribution<_RT>& __x)
4563{
4564 typedef gamma_distribution<_RT> _Eng;
4565 typedef typename _Eng::result_type result_type;
4566 typedef typename _Eng::param_type param_type;
4567 __save_flags<_CharT, _Traits> _(__is);
4568 __is.flags(ios_base::dec | ios_base::skipws);
4569 result_type __alpha;
4570 result_type __beta;
4571 __is >> __alpha >> __beta;
4572 if (!__is.fail())
4573 __x.param(param_type(__alpha, __beta));
4574 return __is;
4575}
Howard Hinnanta64111c2010-05-12 21:02:31 +00004576
Howard Hinnantf2fe5d52010-05-17 00:09:38 +00004577// negative_binomial_distribution
4578
4579template<class _IntType = int>
4580class negative_binomial_distribution
4581{
4582public:
4583 // types
4584 typedef _IntType result_type;
4585
4586 class param_type
4587 {
4588 result_type __k_;
4589 double __p_;
4590 public:
4591 typedef negative_binomial_distribution distribution_type;
4592
4593 explicit param_type(result_type __k = 1, double __p = 0.5)
4594 : __k_(__k), __p_(__p) {}
4595
4596 result_type k() const {return __k_;}
4597 double p() const {return __p_;}
4598
4599 friend bool operator==(const param_type& __x, const param_type& __y)
4600 {return __x.__k_ == __y.__k_ && __x.__p_ == __y.__p_;}
4601 friend bool operator!=(const param_type& __x, const param_type& __y)
4602 {return !(__x == __y);}
4603 };
4604
4605private:
4606 param_type __p_;
4607
4608public:
4609 // constructor and reset functions
4610 explicit negative_binomial_distribution(result_type __k = 1, double __p = 0.5)
4611 : __p_(__k, __p) {}
4612 explicit negative_binomial_distribution(const param_type& __p) : __p_(__p) {}
4613 void reset() {}
4614
4615 // generating functions
4616 template<class _URNG> result_type operator()(_URNG& __g)
4617 {return (*this)(__g, __p_);}
4618 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
4619
4620 // property functions
4621 result_type k() const {return __p_.k();}
4622 double p() const {return __p_.p();}
4623
4624 param_type param() const {return __p_;}
4625 void param(const param_type& __p) {__p_ = __p;}
4626
4627 result_type min() const {return 0;}
4628 result_type max() const {return numeric_limits<result_type>::max();}
4629
4630 friend bool operator==(const negative_binomial_distribution& __x,
4631 const negative_binomial_distribution& __y)
4632 {return __x.__p_ == __y.__p_;}
4633 friend bool operator!=(const negative_binomial_distribution& __x,
4634 const negative_binomial_distribution& __y)
4635 {return !(__x == __y);}
4636};
4637
4638template <class _IntType>
4639template<class _URNG>
4640_IntType
4641negative_binomial_distribution<_IntType>::operator()(_URNG& __urng, const param_type& __pr)
4642{
4643 result_type __k = __pr.k();
4644 double __p = __pr.p();
4645 if (__k <= 21 * __p)
4646 {
4647 bernoulli_distribution __gen(__p);
4648 result_type __f = 0;
4649 result_type __s = 0;
4650 while (__s < __k)
4651 {
4652 if (__gen(__urng))
4653 ++__s;
4654 else
4655 ++__f;
4656 }
4657 return __f;
4658 }
4659 return poisson_distribution<result_type>(gamma_distribution<double>
4660 (__k, (1-__p)/__p)(__urng))(__urng);
4661}
4662
4663template <class _CharT, class _Traits, class _IntType>
4664basic_ostream<_CharT, _Traits>&
4665operator<<(basic_ostream<_CharT, _Traits>& __os,
4666 const negative_binomial_distribution<_IntType>& __x)
4667{
4668 __save_flags<_CharT, _Traits> _(__os);
4669 __os.flags(ios_base::dec | ios_base::left);
4670 _CharT __sp = __os.widen(' ');
4671 __os.fill(__sp);
4672 return __os << __x.k() << __sp << __x.p();
4673}
4674
4675template <class _CharT, class _Traits, class _IntType>
4676basic_istream<_CharT, _Traits>&
4677operator>>(basic_istream<_CharT, _Traits>& __is,
4678 negative_binomial_distribution<_IntType>& __x)
4679{
4680 typedef negative_binomial_distribution<_IntType> _Eng;
4681 typedef typename _Eng::result_type result_type;
4682 typedef typename _Eng::param_type param_type;
4683 __save_flags<_CharT, _Traits> _(__is);
4684 __is.flags(ios_base::dec | ios_base::skipws);
4685 result_type __k;
4686 double __p;
4687 __is >> __k >> __p;
4688 if (!__is.fail())
4689 __x.param(param_type(__k, __p));
4690 return __is;
4691}
4692
Howard Hinnant34e8a572010-05-17 13:44:27 +00004693// geometric_distribution
4694
4695template<class _IntType = int>
4696class geometric_distribution
4697{
4698public:
4699 // types
4700 typedef _IntType result_type;
4701
4702 class param_type
4703 {
4704 double __p_;
4705 public:
4706 typedef geometric_distribution distribution_type;
4707
4708 explicit param_type(double __p = 0.5) : __p_(__p) {}
4709
4710 double p() const {return __p_;}
4711
4712 friend bool operator==(const param_type& __x, const param_type& __y)
4713 {return __x.__p_ == __y.__p_;}
4714 friend bool operator!=(const param_type& __x, const param_type& __y)
4715 {return !(__x == __y);}
4716 };
4717
4718private:
4719 param_type __p_;
4720
4721public:
4722 // constructors and reset functions
4723 explicit geometric_distribution(double __p = 0.5) : __p_(__p) {}
4724 explicit geometric_distribution(const param_type& __p) : __p_(__p) {}
4725 void reset() {}
4726
4727 // generating functions
4728 template<class _URNG> result_type operator()(_URNG& __g)
4729 {return (*this)(__g, __p_);}
4730 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p)
4731 {return negative_binomial_distribution<result_type>(1, __p.p())(__g);}
4732
4733 // property functions
4734 double p() const {return __p_.p();}
4735
4736 param_type param() const {return __p_;}
4737 void param(const param_type& __p) {__p_ = __p;}
4738
4739 result_type min() const {return 0;}
4740 result_type max() const {return numeric_limits<result_type>::max();}
4741
4742 friend bool operator==(const geometric_distribution& __x,
4743 const geometric_distribution& __y)
4744 {return __x.__p_ == __y.__p_;}
4745 friend bool operator!=(const geometric_distribution& __x,
4746 const geometric_distribution& __y)
4747 {return !(__x == __y);}
4748};
4749
4750template <class _CharT, class _Traits, class _IntType>
4751basic_ostream<_CharT, _Traits>&
4752operator<<(basic_ostream<_CharT, _Traits>& __os,
4753 const geometric_distribution<_IntType>& __x)
4754{
4755 __save_flags<_CharT, _Traits> _(__os);
4756 __os.flags(ios_base::dec | ios_base::left);
4757 return __os << __x.p();
4758}
4759
4760template <class _CharT, class _Traits, class _IntType>
4761basic_istream<_CharT, _Traits>&
4762operator>>(basic_istream<_CharT, _Traits>& __is,
4763 geometric_distribution<_IntType>& __x)
4764{
4765 typedef geometric_distribution<_IntType> _Eng;
4766 typedef typename _Eng::param_type param_type;
4767 __save_flags<_CharT, _Traits> _(__is);
4768 __is.flags(ios_base::dec | ios_base::skipws);
4769 double __p;
4770 __is >> __p;
4771 if (!__is.fail())
4772 __x.param(param_type(__p));
4773 return __is;
4774}
4775
Howard Hinnant97dc2f32010-05-15 23:36:00 +00004776// chi_squared_distribution
4777
4778template<class _RealType = double>
4779class chi_squared_distribution
4780{
4781public:
4782 // types
4783 typedef _RealType result_type;
4784
4785 class param_type
4786 {
4787 result_type __n_;
4788 public:
4789 typedef chi_squared_distribution distribution_type;
4790
4791 explicit param_type(result_type __n = 1) : __n_(__n) {}
4792
4793 result_type n() const {return __n_;}
4794
4795 friend bool operator==(const param_type& __x, const param_type& __y)
4796 {return __x.__n_ == __y.__n_;}
4797 friend bool operator!=(const param_type& __x, const param_type& __y)
4798 {return !(__x == __y);}
4799 };
4800
4801private:
4802 param_type __p_;
4803
4804public:
4805 // constructor and reset functions
4806 explicit chi_squared_distribution(result_type __n = 1)
4807 : __p_(param_type(__n)) {}
4808 explicit chi_squared_distribution(const param_type& __p)
4809 : __p_(__p) {}
4810 void reset() {}
4811
4812 // generating functions
4813 template<class _URNG> result_type operator()(_URNG& __g)
4814 {return (*this)(__g, __p_);}
4815 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p)
4816 {return gamma_distribution<result_type>(__p.n() / 2, 2)(__g);}
4817
4818 // property functions
4819 result_type n() const {return __p_.n();}
4820
4821 param_type param() const {return __p_;}
4822 void param(const param_type& __p) {__p_ = __p;}
4823
4824 result_type min() const {return 0;}
4825 result_type max() const {return numeric_limits<result_type>::infinity();}
4826
4827
4828 friend bool operator==(const chi_squared_distribution& __x,
4829 const chi_squared_distribution& __y)
4830 {return __x.__p_ == __y.__p_;}
4831 friend bool operator!=(const chi_squared_distribution& __x,
4832 const chi_squared_distribution& __y)
4833 {return !(__x == __y);}
4834};
4835
4836template <class _CharT, class _Traits, class _RT>
4837basic_ostream<_CharT, _Traits>&
4838operator<<(basic_ostream<_CharT, _Traits>& __os,
4839 const chi_squared_distribution<_RT>& __x)
4840{
4841 __save_flags<_CharT, _Traits> _(__os);
4842 __os.flags(ios_base::dec | ios_base::left);
4843 __os << __x.n();
4844 return __os;
4845}
4846
4847template <class _CharT, class _Traits, class _RT>
4848basic_istream<_CharT, _Traits>&
4849operator>>(basic_istream<_CharT, _Traits>& __is,
4850 chi_squared_distribution<_RT>& __x)
4851{
4852 typedef chi_squared_distribution<_RT> _Eng;
4853 typedef typename _Eng::result_type result_type;
4854 typedef typename _Eng::param_type param_type;
4855 __save_flags<_CharT, _Traits> _(__is);
4856 __is.flags(ios_base::dec | ios_base::skipws);
4857 result_type __n;
4858 __is >> __n;
4859 if (!__is.fail())
4860 __x.param(param_type(__n));
4861 return __is;
4862}
4863
Howard Hinnantd7d01132010-05-17 21:55:46 +00004864// cauchy_distribution
4865
4866template<class _RealType = double>
4867class cauchy_distribution
4868{
4869public:
4870 // types
4871 typedef _RealType result_type;
4872
4873 class param_type
4874 {
4875 result_type __a_;
4876 result_type __b_;
4877 public:
4878 typedef cauchy_distribution distribution_type;
4879
4880 explicit param_type(result_type __a = 0, result_type __b = 1)
4881 : __a_(__a), __b_(__b) {}
4882
4883 result_type a() const {return __a_;}
4884 result_type b() const {return __b_;}
4885
4886 friend bool operator==(const param_type& __x, const param_type& __y)
4887 {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
4888 friend bool operator!=(const param_type& __x, const param_type& __y)
4889 {return !(__x == __y);}
4890 };
4891
4892private:
4893 param_type __p_;
4894
4895public:
4896 // constructor and reset functions
4897 explicit cauchy_distribution(result_type __a = 0, result_type __b = 1)
4898 : __p_(param_type(__a, __b)) {}
4899 explicit cauchy_distribution(const param_type& __p)
4900 : __p_(__p) {}
4901 void reset() {}
4902
4903 // generating functions
4904 template<class _URNG> result_type operator()(_URNG& __g)
4905 {return (*this)(__g, __p_);}
4906 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
4907
4908 // property functions
4909 result_type a() const {return __p_.a();}
4910 result_type b() const {return __p_.b();}
4911
4912 param_type param() const {return __p_;}
4913 void param(const param_type& __p) {__p_ = __p;}
4914
4915 result_type min() const {return -numeric_limits<result_type>::infinity();}
4916 result_type max() const {return numeric_limits<result_type>::infinity();}
4917
4918 friend bool operator==(const cauchy_distribution& __x,
4919 const cauchy_distribution& __y)
4920 {return __x.__p_ == __y.__p_;}
4921 friend bool operator!=(const cauchy_distribution& __x,
4922 const cauchy_distribution& __y)
4923 {return !(__x == __y);}
4924
4925 template <class _CharT, class _Traits, class _RT>
4926 friend
4927 basic_ostream<_CharT, _Traits>&
4928 operator<<(basic_ostream<_CharT, _Traits>& __os,
4929 const cauchy_distribution<_RT>& __x);
4930
4931 template <class _CharT, class _Traits, class _RT>
4932 friend
4933 basic_istream<_CharT, _Traits>&
4934 operator>>(basic_istream<_CharT, _Traits>& __is,
4935 cauchy_distribution<_RT>& __x);
4936};
4937
4938template <class _RealType>
4939template<class _URNG>
4940inline
4941_RealType
4942cauchy_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
4943{
4944 uniform_real_distribution<result_type> __gen;
4945 // purposefully let tan arg get as close to pi/2 as it wants, tan will return a finite
4946 return __p.a() + __p.b() * _STD::tan(3.1415926535897932384626433832795 * __gen(__g));
4947}
4948
4949template <class _CharT, class _Traits, class _RT>
4950basic_ostream<_CharT, _Traits>&
4951operator<<(basic_ostream<_CharT, _Traits>& __os,
4952 const cauchy_distribution<_RT>& __x)
4953{
4954 __save_flags<_CharT, _Traits> _(__os);
4955 __os.flags(ios_base::dec | ios_base::left);
4956 _CharT __sp = __os.widen(' ');
4957 __os.fill(__sp);
4958 __os << __x.a() << __sp << __x.b();
4959 return __os;
4960}
4961
4962template <class _CharT, class _Traits, class _RT>
4963basic_istream<_CharT, _Traits>&
4964operator>>(basic_istream<_CharT, _Traits>& __is,
4965 cauchy_distribution<_RT>& __x)
4966{
4967 typedef cauchy_distribution<_RT> _Eng;
4968 typedef typename _Eng::result_type result_type;
4969 typedef typename _Eng::param_type param_type;
4970 __save_flags<_CharT, _Traits> _(__is);
4971 __is.flags(ios_base::dec | ios_base::skipws);
4972 result_type __a;
4973 result_type __b;
4974 __is >> __a >> __b;
4975 if (!__is.fail())
4976 __x.param(param_type(__a, __b));
4977 return __is;
4978}
4979
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00004980_LIBCPP_END_NAMESPACE_STD
4981
4982#endif // _LIBCPP_RANDOM