1 use core::iter::FusedIterator;
2
3 cfg_digit!(
4 /// An iterator of `u32` digits representation of a `BigUint` or `BigInt`,
5 /// ordered least significant digit first.
6 pub struct U32Digits<'a> {
7 it: core::slice::Iter<'a, u32>,
8 }
9
10 /// An iterator of `u32` digits representation of a `BigUint` or `BigInt`,
11 /// ordered least significant digit first.
12 pub struct U32Digits<'a> {
13 data: &'a [u64],
14 next_is_lo: bool,
15 last_hi_is_zero: bool,
16 }
17 );
18
19 cfg_digit!(
20 const _: () = {
21 impl<'a> U32Digits<'a> {
22 #[inline]
23 pub(super) fn new(data: &'a [u32]) -> Self {
24 Self { it: data.iter() }
25 }
26 }
27
28 impl Iterator for U32Digits<'_> {
29 type Item = u32;
30 #[inline]
31 fn next(&mut self) -> Option<u32> {
32 self.it.next().cloned()
33 }
34
35 #[inline]
36 fn size_hint(&self) -> (usize, Option<usize>) {
37 self.it.size_hint()
38 }
39
40 #[inline]
41 fn nth(&mut self, n: usize) -> Option<u32> {
42 self.it.nth(n).cloned()
43 }
44
45 #[inline]
46 fn last(self) -> Option<u32> {
47 self.it.last().cloned()
48 }
49
50 #[inline]
51 fn count(self) -> usize {
52 self.it.count()
53 }
54 }
55
56 impl DoubleEndedIterator for U32Digits<'_> {
57 fn next_back(&mut self) -> Option<Self::Item> {
58 self.it.next_back().cloned()
59 }
60 }
61
62 impl ExactSizeIterator for U32Digits<'_> {
63 #[inline]
64 fn len(&self) -> usize {
65 self.it.len()
66 }
67 }
68 };
69
70 const _: () = {
71 impl<'a> U32Digits<'a> {
72 #[inline]
73 pub(super) fn new(data: &'a [u64]) -> Self {
74 let last_hi_is_zero = data
75 .last()
76 .map(|&last| {
77 let last_hi = (last >> 32) as u32;
78 last_hi == 0
79 })
80 .unwrap_or(false);
81 U32Digits {
82 data,
83 next_is_lo: true,
84 last_hi_is_zero,
85 }
86 }
87 }
88
89 impl Iterator for U32Digits<'_> {
90 type Item = u32;
91 #[inline]
92 fn next(&mut self) -> Option<u32> {
93 match self.data.split_first() {
94 Some((&first, data)) => {
95 let next_is_lo = self.next_is_lo;
96 self.next_is_lo = !next_is_lo;
97 if next_is_lo {
98 Some(first as u32)
99 } else {
100 self.data = data;
101 if data.is_empty() && self.last_hi_is_zero {
102 self.last_hi_is_zero = false;
103 None
104 } else {
105 Some((first >> 32) as u32)
106 }
107 }
108 }
109 None => None,
110 }
111 }
112
113 #[inline]
114 fn size_hint(&self) -> (usize, Option<usize>) {
115 let len = self.len();
116 (len, Some(len))
117 }
118
119 #[inline]
120 fn last(self) -> Option<u32> {
121 self.data.last().map(|&last| {
122 if self.last_hi_is_zero {
123 last as u32
124 } else {
125 (last >> 32) as u32
126 }
127 })
128 }
129
130 #[inline]
131 fn count(self) -> usize {
132 self.len()
133 }
134 }
135
136 impl DoubleEndedIterator for U32Digits<'_> {
137 fn next_back(&mut self) -> Option<Self::Item> {
138 match self.data.split_last() {
139 Some((&last, data)) => {
140 let last_is_lo = self.last_hi_is_zero;
141 self.last_hi_is_zero = !last_is_lo;
142 if last_is_lo {
143 self.data = data;
144 if data.is_empty() && !self.next_is_lo {
145 self.next_is_lo = true;
146 None
147 } else {
148 Some(last as u32)
149 }
150 } else {
151 Some((last >> 32) as u32)
152 }
153 }
154 None => None,
155 }
156 }
157 }
158
159 impl ExactSizeIterator for U32Digits<'_> {
160 #[inline]
161 fn len(&self) -> usize {
162 self.data.len() * 2
163 - usize::from(self.last_hi_is_zero)
164 - usize::from(!self.next_is_lo)
165 }
166 }
167 };
168 );
169
170 impl FusedIterator for U32Digits<'_> {}
171
172 cfg_digit!(
173 /// An iterator of `u64` digits representation of a `BigUint` or `BigInt`,
174 /// ordered least significant digit first.
175 pub struct U64Digits<'a> {
176 it: core::slice::Chunks<'a, u32>,
177 }
178
179 /// An iterator of `u64` digits representation of a `BigUint` or `BigInt`,
180 /// ordered least significant digit first.
181 pub struct U64Digits<'a> {
182 it: core::slice::Iter<'a, u64>,
183 }
184 );
185
186 cfg_digit!(
187 const _: () = {
188 impl<'a> U64Digits<'a> {
189 #[inline]
190 pub(super) fn new(data: &'a [u32]) -> Self {
191 U64Digits { it: data.chunks(2) }
192 }
193 }
194
195 impl Iterator for U64Digits<'_> {
196 type Item = u64;
197 #[inline]
198 fn next(&mut self) -> Option<u64> {
199 self.it.next().map(super::u32_chunk_to_u64)
200 }
201
202 #[inline]
203 fn size_hint(&self) -> (usize, Option<usize>) {
204 let len = self.len();
205 (len, Some(len))
206 }
207
208 #[inline]
209 fn last(self) -> Option<u64> {
210 self.it.last().map(super::u32_chunk_to_u64)
211 }
212
213 #[inline]
214 fn count(self) -> usize {
215 self.len()
216 }
217 }
218
219 impl DoubleEndedIterator for U64Digits<'_> {
220 fn next_back(&mut self) -> Option<Self::Item> {
221 self.it.next_back().map(super::u32_chunk_to_u64)
222 }
223 }
224 };
225
226 const _: () = {
227 impl<'a> U64Digits<'a> {
228 #[inline]
229 pub(super) fn new(data: &'a [u64]) -> Self {
230 Self { it: data.iter() }
231 }
232 }
233
234 impl Iterator for U64Digits<'_> {
235 type Item = u64;
236 #[inline]
237 fn next(&mut self) -> Option<u64> {
238 self.it.next().cloned()
239 }
240
241 #[inline]
242 fn size_hint(&self) -> (usize, Option<usize>) {
243 self.it.size_hint()
244 }
245
246 #[inline]
247 fn nth(&mut self, n: usize) -> Option<u64> {
248 self.it.nth(n).cloned()
249 }
250
251 #[inline]
252 fn last(self) -> Option<u64> {
253 self.it.last().cloned()
254 }
255
256 #[inline]
257 fn count(self) -> usize {
258 self.it.count()
259 }
260 }
261
262 impl DoubleEndedIterator for U64Digits<'_> {
263 fn next_back(&mut self) -> Option<Self::Item> {
264 self.it.next_back().cloned()
265 }
266 }
267 };
268 );
269
270 impl ExactSizeIterator for U64Digits<'_> {
271 #[inline]
len(&self) -> usize272 fn len(&self) -> usize {
273 self.it.len()
274 }
275 }
276
277 impl FusedIterator for U64Digits<'_> {}
278
279 #[test]
test_iter_u32_digits()280 fn test_iter_u32_digits() {
281 let n = super::BigUint::from(5u8);
282 let mut it = n.iter_u32_digits();
283 assert_eq!(it.len(), 1);
284 assert_eq!(it.next(), Some(5));
285 assert_eq!(it.len(), 0);
286 assert_eq!(it.next(), None);
287 assert_eq!(it.len(), 0);
288 assert_eq!(it.next(), None);
289
290 let n = super::BigUint::from(112500000000u64);
291 let mut it = n.iter_u32_digits();
292 assert_eq!(it.len(), 2);
293 assert_eq!(it.next(), Some(830850304));
294 assert_eq!(it.len(), 1);
295 assert_eq!(it.next(), Some(26));
296 assert_eq!(it.len(), 0);
297 assert_eq!(it.next(), None);
298 }
299
300 #[test]
test_iter_u64_digits()301 fn test_iter_u64_digits() {
302 let n = super::BigUint::from(5u8);
303 let mut it = n.iter_u64_digits();
304 assert_eq!(it.len(), 1);
305 assert_eq!(it.next(), Some(5));
306 assert_eq!(it.len(), 0);
307 assert_eq!(it.next(), None);
308 assert_eq!(it.len(), 0);
309 assert_eq!(it.next(), None);
310
311 let n = super::BigUint::from(18_446_744_073_709_551_616u128);
312 let mut it = n.iter_u64_digits();
313 assert_eq!(it.len(), 2);
314 assert_eq!(it.next(), Some(0));
315 assert_eq!(it.len(), 1);
316 assert_eq!(it.next(), Some(1));
317 assert_eq!(it.len(), 0);
318 assert_eq!(it.next(), None);
319 }
320
321 #[test]
test_iter_u32_digits_be()322 fn test_iter_u32_digits_be() {
323 let n = super::BigUint::from(5u8);
324 let mut it = n.iter_u32_digits();
325 assert_eq!(it.len(), 1);
326 assert_eq!(it.next(), Some(5));
327 assert_eq!(it.len(), 0);
328 assert_eq!(it.next(), None);
329 assert_eq!(it.len(), 0);
330 assert_eq!(it.next(), None);
331
332 let n = super::BigUint::from(112500000000u64);
333 let mut it = n.iter_u32_digits();
334 assert_eq!(it.len(), 2);
335 assert_eq!(it.next(), Some(830850304));
336 assert_eq!(it.len(), 1);
337 assert_eq!(it.next(), Some(26));
338 assert_eq!(it.len(), 0);
339 assert_eq!(it.next(), None);
340 }
341
342 #[test]
test_iter_u64_digits_be()343 fn test_iter_u64_digits_be() {
344 let n = super::BigUint::from(5u8);
345 let mut it = n.iter_u64_digits();
346 assert_eq!(it.len(), 1);
347 assert_eq!(it.next_back(), Some(5));
348 assert_eq!(it.len(), 0);
349 assert_eq!(it.next(), None);
350 assert_eq!(it.len(), 0);
351 assert_eq!(it.next(), None);
352
353 let n = super::BigUint::from(18_446_744_073_709_551_616u128);
354 let mut it = n.iter_u64_digits();
355 assert_eq!(it.len(), 2);
356 assert_eq!(it.next_back(), Some(1));
357 assert_eq!(it.len(), 1);
358 assert_eq!(it.next_back(), Some(0));
359 assert_eq!(it.len(), 0);
360 assert_eq!(it.next(), None);
361 }
362