use criterion::{criterion_group, criterion_main, BenchmarkId, Criterion};
use iterstats::Iterstats;
use rand::seq::IteratorRandom;
use std::hint::black_box;

fn naive<'a>(iter: impl Iterator<Item = &'a f64> + Clone) -> f64 {
    let mut v = iter.collect::<Vec<_>>();
    v.sort_unstable_by(|a, b| a.partial_cmp(b).unwrap());
    let len = v.len();
    if len % 2 == 0 {
        (v[(len / 2) - 1] + v[len / 2]) / 2.
    } else {
        *v[len / 2]
    }
}

fn bench_median(c: &mut Criterion) {
    let mut group = c.benchmark_group("median");
    let mut rng = &mut rand::thread_rng();
    for len in [10, 101, 1000, 10001, 100_000, 1_000_000] {
        let data = (0..2 * len)
            .map(|i| i as f64)
            .choose_multiple(&mut rng, len);
        assert_eq!(data.len(), len);
        group.bench_with_input(BenchmarkId::new("naive", len), &data, |b, i| {
            b.iter(|| black_box(naive(black_box(i.iter()))))
        });
        group.bench_with_input(BenchmarkId::new("iterstats", len), &data, |b, i| {
            b.iter(|| black_box(black_box(i.iter()).median()))
        });
    }
    group.finish();
}

criterion_group!(benches, bench_median);
criterion_main!(benches);