finit 0.4.0

use crate::Set;
use crate::comparisons::{SetEq, SubsetOf};
use crate::operations::identity::{
    disjunctive_union_using_difference_and_union, intersection_using_double_difference,
};
use crate::operations::{
    Difference, DifferenceAssign, DisjunctiveUnionAssign, IntersectionAssign, Union, UnionAssign,
};
use std::{collections::BTreeMap, ops::Deref};

#[derive(Debug, Clone, PartialEq, Eq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
/// An extension of [`BTreeMap`] with easy representation of undefined key values.
///
/// This is a generalization of a [`BTreeMap`] which cannot represent the universal set of its domain in an easy way without having to define a specific value for every value possible of its key type.
///
/// For a similar structure that uses a [`std::collections::HashMap`] instead of a [`BTreeMap`], see [`super::WildcardHashMap`].
pub struct WildcardBTreeMap<Key: Ord + Eq + Clone, Value: Set> {
    wildcard_exceptions: BTreeMap<Key, Value>,
    wildcard_value: Box<Value>,
    rest_list: BTreeMap<Key, Value>,
}

impl<Key: Ord + Eq + Clone, Value: Set> WildcardBTreeMap<Key, Value> {
    pub fn new(wildcard_value: Value) -> Self {
        Self {
            wildcard_exceptions: BTreeMap::empty(),
            wildcard_value: Box::new(wildcard_value),
            rest_list: BTreeMap::empty(),
        }
    }
}

impl<Key: Ord + Eq + Clone, Value: Set<Empty = Value>> Set for WildcardBTreeMap<Key, Value> {
    type Empty = Self;

    fn is_empty(&self) -> bool {
        self.rest_list.is_empty() && self.wildcard_value.is_empty()
    }

    fn empty() -> Self::Empty {
        WildcardBTreeMap {
            wildcard_exceptions: BTreeMap::empty(),
            wildcard_value: Box::new(Value::empty()),
            rest_list: BTreeMap::empty(),
        }
    }
}

impl<Key: Ord + Eq + Clone, Value: Set<Empty = Value>> Default for WildcardBTreeMap<Key, Value> {
    fn default() -> Self {
        Self::empty()
    }
}

impl<Key: Ord + Eq + Clone, Value: Set<Empty = Value>> From<BTreeMap<Key, Value>>
    for WildcardBTreeMap<Key, Value>
{
    fn from(rest_list: BTreeMap<Key, Value>) -> Self {
        WildcardBTreeMap {
            rest_list,
            ..Default::default()
        }
    }
}

// WildcardList A <-> List B
impl<Key: Ord + Eq + Clone, Value: Set<Empty = Value>, OtherValue: Clone>
    UnionAssign<&BTreeMap<Key, OtherValue>> for WildcardBTreeMap<Key, Value>
where
    for<'a> Value: DifferenceAssign<&'a Value>
        + IntersectionAssign<&'a OtherValue>
        + UnionAssign<&'a OtherValue>,
    for<'a> OtherValue: DifferenceAssign<&'a Value>,
{
    fn union_assign(&mut self, rhs: &BTreeMap<Key, OtherValue>) {
        for (key, value) in rhs.iter() {
            //For each key, for the intersection that is covered by the wildcard and value, remove it from the exceptions for this key.
            //For the rest (that is not part of the intersection), add it to the rest list.
            self.wildcard_value.intersection_assign(value);

            let mut rest = value.clone();

            rest.difference_assign(&self.wildcard_value);

            if !self.wildcard_value.is_empty() {
                let mut remove: bool = false;
                if let Some(val) = self.wildcard_exceptions.get_mut(key) {
                    val.difference_assign(&self.wildcard_value);

                    remove = val.is_empty();
                };

                if remove {
                    self.wildcard_exceptions.remove(key);
                };
            }

            if !rest.is_empty() {
                self.rest_list
                    .entry(key.clone())
                    .or_insert_with(Value::empty)
                    .union_assign(&rest);
            }
        }
    }
}

impl<Key: Ord + Eq + Clone, Value: Set<Empty = Value>, OtherValue: Clone>
    Union<&BTreeMap<Key, OtherValue>> for WildcardBTreeMap<Key, Value>
where
    for<'a> Value: DifferenceAssign<&'a Value>
        + IntersectionAssign<&'a OtherValue>
        + UnionAssign<&'a OtherValue>,
    for<'a> OtherValue: DifferenceAssign<&'a Value>,
{
    type Output = Self;

    fn union(mut self, rhs: &BTreeMap<Key, OtherValue>) -> Self::Output {
        self.union_assign(rhs);
        self
    }
}

impl<Key: Ord + Eq + Clone, Value: Set<Empty = Value>, OtherValue: Clone>
    Union<BTreeMap<Key, OtherValue>> for WildcardBTreeMap<Key, Value>
where
    for<'a> Self: Union<&'a BTreeMap<Key, OtherValue>, Output = Self>,
{
    type Output = Self;

    fn union(self, rhs: BTreeMap<Key, OtherValue>) -> Self::Output {
        self.union(&rhs)
    }
}

impl<Key: Ord + Eq + Clone, Value: Set<Empty = Value>, OtherValue: Set<Empty = OtherValue>>
    DifferenceAssign<&BTreeMap<Key, OtherValue>> for WildcardBTreeMap<Key, Value>
where
    for<'a> Value: DifferenceAssign<&'a OtherValue>
        + IntersectionAssign<&'a OtherValue>
        + UnionAssign<&'a Value>,
{
    fn difference_assign(&mut self, rhs: &BTreeMap<Key, OtherValue>) {
        self.rest_list.difference_assign(rhs);

        for (key, value) in rhs.iter() {
            self.wildcard_value.intersection_assign(value);

            // Whatever intersection exists between the wildcard and the value of a key should be inserted as an exception on that key.
            if !self.wildcard_value.is_empty() {
                self.wildcard_exceptions
                    .entry(key.clone())
                    .or_insert_with(Value::empty)
                    .union_assign(&self.wildcard_value);
            }
        }
    }
}

impl<Key: Ord + Eq + Clone, Value: Set<Empty = Value>, OtherValue: Set<Empty = OtherValue>>
    Difference<&BTreeMap<Key, OtherValue>> for WildcardBTreeMap<Key, Value>
where
    for<'a> Value: DifferenceAssign<&'a OtherValue>
        + IntersectionAssign<&'a OtherValue>
        + UnionAssign<&'a Value>,
{
    type Output = Self;

    fn difference(mut self, rhs: &BTreeMap<Key, OtherValue>) -> Self::Output {
        self.difference_assign(rhs);
        self
    }
}

// WildcardList A <-> WildcardList B
impl<Key, Value, OtherValue> UnionAssign<&WildcardBTreeMap<Key, OtherValue>>
    for WildcardBTreeMap<Key, Value>
where
    Key: Ord + Eq + Clone,
    Value: Set<Empty = Value> + Clone,
    for<'a> Value: DifferenceAssign<&'a Value>
        + DifferenceAssign<&'a OtherValue>
        + UnionAssign<&'a OtherValue>,
    OtherValue: Set<Empty = OtherValue> + Clone,
    for<'a> OtherValue: DifferenceAssign<&'a Value> + DifferenceAssign<&'a OtherValue>,
    for<'a> BTreeMap<Key, Value>: UnionAssign<&'a BTreeMap<Key, OtherValue>>,
{
    fn union_assign(&mut self, rhs: &WildcardBTreeMap<Key, OtherValue>) {
        let mut cleaned_rhs_wildcard_exceptions = rhs.wildcard_exceptions.clone();

        /// This function removes covered exceptions from a wildcard value (and it's associated exceptions).
        fn remove_covered_values<Key, Value, OtherValue>(
            exceptions: &mut BTreeMap<Key, OtherValue>,
            wildcard_value: &Value,
            wildcard_exceptions: &BTreeMap<Key, Value>,
        ) where
            Key: Ord + Eq + Clone,
            Value: Set<Empty = Value> + Clone,
            for<'a> Value: DifferenceAssign<&'a Value>, // + DifferenceAssign<&'a OtherValue>,
            for<'a> OtherValue: DifferenceAssign<&'a Value>, // + DifferenceAssign<&'a OtherValue>,
        {
            for (key, other_exception) in exceptions.iter_mut() {
                if let Some(exception) = wildcard_exceptions.get(key) {
                    let mut wildcard_value = wildcard_value.clone();
                    wildcard_value.difference_assign(exception);
                    other_exception.difference_assign(&wildcard_value);
                } else {
                    other_exception.difference_assign(wildcard_value);
                };
            }

            crate::impls::btreemap::remove_empty_keys(exceptions);
        }

        // Remove exceptions in rhs covered by selfs wildcard.
        remove_covered_values(
            &mut cleaned_rhs_wildcard_exceptions,
            self.wildcard_value.as_ref(),
            &self.wildcard_exceptions,
        );
        cleaned_rhs_wildcard_exceptions.difference_assign(&self.rest_list);

        // Remove exceptions in self covered by rhs' wildcard.
        remove_covered_values(
            &mut self.wildcard_exceptions,
            rhs.wildcard_value.as_ref(),
            &rhs.wildcard_exceptions,
        );
        self.wildcard_exceptions.difference_assign(&rhs.rest_list);

        // Merge the exception lists and the wildcards.
        self.wildcard_exceptions
            .union_assign(&cleaned_rhs_wildcard_exceptions);
        self.wildcard_value.union_assign(rhs.wildcard_value.deref());

        // Merge rest lists.
        self.rest_list.union_assign(&rhs.rest_list);

        // Remove values in rest list covered by new wildcard.
        remove_covered_values(
            &mut self.rest_list,
            self.wildcard_value.as_ref(),
            &self.wildcard_exceptions,
        );
    }
}

impl<Key, Value, OtherValue> Union<&WildcardBTreeMap<Key, OtherValue>>
    for WildcardBTreeMap<Key, Value>
where
    Key: Ord + Eq + Clone,
    Value: Set<Empty = Value> + Clone,
    for<'a> Value: DifferenceAssign<&'a Value>
        + DifferenceAssign<&'a OtherValue>
        + UnionAssign<&'a OtherValue>,
    OtherValue: Set<Empty = OtherValue> + Clone,
    for<'a> OtherValue: DifferenceAssign<&'a Value> + DifferenceAssign<&'a OtherValue>,
    for<'a> BTreeMap<Key, Value>: UnionAssign<&'a BTreeMap<Key, OtherValue>>,
{
    type Output = Self;

    fn union(mut self, rhs: &WildcardBTreeMap<Key, OtherValue>) -> Self::Output {
        self.union_assign(rhs);
        self
    }
}

impl<Key, Value, OtherValue> Union<WildcardBTreeMap<Key, OtherValue>>
    for WildcardBTreeMap<Key, Value>
where
    Key: Ord + Eq + Clone,
    Value: Set<Empty = Value> + Clone,
    OtherValue: Set<Empty = OtherValue> + Clone,
    for<'a> Self: Union<&'a WildcardBTreeMap<Key, OtherValue>, Output = Self>,
{
    type Output = Self;

    fn union(self, rhs: WildcardBTreeMap<Key, OtherValue>) -> Self::Output {
        self.union(&rhs)
    }
}

impl<Key, Value, OtherValue> DifferenceAssign<&WildcardBTreeMap<Key, OtherValue>>
    for WildcardBTreeMap<Key, Value>
where
    Key: Ord + Eq + Clone,
    Value: Set<Empty = Value> + Clone,
    for<'a> Value: DifferenceAssign<&'a Value>
        + DifferenceAssign<&'a OtherValue>
        + IntersectionAssign<&'a OtherValue>
        + UnionAssign<&'a OtherValue>
        + UnionAssign<&'a Value>,
    OtherValue: Set<Empty = OtherValue> + Clone,
    for<'a> OtherValue: IntersectionAssign<&'a Value>,
{
    fn difference_assign(&mut self, rhs: &WildcardBTreeMap<Key, OtherValue>) {
        //If exception exists for X key, that value should not be removed for that key.
        //That means, if there is an intersection between that exception and the wildcard value, it should be added to the rest list.
        for (key, other_exception) in rhs.wildcard_exceptions.iter() {
            let mut value = self.wildcard_value.deref().clone();

            if let Some(exception) = self.wildcard_exceptions.get(key) {
                value.difference_assign(exception);
            }

            value.intersection_assign(other_exception);

            if value.is_empty() {
                continue;
            }

            if let Some(rest_value) = self.rest_list.get_mut(key) {
                rest_value.union_assign(&value);
            } else {
                self.rest_list.insert(key.clone(), value);
            }
        }
        //Remove rhs wildcard from self wildcard.
        self.wildcard_value
            .difference_assign(rhs.wildcard_value.as_ref());

        // If any rest list items in rhs intersect with the self wildcard, add them to the exceptions.
        // Subtract any rest list items in self with rhs.

        for (key, value) in rhs.rest_list.iter() {
            let mut value = value.clone();

            value.intersection_assign(&self.wildcard_value);

            if value.is_empty() {
                continue;
            }

            self.wildcard_exceptions
                .entry(key.clone())
                .or_insert_with(Value::empty)
                .union_assign(&value);
        }

        self.rest_list.difference_assign(&rhs.rest_list);
    }
}

impl<Key, Value, OtherValue> Difference<&WildcardBTreeMap<Key, OtherValue>>
    for WildcardBTreeMap<Key, Value>
where
    Key: Ord + Eq + Clone,
    Value: Set<Empty = Value> + Clone,
    OtherValue: Set<Empty = OtherValue> + Clone,
    for<'a> Self: DifferenceAssign<&'a WildcardBTreeMap<Key, OtherValue>>,
{
    type Output = Self;

    fn difference(mut self, rhs: &WildcardBTreeMap<Key, OtherValue>) -> Self::Output {
        self.difference_assign(rhs);
        self
    }
}

impl<Key, Value, OtherValue> Difference<WildcardBTreeMap<Key, OtherValue>>
    for WildcardBTreeMap<Key, Value>
where
    Key: Ord + Eq + Clone,
    Value: Set<Empty = Value> + Clone,
    OtherValue: Set<Empty = OtherValue> + Clone,
    for<'a> Self: Difference<&'a WildcardBTreeMap<Key, OtherValue>, Output = Self>,
{
    type Output = Self;

    fn difference(self, rhs: WildcardBTreeMap<Key, OtherValue>) -> Self::Output {
        self.difference(&rhs)
    }
}

impl<Key, Value, OtherValue> IntersectionAssign<&WildcardBTreeMap<Key, OtherValue>>
    for WildcardBTreeMap<Key, Value>
where
    Key: Ord + Eq + Clone,
    Value: Set<Empty = Value> + Clone,
    OtherValue: Set<Empty = OtherValue> + Clone,
    for<'a> Self: Difference<&'a WildcardBTreeMap<Key, OtherValue>, Output = Self>,
    Self: Difference<Self, Output = Self>,
{
    fn intersection_assign(&mut self, rhs: &WildcardBTreeMap<Key, OtherValue>) {
        *self = intersection_using_double_difference(self.clone(), rhs);
    }
}

impl<Key, Value, OtherValue> IntersectionAssign<WildcardBTreeMap<Key, OtherValue>>
    for WildcardBTreeMap<Key, Value>
where
    Key: Ord + Eq + Clone,
    Value: Set<Empty = Value> + Clone,
    OtherValue: Set<Empty = OtherValue> + Clone,
    for<'a> Self: IntersectionAssign<&'a WildcardBTreeMap<Key, OtherValue>>,
{
    fn intersection_assign(&mut self, rhs: WildcardBTreeMap<Key, OtherValue>) {
        self.intersection_assign(&rhs);
    }
}

impl<Key, Value, OtherValue> DisjunctiveUnionAssign<&WildcardBTreeMap<Key, OtherValue>>
    for WildcardBTreeMap<Key, Value>
where
    Key: Ord + Eq + Clone,
    Value: Set<Empty = Value> + Clone,
    OtherValue: Set<Empty = OtherValue> + Clone,
    Self: DisjunctiveUnionAssign<WildcardBTreeMap<Key, OtherValue>>,
    WildcardBTreeMap<Key, OtherValue>: Clone,
{
    fn disjunctive_union_assign(&mut self, rhs: &WildcardBTreeMap<Key, OtherValue>) {
        self.disjunctive_union_assign(rhs.clone());
    }
}

impl<Key, Value, OtherValue> DisjunctiveUnionAssign<WildcardBTreeMap<Key, OtherValue>>
    for WildcardBTreeMap<Key, Value>
where
    Key: Ord + Eq + Clone,
    Value: Set<Empty = Value> + Clone,
    OtherValue: Set<Empty = OtherValue> + Clone,
    Self: Difference<WildcardBTreeMap<Key, OtherValue>, Output = Self> + Union<Self, Output = Self>,
    WildcardBTreeMap<Key, OtherValue>: Difference<Self, Output = Self>,
{
    fn disjunctive_union_assign(&mut self, rhs: WildcardBTreeMap<Key, OtherValue>) {
        *self = disjunctive_union_using_difference_and_union(self.clone(), rhs);
    }
}

impl<Key: Ord + Eq + Clone, Value: Set + SetEq<OtherValue>, OtherValue: Set>
    SetEq<WildcardBTreeMap<Key, OtherValue>> for WildcardBTreeMap<Key, Value>
{
    fn set_eq(&self, rhs: &WildcardBTreeMap<Key, OtherValue>) -> bool {
        self.wildcard_value.set_eq(rhs.wildcard_value.as_ref())
            && self.wildcard_exceptions.set_eq(&rhs.wildcard_exceptions)
            && self.rest_list.set_eq(&rhs.rest_list)
    }
}

impl<Key: Ord + Eq + Clone, Value: Set + SetEq<OtherValue>, OtherValue: Set>
    SetEq<BTreeMap<Key, OtherValue>> for WildcardBTreeMap<Key, Value>
{
    fn set_eq(&self, rhs: &BTreeMap<Key, OtherValue>) -> bool {
        self.wildcard_value.is_empty() && self.rest_list.set_eq(rhs)
    }
}

impl<Key: Ord + Eq + Clone, Value: Set + SubsetOf<OtherValue>, OtherValue: Set>
    SubsetOf<WildcardBTreeMap<Key, OtherValue>> for WildcardBTreeMap<Key, Value>
where
    for<'a> Value: DifferenceAssign<&'a Value>
        + DifferenceAssign<&'a OtherValue>
        + UnionAssign<&'a Value>
        + IntersectionAssign<&'a OtherValue>
        + Clone,
{
    fn subset_of(&self, rhs: &WildcardBTreeMap<Key, OtherValue>) -> bool {
        // The wildcard itself must be a subset
        if !self.wildcard_value.subset_of(rhs.wildcard_value.as_ref()) {
            return false;
        }

        let mut checked_keys = std::collections::BTreeSet::new();

        for key in rhs.wildcard_exceptions.keys().chain(self.rest_list.keys()) {
            if checked_keys.contains(key) {
                continue;
            }
            checked_keys.insert(key);

            let mut a = self.wildcard_value.deref().clone();
            if let Some(exc) = self.wildcard_exceptions.get(key) {
                a.difference_assign(exc);
            }
            if let Some(rest) = self.rest_list.get(key) {
                a.union_assign(rest);
            }

            if let Some(rhs_rest) = rhs.rest_list.get(key) {
                a.difference_assign(rhs_rest);
            }

            let mut a_minus_wb = a.clone();
            a_minus_wb.difference_assign(rhs.wildcard_value.as_ref());
            if !a_minus_wb.is_empty() {
                return false;
            }

            if let Some(rhs_exc) = rhs.wildcard_exceptions.get(key) {
                a.intersection_assign(rhs_exc);
                if !a.is_empty() {
                    return false;
                }
            }
        }

        true
    }
}

impl<Key: Ord + Eq + Clone, Value: Set + SubsetOf<OtherValue>, OtherValue: Set>
    SubsetOf<BTreeMap<Key, OtherValue>> for WildcardBTreeMap<Key, Value>
{
    fn subset_of(&self, rhs: &BTreeMap<Key, OtherValue>) -> bool {
        if !self.wildcard_value.is_empty() {
            return false;
        }

        self.rest_list.subset_of(rhs)
    }
}

#[cfg(test)]
mod tests {
    use std::fmt::Debug;

    use rstest::*;

    #[allow(unused_imports)]
    use super::*;

    use maplit::btreemap;

    #[rstest]
    // WildcardList A <-> List B
    #[case(WildcardBTreeMap {
        wildcard_value: Box::new(false),
        wildcard_exceptions: btreemap! {},
        rest_list: btreemap! {
            0 => true,
        },
    }, btreemap! {
        1 => true,
    }, WildcardBTreeMap {
        wildcard_value: Box::new(false),
        wildcard_exceptions: btreemap! {},
        rest_list: btreemap! {
            0 => true,
            1 => true,
        }
    })]
    #[case(WildcardBTreeMap {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {},
        rest_list: btreemap! {},
    }, btreemap! {
        1 => true,
    }, WildcardBTreeMap {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {},
        rest_list: btreemap! {}
    })]
    #[case(WildcardBTreeMap {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {
            1 => true
        },
        rest_list: btreemap! {},
    }, btreemap! {
        1 => true,
    }, WildcardBTreeMap {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {},
        rest_list: btreemap! {}
    })]
    #[case(WildcardBTreeMap {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {
            1 => true,
            2 => true,
        },
        rest_list: btreemap! {},
    }, btreemap! {
        1 => true,
    }, WildcardBTreeMap {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {
            2 => true,
        },
        rest_list: btreemap! {}
    })]
    // WildcardList A <-> WildcardList B
    #[case(WildcardBTreeMap {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {
            2 => true,
        },
        rest_list: btreemap! {},
    }, WildcardBTreeMap {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {
            1 => true,
        },
        rest_list: btreemap! {},
    }, WildcardBTreeMap {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {},
        rest_list: btreemap! {}
    })]
    #[case(WildcardBTreeMap {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {
            1 => true,
            2 => true,
        },
        rest_list: btreemap! {},
    }, WildcardBTreeMap {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {
            1 => true,
        },
        rest_list: btreemap! {},
    }, WildcardBTreeMap {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {
            1 => true,
        },
        rest_list: btreemap! {}
    })]
    #[case(WildcardBTreeMap {
        wildcard_value: Box::new(btreemap! {
            1 => true
        }),
        wildcard_exceptions: btreemap! {
            2 => btreemap! {
                1 => true
            }
        },
        rest_list: btreemap! {},
    }, WildcardBTreeMap {
        wildcard_value: Box::new(btreemap! {
            2 => true
        }),
        wildcard_exceptions: btreemap! {
            1 => btreemap! {
                2 => true
            }
        },
        rest_list: btreemap! {
            2 => btreemap! {
                1 => true
            }
        },
    }, WildcardBTreeMap {
        wildcard_value: Box::new(btreemap! {
            1 => true,
            2 => true
        }),
        wildcard_exceptions: btreemap! {
            1 => btreemap! {
                2 => true
            }
        },
        rest_list: btreemap! {}
    })]
    fn union_list_tests<I1, I2, R>(#[case] mut list1: I1, #[case] list2: I2, #[case] result: R)
    where
        I1: PartialEq<R> + Debug,
        I2: Debug,
        R: Debug,
        for<'a> I1: UnionAssign<&'a I2>,
    {
        list1.union_assign(&list2);

        assert_eq!(list1, result);
    }

    #[rstest]
    #[case(WildcardBTreeMap {
        wildcard_value: Box::new(false),
        wildcard_exceptions: btreemap! {},
        rest_list: btreemap! {
            0 => true,
        },
    }, btreemap! {
        1 => true,
    }, WildcardBTreeMap {
        wildcard_value: Box::new(false),
        wildcard_exceptions: btreemap! {},
        rest_list: btreemap! {
            0 => true,
        }
    })]
    #[case(WildcardBTreeMap {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {},
        rest_list: btreemap! {},
    }, btreemap! {
        1 => true,
    }, WildcardBTreeMap {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {
            1 => true,
        },
        rest_list: btreemap! {}
    })]
    #[case(WildcardBTreeMap {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {
            1 => true
        },
        rest_list: btreemap! {},
    }, btreemap! {
        1 => true,
    }, WildcardBTreeMap {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {
            1 => true,
        },
        rest_list: btreemap! {}
    })]
    #[case(WildcardBTreeMap {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {
            2 => true,
        },
        rest_list: btreemap! {
        },
    }, btreemap! {
        1 => true,
    }, WildcardBTreeMap {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {
            2 => true,
            1 => true,
        },
        rest_list: btreemap! {}
    })]
    // WildcardList A <-> WildcardList B
    #[case(WildcardBTreeMap::<i32, bool> {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {},
        rest_list: btreemap! {},
    }, WildcardBTreeMap {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {},
        rest_list: btreemap! {},
    }, WildcardBTreeMap {
        wildcard_value: Box::new(false),
        wildcard_exceptions: btreemap! {},
        rest_list: btreemap! {}
    })]
    #[case(WildcardBTreeMap {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {},
        rest_list: btreemap! {},
    }, WildcardBTreeMap {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {
            1 => true,
        },
        rest_list: btreemap! {},
    }, WildcardBTreeMap {
        wildcard_value: Box::new(false),
        wildcard_exceptions: btreemap! {},
        rest_list: btreemap! {
            1 => true,
        }
    })]
    #[case(WildcardBTreeMap {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {},
        rest_list: btreemap! {},
    }, WildcardBTreeMap {
        wildcard_value: Box::new(false),
        wildcard_exceptions: btreemap! {},
        rest_list: btreemap! {
            1 => true,
        },
    }, WildcardBTreeMap {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {
            1 => true,
        },
        rest_list: btreemap! {}
    })]
    #[case(WildcardBTreeMap {
        wildcard_value: Box::new(btreemap! {
            1 => true,
            2 => true
        }),
        wildcard_exceptions: btreemap! {},
        rest_list: btreemap! {},
    }, WildcardBTreeMap {
        wildcard_value: Box::new(btreemap! {
            1 => true
        }),
        wildcard_exceptions: btreemap! {
            2 => btreemap! {
                1 => true
            }
        },
        rest_list: btreemap! {},
    }, WildcardBTreeMap {
        wildcard_value: Box::new(btreemap! {
            2 => true
        }),
        wildcard_exceptions: btreemap! {},
        rest_list: btreemap! {
            2 => btreemap! {
                1 => true
            }
        }
    })]
    fn difference_list_tests<I1, I2, R>(#[case] mut list1: I1, #[case] list2: I2, #[case] result: R)
    where
        I1: PartialEq<R> + Debug,
        I2: Debug,
        R: Debug,
        for<'a> I1: DifferenceAssign<&'a I2>,
    {
        list1.difference_assign(&list2);

        assert_eq!(list1, result);
    }

    #[test]
    fn test_add() {
        let tree_1 = btreemap! {
            1 => WildcardBTreeMap {
                rest_list: btreemap! {},
                wildcard_exceptions: btreemap! {},
                wildcard_value: Box::new(btreemap! {
                    15 => true,
                })
            }
        };

        let tree_2 = btreemap! {
            1 => btreemap! {
                5 => btreemap! {
                    15 => true,
                    5 => true,
                },
            },
        };

        let mut tree_1_minus_2 = tree_1.clone();
        tree_1_minus_2.difference_assign(&tree_2);

        let result = btreemap! {
          1 => WildcardBTreeMap {
            rest_list: btreemap! {},
            wildcard_exceptions: btreemap! {
                5 => btreemap! {
                    15 => true,
                },
            },
            wildcard_value: Box::new(btreemap! {
                15 => true,
            }),
          }
        };

        assert_eq!(tree_1_minus_2, result);

        tree_1_minus_2.union_assign(&tree_2);
        //Does not equal tree_1 because 1.5.5 has been added.
        assert_ne!(tree_1, tree_1_minus_2);
    }

    #[rstest]
    #[case(WildcardBTreeMap::<i32, bool> {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {},
        rest_list: btreemap! {},
    }, WildcardBTreeMap {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {},
        rest_list: btreemap! {},
    }, WildcardBTreeMap {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {},
        rest_list: btreemap! {}
    })]
    #[case(WildcardBTreeMap {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {
            1 => true,
        },
        rest_list: btreemap! {},
    }, WildcardBTreeMap {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {},
        rest_list: btreemap! {},
    }, WildcardBTreeMap {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {
            1 => true,
        },
        rest_list: btreemap! {}
    })]
    #[case(WildcardBTreeMap {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {},
        rest_list: btreemap! {
            1 => true,
        },
    }, WildcardBTreeMap {
        wildcard_value: Box::new(false),
        wildcard_exceptions: btreemap! {},
        rest_list: btreemap! {
            1 => true,
        },
    }, WildcardBTreeMap {
        wildcard_value: Box::new(false),
        wildcard_exceptions: btreemap! {},
        rest_list: btreemap! {
            1 => true,
        }
    })]
    fn intersection_list_tests<I1, I2, R>(
        #[case] mut list1: I1,
        #[case] list2: I2,
        #[case] result: R,
    ) where
        I1: PartialEq<R> + Debug,
        I2: Debug,
        R: Debug,
        for<'a> I1: IntersectionAssign<&'a I2>,
    {
        list1.intersection_assign(&list2);
        assert_eq!(list1, result);
    }

    #[rstest]
    #[case(WildcardBTreeMap::<i32, bool> {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {},
        rest_list: btreemap! {},
    }, WildcardBTreeMap {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {},
        rest_list: btreemap! {},
    }, WildcardBTreeMap {
        wildcard_value: Box::new(false),
        wildcard_exceptions: btreemap! {},
        rest_list: btreemap! {}
    })]
    #[case(WildcardBTreeMap {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {
            1 => true,
        },
        rest_list: btreemap! {},
    }, WildcardBTreeMap {
        wildcard_value: Box::new(false),
        wildcard_exceptions: btreemap! {},
        rest_list: btreemap! {
            1 => true,
        },
    }, WildcardBTreeMap {
        wildcard_value: Box::new(true),
        wildcard_exceptions: btreemap! {},
        rest_list: btreemap! {}
    })]
    fn disjunctive_union_list_tests<I1, I2, R>(
        #[case] mut list1: I1,
        #[case] list2: I2,
        #[case] result: R,
    ) where
        I1: PartialEq<R> + Debug,
        I2: Debug,
        R: Debug,
        I1: DisjunctiveUnionAssign<I2>,
    {
        list1.disjunctive_union_assign(list2);
        assert_eq!(list1, result);
    }
}