source: mainline/uspace/lib/cpp/include/__bits/random.hpp

Last change on this file was bc56f30, checked in by Jiří Zárevúcky <zarevucky.jiri@…>, 6 years ago

Make some libc and libposix headers usable in C++

These headers either get included from standard C++ headers,
or are standard themselves, which means any unnamespaced nonstandard
identifiers are a problem. This commit attempts to fix those
issues, and removes hacks previously used in libcpp to work around it.
  • Property mode set to 100644
File size: 43.7 KB
Line 
1/*
2 * Copyright (c) 2018 Jaroslav Jindrak
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29#ifndef LIBCPP_BITS_RANDOM
30#define LIBCPP_BITS_RANDOM
31
32#include <__bits/builtins.hpp>
33#include <cstdint>
34#include <cstdlib>
35#include <ctime>
36#include <initializer_list>
37#include <limits>
38#include <type_traits>
39#include <vector>
40
41/**
42 * Note: Variables with one or two lettered
43 * names here are named after their counterparts in
44 * the standard. If one needs to understand their meaning,
45 * they should seek the mentioned standard section near
46 * the declaration of these variables.
47 * Note: There will be a lot of mathematical expressions in this header.
48 * All of these are taken directly from the standard's requirements
49 * and as such won't be commented here, check the appropriate
50 * sections if you need explanation of these forumulae.
51 */
52
53namespace std
54{
55 namespace aux
56 {
57 /**
58 * This is the minimum requirement imposed by the
59 * standard for a type to qualify as a seed sequence
60 * in overloading resolutions.
61 * (This is because the engines have constructors
62 * that accept sequence and seed and without this
63 * minimal requirements overload resolution would fail.)
64 */
65 template<class Sequence, class ResultType>
66 struct is_seed_sequence
67 : aux::value_is<
68 bool, !is_convertible_v<Sequence, ResultType>
69 >
70 { /* DUMMY BODY */ };
71
72 template<class T, class Engine>
73 inline constexpr bool is_seed_sequence_v = is_seed_sequence<T, Engine>::value;
74 }
75
76 /**
77 * 26.5.3.1, class template linear_congruential_engine:
78 */
79
80 template<class UIntType, UIntType a, UIntType c, UIntType m>
81 class linear_congruential_engine
82 {
83 static_assert(m == 0 || (a < m && c < m));
84
85 public:
86 using result_type = UIntType;
87
88 static constexpr result_type multiplier = a;
89 static constexpr result_type increment = c;
90 static constexpr result_type modulus = m;
91
92 static constexpr result_type min()
93 {
94 return c == 0U ? 1U : 0U;
95 }
96
97 static constexpr result_type max()
98 {
99 return m - 1U;
100 }
101
102 static constexpr result_type default_seed = 1U;
103
104 explicit linear_congruential_engine(result_type s = default_seed)
105 : state_{}
106 {
107 seed(s);
108 }
109
110 linear_congruential_engine(const linear_congruential_engine& other)
111 : state_{other.state_}
112 { /* DUMMY BODY */ }
113
114 template<class Seq>
115 explicit linear_congruential_engine(
116 enable_if_t<aux::is_seed_sequence_v<Seq, result_type>, Seq&> q
117 )
118 : state_{}
119 {
120 seed(q);
121 }
122
123 void seed(result_type s = default_seed)
124 {
125 if (c % modulus_ == 0 && s % modulus_ == 0)
126 state_ = 1;
127 else
128 state_ = s % modulus_;
129 }
130
131 template<class Seq>
132 void seed(
133 enable_if_t<aux::is_seed_sequence_v<Seq, result_type>, Seq&> q
134 )
135 {
136 auto k = static_cast<size_t>(aux::ceil(aux::log2(modulus_) / 32));
137 auto arr = new result_type[k + 3];
138
139 q.generate(arr, arr + k + 3);
140
141 result_type s{};
142 for (size_t j = 0; j < k; ++j)
143 s += arr[j + 3] * aux::pow2(32U * j);
144 s = s % modulus_;
145
146 if (c % modulus_ == 0 && s == 0)
147 state_ = 1;
148 else
149 state_ = s % modulus_;
150 delete[] arr;
151 }
152
153 result_type operator()()
154 {
155 return generate_();
156 }
157
158 void discard(unsigned long long z)
159 {
160 for (unsigned long long i = 0ULL; i < z; ++i)
161 transition_();
162 }
163
164 bool operator==(const linear_congruential_engine& rhs) const
165 {
166 return state_ = rhs.state_;
167 }
168
169 bool operator!=(const linear_congruential_engine& rhs) const
170 {
171 return !(*this == rhs);
172 }
173
174 template<class Char, class Traits>
175 basic_ostream<Char, Traits>& operator<<(basic_ostream<Char, Traits>& os) const
176 {
177 auto flags = os.flags();
178 os.flags(ios_base::dec | ios_base::left);
179
180 os << state_;
181
182 os.flags(flags);
183 return os;
184 }
185
186 template<class Char, class Traits>
187 basic_istream<Char, Traits>& operator>>(basic_istream<Char, Traits>& is) const
188 {
189 auto flags = is.flags();
190 is.flags(ios_base::dec);
191
192 result_type tmp{};
193 if (is >> tmp)
194 state_ = tmp;
195 else
196 is.setstate(ios::failbit);
197
198 is.flags(flags);
199 return is;
200 }
201
202 private:
203 result_type state_;
204
205 static constexpr result_type modulus_ =
206 (m == 0) ? (numeric_limits<result_type>::max() + 1) : m;
207
208 void transition_()
209 {
210 state_ = (a * state_ + c) % modulus_;
211 }
212
213 result_type generate_()
214 {
215 transition_();
216
217 return state_;
218 }
219 };
220
221 /**
222 * 26.5.3.2, class template mersenne_twister_engine:
223 */
224
225 template<
226 class UIntType, size_t w, size_t n, size_t m, size_t r,
227 UIntType a, size_t u, UIntType d, size_t s,
228 UIntType b, size_t t, UIntType c, size_t l, UIntType f
229 >
230 class mersenne_twister_engine
231 {
232 // TODO: fix these
233 /* static_assert(0 < m && m <= n); */
234 /* static_assert(2 * u < w); */
235 /* static_assert(r <= w && u <= w && s <= w && t <= w && l <= w); */
236 /* /1* static_assert(w <= numeric_limits<UIntType>::digits); *1/ */
237 /* static_assert(a <= (1U << w) - 1U); */
238 /* static_assert(b <= (1U << w) - 1U); */
239 /* static_assert(c <= (1U << w) - 1U); */
240 /* static_assert(d <= (1U << w) - 1U); */
241 /* static_assert(f <= (1U << w) - 1U); */
242
243 public:
244 using result_type = UIntType;
245
246 static constexpr size_t word_size = w;
247 static constexpr size_t state_size = n;
248 static constexpr size_t shift_size = m;
249 static constexpr size_t mask_bits = r;
250 static constexpr UIntType xor_mask = a;
251
252 static constexpr size_t tempering_u = u;
253 static constexpr UIntType tempering_d = d;
254 static constexpr size_t tempering_s = s;
255 static constexpr UIntType tempering_b = b;
256 static constexpr size_t tempering_t = t;
257 static constexpr UIntType tempering_c = c;
258 static constexpr size_t tempering_l = l;
259
260 static constexpr UIntType initialization_multiplier = f;
261
262 static constexpr result_type min()
263 {
264 return result_type{};
265 }
266
267 static constexpr result_type max()
268 {
269 return static_cast<result_type>(aux::pow2(w)) - 1U;
270 }
271
272 static constexpr result_type default_seed = 5489U;
273
274 explicit mersenne_twister_engine(result_type value = default_seed)
275 : state_{}, i_{}
276 {
277 seed(value);
278 }
279
280 template<class Seq>
281 explicit mersenne_twister_engine(
282 enable_if_t<aux::is_seed_sequence_v<Seq, result_type>, Seq&> q
283 )
284 : state_{}, i_{}
285 {
286 seed(q);
287 }
288
289 void seed(result_type value = default_seed)
290 {
291 state_[idx_(-n)] = value % aux::pow2u(w);;
292
293 for (long long i = 1 - n; i <= -1; ++i)
294 {
295 state_[idx_(i)] = (f * (state_[idx_(i - 1)] ^
296 (state_[idx_(i - 1)] >> (w - 2))) + 1 % n) % aux::pow2u(w);
297 }
298 }
299
300 template<class Seq>
301 void seed(
302 enable_if_t<aux::is_seed_sequence_v<Seq, result_type>, Seq&> q
303 )
304 {
305 auto k = static_cast<size_t>(w / 32);
306 auto arr = new result_type[n * k];
307 q.generate(arr, arr + n * k);
308
309 for (long long i = -n; i <= -1; ++i)
310 {
311 state_[idx_(i)] = result_type{};
312 for (long long j = 0; j < k; ++j)
313 state_[idx_(i)] += arr[k * (i + n) + j] * aux::pow2(32 * j);
314 state_[idx_(i)] %= aux::pow2(w);
315 }
316
317 delete[] arr;
318 }
319
320 result_type operator()()
321 {
322 return generate_();
323 }
324
325 void discard(unsigned long long z)
326 {
327 for (unsigned long long i = 0ULL; i < z; ++i)
328 transition_();
329 }
330
331 bool operator==(const mersenne_twister_engine& rhs) const
332 {
333 if (i_ != rhs.i_)
334 return false;
335
336 for (size_t i = 0; i < n; ++i)
337 {
338 if (state_[i] != rhs.state_[i])
339 return false;
340 }
341
342 return true;
343 }
344
345 bool operator!=(const mersenne_twister_engine& rhs) const
346 {
347 return !(*this == rhs);
348 }
349
350 template<class Char, class Traits>
351 basic_ostream<Char, Traits>& operator<<(basic_ostream<Char, Traits>& os) const
352 {
353 auto flags = os.flags();
354 os.flags(ios_base::dec | ios_base::left);
355
356 for (size_t j = n + 1; j > 1; --j)
357 {
358 os << state_[idx_(i_ - j - 1)];
359
360 if (j > 2)
361 os << os.widen(' ');
362 }
363
364 os.flags(flags);
365 return os;
366 }
367
368 template<class Char, class Traits>
369 basic_istream<Char, Traits>& operator>>(basic_istream<Char, Traits>& is) const
370 {
371 auto flags = is.flags();
372 is.flags(ios_base::dec);
373
374 for (size_t j = n + 1; j > 1; --j)
375 {
376 if (!(is >> state_[idx_(i_ - j - 1)]))
377 {
378 is.setstate(ios::failbit);
379 break;
380 }
381 }
382
383 is.flags(flags);
384 return is;
385 }
386
387 private:
388 result_type state_[n];
389 size_t i_;
390
391 void transition_()
392 {
393 auto mask = (result_type{1} << r) - 1;
394 auto y = (state_[idx_(i_ - n)] & ~mask) | (state_[idx_(i_ + 1 - n)] & mask);
395 auto alpha = a * (y & 1);
396 state_[i_] = state_[idx_(i_ + m - n)] ^ (y >> 1) ^ alpha;
397
398 i_ = (i_ + 1) % n;
399 }
400
401 result_type generate_()
402 {
403 auto z1 = state_[i_] ^ ((state_[i_] >> u) & d);
404 auto z2 = z1 ^ (lshift_(z1, s) & b);
405 auto z3 = z2 ^ (lshift_(z2, t) & c);
406 auto z4 = z3 ^ (z3 >> l);
407
408 transition_();
409
410 return z4;
411 }
412
413 size_t idx_(size_t idx) const
414 {
415 return idx % n;
416 }
417
418 result_type lshift_(result_type val, size_t count)
419 {
420 return (val << count) % aux::pow2u(w);
421 }
422 };
423
424 /**
425 * 26.5.3.3, class template subtract_with_carry_engine:
426 */
427
428 template<class UIntType, size_t w, size_t s, size_t r>
429 class subtract_with_carry_engine
430 {
431 // TODO: fix these
432 /* static_assert(0U < s); */
433 /* static_assert(s < r); */
434 /* static_assert(0U < w); */
435 /* static_assert(w <= numeric_limits<UIntType>::digits); */
436
437 public:
438 using result_type = UIntType;
439
440 static constexpr size_t word_size = w;
441 static constexpr size_t short_lag = s;
442 static constexpr size_t long_lag = r;
443
444 static constexpr result_type min()
445 {
446 return result_type{};
447 }
448
449 static constexpr result_type max()
450 {
451 return m_ - 1;
452 }
453
454 static constexpr result_type default_seed = 19780503U;
455
456 explicit subtract_with_carry_engine(result_type value = default_seed)
457 : state_{}, i_{}, carry_{}
458 {
459 seed(value);
460 }
461
462 template<class Seq>
463 explicit subtract_with_carry_engine(
464 enable_if_t<aux::is_seed_sequence_v<Seq, result_type>, Seq&> q
465 )
466 : state_{}, i_{}, carry_{}
467 {
468 seed(q);
469 }
470
471 void seed(result_type value = default_seed)
472 {
473 linear_congruential_engine<
474 result_type, 40014U, 0U, 2147483563U
475 > e{value == 0U ? default_seed : value};
476
477 auto n = aux::ceil(w / 32.0);
478 auto z = new result_type[n];
479
480 for (long long i = -r; i <= -1; ++i)
481 {
482 for (size_t i = 0; i < n; ++i)
483 z[i] = e() % aux::pow2u(32);
484
485 state_[idx_(i)] = result_type{};
486 for (size_t j = 0; j < n; ++j)
487 state_[idx_(i)] += z[j] * aux::pow2u(32 * j);
488 state_[idx_(i)] %= m_;
489 }
490
491 if (state_[idx_(-1)] == 0)
492 carry_ = 1;
493 else
494 carry_ = 0;
495
496 delete[] z;
497 }
498
499 template<class Seq>
500 void seed(
501 enable_if_t<aux::is_seed_sequence_v<Seq, result_type>, Seq&> q
502 )
503 {
504 auto k = aux::ceil(w / 32.0);
505 auto arr = new result_type[r * k];
506
507 q.generate(arr, arr + r * k);
508
509 for (long long i = -r; i <= -1; ++i)
510 {
511 state_[idx_(i)] = result_type{};
512 for (long long j = 0; j < k; ++j)
513 state_[idx_(i)] += arr[k * (i + r) + j] * aux::pow2(32 * j);
514 state_[idx_(i)] %= m_;
515 }
516
517 delete[] arr;
518
519 if (state_[idx_(-1)] == 0)
520 carry_ = 1;
521 else
522 carry_ = 0;
523 }
524
525 result_type operator()()
526 {
527 return generate_();
528 }
529
530 void discard(unsigned long long z)
531 {
532 for (unsigned long long i = 0ULL; i < z; ++i)
533 transition_();
534 }
535
536 bool operator==(const subtract_with_carry_engine& rhs) const
537 {
538 if (i_ != rhs.i_)
539 return false;
540
541 for (size_t i = 0; i < r; ++i)
542 {
543 if (state_[i] != rhs.state_[i])
544 return false;
545 }
546
547 return true;
548 }
549
550 bool operator!=(const subtract_with_carry_engine& rhs) const
551 {
552 return !(*this == rhs);
553 }
554
555 template<class Char, class Traits>
556 basic_ostream<Char, Traits>& operator<<(basic_ostream<Char, Traits>& os) const
557 {
558 auto flags = os.flags();
559 os.flags(ios_base::dec | ios_base::left);
560
561 for (size_t j = r + 1; j > 1; --j)
562 {
563 os << state_[idx_(i_ - j - 1)];
564 os << os.widen(' ');
565 }
566
567 os << carry_;
568
569 os.flags(flags);
570 return os;
571 }
572
573 template<class Char, class Traits>
574 basic_istream<Char, Traits>& operator>>(basic_istream<Char, Traits>& is) const
575 {
576 auto flags = is.flags();
577 is.flags(ios_base::dec);
578
579 for (size_t j = r + 1; j > 1; --j)
580 {
581 if (!(is >> state_[idx_(i_ - j - 1)]))
582 {
583 is.setstate(ios::failbit);
584 break;
585 }
586 }
587
588 if (!(is >> carry_))
589 is.setstate(ios::failbit);
590
591 is.flags(flags);
592 return is;
593 }
594
595 private:
596 result_type state_[r];
597 size_t i_;
598 uint8_t carry_;
599
600 static constexpr result_type m_ = aux::pow2u(w);
601
602 auto transition_()
603 {
604 auto y = static_cast<int64_t>(state_[idx_(i_ - s)]) - state_[idx_(i_ - r)] - carry_;
605 state_[i_] = y % m_;
606
607 i_ = (i_ + 1) % r;
608
609 return static_cast<result_type>(y % m_);
610 }
611
612 result_type generate_()
613 {
614 return transition_();
615 }
616
617 size_t idx_(size_t idx) const
618 {
619 return idx % r;
620 }
621 };
622
623 /**
624 * 26.5.4.2, class template discard_block_engine:
625 */
626
627 template<class Engine, size_t p, size_t r>
628 class discard_block_engine
629 {
630 static_assert(0 < r);
631 static_assert(r <= p);
632
633 public:
634 using result_type = typename Engine::result_type;
635
636 static constexpr size_t block_size = p;
637 static constexpr size_t used_block = r;
638
639 static constexpr result_type min()
640 {
641 return Engine::min();
642 }
643
644 static constexpr result_type max()
645 {
646 return Engine::max();
647 }
648
649 discard_block_engine()
650 : engine_{}, n_{}
651 { /* DUMMY BODY */ }
652
653 explicit discard_block_engine(const Engine& e)
654 : engine_{e}, n_{}
655 { /* DUMMY BODY */ }
656
657 explicit discard_block_engine(Engine&& e)
658 : engine_{move(e)}, n_{}
659 { /* DUMMY BODY */ }
660
661 explicit discard_block_engine(result_type s)
662 : engine_{s}, n_{}
663 { /* DUMMY BODY */ }
664
665 template<class Seq>
666 explicit discard_block_engine(
667 enable_if_t<aux::is_seed_sequence_v<Seq, result_type>, Seq&> q
668 )
669 : engine_{q}, n_{}
670 { /* DUMMY BODY */ }
671
672 void seed()
673 {
674 engine_.seed();
675 }
676
677 void seed(result_type s)
678 {
679 engine_.seed(s);
680 }
681
682 template<class Seq>
683 void seed(
684 enable_if_t<aux::is_seed_sequence_v<Seq, result_type>, Seq&> q
685 )
686 {
687 engine_.seed(q);
688 }
689
690 result_type operator()()
691 {
692 if (n_ > static_cast<int>(r))
693 {
694 auto count = p - r;
695 for (size_t i = 0; i < count; ++i)
696 engine_();
697 n_ = 0;
698 }
699 ++n_;
700
701 return engine_();
702 }
703
704 void discard(unsigned long long z)
705 {
706 for (unsigned long long i = 0ULL; i < z; ++i)
707 operator()(); // We need to discard our (), not engine's.
708 }
709
710 const Engine& base() const noexcept
711 {
712 return engine_;
713 }
714
715 bool operator==(const discard_block_engine& rhs) const
716 {
717 return engine_ == rhs.engine_ && n_ == rhs.n_;
718 }
719
720 bool operator!=(const discard_block_engine& rhs) const
721 {
722 return !(*this == rhs);
723 }
724
725 template<class Char, class Traits>
726 basic_ostream<Char, Traits>& operator<<(basic_ostream<Char, Traits>& os) const
727 {
728 auto flags = os.flags();
729 os.flags(ios_base::dec | ios_base::left);
730
731 os << n_ << os.widen(' ') << engine_;
732
733 os.flags(flags);
734 return os;
735 }
736
737 template<class Char, class Traits>
738 basic_istream<Char, Traits>& operator>>(basic_istream<Char, Traits>& is) const
739 {
740 auto flags = is.flags();
741 is.flags(ios_base::dec);
742
743 if (!(is >> n_) || !(is >> engine_))
744 is.setstate(ios::failbit);
745
746 is.flags(flags);
747 return is;
748 }
749
750 private:
751 Engine engine_;
752 int n_;
753 };
754
755 /**
756 * 26.5.4.3, class template independent_bits_engine:
757 */
758
759 template<class Engine, size_t w, class UIntType>
760 class independent_bits_engine
761 {
762 static_assert(0U < w);
763 /* static_assert(w <= numeric_limits<result_type>::digits); */
764
765 public:
766 using result_type = UIntType;
767
768 static constexpr result_type min()
769 {
770 return result_type{};
771 }
772
773 static constexpr result_type max()
774 {
775 return aux::pow2u(w) - 1;
776 }
777
778 independent_bits_engine()
779 : engine_{}
780 { /* DUMMY BODY */ }
781
782 explicit independent_bits_engine(const Engine& e)
783 : engine_{e}
784 { /* DUMMY BODY */ }
785
786 explicit independent_bits_engine(Engine&& e)
787 : engine_{move(e)}
788 { /* DUMMY BODY */ }
789
790 explicit independent_bits_engine(result_type s)
791 : engine_{s}
792 { /* DUMMY BODY */ }
793
794 template<class Seq>
795 explicit independent_bits_engine(
796 enable_if_t<aux::is_seed_sequence_v<Seq, result_type>, Seq&> q
797 )
798 : engine_{q}
799 { /* DUMMY BODY */ }
800
801 void seed()
802 {
803 engine_.seed();
804 }
805
806 void seed(result_type s)
807 {
808 engine_.seed(s);
809 }
810
811 template<class Seq>
812 void seed(
813 enable_if_t<aux::is_seed_sequence_v<Seq, result_type>, Seq&> q
814 )
815 {
816 engine_.seed(q);
817 }
818
819 result_type operator()()
820 {
821 /* auto r = engine_.max() - engine_.min() + 1; */
822 /* auto m = aux::floor(aux::log2(r)); */
823 // TODO:
824
825 return engine_();
826 }
827
828 void discard(unsigned long long z)
829 {
830 for (unsigned long long i = 0ULL; i < z; ++i)
831 operator()();
832 }
833
834 const Engine& base() const noexcept
835 {
836 return engine_;
837 }
838
839 bool operator==(const independent_bits_engine& rhs) const
840 {
841 return engine_ == rhs.engine_;
842 }
843
844 bool operator!=(const independent_bits_engine& rhs) const
845 {
846 return !(*this == rhs);
847 }
848
849 template<class Char, class Traits>
850 basic_ostream<Char, Traits>& operator<<(basic_ostream<Char, Traits>& os) const
851 {
852 return os << engine_;
853 }
854
855 template<class Char, class Traits>
856 basic_istream<Char, Traits>& operator>>(basic_istream<Char, Traits>& is) const
857 {
858 return is >> engine_;
859 }
860
861 private:
862 Engine engine_;
863 };
864
865 /**
866 * 26.5.4.4, class template shiffle_order_engine:
867 */
868
869 template<class Engine, size_t k>
870 class shuffle_order_engine
871 {
872 static_assert(0U < k);
873
874 public:
875 using result_type = typename Engine::result_type;
876
877 static constexpr size_t table_size = k;
878
879 static constexpr result_type min()
880 {
881 return Engine::min();
882 }
883
884 static constexpr result_type max()
885 {
886 return Engine::max();
887 }
888
889 shuffle_order_engine()
890 : engine_{}
891 { /* DUMMY BODY */ }
892
893 explicit shuffle_order_engine(const Engine& e)
894 : engine_{e}
895 { /* DUMMY BODY */ }
896
897 explicit shuffle_order_engine(Engine&& e)
898 : engine_{move(e)}
899 { /* DUMMY BODY */ }
900
901 explicit shuffle_order_engine(result_type s)
902 : engine_{s}
903 { /* DUMMY BODY */ }
904
905 template<class Seq>
906 explicit shuffle_order_engine(
907 enable_if_t<aux::is_seed_sequence_v<Seq, result_type>, Seq&> q
908 )
909 : engine_{q}
910 { /* DUMMY BODY */ }
911
912 void seed()
913 {
914 engine_.seed();
915 }
916
917 void seed(result_type s)
918 {
919 engine_.seed(s);
920 }
921
922 template<class Seq>
923 void seed(
924 enable_if_t<aux::is_seed_sequence_v<Seq, result_type>, Seq&> q
925 )
926 {
927 engine_.seed(q);
928 }
929
930 result_type operator()()
931 {
932 // TODO:
933
934 return engine_();
935 }
936
937 void discard(unsigned long long z)
938 {
939 for (unsigned long long i = 0ULL; i < z; ++i)
940 operator()();
941 }
942
943 const Engine& base() const noexcept
944 {
945 return engine_;
946 }
947
948 bool operator==(const shuffle_order_engine& rhs) const
949 {
950 return engine_ == rhs.engine_;
951 }
952
953 bool operator!=(const shuffle_order_engine& rhs) const
954 {
955 return !(*this == rhs);
956 }
957
958 template<class Char, class Traits>
959 basic_ostream<Char, Traits>& operator<<(basic_ostream<Char, Traits>& os) const
960 {
961 return os << engine_;
962 }
963
964 template<class Char, class Traits>
965 basic_istream<Char, Traits>& operator>>(basic_istream<Char, Traits>& is) const
966 {
967 return is >> engine_;
968 }
969
970 private:
971 Engine engine_;
972 result_type y_;
973 result_type table_[k];
974 };
975
976 /**
977 * 26.5.5, engines and engine adaptors with predefined
978 * parameters:
979 * TODO: check their requirements for testing
980 */
981
982 using minstd_rand0 = linear_congruential_engine<uint_fast32_t, 16807, 0, 2147483647>;
983 using minstd_rand = linear_congruential_engine<uint_fast32_t, 48271, 0, 2147483647>;
984 using mt19937 = mersenne_twister_engine<
985 uint_fast32_t, 32, 624, 397, 31, 0x9908b0df, 11, 0xffffffff, 7,
986 0x9d2c5680, 15, 0xefc60000, 18, 1812433253
987 >;
988 using mt19937_64 = mersenne_twister_engine<
989 uint_fast64_t, 64, 312, 156, 31, 0xb5026f5aa96619e9, 29,
990 0x5555555555555555, 17, 0x71d67fffeda60000, 37, 0xfff7eee000000000,
991 43, 6364136223846793005
992 >;
993 using ranlux24_base = subtract_with_carry_engine<uint_fast32_t, 24, 10, 24>;
994 using ranlux48_base = subtract_with_carry_engine<uint_fast64_t, 48, 5, 12>;
995 using ranlux24 = discard_block_engine<ranlux24_base, 223, 23>;
996 using ranlux48 = discard_block_engine<ranlux48_base, 389, 11>;
997 using knuth_b = shuffle_order_engine<minstd_rand0, 256>;
998
999 using default_random_engine = minstd_rand0;
1000
1001 /**
1002 * 26.5.6, class random_device:
1003 */
1004
1005 class random_device
1006 {
1007 using result_type = unsigned int;
1008
1009 static constexpr result_type min()
1010 {
1011 return numeric_limits<result_type>::min();
1012 }
1013
1014 static constexpr result_type max()
1015 {
1016 return numeric_limits<result_type>::max();
1017 }
1018
1019 explicit random_device(const string& token = "")
1020 {
1021 /**
1022 * Note: token can be used to choose between
1023 * random generators, but HelenOS only
1024 * has one :/
1025 * Also note that it is implementation
1026 * defined how this class generates
1027 * random numbers and I decided to use
1028 * time seeding with C stdlib random,
1029 * - feel free to change it if you know
1030 * something better.
1031 */
1032 ::srand(::time(nullptr));
1033 }
1034
1035 result_type operator()()
1036 {
1037 return ::rand();
1038 }
1039
1040 double entropy() const noexcept
1041 {
1042 return 0.0;
1043 }
1044
1045 random_device(const random_device&) = delete;
1046 random_device& operator=(const random_device&) = delete;
1047 };
1048
1049 /**
1050 * 26.5.7.1, class seed_seq:
1051 */
1052
1053 class seed_seq
1054 {
1055 public:
1056 using result_type = uint_least32_t;
1057
1058 seed_seq()
1059 : vec_{}
1060 { /* DUMMY BODY */ }
1061
1062 template<class T>
1063 seed_seq(initializer_list<T> init)
1064 : seed_seq(init.begin(), init.end())
1065 { /* DUMMY BODY */ }
1066
1067 template<class InputIterator>
1068 seed_seq(InputIterator first, InputIterator last)
1069 : vec_{}
1070 {
1071 while (first != last)
1072 vec_.push_back((*first++) % aux::pow2u(32));
1073 }
1074
1075 template<class RandomAccessGenerator>
1076 void generate(RandomAccessGenerator first,
1077 RandomAccessGenerator last)
1078 {
1079 if (first == last)
1080 return;
1081
1082 auto s = vec_.size();
1083 size_t n = last - first;
1084 result_type t = (n >= 623) ? 11 : (n >= 68) ? 7 : (n >= 39) ? 5 : (n >= 7) ? 3 : (n - 1) / 2;
1085 result_type p = (n - t) / 2;
1086 result_type q = p + t;
1087
1088 auto current = first;
1089 while (current != last)
1090 *current++ = 0x8b8b8b8b;
1091
1092 auto m = (s + 1 > n) ? (s + 1) : n;
1093 decltype(m) k{};
1094 for (; k < m; ++k)
1095 {
1096 auto r1 = 1664525 * t_(first[k % n] ^ first[(k + p) % n] ^ first[(k - 1) % n]);
1097 auto r2 = r1;
1098
1099 if (k == 0)
1100 r2 += s;
1101 else if (k > 0 && k <= s)
1102 r2 += (k % n) + vec_[(k - 1) % n];
1103 else if (s < k)
1104 r2 += (k % n);
1105
1106 first[(k + p) % n] += r1;
1107 first[(k + q) % n] += r2;
1108 first[k % n] = r2;
1109 }
1110
1111 for (; k < m + n - 1; ++k)
1112 {
1113 auto r3 = 1566083941 * t_(first[k % n] + first[(k + p) % n] + first[(k - 1) % n]);
1114 auto r4 = r3 - (k % n);
1115
1116 first[(k + p) % n] ^= r3;
1117 first[(k + q) % n] ^= r4;
1118 first[k % n] = r4;
1119 }
1120 }
1121
1122 size_t size() const
1123 {
1124 return vec_.size();
1125 }
1126
1127 template<class OutputIterator>
1128 void param(OutputIterator dest) const
1129 {
1130 for (const auto& x: vec_)
1131 *dest++ = x;
1132 }
1133
1134 seed_seq(const seed_seq&) = delete;
1135 seed_seq& operator=(const seed_seq&) = delete;
1136
1137 private:
1138 vector<result_type> vec_;
1139
1140 result_type t_(result_type val) const
1141 {
1142 return val ^ (val >> 27);
1143 }
1144 };
1145
1146 /**
1147 * 26.5.7.2, function template generate_canonical:
1148 */
1149
1150 template<class RealType, size_t bits, class URNG>
1151 RealType generate_canonical(URNG& g)
1152 {
1153 auto b = (bits < numeric_limits<RealType>::digits) ? bits : numeric_limits<RealType>::digits;
1154 RealType r = g.max() - g.min() + 1;
1155 size_t tmp = aux::ceil(b / aux::log2(r));
1156 size_t k = (1U < tmp) ? tmp : 1U;
1157
1158 RealType s{};
1159 for (size_t i = 0; i < k; ++i)
1160 s += (g() - g.min()) * aux::pow(r, i);
1161
1162 return s / aux::pow(r, k);
1163 }
1164
1165 /**
1166 * 26.5.8.2.1, class template uniform_int_distribution:
1167 */
1168
1169 template<class IntType = int>
1170 class uniform_int_distribution
1171 {
1172 public:
1173 using result_type = IntType;
1174 using param_type = pair<result_type, result_type>;
1175
1176 explicit uniform_int_distribution(result_type a = 0,
1177 result_type b = numeric_limits<result_type>::max())
1178 : a_{a}, b_{b}
1179 { /* DUMMY BODY */ }
1180
1181 explicit uniform_int_distribution(const param_type& p)
1182 : a_{p.first}, b_{p.second}
1183 { /* DUMMY BODY */ }
1184
1185 void reset()
1186 { /* DUMMY BODY */ }
1187
1188 template<class URNG>
1189 result_type operator()(URNG& g)
1190 {
1191 auto range = b_ - a_ + 1;
1192
1193 return g() % range + a_;
1194 }
1195
1196 template<class URNG>
1197 result_type operator()(URNG& g, const param_type& p)
1198 {
1199 auto range = p.second - p.first + 1;
1200
1201 return g() % range + p.first;
1202 }
1203
1204 result_type a() const
1205 {
1206 return a_;
1207 }
1208
1209 result_type b() const
1210 {
1211 return b_;
1212 }
1213
1214 param_type param() const
1215 {
1216 return param_type{a_, b_};
1217 }
1218
1219 void param(const param_type& p)
1220 {
1221 a_ = p.first;
1222 b_ = p.second;
1223 }
1224
1225 result_type min() const
1226 {
1227 return a_;
1228 }
1229
1230 result_type max() const
1231 {
1232 return b_;
1233 }
1234
1235 bool operator==(const uniform_int_distribution& rhs) const
1236 {
1237 return a_ == rhs.a_ && b_ == rhs.b_;
1238 }
1239
1240 bool operator!=(const uniform_int_distribution& rhs) const
1241 {
1242 return !(*this == rhs);
1243 }
1244
1245 template<class Char, class Traits>
1246 basic_ostream<Char, Traits>& operator<<(basic_ostream<Char, Traits>& os) const
1247 {
1248 auto flags = os.flags();
1249 os.flags(ios_base::dec | ios_base::left);
1250
1251 os << a_ << os.widen(' ') << b_;
1252
1253 os.flags(flags);
1254 return os;
1255 }
1256
1257 template<class Char, class Traits>
1258 basic_istream<Char, Traits>& operator>>(basic_istream<Char, Traits>& is) const
1259 {
1260 auto flags = is.flags();
1261 is.flags(ios_base::dec);
1262
1263 if (!(is >> a_) || !(is >> b_))
1264 is.setstate(ios::failbit);
1265
1266 is.flags(flags);
1267 return is;
1268 }
1269
1270 private:
1271 result_type a_;
1272 result_type b_;
1273 };
1274
1275 /**
1276 * 26.5.8.2.2, class template uniform_real_distribution:
1277 */
1278
1279 template<class RealType = double>
1280 class uniform_real_distribution
1281 {
1282 public:
1283 using result_type = RealType;
1284 using param_type = pair<result_type, result_type>;
1285
1286 explicit uniform_real_distribution(result_type a = 0.0,
1287 result_type b = 1.0)
1288 : a_{a}, b_{b}
1289 { /* DUMMY BODY */ }
1290
1291 explicit uniform_real_distribution(const param_type& p)
1292 : a_{p.first}, b_{p.second}
1293 { /* DUMMY BODY */ }
1294
1295 void reset()
1296 { /* DUMMY BODY */ }
1297
1298 template<class URNG>
1299 result_type operator()(URNG& g)
1300 {
1301 auto range = b_ - a_ + 1;
1302
1303 return generate_canonical<
1304 result_type, numeric_limits<result_type>::digits
1305 >(g) * range + a_;
1306 }
1307
1308 template<class URNG>
1309 result_type operator()(URNG& g, const param_type& p)
1310 {
1311 auto range = p.second - p.first + 1;
1312
1313 return generate_canonical<
1314 result_type, numeric_limits<result_type>::digits
1315 >(g) * range + p.first;
1316 }
1317
1318 result_type a() const
1319 {
1320 return a_;
1321 }
1322
1323 result_type b() const
1324 {
1325 return b_;
1326 }
1327
1328 param_type param() const
1329 {
1330 return param_type{a_, b_};
1331 }
1332
1333 void param(const param_type& p)
1334 {
1335 a_ = p.first;
1336 b_ = p.second;
1337 }
1338
1339 result_type min() const
1340 {
1341 return a_;
1342 }
1343
1344 result_type max() const
1345 {
1346 return b_;
1347 }
1348
1349 bool operator==(const uniform_real_distribution& rhs) const
1350 {
1351 return a_ == rhs.a_ && b_ == rhs.b_;
1352 }
1353
1354 bool operator!=(const uniform_real_distribution& rhs) const
1355 {
1356 return !(*this == rhs);
1357 }
1358
1359 // TODO: ostream/istream operators can't be members
1360 template<class Char, class Traits>
1361 basic_ostream<Char, Traits>& operator<<(basic_ostream<Char, Traits>& os) const
1362 {
1363 auto flags = os.flags();
1364 os.flags(ios_base::dec | ios_base::left);
1365
1366 os << a_ << os.widen(' ') << b_;
1367
1368 os.flags(flags);
1369 return os;
1370 }
1371
1372 template<class Char, class Traits>
1373 basic_istream<Char, Traits>& operator>>(basic_istream<Char, Traits>& is) const
1374 {
1375 auto flags = is.flags();
1376 is.flags(ios_base::dec);
1377
1378 if (!(is >> a_) || !(is >> b_))
1379 is.setstate(ios::failbit);
1380
1381 is.flags(flags);
1382 return is;
1383 }
1384
1385 private:
1386 result_type a_;
1387 result_type b_;
1388 };
1389
1390 /**
1391 * 26.5.8.3.1, class bernoulli_distribution:
1392 */
1393
1394 class bernoulli_distribution
1395 {
1396 public:
1397 using result_type = bool;
1398 using param_type = float;
1399
1400 explicit bernoulli_distribution(double prob = 0.5)
1401 : prob_{static_cast<float>(prob)}
1402 { /* DUMMY BODY */ }
1403
1404 explicit bernoulli_distribution(const param_type& p)
1405 : prob_{p}
1406 { /* DUMMY BODY */ }
1407
1408 void reset()
1409 { /* DUMMY BODY */ }
1410
1411 template<class URNG>
1412 result_type operator()(URNG& g)
1413 {
1414 uniform_real_distribution<float> dist{};
1415
1416 return dist(g) < prob_;
1417 }
1418
1419 template<class URNG>
1420 result_type operator()(const param_type& p)
1421 {
1422 uniform_real_distribution<float> dist{};
1423
1424 return dist(p) < prob_;
1425 }
1426
1427 double p() const
1428 {
1429 return prob_;
1430 }
1431
1432 param_type param() const
1433 {
1434 return prob_;
1435 }
1436
1437 void param(const param_type& p)
1438 {
1439 prob_ = p;
1440 }
1441
1442 result_type min() const
1443 {
1444 return false;
1445 }
1446
1447 result_type max() const
1448 {
1449 return true;
1450 }
1451
1452 private:
1453 /**
1454 * Note: We use float because we do not
1455 * have the macro DBL_MANT_DIGITS
1456 * for generate_cannonical.
1457 */
1458 float prob_;
1459 };
1460
1461 // TODO: complete the rest of the distributions
1462
1463 /**
1464 * 26.5.8.3.2, class template binomial_distribution:
1465 */
1466
1467 template<class IntType = int>
1468 class binomial_distribution;
1469
1470 /**
1471 * 26.5.8.3.3, class template geometric_distribution:
1472 */
1473
1474 template<class IntType = int>
1475 class geometric_distribution;
1476
1477 /**
1478 * 26.5.8.3.4, class template negative_binomial_distribution:
1479 */
1480
1481 template<class IntType = int>
1482 class negative_binomial_distribution;
1483
1484 /**
1485 * 26.5.8.4.1, class template poisson_distribution:
1486 */
1487
1488 template<class IntType = int>
1489 class poisson_distribution;
1490
1491 /**
1492 * 26.5.8.4.2, class template exponential_distribution:
1493 */
1494
1495 template<class RealType = double>
1496 class exponential_distribution;
1497
1498 /**
1499 * 26.5.8.4.3, class template gamma_distribution:
1500 */
1501
1502 template<class RealType = double>
1503 class gamma_distribution;
1504
1505 /**
1506 * 26.5.8.4.4, class template weibull_distribution:
1507 */
1508
1509 template<class RealType = double>
1510 class weibull_distribution;
1511
1512 /**
1513 * 26.5.8.4.5, class template extreme_value_distribution:
1514 */
1515
1516 template<class RealType = double>
1517 class extreme_value_distribution;
1518
1519 /**
1520 * 26.5.8.5.1, class template normal_distribution:
1521 */
1522
1523 template<class RealType = double>
1524 class normal_distribution;
1525
1526 /**
1527 * 26.5.8.5.2, class template lognormal_distribution:
1528 */
1529
1530 template<class RealType = double>
1531 class lognormal_distribution;
1532
1533 /**
1534 * 26.5.8.5.3, class template chi_squared_distribution:
1535 */
1536
1537 template<class RealType = double>
1538 class chi_squared_distribution;
1539
1540 /**
1541 * 26.5.8.5.4, class template cauchy_distribution:
1542 */
1543
1544 template<class RealType = double>
1545 class cauchy_distribution;
1546
1547 /**
1548 * 26.5.8.5.5, class template fisher_f_distribution:
1549 */
1550
1551 template<class RealType = double>
1552 class fisher_f_distribution;
1553
1554 /**
1555 * 26.5.8.5.6, class template student_t_distribution:
1556 */
1557
1558 template<class RealType = double>
1559 class student_t_distribution;
1560
1561 /**
1562 * 26.5.8.6.1, class template discrete_distribution:
1563 */
1564
1565 template<class IntType = int>
1566 class discrete_distribution;
1567
1568 /**
1569 * 26.5.8.6.2, class template piecewise_constant_distribution:
1570 */
1571
1572 template<class RealType = double>
1573 class piecewise_constant_distribution;
1574
1575 /**
1576 * 26.5.8.6.3, class template piecewise_linear_distribution:
1577 */
1578
1579 template<class RealType = double>
1580 class piecewise_linear_distribution;
1581}
1582
1583#endif
Note: See TracBrowser for help on using the repository browser.