dashu-int 0.6.0

//! Definitions of [UBig].
//!
//! Conversion from internal representations including [Buffer][crate::buffer::Buffer], [TypedRepr], [TypedReprRef]
//! to [UBig] is not implemented, the designed way to construct UBig from them is first convert them
//! into [Repr], and then directly construct from the [Repr]. This restriction is set to make
//! the source type explicit.

use crate::repr::{Repr, TypedRepr, TypedReprRef};

/// An unsigned arbitrary precision integer.
///
/// `UBig` represents an arbitrarily large non-negative integer. Values that fit in a
/// [`DoubleWord`](crate::DoubleWord) are inlined (no heap allocation); larger values are stored as a
/// heap-allocated array of [`Word`](crate::Word)s. The type carries a niche bit, so
/// [`Option<UBig>`] occupies the same space as [`UBig`].
///
/// For the full discussion — construction, parsing, printing, and the memory layout — see the
/// [user guide](https://zyxin.xyz/dashu/types.html).
///
/// # Examples
///
/// Parsing and printing (base 2–36 is supported for string/literal parsing):
///
/// ```
/// # use dashu_base::ParseError;
/// # use dashu_int::{UBig, Word};
/// // parsing
/// let a = UBig::from(408580953453092208335085386466371u128);
/// let b = UBig::from(0x1231abcd4134u64);
/// let c = UBig::from_str_radix("a2a123bbb127779cccc123", 32)?;
/// let d = UBig::from_str_radix("1231abcd4134", 16)?;
/// assert_eq!(a, c);
/// assert_eq!(b, d);
///
/// // printing
/// assert_eq!(format!("{}", UBig::from(12u8)), "12");
/// assert_eq!(format!("{:#X}", UBig::from(0xabcdu16)), "0xABCD");
/// if Word::BITS == 64 {
///     // number of digits to display depends on the word size
///     assert_eq!(
///         format!("{:?}", UBig::ONE << 1000),
///         "1071508607186267320..4386837205668069376"
///     );
/// }
/// # Ok::<(), ParseError>(())
/// ```
///
/// The niche bit makes `Option<UBig>` free:
///
/// ```
/// # use dashu_int::UBig;
/// use core::mem::size_of;
/// assert_eq!(size_of::<UBig>(), size_of::<Option<UBig>>());
/// ```
#[derive(Eq, Hash, PartialEq)]
#[repr(transparent)]
pub struct UBig(pub(crate) Repr);

impl UBig {
    /// Get the representation of UBig.
    #[inline]
    pub(crate) const fn repr(&self) -> TypedReprRef<'_> {
        self.0.as_typed()
    }

    /// Convert into representation.
    #[inline]
    pub(crate) fn into_repr(self) -> TypedRepr {
        self.0.into_typed()
    }

    /// [UBig] with value 0
    pub const ZERO: Self = Self(Repr::zero());
    /// [UBig] with value 1
    pub const ONE: Self = Self(Repr::one());

    /// Get the raw representation in [Word][crate::Word]s.
    ///
    /// If the number is zero, then empty slice will be returned.
    ///
    /// # Examples
    ///
    /// ```
    /// # use dashu_int::{UBig, Word};
    /// assert_eq!(UBig::ZERO.as_words(), &[] as &[Word]);
    /// assert_eq!(UBig::ONE.as_words(), &[1]);
    /// ```
    #[inline]
    pub fn as_words(&self) -> &[crate::Word] {
        let (sign, words) = self.0.as_sign_slice();
        debug_assert!(matches!(sign, crate::Sign::Positive));
        words
    }

    /// Create a UBig from a single [Word][crate::Word].
    ///
    /// # Examples
    ///
    /// ```
    /// # use dashu_int::UBig;
    /// const ZERO: UBig = UBig::from_word(0);
    /// assert_eq!(ZERO, UBig::ZERO);
    /// const ONE: UBig = UBig::from_word(1);
    /// assert_eq!(ONE, UBig::ONE);
    /// ```
    #[inline]
    pub const fn from_word(word: crate::Word) -> Self {
        Self(Repr::from_word(word))
    }

    /// Create a UBig from a [DoubleWord][crate::DoubleWord].
    ///
    /// # Examples
    ///
    /// ```
    /// # use dashu_int::UBig;
    /// const ZERO: UBig = UBig::from_dword(0);
    /// assert_eq!(ZERO, UBig::ZERO);
    /// const ONE: UBig = UBig::from_dword(1);
    /// assert_eq!(ONE, UBig::ONE);
    /// ```
    #[inline]
    pub const fn from_dword(dword: crate::DoubleWord) -> Self {
        Self(Repr::from_dword(dword))
    }

    /// Create a UBig from a u64.
    ///
    /// This function is const on 32-bit and 64-bit targets.
    ///
    /// # Examples
    ///
    /// ```
    /// # use dashu_int::UBig;
    /// assert_eq!(UBig::from_u64(42), UBig::from(42u64));
    /// assert_eq!(UBig::from_u64(10_939_058_860_032_000), UBig::from(10_939_058_860_032_000u64));
    /// ```
    #[cfg(not(any(target_pointer_width = "16", force_bits = "16")))]
    #[inline]
    pub const fn from_u64(n: u64) -> Self {
        Self(Repr::from_dword(n as crate::DoubleWord))
    }

    /// Create a UBig from a u64.
    ///
    /// On 16-bit targets `u64` is wider than [`DoubleWord`][crate::DoubleWord], so this delegates
    /// to `From<u64>` and is not `const`; on 32-bit and 64-bit targets the `const` constructor
    /// above is used instead.
    #[cfg(any(target_pointer_width = "16", force_bits = "16"))]
    #[inline]
    pub fn from_u64(n: u64) -> Self {
        Self::from(n)
    }

    /// Convert a sequence of [Word][crate::Word]s into a UBig
    ///
    /// # Examples
    ///
    /// ```
    /// # use dashu_int::{UBig, Word};
    /// assert_eq!(UBig::from_words(&[] as &[Word]), UBig::ZERO);
    /// assert_eq!(UBig::from_words(&[1]), UBig::ONE);
    /// assert_eq!(UBig::from_words(&[1, 1]), (UBig::ONE << Word::BITS as usize) + UBig::ONE);
    /// ```
    #[inline]
    pub fn from_words(words: &[crate::Word]) -> Self {
        Self(Repr::from_buffer(words.into()))
    }

    /// Create an UBig from a static sequence of [Word][crate::Word]s. Similar to [from_words][UBig::from_words].
    ///
    /// The top word of the input word array must not be zero.
    ///
    /// This method is unsafe because it must be carefully handled. The generated instance
    /// must not be mutated or dropped. Therefore the correct usage is to assign it to an
    /// immutable static variable. Due to the risk, it's generally not recommended to use this method.
    /// This method is intended for the use of static creation macros.
    #[doc(hidden)]
    #[inline]
    pub const unsafe fn from_static_words(words: &'static [crate::Word]) -> Self {
        Self(Repr::from_static_words(words))
    }

    /// Check whether the value is 0
    ///
    /// # Examples
    ///
    /// ```
    /// # use dashu_int::UBig;
    /// assert!(UBig::ZERO.is_zero());
    /// assert!(!UBig::ONE.is_zero());
    /// ```
    #[inline]
    pub const fn is_zero(&self) -> bool {
        self.0.is_zero()
    }

    /// Check whether the value is 1
    ///
    /// # Examples
    ///
    /// ```
    /// # use dashu_int::UBig;
    /// assert!(!UBig::ZERO.is_one());
    /// assert!(UBig::ONE.is_one());
    /// ```
    #[inline]
    pub const fn is_one(&self) -> bool {
        self.0.is_one()
    }

    /// Create an integer with `n` consecutive one bits (i.e. 2^n - 1).
    ///
    /// # Examples
    ///
    /// ```
    /// # use dashu_int::UBig;
    /// let mut n = UBig::ZERO;
    /// n.set_bit(20);
    /// n -= UBig::ONE;
    /// assert_eq!(UBig::ones(20), n);
    /// ```
    #[inline]
    pub fn ones(n: usize) -> Self {
        Self(Repr::ones(n))
    }
}

// This custom implementation is necessary due to https://github.com/rust-lang/rust/issues/98374
impl Clone for UBig {
    #[inline]
    fn clone(&self) -> UBig {
        UBig(self.0.clone())
    }
    #[inline]
    fn clone_from(&mut self, source: &UBig) {
        self.0.clone_from(&source.0)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::{buffer::Buffer, DoubleWord, Word};

    impl UBig {
        /// Capacity in Words.
        #[inline]
        fn capacity(&self) -> usize {
            self.0.capacity()
        }
    }

    fn gen_ubig(num_words: usize) -> UBig {
        let mut buf = Buffer::allocate(num_words);
        for i in 0..num_words {
            buf.push(i as Word);
        }
        UBig(Repr::from_buffer(buf))
    }

    #[test]
    fn test_buffer_to_ubig() {
        let buf = Buffer::allocate(5);
        let num = UBig(Repr::from_buffer(buf));
        assert_eq!(num, UBig::ZERO);

        let mut buf = Buffer::allocate(5);
        buf.push(7);
        let num = UBig(Repr::from_buffer(buf));
        assert_eq!(num, UBig::from(7u8));

        let mut buf = Buffer::allocate(100);
        buf.push(7);
        buf.push(0);
        buf.push(0);
        let num = UBig(Repr::from_buffer(buf));
        assert_eq!(num, UBig::from(7u8));

        let mut buf = Buffer::allocate(5);
        buf.push(1);
        buf.push(2);
        buf.push(3);
        buf.push(4);
        let num = UBig(Repr::from_buffer(buf));
        assert_eq!(num.capacity(), 7);

        let mut buf = Buffer::allocate(100);
        buf.push(1);
        buf.push(2);
        buf.push(3);
        buf.push(4);
        let num = UBig(Repr::from_buffer(buf));
        assert_eq!(num.capacity(), 6);
    }

    #[test]
    fn test_clone() {
        let a = UBig::from(5u8);
        assert_eq!(a.clone(), a);

        let a = gen_ubig(10);
        let b = a.clone();
        assert_eq!(a, b);
        assert_eq!(a.capacity(), b.capacity());
    }

    #[test]
    fn test_clone_from() {
        let num: UBig = gen_ubig(10);

        let mut a = UBig::from(3u8);
        a.clone_from(&num);
        assert_eq!(a, num);
        let b = UBig::from(7u8);
        a.clone_from(&b);
        assert_eq!(a, b);
        a.clone_from(&b);
        assert_eq!(a, b);

        let mut a = gen_ubig(9);
        let prev_cap = a.capacity();
        a.clone_from(&num);
        // the buffer should be reused, 9 is close enough to 10.
        assert_eq!(a.capacity(), prev_cap);
        assert_ne!(a.capacity(), num.capacity());

        let mut a = gen_ubig(3);
        let prev_cap = a.capacity();
        a.clone_from(&num);
        // the buffer should now be reallocated, it's too Small.
        assert_ne!(a.capacity(), prev_cap);
        assert_eq!(a.capacity(), num.capacity());

        let mut a = gen_ubig(100);
        let prev_cap = a.capacity();
        a.clone_from(&num);
        // the buffer should now be reallocated, it's too large.
        assert_ne!(a.capacity(), prev_cap);
        assert_eq!(a.capacity(), num.capacity());
    }

    #[test]
    fn test_const_generation() {
        const ZERO: UBig = UBig::from_word(0);
        const ONE_SINGLE: UBig = UBig::from_word(1);
        const ONE_DOUBLE: UBig = UBig::from_dword(1);
        const DMAX: UBig = UBig::from_dword(DoubleWord::MAX);

        const CDATA: [Word; 3] = [Word::MAX, Word::MAX, Word::MAX];
        // SAFETY: DATA meets the requirements of from_static_words
        static CONST_TMAX: UBig = unsafe { UBig::from_static_words(&CDATA) };
        static DATA: [Word; 3] = [Word::MAX, Word::MAX, Word::MAX];
        // SAFETY: DATA meets the requirements of from_static_words
        static STATIC_TMAX: UBig = unsafe { UBig::from_static_words(&DATA) };

        assert_eq!(ZERO, UBig::ZERO);
        assert_eq!(ONE_SINGLE, UBig::ONE);
        assert_eq!(ONE_DOUBLE, UBig::ONE);
        assert_eq!(DMAX.capacity(), 2);
        assert_eq!(CONST_TMAX.capacity(), 3);
        assert_eq!(STATIC_TMAX.capacity(), 3);
    }
}