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;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Sign {
Positive,
Negative,
NoSign,
}
impl Sign {
pub fn is_positive(self) -> bool {
match self {
Sign::Positive => true,
_ => false,
}
}
pub fn is_negative(self) -> bool {
match self {
Sign::Negative => true,
_ => false,
}
}
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(()),
}
}
}
#[derive(Clone, Debug, PartialEq)]
pub struct BigInteger {
digits: Vec<u8>,
sign: Sign,
}
impl BigInteger {
pub fn new(literal: &str) -> BigInteger {
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();
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));
Sign::Positive
}
None => panic!("BigInteger literal must begin with a sign or a digit"),
};
digits.extend(chars.map(char_to_digit));
BigInteger::from_digits(&digits[..], sign)
}
pub fn from_digits(digits: &[u8], sign: Sign) -> BigInteger {
let digits = Vec::from(digits);
let mut result = BigInteger { digits, sign };
result.trim();
result
}
pub fn is_positive(&self) -> bool {
self.sign.is_positive()
}
pub fn is_negative(&self) -> bool {
self.sign.is_negative()
}
pub fn count(&self) -> usize {
self.digits.len()
}
pub fn as_slice(&self) -> &[u8] {
self
}
pub fn digits(&self) -> impl Iterator<Item = u8> + DoubleEndedIterator + '_ {
self.digits.iter().cloned().rev()
}
fn trim(&mut self) {
self.digits = self
.digits
.iter()
.cloned()
.skip_while(|&digit| digit == 0)
.collect();
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> {
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) => {
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"));
}
}