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