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