use std::fmt;
use std::time::{Instant, Duration};

const MIN_DUR: f64 = 1.0;
const MIN_TIMES: usize = 4;

pub struct Bench {
    pub executions: usize,
    pub duration: f64,
    pub duration_stddev: f64,
}

impl fmt::Display for Bench {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{} secs ± {} ({}%)",
               self.duration, self.duration_stddev, self.duration_stddev / self.duration * 100.0)
    }
}

fn duration_secs(d: Duration) -> f64 {
    d.as_secs() as f64 + d.subsec_nanos() as f64 / 1.0e9
}

// Returns estimate of single-iteration time
fn warmup<A, F: Fn() -> A>(func: F) -> f64 {
    let mut ntimes = 1;
    let mut time_taken = 0.0;

    while time_taken < 0.5 {
        let start = Instant::now();
        for _ in 0..ntimes {
            func();
        }
        let end = Instant::now();
        time_taken = duration_secs(end - start);

        ntimes *= 2;
    }

    time_taken / ntimes as f64
}

pub fn benchmark<A, F: Fn() -> A>(func: F) -> Bench {
    let estimate = warmup(&func);
    let ntimes_guess = if MIN_TIMES as f64 * estimate >= MIN_DUR {
        MIN_TIMES
    } else {
        (MIN_DUR / estimate).ceil() as usize
    };

    let nparts = if ntimes_guess < 10 {
        ntimes_guess
    } else {
        std::cmp::max(10, ntimes_guess / 10)
    };
    let nperpart = (ntimes_guess + nparts - 1) / nparts;

    let ntimes = nparts * nperpart;

    // eprintln!("BENCH: estimate={} ntimes_guess={} nparts={} nperpart={} ntimes={}", estimate, ntimes_guess, nparts, nperpart, ntimes);

    let mut times = vec![0.0; nparts];

    for i in 0..nparts {
        let start = Instant::now();
        for _ in 0..nperpart {
            func();
        }
        let end = Instant::now();

        times[i] = duration_secs(end - start);
    }

    let mean = times.iter().map(|&t| t).sum::<f64>() / ntimes as f64;
    let stddev = times.iter().map(|t| (t - mean) * (t - mean)).sum::<f64>() / (ntimes - 1) as f64;

    Bench { executions: 0, duration: mean, duration_stddev: stddev }
}