superset_map 0.3.6

extern crate alloc;
use crate::{
    SetOrd, SupersetMap,
    zfc::{BoundedCardinality, Cardinality, Set},
};
use alloc::collections::btree_map::{self, IntoKeys, Keys};
use core::{
    borrow::Borrow,
    hash::{Hash, Hasher},
    iter::FusedIterator,
    ops::{BitAnd, BitOr, Bound, RangeBounds},
};
/// A lazy iterator producing elements in the intersection of `SupersetSet`s.
///
/// This `struct` is created by [`SupersetSet::intersection`].
#[expect(missing_debug_implementations, reason = "Iter does not, so we do not")]
#[derive(Clone)]
pub struct Intersection<'a, T> {
    /// Iterator for the first `SupersetSet`.
    iter_1: Iter<'a, T>,
    /// Iterator for the second `SupersetSet`.
    iter_2: Iter<'a, T>,
    /// Previous value iterated from `iter_1`.
    /// `prev_1` and `prev_2` will never both be `Some`.
    prev_1: Option<&'a T>,
    /// Previous value iterated from `iter_2`.
    prev_2: Option<&'a T>,
}
impl<T> FusedIterator for Intersection<'_, T> where T: SetOrd {}
impl<'a, T> Iterator for Intersection<'a, T>
where
    T: SetOrd,
{
    type Item = &'a T;
    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        loop {
            if let Some(prev1) = self.prev_1 {
                if let Some(cur2) = self.iter_2.next() {
                    if prev1 <= cur2 {
                        self.prev_1 = None;
                        self.prev_2 = Some(cur2);
                        if prev1.is_subset(cur2) {
                            return Some(prev1);
                        }
                    } else if cur2.is_proper_subset(prev1) {
                        return Some(cur2);
                    } else {
                        // Do nothing.
                    }
                } else {
                    self.prev_1 = None;
                    return None;
                }
            } else if let Some(prev2) = self.prev_2 {
                if let Some(cur1) = self.iter_1.next() {
                    if prev2 <= cur1 {
                        self.prev_2 = None;
                        self.prev_1 = Some(cur1);
                        if prev2.is_subset(cur1) {
                            return Some(prev2);
                        }
                    } else if cur1.is_proper_subset(prev2) {
                        return Some(cur1);
                    } else {
                        // Do nothing.
                    }
                } else {
                    self.prev_1 = None;
                    return None;
                }
            } else if let Some(cur1) = self.iter_1.next() {
                if let Some(cur2) = self.iter_2.next() {
                    if cur1 <= cur2 {
                        self.prev_2 = Some(cur2);
                        if cur1.is_subset(cur2) {
                            return Some(cur1);
                        }
                    } else if cur2.is_proper_subset(cur1) {
                        self.prev_1 = Some(cur1);
                        return Some(cur2);
                    } else {
                        // Do nothing.
                    }
                } else {
                    return None;
                }
            } else {
                return None;
            }
        }
    }
}
/// An owning iterator over the items of a `SupersetSet`.
///
/// This `struct` is created by [`SupersetSet::into_iter`] (provided by [`IntoIterator`]).
#[derive(Debug)]
pub struct IntoIter<T> {
    /// Iterator of the values in a `SupersetSet`.
    iter: IntoKeys<T, ()>,
}
impl<T> Default for IntoIter<T> {
    #[inline]
    fn default() -> Self {
        Self {
            iter: IntoKeys::default(),
        }
    }
}
impl<T> DoubleEndedIterator for IntoIter<T> {
    #[inline]
    fn next_back(&mut self) -> Option<Self::Item> {
        self.iter.next_back()
    }
}
impl<T> ExactSizeIterator for IntoIter<T> {
    #[inline]
    fn len(&self) -> usize {
        self.iter.len()
    }
}
impl<T> FusedIterator for IntoIter<T> {}
impl<T> Iterator for IntoIter<T> {
    type Item = T;
    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        self.iter.next()
    }
}
/// An iterator over the items of a `SupersetSet`.
///
/// This `struct` is created by [`SupersetSet::iter`].
#[derive(Clone, Debug)]
pub struct Iter<'a, T> {
    /// Iterator of the values in a `SupersetSet`.
    iter: Keys<'a, T, ()>,
}
impl<T> Default for Iter<'_, T> {
    #[inline]
    fn default() -> Self {
        Self {
            iter: Keys::default(),
        }
    }
}
impl<T> DoubleEndedIterator for Iter<'_, T> {
    #[inline]
    fn next_back(&mut self) -> Option<Self::Item> {
        self.iter.next_back()
    }
}
impl<T> ExactSizeIterator for Iter<'_, T> {
    #[inline]
    fn len(&self) -> usize {
        self.iter.len()
    }
}
impl<T> FusedIterator for Iter<'_, T> {}
impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;
    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        self.iter.next()
    }
}
/// An iterator over a sub-range of items in a `SupersetSet`.
///
/// This `struct` is created by [`SupersetSet::range`].
#[derive(Clone, Debug)]
pub struct Range<'a, T> {
    /// Range iterator for a `SupersetSet`.
    iter: btree_map::Range<'a, T, ()>,
}
impl<T> Default for Range<'_, T> {
    #[inline]
    fn default() -> Self {
        Self {
            iter: btree_map::Range::default(),
        }
    }
}
impl<T> DoubleEndedIterator for Range<'_, T> {
    #[inline]
    fn next_back(&mut self) -> Option<Self::Item> {
        self.iter.next_back().map(|(key, &())| key)
    }
}
impl<T> FusedIterator for Range<'_, T> {}
impl<'a, T> Iterator for Range<'a, T> {
    type Item = &'a T;
    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        self.iter.next().map(|(key, &())| key)
    }
}
/// A minimal collection of `T`s.
///
/// Internally it is based on a [`SupersetMap`]. When a `T` is [`SupersetSet::insert`]ed, it won't actually be
/// inserted unless there isn't a `T` already in the set that is a superset of it. In such event, all `T`s that
/// are subsets of the to-be-inserted `T` are removed before inserting the `T`.
///
/// Note this can have quite good performance due to the fact that a single search is necessary to detect if
/// insertion should occur; furthermore since all subsets occur immediately before where the value will be inserted,
/// a simple linear scan is sufficient to remove subsets avoiding the need to search the entire set.
#[derive(Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]
pub struct SupersetSet<T> {
    /// Collection of `T`s.
    map: SupersetMap<T, ()>,
}
impl<T> SupersetSet<T> {
    /// Read [`BTreeSet::clear`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.clear).
    #[inline]
    pub fn clear(&mut self) {
        self.map.clear();
    }
    /// Read [`BTreeSet::is_empty`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.is_empty).
    #[inline]
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.map.is_empty()
    }
    /// Read [`BTreeSet::iter`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.iter).
    #[inline]
    #[must_use]
    pub fn iter(&self) -> Iter<'_, T> {
        Iter {
            iter: self.map.keys(),
        }
    }
    /// Read [`BTreeSet::len`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.len).
    #[inline]
    #[must_use]
    pub fn len(&self) -> usize {
        self.map.len()
    }
    /// Makes a new, empty `SupersetSet`.
    /// Does not allocate anything on its own.
    #[inline]
    #[must_use]
    pub const fn new() -> Self {
        Self {
            map: SupersetMap::new(),
        }
    }
}
impl<T> SupersetSet<T>
where
    T: Ord,
{
    /// Read [`BTreeSet::contains`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.contains).
    #[expect(clippy::same_name_method, reason = "consistent with BTreeSet")]
    #[inline]
    pub fn contains<Q>(&self, value: &Q) -> bool
    where
        T: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.map.contains_key(value)
    }
    /// Read [`BTreeSet::first`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.first).
    #[inline]
    #[must_use]
    pub fn first(&self) -> Option<&T> {
        self.map.first_key_value().map(|(key, &())| key)
    }
    /// Read [`BTreeSet::get`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.get).
    #[inline]
    pub fn get<Q>(&self, value: &Q) -> Option<&T>
    where
        T: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.map.get_key_value(value).map(|(key, &())| key)
    }
    /// Read [`BTreeSet::last`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.last).
    #[inline]
    #[must_use]
    pub fn last(&self) -> Option<&T> {
        self.map.last_key_value().map(|(key, &())| key)
    }
    /// Read [`BTreeSet::pop_first`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.pop_first).
    #[inline]
    pub fn pop_first(&mut self) -> Option<T> {
        self.map.pop_first().map(|(key, ())| key)
    }
    /// Read [`BTreeSet::pop_last`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.pop_last).
    #[inline]
    pub fn pop_last(&mut self) -> Option<T> {
        self.map.pop_last().map(|(key, ())| key)
    }
    /// Read [`BTreeSet::range`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.range).
    #[inline]
    pub fn range<K, R>(&self, range: R) -> Range<'_, T>
    where
        T: Borrow<K>,
        K: Ord + ?Sized,
        R: RangeBounds<K>,
    {
        Range {
            iter: self.map.range(range),
        }
    }
    /// Read [`BTreeSet::remove`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.remove).
    #[inline]
    pub fn remove<Q>(&mut self, value: &Q) -> bool
    where
        T: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.map.remove(value).is_some()
    }
    /// Read [`BTreeSet::split_off`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.split_off).
    #[inline]
    #[must_use]
    pub fn split_off<Q>(&mut self, value: &Q) -> Self
    where
        T: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        Self {
            map: self.map.split_off(value),
        }
    }
    /// Read [`BTreeSet::take`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.take).
    #[inline]
    pub fn take<Q>(&mut self, value: &Q) -> Option<T>
    where
        T: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.map.remove_entry(value).map(|(key, ())| key)
    }
}
impl<T> SupersetSet<T>
where
    T: SetOrd,
{
    /// Moves all elements from `other` into `self`, consuming `other`.
    /// If a value from `other` is a proper superset of a value in `self`, the respective value from `self` will be removed before inserting
    /// the value from `other`.
    /// If a value from `other` is a subset of a value in `self`, it won't be inserted.
    #[inline]
    pub fn append(&mut self, other: Self) {
        self.map.append(other.map);
    }
    /// Returns `true` if the set contains a proper subset of the specified value.
    /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type.
    #[inline]
    pub fn contains_proper_subset<Q>(&self, value: &Q) -> bool
    where
        T: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        self.map.contains_proper_subset(value)
    }
    /// Returns `true` if the set contains a proper superset of the specified value.
    /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type.
    #[inline]
    pub fn contains_proper_superset<Q>(&self, value: &Q) -> bool
    where
        T: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        self.map.contains_proper_superset(value)
    }
    /// Returns `true` if the set contains a subset of the specified value.
    /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type.
    #[inline]
    pub fn contains_subset<Q>(&self, value: &Q) -> bool
    where
        T: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        self.map.contains_subset(value)
    }
    /// Returns `true` if the set contains a superset of the specified value.
    /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type.
    #[inline]
    pub fn contains_superset<Q>(&self, value: &Q) -> bool
    where
        T: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        self.map.contains_superset(value)
    }
    /// Returns a reference to the value corresponding to the greatest proper subset of the passed value.
    /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type.
    #[inline]
    pub fn get_greatest_proper_subset<Q>(&self, value: &Q) -> Option<&T>
    where
        T: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        self.map
            .get_greatest_proper_subset_key_value(value)
            .map(|(key, &())| key)
    }
    /// Returns a reference to the value corresponding to the greatest subset of the passed value.
    /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type.
    #[inline]
    pub fn get_greatest_subset<Q>(&self, value: &Q) -> Option<&T>
    where
        T: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        self.map
            .get_greatest_subset_key_value(value)
            .map(|(key, &())| key)
    }
    /// Returns a reference to the value corresponding to the least proper superset of the passed value.
    /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type.
    #[inline]
    pub fn get_least_proper_superset<Q>(&self, value: &Q) -> Option<&T>
    where
        T: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        self.map
            .get_least_proper_superset_key_value(value)
            .map(|(key, &())| key)
    }
    /// Returns a reference to the value corresponding to the least superset of the passed value.
    /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type.
    #[inline]
    pub fn get_least_superset<Q>(&self, value: &Q) -> Option<&T>
    where
        T: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        self.map
            .get_least_superset_key_value(value)
            .map(|(key, &())| key)
    }
    /// `value` is inserted iff there doesn't already
    /// exist a `T` that is a superset of `value`.
    /// In the event `value` will be inserted, all `T`s
    /// where the `T` is a subset of `value` are first removed before
    /// inserting.
    #[inline]
    pub fn insert(&mut self, value: T) -> bool {
        self.map.insert(value, ())
    }
    /// Visits the elements representing the intersection, i.e., the subsets of elements that are both in `self` and `other`, in ascending order.
    /// For example if `self` contains a sequence of sets each of which being a subset of the same set in `other`, then only the subsets in `self` will be iterated.
    #[inline]
    #[must_use]
    pub fn intersection<'a>(&'a self, other: &'a Self) -> Intersection<'a, T> {
        Intersection {
            iter_1: self.into_iter(),
            iter_2: other.into_iter(),
            prev_1: None,
            prev_2: None,
        }
    }
    /// Removes the greatest proper subset of value from the set, returning the value if one existed.
    /// The value may be any borrowed form of the set's value type, but the ordering on the borrowed form must match the ordering on the value type.
    #[inline]
    pub fn remove_greatest_proper_subset<Q>(&mut self, value: &Q) -> Option<T>
    where
        T: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        self.map
            .remove_greatest_proper_subset(value)
            .map(|(key, ())| key)
    }
    /// Removes the greatest subset of value from the set, returning the value if one existed.
    /// The value may be any borrowed form of the set's value type, but the ordering on the borrowed form must match the ordering on the value type.
    #[inline]
    pub fn remove_greatest_subset<Q>(&mut self, value: &Q) -> Option<T>
    where
        T: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        self.map.remove_greatest_subset(value).map(|(key, ())| key)
    }
    /// Removes the least proper superset of value from the set, returning the value if one existed.
    /// The value may be any borrowed form of the set's value type, but the ordering on the borrowed form must match the ordering on the value type.
    #[inline]
    pub fn remove_least_proper_superset<Q>(&mut self, value: &Q) -> Option<T>
    where
        T: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        self.map
            .remove_least_proper_superset(value)
            .map(|(key, ())| key)
    }
    /// Removes the least superset of value from the set, returning the value if one existed.
    /// The value may be any borrowed form of the set's value type, but the ordering on the borrowed form must match the ordering on the value type.
    #[inline]
    pub fn remove_least_superset<Q>(&mut self, value: &Q) -> Option<T>
    where
        T: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        self.map.remove_least_superset(value).map(|(key, ())| key)
    }
    /// Removes all proper subsets of value from the set, returning the count removed.
    /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type.
    /// # Overflow Behavior
    ///
    /// The method does no guarding against overflows, so the removal of more than `usize::MAX` elements either produces the wrong result or panics. If debug assertions are enabled, a panic is guaranteed.
    /// # Panics
    ///
    /// This function might panic if the number of elements removed is greater than `usize::MAX`.
    #[inline]
    pub fn remove_proper_subsets<Q>(&mut self, value: &Q) -> usize
    where
        T: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        self.map.remove_proper_subsets(value)
    }
    /// Removes all proper supersets of value from the set, returning the count removed.
    /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type.
    /// # Overflow Behavior
    ///
    /// The method does no guarding against overflows, so the removal of more than `usize::MAX` elements either produces the wrong result or panics. If debug assertions are enabled, a panic is guaranteed.
    /// # Panics
    ///
    /// This function might panic if the number of elements removed is greater than `usize::MAX`.
    #[inline]
    pub fn remove_proper_supersets<Q>(&mut self, value: &Q) -> usize
    where
        T: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        self.map.remove_proper_supersets(value)
    }
    /// Removes all subsets of value from the set, returning the count removed.
    /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type.
    /// # Overflow Behavior
    ///
    /// The method does no guarding against overflows, so the removal of more than `usize::MAX` elements either produces the wrong result or panics. If debug assertions are enabled, a panic is guaranteed.
    /// # Panics
    ///
    /// This function might panic if the number of elements removed is greater than `usize::MAX`.
    #[inline]
    pub fn remove_subsets<Q>(&mut self, value: &Q) -> usize
    where
        T: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        self.map.remove_subsets(value)
    }
    /// Removes all supersets of value from the set, returning the count removed.
    /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type.
    /// # Overflow Behavior
    ///
    /// The method does no guarding against overflows, so the removal of more than `usize::MAX` elements either produces the wrong result or panics. If debug assertions are enabled, a panic is guaranteed.
    /// # Panics
    ///
    /// This function might panic if the number of elements removed is greater than `usize::MAX`.
    #[inline]
    pub fn remove_supersets<Q>(&mut self, value: &Q) -> usize
    where
        T: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        self.map.remove_supersets(value)
    }
    /// Adds a value to the set iff there doesn't already exist a proper superset of it.
    /// In the event a value that is equal to it already exists, then it is replaced and returned.
    #[inline]
    pub fn replace(&mut self, value: T) -> Option<T> {
        let prev = {
            let mut cursor = self.map.lower_bound_mut(Bound::Included(&value));
            if let Some(ge) = cursor.next() {
                if *ge.0 == value {
                    cursor.remove_prev().map(|(key, ())| key)
                } else {
                    None
                }
            } else {
                None
            }
        };
        _ = self.insert(value);
        prev
    }
    /// Retains only the elements specified by the predicate.
    /// In other words, remove all `t`s for which `f(&t)` returns `false`. The elements are visited in ascending value order.
    #[inline]
    pub fn retain<F>(&mut self, mut f: F)
    where
        F: FnMut(&T) -> bool,
    {
        self.map.retain(|key, &mut ()| f(key));
    }
    /// Visits the elements representing the union, i.e., the supersets of elements that are in `self` or `other`, in ascending order.
    /// For example if `self` contains a sequence of sets each of which being a subset of the same set in `other`, then only the superset in `other` will be iterated.
    /// The items iterated and the order in which they are iterated will match exactly as if one iterated `self` after `append`ing `other` to it.
    #[inline]
    #[must_use]
    pub fn union<'a>(&'a self, other: &'a Self) -> Union<'a, T> {
        Union {
            iter_1: self.into_iter(),
            iter_2: other.into_iter(),
            prev_1: None,
            prev_2: None,
        }
    }
}
impl<T> BitAnd<Self> for &SupersetSet<T>
where
    T: Clone + SetOrd,
{
    type Output = SupersetSet<T>;
    #[inline]
    fn bitand(self, rhs: Self) -> Self::Output {
        self.intersection(rhs).cloned().collect()
    }
}
impl<T> BitOr<Self> for &SupersetSet<T>
where
    T: Clone + SetOrd,
{
    type Output = SupersetSet<T>;
    #[inline]
    fn bitor(self, rhs: Self) -> Self::Output {
        self.union(rhs).cloned().collect()
    }
}
impl<T> Default for SupersetSet<T> {
    #[inline]
    fn default() -> Self {
        Self::new()
    }
}
impl<T> Extend<T> for SupersetSet<T>
where
    T: SetOrd,
{
    #[inline]
    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        self.map.extend(iter.into_iter().map(|val| (val, ())));
    }
}
impl<'a, T> Extend<&'a T> for SupersetSet<T>
where
    T: SetOrd + Copy,
{
    #[inline]
    fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
        self.map.extend(iter.into_iter().map(|val| (val, &())));
    }
}
impl<T, const N: usize> From<[T; N]> for SupersetSet<T>
where
    T: SetOrd,
{
    #[inline]
    fn from(value: [T; N]) -> Self {
        let mut set = Self::new();
        set.extend(value);
        set
    }
}
impl<T> FromIterator<T> for SupersetSet<T>
where
    T: SetOrd,
{
    #[inline]
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        let mut set = Self::new();
        set.extend(iter);
        set
    }
}
impl<T> Hash for SupersetSet<T>
where
    T: Hash,
{
    #[inline]
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.map.hash(state);
    }
}
impl<T> IntoIterator for SupersetSet<T> {
    type Item = T;
    type IntoIter = IntoIter<T>;
    #[inline]
    fn into_iter(self) -> Self::IntoIter {
        IntoIter {
            iter: self.map.into_keys(),
        }
    }
}
impl<'a, T> IntoIterator for &'a SupersetSet<T> {
    type Item = &'a T;
    type IntoIter = Iter<'a, T>;
    #[inline]
    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}
impl<T> Set for SupersetSet<T>
where
    T: SetOrd,
{
    type Elem = T;
    #[inline]
    fn bounded_cardinality(&self) -> BoundedCardinality {
        BoundedCardinality::from_biguint_exact(self.len().into())
    }
    #[inline]
    fn cardinality(&self) -> Option<Cardinality> {
        Some(Cardinality::Finite(self.len().into()))
    }
    #[inline]
    fn contains<Q>(&self, elem: &Q) -> bool
    where
        Q: Borrow<Self::Elem> + Eq + ?Sized,
    {
        self.contains(elem.borrow())
    }
    #[inline]
    fn is_proper_subset(&self, val: &Self) -> bool {
        self.len() < val.len() && self.intersection(val).count() == val.len()
    }
    #[inline]
    fn is_subset(&self, val: &Self) -> bool {
        self.len() <= val.len() && self.intersection(val).count() == val.len()
    }
}
/// A lazy iterator producing elements in the union of `SupersetSet`s.
///
/// This `struct` is created by [`SupersetSet::union`].
#[expect(missing_debug_implementations, reason = "Iter does not, so we do not")]
#[derive(Clone)]
pub struct Union<'a, T> {
    /// Iterator from the first `SupersetSet`.
    iter_1: Iter<'a, T>,
    /// Iterator from the second `SupersetSet`.
    iter_2: Iter<'a, T>,
    /// Previous value iterated form `iter_1`.
    /// `prev_1` and `prev_2` are never both `Some`.
    prev_1: Option<&'a T>,
    /// Previous value iterated form `iter_2`.
    prev_2: Option<&'a T>,
}
impl<T> FusedIterator for Union<'_, T> where T: SetOrd {}
impl<'a, T> Iterator for Union<'a, T>
where
    T: SetOrd,
{
    type Item = &'a T;
    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        loop {
            if let Some(prev1) = self.prev_1 {
                if let Some(cur2) = self.iter_2.next() {
                    if prev1 >= cur2 {
                        if !prev1.is_superset(cur2) {
                            return Some(cur2);
                        }
                    } else if cur2.is_proper_superset(prev1) {
                        self.prev_1 = None;
                        self.prev_2 = Some(cur2);
                    } else {
                        self.prev_2 = Some(cur2);
                        return self.prev_1.take();
                    }
                } else {
                    return self.prev_1.take();
                }
            } else if let Some(prev2) = self.prev_2 {
                if let Some(cur1) = self.iter_1.next() {
                    if prev2 >= cur1 {
                        if !prev2.is_superset(cur1) {
                            return Some(cur1);
                        }
                    } else if cur1.is_proper_superset(prev2) {
                        self.prev_1 = Some(cur1);
                        self.prev_2 = None;
                    } else {
                        self.prev_1 = Some(cur1);
                        return self.prev_2.take();
                    }
                } else {
                    return self.prev_2.take();
                }
            } else if let Some(cur1) = self.iter_1.next() {
                if let Some(cur2) = self.iter_2.next() {
                    if cur1 >= cur2 {
                        self.prev_1 = Some(cur1);
                        if !cur1.is_superset(cur2) {
                            return Some(cur2);
                        }
                    } else if cur2.is_proper_superset(cur1) {
                        self.prev_2 = Some(cur2);
                    } else {
                        self.prev_2 = Some(cur2);
                        return Some(cur1);
                    }
                } else {
                    return Some(cur1);
                }
            } else {
                return self.iter_2.next();
            }
        }
    }
}
#[cfg(test)]
mod tests {
    use super::{
        super::zfc::{BoundedCardinality, Cardinality, Set, num_bigint::BigUint},
        SetOrd, SupersetSet,
    };
    use core::{borrow::Borrow, cmp::Ordering};
    #[derive(Eq, PartialEq)]
    struct ClosedInterval {
        min: usize,
        max: usize,
    }
    impl PartialOrd<Self> for ClosedInterval {
        fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
            Some(self.cmp(other))
        }
    }
    impl Ord for ClosedInterval {
        fn cmp(&self, other: &Self) -> Ordering {
            match self.min.cmp(&other.min) {
                Ordering::Less => {
                    if self.max >= other.max {
                        Ordering::Greater
                    } else {
                        Ordering::Less
                    }
                }
                Ordering::Equal => self.max.cmp(&other.max),
                Ordering::Greater => {
                    if self.max > other.max {
                        Ordering::Greater
                    } else {
                        Ordering::Less
                    }
                }
            }
        }
    }
    impl Set for ClosedInterval {
        type Elem = usize;
        #[expect(clippy::panic, reason = "want to crash when there is a bug")]
        #[expect(
            clippy::arithmetic_side_effects,
            reason = "comment justifies correctness"
        )]
        fn bounded_cardinality(&self) -> BoundedCardinality {
            BoundedCardinality::from_biguint_exact(
                // `BigUint`s can always be added together.
                BigUint::from(self.max.checked_sub(self.min).unwrap_or_else(|| {
                    panic!("superset_set::test::ClosedInterval must have max >= min")
                })) + BigUint::from(1usize),
            )
        }
        #[expect(clippy::panic, reason = "want to crash when there is a bug")]
        #[expect(
            clippy::arithmetic_side_effects,
            reason = "comment justifies correctness"
        )]
        fn cardinality(&self) -> Option<Cardinality> {
            Some(Cardinality::Finite(
                // `BigUint`s can always be added together.
                BigUint::from(self.max.checked_sub(self.min).unwrap_or_else(|| {
                    panic!("superset_set::test::ClosedInterval must have max >= min")
                })) + BigUint::from(1usize),
            ))
        }
        fn contains<Q>(&self, elem: &Q) -> bool
        where
            Q: ?Sized + Borrow<Self::Elem> + Eq,
        {
            self.min <= *elem.borrow() && self.max >= *elem.borrow()
        }
        fn is_proper_subset(&self, val: &Self) -> bool {
            match self.min.cmp(&val.min) {
                Ordering::Less => false,
                Ordering::Equal => self.max < val.max,
                Ordering::Greater => self.max <= val.max,
            }
        }
        fn is_subset(&self, val: &Self) -> bool {
            self.min >= val.min && self.max <= val.max
        }
    }
    impl SetOrd for ClosedInterval {}
    #[test]
    fn union() {
        let mut set1 = SupersetSet::new();
        _ = set1.insert(ClosedInterval { min: 14, max: 19 });
        _ = set1.insert(ClosedInterval { min: 10, max: 12 });
        _ = set1.insert(ClosedInterval { min: 0, max: 3 });
        _ = set1.insert(ClosedInterval { min: 0, max: 2 });
        _ = set1.insert(ClosedInterval { min: 1, max: 4 });
        _ = set1.insert(ClosedInterval { min: 20, max: 22 });
        _ = set1.insert(ClosedInterval { min: 25, max: 26 });
        _ = set1.insert(ClosedInterval { min: 26, max: 27 });
        let mut set2 = SupersetSet::new();
        _ = set2.insert(ClosedInterval { min: 10, max: 12 });
        _ = set2.insert(ClosedInterval { min: 14, max: 16 });
        _ = set2.insert(ClosedInterval { min: 0, max: 3 });
        _ = set2.insert(ClosedInterval { min: 3, max: 4 });
        _ = set2.insert(ClosedInterval { min: 23, max: 25 });
        _ = set2.insert(ClosedInterval { min: 25, max: 27 });
        let mut union = set1.union(&set2);
        assert!(union.next() == Some(&ClosedInterval { min: 0, max: 3 }));
        assert!(union.next() == Some(&ClosedInterval { min: 1, max: 4 }));
        assert!(union.next() == Some(&ClosedInterval { min: 10, max: 12 }));
        assert!(union.next() == Some(&ClosedInterval { min: 14, max: 19 }));
        assert!(union.next() == Some(&ClosedInterval { min: 20, max: 22 }));
        assert!(union.next() == Some(&ClosedInterval { min: 23, max: 25 }));
        assert!(union.next() == Some(&ClosedInterval { min: 25, max: 27 }));
        assert!(union.next().is_none());
        assert!(union.next().is_none());
        assert!(union.next().is_none());
    }
    #[test]
    fn intersection() {
        let mut set1 = SupersetSet::new();
        _ = set1.insert(ClosedInterval { min: 14, max: 19 });
        _ = set1.insert(ClosedInterval { min: 10, max: 12 });
        _ = set1.insert(ClosedInterval { min: 0, max: 3 });
        _ = set1.insert(ClosedInterval { min: 0, max: 2 });
        _ = set1.insert(ClosedInterval { min: 1, max: 4 });
        _ = set1.insert(ClosedInterval { min: 20, max: 22 });
        _ = set1.insert(ClosedInterval { min: 25, max: 26 });
        _ = set1.insert(ClosedInterval { min: 26, max: 27 });
        let mut set2 = SupersetSet::new();
        _ = set2.insert(ClosedInterval { min: 10, max: 12 });
        _ = set2.insert(ClosedInterval { min: 14, max: 16 });
        _ = set2.insert(ClosedInterval { min: 0, max: 3 });
        _ = set2.insert(ClosedInterval { min: 3, max: 4 });
        _ = set2.insert(ClosedInterval { min: 23, max: 25 });
        _ = set2.insert(ClosedInterval { min: 25, max: 27 });
        let mut intersection = set1.intersection(&set2);
        assert!(intersection.next() == Some(&ClosedInterval { min: 0, max: 3 }));
        assert!(intersection.next() == Some(&ClosedInterval { min: 3, max: 4 }));
        assert!(intersection.next() == Some(&ClosedInterval { min: 10, max: 12 }));
        assert!(intersection.next() == Some(&ClosedInterval { min: 14, max: 16 }));
        assert!(intersection.next() == Some(&ClosedInterval { min: 25, max: 26 }));
        assert!(intersection.next() == Some(&ClosedInterval { min: 26, max: 27 }));
        assert!(intersection.next().is_none());
        assert!(intersection.next().is_none());
        assert!(intersection.next().is_none());
    }
    #[test]
    fn replace() {
        let mut set = SupersetSet::new();
        _ = set.insert(ClosedInterval { min: 14, max: 19 });
        _ = set.insert(ClosedInterval { min: 10, max: 12 });
        _ = set.insert(ClosedInterval { min: 0, max: 3 });
        _ = set.insert(ClosedInterval { min: 0, max: 2 });
        _ = set.insert(ClosedInterval { min: 1, max: 4 });
        _ = set.insert(ClosedInterval { min: 20, max: 22 });
        _ = set.insert(ClosedInterval { min: 25, max: 26 });
        _ = set.insert(ClosedInterval { min: 26, max: 27 });
        // Does not replace proper supersets.
        assert!(
            set.replace(ClosedInterval { min: 20, max: 21 }).is_none()
                && set.contains(&ClosedInterval { min: 20, max: 22 })
                && set.contains_proper_superset(&ClosedInterval { min: 20, max: 21 })
                && !set.contains(&ClosedInterval { min: 20, max: 21 })
        );
        // Successful replace.
        assert!(
            set.replace(ClosedInterval { min: 0, max: 3 })
                == Some(ClosedInterval { min: 0, max: 3 })
                && set.contains(&ClosedInterval { min: 0, max: 3 })
        );
        // Replace is just an insert when a superset does not exist.
        assert!(
            set.replace(ClosedInterval { min: 100, max: 300 }).is_none()
                && set.contains(&ClosedInterval { min: 100, max: 300 })
        );
    }
}