malachite_base/rational_sequences/
exhaustive.rs

1// Copyright © 2025 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::num::exhaustive::PrimitiveIntIncreasingRange;
10use crate::rational_sequences::{RationalSequence, rational_sequence_is_reduced};
11use crate::tuples::exhaustive::{ExhaustivePairs1Input, exhaustive_pairs_from_single};
12use crate::vecs::exhaustive::{ExhaustiveVecs, exhaustive_vecs};
13
14/// Generates all [`RationalSequence`]s containing elements from an iterator.
15///
16/// This `struct` is created by [`exhaustive_rational_sequences`]; see its documentation for more.
17#[derive(Clone, Debug)]
18pub struct ExhaustiveRationalSequences<I: Clone + Iterator>(
19    ExhaustivePairs1Input<ExhaustiveVecs<I::Item, PrimitiveIntIncreasingRange<u64>, I>>,
20)
21where
22    I::Item: Clone;
23
24impl<I: Clone + Iterator> Iterator for ExhaustiveRationalSequences<I>
25where
26    I::Item: Clone + Eq,
27{
28    type Item = RationalSequence<I::Item>;
29
30    fn next(&mut self) -> Option<RationalSequence<I::Item>> {
31        loop {
32            let (non_repeating, repeating) = self.0.next()?;
33            if rational_sequence_is_reduced(&non_repeating, &repeating) {
34                return Some(RationalSequence {
35                    non_repeating,
36                    repeating,
37                });
38            }
39        }
40    }
41}
42
43/// Generates all [`RationalSequence`]s containing elements from a given iterator.
44///
45/// The input iterator should contain no repetitions, but this is not enforced.
46///
47/// The output length is 1 if the input iterator is empty, and infinite otherwise.
48///
49/// # Worst-case complexity per iteration
50/// $T(i) = O(T^\prime(i) + (\log i)^{1+\varepsilon})$ for all $\varepsilon > 0$
51///
52/// $M(i) = O((\log i) M^\prime(i))$
53///
54/// where $T$ is time, $M$ is additional memory, and $T^\prime$ and $M^\prime$ are the time and
55/// memory functions of the input iterator.
56///
57/// # Examples
58/// ```
59/// use itertools::Itertools;
60/// use malachite_base::num::exhaustive::exhaustive_unsigneds;
61/// use malachite_base::rational_sequences::exhaustive::exhaustive_rational_sequences;
62/// use malachite_base::strings::ToDebugString;
63///
64/// assert_eq!(
65///     exhaustive_rational_sequences(exhaustive_unsigneds::<u8>())
66///         .take(10)
67///         .collect_vec()
68///         .to_debug_string(),
69///     "[[], [[0]], [0], [[1]], [0, [1]], [1], [1, [0]], [0, 0, 0], [0, 0, 0, [1]], [[2]]]"
70/// )
71/// ```
72pub fn exhaustive_rational_sequences<I: Clone + Iterator>(xs: I) -> ExhaustiveRationalSequences<I>
73where
74    I::Item: Clone + Eq,
75{
76    ExhaustiveRationalSequences(exhaustive_pairs_from_single(exhaustive_vecs(xs)))
77}
malachite_base/rational_sequences/exhaustive.rs

malachite_base/rational_sequences/
exhaustive.rs
