lots of work on parts 05 and 06

[rust-101.git] / src / part07.rs

diff --git a/src/part07.rs b/src/part07.rs
index e9715e09ff7cbcca6a9f24a398acb0325086221b..92da555374ed969f64f10531978685de1a3930ab 100644 (file)
--- a/src/part07.rs
+++ b/src/part07.rs
@@ -1,30 +1,54 @@
-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.");
-    }
+pub trait Minimum {
+    /// Return the smaller of the two
+    fn min<'a>(&'a self, other: &'a Self) -> &'a Self;
 }
 
-/*#[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));
+/// 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
 }
+// Notice that `Option<&T>` is technically (leaving the borrowing story aside) a pointer to a `T`,
+// that could optionally be invalid. In other words, it's just like a pointer in C(++) or Java
+// that can be `NULL`! However, thanks to `Option` being an `enum`, we cannot forget to check
+// the pointer for validity, avoiding the safety issues of C(++). At the same time, when we
+// have a borrow like `v` above that's not an `Option`, we *know* that is has to be a valid
+// pointer, so we don't even need to do a `NULL`-check.<br/>
+// Also, if you are worried about wasting space, notice that Rust knows that `&T` can never be
+// `NULL`, and hence optimizes `Option<&T>` to be no larger than `&T`. The `None` case is represented
+// as `NULL`. This is another great example of a zero-cost abstraction: `Option<&T>` is exactly like
+// a pointer in C(++), if you look at what happens during execution - but it's much safer to use.
 
-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.");
+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;
+        }
     }
 }