num_bigint/biguint/
iter.rs

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

num_bigint/biguint/
iter.rs
