From: Ralf Jung <post@ralfj.de>
Date: Mon, 15 Jun 2015 20:46:30 +0000 (+0200)
Subject: start doing the course-part of BigInt
X-Git-Url: https://git.ralfj.de/rust-101.git/commitdiff_plain/17ab30e2988868e5f59b36bb0364cadb0a1c42f8

start doing the course-part of BigInt
---

diff --git a/solutions/src/bigint.rs b/solutions/src/bigint.rs
index e9dfdf0..0abb6b3 100644
--- a/solutions/src/bigint.rs
+++ b/solutions/src/bigint.rs
@@ -2,30 +2,41 @@ use std::ops;
 use std::cmp;
 use std::fmt;
 
+pub trait Minimum {
+    /// Return the smaller of the two
+    fn min<'a>(&'a self, other: &'a Self) -> &'a Self;
+}
+
+/// Return a pointer to the minimal value of `v`.
+pub fn vec_min<T: Minimum>(v: &Vec<T>) -> Option<&T> {
+    let mut min = None;
+    for e in v {
+        min = Some(match min {
+            None => e,
+            Some(n) => e.min(n)
+        });
+    }
+    min
+}
+
 pub struct BigInt {
     data: Vec<u64>, // least significant digits first. The last block will *not* be 0.
 }
 
 // Add with carry, returning the sum and the carry
 fn overflowing_add(a: u64, b: u64, carry: bool) -> (u64, bool) {
-    match u64::checked_add(a, b) {
-        Some(sum) if !carry => (sum, false),
-        Some(sum) => { // we have to increment the sum by 1, where it may overflow again
-            match u64::checked_add(sum, 1) {
-                Some(total_sum) => (total_sum, false),
-                None => (0, true) // we overflowed incrementing by 1, so we are just "at the edge"
-            }
-        },
-        None => {
-            // Get the remainder, i.e., the wrapping sum. This cannot overflow again by adding just 1, so it is safe
-            // to add the carry here.
-            let rem = u64::wrapping_add(a, b) + if carry { 1 } else { 0 };
-            (rem, true)
-        }
+    let sum = u64::wrapping_add(a, b);
+    let carry_n = if carry { 1 } else { 0 };
+    if sum >= a { // the first sum did not overflow
+        let sum_total = u64::wrapping_add(sum, carry_n);
+        let had_overflow = sum_total < sum;
+        (sum_total, had_overflow)
+    } else { // the first sum did overflow
+        // it is impossible for this to overflow again, as we are just adding 0 or 1
+        (sum + carry_n, true)
     }
 }
 
-
 impl BigInt {
     /// Construct a BigInt from a "small" one.
     pub fn new(x: u64) -> Self {
@@ -53,43 +64,6 @@ impl BigInt {
         BigInt { data: v }
     }
 
-    /// Return the smaller of the two numbers
-    pub fn min(self, other: Self) -> Self {
-        debug_assert!(self.test_invariant() && other.test_invariant());
-        if self.data.len() < other.data.len() {
-            self
-        } else if self.data.len() > other.data.len() {
-            other
-        } else {
-            // compare back-to-front, i.e., most significant digit first
-            let mut idx = self.data.len()-1;
-            while idx > 0 {
-                if self.data[idx] < other.data[idx] {
-                    return self;
-                } else if self.data[idx] > other.data[idx] {
-                    return other;
-                }
-                else {
-                    idx = idx-1;
-                }
-            }
-            // the two are equal
-            return self;
-        }
-    }
-
-    /// Returns a view on the raw digits representing the number.
-    /// 
-    /// ```
-    /// use solutions::bigint::BigInt;
-    /// let b = BigInt::new(13);
-    /// let d = b.data();
-    /// assert_eq!(d, [13]);
-    /// ```
-    pub fn data(&self) -> &[u64] {
-        &self.data[..]
-    }
-
     /// Increments the number by "by".
     pub fn inc(&mut self, mut by: u64) {
         let mut idx = 0;
@@ -129,34 +103,65 @@ impl Clone for BigInt {
     }
 }
 
-
 impl PartialEq for BigInt {
     fn eq(&self, other: &BigInt) -> bool {
         debug_assert!(self.test_invariant() && other.test_invariant());
-        self.data() == other.data()
+        self.data == other.data
+    }
+}
+
+impl Minimum for BigInt {
+    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() {
+            self
+        } else if self.data.len() > other.data.len() {
+            other
+        } else {
+            // compare back-to-front, i.e., most significant digit first
+            let mut idx = self.data.len()-1;
+            while idx > 0 {
+                if self.data[idx] < other.data[idx] {
+                    return self;
+                } else if self.data[idx] > other.data[idx] {
+                    return other;
+                }
+                else {
+                    idx = idx-1;
+                }
+            }
+            // the two are equal
+            return self;
+        }
     }
 }
 
 impl fmt::Debug for BigInt {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        self.data().fmt(f)
+        self.data.fmt(f)
     }
 }
 
 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 mut result_vec:Vec<u64> = Vec::with_capacity(cmp::max(self.data.len(), rhs.data.len()));
         let mut carry:bool = false; // the carry bit
-        for (i, val) in self.data().into_iter().enumerate() {
+        for (i, val) in (&self.data).into_iter().enumerate() {
             // compute next digit and carry
-            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);
             // store them
             result_vec.push(sum);
             carry = new_carry;
         }
-        BigInt::from_vec(result_vec)
+        if carry {
+            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.
+        BigInt { data: result_vec }
     }
 }
 
diff --git a/src/main.rs b/src/main.rs
index 06ad4b2..15b798c 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -70,7 +70,7 @@
 // * [Part 03](part03.html)
 // * [Part 04](part04.html) (WIP)
 // * (to be continued)
-#![allow(dead_code, unused_imports, unused_variables)]
+#![allow(dead_code, unused_imports, unused_variables, unused_mut)]
 mod part00;
 mod part01;
 mod part02;
@@ -78,6 +78,7 @@ mod part03;
 mod part04;
 mod part05;
 mod part06;
+mod part07;
 
 // To actually run the code of some part (after filling in the blanks, if necessary), simply edit the `main`
 // function.
diff --git a/src/part05.rs b/src/part05.rs
index 274e3b5..25c98e2 100644
--- a/src/part05.rs
+++ b/src/part05.rs
@@ -1,2 +1,137 @@
 // Rust-101, Part 05: Copy, Clone
 // ==============================
+
+use std::cmp;
+use std::ops;
+
+// In the course of the next few parts, we are going to build a data-structure for
+// computations with *bug* numbers. We would like to not have an upper bound
+// to how large these numbers can get, with the memory of the machine being the
+// only limit.
+// 
+// We start by deciding how to represent such big numbers. One possibility here is
+// to use a vector of "small" numbers, which we will then consider the "digits"
+// of the big number. This is like "1337" being a vector of 4 small numbers (1, 3, 3, 7),
+// except that we will use `u64` as type of our base numbers. Now we just have to decide
+// the order in which we store numbers. I decided that we will store the least significant
+// digit first. This means that "1337" would actually become (7, 3, 3, 1).<br/>
+// Finally, we declare that there must not be any trailing zeros (corresponding to
+// useless leading zeros in our usual way of writing numbers). This is to ensure that
+// the same number can only be stored in one way.
+
+// To write this down in Rust, we use a `struct`, which is a lot like structs in C:
+// Just a collection of a bunch of named fields. Every field can be private to the current module
+// (which is the default), or public (which would be indicated by a `pub` in front of the name).
+// For the sake of the tutorial, we make `dat` public - otherwise, the next parts of this
+// course could not work on `BigInt`s. Of course, in a real program, one would make the field
+// private to ensure that the invariant (no trailing zeros) is maintained.
+pub struct BigInt {
+    pub data: Vec<u64>,
+}
+
+// Now that we fixed the data representation, we can start implementing methods on it.
+impl BigInt {
+    // Let's start with a constructor, creating a `BigInt` from an ordinary integer.
+    // To create an instance of a struct, we write its name followed by a list of
+    // fields and initial values assigned to them.
+    pub fn new(x: u64) -> Self {
+        if x == 0 {
+            BigInt { data: vec![] }
+        } else {
+            BigInt { data: vec![x] }
+        }
+    }
+
+    // It can often be useful to encode the invariant of a data-structure in code, so here
+    // is a check that detects useless trailing zeros.
+    pub fn test_invariant(&self) -> bool {
+        if self.data.len() == 0 {
+            true
+        } else {
+            self.data[self.data.len() - 1] != 0
+        }
+    }
+
+    // We can convert any vector of digits into a number, by removing trailing zeros. The `mut`
+    // declaration for `v` here is just like the one in `let mut ...`, it says that we will locally
+    // change the vector `v`. In this case, we need to make that annotation to be able to call `pop`
+    // on `v`.
+    pub fn from_vec(mut v: Vec<u64>) -> Self {
+        while v.len() > 0 && v[v.len()-1] == 0 {
+            v.pop();
+        }
+        BigInt { data: v }
+    }
+}
+
+// If you have a close look at the type of `BigInt::from_vec`, you will notice that it
+// consumes the vector `v`. The caller hence loses access. There is however something
+// we can do if we don't want that to happen: We can explicitly `clone` the vector,
+// which means that a full (or *deep*) copy will be performed. Technically,
+// `clone` takes a borrowed vector, and returns a fully owned one.
+fn clone_demo() {
+    let v = vec![0,1 << 16];
+    let b1 = BigInt::from_vec(v.clone());
+    let b2 = BigInt::from_vec(v);
+}
+
+// To be clonable is a property of a type, and as such, naturally expressed with a trait.
+// In fact, Rust already comes with a trait `Clone` for exactly this purpose. We can hence
+// make our `BigInt` clonable as well.
+impl Clone for BigInt {
+    fn clone(&self) -> Self {
+        BigInt { data: self.data.clone() }
+    }
+}
+// Making a type clonable is such a common exercise that Rust can even help you doing it:
+// If you add `#[derive(Clone)]' right in front of the definition of `BigInt`, Rust will
+// generate an implementation of `clone` that simply clones all the fields. Try it!
+// 
+// To put this in perspective, `clone` in Rust corresponds to what people usually manually do in
+// the copy constructor of a C++ class: It creates new, independent instance containing the
+// same values. Contrary to that, if you pass something to a function normally (like the
+// second call to `from_vec` in `clone_demo`), only a *shallow* copy is created: The fields
+// are copied, but pointers are simply duplicated. This corresponds to the default copy
+// constructor in C++. Rust assumes that after such a copy, the old value is useless
+// (as the new one uses the same pointers), and hence considers the data semantically
+// moved to the copy. That's another explanation of why Rust does not let you access
+// a vector anymore after you passed ownership to some function.
+
+// With `BigInt` being about numbers, we should be able to write a version of `vec_min`
+// that computes the minimum of a list of `BigInt`. We start by writing `min` for
+// `BigInt`. Now our assumption of having no trailing zeros comes in handy!
+impl BigInt {
+    fn min(self, other: Self) -> Self {
+        // Just to be sure, we first check that both operands actually satisfy our invariant.
+        // `debug_assert!` is a macro that checks that its argument (must be of type `bool`)
+        // is `true`, and panics otherwise. It gets removed in release builds, which you do with
+        // `cargo build --release`.
+        // 
+        // If you carefully check the type of `BigInt::test_invariant`, you may be surprised that
+        // we can call the function this way. Doesn't it take `self` in borrowed form? Indeed,
+        // the explicit way to do that would be to call `(&other).test_invariant()`. However, the
+        // `self` argument of a method is treated specially by Rust, and borrowing happens automatically here.
+        debug_assert!(self.test_invariant() && other.test_invariant());
+        // If the lengths of the two numbers differ, we already know which is larger.
+        if self.data.len() < other.data.len() {
+            self
+        } else if self.data.len() > other.data.len() {
+            other
+        } else {
+            // **Exercise**: Fill in this code.
+            panic!("Not yet implemented.");
+        }
+    }
+}
+
+fn vec_min(v: &Vec<BigInt>) -> Option<BigInt> {
+    let mut min: Option<BigInt> = None;
+    for e in v {
+        // In the loop, `e` now has type `&i32`, so we have to dereference it.
+        min = Some(match min {
+            None => e.clone(),
+            Some(n) => e.clone().min(n)
+        });
+    }
+    min
+}
diff --git a/src/part06.rs b/src/part06.rs
index 3b867aa..21046c6 100644
--- a/src/part06.rs
+++ b/src/part06.rs
@@ -1,67 +1,56 @@
-// Rust-101, Part 06: Abstract Datastructure, Testing
-// ==================================================
+// Rust-101, Part 06: Lifetimes, Testing
+// =====================================
 
 use std::cmp;
 use std::ops;
+use std::fmt;
+use part05::BigInt;
 
-pub struct BigInt {
-    data: Vec<u64>, // least significant digits first. The last block will *not* be 0.
-}
 
-impl BigInt {
-    pub fn new(x: u64) -> Self {
-        if x == 0 {
-            BigInt { data: vec![] }
-        } else {
-            BigInt { data: vec![x] }
-        }
+impl PartialEq for BigInt {
+    fn eq(&self, other: &BigInt) -> bool {
+        debug_assert!(self.test_invariant() && other.test_invariant());
+        self.data == other.data
     }
 }
 
-/// Add with carry, returning the sum and the carry
-fn overflowing_add(a: u64, b: u64, carry: bool) -> (u64, bool) {
-    match u64::checked_add(a, b) {
-        Some(sum) if !carry => (sum, false),
-        Some(sum) => { // we have to increment the sum by 1, where it may overflow again
-            match u64::checked_add(sum, 1) {
-                Some(total_sum) => (total_sum, false),
-                None => (0, true) // we overflowed incrementing by 1, so we are just "at the edge"
-            }
-        },
-        None => {
-            // Get the remainder, i.e., the wrapping sum. This cannot overflow again by adding just 1, so it is safe
-            // to add the carry here.
-            let rem = u64::wrapping_add(a, b) + if carry { 1 } else { 0 };
-            (rem, true)
-        }
-    }
+fn call_eq() {
+    let b1 = BigInt::new(13);
+    let b2 = BigInt::new(37);
+    println!("b1 == b1: {} ; b1 == b2: {}; b1 != b2: {}", b1 == b1, b1 == b2, b1 != b2);
 }
 
-#[test]
-fn test_overflowing_add() {
-    assert_eq!(overflowing_add(10, 100, false), (110, false));
-    assert_eq!(overflowing_add(10, 100, true), (111, false));
-    assert_eq!(overflowing_add(1 << 63, 1 << 63, false), (0, true));
-    assert_eq!(overflowing_add(1 << 63, 1 << 63, true), (1, true));
-    assert_eq!(overflowing_add(1 << 63, (1 << 63) -1 , true), (0, true));
+
+impl fmt::Debug for BigInt {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        self.data.fmt(f)
+    }
 }
 
-impl ops::Add<BigInt> for BigInt {
-    type Output = BigInt;
-    fn add(self, rhs: BigInt) -> Self::Output {
-        let mut result_vec:Vec<u64> = Vec::with_capacity(cmp::max(self.data.len(), rhs.data.len()));
-        let mut carry:bool = false; // the carry bit
-        for (i, val) in self.data.into_iter().enumerate() {
-            // compute next digit and carry
-            let rhs_val = if i < rhs.data.len() { rhs.data[i] } else { 0 };
-            let (sum, new_carry) = overflowing_add(val, rhs_val, carry);
-            // store them
-            result_vec.push(sum);
-            carry = new_carry;
-        }
-        BigInt { data: result_vec }
+
+
+impl BigInt {
+    pub fn inc(&mut self, mut by: u64) {
+        panic!("Not yet implemented.");
     }
 }
 
 
+#[test]
+fn test_inc() {
+    let mut b = BigInt::new(1337);
+    b.inc(1337);
+    assert!(b == BigInt::new(1337 + 1337));
+
+    b = BigInt::new(0);
+    assert_eq!(b, BigInt::from_vec(vec![0]));
+    b.inc(1 << 63);
+    assert_eq!(b, BigInt::from_vec(vec![1 << 63]));
+    b.inc(1 << 63);
+    assert_eq!(b, BigInt::from_vec(vec![0, 1]));
+    b.inc(1 << 63);
+    assert_eq!(b, BigInt::from_vec(vec![1 << 63, 1]));
+    b.inc(1 << 63);
+    assert_eq!(b, BigInt::from_vec(vec![0, 2]));
+}
 
diff --git a/src/part07.rs b/src/part07.rs
new file mode 100644
index 0000000..e9715e0
--- /dev/null
+++ b/src/part07.rs
@@ -0,0 +1,30 @@
+use std::cmp;
+use std::ops;
+use part05::BigInt;
+
+// Add with carry, returning the sum and the carry
+fn overflowing_add(a: u64, b: u64, carry: bool) -> (u64, bool) {
+    let sum = u64::wrapping_add(a, b);
+    if sum >= a {
+        panic!("First addition did not overflow. Not implemented.");
+    } else {
+        panic!("First addition *did* overflow. Not implemented.");
+    }
+}
+
+/*#[test]*/
+fn test_overflowing_add() {
+    assert_eq!(overflowing_add(10, 100, false), (110, false));
+    assert_eq!(overflowing_add(10, 100, true), (111, false));
+    assert_eq!(overflowing_add(1 << 63, 1 << 63, false), (0, true));
+    assert_eq!(overflowing_add(1 << 63, 1 << 63, true), (1, true));
+    assert_eq!(overflowing_add(1 << 63, (1 << 63) -1 , true), (0, true));
+}
+
+impl ops::Add for BigInt {
+    type Output = BigInt;
+    fn add(self, rhs: BigInt) -> Self::Output {
+        let mut result_vec:Vec<u64> = Vec::with_capacity(cmp::max(self.data.len(), rhs.data.len()));
+        panic!("Not yet implemented.");
+    }
+}