Implement minmax

[sanxiyn]

C++11 introduced minmax_element.

Preliminary implementation here: https://mail.mozilla.org/pipermail/rust-dev/2013-March/003328.html

[graydon]

nominating to remove from milestone 2. it's nice code, happy to take it, but purely backward-compatible addition.

[graydon]

just a bug, removing milestone/nomination.

[sanxiyn]

Triage. My linked implementation is obsolete because it predates the current Rust iterator. It would be still nice to have minmax, and it should be much easier to implement now.

[pongad]

I'll look into it if no one wants to.

[pongad]

https://gist.github.com/pongad/8270459
The algorithm looks correct though the compiler is giving me a cryptic error message. The error message is pasted into the comment. I'll appreciate any help deciphering it xD. I (and the IRC) am not quite sure where the problem is.

[pongad]

My implementation is now working
https://gist.github.com/pongad/8270459
Does @sanxiyn approve? xD

[huonw]

@pongad not failing on an empty iterator would be good (i.e. returning Option<(T, T)> (if we keep the Clone bound)). Also, having a Clone bound is not so nice: if were were to avoid the Clone bound, it might have to return something like

enum MinMax<T> {
    // Empty iterator
    NoElements,
    // Iterator with one element, so the minimum and maximum are the same (and
    // without Clone we can't make two copies of it)
    OneElement(T)
    // More than one element in the iterator, so we can store them separated
    MinMax(T, T)
}

[pongad]

@huonw Made a version to address your concern
By the way, speed comparison on my machine is
min and max: 60,584,713
minmax: 34,244,845

Also, is there a better way to do what I did without the is_none/unwrap "pattern"?

[huonw]

(BTW, Rust has built-in micro-benchmarking: https://github.com/mozilla/rust/wiki/Doc-unit-testing#benchmarking )

And yes, definitely,

let x = match me.next() {
    None => { ...; break } // (or return)
    Some(x) => x
}

However, I think a more global rewrite may be better:

fn minmax<T: Ord, A: Iterator<T>>(me: &mut A) -> MinMax<T> {
    let (mut min, mut max) = match me.next() {
        None => return NoElements,
        Some(x) => {
            match me.next() {
                None => return OneElement(x),
                Some(y) => if x <= y {(x, y)} else {(y, x)}
            }
        }
    }

    for new in me.iter() {
        if new < min { min = new; }
        else if new > max { max = new; }
    }

    MinMax(min, max)
}

[pongad]

Of course! Though I think the point of @sanxiyn original implementation is to guarantee 1.5n comparisons. Your implementation will take 2n if the elements are increasing. It will take 1n if the elements are decreasing though. I don't know what to think anymore!!!

[huonw]

Oh I see!

A similar thing should be possible by changing my for loop there, unrolling it to something like (I like how the new iterators make the code look nicer, no need for a hand-coded state machine):

let left_over;
loop {
     let first = match me.next() {
          None => { left_over = None; break }
          Some(x) => x
     });
     let second = match me.next() {
          None => { left_over = Some(first); break }
          Some(x) => x
     };

     // do the comparisons to adjust min and max
}

match left_over {
    None = > MinMax(min, max)
    Some(x) => {
        // do the comparisons for the trailing element
    }
}

[pongad]

Updated again from @huonw 's comments. A question though, what about [5,5,5,5]? Should we make special case to return OneElement?

[pnkfelix]

@pongad IMO, I say return the MinMax(5,5) for the input [5,5,5,5], and just state very clearly in the doc that you are not guaranteed in MinMax(x,y) that x < y; you are only guaranteed that x <= y.

(The decision here is not entirely arbitrary; I'm assuming that it is easier/cheaper to inspect the MinMax result to see if the elements are == than it would be to figure out whether OneElement was returned because the iterator had only one element or because all the elements were ==. And besides, I interpret the reason behind the existence of OneElement is solely because its not possible to make a copy of a single value, but that problem does not affect you in the [5,5,5,5] case.)

[pongad]

https://gist.github.com/pongad/8270459
Updated again with comments from @pnkfelix . Should I create a new trait OrdVector for this? It doesn't require TotalOrdVector to work. Will open a PR when I hear back.

[huonw]

Isn't this meant to be on Iterators? I'd add it to std::iter::OrdIterator personally, or just have a free function like you have already.