use criterion::{criterion_group, criterion_main, BenchmarkId, Criterion, Throughput};

use kmp::{kmp_find_with_lsp_table, kmp_table};

fn increasing_haystack(c: &mut Criterion) {
    let max_power: usize = 16;

    // this needle will never match
    let needle = vec![8, 7, 6, 5, 4, 3, 2, 1];
    // we already benchmark this function and can safely reuse the table here
    let table = kmp_table(&needle);

    let mut group = c.benchmark_group("find in increasing haystack");
    // we don't need to benchmark if the haystack is smaller than the needle
    for power in 3..=max_power {
        let elements = 2_usize.pow(power as u32);
        let vector = (0..=elements).collect::<Vec<usize>>();

        group.throughput(Throughput::Elements(elements as u64));
        group.bench_with_input(BenchmarkId::from_parameter(elements), &vector, |b, haystack| {
            b.iter(|| kmp_find_with_lsp_table(&needle, haystack, &table));
        });
    }
    group.finish();
}

fn increasing_needle(c: &mut Criterion) {
    let max_power: usize = 16;

    // we reverse so a match never happens
    let haystack = (0..u16::max_value() as usize).rev().collect::<Vec<usize>>();

    let mut group = c.benchmark_group("find with increasing needle");
    for power in 0..=max_power {
        let elements = 2_usize.pow(power as u32);
        let needle = (0..=elements).collect::<Vec<usize>>();
        let table = kmp_table(&needle);

        group.throughput(Throughput::Elements(elements as u64));
        group.bench_with_input(BenchmarkId::from_parameter(elements), &needle, |b, needle| {
            b.iter(|| kmp_find_with_lsp_table(needle, &haystack, &table));
        });
    }
    group.finish();
}

criterion_group!(benches, increasing_haystack, increasing_needle);
criterion_main!(benches);