src/part07.rs

   1 use part05::BigInt;
   2
   3 pub trait Minimum {
   4     /// Return the smaller of the two
   5     fn min<'a>(&'a self, other: &'a Self) -> &'a Self;
   6 }
   7
   8 /// Return a pointer to the minimal value of `v`.
   9 pub fn vec_min<T: Minimum>(v: &Vec<T>) -> Option<&T> {
  10     let mut min = None;
  11     for e in v {
  12         min = Some(match min {
  13             None => e,
  14             Some(n) => e.min(n)
  15         });
  16     }
  17     min
  18 }
  19 // Notice that `Option<&T>` is technically (leaving the borrowing story aside) a pointer to a `T`,
  20 // that could optionally be invalid. In other words, it's just like a pointer in C(++) or Java
  21 // that can be `NULL`! However, thanks to `Option` being an `enum`, we cannot forget to check
  22 // the pointer for validity, avoiding the safety issues of C(++). At the same time, when we
  23 // have a borrow like `v` above that's not an `Option`, we *know* that is has to be a valid
  24 // pointer, so we don't even need to do a `NULL`-check.<br/>
  25 // Also, if you are worried about wasting space, notice that Rust knows that `&T` can never be
  26 // `NULL`, and hence optimizes `Option<&T>` to be no larger than `&T`. The `None` case is represented
  27 // as `NULL`. This is another great example of a zero-cost abstraction: `Option<&T>` is exactly like
  28 // a pointer in C(++), if you look at what happens during execution - but it's much safer to use.
  29
  30 impl Minimum for BigInt {
  31     fn min<'a>(&'a self, other: &'a Self) -> &'a Self {
  32         debug_assert!(self.test_invariant() && other.test_invariant());
  33         if self.data.len() < other.data.len() {
  34             self
  35         } else if self.data.len() > other.data.len() {
  36             other
  37         } else {
  38             // compare back-to-front, i.e., most significant digit first
  39             let mut idx = self.data.len()-1;
  40             while idx > 0 {
  41                 if self.data[idx] < other.data[idx] {
  42                     return self;
  43                 } else if self.data[idx] > other.data[idx] {
  44                     return other;
  45                 }
  46                 else {
  47                     idx = idx-1;
  48                 }
  49             }
  50             // the two are equal
  51             return self;
  52         }
  53     }
  54 }