bigint_base10/

lib.rs

//! This crate contains the [`BigInteger`] type.
//!
//! The API is currently experimental and is subject to change.
//!
//! # Example
//!
//! There are currently two ways of creating a [`BigInteger`].
//!
//! Using a string literal.
//!
//! ```
//! // This is only necessary for 2015.
//! extern crate bigint_base10;
//!
//! use bigint_base10::BigInteger;
//!
//! let my_int = BigInteger::new("123");
//!
//! assert_eq!(format!("{}", my_int), "+123");
//! ```
//!
//! Using a vector of `u8` values.
//!
//! ```
//! # use bigint_base10::BigInteger;
//! use bigint_base10::Sign;
//!
//! let digits = [1, 2, 3];
//! let my_int = BigInteger::from_digits(&digits, Sign::Positive);
//!
//! assert_eq!(format!("{}", my_int), "+123");
//! ```
//!
//! [`BigInteger`]: struct.BigInteger.html

use std::char;
use std::cmp::Ordering;
use std::fmt;
use std::iter;
use std::iter::{DoubleEndedIterator, Iterator};
use std::ops::{Add, Deref, Index, Mul, Neg, Shl, Sub};

mod ops;

/// Sign indicating postivity of a value.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Sign {
    Positive,
    Negative,
    NoSign,
}

impl Sign {
    /// Return `true` if the enum value is positive, `false` otherwise.
    pub fn is_positive(self) -> bool {
        match self {
            Sign::Positive => true,
            _ => false,
        }
    }

    /// Return `true` if the enum value is negative, `false` otherwise.
    pub fn is_negative(self) -> bool {
        match self {
            Sign::Negative => true,
            _ => false,
        }
    }

    /// Return `true` if the enum value has no sign (equivalent to zero), `false` otherwise.
    pub fn is_nosign(self) -> bool {
        match self {
            Sign::NoSign => true,
            _ => false,
        }
    }
}

impl fmt::Display for Sign {
    fn fmt(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
        match *self {
            Sign::Positive => write!(formatter, "+"),
            Sign::Negative => write!(formatter, "-"),
            Sign::NoSign => Ok(()),
        }
    }
}

// FIXME: Implement Eq.
// FIXME: Implement Ord.
// FIXME: Implement Shr.
// TODO: Implement conversion to/from POD integer.
// TODO: Optimize operations to write to u8 buffer in-place (mut self).
/// A type for arbitrarily-long representations of integer values.
///
/// This is helpful for representing integer values that are expected
/// to exceed the largest representation possible with "plain-old-data"
/// types, i.e. `u64` / `i64`.
///
/// Usage is demonstrated in crate documentation.
#[derive(Clone, Debug, PartialEq)]
pub struct BigInteger {
    digits: Vec<u8>,
    sign: Sign,
}

impl BigInteger {
    /// Create a `BigInteger` from string representation.
    ///
    /// # Example
    ///
    /// Requires a minimum of one digit to initialize a `BigInteger`.
    /// The value is assumed to be positive by default.
    ///
    /// ```
    /// # use bigint_base10::BigInteger;
    /// let my_int = BigInteger::new("1");
    ///
    /// assert_eq!(format!("{}", my_int), "+1");
    /// ```
    ///
    /// A sign can be specified.
    ///
    /// ```
    /// # use bigint_base10::BigInteger;
    /// let my_int = BigInteger::new("-1");
    ///
    /// assert_eq!(format!("{}", my_int), "-1");
    /// ```
    ///
    /// Zero has no sign. Any provided signs are discarded.
    ///
    /// ```
    /// # use bigint_base10::BigInteger;
    /// let my_int = BigInteger::new("-0");
    ///
    /// assert_eq!(format!("{}", my_int), "0");
    /// ```
    ///
    /// # Panics
    ///
    /// - If the literal is empty.
    /// - If invalid numeric characters are passed in the literal.
    pub fn new(literal: &str) -> BigInteger {
        // FIXME: to_digit() also converts A-Z, a-z characters.
        let char_to_digit = |character: char| {
            character
                .to_digit(10)
                .expect("BigInteger literal must use numeric characters") as u8
        };

        let mut digits: Vec<u8> = Vec::new();
        let mut chars = literal.chars();

        // Process the first character. This may be a sign or a digit.
        let sign = match chars.next() {
            Some(character) if character == '+' => Sign::Positive,
            Some(character) if character == '-' => Sign::Negative,
            Some(character) => {
                digits.push(char_to_digit(character));

                // We assume the value is positive by default.
                Sign::Positive
            }
            None => panic!("BigInteger literal must begin with a sign or a digit"),
        };

        // Process the rest of the characters as digits.
        digits.extend(chars.map(char_to_digit));

        BigInteger::from_digits(&digits[..], sign)
    }

    /// Create a `BigInteger` from a slice of `u8` digits.
    pub fn from_digits(digits: &[u8], sign: Sign) -> BigInteger {
        let digits = Vec::from(digits);

        let mut result = BigInteger { digits, sign };

        result.trim();
        result
    }

    /// Return `true` if the integer value is positive, `false` otherwise.
    pub fn is_positive(&self) -> bool {
        self.sign.is_positive()
    }

    /// Return `true` if the integer value is negative, `false` otherwise.
    pub fn is_negative(&self) -> bool {
        self.sign.is_negative()
    }

    /// Count the number of digits in the integer.
    pub fn count(&self) -> usize {
        self.digits.len()
    }

    /// View the integer as a slice of the contained digits.
    pub fn as_slice(&self) -> &[u8] {
        self
    }

    /// Return an iterator of digits from smallest unit to the largest
    /// (right-to-left).
    ///
    /// # Example
    ///
    /// Usage.
    ///
    /// ```
    /// # use bigint_base10::BigInteger;
    /// let my_int = BigInteger::new("123");
    ///
    /// let mut iter = my_int.digits();
    ///
    /// assert_eq!(iter.next(), Some(3));
    /// assert_eq!(iter.next(), Some(2));
    /// assert_eq!(iter.next(), Some(1));
    /// assert_eq!(iter.next(), None);
    /// ```
    pub fn digits(&self) -> impl Iterator<Item = u8> + DoubleEndedIterator + '_ {
        // TODO: Check rev() performance. Since the elements should be
        // contiguous, I imagine this should be reasonably fast.
        self.digits.iter().cloned().rev()
    }

    /// Filter extraneous digits from digits buffer in integer.
    fn trim(&mut self) {
        // Prune zeroes at the beginning of the digits.
        // TODO: Is there a way to perform this in-place?
        self.digits = self
            .digits
            .iter()
            .cloned()
            .skip_while(|&digit| digit == 0)
            .collect();

        // If no digits remain, we assume the integer represents zero.
        if self.digits.is_empty() {
            self.digits.push(0);
            self.sign = Sign::NoSign;
        }
    }
}

impl fmt::Display for BigInteger {
    fn fmt(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
        let mut display_value = String::new();

        display_value.extend(self.digits.iter().map(|digit| {
            char::from_digit(u32::from(*digit), 10)
                .expect("Error occured whilst encoding BigInteger digit")
        }));

        write!(formatter, "{}{}", self.sign, display_value)
    }
}

impl Deref for BigInteger {
    type Target = Vec<u8>;

    fn deref(&self) -> &Vec<u8> {
        &self.digits
    }
}

impl Index<usize> for BigInteger {
    type Output = u8;

    fn index(&self, index: usize) -> &u8 {
        &self.digits[index]
    }
}

impl PartialOrd for BigInteger {
    fn partial_cmp(&self, other: &BigInteger) -> Option<Ordering> {
        // FIXME: Handle zero.

        match (self.is_positive(), other.is_positive()) {
            (true, true) => Some(ops::cmp(self, other)),
            (false, true) => Some(Ordering::Less),
            (true, false) => Some(Ordering::Greater),
            (false, false) => {
                // The result is reversed if both integers are negative.
                match ops::cmp(self, other) {
                    Ordering::Less => Some(Ordering::Greater),
                    Ordering::Equal => Some(Ordering::Equal),
                    Ordering::Greater => Some(Ordering::Less),
                }
            }
        }
    }
}

impl Neg for BigInteger {
    type Output = BigInteger;

    fn neg(mut self) -> BigInteger {
        self.sign = match self.sign {
            Sign::Positive => Sign::Negative,
            Sign::NoSign => Sign::NoSign,
            Sign::Negative => Sign::Negative,
        };
        self
    }
}

impl Shl<usize> for BigInteger {
    type Output = Self;

    fn shl(mut self, count: usize) -> BigInteger {
        self.digits.extend(iter::repeat(0u8).take(count));
        self
    }
}

impl<'a> Add<&'a BigInteger> for BigInteger {
    type Output = Self;

    fn add(self, other: &BigInteger) -> BigInteger {
        match (self.sign, other.sign) {
            (Sign::NoSign, Sign::NoSign) => self,
            (Sign::NoSign, _) => other.clone(),
            (_, Sign::NoSign) => self,
            (Sign::Positive, Sign::Positive) => ops::add(&self, other),
            (Sign::Negative, Sign::Positive) => ops::sub(other, &self),
            (Sign::Positive, Sign::Negative) => ops::sub(&self, other),
            (Sign::Negative, Sign::Negative) => -ops::add(&self, other),
        }
    }
}

impl<'a> Sub<&'a BigInteger> for BigInteger {
    type Output = Self;

    fn sub(self, other: &BigInteger) -> BigInteger {
        match (self.sign, other.sign) {
            (Sign::NoSign, Sign::NoSign) => self,
            (Sign::NoSign, _) => other.clone(),
            (_, Sign::NoSign) => self,
            (Sign::Positive, Sign::Positive) => ops::sub(&self, other),
            (Sign::Negative, Sign::Positive) => -ops::add(&self, other),
            (Sign::Positive, Sign::Negative) => ops::add(&self, other),
            (Sign::Negative, Sign::Negative) => ops::sub(other, &self),
        }
    }
}

impl<'a> Mul<&'a BigInteger> for BigInteger {
    type Output = Self;

    #[allow(clippy::suspicious_arithmetic_impl)]
    fn mul(self, other: &BigInteger) -> BigInteger {
        if self.sign.is_nosign() || other.sign.is_nosign() {
            return BigInteger::from_digits(&[0], Sign::NoSign);
        }

        let positive = self.is_positive() == other.is_positive();

        let mut result = ops::mul(&self, other);

        result.sign = if positive {
            Sign::Positive
        } else {
            Sign::Negative
        };
        result
    }
}

#[cfg(test)]
mod tests {
    use super::BigInteger;

    ///////////////////////////////////////////////////////////////////////////

    #[test]
    fn new_from_literal() {
        assert_eq!(BigInteger::new("123456789").to_string(), "+123456789");
    }

    #[test]
    fn new_from_positive_literal() {
        assert_eq!(BigInteger::new("+123456789").to_string(), "+123456789");
    }

    #[test]
    fn new_from_negative_literal() {
        assert_eq!(BigInteger::new("-123456789").to_string(), "-123456789");
    }

    #[test]
    fn new_with_extraneous_zeroes() {
        assert_eq!(BigInteger::new("000001").to_string(), "+1");
    }

    ///////////////////////////////////////////////////////////////////////////

    #[test]
    fn add_single_digits() {
        let result = BigInteger::new("2") + &BigInteger::new("2");

        assert_eq!(result, BigInteger::new("4"));
    }

    #[test]
    fn add_zero() {
        let result = BigInteger::new("2") + &BigInteger::new("0");

        assert_eq!(result, BigInteger::new("2"));
    }

    #[test]
    fn add_with_carry() {
        let result = BigInteger::new("6") + &BigInteger::new("6");

        assert_eq!(result, BigInteger::new("12"));
    }

    #[test]
    fn add_multiple_digits() {
        let result = BigInteger::new("123") + &BigInteger::new("456");

        assert_eq!(result, BigInteger::new("579"));
    }

    #[test]
    fn add_large() {
        let result = BigInteger::new("999999999999") + &BigInteger::new("999999999999");

        assert_eq!(result, BigInteger::new("1999999999998"));
    }

    #[test]
    fn add_negative() {
        let result = BigInteger::new("456") + &BigInteger::new("-123");

        assert_eq!(result, BigInteger::new("333"));
    }

    ///////////////////////////////////////////////////////////////////////////

    #[test]
    fn subtract_single_digits() {
        let result = BigInteger::new("4") - &BigInteger::new("2");

        assert_eq!(result, BigInteger::new("2"));
    }

    #[test]
    fn subtract_zero() {
        let result = BigInteger::new("2") - &BigInteger::new("0");

        assert_eq!(result, BigInteger::new("2"));
    }

    #[test]
    fn subtract_multiple_digits() {
        let result = BigInteger::new("456") - &BigInteger::new("123");

        assert_eq!(result, BigInteger::new("333"));
    }

    #[test]
    fn subtract_negative() {
        let result = BigInteger::new("123") - &BigInteger::new("-456");

        assert_eq!(result, BigInteger::new("579"));
    }

    #[test]
    fn subtract_below_zero() {
        let result = BigInteger::new("2") - &BigInteger::new("4");

        assert_eq!(result, BigInteger::new("-2"));
    }

    #[test]
    fn subtract_from_negative() {
        let result = BigInteger::new("-123") - &BigInteger::new("456");

        assert_eq!(result, BigInteger::new("-579"));
    }

    #[test]
    fn subtract_large() {
        let result = BigInteger::new("2") - &BigInteger::new("999999999999");

        assert_eq!(result, BigInteger::new("-999999999997"));
    }

    ///////////////////////////////////////////////////////////////////////////

    #[test]
    fn multiply_single_digits() {
        let result = BigInteger::new("2") * &BigInteger::new("2");

        assert_eq!(result, BigInteger::new("4"));
    }

    #[test]
    fn multiply_uneven() {
        let result = BigInteger::new("2") * &BigInteger::new("16384");

        assert_eq!(result, BigInteger::new("32768"));
    }

    #[test]
    fn multiply_large() {
        let result = BigInteger::new("901238123") * &BigInteger::new("238271282");

        assert_eq!(result, BigInteger::new("214739162954483686"));
    }
}