malachite_base/sets/

random.rs

// Copyright © 2026 Mikhail Hogrefe
//
// This file is part of Malachite.
//
// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.

use crate::num::conversion::traits::ExactFrom;
use crate::num::random::geometric::{
    GeometricRandomNaturalValues, geometric_random_unsigned_inclusive_range,
    geometric_random_unsigneds,
};
use crate::num::random::{
    RandomUnsignedInclusiveRange, RandomUnsignedRange, random_unsigned_inclusive_range,
    random_unsigned_range,
};
use crate::random::Seed;
#[cfg(not(feature = "test_build"))]
use alloc::collections::BTreeSet;
use core::hash::Hash;
#[cfg(not(feature = "test_build"))]
use hashbrown::HashSet;
#[cfg(feature = "test_build")]
use std::collections::{BTreeSet, HashSet};

/// Generates random [`HashSet`]s of a fixed length, where the [`Vec`]s have no repeated elements,
/// and the elements are in ascending order.
///
/// This `struct` is created by [`random_hash_sets_fixed_length`]; see its documentation for more.
#[derive(Clone, Debug)]
pub struct RandomHashSetsFixedLength<I: Iterator>
where
    I::Item: Eq + Hash,
{
    len: usize,
    xs: I,
}

impl<I: Iterator> Iterator for RandomHashSetsFixedLength<I>
where
    I::Item: Eq + Hash,
{
    type Item = HashSet<I::Item>;

    #[inline]
    fn next(&mut self) -> Option<HashSet<I::Item>> {
        let mut set = HashSet::new();
        while set.len() < self.len {
            set.insert(self.xs.next().unwrap());
        }
        Some(set)
    }
}

/// Randomly generates [`HashSet`]s of a given length.
///
/// The input iterator must generate at least `len` distinct elements; otherwise, this iterator will
/// hang.
///
/// $$
/// P((x\_i)\_{i=0}^{n-1}) = n!\prod\_{i=0}^{n-1}P(x\_i).
/// $$
///
/// If `len` is 0, the output consists of the empty set, repeated.
///
/// `xs` must be infinite.
///
/// # Expected complexity per iteration
/// $T(i) = O(\ell T^\prime(i))$
///
/// $M(i) = O(\ell M^\prime(i))$
///
/// where $T$ is time, $M$ is additional memory, $i$ is the iteration number, $T^\prime$ and
/// $M^\prime$ are the time and memory functions of `xs`, and $\ell$ is `len`.
///
/// If `xs` can repeat values, extra draws are needed to reach the required number of distinct
/// elements, and an iteration fails to terminate if fewer distinct values are reachable than the
/// requested length.
///
/// # Expected complexity per iteration
/// $T(i) = O(m T^\prime(i))$
///
/// $M(i) = O(m M^\prime(i))$
///
/// where $T$ is time, $M$ is additional memory, $i$ is the iteration number, $T^\prime$ and
/// $M^\prime$ are the time and memory functions of the iterators produced by `xs_gen`, and $m$ is
/// `mean_length_numerator / mean_length_denominator`.
///
/// If `xs` can repeat values, extra draws are needed to reach the required number of distinct
/// elements, and an iteration fails to terminate if fewer distinct values are reachable than the
/// requested length.
///
/// # Examples
/// ```
/// use itertools::Itertools;
/// use malachite_base::num::random::random_unsigned_inclusive_range;
/// use malachite_base::random::EXAMPLE_SEED;
/// use malachite_base::sets::random::random_hash_sets_fixed_length;
/// use maplit::hashset;
///
/// let xss = random_hash_sets_fixed_length(
///     2,
///     random_unsigned_inclusive_range::<u32>(EXAMPLE_SEED, 1, 100),
/// )
/// .take(10)
/// .collect_vec();
/// assert_eq!(
///     xss,
///     &[
///         hashset! {24, 95},
///         hashset! {71, 99},
///         hashset! {53, 93},
///         hashset! {34, 85},
///         hashset! {2, 48},
///         hashset! {11, 55},
///         hashset! {18, 48},
///         hashset! {90, 93},
///         hashset! {67, 93},
///         hashset! {93, 95}
///     ]
/// );
/// ```
#[inline]
pub fn random_hash_sets_fixed_length<I: Iterator>(len: u64, xs: I) -> RandomHashSetsFixedLength<I>
where
    I::Item: Eq + Hash,
{
    RandomHashSetsFixedLength {
        len: usize::exact_from(len),
        xs,
    }
}

/// Generates random [`HashSet`]s with lengths from an iterator.
#[derive(Clone, Debug)]
pub struct RandomHashSets<T: Eq + Hash, I: Iterator<Item = u64>, J: Iterator<Item = T>> {
    lengths: I,
    xs: J,
}

impl<T: Eq + Hash, I: Iterator<Item = u64>, J: Iterator<Item = T>> Iterator
    for RandomHashSets<T, I, J>
{
    type Item = HashSet<T>;

    fn next(&mut self) -> Option<HashSet<T>> {
        let len = usize::exact_from(self.lengths.next().unwrap());
        let mut set = HashSet::new();
        while set.len() < len {
            set.insert(self.xs.next().unwrap());
        }
        Some(set)
    }
}

/// Generates random [`HashSet`]s using elements from an iterator and with lengths from another
/// iterator.
///
/// The input iterator must generate at least many distinct elements as any number generated by the
/// lengths iterator; otherwise, this iterator will hang.
///
/// $$
/// P((x\_i)\_{i=0}^{n-1}) = n!P(n)\prod\_{i=0}^{n-1}P(x\_i).
/// $$
///
/// `lengths` and `xs` must be infinite.
///
/// # Expected complexity per iteration
/// $T(i) = O(T^{\prime\prime}(i) + \ell T^\prime(i))$
///
/// $M(i) = O(M^{\prime\prime}(i) + \ell M^\prime(i))$
///
/// where $T$ is time, $M$ is additional memory, $i$ is the iteration number, $T^\prime$ and
/// $M^\prime$ are the time and memory functions of the iterators produced by `xs_gen`,
/// $T^{\prime\prime}$ and $M^{\prime\prime}$ are the time and memory functions of `lengths`, and
/// $\ell$ is the $i$th generated length.
///
/// If `xs` can repeat values, extra draws are needed to reach the required number of distinct
/// elements, and an iteration fails to terminate if fewer distinct values are reachable than the
/// requested length.
///
/// # Examples
/// ```
/// use itertools::Itertools;
/// use malachite_base::num::random::random_primitive_ints;
/// use malachite_base::random::EXAMPLE_SEED;
/// use malachite_base::sets::random::random_hash_sets_from_length_iterator;
/// use malachite_base::vecs::random_values_from_vec;
/// use maplit::hashset;
///
/// let xs = random_hash_sets_from_length_iterator(
///     EXAMPLE_SEED,
///     &|seed| random_values_from_vec(seed, vec![0, 2, 4]),
///     &random_primitive_ints::<u8>,
/// );
/// let values = xs.take(20).collect_vec();
/// assert_eq!(
///     values,
///     &[
///         hashset! {11, 85},
///         hashset! {134, 136, 200, 235},
///         hashset! {203, 223},
///         hashset! {38, 177, 217, 235},
///         hashset! {32, 162, 166, 234},
///         hashset! {30, 218},
///         hashset! {},
///         hashset! {90, 106},
///         hashset! {},
///         hashset! {9, 151, 204, 216},
///         hashset! {78, 97, 213, 253},
///         hashset! {39, 91},
///         hashset! {170, 175, 191, 232},
///         hashset! {2, 233},
///         hashset! {22, 35, 198, 217},
///         hashset! {17, 32, 114, 173},
///         hashset! {65, 114, 121, 222},
///         hashset! {},
///         hashset! {25, 144, 148, 173},
///         hashset! {}
///     ]
/// );
/// ```
#[inline]
pub fn random_hash_sets_from_length_iterator<
    T: Eq + Hash,
    I: Iterator<Item = u64>,
    J: Iterator<Item = T>,
>(
    seed: Seed,
    lengths_gen: &dyn Fn(Seed) -> I,
    xs_gen: &dyn Fn(Seed) -> J,
) -> RandomHashSets<T, I, J> {
    RandomHashSets {
        lengths: lengths_gen(seed.fork("lengths")),
        xs: xs_gen(seed.fork("xs")),
    }
}

/// Generates random [`HashSet`]s using elements from an iterator.
///
/// The lengths of the [`HashSet`]s are sampled from a geometric distribution with a specified mean
/// $m$, equal to `mean_length_numerator / mean_length_denominator`. $m$ must be greater than 0.
///
/// Strictly speaking, the input iterator must generate infinitely many distinct elements. In
/// practice it only needs to generate $k$ distinct elements, where $k$ is the largest length
/// actually sampled from the geometric distribution. For example, if `mean_length_numerator /
/// mean_length_denominator` is significantly lower than 256, then it's ok to use
/// `random_unsigneds::<u8>`.
///
/// $$
/// P((x\_i)\_{i=0}^{n-1}) = n!P_g(n)\prod\_{i=0}^{n-1}P(x\_i),
/// $$
/// where $P_g(n)$ is the probability function described in [`geometric_random_unsigneds`].
///
/// `xs_gen` must be infinite.
///
/// # Expected complexity per iteration
/// $T(i) = O(m T^\prime(i))$
///
/// $M(i) = O(m M^\prime(i))$
///
/// where $T$ is time, $M$ is additional memory, $i$ is the iteration number, $T^\prime$ and
/// $M^\prime$ are the time and memory functions of `xs`, and $m$ is `mean_length_numerator /
/// mean_length_denominator`.
///
/// # Panics
/// Panics if `mean_length_numerator` or `mean_length_denominator` are zero, or, if after being
/// reduced to lowest terms, their sum is greater than or equal to $2^{64}$.
///
/// # Examples
/// ```
/// use itertools::Itertools;
/// use malachite_base::num::random::random_primitive_ints;
/// use malachite_base::random::EXAMPLE_SEED;
/// use malachite_base::sets::random::random_hash_sets;
/// use maplit::hashset;
///
/// let xs = random_hash_sets(EXAMPLE_SEED, &random_primitive_ints::<u8>, 4, 1);
/// let values = xs.take(20).collect_vec();
/// assert_eq!(
///     values,
///     &[
///         hashset! {},
///         hashset! {11, 32, 38, 85, 134, 136, 162, 166, 177, 200, 203, 217, 223, 235},
///         hashset! {30, 90, 218, 234},
///         hashset! {9, 106, 204, 216},
///         hashset! {151},
///         hashset! {},
///         hashset! {78, 91, 97, 213, 253},
///         hashset! {39, 191},
///         hashset! {170, 175, 232, 233},
///         hashset! {},
///         hashset! {2, 22, 35, 114, 198, 217},
///         hashset! {},
///         hashset! {},
///         hashset! {17, 25, 32, 65, 79, 114, 121, 144, 148, 173, 222},
///         hashset! {52, 69, 73, 91, 115, 137, 153, 178},
///         hashset! {},
///         hashset! {34, 95, 112},
///         hashset! {},
///         hashset! {106, 130, 167, 168, 197},
///         hashset! {86, 101, 122, 150, 172, 177, 207, 218, 221}
///     ]
/// );
/// ```
#[inline]
pub fn random_hash_sets<I: Iterator>(
    seed: Seed,
    xs_gen: &dyn Fn(Seed) -> I,
    mean_length_numerator: u64,
    mean_length_denominator: u64,
) -> RandomHashSets<I::Item, GeometricRandomNaturalValues<u64>, I>
where
    I::Item: Eq + Hash,
{
    random_hash_sets_from_length_iterator(
        seed,
        &|seed_2| {
            geometric_random_unsigneds(seed_2, mean_length_numerator, mean_length_denominator)
        },
        xs_gen,
    )
}

/// Generates random [`HashSet`]s with a minimum length, using elements from an iterator.
///
/// Strictly speaking, the input iterator must generate infinitely many distinct elements. In
/// practice it only needs to generate $k$ distinct elements, where $k$ is the largest length
/// actually sampled from the geometric distribution. For example, if `mean_length_numerator /
/// mean_length_denominator` is significantly lower than 256, then it's ok to use
/// `random_unsigneds::<u8>`.
///
/// $$
/// P((x\_i)\_{i=0}^{n-1}) = n!P_g(n)\prod\_{i=0}^{n-1}P(x\_i),
/// $$
/// where $P_g(n)$ is the probability function described in
/// [`geometric_random_unsigned_inclusive_range`] with $a$ equal to `min_length` and `b` to
/// `u64::MAX`.
///
/// `xs_gen` must be infinite.
///
/// # Expected complexity per iteration
/// $T(i) = O(m T^\prime(i))$
///
/// $M(i) = O(m M^\prime(i))$
///
/// where $T$ is time, $M$ is additional memory, $i$ is the iteration number, $T^\prime$ and
/// $M^\prime$ are the time and memory functions of the iterators produced by `xs_gen`, and $m$ is
/// `mean_length_numerator / mean_length_denominator`.
///
/// If `xs` can repeat values, extra draws are needed to reach the required number of distinct
/// elements, and an iteration fails to terminate if fewer distinct values are reachable than the
/// requested length.
///
/// # Panics
/// Panics if `mean_length_numerator` or `mean_length_denominator` are zero, if their ratio is less
/// than or equal to `min_length`, or if they are too large and manipulating them leads to
/// arithmetic overflow.
///
/// # Examples
/// ```
/// use itertools::Itertools;
/// use malachite_base::num::random::random_primitive_ints;
/// use malachite_base::random::EXAMPLE_SEED;
/// use malachite_base::sets::random::random_hash_sets_min_length;
/// use maplit::hashset;
///
/// let xs = random_hash_sets_min_length(EXAMPLE_SEED, 2, &random_primitive_ints::<u8>, 6, 1);
/// let values = xs.take(20).collect_vec();
/// assert_eq!(
///     values,
///     &[
///         hashset! {11, 85},
///         hashset! {
///             30, 32, 38, 90, 134, 136, 162, 166, 177, 200, 203, 217, 218, 223, 234, 235
///         },
///         hashset! {9, 106, 151, 204, 213, 216},
///         hashset! {39, 78, 91, 97, 191, 253},
///         hashset! {170, 175, 232},
///         hashset! {2, 233},
///         hashset! {17, 22, 32, 35, 114, 198, 217},
///         hashset! {65, 114, 121, 173},
///         hashset! {25, 79, 144, 148, 173, 222},
///         hashset! {52, 115},
///         hashset! {34, 69, 73, 91, 112, 137, 153, 178},
///         hashset! {95, 106},
///         hashset! {167, 197},
///         hashset! {74, 86, 101, 115, 122, 130, 150, 168, 172, 177, 207, 218, 221},
///         hashset! {9, 48, 52, 109, 123, 133, 159, 201, 247, 250},
///         hashset! {196, 235},
///         hashset! {40, 68, 97, 104, 190},
///         hashset! {7, 216},
///         hashset! {11, 24, 43, 112, 157, 216, 217},
///         hashset! {29, 51, 55, 65, 84, 89, 103, 135, 191, 206, 211}
///     ]
/// );
/// ```
#[inline]
pub fn random_hash_sets_min_length<I: Iterator>(
    seed: Seed,
    min_length: u64,
    xs_gen: &dyn Fn(Seed) -> I,
    mean_length_numerator: u64,
    mean_length_denominator: u64,
) -> RandomHashSets<I::Item, GeometricRandomNaturalValues<u64>, I>
where
    I::Item: Eq + Hash,
{
    random_hash_sets_from_length_iterator(
        seed,
        &|seed_2| {
            geometric_random_unsigned_inclusive_range(
                seed_2,
                min_length,
                u64::MAX,
                mean_length_numerator,
                mean_length_denominator,
            )
        },
        xs_gen,
    )
}

/// Generates random [`HashSet`]s with lengths in $[a, b)$, using elements from an iterator.
///
/// The lengths of the [`HashSet`]s are sampled from a uniform distribution on $[a, b)$. $a$ must be
/// less than $b$.
///
/// The input iterator must generate at least $b$ distinct elements.
///
/// $$
/// P((x\_i)\_{i=0}^{n-1}, a, b) = \frac{n!}{b - a}\prod\_{i=0}^{n-1}P(x\_i).
/// $$
///
/// `xs_gen` must be infinite.
///
/// # Expected complexity per iteration
/// $T(i) = O(b T^\prime(i))$
///
/// $M(i) = O(b M^\prime(i))$
///
/// where $T$ is time, $M$ is additional memory, $i$ is the iteration number, $T^\prime$ and
/// $M^\prime$ are the time and memory functions of the iterators produced by `xs_gen`, and $b$ is
/// `b`.
///
/// If `xs` can repeat values, extra draws are needed to reach the required number of distinct
/// elements, and an iteration fails to terminate if fewer distinct values are reachable than the
/// requested length.
///
/// # Panics
/// Panics if $a \geq b$.
///
/// # Examples
/// ```
/// use itertools::Itertools;
/// use malachite_base::num::random::random_primitive_ints;
/// use malachite_base::random::EXAMPLE_SEED;
/// use malachite_base::sets::random::random_hash_sets_length_range;
/// use maplit::hashset;
///
/// let xs = random_hash_sets_length_range(EXAMPLE_SEED, 2, 5, &random_primitive_ints::<u8>);
/// let values = xs.take(20).collect_vec();
/// assert_eq!(
///     values,
///     &[
///         hashset! {11, 85, 136},
///         hashset! {134, 200, 203, 235},
///         hashset! {38, 223, 235},
///         hashset! {32, 162, 177, 217},
///         hashset! {30, 166, 218, 234},
///         hashset! {9, 90, 106},
///         hashset! {204, 216},
///         hashset! {97, 151, 213},
///         hashset! {78, 253},
///         hashset! {39, 91, 175, 191},
///         hashset! {2, 170, 232, 233},
///         hashset! {22, 35, 217},
///         hashset! {17, 32, 114, 198},
///         hashset! {65, 114, 173},
///         hashset! {25, 121, 173, 222},
///         hashset! {79, 115, 144, 148},
///         hashset! {52, 69, 73, 137},
///         hashset! {91, 153},
///         hashset! {34, 95, 112, 178},
///         hashset! {106, 167}
///     ]
/// );
/// ```
#[inline]
pub fn random_hash_sets_length_range<I: Iterator>(
    seed: Seed,
    a: u64,
    b: u64,
    xs_gen: &dyn Fn(Seed) -> I,
) -> RandomHashSets<I::Item, RandomUnsignedRange<u64>, I>
where
    I::Item: Eq + Hash,
{
    random_hash_sets_from_length_iterator(
        seed,
        &|seed_2| random_unsigned_range(seed_2, a, b),
        xs_gen,
    )
}

/// Generates random [`HashSet`]s with lengths in $[a, b]$, using elements from an iterator.
///
/// The lengths of the [`HashSet`]s are sampled from a uniform distribution on $[a, b)$. $a$ must be
/// less than or equal to $b$.
///
/// The input iterator must generate at least $b$ distinct elements.
///
/// $$
/// P((x\_i)\_{i=0}^{n-1}, a, b) = \frac{n!}{b - a + 1}\prod\_{i=0}^{n-1}P(x\_i).
/// $$
///
/// `xs_gen` must be infinite.
///
/// # Expected complexity per iteration
/// $T(i) = O(b T^\prime(i))$
///
/// $M(i) = O(b M^\prime(i))$
///
/// where $T$ is time, $M$ is additional memory, $i$ is the iteration number, $T^\prime$ and
/// $M^\prime$ are the time and memory functions of the iterators produced by `xs_gen`, and $b$ is
/// `b`.
///
/// If `xs` can repeat values, extra draws are needed to reach the required number of distinct
/// elements, and an iteration fails to terminate if fewer distinct values are reachable than the
/// requested length.
///
/// # Panics
/// Panics if $a \geq b$.
///
/// # Examples
/// ```
/// use itertools::Itertools;
/// use malachite_base::num::random::random_primitive_ints;
/// use malachite_base::random::EXAMPLE_SEED;
/// use malachite_base::sets::random::random_hash_sets_length_inclusive_range;
/// use maplit::hashset;
///
/// let xs =
///     random_hash_sets_length_inclusive_range(EXAMPLE_SEED, 2, 4, &random_primitive_ints::<u8>);
/// let values = xs.take(20).collect_vec();
/// assert_eq!(
///     values,
///     &[
///         hashset! {11, 85, 136},
///         hashset! {134, 200, 203, 235},
///         hashset! {38, 223, 235},
///         hashset! {32, 162, 177, 217},
///         hashset! {30, 166, 218, 234},
///         hashset! {9, 90, 106},
///         hashset! {204, 216},
///         hashset! {97, 151, 213},
///         hashset! {78, 253},
///         hashset! {39, 91, 175, 191},
///         hashset! {2, 170, 232, 233},
///         hashset! {22, 35, 217},
///         hashset! {17, 32, 114, 198},
///         hashset! {65, 114, 173},
///         hashset! {25, 121, 173, 222},
///         hashset! {79, 115, 144, 148},
///         hashset! {52, 69, 73, 137},
///         hashset! {91, 153},
///         hashset! {34, 95, 112, 178},
///         hashset! {106, 167}
///     ]
/// );
/// ```
#[inline]
pub fn random_hash_sets_length_inclusive_range<I: Iterator>(
    seed: Seed,
    a: u64,
    b: u64,
    xs_gen: &dyn Fn(Seed) -> I,
) -> RandomHashSets<I::Item, RandomUnsignedInclusiveRange<u64>, I>
where
    I::Item: Eq + Hash,
{
    random_hash_sets_from_length_iterator(
        seed,
        &|seed_2| random_unsigned_inclusive_range(seed_2, a, b),
        xs_gen,
    )
}

/// Generates random [`BTreeSet`]s of a fixed length, where the [`Vec`]s have no repeated elements,
/// and the elements are in ascending order.
///
/// This `struct` is created by [`random_b_tree_sets_fixed_length`]; see its documentation for more.
#[derive(Clone, Debug)]
pub struct RandomBTreeSetsFixedLength<I: Iterator>
where
    I::Item: Ord,
{
    len: usize,
    xs: I,
}

impl<I: Iterator> Iterator for RandomBTreeSetsFixedLength<I>
where
    I::Item: Ord,
{
    type Item = BTreeSet<I::Item>;

    #[inline]
    fn next(&mut self) -> Option<BTreeSet<I::Item>> {
        let mut set = BTreeSet::new();
        while set.len() < self.len {
            set.insert(self.xs.next().unwrap());
        }
        Some(set)
    }
}

/// Randomly generates [`BTreeSet`]s of a given length.
///
/// The input iterator must generate at least `len` distinct elements; otherwise, this iterator will
/// hang.
///
/// $$
/// P((x\_i)\_{i=0}^{n-1}) = n!\prod\_{i=0}^{n-1}P(x\_i).
/// $$
///
/// If `len` is 0, the output consists of the empty set, repeated.
///
/// `xs` must be infinite.
///
/// # Expected complexity per iteration
/// $T(i) = O(\ell \log \ell \cdot T^\prime(i))$
///
/// $M(i) = O(\ell M^\prime(i))$
///
/// where $T$ is time, $M$ is additional memory, $i$ is the iteration number, $T^\prime$ and
/// $M^\prime$ are the time and memory functions of `xs`, and $\ell$ is `len`.
///
/// If `xs` can repeat values, extra draws are needed to reach the required number of distinct
/// elements, and an iteration fails to terminate if fewer distinct values are reachable than the
/// requested length.
///
/// # Expected complexity per iteration
/// $T(i) = O(m \log m \cdot T^\prime(i))$
///
/// $M(i) = O(m M^\prime(i))$
///
/// where $T$ is time, $M$ is additional memory, $i$ is the iteration number, $T^\prime$ and
/// $M^\prime$ are the time and memory functions of the iterators produced by `xs_gen`, and $m$ is
/// `mean_length_numerator / mean_length_denominator`.
///
/// If `xs` can repeat values, extra draws are needed to reach the required number of distinct
/// elements, and an iteration fails to terminate if fewer distinct values are reachable than the
/// requested length.
///
/// # Examples
/// ```
/// use itertools::Itertools;
/// use malachite_base::num::random::random_unsigned_inclusive_range;
/// use malachite_base::random::EXAMPLE_SEED;
/// use malachite_base::sets::random::random_b_tree_sets_fixed_length;
/// use maplit::btreeset;
///
/// let xss = random_b_tree_sets_fixed_length(
///     2,
///     random_unsigned_inclusive_range::<u32>(EXAMPLE_SEED, 1, 100),
/// )
/// .take(10)
/// .collect_vec();
/// assert_eq!(
///     xss,
///     &[
///         btreeset! {24, 95},
///         btreeset! {71, 99},
///         btreeset! {53, 93},
///         btreeset! {34, 85},
///         btreeset! {2, 48},
///         btreeset! {11, 55},
///         btreeset! {18, 48},
///         btreeset! {90, 93},
///         btreeset! {67, 93},
///         btreeset! {93, 95}
///     ]
/// );
/// ```
#[inline]
pub fn random_b_tree_sets_fixed_length<I: Iterator>(
    len: u64,
    xs: I,
) -> RandomBTreeSetsFixedLength<I>
where
    I::Item: Ord,
{
    RandomBTreeSetsFixedLength {
        len: usize::exact_from(len),
        xs,
    }
}

/// Generates random [`BTreeSet`]s with lengths from an iterator.
#[derive(Clone, Debug)]
pub struct RandomBTreeSets<T: Ord, I: Iterator<Item = u64>, J: Iterator<Item = T>> {
    lengths: I,
    xs: J,
}

impl<T: Ord, I: Iterator<Item = u64>, J: Iterator<Item = T>> Iterator for RandomBTreeSets<T, I, J> {
    type Item = BTreeSet<T>;

    fn next(&mut self) -> Option<BTreeSet<T>> {
        let len = usize::exact_from(self.lengths.next().unwrap());
        let mut set = BTreeSet::new();
        while set.len() < len {
            set.insert(self.xs.next().unwrap());
        }
        Some(set)
    }
}

/// Generates random [`BTreeSet`]s using elements from an iterator and with lengths from another
/// iterator.
///
/// The input iterator must generate at least many distinct elements as any number generated by the
/// lengths iterator; otherwise, this iterator will hang.
///
/// $$
/// P((x\_i)\_{i=0}^{n-1}) = n!P(n)\prod\_{i=0}^{n-1}P(x\_i).
/// $$
///
/// `lengths` and `xs` must be infinite.
///
/// # Expected complexity per iteration
/// $T(i) = O(T^{\prime\prime}(i) + \ell \log \ell \cdot T^\prime(i))$
///
/// $M(i) = O(M^{\prime\prime}(i) + \ell M^\prime(i))$
///
/// where $T$ is time, $M$ is additional memory, $i$ is the iteration number, $T^\prime$ and
/// $M^\prime$ are the time and memory functions of the iterators produced by `xs_gen`,
/// $T^{\prime\prime}$ and $M^{\prime\prime}$ are the time and memory functions of `lengths`, and
/// $\ell$ is the $i$th generated length.
///
/// If `xs` can repeat values, extra draws are needed to reach the required number of distinct
/// elements, and an iteration fails to terminate if fewer distinct values are reachable than the
/// requested length.
///
/// # Examples
/// ```
/// use itertools::Itertools;
/// use malachite_base::num::random::random_primitive_ints;
/// use malachite_base::random::EXAMPLE_SEED;
/// use malachite_base::sets::random::random_b_tree_sets_from_length_iterator;
/// use malachite_base::vecs::random_values_from_vec;
/// use maplit::btreeset;
///
/// let xs = random_b_tree_sets_from_length_iterator(
///     EXAMPLE_SEED,
///     &|seed| random_values_from_vec(seed, vec![0, 2, 4]),
///     &random_primitive_ints::<u8>,
/// );
/// let values = xs.take(20).collect_vec();
/// assert_eq!(
///     values,
///     &[
///         btreeset! {11, 85},
///         btreeset! {134, 136, 200, 235},
///         btreeset! {203, 223},
///         btreeset! {38, 177, 217, 235},
///         btreeset! {32, 162, 166, 234},
///         btreeset! {30, 218},
///         btreeset! {},
///         btreeset! {90, 106},
///         btreeset! {},
///         btreeset! {9, 151, 204, 216},
///         btreeset! {78, 97, 213, 253},
///         btreeset! {39, 91},
///         btreeset! {170, 175, 191, 232},
///         btreeset! {2, 233},
///         btreeset! {22, 35, 198, 217},
///         btreeset! {17, 32, 114, 173},
///         btreeset! {65, 114, 121, 222},
///         btreeset! {},
///         btreeset! {25, 144, 148, 173},
///         btreeset! {}
///     ]
/// );
/// ```
#[inline]
pub fn random_b_tree_sets_from_length_iterator<
    T: Ord,
    I: Iterator<Item = u64>,
    J: Iterator<Item = T>,
>(
    seed: Seed,
    lengths_gen: &dyn Fn(Seed) -> I,
    xs_gen: &dyn Fn(Seed) -> J,
) -> RandomBTreeSets<T, I, J> {
    RandomBTreeSets {
        lengths: lengths_gen(seed.fork("lengths")),
        xs: xs_gen(seed.fork("xs")),
    }
}

/// Generates random [`BTreeSet`]s using elements from an iterator.
///
/// The lengths of the [`BTreeSet`]s are sampled from a geometric distribution with a specified mean
/// $m$, equal to `mean_length_numerator / mean_length_denominator`. $m$ must be greater than 0.
///
/// Strictly speaking, the input iterator must generate infinitely many distinct elements. In
/// practice it only needs to generate $k$ distinct elements, where $k$ is the largest length
/// actually sampled from the geometric distribution. For example, if `mean_length_numerator /
/// mean_length_denominator` is significantly lower than 256, then it's ok to use
/// `random_unsigneds::<u8>`.
///
/// $$
/// P((x\_i)\_{i=0}^{n-1}) = n!P_g(n)\prod\_{i=0}^{n-1}P(x\_i),
/// $$
/// where $P_g(n)$ is the probability function described in [`geometric_random_unsigneds`].
///
/// `xs_gen` must be infinite.
///
/// # Expected complexity per iteration
/// $T(i) = O(m \log m T^\prime(i))$
///
/// $M(i) = O(m M^\prime(i))$
///
/// where $T$ is time, $M$ is additional memory, $i$ is the iteration number, $T^\prime$ and
/// $M^\prime$ are the time and memory functions of `xs`, and $m$ is `mean_length_numerator /
/// mean_length_denominator`.
///
/// # Panics
/// Panics if `mean_length_numerator` or `mean_length_denominator` are zero, or, if after being
/// reduced to lowest terms, their sum is greater than or equal to $2^{64}$.
///
/// # Examples
/// ```
/// use itertools::Itertools;
/// use malachite_base::num::random::random_primitive_ints;
/// use malachite_base::random::EXAMPLE_SEED;
/// use malachite_base::sets::random::random_b_tree_sets;
/// use maplit::btreeset;
///
/// let xs = random_b_tree_sets(EXAMPLE_SEED, &random_primitive_ints::<u8>, 4, 1);
/// let values = xs.take(20).collect_vec();
/// assert_eq!(
///     values,
///     &[
///         btreeset! {},
///         btreeset! {11, 32, 38, 85, 134, 136, 162, 166, 177, 200, 203, 217, 223, 235},
///         btreeset! {30, 90, 218, 234},
///         btreeset! {9, 106, 204, 216},
///         btreeset! {151},
///         btreeset! {},
///         btreeset! {78, 91, 97, 213, 253},
///         btreeset! {39, 191},
///         btreeset! {170, 175, 232, 233},
///         btreeset! {},
///         btreeset! {2, 22, 35, 114, 198, 217},
///         btreeset! {},
///         btreeset! {},
///         btreeset! {17, 25, 32, 65, 79, 114, 121, 144, 148, 173, 222},
///         btreeset! {52, 69, 73, 91, 115, 137, 153, 178},
///         btreeset! {},
///         btreeset! {34, 95, 112},
///         btreeset! {},
///         btreeset! {106, 130, 167, 168, 197},
///         btreeset! {86, 101, 122, 150, 172, 177, 207, 218, 221}
///     ]
/// );
/// ```
#[inline]
pub fn random_b_tree_sets<I: Iterator>(
    seed: Seed,
    xs_gen: &dyn Fn(Seed) -> I,
    mean_length_numerator: u64,
    mean_length_denominator: u64,
) -> RandomBTreeSets<I::Item, GeometricRandomNaturalValues<u64>, I>
where
    I::Item: Ord,
{
    random_b_tree_sets_from_length_iterator(
        seed,
        &|seed_2| {
            geometric_random_unsigneds(seed_2, mean_length_numerator, mean_length_denominator)
        },
        xs_gen,
    )
}

/// Generates random [`BTreeSet`]s with a minimum length, using elements from an iterator.
///
/// Strictly speaking, the input iterator must generate infinitely many distinct elements. In
/// practice it only needs to generate $k$ distinct elements, where $k$ is the largest length
/// actually sampled from the geometric distribution. For example, if `mean_length_numerator /
/// mean_length_denominator` is significantly lower than 256, then it's ok to use
/// `random_unsigneds::<u8>`.
///
/// $$
/// P((x\_i)\_{i=0}^{n-1}) = n!P_g(n)\prod\_{i=0}^{n-1}P(x\_i),
/// $$
/// where $P_g(n)$ is the probability function described in
/// [`geometric_random_unsigned_inclusive_range`], with $a$ equal to `min_length` and `b` to
/// `u64::MAX`.
///
/// `xs_gen` must be infinite.
///
/// # Expected complexity per iteration
/// $T(i) = O(m \log m \cdot T^\prime(i))$
///
/// $M(i) = O(m M^\prime(i))$
///
/// where $T$ is time, $M$ is additional memory, $i$ is the iteration number, $T^\prime$ and
/// $M^\prime$ are the time and memory functions of the iterators produced by `xs_gen`, and $m$ is
/// `mean_length_numerator / mean_length_denominator`.
///
/// If `xs` can repeat values, extra draws are needed to reach the required number of distinct
/// elements, and an iteration fails to terminate if fewer distinct values are reachable than the
/// requested length.
///
/// # Panics
/// Panics if `mean_length_numerator` or `mean_length_denominator` are zero, if their ratio is less
/// than or equal to `min_length`, or if they are too large and manipulating them leads to
/// arithmetic overflow.
///
/// # Examples
/// ```
/// use itertools::Itertools;
/// use malachite_base::num::random::random_primitive_ints;
/// use malachite_base::random::EXAMPLE_SEED;
/// use malachite_base::sets::random::random_b_tree_sets_min_length;
/// use maplit::btreeset;
///
/// let xs = random_b_tree_sets_min_length(EXAMPLE_SEED, 2, &random_primitive_ints::<u8>, 6, 1);
/// let values = xs.take(20).collect_vec();
/// assert_eq!(
///     values,
///     &[
///         btreeset! {11, 85},
///         btreeset! {
///             30, 32, 38, 90, 134, 136, 162, 166, 177, 200, 203, 217, 218, 223, 234, 235
///         },
///         btreeset! {9, 106, 151, 204, 213, 216},
///         btreeset! {39, 78, 91, 97, 191, 253},
///         btreeset! {170, 175, 232},
///         btreeset! {2, 233},
///         btreeset! {17, 22, 32, 35, 114, 198, 217},
///         btreeset! {65, 114, 121, 173},
///         btreeset! {25, 79, 144, 148, 173, 222},
///         btreeset! {52, 115},
///         btreeset! {34, 69, 73, 91, 112, 137, 153, 178},
///         btreeset! {95, 106},
///         btreeset! {167, 197},
///         btreeset! {74, 86, 101, 115, 122, 130, 150, 168, 172, 177, 207, 218, 221},
///         btreeset! {9, 48, 52, 109, 123, 133, 159, 201, 247, 250},
///         btreeset! {196, 235},
///         btreeset! {40, 68, 97, 104, 190},
///         btreeset! {7, 216},
///         btreeset! {11, 24, 43, 112, 157, 216, 217},
///         btreeset! {29, 51, 55, 65, 84, 89, 103, 135, 191, 206, 211}
///     ]
/// );
/// ```
#[inline]
pub fn random_b_tree_sets_min_length<I: Iterator>(
    seed: Seed,
    min_length: u64,
    xs_gen: &dyn Fn(Seed) -> I,
    mean_length_numerator: u64,
    mean_length_denominator: u64,
) -> RandomBTreeSets<I::Item, GeometricRandomNaturalValues<u64>, I>
where
    I::Item: Ord,
{
    random_b_tree_sets_from_length_iterator(
        seed,
        &|seed_2| {
            geometric_random_unsigned_inclusive_range(
                seed_2,
                min_length,
                u64::MAX,
                mean_length_numerator,
                mean_length_denominator,
            )
        },
        xs_gen,
    )
}

/// Generates random [`BTreeSet`]s with lengths in $[a, b]$, using elements from an iterator.
///
/// The lengths of the [`BTreeSet`]s are sampled from a uniform distribution on $[a, b)$. $a$ must
/// be less than or equal to $b$.
///
/// The input iterator must generate at least $b$ distinct elements.
///
/// $$
/// P((x\_i)\_{i=0}^{n-1}, a, b) = \frac{n!}{b - a + 1}\prod\_{i=0}^{n-1}P(x\_i).
/// $$
///
/// `xs_gen` must be infinite.
///
/// # Expected complexity per iteration
/// $T(i) = O(b \log b \cdot T^\prime(i))$
///
/// $M(i) = O(b M^\prime(i))$
///
/// where $T$ is time, $M$ is additional memory, $i$ is the iteration number, $T^\prime$ and
/// $M^\prime$ are the time and memory functions of the iterators produced by `xs_gen`, and $b$ is
/// `b`.
///
/// If `xs` can repeat values, extra draws are needed to reach the required number of distinct
/// elements, and an iteration fails to terminate if fewer distinct values are reachable than the
/// requested length.
///
/// # Panics
/// Panics if $a \geq b$.
///
/// # Examples
/// ```
/// use itertools::Itertools;
/// use malachite_base::num::random::random_primitive_ints;
/// use malachite_base::random::EXAMPLE_SEED;
/// use malachite_base::sets::random::random_b_tree_sets_length_range;
/// use maplit::btreeset;
///
/// let xs = random_b_tree_sets_length_range(EXAMPLE_SEED, 2, 5, &random_primitive_ints::<u8>);
/// let values = xs.take(20).collect_vec();
/// assert_eq!(
///     values,
///     &[
///         btreeset! {11, 85, 136},
///         btreeset! {134, 200, 203, 235},
///         btreeset! {38, 223, 235},
///         btreeset! {32, 162, 177, 217},
///         btreeset! {30, 166, 218, 234},
///         btreeset! {9, 90, 106},
///         btreeset! {204, 216},
///         btreeset! {97, 151, 213},
///         btreeset! {78, 253},
///         btreeset! {39, 91, 175, 191},
///         btreeset! {2, 170, 232, 233},
///         btreeset! {22, 35, 217},
///         btreeset! {17, 32, 114, 198},
///         btreeset! {65, 114, 173},
///         btreeset! {25, 121, 173, 222},
///         btreeset! {79, 115, 144, 148},
///         btreeset! {52, 69, 73, 137},
///         btreeset! {91, 153},
///         btreeset! {34, 95, 112, 178},
///         btreeset! {106, 167}
///     ]
/// );
/// ```
#[inline]
pub fn random_b_tree_sets_length_range<I: Iterator>(
    seed: Seed,
    a: u64,
    b: u64,
    xs_gen: &dyn Fn(Seed) -> I,
) -> RandomBTreeSets<I::Item, RandomUnsignedRange<u64>, I>
where
    I::Item: Ord,
{
    random_b_tree_sets_from_length_iterator(
        seed,
        &|seed_2| random_unsigned_range(seed_2, a, b),
        xs_gen,
    )
}

/// Generates random [`BTreeSet`]s with lengths in $[a, b]$, using elements from an iterator.
///
/// The lengths of the [`BTreeSet`]s are sampled from a uniform distribution on $[a, b)$. $a$ must
/// be less than or equal to $b$.
///
/// The input iterator must generate at least $b$ distinct elements.
///
/// $$
/// P((x\_i)\_{i=0}^{n-1}, a, b) = \frac{n!}{b - a + 1}\prod\_{i=0}^{n-1}P(x\_i).
/// $$
///
/// `xs_gen` must be infinite.
///
/// # Expected complexity per iteration
/// $T(i) = O(b \log b \cdot T^\prime(i))$
///
/// $M(i) = O(b M^\prime(i))$
///
/// where $T$ is time, $M$ is additional memory, $i$ is the iteration number, $T^\prime$ and
/// $M^\prime$ are the time and memory functions of the iterators produced by `xs_gen`, and $b$ is
/// `b`.
///
/// If `xs` can repeat values, extra draws are needed to reach the required number of distinct
/// elements, and an iteration fails to terminate if fewer distinct values are reachable than the
/// requested length.
///
/// # Panics
/// Panics if $a \geq b$.
///
/// # Examples
/// ```
/// use itertools::Itertools;
/// use malachite_base::num::random::random_primitive_ints;
/// use malachite_base::random::EXAMPLE_SEED;
/// use malachite_base::sets::random::random_b_tree_sets_length_inclusive_range;
/// use maplit::btreeset;
///
/// let xs =
///     random_b_tree_sets_length_inclusive_range(EXAMPLE_SEED, 2, 4, &random_primitive_ints::<u8>);
/// let values = xs.take(20).collect_vec();
/// assert_eq!(
///     values,
///     &[
///         btreeset! {11, 85, 136},
///         btreeset! {134, 200, 203, 235},
///         btreeset! {38, 223, 235},
///         btreeset! {32, 162, 177, 217},
///         btreeset! {30, 166, 218, 234},
///         btreeset! {9, 90, 106},
///         btreeset! {204, 216},
///         btreeset! {97, 151, 213},
///         btreeset! {78, 253},
///         btreeset! {39, 91, 175, 191},
///         btreeset! {2, 170, 232, 233},
///         btreeset! {22, 35, 217},
///         btreeset! {17, 32, 114, 198},
///         btreeset! {65, 114, 173},
///         btreeset! {25, 121, 173, 222},
///         btreeset! {79, 115, 144, 148},
///         btreeset! {52, 69, 73, 137},
///         btreeset! {91, 153},
///         btreeset! {34, 95, 112, 178},
///         btreeset! {106, 167}
///     ]
/// );
/// ```
#[inline]
pub fn random_b_tree_sets_length_inclusive_range<I: Iterator>(
    seed: Seed,
    a: u64,
    b: u64,
    xs_gen: &dyn Fn(Seed) -> I,
) -> RandomBTreeSets<I::Item, RandomUnsignedInclusiveRange<u64>, I>
where
    I::Item: Ord,
{
    random_b_tree_sets_from_length_iterator(
        seed,
        &|seed_2| random_unsigned_inclusive_range(seed_2, a, b),
        xs_gen,
    )
}