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