num_bigint/biguint/
iter.rs

Help
1use core::iter::FusedIterator;
2
3cfg_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
19cfg_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
170impl FusedIterator for U32Digits<'_> {}
171
172cfg_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
186cfg_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
270impl ExactSizeIterator for U64Digits<'_> {
271    #[inline]
272    fn len(&self) -> usize {
273        self.it.len()
274    }
275}
276
277impl FusedIterator for U64Digits<'_> {}
278
279#[test]
280fn 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]
301fn 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]
322fn 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]
343fn 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}
num_bigint/biguint/iter.rs

num_bigint/biguint/
iter.rs
