malachite_base/num/conversion/digits/
power_of_2_digit_iterable.rs

1// Copyright © 2025 Mikhail Hogrefe
2//
3// This file is part of Malachite.
4//
5// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
6// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
7// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
8
9use crate::num::arithmetic::traits::{DivRound, SaturatingSubAssign};
10use crate::num::basic::unsigneds::PrimitiveUnsigned;
11use crate::num::conversion::traits::{
12    ExactFrom, PowerOf2DigitIterable, PowerOf2DigitIterator, WrappingFrom,
13};
14use crate::num::logic::traits::BitBlockAccess;
15use crate::rounding_modes::RoundingMode::*;
16use core::marker::PhantomData;
17
18/// A double-ended iterator over the base-$2^k$ digits of an unsigned primitive integer.
19///
20/// This `struct` is created by the [`PowerOf2DigitIterable::power_of_2_digits`] function. See its
21/// documentation for more.
22#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
23pub struct PrimitivePowerOf2DigitIterator<T: PrimitiveUnsigned, U: PrimitiveUnsigned> {
24    pub(crate) value: T,
25    pub(crate) log_base: u64,
26    pub(crate) remaining: usize,
27    // If `n` is nonzero, this index initially points to the least-significant bit of the least-
28    // significant digit, and is left-shifted by `next`.
29    pub(crate) i: u64,
30    // If `n` is nonzero, this mask initially points to the least-significant bit of the most-
31    // significant nonzero digit, and is right-shifted by `next_back`.
32    pub(crate) j: u64,
33    phantom: PhantomData<*const U>,
34}
35
36impl<T: PrimitiveUnsigned, U: PrimitiveUnsigned + WrappingFrom<<T as BitBlockAccess>::Bits>>
37    Iterator for PrimitivePowerOf2DigitIterator<T, U>
38{
39    type Item = U;
40
41    fn next(&mut self) -> Option<U> {
42        if self.remaining != 0 {
43            let digit = U::wrapping_from(self.value.get_bits(self.i, self.i + self.log_base));
44            self.i += self.log_base;
45            self.remaining -= 1;
46            Some(digit)
47        } else {
48            None
49        }
50    }
51
52    fn size_hint(&self) -> (usize, Option<usize>) {
53        (self.remaining, Some(self.remaining))
54    }
55}
56
57impl<T: PrimitiveUnsigned, U: PrimitiveUnsigned + WrappingFrom<<T as BitBlockAccess>::Bits>>
58    DoubleEndedIterator for PrimitivePowerOf2DigitIterator<T, U>
59{
60    fn next_back(&mut self) -> Option<U> {
61        if self.remaining != 0 {
62            let digit = U::wrapping_from(self.value.get_bits(self.j, self.j + self.log_base));
63            self.j.saturating_sub_assign(self.log_base);
64            self.remaining -= 1;
65            Some(digit)
66        } else {
67            None
68        }
69    }
70}
71
72impl<T: PrimitiveUnsigned, U: PrimitiveUnsigned + WrappingFrom<<T as BitBlockAccess>::Bits>>
73    ExactSizeIterator for PrimitivePowerOf2DigitIterator<T, U>
74{
75}
76
77impl<T: PrimitiveUnsigned, U: PrimitiveUnsigned + WrappingFrom<<T as BitBlockAccess>::Bits>>
78    PowerOf2DigitIterator<U> for PrimitivePowerOf2DigitIterator<T, U>
79{
80    /// Retrieves base-$2^k$ digits by index.
81    ///
82    /// Indexing at or above the significant digit count returns zero.
83    ///
84    /// This function doesn't affect, and isn't affected by, the iterator's position.
85    ///
86    /// $f(x, k, i) = d_i$, where $0 \leq d_i < 2^k$ for all $i$ and
87    /// $$
88    /// \sum_{i=0}^\infty2^{ki}d_i = x.
89    /// $$
90    ///
91    /// # Worst-case complexity
92    /// Constant time and additional memory.
93    ///
94    /// # Examples
95    /// ```
96    /// use malachite_base::num::conversion::traits::{
97    ///     PowerOf2DigitIterable, PowerOf2DigitIterator,
98    /// };
99    ///
100    /// let digits = PowerOf2DigitIterable::<u8>::power_of_2_digits(0u8, 2);
101    /// assert_eq!(digits.get(0), 0);
102    ///
103    /// // 107 = 1101011b
104    /// let digits = PowerOf2DigitIterable::<u8>::power_of_2_digits(107u32, 2);
105    /// assert_eq!(digits.get(0), 3);
106    /// assert_eq!(digits.get(1), 2);
107    /// assert_eq!(digits.get(2), 2);
108    /// assert_eq!(digits.get(100), 0);
109    /// ```
110    fn get(&self, index: u64) -> U {
111        let i = index * self.log_base;
112        U::wrapping_from(self.value.get_bits(i, i + self.log_base))
113    }
114}
115
116fn power_of_2_digits<T: PrimitiveUnsigned, U: PrimitiveUnsigned>(
117    x: T,
118    log_base: u64,
119) -> PrimitivePowerOf2DigitIterator<T, U> {
120    assert_ne!(log_base, 0);
121    assert!(
122        log_base <= U::WIDTH,
123        "type {:?} is too small for a digit of width {}",
124        U::NAME,
125        log_base
126    );
127    let significant_digits = x.significant_bits().div_round(log_base, Ceiling).0;
128    PrimitivePowerOf2DigitIterator {
129        value: x,
130        log_base,
131        remaining: usize::exact_from(significant_digits),
132        i: 0,
133        j: significant_digits.saturating_sub(1) * log_base,
134        phantom: PhantomData,
135    }
136}
137
138macro_rules! impl_power_of_2_digit_iterable {
139    ($t:ident) => {
140        macro_rules! impl_power_of_2_digit_iterable_inner {
141            ($u:ident) => {
142                impl PowerOf2DigitIterable<$u> for $t {
143                    type PowerOf2DigitIterator = PrimitivePowerOf2DigitIterator<$t, $u>;
144
145                    /// Returns a double-ended iterator over the base-$2^k$ digits of a primitive
146                    /// unsigned integer.
147                    ///
148                    /// The forward order is ascending, so that less-significant digits appear
149                    /// first. There are no trailing zeros going forward, or leading zeros going
150                    /// backward.
151                    ///
152                    /// If it's necessary to get a [`Vec`] of all the digits, consider using
153                    /// [`to_power_of_2_digits_asc`](super::super::traits::PowerOf2Digits::to_power_of_2_digits_asc)
154                    /// or
155                    /// [`to_power_of_2_digits_desc`](super::super::traits::PowerOf2Digits::to_power_of_2_digits_desc)
156                    /// instead.
157                    ///
158                    /// # Worst-case complexity
159                    /// Constant time and additional memory.
160                    ///
161                    /// # Panics
162                    /// Panics if `log_base` is larger than the width of output type width.
163                    ///
164                    /// # Examples
165                    /// See [here](super::power_of_2_digit_iterable#power_of_2_digits).
166                    #[inline]
167                    fn power_of_2_digits(
168                        self,
169                        log_base: u64,
170                    ) -> PrimitivePowerOf2DigitIterator<$t, $u> {
171                        power_of_2_digits(self, log_base)
172                    }
173                }
174            };
175        }
176        apply_to_unsigneds!(impl_power_of_2_digit_iterable_inner);
177    };
178}
179apply_to_unsigneds!(impl_power_of_2_digit_iterable);
malachite_base/num/conversion/digits/power_of_2_digit_iterable.rs

malachite_base/num/conversion/digits/
power_of_2_digit_iterable.rs
