malachite-q 0.14.0

The arbitrary-precision type Rational, with efficient algorithms partially derived from GMP and FLINT.
Documentation 
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

// 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::Rational;
use crate::rational::exhaustive::{ExhaustiveNonzeroRationals, exhaustive_rationals};
use crate::rational_vector::RationalVector;
use alloc::vec::Vec;
use core::iter::{Chain, Once};
use malachite_base::num::exhaustive::PrimitiveIntIncreasingRange;
use malachite_base::vecs::exhaustive::{
    ExhaustiveFixedLengthVecs1Input, ExhaustiveVecs, exhaustive_vecs,
    exhaustive_vecs_fixed_length_from_single,
};

/// Generates [`RationalVector`]s from an iterator of [`Vec`]s of [`Rational`]s.
///
/// This `struct` is created by [`exhaustive_rational_vectors`] and
/// [`exhaustive_rational_vectors_with_dimension`]; see their documentation for more.
#[derive(Clone, Debug)]
pub struct ExhaustiveRationalVectors<I: Iterator<Item = Vec<Rational>>>(I);

impl<I: Iterator<Item = Vec<Rational>>> Iterator for ExhaustiveRationalVectors<I> {
    type Item = RationalVector;

    #[inline]
    fn next(&mut self) -> Option<RationalVector> {
        self.0.next().map(|elements| RationalVector { elements })
    }
}

/// Generates all [`RationalVector`]s.
///
/// Every vector, of every dimension, is generated once, the 0-dimensional vector first.
///
/// The dimensions grow logarithmically, as the degrees do in [`exhaustive_rational_polynomials`](
/// crate::rational_polynomial::exhaustive::exhaustive_rational_polynomials): dimension $d$ is first
/// reached after $O(2^d)$ outputs.
///
/// The output length is infinite.
///
/// # Worst-case complexity per iteration
/// $T(i) = O(n\ell)$
///
/// $M(i) = O(n\ell)$
///
/// where $T$ is time, $M$ is additional memory, $i$ is the iteration number, $n$ is the dimension
/// of the $i$th output, and $\ell$ is the number of significant bits of its largest element.
///
/// # Examples
/// ```
/// use malachite_base::iterators::prefix_to_string;
/// use malachite_q::rational_vector::exhaustive::exhaustive_rational_vectors;
///
/// assert_eq!(
///     prefix_to_string(exhaustive_rational_vectors(), 20),
///     "[(), (0), (1), (0, 0, 0), (-1), (0, 0), (1/2), (0, 0, 0, 0), (-1/2), (0, 1), (2), (0, 0, \
///     1), (-2), (1, 0), (1/3), (0, 0, 0, 0, 0), (-1/3), (1, 1), (3/2), (0, 1, 0), ...]"
/// );
/// ```
#[inline]
pub fn exhaustive_rational_vectors() -> ExhaustiveRationalVectors<
    ExhaustiveVecs<
        Rational,
        PrimitiveIntIncreasingRange<u64>,
        Chain<Once<Rational>, ExhaustiveNonzeroRationals>,
    >,
> {
    ExhaustiveRationalVectors(exhaustive_vecs(exhaustive_rationals()))
}

/// Generates all [`RationalVector`]s of a given dimension.
///
/// If `dimension` is 0, the only output is the 0-dimensional vector; otherwise the output length is
/// infinite.
///
/// # Worst-case complexity per iteration
/// $T(i) = O(n\ell)$
///
/// $M(i) = O(n\ell)$
///
/// where $T$ is time, $M$ is additional memory, $i$ is the iteration number, $n$ is `dimension`,
/// and $\ell$ is the number of significant bits of the $i$th output's largest element.
///
/// # Examples
/// ```
/// use malachite_base::iterators::prefix_to_string;
/// use malachite_q::rational_vector::exhaustive::exhaustive_rational_vectors_with_dimension;
///
/// assert_eq!(
///     prefix_to_string(exhaustive_rational_vectors_with_dimension(0), 10),
///     "[()]"
/// );
/// assert_eq!(
///     prefix_to_string(exhaustive_rational_vectors_with_dimension(2), 10),
///     "[(0, 0), (0, 1), (1, 0), (1, 1), (0, -1), (0, 1/2), (1, -1), (1, 1/2), (-1, 0), \
///     (-1, 1), ...]"
/// );
/// ```
#[inline]
pub fn exhaustive_rational_vectors_with_dimension(
    dimension: u64,
) -> ExhaustiveRationalVectors<
    ExhaustiveFixedLengthVecs1Input<Chain<Once<Rational>, ExhaustiveNonzeroRationals>>,
> {
    ExhaustiveRationalVectors(exhaustive_vecs_fixed_length_from_single(
        dimension,
        exhaustive_rationals(),
    ))
}