src/part06.rs

   1 // Rust-101, Part 06: Abstract Datastructure, Testing
   2 // ==================================================
   3
   4 use std::cmp;
   5 use std::ops;
   6
   7 pub struct BigInt {
   8     data: Vec<u64>, // least significant digits first. The last block will *not* be 0.
   9 }
  10
  11 impl BigInt {
  12     pub fn new(x: u64) -> Self {
  13         if x == 0 {
  14             BigInt { data: vec![] }
  15         } else {
  16             BigInt { data: vec![x] }
  17         }
  18     }
  19 }
  20
  21 /// Add with carry, returning the sum and the carry
  22 fn overflowing_add(a: u64, b: u64, carry: bool) -> (u64, bool) {
  23     match u64::checked_add(a, b) {
  24         Some(sum) if !carry => (sum, false),
  25         Some(sum) => { // we have to increment the sum by 1, where it may overflow again
  26             match u64::checked_add(sum, 1) {
  27                 Some(total_sum) => (total_sum, false),
  28                 None => (0, true) // we overflowed incrementing by 1, so we are just "at the edge"
  29             }
  30         },
  31         None => {
  32             // Get the remainder, i.e., the wrapping sum. This cannot overflow again by adding just 1, so it is safe
  33             // to add the carry here.
  34             let rem = u64::wrapping_add(a, b) + if carry { 1 } else { 0 };
  35             (rem, true)
  36         }
  37     }
  38 }
  39
  40 #[test]
  41 fn test_overflowing_add() {
  42     assert_eq!(overflowing_add(10, 100, false), (110, false));
  43     assert_eq!(overflowing_add(10, 100, true), (111, false));
  44     assert_eq!(overflowing_add(1 << 63, 1 << 63, false), (0, true));
  45     assert_eq!(overflowing_add(1 << 63, 1 << 63, true), (1, true));
  46     assert_eq!(overflowing_add(1 << 63, (1 << 63) -1 , true), (0, true));
  47 }
  48
  49 impl ops::Add<BigInt> for BigInt {
  50     type Output = BigInt;
  51     fn add(self, rhs: BigInt) -> Self::Output {
  52         let mut result_vec:Vec<u64> = Vec::with_capacity(cmp::max(self.data.len(), rhs.data.len()));
  53         let mut carry:bool = false; // the carry bit
  54         for (i, val) in self.data.into_iter().enumerate() {
  55             // compute next digit and carry
  56             let rhs_val = if i < rhs.data.len() { rhs.data[i] } else { 0 };
  57             let (sum, new_carry) = overflowing_add(val, rhs_val, carry);
  58             // store them
  59             result_vec.push(sum);
  60             carry = new_carry;
  61         }
  62         BigInt { data: result_vec }
  63     }
  64 }
  65
  66
  67