source: mainline/uspace/lib/cpp/include/impl/random.hpp@ 87f625f

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 87f625f was 87f625f, checked in by Dzejrou <dzejrou@…>, 7 years ago

cpp: added discard_block_engine adaptor and WIP versions of independent_bits_engine and shuffle_order_engine adaptors
  • Property mode set to 100644
File size: 34.7 KB
RevLine 
[08e16de0]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_RANDOM
30#define LIBCPP_RANDOM
31
32#include <cstdlib>
33#include <ctime>
34#include <initializer_list>
[1a617ac]35#include <internal/builtins.hpp>
[08e16de0]36#include <limits>
37#include <type_traits>
38#include <vector>
39
40/**
41 * Note: Variables with one or two lettered
42 * names here are named after their counterparts in
43 * the standard. If one needs to understand their meaning,
44 * they should seek the mentioned standard section near
45 * the declaration of these variables.
[1a617ac]46 * Note: There will be a lot of mathematical expressions in this header.
47 * All of these are taken directly from the standard's requirements
48 * and as such won't be commented here, check the appropriate
49 * sections if you need explanation of these forumulae.
[08e16de0]50 */
51
52namespace std
53{
54 namespace aux
55 {
56 /**
57 * This is the minimum requirement imposed by the
58 * standard for a type to qualify as a seed sequence
59 * in overloading resolutions.
60 * (This is because the engines have constructors
61 * that accept sequence and seed and without this
62 * minimal requirements overload resolution would fail.)
63 */
64 template<class Sequence, class ResultType>
65 struct is_seed_sequence
66 : aux::value_is<
67 bool, !is_convertible_v<Sequence, ResultType>
68 >
69 { /* DUMMY BODY */ };
70
71 template<class T, class Engine>
72 inline constexpr bool is_seed_sequence_v = is_seed_sequence<T, Engine>::value;
73 }
74
75 /**
76 * 26.5.3.1, class template linear_congruential_engine:
77 */
78
79 template<class UIntType, UIntType a, UIntType c, UIntType m>
80 class linear_congruential_engine
81 {
[1a617ac]82 static_assert(m == 0 || (a < m && c < m));
83
[08e16de0]84 public:
85 using result_type = UIntType;
86
87 static constexpr result_type multiplier = a;
88 static constexpr result_type increment = c;
89 static constexpr result_type modulus = m;
90
[08be4a4]91 static constexpr result_type min()
[08e16de0]92 {
93 return c == 0U ? 1U : 0U;
94 }
95
[08be4a4]96 static constexpr result_type max()
[08e16de0]97 {
98 return m - 1U;
99 }
100
101 static constexpr result_type default_seed = 1U;
102
[1a617ac]103 explicit linear_congruential_engine(result_type s = default_seed)
104 : state_{}
105 {
106 seed(s);
107 }
108
109 linear_congruential_engine(const linear_congruential_engine& other)
110 : state_{other.state_}
111 { /* DUMMY BODY */ }
[08e16de0]112
113 template<class Seq>
114 explicit linear_congruential_engine(
115 enable_if_t<aux::is_seed_sequence_v<Seq, result_type>, Seq&> q
[1a617ac]116 )
117 : state_{}
118 {
[2fe861d]119 seed(q);
[1a617ac]120 }
121
122 void seed(result_type s = default_seed)
123 {
124 if (c % modulus_ == 0 && s == 0)
125 state_ = 0;
126 else
127 state_ = s;
128 }
[08e16de0]129
130 template<class Seq>
131 void seed(
132 enable_if_t<aux::is_seed_sequence_v<Seq, result_type>, Seq&> q
[2fe861d]133 )
134 {
[08be4a4]135 q.generate(arr_, arr_ + k_ + 3);
[2fe861d]136
137 result_type s{};
[08be4a4]138 for (size_t j = 0; j < k_; ++j)
139 s += arr_[j + 3] * aux::pow2(32U * j);
[2fe861d]140 s = s % modulus_;
141
142 seed(s);
143 }
[08e16de0]144
[1a617ac]145 result_type operator()()
146 {
147 return generate_();
148 }
149
150 void discard(unsigned long long z)
151 {
152 for (unsigned long long i = 0ULL; i < z; ++i)
153 transition_();
154 }
155
156 bool operator==(const linear_congruential_engine& rhs) const
157 {
158 return state_ = rhs.state_;
159 }
[08e16de0]160
[1a617ac]161 bool operator!=(const linear_congruential_engine& rhs) const
162 {
163 return !(*this == rhs);
164 }
165
166 template<class Char, class Traits>
167 basic_ostream<Char, Traits>& operator<<(basic_ostream<Char, Traits>& os) const
168 {
169 auto flags = os.flags();
170 os.flags(ios_base::dec | ios_base::left);
171
172 os << state_;
173
174 os.flags(flags);
175 return os;
176 }
177
178 template<class Char, class Traits>
179 basic_istream<Char, Traits>& operator>>(basic_istream<Char, Traits>& is) const
180 {
181 auto flags = is.flags();
182 is.flags(ios_base::dec);
183
184 result_type tmp{};
185 if (is >> tmp)
186 state_ = tmp;
187 else
188 is.setstate(ios::failbit);
189
190 is.flags(flags);
191 return is;
192 }
193
194 private:
195 result_type state_;
196
197 static constexpr result_type modulus_ =
198 (m == 0) ? (numeric_limits<result_type>::max() + 1) : m;
199
[08be4a4]200 /**
201 * We use constexpr builtins to keep this array
202 * between calls to seed(Seq&), which means we don't
203 * have to keep allocating and deleting it.
204 */
205 static constexpr size_t k_ = static_cast<size_t>(aux::ceil(aux::log2(modulus_) / 32));
206 result_type arr_[k_ + 3];
207
[1a617ac]208 void transition_()
209 {
210 state_ = (a * state_ + c) % modulus_;
211 }
212
213 result_type generate_()
214 {
215 transition_();
216
217 return state_;
218 }
[08e16de0]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 >
[08be4a4]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 q.generate(arr_, arr_ + n * k_);
306
307 for (long long i = -n; i <= -1; ++i)
308 {
309 state_[idx_(i)] = result_type{};
310 for (long long j = 0; j < k_; ++j)
311 state_[idx_(i)] += arr_[k_ * (i + n) + j] * aux::pow2(32 * j);
312 state_[idx_(i)] %= aux::pow2(w);
313 }
314 }
315
316 result_type operator()()
317 {
318 return generate_();
319 }
320
321 void discard(unsigned long long z)
322 {
323 for (unsigned long long i = 0ULL; i < z; ++i)
324 transition_();
325 }
326
327 bool operator==(const mersenne_twister_engine& rhs) const
328 {
[87f625f]329 if (i_ != rhs.i_)
330 return false;
331
[08be4a4]332 for (size_t i = 0; i < n; ++i)
333 {
334 if (state_[i] != rhs.state_[i])
335 return false;
336 }
337
338 return true;
339 }
340
341 bool operator!=(const mersenne_twister_engine& rhs) const
342 {
343 return !(*this == rhs);
344 }
345
346 template<class Char, class Traits>
347 basic_ostream<Char, Traits>& operator<<(basic_ostream<Char, Traits>& os) const
348 {
349 auto flags = os.flags();
350 os.flags(ios_base::dec | ios_base::left);
351
352 for (size_t j = n + 1; j > 1; --j)
353 {
354 os << state_[idx_(i_ - j - 1)];
355
356 if (j > 2)
357 os << os.widen(' ');
358 }
359
360 os.flags(flags);
361 return os;
362 }
363
364 template<class Char, class Traits>
365 basic_istream<Char, Traits>& operator>>(basic_istream<Char, Traits>& is) const
366 {
367 auto flags = is.flags();
368 is.flags(ios_base::dec);
369
370 for (size_t j = n + 1; j > 1; --j)
371 {
372 if (!(is >> state_[idx_(i_ - j - 1)]))
373 {
374 is.setstate(ios::failbit);
375 break;
376 }
377 }
378
379 is.flags(flags);
380 return is;
381 }
382
383 private:
384 result_type state_[n];
385 size_t i_;
386
387 static constexpr size_t k_ = static_cast<size_t>(w / 32);
388 result_type arr_[n * k_];
389
390 void transition_()
391 {
392 auto mask = (result_type{1} << r) - 1;
393 auto y = (state_[idx_(i_ - n)] & ~mask) | (state_[idx_(i_ + 1 - n)] & mask);
394 auto alpha = a * (y & 1);
395 state_[i_] = state_[idx_(i_ + m - n)] ^ (y >> 1) ^ alpha;
396
397 i_ = (i_ + 1) % n;
398 }
399
400 result_type generate_()
401 {
402 auto z1 = state_[i_] ^ ((state_[i_] >> u) & d);
403 auto z2 = z1 ^ (lshift_(z1, s) & b);
404 auto z3 = z2 ^ (lshift_(z2, t) & c);
405 auto z4 = z3 ^ (z3 >> l);
406
407 transition_();
408
409 return z4;
410 }
411
412 size_t idx_(size_t idx) const
413 {
414 return idx % n;
415 }
416
417 result_type lshift_(result_type val, size_t count)
418 {
419 return (val << count) % aux::pow2u(w);
420 }
421 };
[08e16de0]422
423 /**
424 * 26.5.3.3, class template subtract_with_carry_engine:
425 */
426
427 template<class UIntType, size_t w, size_t s, size_t r>
[e7a4f41]428 class subtract_with_carry_engine
429 {
430 // TODO: fix these
431 /* static_assert(0U < s); */
432 /* static_assert(s < r); */
433 /* static_assert(0U < w); */
434 /* static_assert(w <= numeric_limits<UIntType>::digits); */
435
436 public:
437 using result_type = UIntType;
438
439 static constexpr size_t word_size = w;
440 static constexpr size_t short_lag = s;
441 static constexpr size_t long_lag = r;
442
443 static constexpr result_type min()
444 {
445 return result_type{};
446 }
447
448 static constexpr result_type max()
449 {
450 return m_ - 1;
451 }
452
453 static constexpr result_type default_seed = 19780503U;
454
455 explicit subtract_with_carry_engine(result_type value = default_seed)
456 : state_{}, i_{}, carry_{}
457 {
458 seed(value);
459 }
460
461 template<class Seq>
462 explicit subtract_with_carry_engine(
463 enable_if_t<aux::is_seed_sequence_v<Seq, result_type>, Seq&> q
464 )
465 : state_{}, i_{}, carry_{}
466 {
467 seed(q);
468 }
469
470 void seed(result_type value = default_seed)
471 {
472 linear_congruential_engine<
473 result_type, 40014U, 0U, 2147483563U
474 > e{value == 0U ? default_seed : value};
475
476 auto n = aux::ceil(w / 32.0);
477 auto z = new result_type[n];
478
479 for (long long i = -r; i <= -1; ++i)
480 {
481 for (size_t i = 0; i < n; ++i)
482 z[i] = e() % aux::pow2u(32);
483
484 state_[idx_(i)] = result_type{};
485 for (size_t j = 0; j < n; ++j)
486 state_[idx_(i)] += z[j] * aux::pow2u(32 * j);
487 state_[idx_(i)] %= m_;
488 }
489
490 if (state_[idx_(-1)] == 0)
491 carry_ = 1;
492 else
493 carry_ = 0;
494
495 delete[] z;
496 }
497
498 template<class Seq>
499 void seed(
500 enable_if_t<aux::is_seed_sequence_v<Seq, result_type>, Seq&> q
501 )
502 {
503 auto k = aux::ceil(w / 32.0);
504 auto arr = new result_type[r * k];
505
506 q.generate(arr, arr + r * k);
507
508 for (long long i = -r; i <= -1; ++i)
509 {
510 state_[idx_(i)] = result_type{};
511 for (long long j = 0; j < k; ++j)
512 state_[idx_(i)] += arr[k * (i + r) + j] * aux::pow2(32 * j);
513 state_[idx_(i)] %= m_;
514 }
515
516 delete[] arr;
517
518 if (state_[idx_(-1)] == 0)
519 carry_ = 1;
520 else
521 carry_ = 0;
522 }
523
524 result_type operator()()
525 {
526 return generate_();
527 }
528
529 void discard(unsigned long long z)
530 {
531 for (unsigned long long i = 0ULL; i < z; ++i)
532 transition_();
533 }
534
535 bool operator==(const subtract_with_carry_engine& rhs) const
536 {
[87f625f]537 if (i_ != rhs.i_)
538 return false;
539
[e7a4f41]540 for (size_t i = 0; i < r; ++i)
541 {
542 if (state_[i] != rhs.state_[i])
543 return false;
544 }
545
546 return true;
547 }
548
549 bool operator!=(const subtract_with_carry_engine& rhs) const
550 {
551 return !(*this == rhs);
552 }
553
554 template<class Char, class Traits>
555 basic_ostream<Char, Traits>& operator<<(basic_ostream<Char, Traits>& os) const
556 {
557 auto flags = os.flags();
558 os.flags(ios_base::dec | ios_base::left);
559
560 for (size_t j = r + 1; j > 1; --j)
561 {
562 os << state_[idx_(i_ - j - 1)];
563 os << os.widen(' ');
564 }
565
566 os << carry_;
567
568 os.flags(flags);
569 return os;
570 }
571
572 template<class Char, class Traits>
573 basic_istream<Char, Traits>& operator>>(basic_istream<Char, Traits>& is) const
574 {
575 auto flags = is.flags();
576 is.flags(ios_base::dec);
577
578 for (size_t j = r + 1; j > 1; --j)
579 {
580 if (!(is >> state_[idx_(i_ - j - 1)]))
581 {
582 is.setstate(ios::failbit);
583 break;
584 }
585 }
586
587 if (!(is >> carry_))
588 is.setstate(ios::failbit);
589
590 is.flags(flags);
591 return is;
592 }
593
594 private:
595 result_type state_[r];
596 size_t i_;
597 uint8_t carry_;
598
599 static constexpr result_type m_ = aux::pow2u(w);
600
601 auto transition_()
602 {
603 auto y = static_cast<int64_t>(state_[idx_(i_ - s)]) - state_[idx_(i_ - r)] - carry_;
604 state_[i_] = y % m_;
605
606 i_ = (i_ + 1) % r;
607
608 return static_cast<result_type>(y % m_);
609 }
610
611 result_type generate_()
612 {
613 return transition_();
614 }
615
616 size_t idx_(size_t idx) const
617 {
618 return idx % r;
619 }
620 };
[08e16de0]621
622 /**
623 * 26.5.4.2, class template discard_block_engine:
624 */
625
626 template<class Engine, size_t p, size_t r>
[87f625f]627 class discard_block_engine
628 {
629 static_assert(0 < r);
630 static_assert(r <= p);
631
632 public:
633 using result_type = typename Engine::result_type;
634
635 static constexpr size_t block_size = p;
636 static constexpr size_t used_block = r;
637
638 static constexpr result_type min()
639 {
640 return Engine::min();
641 }
642
643 static constexpr result_type max()
644 {
645 return Engine::max();
646 }
647
648 discard_block_engine()
649 : engine_{}, n_{}
650 { /* DUMMY BODY */ }
651
652 explicit discard_block_engine(const Engine& e)
653 : engine_{e}, n_{}
654 { /* DUMMY BODY */ }
655
656 explicit discard_block_engine(Engine&& e)
657 : engine_{move(e)}, n_{}
658 { /* DUMMY BODY */ }
659
660 explicit discard_block_engine(result_type s)
661 : engine_{s}, n_{}
662 { /* DUMMY BODY */ }
663
664 template<class Seq>
665 explicit discard_block_engine(
666 enable_if_t<aux::is_seed_sequence_v<Seq, result_type>, Seq&> q
667 )
668 : engine_{q}, n_{}
669 { /* DUMMY BODY */ }
670
671 void seed()
672 {
673 engine_.seed();
674 }
675
676 void seed(result_type s)
677 {
678 engine_.seed(s);
679 }
680
681 template<class Seq>
682 void seed(
683 enable_if_t<aux::is_seed_sequence_v<Seq, result_type>, Seq&> q
684 )
685 {
686 engine_.seed(q);
687 }
688
689 result_type operator()()
690 {
691 if (n_ > static_cast<int>(r))
692 {
693 auto count = p - r;
694 for (size_t i = 0; i < count; ++i)
695 engine_();
696 n_ = 0;
697 }
698 ++n_;
699
700 return engine_();
701 }
702
703 void discard(unsigned long long z)
704 {
705 for (unsigned long long i = 0ULL; i < z; ++i)
706 operator()(); // We need to discard our (), not engine's.
707 }
708
709 const Engine& base() const noexcept
710 {
711 return engine_;
712 }
713
714 bool operator==(const discard_block_engine& rhs) const
715 {
716 return engine_ == rhs.engine_ && n_ == rhs.n_;
717 }
718
719 bool operator!=(const discard_block_engine& rhs) const
720 {
721 return !(*this == rhs);
722 }
723
724 template<class Char, class Traits>
725 basic_ostream<Char, Traits>& operator<<(basic_ostream<Char, Traits>& os) const
726 {
727 auto flags = os.flags();
728 os.flags(ios_base::dec | ios_base::left);
729
730 os << n_ << os.widen(' ') << engine_;
731
732 os.flags(flags);
733 return os;
734 }
735
736 template<class Char, class Traits>
737 basic_istream<Char, Traits>& operator>>(basic_istream<Char, Traits>& is) const
738 {
739 auto flags = is.flags();
740 is.flags(ios_base::dec);
741
742 if (!(is >> n_) || !(is >> engine_))
743 is.setstate(ios::failbit);
744
745 is.flags(flags);
746 return is;
747 }
748
749 private:
750 Engine engine_;
751 int n_;
752 };
[08e16de0]753
754 /**
755 * 26.5.4.3, class template independent_bits_engine:
756 */
757
758 template<class Engine, size_t w, class UIntType>
[87f625f]759 class independent_bits_engine
760 {
761 static_assert(0U < w);
762 /* static_assert(w <= numeric_limits<result_type>::digits); */
763
764 public:
765 using result_type = UIntType;
766
767 static constexpr result_type min()
768 {
769 return result_type{};
770 }
771
772 static constexpr result_type max()
773 {
774 return aux::pow2u(w) - 1;
775 }
776
777 independent_bits_engine()
778 : engine_{}
779 { /* DUMMY BODY */ }
780
781 explicit independent_bits_engine(const Engine& e)
782 : engine_{e}
783 { /* DUMMY BODY */ }
784
785 explicit independent_bits_engine(Engine&& e)
786 : engine_{move(e)}
787 { /* DUMMY BODY */ }
788
789 explicit independent_bits_engine(result_type s)
790 : engine_{s}
791 { /* DUMMY BODY */ }
792
793 template<class Seq>
794 explicit independent_bits_engine(
795 enable_if_t<aux::is_seed_sequence_v<Seq, result_type>, Seq&> q
796 )
797 : engine_{q}
798 { /* DUMMY BODY */ }
799
800 void seed()
801 {
802 engine_.seed();
803 }
804
805 void seed(result_type s)
806 {
807 engine_.seed(s);
808 }
809
810 template<class Seq>
811 void seed(
812 enable_if_t<aux::is_seed_sequence_v<Seq, result_type>, Seq&> q
813 )
814 {
815 engine_.seed(q);
816 }
817
818 result_type operator()()
819 {
820 /* auto r = engine_.max() - engine_.min() + 1; */
821 /* auto m = aux::floor(aux::log2(r)); */
822 // TODO:
823
824 return engine_();
825 }
826
827 void discard(unsigned long long z)
828 {
829 for (unsigned long long i = 0ULL; i < z; ++i)
830 operator()();
831 }
832
833 const Engine& base() const noexcept
834 {
835 return engine_;
836 }
837
838 bool operator==(const independent_bits_engine& rhs) const
839 {
840 return engine_ == rhs.engine_;
841 }
842
843 bool operator!=(const independent_bits_engine& rhs) const
844 {
845 return !(*this == rhs);
846 }
847
848 template<class Char, class Traits>
849 basic_ostream<Char, Traits>& operator<<(basic_ostream<Char, Traits>& os) const
850 {
851 return os << engine_;
852 }
853
854 template<class Char, class Traits>
855 basic_istream<Char, Traits>& operator>>(basic_istream<Char, Traits>& is) const
856 {
857 return is >> engine_;
858 }
859
860 private:
861 Engine engine_;
862 };
[08e16de0]863
864 /**
865 * 26.5.4.4, class template shiffle_order_engine:
866 */
867
868 template<class Engine, size_t k>
[87f625f]869 class shuffle_order_engine
870 {
871 static_assert(0U < k);
872
873 public:
874 using result_type = typename Engine::result_type;
875
876 static constexpr size_t table_size = k;
877
878 static constexpr result_type min()
879 {
880 return Engine::min();
881 }
882
883 static constexpr result_type max()
884 {
885 return Engine::max();
886 }
887
888 shuffle_order_engine()
889 : engine_{}
890 { /* DUMMY BODY */ }
891
892 explicit shuffle_order_engine(const Engine& e)
893 : engine_{e}
894 { /* DUMMY BODY */ }
895
896 explicit shuffle_order_engine(Engine&& e)
897 : engine_{move(e)}
898 { /* DUMMY BODY */ }
899
900 explicit shuffle_order_engine(result_type s)
901 : engine_{s}
902 { /* DUMMY BODY */ }
903
904 template<class Seq>
905 explicit shuffle_order_engine(
906 enable_if_t<aux::is_seed_sequence_v<Seq, result_type>, Seq&> q
907 )
908 : engine_{q}
909 { /* DUMMY BODY */ }
910
911 void seed()
912 {
913 engine_.seed();
914 }
915
916 void seed(result_type s)
917 {
918 engine_.seed(s);
919 }
920
921 template<class Seq>
922 void seed(
923 enable_if_t<aux::is_seed_sequence_v<Seq, result_type>, Seq&> q
924 )
925 {
926 engine_.seed(q);
927 }
928
929 result_type operator()()
930 {
931 // TODO:
932
933 return engine_();
934 }
935
936 void discard(unsigned long long z)
937 {
938 for (unsigned long long i = 0ULL; i < z; ++i)
939 operator()();
940 }
941
942 const Engine& base() const noexcept
943 {
944 return engine_;
945 }
946
947 bool operator==(const shuffle_order_engine& rhs) const
948 {
949 return engine_ == rhs.engine_;
950 }
951
952 bool operator!=(const shuffle_order_engine& rhs) const
953 {
954 return !(*this == rhs);
955 }
956
957 template<class Char, class Traits>
958 basic_ostream<Char, Traits>& operator<<(basic_ostream<Char, Traits>& os) const
959 {
960 return os << engine_;
961 }
962
963 template<class Char, class Traits>
964 basic_istream<Char, Traits>& operator>>(basic_istream<Char, Traits>& is) const
965 {
966 return is >> engine_;
967 }
968
969 private:
970 Engine engine_;
971 result_type y_;
972 result_type table_[k];
973 };
[08e16de0]974
975 /**
976 * 26.5.5, engines and engine adaptors with predefined
977 * parameters:
978 * TODO: check their requirements for testing
979 */
980
981 using minstd_rand0 = linear_congruential_engine<uint_fast32_t, 16807, 0, 2147483647>;
982 using minstd_rand = linear_congruential_engine<uint_fast32_t, 48271, 0, 2147483647>;
983 using mt19937 = mersenne_twister_engine<
984 uint_fast32_t, 32, 624, 397, 31, 0x9908b0df, 11, 0xffffffff, 7,
985 0x9d2c5680, 15, 0xefc60000, 18, 1812433253
986 >;
987 using mt19937_64 = mersenne_twister_engine<
988 uint_fast64_t, 64, 312, 156, 31, 0xb5026f5aa96619e9, 29,
989 0x5555555555555555, 17, 0x71d67fffeda60000, 37, 0xfff7eee000000000,
990 43, 6364136223846793005
991 >;
992 using ranlux24_base = subtract_with_carry_engine<uint_fast32_t, 24, 10, 24>;
993 using ranlux48_base = subtract_with_carry_engine<uint_fast64_t, 48, 5, 12>;
994 using ranlux24 = discard_block_engine<ranlux24_base, 223, 23>;
995 using ranlux48 = discard_block_engine<ranlux48_base, 389, 11>;
996 using knuth_b = shuffle_order_engine<minstd_rand0, 256>;
997
998 using default_random_engine = minstd_rand0;
999
1000 /**
1001 * 26.5.6, class random_device:
1002 */
1003
1004 class random_device
1005 {
1006 using result_type = unsigned int;
1007
1008 static constexpr result_type min()
1009 {
1010 return numeric_limits<result_type>::min();
1011 }
1012
1013 static constexpr result_type max()
1014 {
1015 return numeric_limits<result_type>::max();
1016 }
1017
1018 explicit random_device(const string& token = "")
1019 {
1020 /**
1021 * Note: token can be used to choose between
1022 * random generators, but HelenOS only
1023 * has one :/
1024 * Also note that it is implementation
1025 * defined how this class generates
1026 * random numbers and I decided to use
1027 * time seeding with C stdlib random,
1028 * - feel free to change it if you know
1029 * something better.
1030 */
1031 hel::srandom(hel::time(nullptr));
1032 }
1033
1034 result_type operator()()
1035 {
1036 return hel::random();
1037 }
1038
1039 double entropy() const noexcept
1040 {
1041 return 0.0;
1042 }
1043
1044 random_device(const random_device&) = delete;
1045 random_device& operator=(const random_device&) = delete;
1046 };
1047
1048 /**
1049 * 26.5.7.1, class seed_seq:
1050 */
1051
1052 class seed_seq
1053 {
1054 public:
1055 using result_type = uint_least32_t;
1056
1057 seed_seq()
1058 : vec_{}
1059 { /* DUMMY BODY */ }
1060
1061 template<class T>
1062 seed_seq(initializer_list<T> init)
1063 : seed_seq(init.begin(), init.end())
1064 { /* DUMMY BODY */ }
1065
1066 template<class InputIterator>
1067 seed_seq(InputIterator first, InputIterator last)
1068 : vec_{}
1069 {
1070 while (first != last)
1071 vec_.push_back(*first++ % aux::pow2(32));
1072 }
1073
1074 template<class RandomAccessGenerator>
1075 void generate(RandomAccessGenerator first,
1076 RandomAccessGenerator last)
1077 {
1078 if (first == last)
1079 return;
1080
1081 // TODO: research this
1082 }
1083
1084 size_t size() const
1085 {
1086 return vec_.size();
1087 }
1088
1089 template<class OutputIterator>
1090 void param(OutputIterator dest) const
1091 {
1092 for (const auto& x: vec_)
1093 *dest++ = x;
1094 }
1095
1096 seed_seq(const seed_seq&) = delete;
1097 seed_seq& operator=(const seed_seq&) = delete;
1098
1099 private:
1100 vector<result_type> vec_;
1101 };
1102
1103 /**
1104 * 26.5.7.2, function template generate_canonical:
1105 */
1106
1107 template<class RealType, size_t bits, class URNG>
1108 RealType generate_canonical(URNG& g);
1109
1110 /**
1111 * 26.5.8.2.1, class template uniform_int_distribution:
1112 */
1113
1114 template<class IntType = int>
1115 class uniform_int_distribution;
1116
1117 /**
1118 * 26.5.8.2.2, class template uniform_real_distribution:
1119 */
1120
1121 template<class RealType = double>
1122 class uniform_real_distribution;
1123
1124 /**
1125 * 26.5.8.3.1, class bernoulli_distribution:
1126 */
1127
1128 class bernoulli_distribution;
1129
1130 /**
1131 * 26.5.8.3.2, class template binomial_distribution:
1132 */
1133
1134 template<class IntType = int>
1135 class binomial_distribution;
1136
1137 /**
1138 * 26.5.8.3.3, class template geometric_distribution:
1139 */
1140
1141 template<class IntType = int>
1142 class geometric_distribution;
1143
1144 /**
1145 * 26.5.8.3.4, class template negative_binomial_distribution:
1146 */
1147
1148 template<class IntType = int>
1149 class negative_binomial_distribution;
1150
1151 /**
1152 * 26.5.8.4.1, class template poisson_distribution:
1153 */
1154
1155 template<class IntType = int>
1156 class poisson_distribution;
1157
1158 /**
1159 * 26.5.8.4.2, class template exponential_distribution:
1160 */
1161
1162 template<class RealType = double>
1163 class exponential_distribution;
1164
1165 /**
1166 * 26.5.8.4.3, class template gamma_distribution:
1167 */
1168
1169 template<class RealType = double>
1170 class gamma_distribution;
1171
1172 /**
1173 * 26.5.8.4.4, class template weibull_distribution:
1174 */
1175
1176 template<class RealType = double>
1177 class weibull_distribution;
1178
1179 /**
1180 * 26.5.8.4.5, class template extreme_value_distribution:
1181 */
1182
1183 template<class RealType = double>
1184 class extreme_value_distribution;
1185
1186 /**
1187 * 26.5.8.5.1, class template normal_distribution:
1188 */
1189
1190 template<class RealType = double>
1191 class normal_distribution;
1192
1193 /**
1194 * 26.5.8.5.2, class template lognormal_distribution:
1195 */
1196
1197 template<class RealType = double>
1198 class lognormal_distribution;
1199
1200 /**
1201 * 26.5.8.5.3, class template chi_squared_distribution:
1202 */
1203
1204 template<class RealType = double>
1205 class chi_squared_distribution;
1206
1207 /**
1208 * 26.5.8.5.4, class template cauchy_distribution:
1209 */
1210
1211 template<class RealType = double>
1212 class cauchy_distribution;
1213
1214 /**
1215 * 26.5.8.5.5, class template fisher_f_distribution:
1216 */
1217
1218 template<class RealType = double>
1219 class fisher_f_distribution;
1220
1221 /**
1222 * 26.5.8.5.6, class template student_t_distribution:
1223 */
1224
1225 template<class RealType = double>
1226 class student_t_distribution;
1227
1228 /**
1229 * 26.5.8.6.1, class template discrete_distribution:
1230 */
1231
1232 template<class IntType = int>
1233 class discrete_distribution;
1234
1235 /**
1236 * 26.5.8.6.2, class template piecewise_constant_distribution:
1237 */
1238
1239 template<class RealType = double>
1240 class piecewise_constant_distribution;
1241
1242 /**
1243 * 26.5.8.6.3, class template piecewise_linear_distribution:
1244 */
1245
1246 template<class RealType = double>
1247 class piecewise_linear_distribution;
1248}
1249
1250#endif
Note: See TracBrowser for help on using the repository browser.