malachite_base/options/
random.rs

1// Copyright © 2026 Mikhail Hogrefe
2//
3// This file is part of Malachite.
4//
5// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
6// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
7// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
8
9use crate::bools::random::{WeightedRandomBools, weighted_random_bools};
10use crate::random::Seed;
11
12/// Generates random [`Option`]s except `None`, with values from a given random iterator.
13///
14/// This `struct` is created by [`random_somes`]; see its documentation for more.
15#[derive(Clone, Debug)]
16pub struct RandomSomes<I: Iterator> {
17    xs: I,
18}
19
20impl<I: Iterator> Iterator for RandomSomes<I> {
21    type Item = Option<I::Item>;
22
23    #[inline]
24    fn next(&mut self) -> Option<Option<I::Item>> {
25        Some(self.xs.next())
26    }
27}
28
29/// Generates random [`Option`]s except `None`, with values from a given random iterator.
30///
31/// The values have the same distribution as the values generated by the given iterator: If $Q(x)$
32/// is the probability of $x$ being generated by `xs`, then
33///
34/// $P(\operatorname{Some}(x)) = Q(x)$.
35///
36/// `xs` must be infinite.
37///
38/// The output length is infinite.
39///
40/// # Worst-case complexity per iteration
41/// $T(i) = O(T^\prime(i))$
42///
43/// $M(i) = O(M^\prime(i))$
44///
45/// where $T$ is time, $M$ is additional memory, $i$ is the iteration number, and $T^\prime$ and
46/// $M^\prime$ are the time and memory functions of `xs`.
47///
48/// # Examples
49/// ```
50/// use malachite_base::iterators::prefix_to_string;
51/// use malachite_base::num::random::random_primitive_ints;
52/// use malachite_base::options::random::random_somes;
53/// use malachite_base::random::EXAMPLE_SEED;
54/// use malachite_base::strings::ToDebugString;
55///
56/// assert_eq!(
57///     prefix_to_string(
58///         random_somes(random_primitive_ints::<u8>(EXAMPLE_SEED)).map(|x| x.to_debug_string()),
59///         5
60///     ),
61///     "[Some(113), Some(239), Some(69), Some(108), Some(228), ...]",
62/// )
63/// ```
64pub const fn random_somes<I: Iterator>(xs: I) -> RandomSomes<I> {
65    RandomSomes { xs }
66}
67
68/// Generates random [`Option`]s with values from a given random iterator.
69///
70/// We don't use [`WithSpecialValue`](crate::iterators::WithSpecialValue) here because that requires
71/// `I::Item` to be cloneable. The "special value" in this case, `None`, can be produced on demand
72/// without any cloning.
73///
74/// This `struct` is created by [`random_options`]; see its documentation for more.
75#[derive(Clone, Debug)]
76pub struct RandomOptions<I: Iterator> {
77    bs: WeightedRandomBools,
78    xs: I,
79}
80
81impl<I: Iterator> Iterator for RandomOptions<I> {
82    type Item = Option<I::Item>;
83
84    #[inline]
85    fn next(&mut self) -> Option<Option<I::Item>> {
86        Some(if self.bs.next().unwrap() {
87            self.xs.next()
88        } else {
89            None
90        })
91    }
92}
93
94/// Generates random [`Option`]s with values from a given random iterator.
95///
96/// The probability of generating `None` is specified by $p$ = `none_p_numerator /
97/// none_p_denominator`. If a `Some` is generated, its values have the same distribution as the
98/// values generated by the given iterator.
99///
100/// If $Q(x)$ is the probability of $x$ being generated by `xs`, then
101///
102/// $P(\text{None}) = p$
103///
104/// $P(\operatorname{Some}(x)) = (1-p)Q(x)$
105///
106/// `xs` must be infinite.
107///
108/// The output length is infinite.
109///
110/// # Expected complexity per iteration
111/// $T(i) = O(T^\prime(i))$
112///
113/// $M(i) = O(M^\prime(i))$
114///
115/// where $T$ is time, $M$ is additional memory, $i$ is the iteration number, and $T^\prime$ and
116/// $M^\prime$ are the time and memory functions of `xs`: each iteration adds only the weighted coin
117/// flip that decides between `None` and a wrapped value.
118///
119/// # Panics
120/// Panics if `none_p_denominator` is 0 or `none_p_numerator > none_p_denominator`.
121///
122/// # Examples
123/// ```
124/// use malachite_base::iterators::prefix_to_string;
125/// use malachite_base::num::random::random_primitive_ints;
126/// use malachite_base::options::random::random_options;
127/// use malachite_base::random::EXAMPLE_SEED;
128/// use malachite_base::strings::ToDebugString;
129///
130/// assert_eq!(
131///     prefix_to_string(
132///         random_options(EXAMPLE_SEED, 1, 2, &random_primitive_ints::<u8>)
133///             .map(|x| x.to_debug_string()),
134///         10
135///     ),
136///     "[Some(85), Some(11), Some(136), None, Some(200), None, Some(235), Some(134), Some(203), \
137///     None, ...]"
138/// )
139/// ```
140pub fn random_options<I: Iterator>(
141    seed: Seed,
142    none_p_numerator: u64,
143    none_p_denominator: u64,
144    xs_gen: &dyn Fn(Seed) -> I,
145) -> RandomOptions<I> {
146    RandomOptions {
147        bs: weighted_random_bools(
148            seed.fork("bs"),
149            none_p_denominator - none_p_numerator,
150            none_p_denominator,
151        ),
152        xs: xs_gen(seed.fork("xs")),
153    }
154}
malachite_base/options/random.rs

malachite_base/options/
random.rs
