1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

use crate::num::arithmetic::traits::Parity;
use crate::num::random::geometric::SimpleRational;
use crate::num::random::{random_unsigneds_less_than, RandomUnsignedsLessThan};
use crate::random::Seed;
use rand::Rng;
use rand_chacha::ChaCha20Rng;

/// Uniformly generates random [`bool`]s.
///
/// This `struct` is created by [`random_bools`]; see its documentation for more.
#[derive(Clone, Debug)]
pub struct RandomBools {
    rng: ChaCha20Rng,
    x: u32,
    bits_left: u8,
}

impl Iterator for RandomBools {
    type Item = bool;

    #[inline]
    fn next(&mut self) -> Option<bool> {
        if self.bits_left == 0 {
            self.x = self.rng.gen();
            self.bits_left = 31;
        } else {
            self.x >>= 1;
            self.bits_left -= 1;
        }
        Some(self.x.odd())
    }
}

/// Uniformly generates random [`bool`]s.
///
/// $P(\text{false}) = P(\text{true}) = \frac{1}{2}$.
///
/// The output length is infinite.
///
/// # Worst-case complexity per iteration
/// Constant time and additional memory.
///
/// # Examples
/// ```
/// use malachite_base::bools::random::random_bools;
/// use malachite_base::iterators::prefix_to_string;
/// use malachite_base::random::EXAMPLE_SEED;
///
/// assert_eq!(
///     prefix_to_string(random_bools(EXAMPLE_SEED), 10),
///     "[true, false, false, false, true, true, true, false, true, true, ...]"
/// )
/// ```
///
/// # Notes
/// The resulting iterator uses every random bit generated by the PRNG, unlike some implementations
/// which only use one bit out of 32 or 64.
#[inline]
pub fn random_bools(seed: Seed) -> RandomBools {
    RandomBools {
        rng: seed.get_rng(),
        x: 0,
        bits_left: 0,
    }
}

/// Generates random [`bool`]s, with a fixed probability of generating `true`.
///
/// This `struct` is created by [`weighted_random_bools`]; see its documentation for more.
#[derive(Clone, Debug)]
pub struct WeightedRandomBools {
    numerator: u64,
    xs: RandomUnsignedsLessThan<u64>,
}

impl Iterator for WeightedRandomBools {
    type Item = bool;

    #[inline]
    fn next(&mut self) -> Option<bool> {
        Some(self.xs.next().unwrap() < self.numerator)
    }
}

/// Generates random [`bool`]s, with a fixed probability of generating `true`.
///
/// Let $n_p$ be `p_numerator`, $d_p$ be `p_denominator`, and let $p=n_p/d_p$. Then
///
/// $P(\text{true}) = p$,
///
/// $P(\text{false}) = 1-p$.
///
/// The output length is infinite.
///
/// # Panics
/// Panics if `p_denominator` is 0 or `p_numerator > p_denominator`.
///
/// # Expected complexity per iteration
/// Constant time and additional memory.
///
/// # Examples
/// ```
/// use malachite_base::bools::random::weighted_random_bools;
/// use malachite_base::iterators::prefix_to_string;
/// use malachite_base::random::EXAMPLE_SEED;
///
/// assert_eq!(
///     prefix_to_string(weighted_random_bools(EXAMPLE_SEED, 3, 4), 10),
///     "[true, true, false, true, false, false, true, false, true, true, ...]"
/// )
/// ```
pub fn weighted_random_bools(
    seed: Seed,
    p_numerator: u64,
    p_denominator: u64,
) -> WeightedRandomBools {
    assert!(p_numerator <= p_denominator);
    let p = SimpleRational::new(p_numerator, p_denominator);
    WeightedRandomBools {
        numerator: p.n,
        xs: random_unsigneds_less_than(seed, p.d),
    }
}