iter_rationals/
lib.rs

1//! An implementation of a fixed-size iterator over the rational numbers based on the
2//! algorithm described by Gibbons, Lester, and Bird in
3//! [Functional Pearl: Enumerating the Rationals].
4//!
5//! [Functional Pearl: Enumerating the Rationals]: http://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/rationals.pdf
6
7#![cfg_attr(not(test), no_std)]
8
9use num_integer::Integer;
10use num_rational::Ratio;
11
12pub struct Rationals<T: Integer> {
13    state: Ratio<T>,
14}
15
16impl<T> Rationals<T>
17where
18    T: Integer + Clone,
19{
20    /// Create a new iterator over the rationals.
21    ///
22    /// ```
23    /// use iter_rationals::Rationals;
24    ///
25    /// let rationals = Rationals::<u32>::new();
26    ///
27    /// for r in rationals.take(10) {
28    ///     println!("{}", r);
29    /// }
30    /// ```
31    pub fn new() -> Self {
32        Self { state: Self::one() }
33    }
34
35    fn one() -> Ratio<T> {
36        Ratio::from_integer(T::one())
37    }
38}
39
40impl<T> Default for Rationals<T>
41where
42    T: Integer + Clone,
43{
44    fn default() -> Self {
45        Self::new()
46    }
47}
48
49impl<T> Iterator for Rationals<T>
50where
51    T: Integer + Clone + core::ops::Add,
52{
53    type Item = Ratio<T>;
54
55    fn next(&mut self) -> Option<Self::Item> {
56        let r = self.state.clone();
57        let n = r.trunc();
58        let y = r.fract();
59        let next = (n + T::one() - y).recip();
60        self.state = next;
61        Some(r)
62    }
63}
64
65#[cfg(test)]
66mod tests {
67    use super::*;
68
69    #[test]
70    fn test_speed_is_reasonable() {
71        let mut r = Rationals::<u32>::new();
72        let nth_rational = r.nth(1_000_000).unwrap();
73        println!("{}", nth_rational);
74        let expected = Ratio::new(1287, 1096);
75        assert_eq!(expected, nth_rational);
76    }
77
78    #[test]
79    fn test_first_values_are_as_expected() {
80        let expected_parts = [
81            (1, 1),
82            (1, 2),
83            (2, 1),
84            (1, 3),
85            (3, 2),
86            (2, 3),
87            (3, 1),
88            (1, 4),
89            (4, 3),
90            (3, 5),
91            (5, 2),
92            (2, 5),
93            (5, 3),
94            (3, 4),
95            (4, 1),
96        ];
97        let expected: Vec<Ratio<u32>> = expected_parts
98            .iter()
99            .map(|p| Ratio::new(p.0, p.1))
100            .collect();
101        let found: Vec<Ratio<u32>> = Rationals::<u32>::new().take(expected.len()).collect();
102        assert_eq!(found, expected);
103    }
104
105    #[test]
106    fn test_builtin_types() {
107        let limit = 32;
108
109        Rationals::<u8>::new().nth(limit).unwrap();
110        Rationals::<u16>::new().nth(limit).unwrap();
111        Rationals::<u32>::new().nth(limit).unwrap();
112        Rationals::<u64>::new().nth(limit).unwrap();
113        Rationals::<u128>::new().nth(limit).unwrap();
114
115        Rationals::<i8>::new().nth(limit).unwrap();
116        Rationals::<i16>::new().nth(limit).unwrap();
117        Rationals::<i32>::new().nth(limit).unwrap();
118        Rationals::<i64>::new().nth(limit).unwrap();
119        Rationals::<i128>::new().nth(limit).unwrap();
120
121        Rationals::<usize>::new().nth(limit).unwrap();
122        Rationals::<isize>::new().nth(limit).unwrap();
123    }
124}
iter_rationals/lib.rs

iter_rationals/
lib.rs
