1
2pub struct ThueMorseProvider {
3 base: u32,
4}
5
6impl ThueMorseProvider {
7 pub fn new(base: u32) -> Self {
8 Self {
9 base,
10 }
11 }
12 #[inline(always)]
13 pub fn get_value(&self, index: usize) -> u32 {
14 match self.base {
15 2 => {
16 index.count_ones() % 2
17 },
18 base => {
19 let mut index = index;
20 let base = base as usize;
21 let mut result: usize = 0;
22 while index > 0 {
23 result += index % base;
24 index /= base;
25 }
26 (result % base) as u32
27 },
28 }
29 }
30 pub fn into_iter(self) -> ThueMorseIterator {
31 ThueMorseIterator {
32 thue_morse_provider: self,
33 index: 0,
34 is_maximum_reached: false,
35 }
36 }
37}
38
39pub struct ThueMorseIterator {
40 thue_morse_provider: ThueMorseProvider,
41 index: usize,
42 is_maximum_reached: bool,
43}
44
45impl Iterator for ThueMorseIterator {
46 type Item = u32;
47
48 fn next(&mut self) -> Option<Self::Item> {
49 if self.is_maximum_reached {
50 return None;
51 }
52
53 let value = self.thue_morse_provider.get_value(self.index);
54
55 match self.index.checked_add(1) {
57 Some(next_index) => {
58 self.index = next_index;
59 },
60 None => {
61 self.is_maximum_reached = true;
62 },
63 }
64
65 Some(value)
66 }
67}
68
69pub struct EvilNumberIterator {
70 thue_morse_provider: ThueMorseProvider,
71 index: usize,
72 is_maximum_reached: bool,
73}
74
75impl EvilNumberIterator {
76 pub fn new() -> Self {
77 Self {
78 thue_morse_provider: ThueMorseProvider::new(2),
79 index: 0,
80 is_maximum_reached: false,
81 }
82 }
83}
84
85impl Iterator for EvilNumberIterator {
86 type Item = usize;
87
88 fn next(&mut self) -> Option<Self::Item> {
89 if self.is_maximum_reached {
90 return None;
91 }
92
93 let mut value = self.thue_morse_provider.get_value(self.index);
94 while value != 0 {
95 match self.index.checked_add(1) {
96 Some(next_index) => {
97 self.index = next_index;
98 },
99 None => {
100 self.is_maximum_reached = true;
101 return None;
102 },
103 }
104 value = self.thue_morse_provider.get_value(self.index);
105 }
106 let found_at_index = self.index;
107 match self.index.checked_add(1) {
108 Some(next_index) => {
109 self.index = next_index;
110 },
111 None => {
112 self.is_maximum_reached = true;
113 },
114 }
115 Some(found_at_index)
116 }
117}
118
119pub struct OdiousNumberIterator {
120 thue_morse_provider: ThueMorseProvider,
121 index: usize,
122 is_maximum_reached: bool,
123}
124
125impl OdiousNumberIterator {
126 pub fn new() -> Self {
127 Self {
128 thue_morse_provider: ThueMorseProvider::new(2),
129 index: 0,
130 is_maximum_reached: false,
131 }
132 }
133}
134
135impl Iterator for OdiousNumberIterator {
136 type Item = usize;
137
138 fn next(&mut self) -> Option<Self::Item> {
139 if self.is_maximum_reached {
140 return None;
141 }
142
143 let mut value = self.thue_morse_provider.get_value(self.index);
144 while value != 1 {
145 match self.index.checked_add(1) {
146 Some(next_index) => {
147 self.index = next_index;
148 },
149 None => {
150 self.is_maximum_reached = true;
151 return None;
152 },
153 }
154 value = self.thue_morse_provider.get_value(self.index);
155 }
156 let found_at_index = self.index;
157 match self.index.checked_add(1) {
158 Some(next_index) => {
159 self.index = next_index;
160 },
161 None => {
162 self.is_maximum_reached = true;
163 },
164 }
165 Some(found_at_index)
166 }
167}
168
169#[cfg(test)]
170mod tests {
171 use crate::*;
172
173 #[test]
174 fn test_r2n8_binary() {
175 let provider = ThueMorseProvider::new(2);
176 assert_eq!(0, provider.get_value(0));
177 assert_eq!(1, provider.get_value(1));
178 assert_eq!(1, provider.get_value(2));
179 assert_eq!(0, provider.get_value(3));
180 assert_eq!(1, provider.get_value(4));
181 assert_eq!(0, provider.get_value(5));
182 assert_eq!(0, provider.get_value(6));
183 assert_eq!(1, provider.get_value(7));
184 }
185
186 #[test]
187 fn test_w8m2_trinary() {
188 let expected_values = [
189 0u32,
190 1,
191 2,
192 1,
193 2,
194 0,
195 2,
196 0,
197 1,
198 1,
199 2,
200 0,
201 2,
202 0,
203 1,
204 0,
205 1,
206 2,
207 2,
208 0,
209 1,
210 0,
211 1,
212 2,
213 1,
214 2,
215 0,
216 ];
217 let iterator = ThueMorseProvider::new(3).into_iter();
218 for (expected_value, actual_value) in expected_values.into_iter().zip(iterator) {
219 println!("comparing {} to {}", actual_value, expected_value);
220 assert_eq!(expected_value, actual_value);
221 }
222 }
223 #[test]
224 fn test_j1v5_five() {
225 let expected_values = [0, 1, 2, 3, 4, 1, 2, 3, 4, 0, 2, 3, 4, 0, 1, 3, 4, 0, 1, 2, 4, 0, 1, 2, 3, 1, 2, 3, 4, 0];
226 let iterator = ThueMorseProvider::new(5).into_iter();
227 for (expected_value, actual_value) in expected_values.into_iter().zip(iterator) {
228 println!("comparing {} to {}", actual_value, expected_value);
229 assert_eq!(expected_value, actual_value);
230 }
231 }
232 #[test]
233 fn test_u6x9_evil_numbers() {
234 let expected_values = [0, 3, 5, 6, 9, 10, 12, 15, 17, 18, 20, 23, 24, 27, 29, 30, 33, 34, 36, 39];
235 let iterator = EvilNumberIterator::new();
236 for (expected_value, actual_value) in expected_values.into_iter().zip(iterator) {
237 println!("comparing {} to {}", actual_value, expected_value);
238 assert_eq!(expected_value, actual_value);
239 }
240 }
241 #[test]
242 fn test_q5p8_odious_numbers() {
243 let expected_values = [1, 2, 4, 7, 8, 11, 13, 14, 16, 19, 21, 22, 25, 26, 28, 31, 32, 35, 37, 38];
244 let iterator = OdiousNumberIterator::new();
245 for (expected_value, actual_value) in expected_values.into_iter().zip(iterator) {
246 println!("comparing {} to {}", actual_value, expected_value);
247 assert_eq!(expected_value, actual_value);
248 }
249 }
250}