Coverage Report

Created: 2020-07-11 14:00

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