*oops*

[rust-101.git] / solutions / src / bigint.rs

diff --git a/solutions/src/bigint.rs b/solutions/src/bigint.rs
index 80ac63d75327a9584bc0abfeaf724e05f981e637..120ae6c8d008e9d6b9d682728f6b7bc1f09a3657 100644 (file)
--- a/solutions/src/bigint.rs
+++ b/solutions/src/bigint.rs
@@ -55,16 +55,16 @@ impl BigInt {
         }
     }
 
         }
     }
 

-    /// Construct a BigInt from a vector of 64-bit "digits", with the last significant digit being first
+    /// Construct a BigInt from a vector of 64-bit "digits", with the last significant digit being first. Solution to 05.1.

     pub fn from_vec(mut v: Vec<u64>) -> Self {
     pub fn from_vec(mut v: Vec<u64>) -> Self {

-        // remove trailing zeroes
+        // remove trailing zeros

         while v.len() > 0 && v[v.len()-1] == 0 {
             v.pop();
         }
         BigInt { data: v }
     }
 
         while v.len() > 0 && v[v.len()-1] == 0 {
             v.pop();
         }
         BigInt { data: v }
     }
 

-    /// Increments the number by 1. Solution to 05.1.
+    /// Increments the number by 1.

     pub fn inc1(&mut self) {
         let mut idx = 0;
         // This loop adds "(1 << idx)". If there is no more carry, we leave.
     pub fn inc1(&mut self) {
         let mut idx = 0;
         // This loop adds "(1 << idx)". If there is no more carry, we leave.


@@ -131,6 +131,7 @@ impl PartialEq for BigInt {
 }
 
 impl Minimum for BigInt {
 }
 
 impl Minimum for BigInt {

+    // This is essentially the solution to 06.1.

     fn min<'a>(&'a self, other: &'a Self) -> &'a Self {
         debug_assert!(self.test_invariant() && other.test_invariant());
         if self.data.len() < other.data.len() {
     fn min<'a>(&'a self, other: &'a Self) -> &'a Self {
         debug_assert!(self.test_invariant() && other.test_invariant());
         if self.data.len() < other.data.len() {


@@ -165,12 +166,14 @@ impl fmt::Debug for BigInt {
 impl<'a, 'b> ops::Add<&'a BigInt> for &'b BigInt {
     type Output = BigInt;
     fn add(self, rhs: &'a BigInt) -> Self::Output {
 impl<'a, 'b> ops::Add<&'a BigInt> for &'b BigInt {
     type Output = BigInt;
     fn add(self, rhs: &'a BigInt) -> Self::Output {

-        let mut result_vec:Vec<u64> = Vec::with_capacity(cmp::max(self.data.len(), rhs.data.len()));
+        let max_len = cmp::max(self.data.len(), rhs.data.len());
+        let mut result_vec:Vec<u64> = Vec::with_capacity(max_len);

         let mut carry:bool = false; // the carry bit
         let mut carry:bool = false; // the carry bit

-        for (i, val) in (&self.data).into_iter().enumerate() {
+        for i in 0..max_len {

             // compute next digit and carry
             // compute next digit and carry

+            let lhs_val = if i < self.data.len() { self.data[i] } else { 0 };

             let rhs_val = if i < rhs.data.len() { rhs.data[i] } else { 0 };
             let rhs_val = if i < rhs.data.len() { rhs.data[i] } else { 0 };

-            let (sum, new_carry) = overflowing_add(*val, rhs_val, carry);
+            let (sum, new_carry) = overflowing_add(lhs_val, rhs_val, carry);

             // store them
             result_vec.push(sum);
             carry = new_carry;
             // store them
             result_vec.push(sum);
             carry = new_carry;


@@ -179,8 +182,8 @@ impl<'a, 'b> ops::Add<&'a BigInt> for &'b BigInt {
             result_vec.push(1);
         }
         // We know that the invariant holds: overflowing_add would only return (0, false) if
             result_vec.push(1);
         }
         // We know that the invariant holds: overflowing_add would only return (0, false) if

-        // the arguments are (0, 0, false), but we know that in the last iteration, `val` is the
-        // last digit of `self` and hence not 0.
+        // the arguments are (0, 0, false), but we know that in the last iteration, one od the two digits
+        // is the last of its number and hence not 0.

         BigInt { data: result_vec }
     }
 }
         BigInt { data: result_vec }
     }
 }


@@ -224,6 +227,14 @@ mod tests {
         assert_eq!(overflowing_add(1 << 63, (1 << 63) -1 , true), (0, true));
     }
 
         assert_eq!(overflowing_add(1 << 63, (1 << 63) -1 , true), (0, true));
     }
 

+    #[test]
+    fn test_add() {
+        let b1 = BigInt::new(1 << 32);
+        let b2 = BigInt::from_vec(vec![0, 1]);
+
+        assert_eq!(&b1 + &b2, BigInt::from_vec(vec![1 << 32, 1]));
+    }
+

     #[test]
     fn test_inc1() {
         let mut b = BigInt::new(0);
     #[test]
     fn test_inc1() {
         let mut b = BigInt::new(0);