use std::cmp;
use crate::set::{Set, vec_sets_into_slices};
use crate::{SetOperation, exponential_offset_ge_by_key};
#[derive(Clone)]
pub struct DifferenceByKey<'a, T: 'a, U: 'a, F, G, K>
where F: Fn(&T) -> K,
G: Fn(&U) -> K,
K: Ord,
{
base: &'a [T],
others: Vec<&'a [U]>,
f: F,
g: G,
}
impl<'a, T, U, F, G, K> DifferenceByKey<'a, T, U, F, G, K>
where F: Fn(&T) -> K,
G: Fn(&U) -> K,
K: Ord,
{
pub fn new(base: &'a Set<T>, others: Vec<&'a Set<U>>, f: F, g: G) -> Self {
Self {
base: base.as_slice(),
others: vec_sets_into_slices(others),
f: f,
g: g,
}
}
}
impl<'a, T, U, F, G, K> DifferenceByKey<'a, T, U, F, G, K>
where F: Fn(&T) -> K,
G: Fn(&U) -> K,
K: Ord,
{
fn extend_vec<X, E>(mut self, output: &mut Vec<X>, extend: E)
where E: Fn(&mut Vec<X>, &'a [T]),
{
while let Some(first) = self.base.first().map(|x| (self.f)(x)) {
let mut minimum = None;
for slice in self.others.iter_mut() {
*slice = exponential_offset_ge_by_key(slice, &first, &self.g);
let first = match slice.first() {
Some(first) => Some((self.g)(first)),
None => None,
};
minimum = match (minimum, first) {
(Some(min), Some(first)) => Some(cmp::min(min, first)),
(None, Some(first)) => Some(first),
(min, _) => min,
};
}
match minimum {
Some(min) => {
if min == first {
self.base = exponential_offset_ge_by_key(&self.base[1..], &min, &self.f);
} else {
let off = self.base.iter().take_while(|&x| (self.f)(x) < min).count();
extend(output, &self.base[..off]);
self.base = &self.base[off..];
}
},
None => {
extend(output, self.base);
break;
},
}
}
}
}
impl<'a, T, U, F, G, K> SetOperation<T> for DifferenceByKey<'a, T, U, F, G, K>
where T: Clone,
F: Fn(&T) -> K,
G: Fn(&U) -> K,
K: Ord,
{
fn extend_vec(self, output: &mut Vec<T>) {
self.extend_vec(output, Vec::extend_from_slice)
}
}
impl<'a, T, U, F, G, K> SetOperation<&'a T> for DifferenceByKey<'a, T, U, F, G, K>
where F: Fn(&T) -> K,
G: Fn(&U) -> K,
K: Ord,
{
fn extend_vec(self, output: &mut Vec<&'a T>) {
self.extend_vec(output, Extend::extend)
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::set::{sort_dedup_vec, SetBuf};
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
struct Foo {
a: i32,
b: i8,
}
impl Foo {
fn new(a: i32) -> Foo {
Foo { a, b: 0 }
}
}
#[test]
fn one_empty_slice() {
let a: &[Foo] = &[];
let op = DifferenceByKey { base: a, others: vec![], f: |x| x.a, g: |&x| x };
let res: SetBuf<Foo> = op.into_set_buf();
assert_eq!(&res[..], &[]);
}
#[test]
fn one_slice() {
let a = &[Foo::new(1), Foo::new(2), Foo::new(3)];
let op = DifferenceByKey { base: a, others: vec![], f: |x| x.a, g: |&x| x };
let res: SetBuf<Foo> = op.into_set_buf();
assert_eq!(&res[..], &[Foo::new(1), Foo::new(2), Foo::new(3)]);
}
#[test]
fn two_slices() {
let a = &[Foo::new(1), Foo::new(2), Foo::new(3)];
let b = &[2, 4];
let op = DifferenceByKey { base: a, others: vec![b], f: |x| x.a, g: |&x| x };
let res: SetBuf<Foo> = op.into_set_buf();
assert_eq!(&res[..], &[Foo::new(1), Foo::new(3)]);
}
#[test]
fn two_slices_special_case() {
let a = &[Foo::new(1), Foo::new(2), Foo::new(3)];
let b = &[3];
let op = DifferenceByKey { base: a, others: vec![b], f: |x| x.a, g: |&x| x };
let res: SetBuf<Foo> = op.into_set_buf();
assert_eq!(&res[..], &[Foo::new(1), Foo::new(2)]);
}
#[test]
fn three_slices() {
let a = &[Foo::new(1), Foo::new(2), Foo::new(3), Foo::new(6), Foo::new(7)];
let b = &[2, 3, 4];
let c = &[3, 4, 5, 7];
let op = DifferenceByKey { base: a, others: vec![b, c], f: |x| x.a, g: |&x| x };
let res: SetBuf<Foo> = op.into_set_buf();
assert_eq!(&res[..], &[Foo::new(1), Foo::new(6)]);
}
quickcheck! {
fn qc_difference(base: Vec<i32>, xss: Vec<Vec<i64>>) -> bool {
use std::collections::BTreeSet;
use std::iter::FromIterator;
let mut base = base;
let mut xss = xss;
sort_dedup_vec(&mut base);
for xs in &mut xss {
sort_dedup_vec(xs);
}
let x: SetBuf<i32> = {
let xss = xss.iter().map(|xs| xs.as_slice()).collect();
DifferenceByKey { base: &base, others: xss, f: |&x| x, g: |&x| x as i32 }.into_set_buf()
};
let mut y = BTreeSet::from_iter(base);
for v in xss {
let x = BTreeSet::from_iter(v.into_iter().map(|x| x as i32));
y = y.difference(&x).cloned().collect();
}
let y: Vec<_> = y.into_iter().collect();
x.as_slice() == y.as_slice()
}
}
}
#[cfg(all(feature = "unstable", test))]
mod bench {
extern crate test;
use super::*;
use self::test::Bencher;
use crate::set::SetBuf;
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
struct Foo {
a: i32,
b: i8,
}
impl Foo {
fn new(a: i32) -> Foo {
Foo { a, b: 0 }
}
}
#[bench]
fn two_slices_big(bench: &mut Bencher) {
let a: Vec<_> = (0..100).map(Foo::new).collect();
let b: Vec<_> = (1..101).collect();
bench.iter(|| {
let op = DifferenceByKey { base: &a, others: vec![&b], f: |x| x.a, g: |&x| x };
let res: SetBuf<Foo> = op.into_set_buf();
test::black_box(|| res);
});
}
#[bench]
fn two_slices_big2(bench: &mut Bencher) {
let a: Vec<_> = (0..100).map(Foo::new).collect();
let b: Vec<_> = (51..151).collect();
bench.iter(|| {
let op = DifferenceByKey { base: &a, others: vec![&b], f: |x| x.a, g: |&x| x };
let res: SetBuf<Foo> = op.into_set_buf();
test::black_box(|| res);
});
}
#[bench]
fn two_slices_big3(bench: &mut Bencher) {
let a: Vec<_> = (0..100).map(Foo::new).collect();
let b: Vec<_> = (100..200).collect();
bench.iter(|| {
let op = DifferenceByKey { base: &a, others: vec![&b], f: |x| x.a, g: |&x| x };
let res: SetBuf<Foo> = op.into_set_buf();
test::black_box(|| res);
});
}
#[bench]
fn three_slices_big(bench: &mut Bencher) {
let a: Vec<_> = (0..100).map(Foo::new).collect();
let b: Vec<_> = (1..101).collect();
let c: Vec<_> = (2..102).collect();
bench.iter(|| {
let op = DifferenceByKey { base: &a, others: vec![&b, &c], f: |x| x.a, g: |&x| x };
let res: SetBuf<Foo> = op.into_set_buf();
test::black_box(|| res);
});
}
#[bench]
fn three_slices_big2(bench: &mut Bencher) {
let a: Vec<_> = (0..100).map(Foo::new).collect();
let b: Vec<_> = (34..134).collect();
let c: Vec<_> = (66..167).collect();
bench.iter(|| {
let op = DifferenceByKey { base: &a, others: vec![&b, &c], f: |x| x.a, g: |&x| x };
let res: SetBuf<Foo> = op.into_set_buf();
test::black_box(|| res);
});
}
#[bench]
fn three_slices_big3(bench: &mut Bencher) {
let a: Vec<_> = (0..100).map(Foo::new).collect();
let b: Vec<_> = (100..200).collect();
let c: Vec<_> = (200..300).collect();
bench.iter(|| {
let op = DifferenceByKey { base: &a, others: vec![&b, &c], f: |x| x.a, g: |&x| x };
let res: SetBuf<Foo> = op.into_set_buf();
test::black_box(|| res);
});
}
}