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