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_stderr: f64,
}

impl fmt::Display for Bench {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{} secs ± {} ({}%)",
               self.duration, self.duration_stderr, self.duration_stderr / 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 / 100)
    };
    let nperpart = (ntimes_guess + nparts - 1) / nparts;

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

    let mut times = Vec::new();

    let mut mean = 0.0;
    let mut stderr = 0.0;

    eprint!("BENCH: Running {} blocks of {} calls...", nparts, nperpart);

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

            times.push(duration_secs(end - start));
        }

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

        if stderr / mean < 0.05 {
            break;
        }

        eprint!(" again({},{})", mean, stderr);
    }

    eprintln!("");

    Bench { executions: times.len() * nperpart, duration: mean, duration_stderr: stderr }
}