Project

General

Profile

Statistics
| Revision:

root / lab4 / .minix-src / include / c++ / random @ 14

History | View | Annotate | Download (220 KB)

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