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

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

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