splinter-rs 0.12.2

use std::{
    mem,
    ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Deref, Sub, SubAssign},
};

use crate::{CowSplinter, Cut, PartitionRead, Splinter, SplinterRef};

impl<B: Deref<Target = [u8]>> PartialEq<SplinterRef<B>> for Splinter {
    #[inline]
    fn eq(&self, other: &SplinterRef<B>) -> bool {
        self.inner() == &other.load_unchecked()
    }
}

impl<B: Deref<Target = [u8]>> PartialEq<CowSplinter<B>> for Splinter {
    fn eq(&self, other: &CowSplinter<B>) -> bool {
        match other {
            CowSplinter::Ref(splinter_ref) => self.eq(splinter_ref),
            CowSplinter::Owned(splinter) => self.eq(splinter),
        }
    }
}

impl Cut for Splinter {
    type Out = Self;

    fn cut(&mut self, rhs: &Self) -> Self::Out {
        Self::new(self.inner_mut().cut(rhs.inner()))
    }
}

impl<B: Deref<Target = [u8]>> Cut<SplinterRef<B>> for Splinter {
    type Out = Self;

    fn cut(&mut self, rhs: &SplinterRef<B>) -> Self::Out {
        Self::new(self.inner_mut().cut(&rhs.load_unchecked()))
    }
}

impl<B: Deref<Target = [u8]>> Cut<CowSplinter<B>> for Splinter {
    type Out = Self;

    fn cut(&mut self, rhs: &CowSplinter<B>) -> Self::Out {
        match rhs {
            CowSplinter::Ref(splinter_ref) => self.cut(splinter_ref),
            CowSplinter::Owned(splinter) => self.cut(splinter),
        }
    }
}

macro_rules! binary_bitop {
    ($BitOp:tt, $bitop:ident, $bitassign:path) => {
        impl $BitOp<Splinter> for Splinter {
            type Output = Splinter;
            #[inline]
            fn $bitop(mut self, rhs: Splinter) -> Self::Output {
                $bitassign(&mut self, rhs);
                self
            }
        }
        impl $BitOp<&Splinter> for Splinter {
            type Output = Splinter;
            #[inline]
            fn $bitop(mut self, rhs: &Splinter) -> Self::Output {
                $bitassign(&mut self, rhs);
                self
            }
        }
        impl<B: Deref<Target = [u8]>> $BitOp<SplinterRef<B>> for Splinter {
            type Output = Splinter;
            #[inline]
            fn $bitop(mut self, rhs: SplinterRef<B>) -> Self::Output {
                $bitassign(&mut self, rhs);
                self
            }
        }
        impl<B: Deref<Target = [u8]>> $BitOp<&SplinterRef<B>> for Splinter {
            type Output = Splinter;
            #[inline]
            fn $bitop(mut self, rhs: &SplinterRef<B>) -> Self::Output {
                $bitassign(&mut self, rhs);
                self
            }
        }
        impl<B: Deref<Target = [u8]>> $BitOp<SplinterRef<B>> for &Splinter {
            type Output = Splinter;
            #[inline]
            fn $bitop(self, rhs: SplinterRef<B>) -> Self::Output {
                $BitOp::$bitop(self.clone(), rhs)
            }
        }
        impl<B: Deref<Target = [u8]>> $BitOp<&SplinterRef<B>> for &Splinter {
            type Output = Splinter;
            #[inline]
            fn $bitop(self, rhs: &SplinterRef<B>) -> Self::Output {
                $BitOp::$bitop(self.clone(), rhs)
            }
        }
        impl<B: Deref<Target = [u8]>> $BitOp<CowSplinter<B>> for Splinter {
            type Output = Splinter;
            #[inline]
            fn $bitop(self, rhs: CowSplinter<B>) -> Self::Output {
                $BitOp::$bitop(&self, &rhs)
            }
        }
        impl<B: Deref<Target = [u8]>> $BitOp<CowSplinter<B>> for &Splinter {
            type Output = Splinter;
            #[inline]
            fn $bitop(self, rhs: CowSplinter<B>) -> Self::Output {
                $BitOp::$bitop(self, &rhs)
            }
        }
        impl<B: Deref<Target = [u8]>> $BitOp<&CowSplinter<B>> for Splinter {
            type Output = Splinter;
            #[inline]
            fn $bitop(self, rhs: &CowSplinter<B>) -> Self::Output {
                $BitOp::$bitop(&self, rhs)
            }
        }
        impl<B: Deref<Target = [u8]>> $BitOp<&CowSplinter<B>> for &Splinter {
            type Output = Splinter;
            fn $bitop(self, rhs: &CowSplinter<B>) -> Self::Output {
                match rhs {
                    CowSplinter::Ref(inner) => $BitOp::$bitop(self, inner),
                    CowSplinter::Owned(inner) => $BitOp::$bitop(self, inner),
                }
            }
        }
    };
}

macro_rules! unary_bitassign {
    ($BitOpAssign:tt, $bitassign:ident) => {
        impl $BitOpAssign<&Splinter> for Splinter {
            #[inline]
            fn $bitassign(&mut self, rhs: &Splinter) {
                $BitOpAssign::$bitassign(self.inner_mut(), rhs.inner())
            }
        }
        impl<B: Deref<Target = [u8]>> $BitOpAssign<SplinterRef<B>> for Splinter {
            #[inline]
            fn $bitassign(&mut self, rhs: SplinterRef<B>) {
                $BitOpAssign::$bitassign(self.inner_mut(), &rhs.load_unchecked())
            }
        }
        impl<B: Deref<Target = [u8]>> $BitOpAssign<&SplinterRef<B>> for Splinter {
            #[inline]
            fn $bitassign(&mut self, rhs: &SplinterRef<B>) {
                $BitOpAssign::$bitassign(self.inner_mut(), &rhs.load_unchecked())
            }
        }
        impl<B: Deref<Target = [u8]>> $BitOpAssign<CowSplinter<B>> for Splinter {
            fn $bitassign(&mut self, rhs: CowSplinter<B>) {
                match rhs {
                    CowSplinter::Ref(splinter_ref) => $BitOpAssign::$bitassign(self, splinter_ref),
                    CowSplinter::Owned(splinter) => $BitOpAssign::$bitassign(self, splinter),
                }
            }
        }
        impl<B: Deref<Target = [u8]>> $BitOpAssign<&CowSplinter<B>> for Splinter {
            fn $bitassign(&mut self, rhs: &CowSplinter<B>) {
                match rhs {
                    CowSplinter::Ref(splinter_ref) => $BitOpAssign::$bitassign(self, splinter_ref),
                    CowSplinter::Owned(splinter) => $BitOpAssign::$bitassign(self, splinter),
                }
            }
        }
    };
}

binary_bitop!(BitOr, bitor, BitOrAssign::bitor_assign);
unary_bitassign!(BitOrAssign, bitor_assign);

binary_bitop!(BitAnd, bitand, BitAndAssign::bitand_assign);
unary_bitassign!(BitAndAssign, bitand_assign);

binary_bitop!(BitXor, bitxor, BitXorAssign::bitxor_assign);
unary_bitassign!(BitXorAssign, bitxor_assign);

binary_bitop!(Sub, sub, SubAssign::sub_assign);
unary_bitassign!(SubAssign, sub_assign);

impl BitOr<&Splinter> for &Splinter {
    type Output = Splinter;
    fn bitor(self, rhs: &Splinter) -> Self::Output {
        // merge into the larger set
        if rhs.cardinality() > self.cardinality() {
            let mut result = rhs.clone();
            result.inner_mut().bitor_assign(self.inner());
            result
        } else {
            let mut result = self.clone();
            result.inner_mut().bitor_assign(rhs.inner());
            result
        }
    }
}

impl BitOr<Splinter> for &Splinter {
    type Output = Splinter;
    fn bitor(self, rhs: Splinter) -> Self::Output {
        rhs | self
    }
}

impl BitOrAssign<Splinter> for Splinter {
    fn bitor_assign(&mut self, mut rhs: Splinter) {
        // merge into the larger set
        if rhs.cardinality() > self.cardinality() {
            mem::swap(self, &mut rhs);
        }
        self.inner_mut().bitor_assign(rhs.inner())
    }
}

impl BitAnd<&Splinter> for &Splinter {
    type Output = Splinter;
    fn bitand(self, rhs: &Splinter) -> Self::Output {
        // intersect into the smaller set
        if rhs.cardinality() < self.cardinality() {
            let mut result = rhs.clone();
            result.inner_mut().bitand_assign(self.inner());
            result
        } else {
            let mut result = self.clone();
            result.inner_mut().bitand_assign(rhs.inner());
            result
        }
    }
}

impl BitAnd<Splinter> for &Splinter {
    type Output = Splinter;
    fn bitand(self, rhs: Splinter) -> Self::Output {
        rhs & self
    }
}

impl BitAndAssign<Splinter> for Splinter {
    fn bitand_assign(&mut self, mut rhs: Splinter) {
        // intersect into the smaller set
        if rhs.cardinality() < self.cardinality() {
            mem::swap(self, &mut rhs);
        }
        self.inner_mut().bitand_assign(rhs.inner())
    }
}

impl BitXor<&Splinter> for &Splinter {
    type Output = Splinter;
    fn bitxor(self, rhs: &Splinter) -> Self::Output {
        let mut result = self.clone();
        result.inner_mut().bitxor_assign(rhs.inner());
        result
    }
}

impl BitXor<Splinter> for &Splinter {
    type Output = Splinter;
    fn bitxor(self, rhs: Splinter) -> Self::Output {
        rhs ^ self
    }
}

impl BitXorAssign<Splinter> for Splinter {
    fn bitxor_assign(&mut self, rhs: Splinter) {
        self.inner_mut().bitxor_assign(rhs.inner())
    }
}

impl Sub<&Splinter> for &Splinter {
    type Output = Splinter;
    fn sub(self, rhs: &Splinter) -> Self::Output {
        let mut result = self.clone();
        result.inner_mut().sub_assign(rhs.inner());
        result
    }
}

impl Sub<Splinter> for &Splinter {
    type Output = Splinter;
    fn sub(self, rhs: Splinter) -> Self::Output {
        self - &rhs
    }
}

impl SubAssign<Splinter> for Splinter {
    fn sub_assign(&mut self, rhs: Splinter) {
        self.inner_mut().sub_assign(rhs.inner())
    }
}

#[cfg(test)]
mod tests {
    use std::ops::{
        BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Sub, SubAssign,
    };

    use itertools::Itertools;
    use proptest::collection::{hash_set, vec};
    use proptest::proptest;

    use crate::testutil::{mksplinter_cow, mksplinter_ref};
    use crate::{Optimizable, PartitionRead, Splinter, testutil::mksplinter, traits::Cut};

    macro_rules! exercise_bitop {
        ($a:expr, $b:expr, $seta:expr, $setb:expr, $op_method:ident, $hashset_method:ident) => {
            let expected: Splinter = $seta.$hashset_method(&$setb).copied().collect();

            assert_eq!((&$a).$op_method(&$b), expected, "&a, &b");
            assert_eq!((&$a).$op_method($b.clone()), expected, "&a, b");
            assert_eq!($a.clone().$op_method(&$b), expected, "a, &b");
            assert_eq!($a.clone().$op_method($b.clone()), expected, "a, b");
        };
    }

    macro_rules! exercise_bitop_assign {
        ($a:expr, $b:expr, $seta:expr, $setb:expr, $op_assign_method:ident, $hashset_method:ident) => {
            let expected: Splinter = $seta.$hashset_method(&$setb).copied().collect();

            let mut c = $a.clone();
            c.$op_assign_method($b.clone());
            assert_eq!(c, expected, "c assign b");

            let mut c = $a.clone();
            c.$op_assign_method(&$b);
            assert_eq!(c, expected, "c assign &b");
        };
    }

    macro_rules! gen_bitop_test {
        ($test_name:ident, $make_a:path, $make_b:path) => {
            proptest! {
                #[test]
                fn $test_name(
                    seta in hash_set(0u32..16384, 0..1024),
                    setb in hash_set(0u32..16384, 0..1024),
                ) {
                    let a = $make_a(seta.clone());
                    let b = $make_b(setb.clone());
                    exercise_bitop!(a, b, seta, setb, bitor, union);
                    exercise_bitop!(a, b, seta, setb, bitand, intersection);
                    exercise_bitop!(a, b, seta, setb, bitxor, symmetric_difference);
                    exercise_bitop!(a, b, seta, setb, sub, difference);
                }
            }
        };
    }

    macro_rules! gen_bitop_assign_test {
        ($test_name:ident, $make_b:path) => {
            proptest! {
                #[test]
                fn $test_name(
                    optimize: bool,
                    seta in hash_set(0u32..16384, 0..1024),
                    setb in hash_set(0u32..16384, 0..1024),
                ) {
                    let mut a = Splinter::from_iter(seta.clone());
                    let b = $make_b(setb.clone());
                    if optimize {
                        a.optimize();
                    }
                    exercise_bitop_assign!(a, b, seta, setb, bitor_assign, union);
                    exercise_bitop_assign!(a, b, seta, setb, bitand_assign, intersection);
                    exercise_bitop_assign!(a, b, seta, setb, bitxor_assign, symmetric_difference);
                    exercise_bitop_assign!(a, b, seta, setb, sub_assign, difference);
                }
            }
        };
    }

    gen_bitop_test!(test_ops_s_s, Splinter::from_iter, Splinter::from_iter);
    gen_bitop_test!(test_ops_s_sr, Splinter::from_iter, mksplinter_ref);
    gen_bitop_test!(test_ops_s_sc, Splinter::from_iter, mksplinter_cow);

    gen_bitop_test!(test_ops_sr_sr, mksplinter_ref, mksplinter_ref);
    gen_bitop_test!(test_ops_sr_sc, mksplinter_ref, mksplinter_cow);

    gen_bitop_test!(test_ops_sc_s, mksplinter_cow, Splinter::from_iter);
    gen_bitop_test!(test_ops_sc_sr, mksplinter_cow, mksplinter_ref);

    gen_bitop_assign_test!(test_ops_splinter_splinter_assign, Splinter::from_iter);
    gen_bitop_assign_test!(test_ops_splinter_splinterref_assign, mksplinter_ref);
    gen_bitop_assign_test!(test_ops_splinter_splintercow_assign, mksplinter_cow);

    proptest! {
        #[test]
        fn test_splinter_equality_proptest(values in vec(0u32..16384, 0..1024)) {
            let mut a = mksplinter(&values);
            a.optimize();
            let b = mksplinter(&values);
            assert!(a == b)
        }

        #[test]
        fn test_splinter_equality_ref_proptest(values in vec(0u32..16384, 0..1024)) {
            let mut a = mksplinter(&values);
            a.optimize();
            let b = mksplinter(&values).encode_to_splinter_ref();
            assert!(a == b)
        }

        #[test]
        fn test_splinter_equality_proptest_2(
            a in vec(0u32..16384, 0..1024),
            b in vec(0u32..16384, 0..1024),
        ) {
            let expected = itertools::equal(a.iter().sorted().dedup(), b.iter().sorted().dedup());

            let mut a = mksplinter(&a);
            a.optimize();
            let b = mksplinter(&b);

            assert!((a == b) == expected)
        }

        #[test]
        fn test_splinter_equality_ref_proptest_2(
            a in vec(0u32..16384, 0..1024),
            b in vec(0u32..16384, 0..1024),
        ) {
            let expected = itertools::equal(a.iter().sorted().dedup(), b.iter().sorted().dedup());

            let mut a = mksplinter(&a);
            a.optimize();
            let b = mksplinter(&b).encode_to_splinter_ref();

            assert!((a == b) == expected)
        }

        #[test]
        fn test_bitor_assign_proptest(
            optimize: bool,
            a in hash_set(0u32..16384, 0..1024),
            b in hash_set(0u32..16384, 0..1024),
        ) {
            let mut set: Splinter = a.iter().copied().collect();
            let other: Splinter = b.iter().copied().collect();

            if optimize {
                set.optimize();
            }

            let expected: Splinter = a.union(&b).copied().collect();
            set |= other;
            assert!(set == expected)
        }

        #[test]
        fn test_cut_proptest(
            optimize: bool,
            a in hash_set(0u32..16384, 0..1024),
            b in hash_set(0u32..16384, 0..1024),
        ) {
            let mut source: Splinter = a.iter().copied().collect();
            let other: Splinter = b.iter().copied().collect();

            if optimize {
                source.optimize();
            }

            let expected_intersection: Splinter = a.intersection(&b).copied().collect();
            let expected_remaining: Splinter = a.difference(&b).copied().collect();

            let actual_intersection = source.cut(&other);

            assert_eq!(actual_intersection,expected_intersection);
            assert_eq!(source,expected_remaining);
        }

        #[test]
        fn test_bitor_ref_proptest(
            optimize: bool,
            a in hash_set(0u32..16384, 0..1024),
            b in hash_set(0u32..16384, 0..1024),
        ) {
            let mut set: Splinter = a.iter().copied().collect();
            let other_ref = Splinter::from_iter(b.clone()).encode_to_splinter_ref();

            if optimize {
                set.optimize();
            }

            let expected: Splinter = a.union(&b).copied().collect();
            set |= other_ref;
            assert!(set == expected)
        }

        #[test]
        fn test_cut_ref_proptest(
            optimize: bool,
            a in hash_set(0u32..16384, 0..1024),
            b in hash_set(0u32..16384, 0..1024),
        ) {
            let mut source: Splinter = a.iter().copied().collect();
            let other_ref = Splinter::from_iter(b.clone()).encode_to_splinter_ref();

            if optimize {
                source.optimize();
            }

            let expected_intersection: Splinter = a.intersection(&b).copied().collect();
            let expected_remaining: Splinter = a.difference(&b).copied().collect();

            let actual_intersection = source.cut(&other_ref);

            assert_eq!(actual_intersection,expected_intersection);
            assert_eq!(source,expected_remaining);
        }
    }

    // -- Hegel property-based tests --

    use hegel::generators;

    /// Union is commutative: a | b == b | a
    #[hegel::test]
    fn test_union_commutative(tc: hegel::TestCase) {
        let va: Vec<u32> = tc.draw(generators::vecs(generators::integers::<u32>()));
        let vb: Vec<u32> = tc.draw(generators::vecs(generators::integers::<u32>()));
        let a = Splinter::from_iter(va);
        let b = Splinter::from_iter(vb);
        assert_eq!(&a | &b, &b | &a);
    }

    /// Intersection is commutative: a & b == b & a
    #[hegel::test]
    fn test_intersection_commutative(tc: hegel::TestCase) {
        let va: Vec<u32> = tc.draw(generators::vecs(generators::integers::<u32>()));
        let vb: Vec<u32> = tc.draw(generators::vecs(generators::integers::<u32>()));
        let a = Splinter::from_iter(va);
        let b = Splinter::from_iter(vb);
        assert_eq!(&a & &b, &b & &a);
    }

    /// XOR is commutative: a ^ b == b ^ a
    #[hegel::test]
    fn test_xor_commutative(tc: hegel::TestCase) {
        let va: Vec<u32> = tc.draw(generators::vecs(generators::integers::<u32>()));
        let vb: Vec<u32> = tc.draw(generators::vecs(generators::integers::<u32>()));
        let a = Splinter::from_iter(va);
        let b = Splinter::from_iter(vb);
        assert_eq!(&a ^ &b, &b ^ &a);
    }

    /// Union with self is idempotent: a | a == a
    #[hegel::test]
    fn test_union_idempotent(tc: hegel::TestCase) {
        let values: Vec<u32> = tc.draw(generators::vecs(generators::integers::<u32>()));
        let a = Splinter::from_iter(values);
        assert_eq!(&a | &a, a);
    }

    /// Intersection with self is idempotent: a & a == a
    #[hegel::test]
    fn test_intersection_idempotent(tc: hegel::TestCase) {
        let values: Vec<u32> = tc.draw(generators::vecs(generators::integers::<u32>()));
        let a = Splinter::from_iter(values);
        assert_eq!(&a & &a, a);
    }

    /// XOR with self is empty: a ^ a == empty
    #[hegel::test]
    fn test_xor_self_is_empty(tc: hegel::TestCase) {
        let values: Vec<u32> = tc.draw(generators::vecs(generators::integers::<u32>()));
        let a = Splinter::from_iter(values);
        assert_eq!(&a ^ &a, Splinter::EMPTY);
    }

    /// Difference with self is empty: a - a == empty
    #[hegel::test]
    fn test_difference_self_is_empty(tc: hegel::TestCase) {
        let values: Vec<u32> = tc.draw(generators::vecs(generators::integers::<u32>()));
        let a = Splinter::from_iter(values);
        assert_eq!(&a - &a, Splinter::EMPTY);
    }

    /// Union with empty is identity: a | empty == a
    #[hegel::test]
    fn test_union_empty_identity(tc: hegel::TestCase) {
        let values: Vec<u32> = tc.draw(generators::vecs(generators::integers::<u32>()));
        let a = Splinter::from_iter(values);
        assert_eq!(&a | &Splinter::EMPTY, a);
    }

    /// Intersection with empty is empty: a & empty == empty
    #[hegel::test]
    fn test_intersection_empty_is_empty(tc: hegel::TestCase) {
        let values: Vec<u32> = tc.draw(generators::vecs(generators::integers::<u32>()));
        let a = Splinter::from_iter(values);
        assert_eq!(&a & &Splinter::EMPTY, Splinter::EMPTY);
    }

    /// |a & b| <= min(|a|, |b|)
    #[hegel::test]
    fn test_intersection_cardinality_bound(tc: hegel::TestCase) {
        let va: Vec<u32> = tc.draw(generators::vecs(generators::integers::<u32>()));
        let vb: Vec<u32> = tc.draw(generators::vecs(generators::integers::<u32>()));
        let a = Splinter::from_iter(va);
        let b = Splinter::from_iter(vb);
        let intersection = &a & &b;
        assert!(intersection.cardinality() <= a.cardinality().min(b.cardinality()));
    }

    /// |a | b| >= max(|a|, |b|)
    #[hegel::test]
    fn test_union_cardinality_bound(tc: hegel::TestCase) {
        let va: Vec<u32> = tc.draw(generators::vecs(generators::integers::<u32>()));
        let vb: Vec<u32> = tc.draw(generators::vecs(generators::integers::<u32>()));
        let a = Splinter::from_iter(va);
        let b = Splinter::from_iter(vb);
        let union = &a | &b;
        assert!(union.cardinality() >= a.cardinality().max(b.cardinality()));
    }

    /// Inclusion-exclusion: |a | b| = |a| + |b| - |a & b|
    #[hegel::test]
    fn test_inclusion_exclusion(tc: hegel::TestCase) {
        let va: Vec<u32> = tc.draw(generators::vecs(generators::integers::<u32>()));
        let vb: Vec<u32> = tc.draw(generators::vecs(generators::integers::<u32>()));
        let a = Splinter::from_iter(va);
        let b = Splinter::from_iter(vb);
        let union_card = (&a | &b).cardinality();
        let intersection_card = (&a & &b).cardinality();
        assert_eq!(
            union_card,
            a.cardinality() + b.cardinality() - intersection_card
        );
    }

    /// Cut decomposes into intersection + remainder: cut(a, b) returns a&b, leaves a-b.
    #[hegel::test]
    fn test_cut_decomposition(tc: hegel::TestCase) {
        let va: Vec<u32> = tc.draw(generators::vecs(generators::integers::<u32>()));
        let vb: Vec<u32> = tc.draw(generators::vecs(generators::integers::<u32>()));
        let mut a = Splinter::from_iter(va);
        let b = Splinter::from_iter(vb);
        let original_a = a.clone();
        let intersection = a.cut(&b);
        // a now holds the remainder (a - b)
        // intersection holds (a & b)
        // Verify: remainder | intersection == original_a
        assert_eq!(&a | &intersection, original_a);
        // Verify: remainder & intersection == empty (disjoint)
        assert_eq!(&a & &intersection, Splinter::EMPTY);
    }
}