Skip to content

Commit a6e88c5

Browse files
cuvipercuviper
committed
Move iterators to a separate module
1 parent f58cef3 commit a6e88c5

2 files changed

Lines changed: 286 additions & 281 deletions

File tree

‎src/biguint.rs‎

Lines changed: 15 additions & 281 deletions
Original file line numberDiff line numberDiff line change
@@ -1,26 +1,26 @@
1+
use crate::big_digit::{self, BigDigit};
12
use crate::std_alloc::{String, Vec};
3+
24
use core::cmp;
35
use core::cmp::Ordering;
46
use core::default::Default;
57
use core::fmt;
68
use core::hash;
7-
use core::iter::FusedIterator;
89
use core::mem;
910
use core::str;
1011
use core::{u32, u64, u8};
1112

1213
use num_integer::{Integer, Roots};
1314
use num_traits::{Num, One, Pow, ToPrimitive, Unsigned, Zero};
1415

15-
use crate::big_digit::{self, BigDigit};
16-
1716
mod addition;
1817
mod division;
1918
mod multiplication;
2019
mod subtraction;
2120

2221
mod bits;
2322
mod convert;
23+
mod iter;
2424
mod monty;
2525
mod power;
2626
mod shift;
@@ -32,6 +32,7 @@ mod arbitrary;
3232
mod serde;
3333

3434
pub(crate) use self::convert::to_str_radix_reversed;
35+
pub use self::iter::{U32Digits, U64Digits};
3536

3637
/// A big unsigned integer type.
3738
#[derive(Debug)]
@@ -137,17 +138,6 @@ impl fmt::Octal for BigUint {
137138
}
138139
}
139140

140-
/// Convert a u32 chunk (len is either 1 or 2) to a single u64 digit
141-
#[inline]
142-
fn u32_chunk_to_u64(chunk: &[u32]) -> u64 {
143-
// raw could have odd length
144-
let mut digit = chunk[0] as u64;
145-
if let Some(&hi) = chunk.get(1) {
146-
digit |= (hi as u64) << 32;
147-
}
148-
digit
149-
}
150-
151141
impl Zero for BigUint {
152142
#[inline]
153143
fn zero() -> BigUint {
@@ -512,231 +502,6 @@ pub trait ToBigUint {
512502
fn to_biguint(&self) -> Option<BigUint>;
513503
}
514504

515-
/// An iterator of `u32` digits representation of a `BigUint` or `BigInt`,
516-
/// ordered least significant digit first.
517-
pub struct U32Digits<'a> {
518-
#[cfg(u64_digit)]
519-
data: &'a [u64],
520-
#[cfg(u64_digit)]
521-
next_is_lo: bool,
522-
#[cfg(u64_digit)]
523-
last_hi_is_zero: bool,
524-
525-
#[cfg(not(u64_digit))]
526-
it: core::slice::Iter<'a, u32>,
527-
}
528-
529-
#[cfg(u64_digit)]
530-
impl<'a> U32Digits<'a> {
531-
#[inline]
532-
fn new(data: &'a [u64]) -> Self {
533-
let last_hi_is_zero = data
534-
.last()
535-
.map(|&last| {
536-
let last_hi = (last >> 32) as u32;
537-
last_hi == 0
538-
})
539-
.unwrap_or(false);
540-
U32Digits {
541-
data,
542-
next_is_lo: true,
543-
last_hi_is_zero,
544-
}
545-
}
546-
}
547-
548-
#[cfg(u64_digit)]
549-
impl Iterator for U32Digits<'_> {
550-
type Item = u32;
551-
#[inline]
552-
fn next(&mut self) -> Option<u32> {
553-
match self.data.split_first() {
554-
Some((&first, data)) => {
555-
let next_is_lo = self.next_is_lo;
556-
self.next_is_lo = !next_is_lo;
557-
if next_is_lo {
558-
Some(first as u32)
559-
} else {
560-
self.data = data;
561-
if data.is_empty() && self.last_hi_is_zero {
562-
self.last_hi_is_zero = false;
563-
None
564-
} else {
565-
Some((first >> 32) as u32)
566-
}
567-
}
568-
}
569-
None => None,
570-
}
571-
}
572-
573-
#[inline]
574-
fn size_hint(&self) -> (usize, Option<usize>) {
575-
let len = self.len();
576-
(len, Some(len))
577-
}
578-
579-
#[inline]
580-
fn last(self) -> Option<u32> {
581-
self.data.last().map(|&last| {
582-
if self.last_hi_is_zero {
583-
last as u32
584-
} else {
585-
(last >> 32) as u32
586-
}
587-
})
588-
}
589-
590-
#[inline]
591-
fn count(self) -> usize {
592-
self.len()
593-
}
594-
}
595-
596-
#[cfg(u64_digit)]
597-
impl ExactSizeIterator for U32Digits<'_> {
598-
#[inline]
599-
fn len(&self) -> usize {
600-
self.data.len() * 2 - usize::from(self.last_hi_is_zero) - usize::from(!self.next_is_lo)
601-
}
602-
}
603-
604-
#[cfg(not(u64_digit))]
605-
impl<'a> U32Digits<'a> {
606-
#[inline]
607-
fn new(data: &'a [u32]) -> Self {
608-
Self { it: data.iter() }
609-
}
610-
}
611-
612-
#[cfg(not(u64_digit))]
613-
impl Iterator for U32Digits<'_> {
614-
type Item = u32;
615-
#[inline]
616-
fn next(&mut self) -> Option<u32> {
617-
self.it.next().cloned()
618-
}
619-
620-
#[inline]
621-
fn size_hint(&self) -> (usize, Option<usize>) {
622-
self.it.size_hint()
623-
}
624-
625-
#[inline]
626-
fn nth(&mut self, n: usize) -> Option<u32> {
627-
self.it.nth(n).cloned()
628-
}
629-
630-
#[inline]
631-
fn last(self) -> Option<u32> {
632-
self.it.last().cloned()
633-
}
634-
635-
#[inline]
636-
fn count(self) -> usize {
637-
self.it.count()
638-
}
639-
}
640-
641-
#[cfg(not(u64_digit))]
642-
impl ExactSizeIterator for U32Digits<'_> {
643-
#[inline]
644-
fn len(&self) -> usize {
645-
self.it.len()
646-
}
647-
}
648-
649-
impl FusedIterator for U32Digits<'_> {}
650-
651-
/// An iterator of `u64` digits representation of a `BigUint` or `BigInt`,
652-
/// ordered least significant digit first.
653-
pub struct U64Digits<'a> {
654-
#[cfg(not(u64_digit))]
655-
it: core::slice::Chunks<'a, u32>,
656-
657-
#[cfg(u64_digit)]
658-
it: core::slice::Iter<'a, u64>,
659-
}
660-
661-
#[cfg(not(u64_digit))]
662-
impl<'a> U64Digits<'a> {
663-
#[inline]
664-
fn new(data: &'a [u32]) -> Self {
665-
U64Digits { it: data.chunks(2) }
666-
}
667-
}
668-
669-
#[cfg(not(u64_digit))]
670-
impl Iterator for U64Digits<'_> {
671-
type Item = u64;
672-
#[inline]
673-
fn next(&mut self) -> Option<u64> {
674-
self.it.next().map(u32_chunk_to_u64)
675-
}
676-
677-
#[inline]
678-
fn size_hint(&self) -> (usize, Option<usize>) {
679-
let len = self.len();
680-
(len, Some(len))
681-
}
682-
683-
#[inline]
684-
fn last(self) -> Option<u64> {
685-
self.it.last().map(u32_chunk_to_u64)
686-
}
687-
688-
#[inline]
689-
fn count(self) -> usize {
690-
self.len()
691-
}
692-
}
693-
694-
#[cfg(u64_digit)]
695-
impl<'a> U64Digits<'a> {
696-
#[inline]
697-
fn new(data: &'a [u64]) -> Self {
698-
Self { it: data.iter() }
699-
}
700-
}
701-
702-
#[cfg(u64_digit)]
703-
impl Iterator for U64Digits<'_> {
704-
type Item = u64;
705-
#[inline]
706-
fn next(&mut self) -> Option<u64> {
707-
self.it.next().cloned()
708-
}
709-
710-
#[inline]
711-
fn size_hint(&self) -> (usize, Option<usize>) {
712-
self.it.size_hint()
713-
}
714-
715-
#[inline]
716-
fn nth(&mut self, n: usize) -> Option<u64> {
717-
self.it.nth(n).cloned()
718-
}
719-
720-
#[inline]
721-
fn last(self) -> Option<u64> {
722-
self.it.last().cloned()
723-
}
724-
725-
#[inline]
726-
fn count(self) -> usize {
727-
self.it.count()
728-
}
729-
}
730-
731-
impl ExactSizeIterator for U64Digits<'_> {
732-
#[inline]
733-
fn len(&self) -> usize {
734-
self.it.len()
735-
}
736-
}
737-
738-
impl FusedIterator for U64Digits<'_> {}
739-
740505
/// Creates and initializes a `BigUint`.
741506
///
742507
/// The digits are in little-endian base matching `BigDigit`.
@@ -1216,6 +981,17 @@ impl IntDigits for BigUint {
1216981
}
1217982
}
1218983

984+
/// Convert a u32 chunk (len is either 1 or 2) to a single u64 digit
985+
#[inline]
986+
fn u32_chunk_to_u64(chunk: &[u32]) -> u64 {
987+
// raw could have odd length
988+
let mut digit = chunk[0] as u64;
989+
if let Some(&hi) = chunk.get(1) {
990+
digit |= (hi as u64) << 32;
991+
}
992+
digit
993+
}
994+
1219995
/// Combine four `u32`s into a single `u128`.
1220996
#[cfg(any(test, not(u64_digit)))]
1221997
#[inline]
@@ -1319,45 +1095,3 @@ fn test_u128_u32_roundtrip() {
13191095
assert_eq!(u32_to_u128(a, b, c, d), *val);
13201096
}
13211097
}
1322-
1323-
#[test]
1324-
fn test_iter_u32_digits() {
1325-
let n = BigUint::from(5u8);
1326-
let mut it = n.iter_u32_digits();
1327-
assert_eq!(it.len(), 1);
1328-
assert_eq!(it.next(), Some(5));
1329-
assert_eq!(it.len(), 0);
1330-
assert_eq!(it.next(), None);
1331-
assert_eq!(it.len(), 0);
1332-
assert_eq!(it.next(), None);
1333-
1334-
let n = BigUint::from(112500000000u64);
1335-
let mut it = n.iter_u32_digits();
1336-
assert_eq!(it.len(), 2);
1337-
assert_eq!(it.next(), Some(830850304));
1338-
assert_eq!(it.len(), 1);
1339-
assert_eq!(it.next(), Some(26));
1340-
assert_eq!(it.len(), 0);
1341-
assert_eq!(it.next(), None);
1342-
}
1343-
1344-
#[test]
1345-
fn test_iter_u64_digits() {
1346-
let n = BigUint::from(5u8);
1347-
let mut it = n.iter_u64_digits();
1348-
assert_eq!(it.len(), 1);
1349-
assert_eq!(it.next(), Some(5));
1350-
assert_eq!(it.len(), 0);
1351-
assert_eq!(it.next(), None);
1352-
assert_eq!(it.len(), 0);
1353-
assert_eq!(it.next(), None);
1354-
1355-
let n = BigUint::from(18_446_744_073_709_551_616u128);
1356-
let mut it = n.iter_u64_digits();
1357-
assert_eq!(it.len(), 2);
1358-
assert_eq!(it.next(), Some(0));
1359-
assert_eq!(it.len(), 1);
1360-
assert_eq!(it.next(), Some(1));
1361-
assert_eq!(it.len(), 0);
1362-
assert_eq!(it.next(), None);
1363-
}

0 commit comments

Comments
 (0)