mod binary_group;
mod binary_group_by;
mod binary_group_by_key;
pub use self::binary_group::{BinaryGroup, BinaryGroupMut};
pub use self::binary_group_by::{BinaryGroupBy, BinaryGroupByMut};
pub use self::binary_group_by_key::{BinaryGroupByKey, BinaryGroupByKeyMut};
#[cfg(test)]
mod tests {
use super::*;
#[derive(Debug, Eq)]
enum Guard {
Valid(i32),
Invalid(i32),
}
impl PartialEq for Guard {
fn eq(&self, other: &Self) -> bool {
match (self, other) {
(Guard::Valid(_), Guard::Valid(_)) => true,
(a, b) => panic!("denied read on Guard::Invalid variant ({:?}, {:?})", a, b),
}
}
}
#[test]
fn one_big_group() {
let slice = &[1, 1, 1, 1];
let mut iter = BinaryGroup::new(slice);
assert_eq!(iter.next(), Some(&[1, 1, 1, 1][..]));
assert_eq!(iter.next(), None);
}
#[test]
fn two_equal_groups() {
let slice = &[1, 1, 1, 1, 2, 2, 2, 2];
let mut iter = BinaryGroup::new(slice);
assert_eq!(iter.next(), Some(&[1, 1, 1, 1][..]));
assert_eq!(iter.next(), Some(&[2, 2, 2, 2][..]));
assert_eq!(iter.next(), None);
}
#[test]
fn two_little_equal_groups() {
let slice = &[1, 2];
let mut iter = BinaryGroup::new(slice);
assert_eq!(iter.next(), Some(&[1][..]));
assert_eq!(iter.next(), Some(&[2][..]));
assert_eq!(iter.next(), None);
}
#[test]
fn three_groups() {
let slice = &[1, 1, 1, 2, 2, 2, 3, 3];
let mut iter = BinaryGroup::new(slice);
assert_eq!(iter.next(), Some(&[1, 1, 1][..]));
assert_eq!(iter.next(), Some(&[2, 2, 2][..]));
assert_eq!(iter.next(), Some(&[3, 3][..]));
assert_eq!(iter.next(), None);
}
#[test]
fn three_little_groups() {
let slice = &[1, 2, 3];
let mut iter = BinaryGroup::new(slice);
assert_eq!(iter.next(), Some(&[1][..]));
assert_eq!(iter.next(), Some(&[2][..]));
assert_eq!(iter.next(), Some(&[3][..]));
assert_eq!(iter.next(), None);
}
#[test]
fn overflow() {
let slice = &[Guard::Invalid(0), Guard::Valid(1), Guard::Valid(2), Guard::Invalid(3)];
let mut iter = BinaryGroup::new(&slice[1..3]);
assert_eq!(iter.next(), Some(&[Guard::Valid(1), Guard::Valid(2)][..]));
assert_eq!(iter.next(), None);
}
#[test]
fn last_three_little_groups() {
let slice = &[1, 2, 3];
let iter = BinaryGroup::new(slice);
assert_eq!(iter.last(), Some(&[3][..]));
}
#[test]
fn last_three_groups() {
let slice = &[1, 1, 1, 2, 2, 2, 3, 3];
let iter = BinaryGroup::new(slice);
assert_eq!(iter.last(), Some(&[3, 3][..]));
}
#[test]
fn last_overflow() {
let slice = &[Guard::Invalid(0), Guard::Valid(1), Guard::Valid(2), Guard::Invalid(3)];
println!("{:?}", (&slice[1..3]).as_ptr());
let iter = BinaryGroup::new(&slice[1..3]);
assert_eq!(iter.last(), Some(&[Guard::Valid(1), Guard::Valid(2)][..]));
}
#[test]
fn back_empty_slice() {
let slice: &[i32] = &[];
let mut iter = BinaryGroup::new(slice);
assert_eq!(iter.next_back(), None);
}
#[test]
fn back_one_little_group() {
let slice = &[1];
let mut iter = BinaryGroup::new(slice);
assert_eq!(iter.next_back(), Some(&[1][..]));
assert_eq!(iter.next_back(), None);
assert_eq!(iter.next(), None);
}
#[test]
fn back_three_little_groups() {
let slice = &[1, 2, 3];
let mut iter = BinaryGroup::new(slice);
assert_eq!(iter.next_back(), Some(&[3][..]));
assert_eq!(iter.next_back(), Some(&[2][..]));
assert_eq!(iter.next_back(), Some(&[1][..]));
assert_eq!(iter.next_back(), None);
}
#[test]
fn back_three_groups() {
let slice = &[1, 1, 1, 2, 2, 2, 3, 3];
let mut iter = BinaryGroup::new(slice);
assert_eq!(iter.next_back(), Some(&[3, 3][..]));
assert_eq!(iter.next_back(), Some(&[2, 2, 2][..]));
assert_eq!(iter.next_back(), Some(&[1, 1, 1][..]));
assert_eq!(iter.next_back(), None);
}
#[test]
fn double_ended_dont_cross() {
let slice = &[1, 1, 1, 2, 2, 2, 3, 3];
let mut iter = BinaryGroup::new(slice);
assert_eq!(iter.next(), Some(&[1, 1, 1][..]));
assert_eq!(iter.next_back(), Some(&[3, 3][..]));
assert_eq!(iter.next(), Some(&[2, 2, 2][..]));
assert_eq!(iter.next_back(), None);
assert_eq!(iter.next(), None);
}
#[test]
fn fused_iterator() {
let slice = &[1, 2, 3];
let mut iter = BinaryGroup::new(slice);
assert_eq!(iter.next(), Some(&[1][..]));
assert_eq!(iter.next(), Some(&[2][..]));
assert_eq!(iter.next(), Some(&[3][..]));
assert_eq!(iter.next(), None);
assert_eq!(iter.next(), None);
}
#[test]
fn back_fused_iterator() {
let slice = &[1, 2, 3];
let mut iter = BinaryGroup::new(slice);
assert_eq!(iter.next_back(), Some(&[3][..]));
assert_eq!(iter.next_back(), Some(&[2][..]));
assert_eq!(iter.next_back(), Some(&[1][..]));
assert_eq!(iter.next_back(), None);
assert_eq!(iter.next_back(), None);
}
}
#[cfg(all(feature = "nightly", test))]
mod bench {
extern crate test;
extern crate rand;
use super::*;
use self::rand::{Rng, SeedableRng};
use self::rand::rngs::StdRng;
use self::rand::distributions::Alphanumeric;
#[bench]
fn vector_16_000_sorted(b: &mut test::Bencher) {
let mut rng = StdRng::from_seed([42; 32]);
let len = 16_000;
let mut vec = Vec::with_capacity(len);
for _ in 0..len {
vec.push(rng.sample(Alphanumeric));
}
vec.sort_unstable();
b.iter(|| {
let group_by = BinaryGroup::new(vec.as_slice());
test::black_box(group_by.count())
})
}
#[bench]
fn vector_little_sorted(b: &mut test::Bencher) {
let mut rng = StdRng::from_seed([42; 32]);
let len = 30;
let mut vec = Vec::with_capacity(len);
for _ in 0..len {
vec.push(rng.sample(Alphanumeric));
}
vec.sort_unstable();
b.iter(|| {
let group_by = BinaryGroup::new(vec.as_slice());
test::black_box(group_by.count())
})
}
#[bench]
fn vector_16_000_one_group(b: &mut test::Bencher) {
let vec = vec![1; 16_000];
b.iter(|| {
let group_by = BinaryGroup::new(vec.as_slice());
test::black_box(group_by.count())
})
}
#[bench]
fn rev_vector_16_000_sorted(b: &mut test::Bencher) {
let mut rng = StdRng::from_seed([42; 32]);
let len = 16_000;
let mut vec = Vec::with_capacity(len);
for _ in 0..len {
vec.push(rng.sample(Alphanumeric));
}
vec.sort_unstable();
b.iter(|| {
let group_by = BinaryGroup::new(vec.as_slice());
test::black_box(group_by.rev().count())
})
}
#[bench]
fn rev_vector_16_000_one_group(b: &mut test::Bencher) {
let vec = vec![1; 16_000];
b.iter(|| {
let group_by = BinaryGroup::new(vec.as_slice());
test::black_box(group_by.rev().count())
})
}
}