Gitiles
Code Review Sign In
gerrit-public.fairphone.software / platform / external / libcxx / 03aad81afdf77c64e50d0df3f1a8767ea24aa827 / . / include / random
blob: 0f2c6eae24ff998af464c8ba77365ace3e1efc0d [file] [log] [blame]
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]1// -*- C++ -*-
2//===--------------------------- random -----------------------------------===//
3//
Howard Hinnantf5256e12010-05-11 21:36:01 +0000[diff] [blame]4// The LLVM Compiler Infrastructure
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]5//
6// This file is distributed under the University of Illinois Open Source
7// License. See LICENSE.TXT for details.
8//
9//===----------------------------------------------------------------------===//
10
11#ifndef _LIBCPP_RANDOM
12#define _LIBCPP_RANDOM
13
14/*
15 random synopsis
16
17#include <initializer_list>
18
19namespace std
20{
21
22// Engines
23
24template <class UIntType, UIntType a, UIntType c, UIntType m>
25class linear_congruential_engine
26{
27public:
28 // types
29 typedef UIntType result_type;
30
31 // engine characteristics
32 static constexpr result_type multiplier = a;
33 static constexpr result_type increment = c;
34 static constexpr result_type modulus = m;
35 static constexpr result_type min() { return c == 0u ? 1u: 0u;}
36 static constexpr result_type max() { return m - 1u;}
37 static constexpr result_type default_seed = 1u;
38
39 // constructors and seeding functions
40 explicit linear_congruential_engine(result_type s = default_seed);
41 template<class Sseq> explicit linear_congruential_engine(Sseq& q);
42 void seed(result_type s = default_seed);
43 template<class Sseq> void seed(Sseq& q);
44
45 // generating functions
46 result_type operator()();
47 void discard(unsigned long long z);
48};
49
50template <class UIntType, UIntType a, UIntType c, UIntType m>
51bool
52operator==(const linear_congruential_engine<UIntType, a, c, m>& x,
53 const linear_congruential_engine<UIntType, a, c, m>& y);
54
55template <class UIntType, UIntType a, UIntType c, UIntType m>
56bool
57operator!=(const linear_congruential_engine<UIntType, a, c, m>& x,
58 const linear_congruential_engine<UIntType, a, c, m>& y);
59
60template <class charT, class traits,
61 class UIntType, UIntType a, UIntType c, UIntType m>
62basic_ostream<charT, traits>&
63operator<<(basic_ostream<charT, traits>& os,
64 const linear_congruential_engine<UIntType, a, c, m>& x);
65
66template <class charT, class traits,
67 class UIntType, UIntType a, UIntType c, UIntType m>
68basic_istream<charT, traits>&
69operator>>(basic_istream<charT, traits>& is,
70 linear_congruential_engine<UIntType, a, c, m>& x);
71
72template <class UIntType, size_t w, size_t n, size_t m, size_t r,
73 UIntType a, size_t u, UIntType d, size_t s,
74 UIntType b, size_t t, UIntType c, size_t l, UIntType f>
75class mersenne_twister_engine
76{
77public:
78 // types
79 typedef UIntType result_type;
80
81 // engine characteristics
82 static constexpr size_t word_size = w;
83 static constexpr size_t state_size = n;
84 static constexpr size_t shift_size = m;
85 static constexpr size_t mask_bits = r;
86 static constexpr result_type xor_mask = a;
87 static constexpr size_t tempering_u = u;
88 static constexpr result_type tempering_d = d;
89 static constexpr size_t tempering_s = s;
90 static constexpr result_type tempering_b = b;
91 static constexpr size_t tempering_t = t;
92 static constexpr result_type tempering_c = c;
93 static constexpr size_t tempering_l = l;
94 static constexpr result_type initialization_multiplier = f;
95 static constexpr result_type min () { return 0; }
96 static constexpr result_type max() { return 2^w - 1; }
97 static constexpr result_type default_seed = 5489u;
98
99 // constructors and seeding functions
100 explicit mersenne_twister_engine(result_type value = default_seed);
101 template<class Sseq> explicit mersenne_twister_engine(Sseq& q);
102 void seed(result_type value = default_seed);
103 template<class Sseq> void seed(Sseq& q);
104
105 // generating functions
106 result_type operator()();
107 void discard(unsigned long long z);
108};
109
110template <class UIntType, size_t w, size_t n, size_t m, size_t r,
111 UIntType a, size_t u, UIntType d, size_t s,
112 UIntType b, size_t t, UIntType c, size_t l, UIntType f>
113bool
114operator==(
115 const mersenne_twister_engine<UIntType, w, n, m, r, a, u, d, s, b, t, c, l, f>& x,
116 const mersenne_twister_engine<UIntType, w, n, m, r, a, u, d, s, b, t, c, l, f>& y);
117
118template <class UIntType, size_t w, size_t n, size_t m, size_t r,
119 UIntType a, size_t u, UIntType d, size_t s,
120 UIntType b, size_t t, UIntType c, size_t l, UIntType f>
121bool
122operator!=(
123 const mersenne_twister_engine<UIntType, w, n, m, r, a, u, d, s, b, t, c, l, f>& x,
124 const mersenne_twister_engine<UIntType, w, n, m, r, a, u, d, s, b, t, c, l, f>& y);
125
126template <class charT, class traits,
127 class UIntType, size_t w, size_t n, size_t m, size_t r,
128 UIntType a, size_t u, UIntType d, size_t s,
129 UIntType b, size_t t, UIntType c, size_t l, UIntType f>
130basic_ostream<charT, traits>&
131operator<<(basic_ostream<charT, traits>& os,
132 const mersenne_twister_engine<UIntType, w, n, m, r, a, u, d, s, b, t, c, l, f>& x);
133
134template <class charT, class traits,
135 class UIntType, size_t w, size_t n, size_t m, size_t r,
136 UIntType a, size_t u, UIntType d, size_t s,
137 UIntType b, size_t t, UIntType c, size_t l, UIntType f>
138basic_istream<charT, traits>&
139operator>>(basic_istream<charT, traits>& is,
140 mersenne_twister_engine<UIntType, w, n, m, r, a, u, d, s, b, t, c, l, f>& x);
141
142template<class UIntType, size_t w, size_t s, size_t r>
143class subtract_with_carry_engine
144{
145public:
146 // types
147 typedef UIntType result_type;
148
149 // engine characteristics
150 static constexpr size_t word_size = w;
151 static constexpr size_t short_lag = s;
152 static constexpr size_t long_lag = r;
153 static constexpr result_type min() { return 0; }
154 static constexpr result_type max() { return m-1; }
155 static constexpr result_type default_seed = 19780503u;
156
157 // constructors and seeding functions
158 explicit subtract_with_carry_engine(result_type value = default_seed);
159 template<class Sseq> explicit subtract_with_carry_engine(Sseq& q);
160 void seed(result_type value = default_seed);
161 template<class Sseq> void seed(Sseq& q);
162
163 // generating functions
164 result_type operator()();
165 void discard(unsigned long long z);
166};
167
168template<class UIntType, size_t w, size_t s, size_t r>
169bool
170operator==(
171 const subtract_with_carry_engine<UIntType, w, s, r>& x,
172 const subtract_with_carry_engine<UIntType, w, s, r>& y);
173
174template<class UIntType, size_t w, size_t s, size_t r>
175bool
176operator!=(
177 const subtract_with_carry_engine<UIntType, w, s, r>& x,
178 const subtract_with_carry_engine<UIntType, w, s, r>& y);
179
180template <class charT, class traits,
181 class UIntType, size_t w, size_t s, size_t r>
182basic_ostream<charT, traits>&
183operator<<(basic_ostream<charT, traits>& os,
184 const subtract_with_carry_engine<UIntType, w, s, r>& x);
185
186template <class charT, class traits,
187 class UIntType, size_t w, size_t s, size_t r>
188basic_istream<charT, traits>&
189operator>>(basic_istream<charT, traits>& is,
190 subtract_with_carry_engine<UIntType, w, s, r>& x);
191
192template<class Engine, size_t p, size_t r>
193class discard_block_engine
194{
195public:
196 // types
197 typedef typename Engine::result_type result_type;
198
199 // engine characteristics
200 static constexpr size_t block_size = p;
201 static constexpr size_t used_block = r;
202 static constexpr result_type min() { return Engine::min(); }
203 static constexpr result_type max() { return Engine::max(); }
204
205 // constructors and seeding functions
206 discard_block_engine();
207 explicit discard_block_engine(const Engine& e);
208 explicit discard_block_engine(Engine&& e);
209 explicit discard_block_engine(result_type s);
210 template<class Sseq> explicit discard_block_engine(Sseq& q);
211 void seed();
212 void seed(result_type s);
213 template<class Sseq> void seed(Sseq& q);
214
215 // generating functions
216 result_type operator()();
217 void discard(unsigned long long z);
218
219 // property functions
220 const Engine& base() const;
221};
222
223template<class Engine, size_t p, size_t r>
224bool
225operator==(
226 const discard_block_engine<Engine, p, r>& x,
227 const discard_block_engine<Engine, p, r>& y);
228
229template<class Engine, size_t p, size_t r>
230bool
231operator!=(
232 const discard_block_engine<Engine, p, r>& x,
233 const discard_block_engine<Engine, p, r>& y);
234
235template <class charT, class traits,
236 class Engine, size_t p, size_t r>
237basic_ostream<charT, traits>&
238operator<<(basic_ostream<charT, traits>& os,
239 const discard_block_engine<Engine, p, r>& x);
240
241template <class charT, class traits,
242 class Engine, size_t p, size_t r>
243basic_istream<charT, traits>&
244operator>>(basic_istream<charT, traits>& is,
245 discard_block_engine<Engine, p, r>& x);
246
247template<class Engine, size_t w, class UIntType>
248class independent_bits_engine
249{
250public:
251 // types
252 typedef UIntType result_type;
253
254 // engine characteristics
255 static constexpr result_type min() { return 0; }
256 static constexpr result_type max() { return 2^w - 1; }
257
258 // constructors and seeding functions
259 independent_bits_engine();
260 explicit independent_bits_engine(const Engine& e);
261 explicit independent_bits_engine(Engine&& e);
262 explicit independent_bits_engine(result_type s);
263 template<class Sseq> explicit independent_bits_engine(Sseq& q);
264 void seed();
265 void seed(result_type s);
266 template<class Sseq> void seed(Sseq& q);
267
268 // generating functions
269 result_type operator()(); void discard(unsigned long long z);
270
271 // property functions
272 const Engine& base() const;
273};
274
275template<class Engine, size_t w, class UIntType>
276bool
277operator==(
278 const independent_bits_engine<Engine, w, UIntType>& x,
279 const independent_bits_engine<Engine, w, UIntType>& y);
280
281template<class Engine, size_t w, class UIntType>
282bool
283operator!=(
284 const independent_bits_engine<Engine, w, UIntType>& x,
285 const independent_bits_engine<Engine, w, UIntType>& y);
286
287template <class charT, class traits,
288 class Engine, size_t w, class UIntType>
289basic_ostream<charT, traits>&
290operator<<(basic_ostream<charT, traits>& os,
291 const independent_bits_engine<Engine, w, UIntType>& x);
292
293template <class charT, class traits,
294 class Engine, size_t w, class UIntType>
295basic_istream<charT, traits>&
296operator>>(basic_istream<charT, traits>& is,
297 independent_bits_engine<Engine, w, UIntType>& x);
298
299template<class Engine, size_t k>
300class shuffle_order_engine
301{
302public:
303 // types
304 typedef typename Engine::result_type result_type;
305
306 // engine characteristics
307 static constexpr size_t table_size = k;
308 static constexpr result_type min() { return Engine::min; }
309 static constexpr result_type max() { return Engine::max; }
310
311 // constructors and seeding functions
312 shuffle_order_engine();
313 explicit shuffle_order_engine(const Engine& e);
314 explicit shuffle_order_engine(Engine&& e);
315 explicit shuffle_order_engine(result_type s);
316 template<class Sseq> explicit shuffle_order_engine(Sseq& q);
317 void seed();
318 void seed(result_type s);
319 template<class Sseq> void seed(Sseq& q);
320
321 // generating functions
322 result_type operator()();
323 void discard(unsigned long long z);
324
325 // property functions
326 const Engine& base() const;
327};
328
329template<class Engine, size_t k>
330bool
331operator==(
332 const shuffle_order_engine<Engine, k>& x,
333 const shuffle_order_engine<Engine, k>& y);
334
335template<class Engine, size_t k>
336bool
337operator!=(
338 const shuffle_order_engine<Engine, k>& x,
339 const shuffle_order_engine<Engine, k>& y);
340
341template <class charT, class traits,
342 class Engine, size_t k>
343basic_ostream<charT, traits>&
344operator<<(basic_ostream<charT, traits>& os,
345 const shuffle_order_engine<Engine, k>& x);
346
347template <class charT, class traits,
348 class Engine, size_t k>
349basic_istream<charT, traits>&
350operator>>(basic_istream<charT, traits>& is,
351 shuffle_order_engine<Engine, k>& x);
352
353typedef linear_congruential_engine<uint_fast32_t, 16807, 0, 2147483647>
354 minstd_rand0;
355typedef linear_congruential_engine<uint_fast32_t, 48271, 0, 2147483647>
356 minstd_rand;
357typedef mersenne_twister_engine<uint_fast32_t, 32, 624, 397, 31,
358 0x9908b0df,
359 11, 0xffffffff,
360 7, 0x9d2c5680,
361 15, 0xefc60000,
362 18, 1812433253> mt19937;
363typedef mersenne_twister_engine<uint_fast64_t, 64, 312, 156, 31,
364 0xb5026f5aa96619e9,
365 29, 0x5555555555555555,
366 17, 0x71d67fffeda60000,
367 37, 0xfff7eee000000000,
368 43, 6364136223846793005> mt19937_64;
369typedef subtract_with_carry_engine<uint_fast32_t, 24, 10, 24> ranlux24_base;
370typedef subtract_with_carry_engine<uint_fast64_t, 48, 5, 12> ranlux48_base;
371typedef discard_block_engine<ranlux24_base, 223, 23> ranlux24;
372typedef discard_block_engine<ranlux48_base, 389, 11> ranlux48;
373typedef shuffle_order_engine<minstd_rand0, 256> knuth_b;
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 +0000[diff] [blame^]611class binomial_distribution
612{
613public:
614 // types
615 typedef IntType result_type;
616
617 class param_type
618 {
619 public:
620 typedef binomial_distribution distribution_type;
621
622 explicit param_type(IntType t = 1, double p = 0.5);
623
624 IntType t() const;
625 double p() const;
626
627 friend bool operator==(const param_type& x, const param_type& y);
628 friend bool operator!=(const param_type& x, const param_type& y);
629 };
630
631 // constructors and reset functions
632 explicit binomial_distribution(IntType t = 1, double p = 0.5);
633 explicit binomial_distribution(const param_type& parm);
634 void reset();
635
636 // generating functions
637 template<class URNG> result_type operator()(URNG& g);
638 template<class URNG> result_type operator()(URNG& g, const param_type& parm);
639
640 // property functions
641 IntType t() const;
642 double p() const;
643
644 param_type param() const;
645 void param(const param_type& parm);
646
647 result_type min() const;
648 result_type max() const;
649
650 friend bool operator==(const binomial_distribution& x,
651 const binomial_distribution& y);
652 friend bool operator!=(const binomial_distribution& x,
653 const binomial_distribution& y);
654
655 template <class charT, class traits>
656 friend
657 basic_ostream<charT, traits>&
658 operator<<(basic_ostream<charT, traits>& os,
659 const binomial_distribution& x);
660
661 template <class charT, class traits>
662 friend
663 basic_istream<charT, traits>&
664 operator>>(basic_istream<charT, traits>& is,
665 binomial_distribution& x);
666};
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]667
668template<class IntType = int>
669 class geometric_distribution;
670
671template<class IntType = int>
672 class negative_binomial_distribution;
673
674template<class IntType = int>
675 class poisson_distribution;
676
677template<class RealType = double>
678 class exponential_distribution;
679
680template<class RealType = double>
681 class gamma_distribution;
682
683template<class RealType = double>
684 class weibull_distribution;
685
686template<class RealType = double>
687 class extreme_value_distribution;
688
689template<class RealType = double>
690 class normal_distribution;
691
692template<class RealType = double>
693 class lognormal_distribution;
694
695template<class RealType = double>
696 class chi_squared_distribution;
697
698template<class RealType = double>
699 class cauchy_distribution;
700
701template<class RealType = double>
702 class fisher_f_distribution;
703
704template<class RealType = double>
705 class student_t_distribution;
706
707template<class IntType = int>
708 class discrete_distribution;
709
710template<class RealType = double>
711 class piecewise_constant_distribution;
712
713template<class RealType = double>
714 class piecewise_linear_distribution;
715
716} // std
717*/
718
719#include <__config>
720#include <cstddef>
721#include <type_traits>
722#include <initializer_list>
723#include <cstdint>
724#include <limits>
725#include <algorithm>
726#include <vector>
727#include <string>
728#include <istream>
729#include <ostream>
730
731#pragma GCC system_header
732
733_LIBCPP_BEGIN_NAMESPACE_STD
734
735// linear_congruential_engine
736
737template <unsigned long long __a, unsigned long long __c,
738 unsigned long long __m, unsigned long long _M,
739 bool _MightOverflow = (__a != 0 && __m != 0 && __m-1 > (_M-__c)/__a)>
740struct __lce_ta;
741
742// 64
743
744template <unsigned long long __a, unsigned long long __c, unsigned long long __m>
745struct __lce_ta<__a, __c, __m, (unsigned long long)(~0), true>
746{
747 typedef unsigned long long result_type;
748 static result_type next(result_type __x)
749 {
750 // Schrage's algorithm
751 const result_type __q = __m / __a;
752 const result_type __r = __m % __a;
753 const result_type __t0 = __a * (__x % __q);
754 const result_type __t1 = __r * (__x / __q);
755 __x = __t0 + (__t0 < __t1) * __m - __t1;
756 __x += __c - (__x >= __m - __c) * __m;
757 return __x;
758 }
759};
760
761template <unsigned long long __a, unsigned long long __m>
762struct __lce_ta<__a, 0, __m, (unsigned long long)(~0), true>
763{
764 typedef unsigned long long result_type;
765 static result_type next(result_type __x)
766 {
767 // Schrage's algorithm
768 const result_type __q = __m / __a;
769 const result_type __r = __m % __a;
770 const result_type __t0 = __a * (__x % __q);
771 const result_type __t1 = __r * (__x / __q);
772 __x = __t0 + (__t0 < __t1) * __m - __t1;
773 return __x;
774 }
775};
776
777template <unsigned long long __a, unsigned long long __c, unsigned long long __m>
778struct __lce_ta<__a, __c, __m, (unsigned long long)(~0), false>
779{
780 typedef unsigned long long result_type;
781 static result_type next(result_type __x)
782 {
783 return (__a * __x + __c) % __m;
784 }
785};
786
787template <unsigned long long __a, unsigned long long __c>
788struct __lce_ta<__a, __c, 0, (unsigned long long)(~0), false>
789{
790 typedef unsigned long long result_type;
791 static result_type next(result_type __x)
792 {
793 return __a * __x + __c;
794 }
795};
796
797// 32
798
799template <unsigned long long _A, unsigned long long _C, unsigned long long _M>
800struct __lce_ta<_A, _C, _M, unsigned(~0), true>
801{
802 typedef unsigned result_type;
803 static result_type next(result_type __x)
804 {
805 const result_type __a = static_cast<result_type>(_A);
806 const result_type __c = static_cast<result_type>(_C);
807 const result_type __m = static_cast<result_type>(_M);
808 // Schrage's algorithm
809 const result_type __q = __m / __a;
810 const result_type __r = __m % __a;
811 const result_type __t0 = __a * (__x % __q);
812 const result_type __t1 = __r * (__x / __q);
813 __x = __t0 + (__t0 < __t1) * __m - __t1;
814 __x += __c - (__x >= __m - __c) * __m;
815 return __x;
816 }
817};
818
819template <unsigned long long _A, unsigned long long _M>
820struct __lce_ta<_A, 0, _M, unsigned(~0), true>
821{
822 typedef unsigned result_type;
823 static result_type next(result_type __x)
824 {
825 const result_type __a = static_cast<result_type>(_A);
826 const result_type __m = static_cast<result_type>(_M);
827 // Schrage's algorithm
828 const result_type __q = __m / __a;
829 const result_type __r = __m % __a;
830 const result_type __t0 = __a * (__x % __q);
831 const result_type __t1 = __r * (__x / __q);
832 __x = __t0 + (__t0 < __t1) * __m - __t1;
833 return __x;
834 }
835};
836
837template <unsigned long long _A, unsigned long long _C, unsigned long long _M>
838struct __lce_ta<_A, _C, _M, unsigned(~0), false>
839{
840 typedef unsigned result_type;
841 static result_type next(result_type __x)
842 {
843 const result_type __a = static_cast<result_type>(_A);
844 const result_type __c = static_cast<result_type>(_C);
845 const result_type __m = static_cast<result_type>(_M);
846 return (__a * __x + __c) % __m;
847 }
848};
849
850template <unsigned long long _A, unsigned long long _C>
851struct __lce_ta<_A, _C, 0, unsigned(~0), false>
852{
853 typedef unsigned result_type;
854 static result_type next(result_type __x)
855 {
856 const result_type __a = static_cast<result_type>(_A);
857 const result_type __c = static_cast<result_type>(_C);
858 return __a * __x + __c;
859 }
860};
861
862// 16
863
864template <unsigned long long __a, unsigned long long __c, unsigned long long __m, bool __b>
865struct __lce_ta<__a, __c, __m, (unsigned short)(~0), __b>
866{
867 typedef unsigned short result_type;
868 static result_type next(result_type __x)
869 {
870 return static_cast<result_type>(__lce_ta<__a, __c, __m, unsigned(~0)>::next(__x));
871 }
872};
873
874template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
875class linear_congruential_engine;
876
877template <class _CharT, class _Traits,
878 class _U, _U _A, _U _C, _U _N>
879basic_ostream<_CharT, _Traits>&
880operator<<(basic_ostream<_CharT, _Traits>& __os,
881 const linear_congruential_engine<_U, _A, _C, _N>&);
882
883template <class _CharT, class _Traits,
884 class _U, _U _A, _U _C, _U _N>
885basic_istream<_CharT, _Traits>&
886operator>>(basic_istream<_CharT, _Traits>& __is,
887 linear_congruential_engine<_U, _A, _C, _N>& __x);
888
889template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
890class linear_congruential_engine
891{
892public:
893 // types
894 typedef _UIntType result_type;
895
896private:
897 result_type __x_;
898
899 static const result_type _M = result_type(~0);
900
901 static_assert(__m == 0 || __a < __m, "linear_congruential_engine invalid parameters");
902 static_assert(__m == 0 || __c < __m, "linear_congruential_engine invalid parameters");
903public:
904 static const result_type _Min = __c == 0u ? 1u: 0u;
905 static const result_type _Max = __m - 1u;
906 static_assert(_Min < _Max, "linear_congruential_engine invalid parameters");
907
908 // engine characteristics
909 static const/*expr*/ result_type multiplier = __a;
910 static const/*expr*/ result_type increment = __c;
911 static const/*expr*/ result_type modulus = __m;
912 static const/*expr*/ result_type min() {return _Min;}
913 static const/*expr*/ result_type max() {return _Max;}
914 static const/*expr*/ result_type default_seed = 1u;
915
916 // constructors and seeding functions
917 explicit linear_congruential_engine(result_type __s = default_seed)
918 {seed(__s);}
919 template<class _Sseq> explicit linear_congruential_engine(_Sseq& __q)
920 {seed(__q);}
921 void seed(result_type __s = default_seed)
922 {seed(integral_constant<bool, __m == 0>(),
923 integral_constant<bool, __c == 0>(), __s);}
924 template<class _Sseq>
925 typename enable_if
926 <
927 !is_convertible<_Sseq, result_type>::value,
928 void
929 >::type
930 seed(_Sseq& __q)
931 {__seed(__q, integral_constant<unsigned,
932 1 + (__m == 0 ? (sizeof(result_type) * __CHAR_BIT__ - 1)/32
933 : (__m-1) / 0x100000000ull)>());}
934
935 // generating functions
936 result_type operator()()
937 {return __x_ = static_cast<result_type>(__lce_ta<__a, __c, __m, _M>::next(__x_));}
938 void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
939
940 friend bool operator==(const linear_congruential_engine& __x,
941 const linear_congruential_engine& __y)
942 {return __x.__x_ == __y.__x_;}
943 friend bool operator!=(const linear_congruential_engine& __x,
944 const linear_congruential_engine& __y)
945 {return !(__x == __y);}
946
947private:
948
949 void seed(true_type, true_type, result_type __s) {__x_ = __s == 0 ? 1 : __s;}
950 void seed(true_type, false_type, result_type __s) {__x_ = __s;}
951 void seed(false_type, true_type, result_type __s) {__x_ = __s % __m == 0 ?
952 1 : __s % __m;}
953 void seed(false_type, false_type, result_type __s) {__x_ = __s % __m;}
954
955 template<class _Sseq>
956 void __seed(_Sseq& __q, integral_constant<unsigned, 1>);
957 template<class _Sseq>
958 void __seed(_Sseq& __q, integral_constant<unsigned, 2>);
959
960 template <class _CharT, class _Traits,
961 class _U, _U _A, _U _C, _U _N>
962 friend
963 basic_ostream<_CharT, _Traits>&
964 operator<<(basic_ostream<_CharT, _Traits>& __os,
965 const linear_congruential_engine<_U, _A, _C, _N>&);
966
967 template <class _CharT, class _Traits,
968 class _U, _U _A, _U _C, _U _N>
969 friend
970 basic_istream<_CharT, _Traits>&
971 operator>>(basic_istream<_CharT, _Traits>& __is,
972 linear_congruential_engine<_U, _A, _C, _N>& __x);
973};
974
975template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
976template<class _Sseq>
977void
978linear_congruential_engine<_UIntType, __a, __c, __m>::__seed(_Sseq& __q,
979 integral_constant<unsigned, 1>)
980{
981 const unsigned __k = 1;
982 uint32_t __ar[__k+3];
983 __q.generate(__ar, __ar + __k + 3);
984 result_type __s = static_cast<result_type>(__ar[3] % __m);
985 __x_ = __c == 0 && __s == 0 ? result_type(1) : __s;
986}
987
988template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
989template<class _Sseq>
990void
991linear_congruential_engine<_UIntType, __a, __c, __m>::__seed(_Sseq& __q,
992 integral_constant<unsigned, 2>)
993{
994 const unsigned __k = 2;
995 uint32_t __ar[__k+3];
996 __q.generate(__ar, __ar + __k + 3);
997 result_type __s = static_cast<result_type>((__ar[3] +
998 (uint64_t)__ar[4] << 32) % __m);
999 __x_ = __c == 0 && __s == 0 ? result_type(1) : __s;
1000}
1001
1002template <class _CharT, class _Traits>
1003class __save_flags
1004{
1005 typedef basic_ios<_CharT, _Traits> __stream_type;
1006 typedef typename __stream_type::fmtflags fmtflags;
1007
1008 __stream_type& __stream_;
1009 fmtflags __fmtflags_;
1010 _CharT __fill_;
1011
1012 __save_flags(const __save_flags&);
1013 __save_flags& operator=(const __save_flags&);
1014public:
1015 explicit __save_flags(__stream_type& __stream)
1016 : __stream_(__stream),
1017 __fmtflags_(__stream.flags()),
1018 __fill_(__stream.fill())
1019 {}
1020 ~__save_flags()
1021 {
1022 __stream_.flags(__fmtflags_);
1023 __stream_.fill(__fill_);
1024 }
1025};
1026
1027template <class _CharT, class _Traits,
1028 class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1029inline
1030basic_ostream<_CharT, _Traits>&
1031operator<<(basic_ostream<_CharT, _Traits>& __os,
1032 const linear_congruential_engine<_UIntType, __a, __c, __m>& __x)
1033{
1034 __save_flags<_CharT, _Traits> _(__os);
1035 __os.flags(ios_base::dec | ios_base::left);
1036 __os.fill(__os.widen(' '));
1037 return __os << __x.__x_;
1038}
1039
1040template <class _CharT, class _Traits,
1041 class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1042basic_istream<_CharT, _Traits>&
1043operator>>(basic_istream<_CharT, _Traits>& __is,
1044 linear_congruential_engine<_UIntType, __a, __c, __m>& __x)
1045{
1046 __save_flags<_CharT, _Traits> _(__is);
1047 __is.flags(ios_base::dec | ios_base::skipws);
1048 _UIntType __t;
1049 __is >> __t;
1050 if (!__is.fail())
1051 __x.__x_ = __t;
1052 return __is;
1053}
1054
1055typedef linear_congruential_engine<uint_fast32_t, 16807, 0, 2147483647>
1056 minstd_rand0;
1057typedef minstd_rand0 default_random_engine;
1058typedef linear_congruential_engine<uint_fast32_t, 48271, 0, 2147483647>
1059 minstd_rand;
1060// mersenne_twister_engine
1061
1062template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
1063 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
1064 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
1065class mersenne_twister_engine;
1066
1067template <class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
1068 _UI _A, size_t _U, _UI _D, size_t _S,
1069 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
1070bool
1071operator==(const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1072 _B, _T, _C, _L, _F>& __x,
1073 const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1074 _B, _T, _C, _L, _F>& __y);
1075
1076template <class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
1077 _UI _A, size_t _U, _UI _D, size_t _S,
1078 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
1079bool
1080operator!=(const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1081 _B, _T, _C, _L, _F>& __x,
1082 const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1083 _B, _T, _C, _L, _F>& __y);
1084
1085template <class _CharT, class _Traits,
1086 class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
1087 _UI _A, size_t _U, _UI _D, size_t _S,
1088 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
1089basic_ostream<_CharT, _Traits>&
1090operator<<(basic_ostream<_CharT, _Traits>& __os,
1091 const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1092 _B, _T, _C, _L, _F>& __x);
1093
1094template <class _CharT, class _Traits,
1095 class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
1096 _UI _A, size_t _U, _UI _D, size_t _S,
1097 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
1098basic_istream<_CharT, _Traits>&
1099operator>>(basic_istream<_CharT, _Traits>& __is,
1100 mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1101 _B, _T, _C, _L, _F>& __x);
1102
1103template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
1104 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
1105 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
1106class mersenne_twister_engine
1107{
1108public:
1109 // types
1110 typedef _UIntType result_type;
1111
1112private:
1113 result_type __x_[__n];
1114 size_t __i_;
1115
1116 static_assert( 0 < __m, "mersenne_twister_engine invalid parameters");
1117 static_assert(__m <= __n, "mersenne_twister_engine invalid parameters");
1118 static const result_type _Dt = numeric_limits<result_type>::digits;
1119 static_assert(__w <= _Dt, "mersenne_twister_engine invalid parameters");
1120 static_assert( 2 <= __w, "mersenne_twister_engine invalid parameters");
1121 static_assert(__r <= __w, "mersenne_twister_engine invalid parameters");
1122 static_assert(__u <= __w, "mersenne_twister_engine invalid parameters");
1123 static_assert(__s <= __w, "mersenne_twister_engine invalid parameters");
1124 static_assert(__t <= __w, "mersenne_twister_engine invalid parameters");
1125 static_assert(__l <= __w, "mersenne_twister_engine invalid parameters");
1126public:
1127 static const result_type _Min = 0;
1128 static const result_type _Max = __w == _Dt ? result_type(~0) :
1129 (result_type(1) << __w) - result_type(1);
1130 static_assert(_Min < _Max, "mersenne_twister_engine invalid parameters");
1131 static_assert(__a <= _Max, "mersenne_twister_engine invalid parameters");
1132 static_assert(__b <= _Max, "mersenne_twister_engine invalid parameters");
1133 static_assert(__c <= _Max, "mersenne_twister_engine invalid parameters");
1134 static_assert(__d <= _Max, "mersenne_twister_engine invalid parameters");
1135 static_assert(__f <= _Max, "mersenne_twister_engine invalid parameters");
1136
1137 // engine characteristics
1138 static const/*expr*/ size_t word_size = __w;
1139 static const/*expr*/ size_t state_size = __n;
1140 static const/*expr*/ size_t shift_size = __m;
1141 static const/*expr*/ size_t mask_bits = __r;
1142 static const/*expr*/ result_type xor_mask = __a;
1143 static const/*expr*/ size_t tempering_u = __u;
1144 static const/*expr*/ result_type tempering_d = __d;
1145 static const/*expr*/ size_t tempering_s = __s;
1146 static const/*expr*/ result_type tempering_b = __b;
1147 static const/*expr*/ size_t tempering_t = __t;
1148 static const/*expr*/ result_type tempering_c = __c;
1149 static const/*expr*/ size_t tempering_l = __l;
1150 static const/*expr*/ result_type initialization_multiplier = __f;
1151 static const/*expr*/ result_type min() { return _Min; }
1152 static const/*expr*/ result_type max() { return _Max; }
1153 static const/*expr*/ result_type default_seed = 5489u;
1154
1155 // constructors and seeding functions
1156 explicit mersenne_twister_engine(result_type __sd = default_seed)
1157 {seed(__sd);}
1158 template<class _Sseq> explicit mersenne_twister_engine(_Sseq& __q)
1159 {seed(__q);}
1160 void seed(result_type __sd = default_seed);
1161 template<class _Sseq>
1162 typename enable_if
1163 <
1164 !is_convertible<_Sseq, result_type>::value,
1165 void
1166 >::type
1167 seed(_Sseq& __q)
1168 {__seed(__q, integral_constant<unsigned, 1 + (__w - 1) / 32>());}
1169
1170 // generating functions
1171 result_type operator()();
1172 void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
1173
1174 template <class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
1175 _UI _A, size_t _U, _UI _D, size_t _S,
1176 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
1177 friend
1178 bool
1179 operator==(const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1180 _B, _T, _C, _L, _F>& __x,
1181 const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1182 _B, _T, _C, _L, _F>& __y);
1183
1184 template <class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
1185 _UI _A, size_t _U, _UI _D, size_t _S,
1186 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
1187 friend
1188 bool
1189 operator!=(const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1190 _B, _T, _C, _L, _F>& __x,
1191 const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1192 _B, _T, _C, _L, _F>& __y);
1193
1194 template <class _CharT, class _Traits,
1195 class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
1196 _UI _A, size_t _U, _UI _D, size_t _S,
1197 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
1198 friend
1199 basic_ostream<_CharT, _Traits>&
1200 operator<<(basic_ostream<_CharT, _Traits>& __os,
1201 const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1202 _B, _T, _C, _L, _F>& __x);
1203
1204 template <class _CharT, class _Traits,
1205 class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
1206 _UI _A, size_t _U, _UI _D, size_t _S,
1207 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
1208 friend
1209 basic_istream<_CharT, _Traits>&
1210 operator>>(basic_istream<_CharT, _Traits>& __is,
1211 mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1212 _B, _T, _C, _L, _F>& __x);
1213private:
1214
1215 template<class _Sseq>
1216 void __seed(_Sseq& __q, integral_constant<unsigned, 1>);
1217 template<class _Sseq>
1218 void __seed(_Sseq& __q, integral_constant<unsigned, 2>);
1219
1220 template <size_t __count>
1221 static
1222 typename enable_if
1223 <
1224 __count < __w,
1225 result_type
1226 >::type
1227 __lshift(result_type __x) {return (__x << __count) & _Max;}
1228
1229 template <size_t __count>
1230 static
1231 typename enable_if
1232 <
1233 (__count >= __w),
1234 result_type
1235 >::type
1236 __lshift(result_type __x) {return result_type(0);}
1237
1238 template <size_t __count>
1239 static
1240 typename enable_if
1241 <
1242 __count < _Dt,
1243 result_type
1244 >::type
1245 __rshift(result_type __x) {return __x >> __count;}
1246
1247 template <size_t __count>
1248 static
1249 typename enable_if
1250 <
1251 (__count >= _Dt),
1252 result_type
1253 >::type
1254 __rshift(result_type __x) {return result_type(0);}
1255};
1256
1257template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
1258 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
1259 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
1260void
1261mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b,
1262 __t, __c, __l, __f>::seed(result_type __sd)
1263{ // __w >= 2
1264 __x_[0] = __sd & _Max;
1265 for (size_t __i = 1; __i < __n; ++__i)
1266 __x_[__i] = (__f * (__x_[__i-1] ^ __rshift<__w - 2>(__x_[__i-1])) + __i) & _Max;
1267 __i_ = 0;
1268}
1269
1270template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
1271 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
1272 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
1273template<class _Sseq>
1274void
1275mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b,
1276 __t, __c, __l, __f>::__seed(_Sseq& __q, integral_constant<unsigned, 1>)
1277{
1278 const unsigned __k = 1;
1279 uint32_t __ar[__n * __k];
1280 __q.generate(__ar, __ar + __n * __k);
1281 for (size_t __i = 0; __i < __n; ++__i)
1282 __x_[__i] = static_cast<result_type>(__ar[__i] & _Max);
1283 const result_type __mask = __r == _Dt ? result_type(~0) :
1284 (result_type(1) << __r) - result_type(1);
1285 __i_ = 0;
1286 if ((__x_[0] & ~__mask) == 0)
1287 {
1288 for (size_t __i = 1; __i < __n; ++__i)
1289 if (__x_[__i] != 0)
1290 return;
1291 __x_[0] = _Max;
1292 }
1293}
1294
1295template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
1296 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
1297 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
1298template<class _Sseq>
1299void
1300mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b,
1301 __t, __c, __l, __f>::__seed(_Sseq& __q, integral_constant<unsigned, 2>)
1302{
1303 const unsigned __k = 2;
1304 uint32_t __ar[__n * __k];
1305 __q.generate(__ar, __ar + __n * __k);
1306 for (size_t __i = 0; __i < __n; ++__i)
1307 __x_[__i] = static_cast<result_type>(
1308 (__ar[2 * __i] + ((uint64_t)__ar[2 * __i + 1] << 32)) & _Max);
1309 const result_type __mask = __r == _Dt ? result_type(~0) :
1310 (result_type(1) << __r) - result_type(1);
1311 __i_ = 0;
1312 if ((__x_[0] & ~__mask) == 0)
1313 {
1314 for (size_t __i = 1; __i < __n; ++__i)
1315 if (__x_[__i] != 0)
1316 return;
1317 __x_[0] = _Max;
1318 }
1319}
1320
1321template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
1322 _UIntType __a, size_t __u, _UIntType __d, size_t __s,
1323 _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
1324_UIntType
1325mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b,
1326 __t, __c, __l, __f>::operator()()
1327{
1328 const size_t __j = (__i_ + 1) % __n;
1329 const result_type __mask = __r == _Dt ? result_type(~0) :
1330 (result_type(1) << __r) - result_type(1);
1331 const result_type _Y = (__x_[__i_] & ~__mask) | (__x_[__j] & __mask);
1332 const size_t __k = (__i_ + __m) % __n;
1333 __x_[__i_] = __x_[__k] ^ __rshift<1>(_Y) ^ (__a * (_Y & 1));
1334 result_type __z = __x_[__i_] ^ (__rshift<__u>(__x_[__i_]) & __d);
1335 __i_ = __j;
1336 __z ^= __lshift<__s>(__z) & __b;
1337 __z ^= __lshift<__t>(__z) & __c;
1338 return __z ^ __rshift<__l>(__z);
1339}
1340
1341template <class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
1342 _UI _A, size_t _U, _UI _D, size_t _S,
1343 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
1344bool
1345operator==(const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1346 _B, _T, _C, _L, _F>& __x,
1347 const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1348 _B, _T, _C, _L, _F>& __y)
1349{
1350 if (__x.__i_ == __y.__i_)
1351 return _STD::equal(__x.__x_, __x.__x_ + _N, __y.__x_);
1352 if (__x.__i_ == 0 || __y.__i_ == 0)
1353 {
1354 size_t __j = _STD::min(_N - __x.__i_, _N - __y.__i_);
1355 if (!_STD::equal(__x.__x_ + __x.__i_, __x.__x_ + __x.__i_ + __j,
1356 __y.__x_ + __y.__i_))
1357 return false;
1358 if (__x.__i_ == 0)
1359 return _STD::equal(__x.__x_ + __j, __x.__x_ + _N, __y.__x_);
1360 return _STD::equal(__x.__x_, __x.__x_ + (_N - __j), __y.__x_ + __j);
1361 }
1362 if (__x.__i_ < __y.__i_)
1363 {
1364 size_t __j = _N - __y.__i_;
1365 if (!_STD::equal(__x.__x_ + __x.__i_, __x.__x_ + (__x.__i_ + __j),
1366 __y.__x_ + __y.__i_))
1367 return false;
1368 if (!_STD::equal(__x.__x_ + (__x.__i_ + __j), __x.__x_ + _N,
1369 __y.__x_))
1370 return false;
1371 return _STD::equal(__x.__x_, __x.__x_ + __x.__i_,
1372 __y.__x_ + (_N - (__x.__i_ + __j)));
1373 }
1374 size_t __j = _N - __x.__i_;
1375 if (!_STD::equal(__y.__x_ + __y.__i_, __y.__x_ + (__y.__i_ + __j),
1376 __x.__x_ + __x.__i_))
1377 return false;
1378 if (!_STD::equal(__y.__x_ + (__y.__i_ + __j), __y.__x_ + _N,
1379 __x.__x_))
1380 return false;
1381 return _STD::equal(__y.__x_, __y.__x_ + __y.__i_,
1382 __x.__x_ + (_N - (__y.__i_ + __j)));
1383}
1384
1385template <class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
1386 _UI _A, size_t _U, _UI _D, size_t _S,
1387 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
1388inline
1389bool
1390operator!=(const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1391 _B, _T, _C, _L, _F>& __x,
1392 const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1393 _B, _T, _C, _L, _F>& __y)
1394{
1395 return !(__x == __y);
1396}
1397
1398template <class _CharT, class _Traits,
1399 class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
1400 _UI _A, size_t _U, _UI _D, size_t _S,
1401 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
1402basic_ostream<_CharT, _Traits>&
1403operator<<(basic_ostream<_CharT, _Traits>& __os,
1404 const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1405 _B, _T, _C, _L, _F>& __x)
1406{
1407 __save_flags<_CharT, _Traits> _(__os);
1408 __os.flags(ios_base::dec | ios_base::left);
1409 _CharT __sp = __os.widen(' ');
1410 __os.fill(__sp);
1411 __os << __x.__x_[__x.__i_];
1412 for (size_t __j = __x.__i_ + 1; __j < _N; ++__j)
1413 __os << __sp << __x.__x_[__j];
1414 for (size_t __j = 0; __j < __x.__i_; ++__j)
1415 __os << __sp << __x.__x_[__j];
1416 return __os;
1417}
1418
1419template <class _CharT, class _Traits,
1420 class _UI, size_t _W, size_t _N, size_t _M, size_t _R,
1421 _UI _A, size_t _U, _UI _D, size_t _S,
1422 _UI _B, size_t _T, _UI _C, size_t _L, _UI _F>
1423basic_istream<_CharT, _Traits>&
1424operator>>(basic_istream<_CharT, _Traits>& __is,
1425 mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S,
1426 _B, _T, _C, _L, _F>& __x)
1427{
1428 __save_flags<_CharT, _Traits> _(__is);
1429 __is.flags(ios_base::dec | ios_base::skipws);
1430 _UI __t[_N];
1431 for (size_t __i = 0; __i < _N; ++__i)
1432 __is >> __t[__i];
1433 if (!__is.fail())
1434 {
1435 for (size_t __i = 0; __i < _N; ++__i)
1436 __x.__x_[__i] = __t[__i];
1437 __x.__i_ = 0;
1438 }
1439 return __is;
1440}
1441
1442typedef mersenne_twister_engine<uint_fast32_t, 32, 624, 397, 31,
1443 0x9908b0df, 11, 0xffffffff,
1444 7, 0x9d2c5680,
1445 15, 0xefc60000,
1446 18, 1812433253> mt19937;
1447typedef mersenne_twister_engine<uint_fast64_t, 64, 312, 156, 31,
1448 0xb5026f5aa96619e9ULL, 29, 0x5555555555555555ULL,
1449 17, 0x71d67fffeda60000ULL,
1450 37, 0xfff7eee000000000ULL,
1451 43, 6364136223846793005ULL> mt19937_64;
1452
1453// subtract_with_carry_engine
1454
1455template<class _UIntType, size_t __w, size_t __s, size_t __r>
1456class subtract_with_carry_engine;
1457
1458template<class _UI, size_t _W, size_t _S, size_t _R>
1459bool
1460operator==(
1461 const subtract_with_carry_engine<_UI, _W, _S, _R>& __x,
1462 const subtract_with_carry_engine<_UI, _W, _S, _R>& __y);
1463
1464template<class _UI, size_t _W, size_t _S, size_t _R>
1465bool
1466operator!=(
1467 const subtract_with_carry_engine<_UI, _W, _S, _R>& __x,
1468 const subtract_with_carry_engine<_UI, _W, _S, _R>& __y);
1469
1470template <class _CharT, class _Traits,
1471 class _UI, size_t _W, size_t _S, size_t _R>
1472basic_ostream<_CharT, _Traits>&
1473operator<<(basic_ostream<_CharT, _Traits>& __os,
1474 const subtract_with_carry_engine<_UI, _W, _S, _R>& __x);
1475
1476template <class _CharT, class _Traits,
1477 class _UI, size_t _W, size_t _S, size_t _R>
1478basic_istream<_CharT, _Traits>&
1479operator>>(basic_istream<_CharT, _Traits>& __is,
1480 subtract_with_carry_engine<_UI, _W, _S, _R>& __x);
1481
1482template<class _UIntType, size_t __w, size_t __s, size_t __r>
1483class subtract_with_carry_engine
1484{
1485public:
1486 // types
1487 typedef _UIntType result_type;
1488
1489private:
1490 result_type __x_[__r];
1491 result_type __c_;
1492 size_t __i_;
1493
1494 static const result_type _Dt = numeric_limits<result_type>::digits;
1495 static_assert( 0 < __w, "subtract_with_carry_engine invalid parameters");
1496 static_assert(__w <= _Dt, "subtract_with_carry_engine invalid parameters");
1497 static_assert( 0 < __s, "subtract_with_carry_engine invalid parameters");
1498 static_assert(__s < __r, "subtract_with_carry_engine invalid parameters");
1499public:
1500 static const result_type _Min = 0;
1501 static const result_type _Max = __w == _Dt ? result_type(~0) :
1502 (result_type(1) << __w) - result_type(1);
1503 static_assert(_Min < _Max, "subtract_with_carry_engine invalid parameters");
1504
1505 // engine characteristics
1506 static const/*expr*/ size_t word_size = __w;
1507 static const/*expr*/ size_t short_lag = __s;
1508 static const/*expr*/ size_t long_lag = __r;
1509 static const/*expr*/ result_type min() { return _Min; }
1510 static const/*expr*/ result_type max() { return _Max; }
1511 static const/*expr*/ result_type default_seed = 19780503u;
1512
1513 // constructors and seeding functions
1514 explicit subtract_with_carry_engine(result_type __sd = default_seed)
1515 {seed(__sd);}
1516 template<class _Sseq> explicit subtract_with_carry_engine(_Sseq& __q)
1517 {seed(__q);}
1518 void seed(result_type __sd = default_seed)
1519 {seed(__sd, integral_constant<unsigned, 1 + (__w - 1) / 32>());}
1520 template<class _Sseq>
1521 typename enable_if
1522 <
1523 !is_convertible<_Sseq, result_type>::value,
1524 void
1525 >::type
1526 seed(_Sseq& __q)
1527 {__seed(__q, integral_constant<unsigned, 1 + (__w - 1) / 32>());}
1528
1529 // generating functions
1530 result_type operator()();
1531 void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
1532
1533 template<class _UI, size_t _W, size_t _S, size_t _R>
1534 friend
1535 bool
1536 operator==(
1537 const subtract_with_carry_engine<_UI, _W, _S, _R>& __x,
1538 const subtract_with_carry_engine<_UI, _W, _S, _R>& __y);
1539
1540 template<class _UI, size_t _W, size_t _S, size_t _R>
1541 friend
1542 bool
1543 operator!=(
1544 const subtract_with_carry_engine<_UI, _W, _S, _R>& __x,
1545 const subtract_with_carry_engine<_UI, _W, _S, _R>& __y);
1546
1547 template <class _CharT, class _Traits,
1548 class _UI, size_t _W, size_t _S, size_t _R>
1549 friend
1550 basic_ostream<_CharT, _Traits>&
1551 operator<<(basic_ostream<_CharT, _Traits>& __os,
1552 const subtract_with_carry_engine<_UI, _W, _S, _R>& __x);
1553
1554 template <class _CharT, class _Traits,
1555 class _UI, size_t _W, size_t _S, size_t _R>
1556 friend
1557 basic_istream<_CharT, _Traits>&
1558 operator>>(basic_istream<_CharT, _Traits>& __is,
1559 subtract_with_carry_engine<_UI, _W, _S, _R>& __x);
1560
1561private:
1562
1563 void seed(result_type __sd, integral_constant<unsigned, 1>);
1564 void seed(result_type __sd, integral_constant<unsigned, 2>);
1565 template<class _Sseq>
1566 void __seed(_Sseq& __q, integral_constant<unsigned, 1>);
1567 template<class _Sseq>
1568 void __seed(_Sseq& __q, integral_constant<unsigned, 2>);
1569};
1570
1571template<class _UIntType, size_t __w, size_t __s, size_t __r>
1572void
1573subtract_with_carry_engine<_UIntType, __w, __s, __r>::seed(result_type __sd,
1574 integral_constant<unsigned, 1>)
1575{
1576 linear_congruential_engine<result_type, 40014u, 0u, 2147483563u>
1577 __e(__sd == 0u ? default_seed : __sd);
1578 for (size_t __i = 0; __i < __r; ++__i)
1579 __x_[__i] = static_cast<result_type>(__e() & _Max);
1580 __c_ = __x_[__r-1] == 0;
1581 __i_ = 0;
1582}
1583
1584template<class _UIntType, size_t __w, size_t __s, size_t __r>
1585void
1586subtract_with_carry_engine<_UIntType, __w, __s, __r>::seed(result_type __sd,
1587 integral_constant<unsigned, 2>)
1588{
1589 linear_congruential_engine<result_type, 40014u, 0u, 2147483563u>
1590 __e(__sd == 0u ? default_seed : __sd);
1591 for (size_t __i = 0; __i < __r; ++__i)
1592 __x_[__i] = static_cast<result_type>(
1593 (__e() + ((uint64_t)__e() << 32)) & _Max);
1594 __c_ = __x_[__r-1] == 0;
1595 __i_ = 0;
1596}
1597
1598template<class _UIntType, size_t __w, size_t __s, size_t __r>
1599template<class _Sseq>
1600void
1601subtract_with_carry_engine<_UIntType, __w, __s, __r>::__seed(_Sseq& __q,
1602 integral_constant<unsigned, 1>)
1603{
1604 const unsigned __k = 1;
1605 uint32_t __ar[__r * __k];
1606 __q.generate(__ar, __ar + __r * __k);
1607 for (size_t __i = 0; __i < __r; ++__i)
1608 __x_[__i] = static_cast<result_type>(__ar[__i] & _Max);
1609 __c_ = __x_[__r-1] == 0;
1610 __i_ = 0;
1611}
1612
1613template<class _UIntType, size_t __w, size_t __s, size_t __r>
1614template<class _Sseq>
1615void
1616subtract_with_carry_engine<_UIntType, __w, __s, __r>::__seed(_Sseq& __q,
1617 integral_constant<unsigned, 2>)
1618{
1619 const unsigned __k = 2;
1620 uint32_t __ar[__r * __k];
1621 __q.generate(__ar, __ar + __r * __k);
1622 for (size_t __i = 0; __i < __r; ++__i)
1623 __x_[__i] = static_cast<result_type>(
1624 (__ar[2 * __i] + ((uint64_t)__ar[2 * __i + 1] << 32)) & _Max);
1625 __c_ = __x_[__r-1] == 0;
1626 __i_ = 0;
1627}
1628
1629template<class _UIntType, size_t __w, size_t __s, size_t __r>
1630_UIntType
1631subtract_with_carry_engine<_UIntType, __w, __s, __r>::operator()()
1632{
1633 const result_type& __xs = __x_[(__i_ + (__r - __s)) % __r];
1634 result_type& __xr = __x_[__i_];
1635 result_type __new_c = __c_ == 0 ? __xs < __xr : __xs != 0 ? __xs <= __xr : 1;
1636 __xr = (__xs - __xr - __c_) & _Max;
1637 __c_ = __new_c;
1638 __i_ = (__i_ + 1) % __r;
1639 return __xr;
1640}
1641
1642template<class _UI, size_t _W, size_t _S, size_t _R>
1643bool
1644operator==(
1645 const subtract_with_carry_engine<_UI, _W, _S, _R>& __x,
1646 const subtract_with_carry_engine<_UI, _W, _S, _R>& __y)
1647{
1648 if (__x.__c_ != __y.__c_)
1649 return false;
1650 if (__x.__i_ == __y.__i_)
1651 return _STD::equal(__x.__x_, __x.__x_ + _R, __y.__x_);
1652 if (__x.__i_ == 0 || __y.__i_ == 0)
1653 {
1654 size_t __j = _STD::min(_R - __x.__i_, _R - __y.__i_);
1655 if (!_STD::equal(__x.__x_ + __x.__i_, __x.__x_ + __x.__i_ + __j,
1656 __y.__x_ + __y.__i_))
1657 return false;
1658 if (__x.__i_ == 0)
1659 return _STD::equal(__x.__x_ + __j, __x.__x_ + _R, __y.__x_);
1660 return _STD::equal(__x.__x_, __x.__x_ + (_R - __j), __y.__x_ + __j);
1661 }
1662 if (__x.__i_ < __y.__i_)
1663 {
1664 size_t __j = _R - __y.__i_;
1665 if (!_STD::equal(__x.__x_ + __x.__i_, __x.__x_ + (__x.__i_ + __j),
1666 __y.__x_ + __y.__i_))
1667 return false;
1668 if (!_STD::equal(__x.__x_ + (__x.__i_ + __j), __x.__x_ + _R,
1669 __y.__x_))
1670 return false;
1671 return _STD::equal(__x.__x_, __x.__x_ + __x.__i_,
1672 __y.__x_ + (_R - (__x.__i_ + __j)));
1673 }
1674 size_t __j = _R - __x.__i_;
1675 if (!_STD::equal(__y.__x_ + __y.__i_, __y.__x_ + (__y.__i_ + __j),
1676 __x.__x_ + __x.__i_))
1677 return false;
1678 if (!_STD::equal(__y.__x_ + (__y.__i_ + __j), __y.__x_ + _R,
1679 __x.__x_))
1680 return false;
1681 return _STD::equal(__y.__x_, __y.__x_ + __y.__i_,
1682 __x.__x_ + (_R - (__y.__i_ + __j)));
1683}
1684
1685template<class _UI, size_t _W, size_t _S, size_t _R>
1686inline
1687bool
1688operator!=(
1689 const subtract_with_carry_engine<_UI, _W, _S, _R>& __x,
1690 const subtract_with_carry_engine<_UI, _W, _S, _R>& __y)
1691{
1692 return !(__x == __y);
1693}
1694
1695template <class _CharT, class _Traits,
1696 class _UI, size_t _W, size_t _S, size_t _R>
1697basic_ostream<_CharT, _Traits>&
1698operator<<(basic_ostream<_CharT, _Traits>& __os,
1699 const subtract_with_carry_engine<_UI, _W, _S, _R>& __x)
1700{
1701 __save_flags<_CharT, _Traits> _(__os);
1702 __os.flags(ios_base::dec | ios_base::left);
1703 _CharT __sp = __os.widen(' ');
1704 __os.fill(__sp);
1705 __os << __x.__x_[__x.__i_];
1706 for (size_t __j = __x.__i_ + 1; __j < _R; ++__j)
1707 __os << __sp << __x.__x_[__j];
1708 for (size_t __j = 0; __j < __x.__i_; ++__j)
1709 __os << __sp << __x.__x_[__j];
1710 __os << __sp << __x.__c_;
1711 return __os;
1712}
1713
1714template <class _CharT, class _Traits,
1715 class _UI, size_t _W, size_t _S, size_t _R>
1716basic_istream<_CharT, _Traits>&
1717operator>>(basic_istream<_CharT, _Traits>& __is,
1718 subtract_with_carry_engine<_UI, _W, _S, _R>& __x)
1719{
1720 __save_flags<_CharT, _Traits> _(__is);
1721 __is.flags(ios_base::dec | ios_base::skipws);
1722 _UI __t[_R+1];
1723 for (size_t __i = 0; __i < _R+1; ++__i)
1724 __is >> __t[__i];
1725 if (!__is.fail())
1726 {
1727 for (size_t __i = 0; __i < _R; ++__i)
1728 __x.__x_[__i] = __t[__i];
1729 __x.__c_ = __t[_R];
1730 __x.__i_ = 0;
1731 }
1732 return __is;
1733}
1734
1735typedef subtract_with_carry_engine<uint_fast32_t, 24, 10, 24> ranlux24_base;
1736typedef subtract_with_carry_engine<uint_fast64_t, 48, 5, 12> ranlux48_base;
1737
1738// discard_block_engine
1739
1740template<class _Engine, size_t __p, size_t __r>
1741class discard_block_engine
1742{
1743 _Engine __e_;
1744 int __n_;
1745
1746 static_assert( 0 < __r, "discard_block_engine invalid parameters");
1747 static_assert(__r <= __p, "discard_block_engine invalid parameters");
1748public:
1749 // types
1750 typedef typename _Engine::result_type result_type;
1751
1752 // engine characteristics
1753 static const/*expr*/ size_t block_size = __p;
1754 static const/*expr*/ size_t used_block = __r;
1755
1756 // Temporary work around for lack of constexpr
1757 static const result_type _Min = _Engine::_Min;
1758 static const result_type _Max = _Engine::_Max;
1759
1760 static const/*expr*/ result_type min() { return _Engine::min(); }
1761 static const/*expr*/ result_type max() { return _Engine::max(); }
1762
1763 // constructors and seeding functions
1764 discard_block_engine() : __n_(0) {}
1765// explicit discard_block_engine(const _Engine& __e);
1766// explicit discard_block_engine(_Engine&& __e);
1767 explicit discard_block_engine(result_type __sd) : __e_(__sd), __n_(0) {}
1768 template<class _Sseq> explicit discard_block_engine(_Sseq& __q)
1769 : __e_(__q), __n_(0) {}
1770 void seed() {__e_.seed(); __n_ = 0;}
1771 void seed(result_type __sd) {__e_.seed(__sd); __n_ = 0;}
1772 template<class _Sseq> void seed(_Sseq& __q) {__e_.seed(__q); __n_ = 0;}
1773
1774 // generating functions
1775 result_type operator()();
1776 void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
1777
1778 // property functions
1779 const _Engine& base() const {return __e_;}
1780
1781 template<class _Eng, size_t _P, size_t _R>
1782 friend
1783 bool
1784 operator==(
1785 const discard_block_engine<_Eng, _P, _R>& __x,
1786 const discard_block_engine<_Eng, _P, _R>& __y);
1787
1788 template<class _Eng, size_t _P, size_t _R>
1789 friend
1790 bool
1791 operator!=(
1792 const discard_block_engine<_Eng, _P, _R>& __x,
1793 const discard_block_engine<_Eng, _P, _R>& __y);
1794
1795 template <class _CharT, class _Traits,
1796 class _Eng, size_t _P, size_t _R>
1797 friend
1798 basic_ostream<_CharT, _Traits>&
1799 operator<<(basic_ostream<_CharT, _Traits>& __os,
1800 const discard_block_engine<_Eng, _P, _R>& __x);
1801
1802 template <class _CharT, class _Traits,
1803 class _Eng, size_t _P, size_t _R>
1804 friend
1805 basic_istream<_CharT, _Traits>&
1806 operator>>(basic_istream<_CharT, _Traits>& __is,
1807 discard_block_engine<_Eng, _P, _R>& __x);
1808};
1809
1810template<class _Engine, size_t __p, size_t __r>
1811typename discard_block_engine<_Engine, __p, __r>::result_type
1812discard_block_engine<_Engine, __p, __r>::operator()()
1813{
1814 if (__n_ >= __r)
1815 {
1816 __e_.discard(__p - __r);
1817 __n_ = 0;
1818 }
1819 ++__n_;
1820 return __e_();
1821}
1822
1823template<class _Eng, size_t _P, size_t _R>
1824inline
1825bool
1826operator==(const discard_block_engine<_Eng, _P, _R>& __x,
1827 const discard_block_engine<_Eng, _P, _R>& __y)
1828{
1829 return __x.__n_ == __y.__n_ && __x.__e_ == __y.__e_;
1830}
1831
1832template<class _Eng, size_t _P, size_t _R>
1833inline
1834bool
1835operator!=(const discard_block_engine<_Eng, _P, _R>& __x,
1836 const discard_block_engine<_Eng, _P, _R>& __y)
1837{
1838 return !(__x == __y);
1839}
1840
1841template <class _CharT, class _Traits,
1842 class _Eng, size_t _P, size_t _R>
1843basic_ostream<_CharT, _Traits>&
1844operator<<(basic_ostream<_CharT, _Traits>& __os,
1845 const discard_block_engine<_Eng, _P, _R>& __x)
1846{
1847 __save_flags<_CharT, _Traits> _(__os);
1848 __os.flags(ios_base::dec | ios_base::left);
1849 _CharT __sp = __os.widen(' ');
1850 __os.fill(__sp);
1851 return __os << __x.__e_ << __sp << __x.__n_;
1852}
1853
1854template <class _CharT, class _Traits,
1855 class _Eng, size_t _P, size_t _R>
1856basic_istream<_CharT, _Traits>&
1857operator>>(basic_istream<_CharT, _Traits>& __is,
1858 discard_block_engine<_Eng, _P, _R>& __x)
1859{
1860 __save_flags<_CharT, _Traits> _(__is);
1861 __is.flags(ios_base::dec | ios_base::skipws);
1862 _Eng __e;
1863 int __n;
1864 __is >> __e >> __n;
1865 if (!__is.fail())
1866 {
1867 __x.__e_ = __e;
1868 __x.__n_ = __n;
1869 }
1870 return __is;
1871}
1872
1873typedef discard_block_engine<ranlux24_base, 223, 23> ranlux24;
1874typedef discard_block_engine<ranlux48_base, 389, 11> ranlux48;
1875
1876// independent_bits_engine
1877
1878template <unsigned long long _X, size_t _R>
1879struct __log2_imp
1880{
1881 static const size_t value = _X & ((unsigned long long)(1) << _R) ? _R
1882 : __log2_imp<_X, _R - 1>::value;
1883};
1884
1885template <unsigned long long _X>
1886struct __log2_imp<_X, 0>
1887{
1888 static const size_t value = 0;
1889};
1890
1891template <size_t _R>
1892struct __log2_imp<0, _R>
1893{
1894 static const size_t value = _R + 1;
1895};
1896
1897template <class _UI, _UI _X>
1898struct __log2
1899{
1900 static const size_t value = __log2_imp<_X,
1901 sizeof(_UI) * __CHAR_BIT__ - 1>::value;
1902};
1903
1904template<class _Engine, size_t __w, class _UIntType>
1905class independent_bits_engine
1906{
1907 template <class _UI, _UI _R0, size_t _W, size_t _M>
1908 class __get_n
1909 {
1910 static const size_t _Dt = numeric_limits<_UI>::digits;
1911 static const size_t _N = _W / _M + (_W % _M != 0);
1912 static const size_t _W0 = _W / _N;
1913 static const _UI _Y0 = _W0 >= _Dt ? 0 : (_R0 >> _W0) << _W0;
1914 public:
1915 static const size_t value = _R0 - _Y0 > _Y0 / _N ? _N + 1 : _N;
1916 };
1917public:
1918 // types
1919 typedef _UIntType result_type;
1920
1921private:
1922 _Engine __e_;
1923
1924 static const result_type _Dt = numeric_limits<result_type>::digits;
1925 static_assert( 0 < __w, "independent_bits_engine invalid parameters");
1926 static_assert(__w <= _Dt, "independent_bits_engine invalid parameters");
1927
1928 typedef typename _Engine::result_type _Engine_result_type;
1929 typedef typename conditional
1930 <
1931 sizeof(_Engine_result_type) <= sizeof(result_type),
1932 result_type,
1933 _Engine_result_type
1934 >::type _Working_result_type;
1935 // Temporary work around for lack of constexpr
1936 static const _Working_result_type _R = _Engine::_Max - _Engine::_Min
1937 + _Working_result_type(1);
1938 static const size_t __m = __log2<_Working_result_type, _R>::value;
1939 static const size_t __n = __get_n<_Working_result_type, _R, __w, __m>::value;
1940 static const size_t __w0 = __w / __n;
1941 static const size_t __n0 = __n - __w % __n;
1942 static const size_t _WDt = numeric_limits<_Working_result_type>::digits;
1943 static const size_t _EDt = numeric_limits<_Engine_result_type>::digits;
1944 static const _Working_result_type __y0 = __w0 >= _WDt ? 0 :
1945 (_R >> __w0) << __w0;
1946 static const _Working_result_type __y1 = __w0 >= _WDt - 1 ? 0 :
1947 (_R >> (__w0+1)) << (__w0+1);
1948 static const _Engine_result_type __mask0 = __w0 > 0 ?
1949 _Engine_result_type(~0) >> (_EDt - __w0) :
1950 _Engine_result_type(0);
1951 static const _Engine_result_type __mask1 = __w0 < _EDt - 1 ?
1952 _Engine_result_type(~0) >> (_EDt - (__w0 + 1)) :
1953 _Engine_result_type(~0);
1954public:
1955 static const result_type _Min = 0;
1956 static const result_type _Max = __w == _Dt ? result_type(~0) :
1957 (result_type(1) << __w) - result_type(1);
1958 static_assert(_Min < _Max, "independent_bits_engine invalid parameters");
1959
1960 // engine characteristics
1961 static const/*expr*/ result_type min() { return _Min; }
1962 static const/*expr*/ result_type max() { return _Max; }
1963
1964 // constructors and seeding functions
1965 independent_bits_engine() {}
1966// explicit independent_bits_engine(const _Engine& __e);
1967// explicit independent_bits_engine(_Engine&& __e);
1968 explicit independent_bits_engine(result_type __sd) : __e_(__sd) {}
1969 template<class _Sseq> explicit independent_bits_engine(_Sseq& __q)
1970 : __e_(__q) {}
1971 void seed() {__e_.seed();}
1972 void seed(result_type __sd) {__e_.seed(__sd);}
1973 template<class _Sseq> void seed(_Sseq& __q) {__e_.seed(__q);}
1974
1975 // generating functions
1976 result_type operator()() {return __eval(integral_constant<bool, _R != 0>());}
1977 void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
1978
1979 // property functions
1980 const _Engine& base() const {return __e_;}
1981
1982 template<class _Eng, size_t _W, class _UI>
1983 friend
1984 bool
1985 operator==(
1986 const independent_bits_engine<_Eng, _W, _UI>& __x,
1987 const independent_bits_engine<_Eng, _W, _UI>& __y);
1988
1989 template<class _Eng, size_t _W, class _UI>
1990 friend
1991 bool
1992 operator!=(
1993 const independent_bits_engine<_Eng, _W, _UI>& __x,
1994 const independent_bits_engine<_Eng, _W, _UI>& __y);
1995
1996 template <class _CharT, class _Traits,
1997 class _Eng, size_t _W, class _UI>
1998 friend
1999 basic_ostream<_CharT, _Traits>&
2000 operator<<(basic_ostream<_CharT, _Traits>& __os,
2001 const independent_bits_engine<_Eng, _W, _UI>& __x);
2002
2003 template <class _CharT, class _Traits,
2004 class _Eng, size_t _W, class _UI>
2005 friend
2006 basic_istream<_CharT, _Traits>&
2007 operator>>(basic_istream<_CharT, _Traits>& __is,
2008 independent_bits_engine<_Eng, _W, _UI>& __x);
2009
2010private:
2011 result_type __eval(false_type);
2012 result_type __eval(true_type);
2013
2014 template <size_t __count>
2015 static
2016 typename enable_if
2017 <
2018 __count < _Dt,
2019 result_type
2020 >::type
2021 __lshift(result_type __x) {return __x << __count;}
2022
2023 template <size_t __count>
2024 static
2025 typename enable_if
2026 <
2027 (__count >= _Dt),
2028 result_type
2029 >::type
2030 __lshift(result_type __x) {return result_type(0);}
2031};
2032
2033template<class _Engine, size_t __w, class _UIntType>
2034inline
2035_UIntType
2036independent_bits_engine<_Engine, __w, _UIntType>::__eval(false_type)
2037{
2038 return static_cast<result_type>(__e_() & __mask0);
2039}
2040
2041template<class _Engine, size_t __w, class _UIntType>
2042_UIntType
2043independent_bits_engine<_Engine, __w, _UIntType>::__eval(true_type)
2044{
2045 result_type _S = 0;
2046 for (size_t __k = 0; __k < __n0; ++__k)
2047 {
2048 _Engine_result_type __u;
2049 do
2050 {
2051 __u = __e_() - _Engine::min();
2052 } while (__u >= __y0);
2053 _S = static_cast<result_type>(__lshift<__w0>(_S) + (__u & __mask0));
2054 }
2055 for (size_t __k = __n0; __k < __n; ++__k)
2056 {
2057 _Engine_result_type __u;
2058 do
2059 {
2060 __u = __e_() - _Engine::min();
2061 } while (__u >= __y1);
2062 _S = static_cast<result_type>(__lshift<__w0+1>(_S) + (__u & __mask1));
2063 }
2064 return _S;
2065}
2066
2067template<class _Eng, size_t _W, class _UI>
2068inline
2069bool
2070operator==(
2071 const independent_bits_engine<_Eng, _W, _UI>& __x,
2072 const independent_bits_engine<_Eng, _W, _UI>& __y)
2073{
2074 return __x.base() == __y.base();
2075}
2076
2077template<class _Eng, size_t _W, class _UI>
2078inline
2079bool
2080operator!=(
2081 const independent_bits_engine<_Eng, _W, _UI>& __x,
2082 const independent_bits_engine<_Eng, _W, _UI>& __y)
2083{
2084 return !(__x == __y);
2085}
2086
2087template <class _CharT, class _Traits,
2088 class _Eng, size_t _W, class _UI>
2089basic_ostream<_CharT, _Traits>&
2090operator<<(basic_ostream<_CharT, _Traits>& __os,
2091 const independent_bits_engine<_Eng, _W, _UI>& __x)
2092{
2093 return __os << __x.base();
2094}
2095
2096template <class _CharT, class _Traits,
2097 class _Eng, size_t _W, class _UI>
2098basic_istream<_CharT, _Traits>&
2099operator>>(basic_istream<_CharT, _Traits>& __is,
2100 independent_bits_engine<_Eng, _W, _UI>& __x)
2101{
2102 _Eng __e;
2103 __is >> __e;
2104 if (!__is.fail())
2105 __x.__e_ = __e;
2106 return __is;
2107}
2108
2109// shuffle_order_engine
2110
2111template <uint64_t _Xp, uint64_t _Yp>
2112struct __ugcd
2113{
2114 static const uint64_t value = __ugcd<_Yp, _Xp % _Yp>::value;
2115};
2116
2117template <uint64_t _Xp>
2118struct __ugcd<_Xp, 0>
2119{
2120 static const uint64_t value = _Xp;
2121};
2122
2123template <uint64_t _N, uint64_t _D>
2124class __uratio
2125{
2126 static_assert(_D != 0, "__uratio divide by 0");
2127 static const uint64_t __gcd = __ugcd<_N, _D>::value;
2128public:
2129 static const uint64_t num = _N / __gcd;
2130 static const uint64_t den = _D / __gcd;
2131
2132 typedef __uratio<num, den> type;
2133};
2134
2135template<class _Engine, size_t __k>
2136class shuffle_order_engine
2137{
2138 static_assert(0 < __k, "shuffle_order_engine invalid parameters");
2139public:
2140 // types
2141 typedef typename _Engine::result_type result_type;
2142
2143private:
2144 _Engine __e_;
2145 result_type _V_[__k];
2146 result_type _Y_;
2147
2148public:
2149 // engine characteristics
2150 static const/*expr*/ size_t table_size = __k;
2151
2152 static const result_type _Min = _Engine::_Min;
2153 static const result_type _Max = _Engine::_Max;
2154 static_assert(_Min < _Max, "shuffle_order_engine invalid parameters");
2155 static const/*expr*/ result_type min() { return _Min; }
2156 static const/*expr*/ result_type max() { return _Max; }
2157
2158 static const unsigned long long _R = _Max - _Min + 1ull;
2159
2160 // constructors and seeding functions
2161 shuffle_order_engine() {__init();}
2162// explicit shuffle_order_engine(const _Engine& __e);
2163// explicit shuffle_order_engine(_Engine&& e);
2164 explicit shuffle_order_engine(result_type __sd) : __e_(__sd) {__init();}
2165 template<class _Sseq> explicit shuffle_order_engine(_Sseq& __q)
2166 : __e_(__q) {__init();}
2167 void seed() {__e_.seed(); __init();}
2168 void seed(result_type __sd) {__e_.seed(__sd); __init();}
2169 template<class _Sseq> void seed(_Sseq& __q) {__e_.seed(__q); __init();}
2170
2171 // generating functions
2172 result_type operator()() {return __eval(integral_constant<bool, _R != 0>());}
2173 void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
2174
2175 // property functions
2176 const _Engine& base() const {return __e_;}
2177
2178private:
2179 template<class _Eng, size_t _K>
2180 friend
2181 bool
2182 operator==(
2183 const shuffle_order_engine<_Eng, _K>& __x,
2184 const shuffle_order_engine<_Eng, _K>& __y);
2185
2186 template<class _Eng, size_t _K>
2187 friend
2188 bool
2189 operator!=(
2190 const shuffle_order_engine<_Eng, _K>& __x,
2191 const shuffle_order_engine<_Eng, _K>& __y);
2192
2193 template <class _CharT, class _Traits,
2194 class _Eng, size_t _K>
2195 friend
2196 basic_ostream<_CharT, _Traits>&
2197 operator<<(basic_ostream<_CharT, _Traits>& __os,
2198 const shuffle_order_engine<_Eng, _K>& __x);
2199
2200 template <class _CharT, class _Traits,
2201 class _Eng, size_t _K>
2202 friend
2203 basic_istream<_CharT, _Traits>&
2204 operator>>(basic_istream<_CharT, _Traits>& __is,
2205 shuffle_order_engine<_Eng, _K>& __x);
2206
2207 void __init()
2208 {
2209 for (size_t __i = 0; __i < __k; ++__i)
2210 _V_[__i] = __e_();
2211 _Y_ = __e_();
2212 }
2213
2214 result_type __eval(false_type) {return __eval2(integral_constant<bool, __k & 1>());}
2215 result_type __eval(true_type) {return __eval(__uratio<__k, _R>());}
2216
2217 result_type __eval2(false_type) {return __eval(__uratio<__k/2, 0x8000000000000000ull>());}
2218 result_type __eval2(true_type) {return __evalf<__k, 0>();}
2219
2220 template <uint64_t _N, uint64_t _D>
2221 typename enable_if
2222 <
2223 (__uratio<_N, _D>::num > 0xFFFFFFFFFFFFFFFFull / (_Max - _Min)),
2224 result_type
2225 >::type
2226 __eval(__uratio<_N, _D>)
2227 {return __evalf<__uratio<_N, _D>::num, __uratio<_N, _D>::den>();}
2228
2229 template <uint64_t _N, uint64_t _D>
2230 typename enable_if
2231 <
2232 __uratio<_N, _D>::num <= 0xFFFFFFFFFFFFFFFFull / (_Max - _Min),
2233 result_type
2234 >::type
2235 __eval(__uratio<_N, _D>)
2236 {
2237 const size_t __j = static_cast<size_t>(__uratio<_N, _D>::num * (_Y_ - _Min)
2238 / __uratio<_N, _D>::den);
2239 _Y_ = _V_[__j];
2240 _V_[__j] = __e_();
2241 return _Y_;
2242 }
2243
2244 template <uint64_t __n, uint64_t __d>
2245 result_type __evalf()
2246 {
2247 const double _F = __d == 0 ?
2248 __n / (2. * 0x8000000000000000ull) :
2249 __n / (double)__d;
2250 const size_t __j = static_cast<size_t>(_F * (_Y_ - _Min));
2251 _Y_ = _V_[__j];
2252 _V_[__j] = __e_();
2253 return _Y_;
2254 }
2255};
2256
2257template<class _Eng, size_t _K>
2258bool
2259operator==(
2260 const shuffle_order_engine<_Eng, _K>& __x,
2261 const shuffle_order_engine<_Eng, _K>& __y)
2262{
2263 return __x._Y_ == __y._Y_ && _STD::equal(__x._V_, __x._V_ + _K, __y._V_) &&
2264 __x.__e_ == __y.__e_;
2265}
2266
2267template<class _Eng, size_t _K>
2268inline
2269bool
2270operator!=(
2271 const shuffle_order_engine<_Eng, _K>& __x,
2272 const shuffle_order_engine<_Eng, _K>& __y)
2273{
2274 return !(__x == __y);
2275}
2276
2277template <class _CharT, class _Traits,
2278 class _Eng, size_t _K>
2279basic_ostream<_CharT, _Traits>&
2280operator<<(basic_ostream<_CharT, _Traits>& __os,
2281 const shuffle_order_engine<_Eng, _K>& __x)
2282{
2283 __save_flags<_CharT, _Traits> _(__os);
2284 __os.flags(ios_base::dec | ios_base::left);
2285 _CharT __sp = __os.widen(' ');
2286 __os.fill(__sp);
2287 __os << __x.__e_ << __sp << __x._V_[0];
2288 for (size_t __i = 1; __i < _K; ++__i)
2289 __os << __sp << __x._V_[__i];
2290 return __os << __sp << __x._Y_;
2291}
2292
2293template <class _CharT, class _Traits,
2294 class _Eng, size_t _K>
2295basic_istream<_CharT, _Traits>&
2296operator>>(basic_istream<_CharT, _Traits>& __is,
2297 shuffle_order_engine<_Eng, _K>& __x)
2298{
2299 typedef typename shuffle_order_engine<_Eng, _K>::result_type result_type;
2300 __save_flags<_CharT, _Traits> _(__is);
2301 __is.flags(ios_base::dec | ios_base::skipws);
2302 _Eng __e;
2303 result_type _V[_K+1];
2304 __is >> __e;
2305 for (size_t __i = 0; __i < _K+1; ++__i)
2306 __is >> _V[__i];
2307 if (!__is.fail())
2308 {
2309 __x.__e_ = __e;
2310 for (size_t __i = 0; __i < _K; ++__i)
2311 __x._V_[__i] = _V[__i];
2312 __x._Y_ = _V[_K];
2313 }
2314 return __is;
2315}
2316
2317typedef shuffle_order_engine<minstd_rand0, 256> knuth_b;
2318
2319// random_device
2320
2321class random_device
2322{
2323 int __f_;
2324public:
2325 // types
2326 typedef unsigned result_type;
2327
2328 // generator characteristics
2329 static const result_type _Min = 0;
2330 static const result_type _Max = 0xFFFFFFFFu;
2331
2332 static const/*expr*/ result_type min() { return _Min;}
2333 static const/*expr*/ result_type max() { return _Max;}
2334
2335 // constructors
2336 explicit random_device(const string& __token = "/dev/urandom");
2337 ~random_device();
2338
2339 // generating functions
2340 result_type operator()();
2341
2342 // property functions
2343 double entropy() const;
2344
2345private:
2346 // no copy functions
2347 random_device(const random_device&); // = delete;
2348 random_device& operator=(const random_device&); // = delete;
2349};
2350
2351// seed_seq
2352
2353class seed_seq
2354{
2355public:
2356 // types
2357 typedef uint32_t result_type;
2358
2359private:
2360 vector<result_type> __v_;
2361
2362 template<class _InputIterator>
2363 void init(_InputIterator __first, _InputIterator __last);
2364public:
2365 // constructors
2366 seed_seq() {}
2367 template<class _Tp>
2368 seed_seq(initializer_list<_Tp> __il) {init(__il.begin(), __il.end());}
2369
2370 template<class _InputIterator>
2371 seed_seq(_InputIterator __first, _InputIterator __last)
2372 {init(__first, __last);}
2373
2374 // generating functions
2375 template<class _RandomAccessIterator>
2376 void generate(_RandomAccessIterator __first, _RandomAccessIterator __last);
2377
2378 // property functions
2379 size_t size() const {return __v_.size();}
2380 template<class _OutputIterator>
2381 void param(_OutputIterator __dest) const
2382 {_STD::copy(__v_.begin(), __v_.end(), __dest);}
2383
2384private:
2385 // no copy functions
2386 seed_seq(const seed_seq&); // = delete;
2387 void operator=(const seed_seq&); // = delete;
2388
2389 static result_type _T(result_type __x) {return __x ^ (__x >> 27);}
2390};
2391
2392template<class _InputIterator>
2393void
2394seed_seq::init(_InputIterator __first, _InputIterator __last)
2395{
2396 for (_InputIterator __s = __first; __s != __last; ++__s)
2397 __v_.push_back(*__s & 0xFFFFFFFF);
2398}
2399
2400template<class _RandomAccessIterator>
2401void
2402seed_seq::generate(_RandomAccessIterator __first, _RandomAccessIterator __last)
2403{
2404 if (__first != __last)
2405 {
2406 _STD::fill(__first, __last, 0x8b8b8b8b);
2407 const size_t __n = static_cast<size_t>(__last - __first);
2408 const size_t __s = __v_.size();
2409 const size_t __t = (__n >= 623) ? 11
2410 : (__n >= 68) ? 7
2411 : (__n >= 39) ? 5
2412 : (__n >= 7) ? 3
2413 : (__n - 1) / 2;
2414 const size_t __p = (__n - __t) / 2;
2415 const size_t __q = __p + __t;
2416 const size_t __m = _STD::max(__s + 1, __n);
2417 // __k = 0;
2418 {
2419 result_type __r = 1664525 * _T(__first[0] ^ __first[__p]
2420 ^ __first[__n - 1]);
2421 __first[__p] += __r;
2422 __r += __s;
2423 __first[__q] += __r;
2424 __first[0] = __r;
2425 }
2426 for (size_t __k = 1; __k <= __s; ++__k)
2427 {
2428 const size_t __kmodn = __k % __n;
2429 const size_t __kpmodn = (__k + __p) % __n;
2430 result_type __r = 1664525 * _T(__first[__kmodn] ^ __first[__kpmodn]
2431 ^ __first[(__k - 1) % __n]);
2432 __first[__kpmodn] += __r;
2433 __r += __kmodn + __v_[__k-1];
2434 __first[(__k + __q) % __n] += __r;
2435 __first[__kmodn] = __r;
2436 }
2437 for (size_t __k = __s + 1; __k < __m; ++__k)
2438 {
2439 const size_t __kmodn = __k % __n;
2440 const size_t __kpmodn = (__k + __p) % __n;
2441 result_type __r = 1664525 * _T(__first[__kmodn] ^ __first[__kpmodn]
2442 ^ __first[(__k - 1) % __n]);
2443 __first[__kpmodn] += __r;
2444 __r += __kmodn;
2445 __first[(__k + __q) % __n] += __r;
2446 __first[__kmodn] = __r;
2447 }
2448 for (size_t __k = __m; __k < __m + __n; ++__k)
2449 {
2450 const size_t __kmodn = __k % __n;
2451 const size_t __kpmodn = (__k + __p) % __n;
2452 result_type __r = 1566083941 * _T(__first[__kmodn] +
2453 __first[__kpmodn] +
2454 __first[(__k - 1) % __n]);
2455 __first[__kpmodn] ^= __r;
2456 __r -= __kmodn;
2457 __first[(__k + __q) % __n] ^= __r;
2458 __first[__kmodn] = __r;
2459 }
2460 }
2461}
2462
2463template<class _RealType, size_t __bits, class _URNG>
2464_RealType
2465generate_canonical(_URNG& __g)
2466{
2467 const size_t _Dt = numeric_limits<_RealType>::digits;
2468 const size_t __b = _Dt < __bits ? _Dt : __bits;
2469 const size_t __logR = __log2<uint64_t, _URNG::_Max - _URNG::_Min + uint64_t(1)>::value;
2470 const size_t __k = __b / __logR + (__b % __logR != 0) + (__b == 0);
2471 const _RealType _R = _URNG::_Max - _URNG::_Min + _RealType(1);
2472 _RealType __base = _R;
2473 _RealType _S = __g() - _URNG::_Min;
2474 for (size_t __i = 1; __i < __k; ++__i, __base *= _R)
2475 _S += (__g() - _URNG::_Min) * __base;
2476 return _S / __base;
2477}
2478
2479// __independent_bits_engine
2480
2481template<class _Engine, class _UIntType>
2482class __independent_bits_engine
2483{
2484public:
2485 // types
2486 typedef _UIntType result_type;
2487
2488private:
2489 typedef typename _Engine::result_type _Engine_result_type;
2490 typedef typename conditional
2491 <
2492 sizeof(_Engine_result_type) <= sizeof(result_type),
2493 result_type,
2494 _Engine_result_type
2495 >::type _Working_result_type;
2496
2497 _Engine& __e_;
2498 size_t __w_;
2499 size_t __w0_;
2500 size_t __n_;
2501 size_t __n0_;
2502 _Working_result_type __y0_;
2503 _Working_result_type __y1_;
2504 _Engine_result_type __mask0_;
2505 _Engine_result_type __mask1_;
2506
2507 static const _Working_result_type _R = _Engine::_Max - _Engine::_Min
2508 + _Working_result_type(1);
2509 static const size_t __m = __log2<_Working_result_type, _R>::value;
2510 static const size_t _WDt = numeric_limits<_Working_result_type>::digits;
2511 static const size_t _EDt = numeric_limits<_Engine_result_type>::digits;
2512
2513public:
2514 // constructors and seeding functions
2515 __independent_bits_engine(_Engine& __e, size_t __w);
2516
2517 // generating functions
2518 result_type operator()() {return __eval(integral_constant<bool, _R != 0>());}
2519
2520private:
2521 result_type __eval(false_type);
2522 result_type __eval(true_type);
2523};
2524
2525template<class _Engine, class _UIntType>
2526__independent_bits_engine<_Engine, _UIntType>
2527 ::__independent_bits_engine(_Engine& __e, size_t __w)
2528 : __e_(__e),
2529 __w_(__w)
2530{
2531 __n_ = __w_ / __m + (__w_ % __m != 0);
2532 __w0_ = __w_ / __n_;
2533 if (_R == 0)
2534 __y0_ = _R;
2535 else if (__w0_ < _WDt)
2536 __y0_ = (_R >> __w0_) << __w0_;
2537 else
2538 __y0_ = 0;
2539 if (_R - __y0_ > __y0_ / __n_)
2540 {
2541 ++__n_;
2542 __w0_ = __w_ / __n_;
2543 if (__w0_ < _WDt)
2544 __y0_ = (_R >> __w0_) << __w0_;
2545 else
2546 __y0_ = 0;
2547 }
2548 __n0_ = __n_ - __w_ % __n_;
2549 if (__w0_ < _WDt - 1)
2550 __y1_ = (_R >> (__w0_ + 1)) << (__w0_ + 1);
2551 else
2552 __y1_ = 0;
2553 __mask0_ = __w0_ > 0 ? _Engine_result_type(~0) >> (_EDt - __w0_) :
2554 _Engine_result_type(0);
2555 __mask1_ = __w0_ < _EDt - 1 ?
2556 _Engine_result_type(~0) >> (_EDt - (__w0_ + 1)) :
2557 _Engine_result_type(~0);
2558}
2559
2560template<class _Engine, class _UIntType>
2561inline
2562_UIntType
2563__independent_bits_engine<_Engine, _UIntType>::__eval(false_type)
2564{
2565 return static_cast<result_type>(__e_() & __mask0_);
2566}
2567
2568template<class _Engine, class _UIntType>
2569_UIntType
2570__independent_bits_engine<_Engine, _UIntType>::__eval(true_type)
2571{
2572 result_type _S = 0;
2573 for (size_t __k = 0; __k < __n0_; ++__k)
2574 {
2575 _Engine_result_type __u;
2576 do
2577 {
2578 __u = __e_() - _Engine::min();
2579 } while (__u >= __y0_);
2580 if (__w0_ < _EDt)
2581 _S <<= __w0_;
2582 else
2583 _S = 0;
2584 _S += __u & __mask0_;
2585 }
2586 for (size_t __k = __n0_; __k < __n_; ++__k)
2587 {
2588 _Engine_result_type __u;
2589 do
2590 {
2591 __u = __e_() - _Engine::min();
2592 } while (__u >= __y1_);
2593 if (__w0_ < _EDt - 1)
2594 _S <<= __w0_ + 1;
2595 else
2596 _S = 0;
2597 _S += __u & __mask1_;
2598 }
2599 return _S;
2600}
2601
2602template<class _IntType = int>
2603class uniform_int_distribution
2604{
2605public:
2606 // types
2607 typedef _IntType result_type;
2608
2609 class param_type
2610 {
2611 result_type __a_;
2612 result_type __b_;
2613 public:
2614 typedef uniform_int_distribution distribution_type;
2615
2616 explicit param_type(result_type __a = 0,
2617 result_type __b = numeric_limits<result_type>::max())
2618 : __a_(__a), __b_(__b) {}
2619
2620 result_type a() const {return __a_;}
2621 result_type b() const {return __b_;}
2622
2623 friend bool operator==(const param_type& __x, const param_type& __y)
2624 {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
2625 friend bool operator!=(const param_type& __x, const param_type& __y)
2626 {return !(__x == __y);}
2627 };
2628
2629private:
2630 param_type __p_;
2631
2632public:
2633 // constructors and reset functions
2634 explicit uniform_int_distribution(result_type __a = 0,
2635 result_type __b = numeric_limits<result_type>::max())
2636 : __p_(param_type(__a, __b)) {}
2637 explicit uniform_int_distribution(const param_type& __p) : __p_(__p) {}
2638 void reset() {}
2639
2640 // generating functions
2641 template<class _URNG> result_type operator()(_URNG& __g)
2642 {return (*this)(__g, __p_);}
2643 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
2644
2645 // property functions
2646 result_type a() const {return __p_.a();}
2647 result_type b() const {return __p_.b();}
2648
2649 param_type param() const {return __p_;}
2650 void param(const param_type& __p) {__p_ = __p;}
2651
2652 result_type min() const {return a();}
2653 result_type max() const {return b();}
2654
2655 friend bool operator==(const uniform_int_distribution& __x,
2656 const uniform_int_distribution& __y)
2657 {return __x.__p_ == __y.__p_;}
2658 friend bool operator!=(const uniform_int_distribution& __x,
2659 const uniform_int_distribution& __y)
2660 {return !(__x == __y);}
2661};
2662
2663template<class _IntType>
2664template<class _URNG>
2665typename uniform_int_distribution<_IntType>::result_type
2666uniform_int_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p)
2667{
2668 typedef typename conditional<sizeof(result_type) <= sizeof(uint32_t),
2669 uint32_t, uint64_t>::type _UIntType;
2670 const _UIntType _R = __p.b() - __p.a() + _UIntType(1);
2671 if (_R == 1)
2672 return __p.a();
2673 const size_t _Dt = numeric_limits<_UIntType>::digits;
2674 typedef __independent_bits_engine<_URNG, _UIntType> _Eng;
2675 if (_R == 0)
2676 return static_cast<result_type>(_Eng(__g, _Dt)());
2677 size_t __w = _Dt - __clz(_R) - 1;
2678 if ((_R & (_UIntType(~0) >> (_Dt - __w))) != 0)
2679 ++__w;
2680 _Eng __e(__g, __w);
2681 _UIntType __u;
2682 do
2683 {
2684 __u = __e();
2685 } while (__u >= _R);
2686 return static_cast<result_type>(__u + __p.a());
2687}
2688
2689template <class _CharT, class _Traits, class _IT>
2690basic_ostream<_CharT, _Traits>&
2691operator<<(basic_ostream<_CharT, _Traits>& __os,
2692 const uniform_int_distribution<_IT>& __x)
2693{
2694 __save_flags<_CharT, _Traits> _(__os);
2695 __os.flags(ios_base::dec | ios_base::left);
2696 _CharT __sp = __os.widen(' ');
2697 __os.fill(__sp);
2698 return __os << __x.a() << __sp << __x.b();
2699}
2700
2701template <class _CharT, class _Traits, class _IT>
2702basic_istream<_CharT, _Traits>&
2703operator>>(basic_istream<_CharT, _Traits>& __is,
2704 uniform_int_distribution<_IT>& __x)
2705{
2706 typedef uniform_int_distribution<_IT> _Eng;
2707 typedef typename _Eng::result_type result_type;
2708 typedef typename _Eng::param_type param_type;
2709 __save_flags<_CharT, _Traits> _(__is);
2710 __is.flags(ios_base::dec | ios_base::skipws);
2711 result_type __a;
2712 result_type __b;
2713 __is >> __a >> __b;
2714 if (!__is.fail())
2715 __x.param(param_type(__a, __b));
2716 return __is;
2717}
2718
2719template<class _RealType = double>
2720class uniform_real_distribution
2721{
2722public:
2723 // types
2724 typedef _RealType result_type;
2725
2726 class param_type
2727 {
2728 result_type __a_;
2729 result_type __b_;
2730 public:
2731 typedef uniform_real_distribution distribution_type;
2732
2733 explicit param_type(result_type __a = 0,
2734 result_type __b = 1)
2735 : __a_(__a), __b_(__b) {}
2736
2737 result_type a() const {return __a_;}
2738 result_type b() const {return __b_;}
2739
2740 friend bool operator==(const param_type& __x, const param_type& __y)
2741 {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
2742 friend bool operator!=(const param_type& __x, const param_type& __y)
2743 {return !(__x == __y);}
2744 };
2745
2746private:
2747 param_type __p_;
2748
2749public:
2750 // constructors and reset functions
2751 explicit uniform_real_distribution(result_type __a = 0, result_type __b = 1)
2752 : __p_(param_type(__a, __b)) {}
2753 explicit uniform_real_distribution(const param_type& __p) : __p_(__p) {}
2754 void reset() {}
2755
2756 // generating functions
2757 template<class _URNG> result_type operator()(_URNG& __g)
2758 {return (*this)(__g, __p_);}
2759 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
2760
2761 // property functions
2762 result_type a() const {return __p_.a();}
2763 result_type b() const {return __p_.b();}
2764
2765 param_type param() const {return __p_;}
2766 void param(const param_type& __p) {__p_ = __p;}
2767
2768 result_type min() const {return a();}
2769 result_type max() const {return b();}
2770
2771 friend bool operator==(const uniform_real_distribution& __x,
2772 const uniform_real_distribution& __y)
2773 {return __x.__p_ == __y.__p_;}
2774 friend bool operator!=(const uniform_real_distribution& __x,
2775 const uniform_real_distribution& __y)
2776 {return !(__x == __y);}
2777};
2778
2779template<class _RealType>
2780template<class _URNG>
2781inline
2782typename uniform_real_distribution<_RealType>::result_type
2783uniform_real_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
2784{
2785 return (__p.b() - __p.a())
2786 * _STD::generate_canonical<_RealType, numeric_limits<_RealType>::digits>(__g)
2787 + __p.a();
2788}
2789
2790template <class _CharT, class _Traits, class _RT>
2791basic_ostream<_CharT, _Traits>&
2792operator<<(basic_ostream<_CharT, _Traits>& __os,
2793 const uniform_real_distribution<_RT>& __x)
2794{
2795 __save_flags<_CharT, _Traits> _(__os);
2796 __os.flags(ios_base::dec | ios_base::left);
2797 _CharT __sp = __os.widen(' ');
2798 __os.fill(__sp);
2799 return __os << __x.a() << __sp << __x.b();
2800}
2801
2802template <class _CharT, class _Traits, class _RT>
2803basic_istream<_CharT, _Traits>&
2804operator>>(basic_istream<_CharT, _Traits>& __is,
2805 uniform_real_distribution<_RT>& __x)
2806{
2807 typedef uniform_real_distribution<_RT> _Eng;
2808 typedef typename _Eng::result_type result_type;
2809 typedef typename _Eng::param_type param_type;
2810 __save_flags<_CharT, _Traits> _(__is);
2811 __is.flags(ios_base::dec | ios_base::skipws);
2812 result_type __a;
2813 result_type __b;
2814 __is >> __a >> __b;
2815 if (!__is.fail())
2816 __x.param(param_type(__a, __b));
2817 return __is;
2818}
2819
2820class bernoulli_distribution
2821{
2822public:
2823 // types
2824 typedef bool result_type;
2825
2826 class param_type
2827 {
2828 double __p_;
2829 public:
2830 typedef bernoulli_distribution distribution_type;
2831
2832 explicit param_type(double __p = 0.5) : __p_(__p) {}
2833
2834 double p() const {return __p_;}
2835
2836 friend bool operator==(const param_type& __x, const param_type& __y)
2837 {return __x.__p_ == __y.__p_;}
2838 friend bool operator!=(const param_type& __x, const param_type& __y)
2839 {return !(__x == __y);}
2840 };
2841
2842private:
2843 param_type __p_;
2844
2845public:
2846 // constructors and reset functions
2847 explicit bernoulli_distribution(double __p = 0.5)
2848 : __p_(param_type(__p)) {}
2849 explicit bernoulli_distribution(const param_type& __p) : __p_(__p) {}
2850 void reset() {}
2851
2852 // generating functions
2853 template<class _URNG> result_type operator()(_URNG& __g)
2854 {return (*this)(__g, __p_);}
Howard Hinnant03aad812010-05-11 23:26:59 +0000[diff] [blame^]2855 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]2856
2857 // property functions
2858 double p() const {return __p_.p();}
2859
2860 param_type param() const {return __p_;}
2861 void param(const param_type& __p) {__p_ = __p;}
2862
2863 result_type min() const {return false;}
2864 result_type max() const {return true;}
2865
2866 friend bool operator==(const bernoulli_distribution& __x,
2867 const bernoulli_distribution& __y)
2868 {return __x.__p_ == __y.__p_;}
2869 friend bool operator!=(const bernoulli_distribution& __x,
2870 const bernoulli_distribution& __y)
2871 {return !(__x == __y);}
2872};
2873
Howard Hinnant03aad812010-05-11 23:26:59 +0000[diff] [blame^]2874template<class _URNG>
2875inline
2876bernoulli_distribution::result_type
2877bernoulli_distribution::operator()(_URNG& __g, const param_type& __p)
2878{
2879 return (__g() - __g.min()) < __p.p() * (__g.max() - __g.min() + 1.);
2880}
2881
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]2882template <class _CharT, class _Traits>
2883basic_ostream<_CharT, _Traits>&
2884operator<<(basic_ostream<_CharT, _Traits>& __os, const bernoulli_distribution& __x)
2885{
2886 __save_flags<_CharT, _Traits> _(__os);
2887 __os.flags(ios_base::dec | ios_base::left);
2888 _CharT __sp = __os.widen(' ');
2889 __os.fill(__sp);
2890 return __os << __x.p();
2891}
2892
2893template <class _CharT, class _Traits>
2894basic_istream<_CharT, _Traits>&
2895operator>>(basic_istream<_CharT, _Traits>& __is, bernoulli_distribution& __x)
2896{
2897 typedef bernoulli_distribution _Eng;
2898 typedef typename _Eng::param_type param_type;
2899 __save_flags<_CharT, _Traits> _(__is);
2900 __is.flags(ios_base::dec | ios_base::skipws);
2901 double __p;
2902 __is >> __p;
2903 if (!__is.fail())
2904 __x.param(param_type(__p));
2905 return __is;
2906}
2907
Howard Hinnant03aad812010-05-11 23:26:59 +0000[diff] [blame^]2908template<class _IntType = int>
2909class binomial_distribution
2910{
2911public:
2912 // types
2913 typedef _IntType result_type;
2914
2915 class param_type
2916 {
2917 result_type __t_;
2918 double __p_;
2919 public:
2920 typedef binomial_distribution distribution_type;
2921
2922 explicit param_type(result_type __t = 1, double __p = 0.5)
2923 : __t_(__t), __p_(__p) {}
2924
2925 result_type t() const {return __t_;}
2926 double p() const {return __p_;}
2927
2928 friend bool operator==(const param_type& __x, const param_type& __y)
2929 {return __x.__t_ == __y.__t_ && __x.__p_ == __y.__p_;}
2930 friend bool operator!=(const param_type& __x, const param_type& __y)
2931 {return !(__x == __y);}
2932 };
2933
2934private:
2935 param_type __p_;
2936
2937public:
2938 // constructors and reset functions
2939 explicit binomial_distribution(result_type __t = 1, double __p = 0.5)
2940 : __p_(param_type(__t, __p)) {}
2941 explicit binomial_distribution(const param_type& __p) : __p_(__p) {}
2942 void reset() {}
2943
2944 // generating functions
2945 template<class _URNG> result_type operator()(_URNG& __g)
2946 {return (*this)(__g, __p_);}
2947 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
2948
2949 // property functions
2950 result_type t() const {return __p_.t();}
2951 double p() const {return __p_.p();}
2952
2953 param_type param() const {return __p_;}
2954 void param(const param_type& __p) {__p_ = __p;}
2955
2956 result_type min() const {return 0;}
2957 result_type max() const {return t();}
2958
2959 friend bool operator==(const binomial_distribution& __x,
2960 const binomial_distribution& __y)
2961 {return __x.__p_ == __y.__p_;}
2962 friend bool operator!=(const binomial_distribution& __x,
2963 const binomial_distribution& __y)
2964 {return !(__x == __y);}
2965};
2966
2967template<class _IntType>
2968template<class _URNG>
2969_IntType
2970binomial_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p)
2971{
2972 bernoulli_distribution __bd(__p.p());
2973 _IntType __r = 0;
2974 _IntType __t = __p.t();
2975 for (_IntType __i = 0; __i < __t; ++__i)
2976 __r += __bd(__g);
2977 return __r;
2978}
2979
2980template <class _CharT, class _Traits, class _IntType>
2981basic_ostream<_CharT, _Traits>&
2982operator<<(basic_ostream<_CharT, _Traits>& __os,
2983 const binomial_distribution<_IntType>& __x)
2984{
2985 __save_flags<_CharT, _Traits> _(__os);
2986 __os.flags(ios_base::dec | ios_base::left);
2987 _CharT __sp = __os.widen(' ');
2988 __os.fill(__sp);
2989 return __os << __x.t() << __sp << __x.p();
2990}
2991
2992template <class _CharT, class _Traits, class _IntType>
2993basic_istream<_CharT, _Traits>&
2994operator>>(basic_istream<_CharT, _Traits>& __is,
2995 binomial_distribution<_IntType>& __x)
2996{
2997 typedef binomial_distribution<_IntType> _Eng;
2998 typedef typename _Eng::result_type result_type;
2999 typedef typename _Eng::param_type param_type;
3000 __save_flags<_CharT, _Traits> _(__is);
3001 __is.flags(ios_base::dec | ios_base::skipws);
3002 result_type __t;
3003 double __p;
3004 __is >> __t >> __p;
3005 if (!__is.fail())
3006 __x.param(param_type(__t, __p));
3007 return __is;
3008}
3009
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]3010_LIBCPP_END_NAMESPACE_STD
3011
3012#endif // _LIBCPP_RANDOM