Shared via Rust Playground

playground.rs

use std::cmp;
use std::iter::IntoIterator;
use std::mem;

struct MedianAccum<T> {
    lower: T,
    lower_ct: usize,
    upper: T,
    upper_ct: usize,
    median: T,
}

impl MedianAccum<T: Ord> {
    fn start_from_iter<I: Iterator<Item=T>>(iter: &mut I) -> Result<Self, MedianErr<T>> {
        use MedianErr::*;
    
        let next0 = match iter.next() {
            Some(next) => next,
            None => return Err(NoItems),
        };
    
        let next1 = match iter.next() {
            Some(next) => next,
            None => return Err(OnlyOne(next0)),
        };
        
        let next2 = match iter.next() {
            Some(next) => next,
            None => return Err(OnlyTwo(next0, next1));
        };
        
        let (lower, median, upper) = match median_3(&next0, &next1, &next2) {
            0 => if next1 < next2 { 
                (next1, next0, next2)
            } else {
                (next2, next0, next1)
            },
            1 => if next0 < next2 {
                (next0, next1, next2)
            } else {
                (next2, next1, next0)
            },
            2 => if next0 < next1 {
                (next0, next2, next1)
            } else {
                (next1, next2, next0)
            }
        };
        
        Ok(MedianAccum {
            lower: lower,
            lower_ct: 0,
            upper: upper,
            upper_ct: 0,
            median: median
        })
    }

    fn add(&mut self, val: T) {
        use cmp::Ordering::*;
    
        match median_3(&self.lower, &val, &self.upper) {
            0 => self.lower_ct += 1,
            2 => self.upper_ct += 1,
            1 => match self.median.cmp(&val) {
                Less | Greater => if self.lower_ct < self.upper_ct {
                    self.lower_ct += 1;
                    mem::swap(&mut self.lower, &mut self.median);
                    self.median = val;
                } else {
                    self.upper_ct += 1;
                    mem::swap(&mut self.median, &mut self.upper);
                    self.median = val;
                },
                _ => 
            },
            _ => unreachable!(),
        }
    }
    
    fn into_median(self) -> T {
        self.median
    }
}

pub enum MedianErr<T> {
    NoItems,
    OnlyOne(T),
    OnlyTwo(T, T),
}

pub fn median<T: Ord, I: IntoIterator<Item=T>>(iter: I) -> Result<T, MedianErr<T>> {
    let mut iter = iter.into_iter();
    
    
    
    let mut accum = MedianAccum {
        lower: lower,
        lower_ct: 1,
        upper: upper,
        upper_ct: 1,
    };
    
    for item in iter {
        accum.add(item);
    }
    
    Ok(accum.into_median)
}


fn median_3<T>(val0: &T, val1: &T, val2: &T) -> usize {
    use cmp::Ordering::*;
    
    if val0 <= val1 {
        if val1 <= val2 { 1 } else { 2 }
    } else if 
}