#[macro_use]
extern crate criterion;

use std::iter;

use criterion::Criterion;
use rand_core::{RngCore, SeedableRng};

use blossom::Graph;

fn generate_random_graph(size: usize, rng: &mut impl RngCore) -> Graph {
    let mut edges: Vec<_> = iter::repeat(vec![]).take(size).collect();
    for i in 0..size {
        let mut j = i + 1;
        while j < size {
            let interval = size + 1 - j;
            let p = (rng.next_u64() as usize) % interval + j;
            if p < size {
                edges[i].push(p);
                edges[p].push(i);
            }
            j = p + 1;
        }
    }

    edges.into_iter().enumerate().collect()
}

fn generator_benchmark(c: &mut Criterion) {
    let mut rng = rand_xorshift::XorShiftRng::from_seed([0; 16]);
    let g10 = generate_random_graph(10, &mut rng);
    c.bench_function("g10", move |b| b.iter(|| g10.maximum_matching()));
    let g100 = generate_random_graph(100, &mut rng);
    c.bench_function("g100", move |b| b.iter(|| g100.maximum_matching()));
}

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