Решение на Bigint от Ралица Димитрова

Обратно към всички решения

Към профила на Ралица Димитрова

Код

use std::ops::Neg;

use std::cmp::Ordering;

use std::cmp::max;

use std::ops::{Add, Sub};

use std::str::FromStr;

#[derive(Debug, PartialEq, Eq)]

pub struct Bigint {

sign: i8,

digits: Vec<u8>,

}

impl Bigint {

pub fn new() -> Self {

Self::from_components(Vec::new(), 1)

}

fn from_components(digits: Vec<u8>, sign: i8) -> Self {

let mut validated_digits: Vec<u8> = Vec::new();

let mut validated_sign = sign;

let mut first_non_zero_index: usize = digits.len();

for i in 0..digits.len() {

if digits[i] != 0 {

first_non_zero_index = i;

break;

}

}

if first_non_zero_index != digits.len() {

validated_digits = digits[first_non_zero_index..digits.len()].iter().cloned().collect();

}

if validated_digits.len() == 0 {

validated_sign = 1;

}

Bigint { sign: validated_sign, digits: validated_digits }

}

pub fn is_positive(&self) -> bool {

!self.digits.is_empty() && self.sign == 1

}

pub fn is_negative(&self) -> bool {

!self.digits.is_empty() && self.sign == -1

}

pub fn abs(&self) -> Self {

Bigint::from_components(self.digits.clone(), 1)

}

}

#[derive(Debug)]

pub struct ParseError;

impl FromStr for Bigint {

type Err = ParseError;

fn from_str(s: &str) -> Result<Self, Self::Err> {

let mut sign: i8 = 1;

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

let mut i: usize = 0;

if s.starts_with('+') {

i = 1;

} else if s.starts_with('-') {

sign = -1;

i = 1;

}

for c in s[i..].chars() {

if c >= '0' && c <= '9' {

digits.push(c as u8 - '0' as u8);

} else {

return Err(ParseError);

}

}

Ok(Bigint::from_components(digits, sign))

}

}

impl PartialOrd for Bigint {

fn partial_cmp(&self, other: &Bigint) -> Option<Ordering> {

Some(self.cmp(other))

}

}

fn cmp_helper(left: &Bigint, right: &Bigint) -> Ordering {

if left.digits.len() == right.digits.len() {

for i in 0..left.digits.len() {

if left.digits[i] > right.digits[i] {

return Ordering::Greater;

} else if left.digits[i] < right.digits[i] {

return Ordering::Less;

}

}

return Ordering::Equal;

}

return left.digits.len().cmp(&right.digits.len());

}

impl Ord for Bigint {

fn cmp(&self, other: &Bigint) -> Ordering {

let self_is_positive = self.is_positive();

let other_is_positive = other.is_positive();

let self_is_zero = self.digits.is_empty();

let other_is_zero = other.digits.is_empty();

match (self_is_positive, other_is_positive) {

(true, false) => return Ordering::Greater,

(false, true) => return Ordering::Less,

(true, true) => cmp_helper(self, other),

(false, false) => match (self_is_zero, other_is_zero) {

(true, true) => return Ordering::Equal,

(true, false) => return Ordering::Greater,

(false, true) => return Ordering::Less,

(false, false) => cmp_helper(other, self),

},

}

}

}

impl Add for Bigint {

type Output = Bigint;

fn add(self, other: Self) -> Self {

let mut sign: i8 = 1;

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

let self_abs = self.abs();

let other_abs = other.abs();

let self_is_positive = self.is_positive();

let other_is_positive = other.is_positive();

match (self_is_positive, other_is_positive) {

(true, true) => digits = add_digits(self.digits, other.digits),

(true, false) => match self_abs.cmp(&other_abs) {

Ordering::Less => digits = {

sign = -1;

subtract_digits(other.digits, self.digits)

},

Ordering::Equal => {},

Ordering::Greater => digits = subtract_digits(self.digits, other.digits),

},

(false, true) => match self_abs.cmp(&other_abs) {

Ordering::Less => digits = subtract_digits(other.digits, self.digits),

Ordering::Equal => {},

Ordering::Greater => {

sign = -1;

digits = subtract_digits(self.digits, other.digits)

},

},

(false, false) => {

sign = -1;

digits = add_digits(self.digits, other.digits);

},

}

Self::from_components(digits, sign)

}

}

impl Neg for Bigint {

type Output = Self;

fn neg(self) -> Self::Output {

if self.digits.is_empty() {

return self;

}

Bigint::from_components(self.digits, -self.sign)

}

}

impl Sub for Bigint {

type Output = Bigint;

fn sub(self, other: Self) -> Self {

self + (- other)

}

}

fn add_digits(mut left: Vec<u8>, mut right: Vec<u8>) -> Vec<u8> {

let mut result: Vec<u8> = Vec::new();

let size = max(left.len(), right.len());

left.reverse();

right.reverse();

while left.len() < size {

left.push(0)

}

while right.len() < size {

right.push(0)

}

let mut carry: u8 = 0;

for i in 0..size {

let mut digit = left[i] + right[i] + carry;

if digit >= 10 {

carry = 1;

digit = digit % 10;

} else {

carry = 0;

}

result.push(digit);

}

if carry == 1 {

result.push(1)

}

result.reverse();

return result;

}

fn subtract_digits(mut larger: Vec<u8>, mut smaller: Vec<u8>) -> Vec<u8> {

let mut result: Vec<u8> = Vec::new();

let size = max(larger.len(), smaller.len());

larger.reverse();

smaller.reverse();

while larger.len() < size {

larger.push(0)

}

while smaller.len() < size {

smaller.push(0)

}

let mut carry: u8 = 0;

for i in 0..size {

let mut digit = larger[i];

if smaller[i] + carry > larger[i] {

digit = digit + 10 - smaller[i] - carry;

carry = 1;

} else {

digit = digit - smaller[i] - carry;

carry = 0;

}

result.push(digit);

}

result.reverse();

return result;

}

#[cfg(test)]

mod tests {

use super::*;

fn newBigint(s: &str) -> Bigint {

Bigint::from_str(s).unwrap()

}

#[test]

fn test_create_zero() {

let zero = Bigint::new();

assert_eq!(zero.digits, Vec::new());

assert_eq!(zero.sign, 1);

let zero2 = newBigint("0");

assert_eq!(zero2.digits, Vec::new());

assert_eq!(zero2.sign, 1);

let zero3 = Bigint::from_str("+0").unwrap();

assert_eq!(zero3.digits, Vec::new());

assert_eq!(zero3.sign, 1);

let zero4 = newBigint("-0");

assert_eq!(zero4.digits, Vec::new());

assert_eq!(zero4.sign, 1);

let zero5 = Bigint::from_str("").unwrap();

assert_eq!(zero5.digits, Vec::new());

assert_eq!(zero5.sign, 1);

let zero6 = Bigint::from_str("+").unwrap();

assert_eq!(zero6.digits, Vec::new());

assert_eq!(zero6.sign, 1);

let zero7 = newBigint("-");

assert_eq!(zero7.digits, Vec::new());

assert_eq!(zero7.sign, 1);

}

#[test]

fn test_create_positive() {

let plus1 = newBigint("1");

assert_eq!(plus1.digits, vec![1]);

assert_eq!(plus1.sign, 1);

let plus123 = Bigint::from_str("+123").unwrap();

assert_eq!(plus123.digits, vec![1, 2, 3]);

assert_eq!(plus123.sign, 1);

let plus0000123 = newBigint("0000123");

assert_eq!(plus0000123.digits, vec![1, 2, 3]);

assert_eq!(plus0000123.sign, 1);

let plus00004 = Bigint::from_str("+00004").unwrap();

assert_eq!(plus00004.digits, vec![4]);

assert_eq!(plus00004.sign, 1);

}

#[test]

fn test_create_negative() {

let minus1 = newBigint("-1");

assert_eq!(minus1.digits, vec![1]);

assert_eq!(minus1.sign, -1);

let minus123 = newBigint("-123");

assert_eq!(minus123.digits, vec![1, 2, 3]);

assert_eq!(minus123.sign, -1);

let minus00123 = newBigint("-00123");

assert_eq!(minus00123.digits, vec![1, 2, 3]);

assert_eq!(minus00123.sign, -1);

}

#[test]

fn test_create_panic() {

assert!(Bigint::from_str("-*00123").is_err());

assert!(Bigint::from_str("--00123").is_err());

assert!(Bigint::from_str("++00123").is_err());

assert!(Bigint::from_str("00123+").is_err());

assert!(Bigint::from_str("001.23").is_err());

}

#[test]

fn test_add_neg_neg_eq_length() {

let a = newBigint("-123");

let b = newBigint("-976");

assert_eq!(a + b,newBigint("-1099"));

}

#[test]

fn test_add_neg_shorter_neg_longer() {

let a = newBigint("-12");

let b = newBigint("-976");

assert_eq!(a + b,newBigint("-988"));

}

#[test]

fn test_add_neg_longer_neg_shorter() {

let a = newBigint("-6798");

let b = newBigint("-11");

assert_eq!(a + b,newBigint("-6809"));

}

#[test]

fn test_add_zero() {

let a = newBigint("-123");

let b = newBigint("0");

assert_eq!(a - b,newBigint("-123"));

}

#[test]

fn test_subtract() {

let a = newBigint("-123");

let b = newBigint("0");

assert_eq!(a - b,newBigint("-123"));

}

#[test]

fn cmp_neg() {

assert_eq!(newBigint("-62").cmp(&newBigint("-25")), Ordering::Less);

assert_eq!(newBigint("-62").cmp(&newBigint("0")), Ordering::Less);

assert_eq!(newBigint("0").cmp(&newBigint("-25")), Ordering::Greater);

assert_eq!(newBigint("0").cmp(&newBigint("0")), Ordering::Equal);

assert_eq!(newBigint("121").cmp(&newBigint("0")), Ordering::Greater);

assert_eq!(newBigint("0").cmp(&newBigint("121")), Ordering::Less);

assert_eq!(newBigint("121").cmp(&Bigint::from_str("+121").unwrap()), Ordering::Equal);

assert_eq!(newBigint("-11").cmp(&newBigint("-11")), Ordering::Equal);

assert_eq!(newBigint("123").cmp(&newBigint("-11")), Ordering::Greater);

assert_eq!(newBigint("-11").cmp(&newBigint("123")), Ordering::Less);

assert_eq!(newBigint("345").cmp(&newBigint("34")), Ordering::Greater);

assert_eq!(newBigint("67").cmp(&newBigint("678")), Ordering::Less);

assert_eq!(newBigint("-11").cmp(&newBigint("-111")), Ordering::Greater);

assert_eq!(newBigint("-234").cmp(&newBigint("-99")), Ordering::Less);

}

}

Лог от изпълнението

Compiling solution v0.1.0 (/tmp/d20201127-2274206-1x4jn9y/solution)
    Finished test [unoptimized + debuginfo] target(s) in 1.72s
     Running target/debug/deps/solution_test-589a43f0f4b10ca3

running 15 tests
test solution_test::test_bigint_construction ... ok
test solution_test::test_bigint_nonzero_sign ... ok
test solution_test::test_bigint_zero_sign ... ok
test solution_test::test_comparison ... ok
test solution_test::test_invalid_string ... ok
test solution_test::test_neutralization ... ok
test solution_test::test_parsing_with_and_without_sign ... ok
test solution_test::test_parsing_with_leading_zeroes ... ok
test solution_test::test_sub_1_basic ... ok
test solution_test::test_sub_2_diferent_lengths ... ok
test solution_test::test_sub_3_carry ... ok
test solution_test::test_sum_1_basic ... ok
test solution_test::test_sum_2_different_lengths ... ok
test solution_test::test_sum_3_overflow ... ok
test solution_test::test_sum_4_negative ... ok

test result: ok. 15 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

История (1 версия и 1 коментар)