use criterion::BatchSize::SmallInput;
use criterion::*;

#[cfg(feature = "arc")]
use im::Vector as IVec;

#[cfg(not(feature = "arc"))]
use im_rc::Vector as IVec;

use rand::{RngCore, SeedableRng};
use rand_xorshift::XorShiftRng;

use pvec::core::RbVec;
use pvec::core::RrbVec;
use pvec::PVec;

use super::*;

fn rnd() -> XorShiftRng {
    XorShiftRng::from_seed([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15])
}

macro_rules! vec_balanced {
    ($n:ident, $new_vec:expr, $push:ident) => {
        || {
            let mut vec = $new_vec();

            for i in 0..*$n {
                vec.$push(i);
            }

            vec
        }
    };
}

macro_rules! vec_relaxed {
    ($n:ident, $new_vec:expr, $push:ident, $append:path) => {
        || {
            let mut i = 1;
            let mut vec = $new_vec();

            while i < *$n && (vec.len() + i) <= *$n {
                let mut another_vec = $new_vec();

                for j in 0..i {
                    another_vec.$push(j);
                }

                $append(&mut vec, another_vec);
                i *= 2;
            }

            while vec.len() < *$n {
                vec.$push(i);
            }

            vec
        }
    };
}

mod append {
    use super::*;

    pub fn ivec(vec: &mut IVec<usize>, data: IVec<usize>) {
        vec.append(data);
    }

    pub fn rrbvec(vec: &mut RrbVec<usize>, mut data: RrbVec<usize>) {
        vec.append(&mut data);
    }

    pub fn pvec(vec: &mut PVec<usize>, mut data: PVec<usize>) {
        vec.append(&mut data);
    }
}

fn index_sequentially(criterion: &mut Criterion) {
    macro_rules! bench {
        ($n:ident) => {
            |vec| {
                for i in 0..*$n {
                    black_box(vec[i]);
                }

                vec
            }
        };
    }

    let mut group = criterion.benchmark_group("index_sequentially");
    group.plot_config(PlotConfiguration::default().summary_scale(AxisScale::Logarithmic));

    macro_rules! bench_balanced {
        ($name:ident, $p:ident, $new_vec:expr, $push:ident) => {
            group.bench_with_input(BenchmarkId::new($name, $p), $p, |b, n| {
                b.iter_batched(vec_balanced!(n, $new_vec, $push), bench!(n), SmallInput)
            });
        };
    }

    macro_rules! bench_relaxed {
        ($name:ident, $p:ident, $new_vec:expr, $push:ident, $append:path) => {
            group.bench_with_input(BenchmarkId::new($name, $p), $p, |b, n| {
                b.iter_batched(
                    vec_relaxed!(n, $new_vec, $push, $append),
                    bench!(n),
                    SmallInput,
                )
            });
        };
    }

    let params = vec![
        20, 40, 60, 80, 100, 200, 400, 600, 800, 1000, 2000, 4000, 6000, 8000, 10000, 20000, 40000,
        60000, 80000, 100000, 200000, 400000, 600000, 800000, 1000000,
    ];

    for p in params.iter() {
        bench_balanced!(STD_VEC, p, || Vec::new(), push);

        bench_balanced!(IM_RS_VECTOR_BALANCED, p, || IVec::new(), push_back);
        bench_relaxed!(
            IM_RS_VECTOR_RELAXED,
            p,
            || IVec::new(),
            push_back,
            append::ivec
        );

        bench_balanced!(RBVEC, p, || RbVec::new(), push);
        bench_relaxed!(RRBVEC, p, || RrbVec::new(), push, append::rrbvec);

        bench_balanced!(PVEC_STD, p, || PVec::new(), push);
        bench_balanced!(PVEC_RRBVEC_BALANCED, p, || PVec::new_with_tree(), push);
        bench_relaxed!(
            PVEC_RRBVEC_RELAXED,
            p,
            || PVec::new_with_tree(),
            push,
            append::pvec
        );
    }

    group.finish();
}

fn index_randomly(criterion: &mut Criterion) {
    macro_rules! bench {
        ($n:ident, $rnd:ident) => {
            |vec| {
                for _ in 0..*$n {
                    let j = ($rnd.next_u32() as usize) % *$n;
                    black_box(vec[j]);
                }

                vec
            }
        };
    }

    let mut group = criterion.benchmark_group("index_randomly");
    group.plot_config(PlotConfiguration::default().summary_scale(AxisScale::Logarithmic));

    macro_rules! bench_balanced {
        ($name:ident, $p:ident, $new_vec:expr, $push:ident) => {
            group.bench_with_input(BenchmarkId::new($name, $p), $p, |b, n| {
                let mut rnd = rnd();

                b.iter_batched(
                    vec_balanced!(n, $new_vec, $push),
                    bench!(n, rnd),
                    SmallInput,
                )
            });
        };
    }

    macro_rules! bench_relaxed {
        ($name:ident, $p:ident, $new_vec:expr, $push:ident, $append:path) => {
            group.bench_with_input(BenchmarkId::new($name, $p), $p, |b, n| {
                let mut rnd = rnd();

                b.iter_batched(
                    vec_relaxed!(n, $new_vec, $push, $append),
                    bench!(n, rnd),
                    SmallInput,
                )
            });
        };
    }

    let params = vec![
        20, 40, 60, 80, 100, 200, 400, 600, 800, 1000, 2000, 4000, 6000, 8000, 10000, 20000, 40000,
        60000, 80000, 100000, 200000, 400000,
    ];

    for p in params.iter() {
        bench_balanced!(STD_VEC, p, || Vec::new(), push);

        bench_balanced!(IM_RS_VECTOR_BALANCED, p, || IVec::new(), push_back);
        bench_relaxed!(
            IM_RS_VECTOR_RELAXED,
            p,
            || IVec::new(),
            push_back,
            append::ivec
        );

        bench_balanced!(RBVEC, p, || RbVec::new(), push);
        bench_relaxed!(RRBVEC, p, || RrbVec::new(), push, append::rrbvec);

        bench_balanced!(PVEC_STD, p, || PVec::new(), push);
        bench_balanced!(PVEC_RRBVEC_BALANCED, p, || PVec::new_with_tree(), push);
        bench_relaxed!(
            PVEC_RRBVEC_RELAXED,
            p,
            || PVec::new_with_tree(),
            push,
            append::pvec
        );
    }

    group.finish();
}

fn iterator_next(criterion: &mut Criterion) {
    macro_rules! bench {
        () => {
            |vec| {
                for i in vec.into_iter() {
                    black_box(i);
                }
            }
        };
    }

    let mut group = criterion.benchmark_group("iterator_next");
    group.plot_config(PlotConfiguration::default().summary_scale(AxisScale::Logarithmic));

    macro_rules! bench_balanced {
        ($name:ident, $p:ident, $new_vec:expr, $push:ident) => {
            group.bench_with_input(BenchmarkId::new($name, $p), $p, |b, n| {
                b.iter_batched(vec_balanced!(n, $new_vec, $push), bench!(), SmallInput)
            });
        };
    }

    macro_rules! bench_relaxed {
        ($name:ident, $p:ident, $new_vec:expr, $push:ident, $append:path) => {
            group.bench_with_input(BenchmarkId::new($name, $p), $p, |b, n| {
                b.iter_batched(
                    vec_relaxed!(n, $new_vec, $push, $append),
                    bench!(),
                    SmallInput,
                )
            });
        };
    }

    let params = vec![
        20, 40, 60, 80, 100, 200, 400, 600, 800, 1000, 2000, 4000, 6000, 8000, 10000, 20000, 40000,
        60000, 80000, 100000, 200000, 400000, 600000, 800000, 1000000,
    ];

    for p in params.iter() {
        bench_balanced!(STD_VEC, p, || Vec::new(), push);

        bench_balanced!(IM_RS_VECTOR_BALANCED, p, || IVec::new(), push_back);
        bench_relaxed!(
            IM_RS_VECTOR_RELAXED,
            p,
            || IVec::new(),
            push_back,
            append::ivec
        );

        bench_balanced!(RBVEC, p, || RbVec::new(), push);
        bench_relaxed!(RRBVEC, p, || RrbVec::new(), push, append::rrbvec);

        bench_balanced!(PVEC_STD, p, || PVec::new(), push);
        bench_balanced!(PVEC_RRBVEC_BALANCED, p, || PVec::new_with_tree(), push);
        bench_relaxed!(
            PVEC_RRBVEC_RELAXED,
            p,
            || PVec::new_with_tree(),
            push,
            append::pvec
        );
    }

    group.finish();
}

fn push(criterion: &mut Criterion) {
    let mut group = criterion.benchmark_group("push");
    group.plot_config(PlotConfiguration::default().summary_scale(AxisScale::Logarithmic));

    macro_rules! bench {
        ($p:ident, $new_vec:expr, $push:ident, $name:ident) => {
            group.bench_with_input(BenchmarkId::new($name, $p), $p, |b, n| {
                b.iter(vec_balanced!(n, $new_vec, $push))
            });
        };
    }

    let params = vec![
        20, 40, 60, 80, 100, 200, 400, 600, 800, 1000, 2000, 4000, 6000, 8000, 10000, 20000, 40000,
        60000, 80000, 100000, 200000, 400000, 600000, 800000, 1000000,
    ];

    for p in params.iter() {
        bench!(p, || Vec::new(), push, STD_VEC);
        bench!(p, || IVec::new(), push_back, IM_RS_VECTOR_BALANCED);
        bench!(p, || RbVec::new(), push, RBVEC);
        bench!(p, || PVec::new(), push, PVEC_STD);
        bench!(p, || PVec::new_with_tree(), push, PVEC_RRBVEC_BALANCED);
    }

    group.finish();
}

fn push_clone(criterion: &mut Criterion) {
    let mut group = criterion.benchmark_group("push_clone");
    group.plot_config(PlotConfiguration::default().summary_scale(AxisScale::Logarithmic));

    macro_rules! bench {
        ($p:ident, $new_vec:expr, $push:ident, $name:ident) => {
            group.bench_with_input(BenchmarkId::new($name, $p), $p, |b, n| {
                b.iter(|| {
                    let mut vec_1 = $new_vec();
                    let mut vec_2 = vec_1.clone();
                    let mut vec_3 = vec_2.clone();

                    for i in 0..*n {
                        vec_3 = vec_1;
                        vec_1 = vec_2;

                        vec_1.$push(i);
                        vec_2 = vec_1.clone();
                    }

                    (vec_1, vec_2, vec_3)
                })
            });
        };
    }

    let params = vec![
        20, 40, 60, 80, 100, 200, 400, 600, 800, 1000, 2000, 4000, 6000, 8000, 10000, 20000, 40000,
    ];

    for p in params.iter() {
        bench!(p, || Vec::new(), push, STD_VEC);
        bench!(p, || IVec::new(), push_back, IM_RS_VECTOR_BALANCED);
        bench!(p, || RbVec::new(), push, RBVEC);
        bench!(p, || PVec::new_with_tree(), push, PVEC_RRBVEC_BALANCED);
    }

    group.finish();
}

fn push_relaxed(criterion: &mut Criterion) {
    macro_rules! bench {
        ($n:ident, $push:ident) => {
            |mut vec| {
                for i in 0..*$n {
                    vec.$push(i);
                }

                vec
            }
        };
    }

    let mut group = criterion.benchmark_group("push_relaxed");
    group.plot_config(PlotConfiguration::default().summary_scale(AxisScale::Logarithmic));

    macro_rules! bench_balanced {
        ($name:ident, $p:ident, $new_vec:expr, $push:ident) => {
            group.bench_with_input(BenchmarkId::new($name, $p), $p, |b, n| {
                b.iter_batched(
                    vec_balanced!(n, $new_vec, $push),
                    bench!(n, $push),
                    SmallInput,
                )
            });
        };
    }

    macro_rules! bench_relaxed {
        ($name:ident, $p:ident, $new_vec:expr, $push:ident, $append:path) => {
            group.bench_with_input(BenchmarkId::new($name, $p), $p, |b, n| {
                b.iter_batched(
                    vec_relaxed!(n, $new_vec, $push, $append),
                    bench!(n, $push),
                    SmallInput,
                )
            });
        };
    }

    let params = vec![
        20, 40, 60, 80, 100, 200, 400, 600, 800, 1000, 2000, 4000, 6000, 8000, 10000, 20000, 40000,
        60000, 80000, 100000,
    ];

    for p in params.iter() {
        bench_balanced!(STD_VEC, p, || Vec::new(), push);

        bench_balanced!(IM_RS_VECTOR_BALANCED, p, || IVec::new(), push_back);
        bench_relaxed!(
            IM_RS_VECTOR_RELAXED,
            p,
            || IVec::new(),
            push_back,
            append::ivec
        );

        bench_balanced!(RBVEC, p, || RbVec::new(), push);
        bench_relaxed!(RRBVEC, p, || RrbVec::new(), push, append::rrbvec);

        bench_balanced!(PVEC_STD, p, || PVec::new(), push);
        bench_balanced!(PVEC_RRBVEC_BALANCED, p, || PVec::new_with_tree(), push);
        bench_relaxed!(
            PVEC_RRBVEC_RELAXED,
            p,
            || PVec::new_with_tree(),
            push,
            append::pvec
        );
    }

    group.finish();
}

fn push_clone_relaxed(criterion: &mut Criterion) {
    macro_rules! bench {
        ($n:ident, $push:ident) => {
            |vec| {
                let mut vec_1 = vec;
                let mut vec_2 = vec_1.clone();
                let mut vec_3 = vec_2.clone();

                for i in 0..*$n {
                    vec_3 = vec_1;
                    vec_1 = vec_2;

                    vec_1.$push(i);
                    vec_2 = vec_1.clone();
                }

                (vec_1, vec_2, vec_3)
            }
        };
    }

    let mut group = criterion.benchmark_group("push_clone_relaxed");
    group.plot_config(PlotConfiguration::default().summary_scale(AxisScale::Logarithmic));

    macro_rules! bench_balanced {
        ($name:ident, $p:ident, $new_vec:expr, $push:ident) => {
            group.bench_with_input(BenchmarkId::new($name, $p), $p, |b, n| {
                b.iter_batched(
                    vec_balanced!(n, $new_vec, $push),
                    bench!(n, $push),
                    SmallInput,
                )
            });
        };
    }

    macro_rules! bench_relaxed {
        ($name:ident, $p:ident, $new_vec:expr, $push:ident, $append:path) => {
            group.bench_with_input(BenchmarkId::new($name, $p), $p, |b, n| {
                b.iter_batched(
                    vec_relaxed!(n, $new_vec, $push, $append),
                    bench!(n, $push),
                    SmallInput,
                )
            });
        };
    }

    let params = vec![
        20, 40, 60, 80, 100, 200, 400, 600, 800, 1000, 2000, 4000, 6000, 8000, 10000, 20000, 40000,
    ];

    for p in params.iter() {
        bench_balanced!(STD_VEC, p, || Vec::new(), push);

        bench_balanced!(IM_RS_VECTOR_BALANCED, p, || IVec::new(), push_back);
        bench_relaxed!(
            IM_RS_VECTOR_RELAXED,
            p,
            || IVec::new(),
            push_back,
            append::ivec
        );

        bench_balanced!(RBVEC, p, || RbVec::new(), push);
        bench_relaxed!(RRBVEC, p, || RrbVec::new(), push, append::rrbvec);

        bench_balanced!(PVEC_STD, p, || PVec::new(), push);
        bench_balanced!(PVEC_RRBVEC_BALANCED, p, || PVec::new_with_tree(), push);
        bench_relaxed!(
            PVEC_RRBVEC_RELAXED,
            p,
            || PVec::new_with_tree(),
            push,
            append::pvec
        );
    }

    group.finish();
}

fn update(criterion: &mut Criterion) {
    macro_rules! bench {
        ($n:ident) => {
            |mut vec| {
                for i in 0..*$n {
                    (*vec.get_mut(i).unwrap()) += 1;
                }

                vec
            }
        };
    }

    let mut group = criterion.benchmark_group("update");
    group.plot_config(PlotConfiguration::default().summary_scale(AxisScale::Logarithmic));

    macro_rules! bench_balanced {
        ($name:ident, $p:ident, $new_vec:expr, $push:ident) => {
            group.bench_with_input(BenchmarkId::new($name, $p), $p, |b, n| {
                b.iter_batched(vec_balanced!(n, $new_vec, $push), bench!(n), SmallInput)
            });
        };
    }

    macro_rules! bench_relaxed {
        ($name:ident, $p:ident, $new_vec:expr, $push:ident, $append:path) => {
            group.bench_with_input(BenchmarkId::new($name, $p), $p, |b, n| {
                b.iter_batched(
                    vec_relaxed!(n, $new_vec, $push, $append),
                    bench!(n),
                    SmallInput,
                )
            });
        };
    }

    let params = vec![
        20, 40, 60, 80, 100, 200, 400, 600, 800, 1000, 2000, 4000, 6000, 8000, 10000, 20000, 40000,
        60000, 80000, 100000,
    ];

    for p in params.iter() {
        bench_balanced!(STD_VEC, p, || Vec::new(), push);

        bench_balanced!(IM_RS_VECTOR_BALANCED, p, || IVec::new(), push_back);
        bench_relaxed!(
            IM_RS_VECTOR_RELAXED,
            p,
            || IVec::new(),
            push_back,
            append::ivec
        );

        bench_balanced!(RBVEC, p, || RbVec::new(), push);
        bench_relaxed!(RRBVEC, p, || RrbVec::new(), push, append::rrbvec);

        bench_balanced!(PVEC_STD, p, || PVec::new(), push);
        bench_balanced!(PVEC_RRBVEC_BALANCED, p, || PVec::new_with_tree(), push);
        bench_relaxed!(
            PVEC_RRBVEC_RELAXED,
            p,
            || PVec::new_with_tree(),
            push,
            append::pvec
        );
    }

    group.finish();
}

fn update_randomly(criterion: &mut Criterion) {
    macro_rules! bench {
        ($n:ident, $rnd:ident) => {
            |mut vec| {
                for _ in 0..*$n {
                    let j = ($rnd.next_u32() as usize) % *$n;
                    (*vec.get_mut(j).unwrap()) += 1;
                }

                vec
            }
        };
    }

    let mut group = criterion.benchmark_group("update_randomly");
    group.plot_config(PlotConfiguration::default().summary_scale(AxisScale::Logarithmic));

    macro_rules! bench_balanced {
        ($name:ident, $p:ident, $new_vec:expr, $push:ident) => {
            group.bench_with_input(BenchmarkId::new($name, $p), $p, |b, n| {
                let mut rnd = rnd();

                b.iter_batched(
                    vec_balanced!(n, $new_vec, $push),
                    bench!(n, rnd),
                    SmallInput,
                )
            });
        };
    }

    macro_rules! bench_relaxed {
        ($name:ident, $p:ident, $new_vec:expr, $push:ident, $append:path) => {
            group.bench_with_input(BenchmarkId::new($name, $p), $p, |b, n| {
                let mut rnd = rnd();

                b.iter_batched(
                    vec_relaxed!(n, $new_vec, $push, $append),
                    bench!(n, rnd),
                    SmallInput,
                )
            });
        };
    }

    let params = vec![
        20, 40, 60, 80, 100, 200, 400, 600, 800, 1000, 2000, 4000, 6000, 8000, 10000, 20000, 40000,
        60000, 80000, 100000,
    ];

    for p in params.iter() {
        bench_balanced!(STD_VEC, p, || Vec::new(), push);

        bench_balanced!(IM_RS_VECTOR_BALANCED, p, || IVec::new(), push_back);
        bench_relaxed!(
            IM_RS_VECTOR_RELAXED,
            p,
            || IVec::new(),
            push_back,
            append::ivec
        );

        bench_balanced!(RBVEC, p, || RbVec::new(), push);
        bench_relaxed!(RRBVEC, p, || RrbVec::new(), push, append::rrbvec);

        bench_balanced!(PVEC_STD, p, || PVec::new(), push);
        bench_balanced!(PVEC_RRBVEC_BALANCED, p, || PVec::new_with_tree(), push);
        bench_relaxed!(
            PVEC_RRBVEC_RELAXED,
            p,
            || PVec::new_with_tree(),
            push,
            append::pvec
        );
    }

    group.finish();
}

fn update_clone(criterion: &mut Criterion) {
    macro_rules! bench {
        ($n:ident) => {
            |vec| {
                let mut vec_1 = vec;
                let mut vec_2 = vec_1.clone();
                let mut vec_3 = vec_2.clone();

                for i in 0..*$n {
                    vec_3 = vec_1;
                    vec_1 = vec_2;

                    (*vec_1.get_mut(i).unwrap()) += 1;
                    vec_2 = vec_1.clone();
                }

                (vec_1, vec_2, vec_3)
            }
        };
    }

    let mut group = criterion.benchmark_group("update_clone");
    group.plot_config(PlotConfiguration::default().summary_scale(AxisScale::Logarithmic));

    macro_rules! bench_balanced {
        ($name:ident, $p:ident, $new_vec:expr, $push:ident) => {
            group.bench_with_input(BenchmarkId::new($name, $p), $p, |b, n| {
                b.iter_batched(vec_balanced!(n, $new_vec, $push), bench!(n), SmallInput)
            });
        };
    }

    macro_rules! bench_relaxed {
        ($name:ident, $p:ident, $new_vec:expr, $push:ident, $append:path) => {
            group.bench_with_input(BenchmarkId::new($name, $p), $p, |b, n| {
                b.iter_batched(
                    vec_relaxed!(n, $new_vec, $push, $append),
                    bench!(n),
                    SmallInput,
                )
            });
        };
    }

    let params = vec![
        20, 40, 60, 80, 100, 200, 400, 600, 800, 1000, 2000, 4000, 6000, 8000, 10000, 20000,
    ];

    for p in params.iter() {
        bench_balanced!(STD_VEC, p, || Vec::new(), push);

        bench_balanced!(IM_RS_VECTOR_BALANCED, p, || IVec::new(), push_back);
        bench_relaxed!(
            IM_RS_VECTOR_RELAXED,
            p,
            || IVec::new(),
            push_back,
            append::ivec
        );

        bench_balanced!(RBVEC, p, || RbVec::new(), push);
        bench_relaxed!(RRBVEC, p, || RrbVec::new(), push, append::rrbvec);

        bench_balanced!(PVEC_STD, p, || PVec::new(), push);
        bench_balanced!(PVEC_RRBVEC_BALANCED, p, || PVec::new_with_tree(), push);
        bench_relaxed!(
            PVEC_RRBVEC_RELAXED,
            p,
            || PVec::new_with_tree(),
            push,
            append::pvec
        );
    }

    group.finish();
}

fn update_clone_randomly(criterion: &mut Criterion) {
    macro_rules! bench {
        ($n:ident, $rnd:ident) => {
            |vec| {
                let mut vec_1 = vec;
                let mut vec_2 = vec_1.clone();
                let mut vec_3 = vec_2.clone();

                for _ in 0..*$n {
                    vec_3 = vec_1;
                    vec_1 = vec_2;

                    let j = ($rnd.next_u32() as usize) % *$n;
                    (*vec_1.get_mut(j).unwrap()) += 1;

                    vec_2 = vec_1.clone();
                }

                (vec_1, vec_2, vec_3)
            }
        };
    }

    let mut group = criterion.benchmark_group("update_clone_randomly");
    group.plot_config(PlotConfiguration::default().summary_scale(AxisScale::Logarithmic));

    macro_rules! bench_balanced {
        ($name:ident, $p:ident, $new_vec:expr, $push:ident) => {
            group.bench_with_input(BenchmarkId::new($name, $p), $p, |b, n| {
                let mut rnd = rnd();

                b.iter_batched(
                    vec_balanced!(n, $new_vec, $push),
                    bench!(n, rnd),
                    SmallInput,
                )
            });
        };
    }

    macro_rules! bench_relaxed {
        ($name:ident, $p:ident, $new_vec:expr, $push:ident, $append:path) => {
            group.bench_with_input(BenchmarkId::new($name, $p), $p, |b, n| {
                let mut rnd = rnd();

                b.iter_batched(
                    vec_relaxed!(n, $new_vec, $push, $append),
                    bench!(n, rnd),
                    SmallInput,
                )
            });
        };
    }

    let params = vec![
        20, 40, 60, 80, 100, 200, 400, 600, 800, 1000, 2000, 4000, 6000, 8000, 10000, 20000,
    ];

    for p in params.iter() {
        bench_balanced!(STD_VEC, p, || Vec::new(), push);

        bench_balanced!(IM_RS_VECTOR_BALANCED, p, || IVec::new(), push_back);
        bench_relaxed!(
            IM_RS_VECTOR_RELAXED,
            p,
            || IVec::new(),
            push_back,
            append::ivec
        );

        bench_balanced!(RBVEC, p, || RbVec::new(), push);
        bench_relaxed!(RRBVEC, p, || RrbVec::new(), push, append::rrbvec);

        bench_balanced!(PVEC_STD, p, || PVec::new(), push);
        bench_balanced!(PVEC_RRBVEC_BALANCED, p, || PVec::new_with_tree(), push);
        bench_relaxed!(
            PVEC_RRBVEC_RELAXED,
            p,
            || PVec::new_with_tree(),
            push,
            append::pvec
        );
    }

    group.finish();
}

fn pop(criterion: &mut Criterion) {
    macro_rules! bench {
        ($n:ident, $pop:ident) => {
            |mut vec| {
                for _ in 0..*$n {
                    black_box(vec.$pop());
                }

                vec
            }
        };
    }

    let mut group = criterion.benchmark_group("pop");
    group.plot_config(PlotConfiguration::default().summary_scale(AxisScale::Logarithmic));

    macro_rules! bench_balanced {
        ($name:ident, $p:ident, $new_vec:expr, $push:ident, $pop:ident) => {
            group.bench_with_input(BenchmarkId::new($name, $p), $p, |b, n| {
                b.iter_batched(
                    vec_balanced!(n, $new_vec, $push),
                    bench!(n, $pop),
                    SmallInput,
                )
            });
        };
    }

    macro_rules! bench_relaxed {
        ($name:ident, $p:ident, $new_vec:expr, $push:ident, $pop:ident, $append:path) => {
            group.bench_with_input(BenchmarkId::new($name, $p), $p, |b, n| {
                b.iter_batched(
                    vec_relaxed!(n, $new_vec, $push, $append),
                    bench!(n, $pop),
                    SmallInput,
                )
            });
        };
    }

    let params = vec![
        20, 40, 60, 80, 100, 200, 400, 600, 800, 1000, 2000, 4000, 6000, 8000, 10000, 20000, 40000,
        60000,
    ];

    for p in params.iter() {
        bench_balanced!(STD_VEC, p, || Vec::new(), push, pop);

        bench_balanced!(
            IM_RS_VECTOR_BALANCED,
            p,
            || IVec::new(),
            push_back,
            pop_back
        );
        bench_relaxed!(
            IM_RS_VECTOR_RELAXED,
            p,
            || IVec::new(),
            push_back,
            pop_back,
            append::ivec
        );

        bench_balanced!(RBVEC, p, || RbVec::new(), push, pop);
        bench_relaxed!(RRBVEC, p, || RrbVec::new(), push, pop, append::rrbvec);

        bench_balanced!(PVEC_STD, p, || PVec::new(), push, pop);
        bench_balanced!(PVEC_RRBVEC_BALANCED, p, || PVec::new_with_tree(), push, pop);
        bench_relaxed!(
            PVEC_RRBVEC_RELAXED,
            p,
            || PVec::new_with_tree(),
            push,
            pop,
            append::pvec
        );
    }

    group.finish();
}

fn pop_clone(criterion: &mut Criterion) {
    macro_rules! bench {
        ($n:ident, $pop:ident) => {
            |vec| {
                let mut vec_1 = vec;
                let mut vec_2 = vec_1.clone();
                let mut vec_3 = vec_2.clone();

                for _ in 0..*$n {
                    vec_3 = vec_1;
                    vec_1 = vec_2;

                    black_box(vec_1.$pop());
                    vec_2 = vec_1.clone();
                }

                (vec_1, vec_2, vec_3)
            }
        };
    }

    let mut group = criterion.benchmark_group("pop_clone");
    group.plot_config(PlotConfiguration::default().summary_scale(AxisScale::Logarithmic));

    macro_rules! bench_balanced {
        ($name:ident, $p:ident, $new_vec:expr, $push:ident, $pop:ident) => {
            group.bench_with_input(BenchmarkId::new($name, $p), $p, |b, n| {
                b.iter_batched(
                    vec_balanced!(n, $new_vec, $push),
                    bench!(n, $pop),
                    SmallInput,
                )
            });
        };
    }

    macro_rules! bench_relaxed {
        ($name:ident, $p:ident, $new_vec:expr, $push:ident, $pop:ident, $append:path) => {
            group.bench_with_input(BenchmarkId::new($name, $p), $p, |b, n| {
                b.iter_batched(
                    vec_relaxed!(n, $new_vec, $push, $append),
                    bench!(n, $pop),
                    SmallInput,
                )
            });
        };
    }

    let params = vec![
        20, 40, 60, 80, 100, 200, 400, 600, 800, 1000, 2000, 4000, 6000, 8000, 10000, 20000, 40000,
    ];

    for p in params.iter() {
        bench_balanced!(STD_VEC, p, || Vec::new(), push, pop);

        bench_balanced!(
            IM_RS_VECTOR_BALANCED,
            p,
            || IVec::new(),
            push_back,
            pop_back
        );
        bench_relaxed!(
            IM_RS_VECTOR_RELAXED,
            p,
            || IVec::new(),
            push_back,
            pop_back,
            append::ivec
        );

        bench_balanced!(RBVEC, p, || RbVec::new(), push, pop);
        bench_relaxed!(RRBVEC, p, || RrbVec::new(), push, pop, append::rrbvec);

        bench_balanced!(PVEC_STD, p, || PVec::new(), push, pop);
        bench_balanced!(PVEC_RRBVEC_BALANCED, p, || PVec::new_with_tree(), push, pop);
        bench_relaxed!(
            PVEC_RRBVEC_RELAXED,
            p,
            || PVec::new_with_tree(),
            push,
            pop,
            append::pvec
        );
    }

    group.finish();
}

fn append(criterion: &mut Criterion) {
    macro_rules! create_input {
        ($n:ident, $new_vec:expr, $push:ident) => {
            || {
                let mut input = Vec::new();
                let mut input_len = 0;
                let mut i = 1;

                while i < *$n && (input_len + i) <= *$n {
                    let mut vec = $new_vec();

                    for j in 0..i {
                        vec.$push(j);
                    }

                    input_len += vec.len();
                    input.push(vec);

                    i *= 2;
                }

                let mut vec = $new_vec();
                let mut j = 0;

                while input_len < *$n {
                    vec.$push(j);

                    input_len += 1;
                    j += 1;
                }

                input.push(vec);
                input
            }
        };
    }

    macro_rules! bench {
        ($n:ident, $new_vec:expr) => {
            |data| {
                let mut vec = $new_vec();

                for mut input in data.into_iter() {
                    vec.append(&mut input);
                }

                vec
            }
        };
    }

    let params = vec![
        20, 40, 60, 80, 100, 200, 400, 600, 800, 1000, 2000, 4000, 6000, 8000, 10000, 20000, 40000,
        60000, 80000, 100000, 200000, 400000, 600000, 800000, 1000000,
    ];

    let mut group = criterion.benchmark_group("append");
    group.plot_config(PlotConfiguration::default().summary_scale(AxisScale::Logarithmic));

    for p in params.iter() {
        group.bench_with_input(BenchmarkId::new(STD_VEC, p), p, |b, n| {
            b.iter_batched(
                create_input!(n, || Vec::new(), push),
                bench!(n, || Vec::new()),
                SmallInput,
            )
        });
        group.bench_with_input(BenchmarkId::new(IM_RS_VECTOR_RELAXED, p), p, |b, n| {
            b.iter_batched(
                create_input!(n, || IVec::new(), push_back),
                |data| {
                    let mut vec_two = IVec::new();

                    for input in data.into_iter() {
                        vec_two.append(input);
                    }

                    vec_two
                },
                SmallInput,
            )
        });
        group.bench_with_input(BenchmarkId::new(RRBVEC, p), p, |b, n| {
            b.iter_batched(
                create_input!(n, || RrbVec::new(), push),
                bench!(n, || RrbVec::new()),
                SmallInput,
            )
        });
        group.bench_with_input(BenchmarkId::new(RBVEC, p), p, |b, n| {
            b.iter_batched(
                create_input!(n, || RbVec::new(), push),
                bench!(n, || RbVec::new()),
                SmallInput,
            )
        });
        group.bench_with_input(BenchmarkId::new(PVEC_STD, p), p, |b, n| {
            b.iter_batched(
                create_input!(n, || PVec::new(), push),
                bench!(n, || PVec::new()),
                SmallInput,
            )
        });
        group.bench_with_input(BenchmarkId::new(PVEC_RRBVEC_RELAXED, p), p, |b, n| {
            b.iter_batched(
                create_input!(n, || PVec::new_with_tree(), push),
                bench!(n, || PVec::new_with_tree()),
                SmallInput,
            )
        });
    }

    group.finish();
}

fn split_off(criterion: &mut Criterion) {
    macro_rules! bench {
        () => {
            |mut vec| {
                while vec.len() > 64 {
                    vec = vec.split_off(64)
                }

                vec
            }
        };
    }

    macro_rules! make_bench {
        ($group:ident, $p:ident, $new_vec:expr, $push:ident, $name:ident) => {
            $group.bench_with_input(BenchmarkId::new($name, $p), $p, |b, n| {
                b.iter_batched(vec_balanced!(n, $new_vec, $push), bench!(), SmallInput)
            });
        };
    }

    let mut group = criterion.benchmark_group("split_off");
    group.plot_config(PlotConfiguration::default().summary_scale(AxisScale::Logarithmic));

    let params = vec![
        128, 512, 768, 1024, 2048, 4096, 10000, 20000, 30000, 40000, 60000, 80000, 100000, 200000,
    ];
    for p in params.iter() {
        make_bench!(group, p, || Vec::new(), push, STD_VEC);
        make_bench!(group, p, || RbVec::new(), push, RBVEC);
        make_bench!(group, p, || RrbVec::new(), push, RRBVEC);
        make_bench!(group, p, || IVec::new(), push_back, IM_RS_VECTOR_RELAXED);
        make_bench!(group, p, || PVec::new(), push, PVEC_STD);
        make_bench!(
            group,
            p,
            || PVec::new_with_tree(),
            push,
            PVEC_RRBVEC_RELAXED
        );
    }

    group.finish();
}

criterion_group!(
    benches,
    index_sequentially,
    index_randomly,
    iterator_next,
    push,
    push_clone,
    push_relaxed,
    push_clone_relaxed,
    update,
    update_randomly,
    update_clone,
    update_clone_randomly,
    pop,
    pop_clone,
    append,
    split_off
);