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

use num::exhaustive::PrimitiveIntIncreasingRange;
use rational_sequences::{rational_sequence_is_reduced, RationalSequence};
use tuples::exhaustive::{exhaustive_pairs_from_single, ExhaustivePairs1Input};
use vecs::exhaustive::{exhaustive_vecs, ExhaustiveVecs};

/// Generates all [`RationalSequence`]s containing elements from an iterator.
///
/// This `struct` is created by [`exhaustive_rational_sequences`]; see its documentation for more.
#[derive(Clone, Debug)]
pub struct ExhaustiveRationalSequences<I: Clone + Iterator>(
    ExhaustivePairs1Input<ExhaustiveVecs<I::Item, PrimitiveIntIncreasingRange<u64>, I>>,
)
where
    I::Item: Clone;

impl<I: Clone + Iterator> Iterator for ExhaustiveRationalSequences<I>
where
    I::Item: Clone + Eq,
{
    type Item = RationalSequence<I::Item>;

    fn next(&mut self) -> Option<RationalSequence<I::Item>> {
        loop {
            let (non_repeating, repeating) = self.0.next()?;
            if rational_sequence_is_reduced(&non_repeating, &repeating) {
                return Some(RationalSequence {
                    non_repeating,
                    repeating,
                });
            }
        }
    }
}

/// Generates all [`RationalSequence`]s containing elements from a given iterator.
///
/// The input iterator should contain no repetitions, but this is not enforced.
///
/// The output length is 1 if the input iterator is empty, and infinite otherwise.
///
/// # Worst-case complexity per iteration
/// $T(i) = O(T^\prime(i) + (\log i)^{1+\epsilon})$ for all $\epsilon > 0$
///
/// $M(i) = O((\log i) M^\prime(i))$
///
/// where $T$ is time, $M$ is additional memory, and $T^\prime$ and $M^\prime$ are the time and
/// memory functions of the input iterator.
///
/// # Examples
/// ```
/// extern crate itertools;
///
/// use itertools::Itertools;
/// use malachite_base::num::exhaustive::exhaustive_unsigneds;
/// use malachite_base::rational_sequences::exhaustive::exhaustive_rational_sequences;
/// use malachite_base::strings::ToDebugString;
///
/// assert_eq!(
///     exhaustive_rational_sequences(exhaustive_unsigneds::<u8>()).take(10).collect_vec()
///         .to_debug_string(),
///     "[[], [[0]], [0], [[1]], [0, [1]], [1], [1, [0]], [0, 0, 0], [0, 0, 0, [1]], [[2]]]"
/// )
/// ```
pub fn exhaustive_rational_sequences<I: Clone + Iterator>(xs: I) -> ExhaustiveRationalSequences<I>
where
    I::Item: Clone + Eq,
{
    ExhaustiveRationalSequences(exhaustive_pairs_from_single(exhaustive_vecs(xs)))
}