Minimum and Maximum

minmax.rs

extern mod std;

fn lt<T: Ord>(a: Option<T>, b: Option<T>) -> bool {
    match (a, b) {
        (None, None) => false,
        (None, Some(_)) => true,
        (Some(_), None) => false,
        (Some(a), Some(b)) => a < b
    }
}

fn minmax<T: Copy + Ord>(self: &[T]) -> (T, T) {
    enum state { s0, s1, se, so }
    let mut state = s0;
    let mut min = None, max = None, last = None;
    for self.each |&cur| {
        let cur = Some(cur);
        match state {
            s0 => {
                min = cur;
                max = cur;
                state = s1;
            }
            s1 => {
                if lt(cur, min) {
                    min = cur;
                } else {
                    max = cur;
                }
                state = se;
            }
            se => {
                last = cur;
                state = so;
            }
            so => {
                if lt(cur, last) {
                    if lt(cur, min) { min = cur; }
                    if lt(max, last) { max = last; }
                } else {
                    if lt(last, min) { min = last; }
                    if lt(max, cur) { max = cur; }
                }
                state = se;
            }
        }
    }
    match state {
        s0 => {
            fail!(~"minmax called on empty iterator");
        }
        so => {
            if lt(last, min) {
                min = last;
            } else if lt(max, last) {
                max = last;
            }
        }
        _ => ()
    }
    (min.unwrap(), max.unwrap())
}

fn main() {
    let n = 1000000;

    let list = vec::from_fn(n, |i| i);
    let begin = std::time::precise_time_ns();
    let (min, max) = (list.min(), list.max());
    let end = std::time::precise_time_ns();
    let time = (end - begin) as uint;
    assert min == 0 && max == n - 1;
    io::println(fmt!("min and max: %u", time));

    let list = vec::from_fn(n, |i| i);
    let begin = std::time::precise_time_ns();
    let (min, max) = minmax(list);
    let end = std::time::precise_time_ns();
    let time = (end - begin) as uint;
    assert min == 0 && max == n - 1;
    io::println(fmt!("minmax: %u", time));
}