kolakoski/
lib.rs

1#[cfg_attr(not(feature = "num-traits"), no_std)]
2
3#[cfg(feature = "num-traits")]
4extern crate num;
5
6#[cfg(test)]
7mod test;
8
9/// An Iterator that returns numbers from the Kolakoski sequence
10///
11/// Information about the Kolakoski sequence and the first 108 numbers
12/// can be found at https://oeis.org/A000002. The source of the numbers
13/// used for testing in `test.rs` is also https://oeis.org/A000002.
14///
15/// This sequence is self-refrential, and the implementation is recursive.
16/// Attempts to get a large number of items from the sequence may overflow
17/// the stack, depending on the machine. Use with caution!
18pub struct Kolakoski
19{
20    run: usize,
21    run_length: u8,
22    is_one: bool,
23}
24
25#[cfg(feature = "num-traits")]
26pub struct KolakoskiNum<N>
27{
28    run: usize,
29    run_length: N,
30    is_one: bool,
31}
32
33impl Kolakoski
34{
35    /// Creates a new Kolakoski iterator
36    pub fn new() -> Kolakoski
37    {
38        Kolakoski
39        {
40            run: 0,
41            run_length: 1,
42            is_one: true,
43        }
44    }
45}
46
47#[cfg(feature = "num-traits")]
48impl<N: Num> KolakoskiNum<N>
49{
50    /// Creates a new Kolakoski iterator
51    pub fn new() -> KolakoskiNum<N>
52    {
53        KolakoskiNum
54        {
55            run: 0,
56            run_length: N::one(),
57            is_one: true,
58        }
59    }
60}
61
62impl Iterator for Kolakoski
63{
64    type Item = u8;
65
66    fn next(&mut self) -> Option<Self::Item>
67    {
68        if self.run_length == 0
69        {
70            self.is_one = !self.is_one;
71            self.run += 1;
72
73            if self.run == 1
74            {
75                self.run_length = 2;
76            }
77            else
78            {
79                self.run_length = Kolakoski::new().nth(self.run).unwrap();
80            }
81        }
82
83        self.run_length -= 1;
84
85        if self.is_one
86        {
87            Some(1)
88        }
89        else
90        {
91            Some(2)
92        }
93    }
94}
95
96#[cfg(feature = "num-traits")]
97use num::traits::Num;
98
99#[cfg(feature = "num-traits")]
100impl<N: Num + Clone> Iterator for KolakoskiNum<N>
101{
102    type Item = N;
103
104    fn next(&mut self) -> Option<Self::Item>
105    {
106        if self.run_length == N::zero()
107        {
108            self.is_one = !self.is_one;
109            self.run += 1;
110
111            if self.run == 1
112            {
113                self.run_length = N::one() + N::one()
114            }
115            else
116            {
117                self.run_length = KolakoskiNum::<N>::new().nth(self.run).unwrap();
118            }
119        }
120
121        self.run_length = self.run_length.clone() - N::one();
122
123        if self.is_one
124        {
125            Some(N::one())
126        }
127        else
128        {
129            Some(N::one() + N::one())
130        }
131    }
132}
kolakoski/lib.rs

kolakoski/
lib.rs
