use crate::natural::logic::bit_block_access::limbs_slice_get_bits;
use crate::natural::logic::significant_bits::limbs_significant_bits;
use crate::natural::InnerNatural::{Large, Small};
use crate::natural::Natural;
use crate::platform::Limb;
use core::cmp::{min, Ordering};
use core::marker::PhantomData;
use core::slice::Chunks;
use malachite_base::num::arithmetic::traits::{
CheckedLogBase2, DivRound, FloorLogBase2, ModPowerOf2, PowerOf2, SaturatingSubAssign, ShrRound,
};
use malachite_base::num::basic::integers::PrimitiveInt;
use malachite_base::num::basic::traits::Zero;
use malachite_base::num::basic::unsigneds::PrimitiveUnsigned;
use malachite_base::num::conversion::digits::power_of_2_digit_iterable::*;
use malachite_base::num::conversion::traits::{
ExactFrom, PowerOf2DigitIterable, PowerOf2DigitIterator,
};
use malachite_base::num::logic::traits::LowMask;
use malachite_base::rounding_modes::RoundingMode;
#[doc(hidden)]
#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
pub struct FitsInLimbIterator<'a, T>(FILIterator<'a, T>);
#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
struct FILIterator<'a, T> {
limbs: &'a [Limb],
log_base: u64,
remaining: usize,
limb_i: usize,
limb_j: usize,
i: u64,
j: u64,
mask: Limb,
phantom: PhantomData<*const T>,
}
impl<'a, T: PrimitiveUnsigned> Iterator for FILIterator<'a, T> {
type Item = T;
fn next(&mut self) -> Option<T> {
if self.remaining != 0 {
let digit = T::wrapping_from((self.limbs[self.limb_i] >> self.i) & self.mask);
self.i += self.log_base;
if self.i == Limb::WIDTH {
self.i = 0;
self.limb_i += 1;
}
self.remaining -= 1;
Some(digit)
} else {
None
}
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
(self.remaining, Some(self.remaining))
}
}
impl<'a, T: PrimitiveUnsigned> DoubleEndedIterator for FILIterator<'a, T> {
fn next_back(&mut self) -> Option<T> {
if self.remaining != 0 {
let digit = T::wrapping_from((self.limbs[self.limb_j] >> self.j) & self.mask);
if self.j == 0 {
self.j = Limb::WIDTH - self.log_base;
self.limb_j.saturating_sub_assign(1);
} else {
self.j -= self.log_base;
}
self.remaining -= 1;
Some(digit)
} else {
None
}
}
}
impl<'a, T: PrimitiveUnsigned> ExactSizeIterator for FILIterator<'a, T> {}
impl<'a, T: PrimitiveUnsigned> PowerOf2DigitIterator<T> for FILIterator<'a, T> {
fn get(&self, index: u64) -> T {
let log_log_base = self.log_base.floor_log_base_2();
let log_ratio = Limb::LOG_WIDTH - log_log_base;
let limb_index = usize::exact_from(index >> log_ratio);
let digit_index = index.mod_power_of_2(log_ratio);
if limb_index < self.limbs.len() {
T::wrapping_from((self.limbs[limb_index] >> (digit_index << log_log_base)) & self.mask)
} else {
T::ZERO
}
}
}
#[doc(hidden)]
#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
pub struct SizeOfLimbIterator<'a, T>(SOLIterator<'a, T>);
#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
struct SOLIterator<'a, T> {
limbs: &'a [Limb],
remaining: usize,
i: usize,
j: usize,
phantom: PhantomData<*const T>,
}
impl<'a, T: PrimitiveUnsigned> Iterator for SOLIterator<'a, T> {
type Item = T;
fn next(&mut self) -> Option<T> {
if self.remaining != 0 {
let digit = T::wrapping_from(self.limbs[self.i]);
self.i += 1;
self.remaining -= 1;
Some(digit)
} else {
None
}
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
(self.remaining, Some(self.remaining))
}
}
impl<'a, T: PrimitiveUnsigned> DoubleEndedIterator for SOLIterator<'a, T> {
fn next_back(&mut self) -> Option<T> {
if self.remaining != 0 {
let digit = T::wrapping_from(self.limbs[self.j]);
self.j.saturating_sub_assign(1);
self.remaining -= 1;
Some(digit)
} else {
None
}
}
}
impl<'a, T: PrimitiveUnsigned> ExactSizeIterator for SOLIterator<'a, T> {}
impl<'a, T: PrimitiveUnsigned> SOLIterator<'a, T> {
fn get(&self, index: u64) -> T {
let index = usize::exact_from(index);
if index < self.limbs.len() {
T::wrapping_from(self.limbs[index])
} else {
T::ZERO
}
}
}
#[doc(hidden)]
#[derive(Clone, Debug)]
pub struct MultipleOfLimbIterator<'a, T>(MOLIterator<'a, T>);
#[derive(Clone, Debug)]
struct MOLIterator<'a, T> {
log_ratio: u64,
limbs: &'a [Limb],
chunks: Chunks<'a, Limb>,
phantom: PhantomData<*const T>,
}
impl<'a, T: PrimitiveUnsigned> Iterator for MOLIterator<'a, T> {
type Item = T;
fn next(&mut self) -> Option<T> {
self.chunks.next().map(T::from_other_type_slice)
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.chunks.size_hint()
}
}
impl<'a, T: PrimitiveUnsigned> DoubleEndedIterator for MOLIterator<'a, T> {
fn next_back(&mut self) -> Option<T> {
self.chunks.next_back().map(T::from_other_type_slice)
}
}
impl<'a, T: PrimitiveUnsigned> ExactSizeIterator for MOLIterator<'a, T> {}
impl<'a, T: PrimitiveUnsigned> PowerOf2DigitIterator<T> for MOLIterator<'a, T> {
fn get(&self, index: u64) -> T {
let start_index = usize::exact_from(index << self.log_ratio);
if start_index >= self.limbs.len() {
T::ZERO
} else {
let end_index = min(
self.limbs.len(),
start_index + usize::power_of_2(self.log_ratio),
);
T::from_other_type_slice(&self.limbs[start_index..end_index])
}
}
}
#[doc(hidden)]
#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
pub struct IrregularIterator<'a, T>(IIterator<'a, T>);
#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
struct IIterator<'a, T> {
limbs: &'a [Limb],
log_base: u64,
remaining: usize,
i: u64,
j: u64,
phantom: PhantomData<*const T>,
}
impl<'a, T: PrimitiveUnsigned> Iterator for IIterator<'a, T> {
type Item = T;
fn next(&mut self) -> Option<T> {
if self.remaining != 0 {
let digit = self.get(self.i);
self.i += 1;
self.remaining -= 1;
Some(digit)
} else {
None
}
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
(self.remaining, Some(self.remaining))
}
}
impl<'a, T: PrimitiveUnsigned> DoubleEndedIterator for IIterator<'a, T> {
fn next_back(&mut self) -> Option<T> {
if self.remaining != 0 {
let digit = self.get(self.j);
self.j.saturating_sub_assign(1);
self.remaining -= 1;
Some(digit)
} else {
None
}
}
}
impl<'a, T: PrimitiveUnsigned> ExactSizeIterator for IIterator<'a, T> {}
impl<'a, T: PrimitiveUnsigned> IIterator<'a, T> {
fn get(&self, index: u64) -> T {
let start = index * self.log_base;
let limb_start = usize::exact_from(start >> Limb::LOG_WIDTH);
let len = self.limbs.len();
let mut result = T::ZERO;
if limb_start >= len {
return result;
}
let mut result_index = 0;
let mut limb_index = start & Limb::WIDTH_MASK;
for &limb in &self.limbs[limb_start..] {
let remaining_result_bits = self.log_base - result_index;
let remaining_limb_bits = Limb::WIDTH - limb_index;
if remaining_limb_bits <= remaining_result_bits {
result |= T::wrapping_from(limb >> limb_index) << result_index;
result_index += remaining_limb_bits;
limb_index = 0;
} else {
result |=
T::wrapping_from((limb >> limb_index).mod_power_of_2(remaining_result_bits))
<< result_index;
break;
}
}
result
}
}
#[derive(Clone, Debug)]
pub enum NaturalPowerOf2DigitPrimitiveIterator<'a, T: PrimitiveUnsigned> {
Small(PrimitivePowerOf2DigitIterator<Limb, T>),
FitsInLimb(FitsInLimbIterator<'a, T>),
SizeOfLimb(SizeOfLimbIterator<'a, T>),
MultipleOfLimb(MultipleOfLimbIterator<'a, T>),
Irregular(IrregularIterator<'a, T>),
}
impl<'a, T: PrimitiveUnsigned> Iterator for NaturalPowerOf2DigitPrimitiveIterator<'a, T> {
type Item = T;
fn next(&mut self) -> Option<T> {
match *self {
NaturalPowerOf2DigitPrimitiveIterator::Small(ref mut xs) => xs.next(),
NaturalPowerOf2DigitPrimitiveIterator::FitsInLimb(ref mut xs) => xs.0.next(),
NaturalPowerOf2DigitPrimitiveIterator::SizeOfLimb(ref mut xs) => xs.0.next(),
NaturalPowerOf2DigitPrimitiveIterator::MultipleOfLimb(ref mut xs) => xs.0.next(),
NaturalPowerOf2DigitPrimitiveIterator::Irregular(ref mut xs) => xs.0.next(),
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
match *self {
NaturalPowerOf2DigitPrimitiveIterator::Small(ref xs) => xs.size_hint(),
NaturalPowerOf2DigitPrimitiveIterator::FitsInLimb(ref xs) => xs.0.size_hint(),
NaturalPowerOf2DigitPrimitiveIterator::SizeOfLimb(ref xs) => xs.0.size_hint(),
NaturalPowerOf2DigitPrimitiveIterator::MultipleOfLimb(ref xs) => xs.0.size_hint(),
NaturalPowerOf2DigitPrimitiveIterator::Irregular(ref xs) => xs.0.size_hint(),
}
}
}
impl<'a, T: PrimitiveUnsigned> DoubleEndedIterator
for NaturalPowerOf2DigitPrimitiveIterator<'a, T>
{
fn next_back(&mut self) -> Option<T> {
match *self {
NaturalPowerOf2DigitPrimitiveIterator::Small(ref mut xs) => xs.next_back(),
NaturalPowerOf2DigitPrimitiveIterator::FitsInLimb(ref mut xs) => xs.0.next_back(),
NaturalPowerOf2DigitPrimitiveIterator::SizeOfLimb(ref mut xs) => xs.0.next_back(),
NaturalPowerOf2DigitPrimitiveIterator::MultipleOfLimb(ref mut xs) => xs.0.next_back(),
NaturalPowerOf2DigitPrimitiveIterator::Irregular(ref mut xs) => xs.0.next_back(),
}
}
}
impl<'a, T: PrimitiveUnsigned> ExactSizeIterator for NaturalPowerOf2DigitPrimitiveIterator<'a, T> {}
impl<'a, T: PrimitiveUnsigned> PowerOf2DigitIterator<T>
for NaturalPowerOf2DigitPrimitiveIterator<'a, T>
{
fn get(&self, index: u64) -> T {
match *self {
NaturalPowerOf2DigitPrimitiveIterator::Small(ref xs) => xs.get(index),
NaturalPowerOf2DigitPrimitiveIterator::FitsInLimb(ref xs) => xs.0.get(index),
NaturalPowerOf2DigitPrimitiveIterator::SizeOfLimb(ref xs) => xs.0.get(index),
NaturalPowerOf2DigitPrimitiveIterator::MultipleOfLimb(ref xs) => xs.0.get(index),
NaturalPowerOf2DigitPrimitiveIterator::Irregular(ref xs) => xs.0.get(index),
}
}
}
fn fits_in_limb_iterator<T: PrimitiveUnsigned>(
xs: &[Limb],
log_base: u64,
) -> FitsInLimbIterator<'_, T> {
let significant_bits = limbs_significant_bits(xs);
let log_log_base = log_base.floor_log_base_2();
let significant_digits = significant_bits
.shr_round(log_log_base, RoundingMode::Ceiling)
.0;
FitsInLimbIterator(FILIterator {
limbs: xs,
log_base,
remaining: usize::exact_from(significant_digits),
limb_i: 0,
limb_j: xs.len() - 1,
i: 0,
j: (significant_digits - 1).mod_power_of_2(Limb::LOG_WIDTH - log_log_base) << log_log_base,
mask: Limb::low_mask(log_base),
phantom: PhantomData,
})
}
const fn size_of_limb_iterator<T: PrimitiveUnsigned>(xs: &[Limb]) -> SizeOfLimbIterator<'_, T> {
SizeOfLimbIterator(SOLIterator {
limbs: xs,
remaining: xs.len(),
i: 0,
j: xs.len() - 1,
phantom: PhantomData,
})
}
fn multiple_of_limb_iterator<T: PrimitiveUnsigned>(
xs: &[Limb],
log_base: u64,
) -> MultipleOfLimbIterator<'_, T> {
let log_log_base = log_base.floor_log_base_2();
let log_ratio = log_log_base - Limb::LOG_WIDTH;
MultipleOfLimbIterator(MOLIterator {
log_ratio,
limbs: xs,
chunks: xs.chunks(usize::power_of_2(log_ratio)),
phantom: PhantomData,
})
}
fn irregular_iterator<T: PrimitiveUnsigned>(
xs: &[Limb],
log_base: u64,
) -> IrregularIterator<'_, T> {
let significant_digits = limbs_significant_bits(xs)
.div_round(log_base, RoundingMode::Ceiling)
.0;
IrregularIterator(IIterator {
limbs: xs,
log_base,
remaining: usize::exact_from(significant_digits),
i: 0,
j: significant_digits - 1,
phantom: PhantomData,
})
}
fn power_of_2_digits<T: PrimitiveUnsigned>(
x: &Natural,
log_base: u64,
) -> NaturalPowerOf2DigitPrimitiveIterator<T>
where
Limb: PowerOf2DigitIterable<T, PowerOf2DigitIterator = PrimitivePowerOf2DigitIterator<Limb, T>>,
{
assert_ne!(log_base, 0);
if log_base > T::WIDTH {
panic!(
"type {:?} is too small for a digit of width {}",
T::NAME,
log_base
);
}
match x {
Natural(Small(small)) => NaturalPowerOf2DigitPrimitiveIterator::Small(
PowerOf2DigitIterable::<T>::power_of_2_digits(*small, log_base),
),
Natural(Large(ref limbs)) => {
if let Some(log_log_base) = log_base.checked_log_base_2() {
match log_log_base.cmp(&Limb::LOG_WIDTH) {
Ordering::Equal => NaturalPowerOf2DigitPrimitiveIterator::SizeOfLimb(
size_of_limb_iterator(limbs),
),
Ordering::Less => NaturalPowerOf2DigitPrimitiveIterator::FitsInLimb(
fits_in_limb_iterator(limbs, log_base),
),
Ordering::Greater => NaturalPowerOf2DigitPrimitiveIterator::MultipleOfLimb(
multiple_of_limb_iterator(limbs, log_base),
),
}
} else {
NaturalPowerOf2DigitPrimitiveIterator::Irregular(irregular_iterator(
limbs, log_base,
))
}
}
}
}
macro_rules! iterables {
(
$t: ident
) => {
impl<'a> PowerOf2DigitIterable<$t> for &'a Natural {
type PowerOf2DigitIterator = NaturalPowerOf2DigitPrimitiveIterator<'a, $t>;
#[inline]
fn power_of_2_digits(
self,
log_base: u64,
) -> NaturalPowerOf2DigitPrimitiveIterator<'a, $t> {
power_of_2_digits(self, log_base)
}
}
};
}
apply_to_unsigneds!(iterables);
#[doc(hidden)]
#[derive(Clone, Debug)]
pub struct NaturalMultipleOfLimbIterator<'a>(NMOLIterator<'a>);
#[derive(Clone, Debug)]
struct NMOLIterator<'a> {
log_ratio: u64,
limbs: &'a [Limb],
chunks: Chunks<'a, Limb>,
}
impl<'a> Iterator for NMOLIterator<'a> {
type Item = Natural;
fn next(&mut self) -> Option<Natural> {
self.chunks.next().map(Natural::from_limbs_asc)
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.chunks.size_hint()
}
}
impl<'a> DoubleEndedIterator for NMOLIterator<'a> {
fn next_back(&mut self) -> Option<Natural> {
self.chunks.next_back().map(Natural::from_limbs_asc)
}
}
impl<'a> ExactSizeIterator for NMOLIterator<'a> {}
impl<'a> PowerOf2DigitIterator<Natural> for NMOLIterator<'a> {
fn get(&self, index: u64) -> Natural {
let start_index = usize::exact_from(index << self.log_ratio);
if start_index >= self.limbs.len() {
Natural::ZERO
} else {
let end_index = min(
self.limbs.len(),
start_index + usize::power_of_2(self.log_ratio),
);
Natural::from_limbs_asc(&self.limbs[start_index..end_index])
}
}
}
#[doc(hidden)]
#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
pub struct NaturalIrregularIterator<'a>(NIIterator<'a>);
#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
struct NIIterator<'a> {
limbs: &'a [Limb],
log_base: u64,
remaining: usize,
i: u64,
j: u64,
}
impl<'a> Iterator for NIIterator<'a> {
type Item = Natural;
fn next(&mut self) -> Option<Natural> {
if self.remaining != 0 {
let digit = self.get(self.i);
self.i += 1;
self.remaining -= 1;
Some(digit)
} else {
None
}
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
(self.remaining, Some(self.remaining))
}
}
impl<'a> DoubleEndedIterator for NIIterator<'a> {
fn next_back(&mut self) -> Option<Natural> {
if self.remaining != 0 {
let digit = self.get(self.j);
self.j.saturating_sub_assign(1);
self.remaining -= 1;
Some(digit)
} else {
None
}
}
}
impl<'a> ExactSizeIterator for NIIterator<'a> {}
impl<'a> NIIterator<'a> {
fn get(&self, index: u64) -> Natural {
let start_index = index.checked_mul(self.log_base).unwrap();
Natural::from_owned_limbs_asc(limbs_slice_get_bits(
self.limbs,
start_index,
start_index + self.log_base,
))
}
}
#[derive(Clone, Debug)]
pub enum NaturalPowerOf2DigitIterator<'a> {
Small(PrimitivePowerOf2DigitIterator<Limb, Limb>),
SmallerThanLimb(NaturalPowerOf2DigitPrimitiveIterator<'a, Limb>),
MultipleOfLimb(NaturalMultipleOfLimbIterator<'a>),
Irregular(NaturalIrregularIterator<'a>),
}
impl<'a> Iterator for NaturalPowerOf2DigitIterator<'a> {
type Item = Natural;
fn next(&mut self) -> Option<Natural> {
match *self {
NaturalPowerOf2DigitIterator::Small(ref mut xs) => xs.next().map(Natural::from),
NaturalPowerOf2DigitIterator::SmallerThanLimb(ref mut xs) => {
xs.next().map(Natural::from)
}
NaturalPowerOf2DigitIterator::MultipleOfLimb(ref mut xs) => xs.0.next(),
NaturalPowerOf2DigitIterator::Irregular(ref mut xs) => xs.0.next(),
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
match *self {
NaturalPowerOf2DigitIterator::Small(ref xs) => xs.size_hint(),
NaturalPowerOf2DigitIterator::SmallerThanLimb(ref xs) => xs.size_hint(),
NaturalPowerOf2DigitIterator::MultipleOfLimb(ref xs) => xs.0.size_hint(),
NaturalPowerOf2DigitIterator::Irregular(ref xs) => xs.0.size_hint(),
}
}
}
impl<'a> DoubleEndedIterator for NaturalPowerOf2DigitIterator<'a> {
fn next_back(&mut self) -> Option<Natural> {
match *self {
NaturalPowerOf2DigitIterator::Small(ref mut xs) => xs.next_back().map(Natural::from),
NaturalPowerOf2DigitIterator::SmallerThanLimb(ref mut xs) => {
xs.next_back().map(Natural::from)
}
NaturalPowerOf2DigitIterator::MultipleOfLimb(ref mut xs) => xs.0.next_back(),
NaturalPowerOf2DigitIterator::Irregular(ref mut xs) => xs.0.next_back(),
}
}
}
impl<'a> ExactSizeIterator for NaturalPowerOf2DigitIterator<'a> {}
impl<'a> PowerOf2DigitIterator<Natural> for NaturalPowerOf2DigitIterator<'a> {
fn get(&self, index: u64) -> Natural {
match *self {
NaturalPowerOf2DigitIterator::Small(ref xs) => Natural::from(xs.get(index)),
NaturalPowerOf2DigitIterator::SmallerThanLimb(ref xs) => Natural::from(xs.get(index)),
NaturalPowerOf2DigitIterator::MultipleOfLimb(ref xs) => xs.0.get(index),
NaturalPowerOf2DigitIterator::Irregular(ref xs) => xs.0.get(index),
}
}
}
fn multiple_of_limb_fn(xs: &[Limb], log_base: u64) -> NaturalMultipleOfLimbIterator<'_> {
let log_ratio = log_base.floor_log_base_2() - Limb::LOG_WIDTH;
NaturalMultipleOfLimbIterator(NMOLIterator {
log_ratio,
limbs: xs,
chunks: xs.chunks(usize::power_of_2(log_ratio)),
})
}
fn irregular_fn(xs: &[Limb], log_base: u64) -> NaturalIrregularIterator<'_> {
let significant_digits = limbs_significant_bits(xs)
.div_round(log_base, RoundingMode::Ceiling)
.0;
NaturalIrregularIterator(NIIterator {
limbs: xs,
log_base,
remaining: usize::exact_from(significant_digits),
i: 0,
j: significant_digits - 1,
})
}
impl<'a> PowerOf2DigitIterable<Natural> for &'a Natural {
type PowerOf2DigitIterator = NaturalPowerOf2DigitIterator<'a>;
fn power_of_2_digits(self, log_base: u64) -> NaturalPowerOf2DigitIterator<'a> {
assert_ne!(log_base, 0);
match self {
Natural(Small(small)) => NaturalPowerOf2DigitIterator::Small(PowerOf2DigitIterable::<
Limb,
>::power_of_2_digits(
*small,
min(log_base, Limb::WIDTH),
)),
Natural(Large(ref limbs)) => {
if let Some(log_log_base) = log_base.checked_log_base_2() {
if log_log_base <= Limb::LOG_WIDTH {
NaturalPowerOf2DigitIterator::SmallerThanLimb(
PowerOf2DigitIterable::<Limb>::power_of_2_digits(self, log_base),
)
} else {
NaturalPowerOf2DigitIterator::MultipleOfLimb(multiple_of_limb_fn(
limbs, log_base,
))
}
} else {
NaturalPowerOf2DigitIterator::Irregular(irregular_fn(limbs, log_base))
}
}
}
}
}