92da555374ed969f64f10531978685de1a3930ab
[rust-101.git] / 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 }