superset_map 0.3.6

extern crate alloc;
use crate::SetOrd;
use alloc::collections::btree_map::{
    BTreeMap, CursorMut, IntoIter, IntoKeys, IntoValues, Iter, IterMut, Keys, OccupiedEntry, Range,
    RangeMut, Values, ValuesMut,
};
use core::{
    borrow::Borrow,
    ops::{Bound, Index, RangeBounds},
};
/// A minimal collection of `(K, V)`s.
///
/// Internally it is based on a [`BTreeMap`]. When a `(K, V)` is [`SupersetMap::insert`]ed, it won't actually be
/// inserted unless there isn't a `K` already in the map that is a superset of it. In such event, all `K`s that
/// are subsets of the to-be-inserted `K` are removed before inserting the `K`.
///
/// 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 key will be inserted,
/// a simple linear scan is sufficient to remove subsets avoiding the need to search the entire map.
#[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub struct SupersetMap<K, V> {
    /// Collection of `(K, V)`s.
    map: BTreeMap<K, V>,
}
impl<K, V> Default for SupersetMap<K, V> {
    #[inline]
    fn default() -> Self {
        Self::new()
    }
}
impl<K, V> SupersetMap<K, V> {
    /// Read [`BTreeMap::clear`].
    #[inline]
    pub fn clear(&mut self) {
        self.map.clear();
    }
    /// Read [`BTreeMap::into_keys`].
    #[inline]
    pub fn into_keys(self) -> IntoKeys<K, V> {
        self.map.into_keys()
    }
    /// Read [`BTreeMap::into_values`].
    #[inline]
    pub fn into_values(self) -> IntoValues<K, V> {
        self.map.into_values()
    }
    /// Read [`BTreeMap::is_empty`].
    #[inline]
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.map.is_empty()
    }
    /// Read [`BTreeMap::iter`].
    #[inline]
    pub fn iter(&self) -> Iter<'_, K, V> {
        self.map.iter()
    }
    /// Read [`BTreeMap::iter_mut`].
    #[inline]
    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
        self.map.iter_mut()
    }
    /// Read [`BTreeMap::keys`].
    #[inline]
    pub fn keys(&self) -> Keys<'_, K, V> {
        self.map.keys()
    }
    /// Read [`BTreeMap::len`].
    #[inline]
    #[must_use]
    pub fn len(&self) -> usize {
        self.map.len()
    }
    /// Makes a new, empty `SupersetMap`.
    /// Does not allocate anything on its own.
    #[inline]
    #[must_use]
    pub const fn new() -> Self {
        Self {
            map: BTreeMap::new(),
        }
    }
    /// Read [`BTreeMap::values`].
    #[inline]
    pub fn values(&self) -> Values<'_, K, V> {
        self.map.values()
    }
    /// Read [`BTreeMap::values_mut`].
    #[inline]
    pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
        self.map.values_mut()
    }
}
impl<K, V> SupersetMap<K, V>
where
    K: Ord,
{
    /// Read [`BTreeMap::contains_key`].
    #[inline]
    pub fn contains_key<Q>(&self, key: &Q) -> bool
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.map.contains_key(key)
    }
    /// Read [`BTreeMap::first_entry`].
    #[inline]
    pub fn first_entry(&mut self) -> Option<OccupiedEntry<'_, K, V>> {
        self.map.first_entry()
    }
    /// Read [`BTreeMap::first_key_value`].
    #[inline]
    #[must_use]
    pub fn first_key_value(&self) -> Option<(&K, &V)> {
        self.map.first_key_value()
    }
    /// Read [`BTreeMap::get`].
    #[inline]
    pub fn get<Q>(&self, key: &Q) -> Option<&V>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.map.get(key)
    }
    /// Read [`BTreeMap::get_key_value`].
    #[inline]
    pub fn get_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.map.get_key_value(key)
    }
    /// Read [`BTreeMap::get_mut`].
    #[inline]
    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.map.get_mut(key)
    }
    /// Read [`BTreeMap::last_entry`].
    #[inline]
    pub fn last_entry(&mut self) -> Option<OccupiedEntry<'_, K, V>> {
        self.map.last_entry()
    }
    /// Read [`BTreeMap::last_key_value`].
    #[inline]
    #[must_use]
    pub fn last_key_value(&self) -> Option<(&K, &V)> {
        self.map.last_key_value()
    }
    /// Read [`BTreeMap::pop_first`].
    #[inline]
    pub fn pop_first(&mut self) -> Option<(K, V)> {
        self.map.pop_first()
    }
    /// Read [`BTreeMap::pop_last`].
    #[inline]
    pub fn pop_last(&mut self) -> Option<(K, V)> {
        self.map.pop_last()
    }
    /// Read [`BTreeMap::range`].
    #[inline]
    pub fn range<T, R>(&self, range: R) -> Range<'_, K, V>
    where
        K: Borrow<T>,
        T: Ord + ?Sized,
        R: RangeBounds<T>,
    {
        self.map.range(range)
    }
    /// Read [`BTreeMap::range_mut`].
    #[inline]
    pub fn range_mut<T, R>(&mut self, range: R) -> RangeMut<'_, K, V>
    where
        K: Borrow<T>,
        T: Ord + ?Sized,
        R: RangeBounds<T>,
    {
        self.map.range_mut(range)
    }
    /// Read [`BTreeMap::remove`].
    #[inline]
    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.map.remove(key)
    }
    /// Read [`BTreeMap::remove_entry`].
    #[inline]
    pub fn remove_entry<Q>(&mut self, key: &Q) -> Option<(K, V)>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.map.remove_entry(key)
    }
    /// Read [`BTreeMap::split_off`].
    #[inline]
    #[must_use]
    pub fn split_off<Q>(&mut self, key: &Q) -> Self
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        Self {
            map: self.map.split_off(key),
        }
    }
}
impl<K, V> SupersetMap<K, V>
where
    K: SetOrd,
{
    /// Moves all elements from `other` into `self`, consuming `other`.
    /// If a key from `other` is a proper superset of a key in `self`, the respective key and value from `self` will be removed before inserting
    /// the key and value from `other`.
    /// If a key from `other` is a subset of a key in `self`, it won't be inserted.
    #[inline]
    pub fn append(&mut self, other: Self) {
        if self.is_empty() {
            *self = other;
        } else {
            other.into_iter().fold((), |(), (key, val)| {
                _ = self.insert(key, val);
            });
        }
    }
    /// Returns `true` if the map contains a value for a proper subset of the specified key.
    /// The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.
    #[inline]
    pub fn contains_proper_subset<Q>(&self, key: &Q) -> bool
    where
        K: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        self.get_greatest_proper_subset(key).is_some()
    }
    /// Returns `true` if the map contains a value for a proper superset of the specified key.
    /// The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.
    #[inline]
    pub fn contains_proper_superset<Q>(&self, key: &Q) -> bool
    where
        K: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        self.get_least_proper_superset(key).is_some()
    }
    /// Returns `true` if the map contains a value for a subset of the specified key.
    /// The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.
    #[inline]
    pub fn contains_subset<Q>(&self, key: &Q) -> bool
    where
        K: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        self.get_greatest_subset(key).is_some()
    }
    /// Returns `true` if the map contains a value for a superset of the specified key.
    /// The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.
    #[inline]
    pub fn contains_superset<Q>(&self, key: &Q) -> bool
    where
        K: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        self.get_least_superset(key).is_some()
    }
    /// Returns a reference to the value corresponding to the greatest proper subset of key.
    /// The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.
    #[inline]
    pub fn get_greatest_proper_subset<Q>(&self, key: &Q) -> Option<&V>
    where
        K: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        self.get_greatest_proper_subset_key_value(key)
            .map(|(_, val)| val)
    }
    /// Returns a reference to the key-value pair corresponding to the greatest proper subset of the supplied key.
    /// The supplied key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.
    #[inline]
    pub fn get_greatest_proper_subset_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
    where
        K: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        self.map
            .upper_bound(Bound::Excluded(key))
            .peek_prev()
            .and_then(|pair| pair.0.borrow().is_proper_subset(key).then_some(pair))
    }
    /// Returns a reference to the value corresponding to the greatest subset of key.
    /// The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.
    #[inline]
    pub fn get_greatest_subset<Q>(&self, key: &Q) -> Option<&V>
    where
        K: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        self.get_greatest_subset_key_value(key).map(|(_, val)| val)
    }
    /// Returns a reference to the key-value pair corresponding to the greatest subset of the supplied key.
    /// The supplied key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.
    #[inline]
    pub fn get_greatest_subset_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
    where
        K: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        self.map
            .upper_bound(Bound::Included(key))
            .peek_prev()
            .and_then(|pair| pair.0.borrow().is_subset(key).then_some(pair))
    }
    /// Returns a reference to the value corresponding to the least proper superset of key.
    /// The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.
    #[inline]
    pub fn get_least_proper_superset<Q>(&self, key: &Q) -> Option<&V>
    where
        K: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        self.get_least_proper_superset_key_value(key)
            .map(|(_, val)| val)
    }
    /// Returns a reference to the key-value pair corresponding to the least proper superset of the supplied key.
    /// The supplied key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.
    #[inline]
    pub fn get_least_proper_superset_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
    where
        K: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        self.map
            .lower_bound(Bound::Excluded(key))
            .peek_next()
            .and_then(|pair| pair.0.borrow().is_proper_superset(key).then_some(pair))
    }
    /// Returns a reference to the value corresponding to the least superset of key.
    /// The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.
    #[inline]
    pub fn get_least_superset<Q>(&self, key: &Q) -> Option<&V>
    where
        K: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        self.get_least_superset_key_value(key).map(|(_, val)| val)
    }
    /// Returns a reference to the key-value pair corresponding to the least superset of the supplied key.
    /// The supplied key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.
    #[inline]
    pub fn get_least_superset_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
    where
        K: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        self.map
            .lower_bound(Bound::Included(key))
            .peek_next()
            .and_then(|pair| pair.0.borrow().is_superset(key).then_some(pair))
    }
    /// `(key, value)` is inserted iff there doesn't already
    /// exist a `K` that is a superset of `key`.
    /// In the event `(key, value)` will be inserted, all `(K, V)`s
    /// where the `K` is a subset of `key` are first removed before
    /// inserting.
    #[expect(
        unsafe_code,
        reason = "we rely on CursorMut::insert_before_unchecked since we verify it is safe to do so"
    )]
    #[inline]
    pub fn insert(&mut self, key: K, value: V) -> bool {
        // Since the only way to `insert` a `(K, V)` is via this function,
        // the following is true:
        // The smallest value greater than or equal to `key` will be a superset
        // of `key` iff there exists a superset of `key`.
        // This means that we simply have to check this one value to decide
        // if `(key, value)` needs to be inserted; furthermore, in the event `(key, value)`
        // does need to be inserted, we only have to traverse backwards until
        // the beginning of `map` or a `K` is not a subset of `key`
        // removing all `(K, V)`s where the `K` is a subset before we insert `(key, value)`.
        let mut cursor = self.map.lower_bound_mut(Bound::Included(&key));
        if let Some(ge) = cursor.peek_next()
            && ge.0.is_superset(&key)
        {
            false
        } else {
            loop {
                match cursor.prev() {
                    None => break,
                    Some(lt) => {
                        if key.is_proper_superset(lt.0) {
                            drop(cursor.remove_next());
                        } else {
                            _ = cursor.next();
                            break;
                        }
                    }
                }
            }
            // SAFETY:
            // If `key` already existed in the map, then cursor
            // would begin pointing at it. Since `Set::is_superset`
            // returns true when both values are the same, we would
            // immediately return from this function. This guarantees
            // that `key` is unique before inserting.
            // Since we only move to smaller values and each time we do
            // we remove said value (or stop), the insert of `key` will occur after
            // all smaller values and before larger values ensuring the sorted
            // order of `map` is retained.
            // Note that due to the requirements of `SetOrd`, a `K` that
            // `is_proper_superset` another `K` is also strictly greater.
            unsafe {
                cursor.insert_before_unchecked(key, value);
            }
            true
        }
    }
    /// Allows for `SupersetSet::replace` to be implemented for supersets.
    #[inline]
    pub(crate) fn lower_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V>
    where
        K: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        self.map.lower_bound_mut(bound)
    }
    /// Removes the greatest proper subset of key from the map, returning the key and value if such a subset exists.
    /// The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.
    #[inline]
    pub fn remove_greatest_proper_subset<Q>(&mut self, key: &Q) -> Option<(K, V)>
    where
        K: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        let mut cursor = self.map.upper_bound_mut(Bound::Excluded(key));
        if let Some(lt) = cursor.peek_prev()
            && lt.0.borrow().is_proper_subset(key)
        {
            cursor.remove_prev()
        } else {
            None
        }
    }
    /// Removes the greatest subset of key from the map, returning the key and value if such a subset exists.
    /// The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.
    #[inline]
    pub fn remove_greatest_subset<Q>(&mut self, key: &Q) -> Option<(K, V)>
    where
        K: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        let mut cursor = self.map.upper_bound_mut(Bound::Included(key));
        if let Some(le) = cursor.peek_prev()
            && le.0.borrow().is_subset(key)
        {
            cursor.remove_prev()
        } else {
            None
        }
    }
    /// Removes the least proper superset of key from the map, returning the key and value if such a superset exists.
    /// The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.
    #[inline]
    pub fn remove_least_proper_superset<Q>(&mut self, key: &Q) -> Option<(K, V)>
    where
        K: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        let mut cursor = self.map.lower_bound_mut(Bound::Excluded(key));
        if let Some(gt) = cursor.peek_next()
            && gt.0.borrow().is_proper_superset(key)
        {
            cursor.remove_next()
        } else {
            None
        }
    }
    /// Removes the least superset of key from the map, returning the key and value if such a superset exists.
    /// The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.
    #[inline]
    pub fn remove_least_superset<Q>(&mut self, key: &Q) -> Option<(K, V)>
    where
        K: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        let mut cursor = self.map.lower_bound_mut(Bound::Included(key));
        if let Some(ge) = cursor.peek_next()
            && ge.0.borrow().is_superset(key)
        {
            cursor.remove_next()
        } else {
            None
        }
    }
    /// Removes all proper subsets of key from the map, returning the count removed.
    /// The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match
    /// the ordering on the key type.
    #[expect(
        clippy::arithmetic_side_effects,
        reason = "we count how many items are removed which can never exceed the length"
    )]
    #[inline]
    pub fn remove_proper_subsets<Q>(&mut self, key: &Q) -> usize
    where
        K: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        let mut cursor = self.map.upper_bound_mut(Bound::Excluded(key));
        let mut count = 0;
        while let Some(lt) = cursor.prev() {
            if lt.0.borrow().is_proper_subset(key) {
                drop(cursor.remove_next());
                count += 1;
            } else {
                return count;
            }
        }
        count
    }
    /// Removes all proper supersets of key from the map, returning the count removed.
    /// The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match
    /// the ordering on the key type.
    #[expect(
        clippy::arithmetic_side_effects,
        reason = "we count how many items are removed which can never exceed the length"
    )]
    #[inline]
    pub fn remove_proper_supersets<Q>(&mut self, key: &Q) -> usize
    where
        K: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        let mut cursor = self.map.lower_bound_mut(Bound::Excluded(key));
        let mut count = 0;
        while let Some(gt) = cursor.next() {
            if gt.0.borrow().is_proper_superset(key) {
                drop(cursor.remove_prev());
                count += 1;
            } else {
                return count;
            }
        }
        count
    }
    /// Removes all subsets of key from the map, returning the count removed.
    /// The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match
    /// the ordering on the key type.
    #[expect(
        clippy::arithmetic_side_effects,
        reason = "we count how many items are removed which can never exceed the length"
    )]
    #[inline]
    pub fn remove_subsets<Q>(&mut self, key: &Q) -> usize
    where
        K: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        let mut cursor = self.map.upper_bound_mut(Bound::Included(key));
        let mut count = 0;
        // To avoid unnecessary checks for equivalence,
        // we separately call `is_subset` on the first element
        // while calling `is_proper_subset` on the other elements.
        if let Some(le) = cursor.prev() {
            if le.0.borrow().is_subset(key) {
                drop(cursor.remove_next());
                count += 1;
                while let Some(lt) = cursor.prev() {
                    if lt.0.borrow().is_proper_subset(key) {
                        drop(cursor.remove_next());
                        count += 1;
                    } else {
                        return count;
                    }
                }
            } else {
                return count;
            }
        }
        count
    }
    /// Removes all supersets of key from the map, returning the count removed.
    /// The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must
    /// match the ordering on the key type.
    #[expect(
        clippy::arithmetic_side_effects,
        reason = "we count how many items are removed which can never exceed the length"
    )]
    #[inline]
    pub fn remove_supersets<Q>(&mut self, key: &Q) -> usize
    where
        K: Borrow<Q>,
        Q: SetOrd + ?Sized,
    {
        let mut cursor = self.map.lower_bound_mut(Bound::Included(key));
        let mut count = 0;
        // To avoid unnecessary checks for equivalence, // we separately call `is_superset` on the first element
        // while calling `is_proper_superset` on the other elements.
        if let Some(ge) = cursor.next() {
            if ge.0.borrow().is_superset(key) {
                drop(cursor.remove_prev());
                // `count` never exceeds `self.map.len()`; thus overflow is no worry.
                count += 1;
                while let Some(gt) = cursor.next() {
                    if gt.0.borrow().is_proper_superset(key) {
                        drop(cursor.remove_prev());
                        // `count` never exceeds `self.map.len()`; thus overflow is no worry.
                        count += 1;
                    } else {
                        return count;
                    }
                }
            } else {
                return count;
            }
        }
        count
    }
    /// Retains only the elements specified by the predicate.
    /// In other words, remove all pairs `(k, v)` for which `f(&k, &mut v)` returns `false`. The elements are visited in ascending key order.
    #[inline]
    pub fn retain<F>(&mut self, f: F)
    where
        F: FnMut(&K, &mut V) -> bool,
    {
        self.map.retain(f);
    }
}
impl<K, V> Extend<(K, V)> for SupersetMap<K, V>
where
    K: SetOrd,
{
    #[inline]
    fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
        iter.into_iter().fold((), |(), (k, v)| {
            _ = self.insert(k, v);
        });
    }
}
impl<'a, K, V> Extend<(&'a K, &'a V)> for SupersetMap<K, V>
where
    K: SetOrd + Copy,
    V: Copy,
{
    #[inline]
    fn extend<T: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: T) {
        iter.into_iter().fold((), |(), (k, v)| {
            _ = self.insert(*k, *v);
        });
    }
}
impl<K, V, const N: usize> From<[(K, V); N]> for SupersetMap<K, V>
where
    K: SetOrd,
{
    #[inline]
    fn from(value: [(K, V); N]) -> Self {
        let mut map = Self::new();
        map.extend(value);
        map
    }
}
impl<K, V> FromIterator<(K, V)> for SupersetMap<K, V>
where
    K: SetOrd,
{
    #[inline]
    fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
        let mut map = Self::new();
        map.extend(iter);
        map
    }
}
impl<K, Q, V> Index<&Q> for SupersetMap<K, V>
where
    K: Borrow<Q> + Ord,
    Q: Ord + ?Sized,
{
    type Output = V;
    #[inline]
    fn index(&self, index: &Q) -> &Self::Output {
        self.map.index(index)
    }
}
impl<K, V> IntoIterator for SupersetMap<K, V> {
    type Item = (K, V);
    type IntoIter = IntoIter<K, V>;
    #[inline]
    fn into_iter(self) -> Self::IntoIter {
        self.map.into_iter()
    }
}
impl<'a, K, V> IntoIterator for &'a SupersetMap<K, V> {
    type Item = (&'a K, &'a V);
    type IntoIter = Iter<'a, K, V>;
    #[inline]
    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}
impl<'a, K, V> IntoIterator for &'a mut SupersetMap<K, V> {
    type Item = (&'a K, &'a mut V);
    type IntoIter = IterMut<'a, K, V>;
    #[inline]
    fn into_iter(self) -> Self::IntoIter {
        self.iter_mut()
    }
}
#[cfg(test)]
mod tests {
    use super::{
        super::zfc::{BoundedCardinality, Cardinality, Set, num_bigint::BigUint},
        SetOrd, SupersetMap,
    };
    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(
                // We can add `BigUint`s.
                BigUint::from(self.max.checked_sub(self.min).unwrap_or_else(|| {
                    panic!(
                        "superset_map::test::ClosedInterval must be created such that max is >= 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(
                // We can add `BigUint`s.
                BigUint::from(self.max.checked_sub(self.min).unwrap_or_else(|| {
                    panic!(
                        "superset_map::test::ClosedInterval must be created such that max is >= 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 insert() {
        let mut map = SupersetMap::new();
        _ = map.insert(ClosedInterval { min: 0, max: 3 }, ());
        _ = map.insert(ClosedInterval { min: 0, max: 3 }, ());
        _ = map.insert(ClosedInterval { min: 0, max: 4 }, ());
        _ = map.insert(ClosedInterval { min: 1, max: 4 }, ());
        _ = map.insert(ClosedInterval { min: 4, max: 6 }, ());
        _ = map.insert(ClosedInterval { min: 2, max: 7 }, ());
        _ = map.insert(ClosedInterval { min: 10, max: 17 }, ());
        let mut keys = map.into_keys();
        assert!(
            keys.next()
                .is_some_and(|set| set == ClosedInterval { min: 0, max: 4 })
        );
        assert!(
            keys.next()
                .is_some_and(|set| set == ClosedInterval { min: 2, max: 7 })
        );
        assert!(
            keys.next()
                .is_some_and(|set| set == ClosedInterval { min: 10, max: 17 })
        );
        assert!(keys.next().is_none());
        assert!(keys.next().is_none());
        assert!(keys.next().is_none());
    }
    #[test]
    fn append() {
        let mut map = SupersetMap::new();
        _ = map.insert(ClosedInterval { min: 0, max: 3 }, ());
        _ = map.insert(ClosedInterval { min: 0, max: 3 }, ());
        _ = map.insert(ClosedInterval { min: 0, max: 4 }, ());
        _ = map.insert(ClosedInterval { min: 1, max: 4 }, ());
        _ = map.insert(ClosedInterval { min: 4, max: 6 }, ());
        _ = map.insert(ClosedInterval { min: 2, max: 7 }, ());
        _ = map.insert(ClosedInterval { min: 10, max: 17 }, ());
        let mut map2 = SupersetMap::new();
        _ = map2.insert(ClosedInterval { min: 0, max: 1 }, ());
        _ = map2.insert(ClosedInterval { min: 1, max: 14 }, ());
        _ = map2.insert(ClosedInterval { min: 11, max: 18 }, ());
        map.append(map2);
        let mut keys = map.into_keys();
        assert!(
            keys.next()
                .is_some_and(|set| set == ClosedInterval { min: 0, max: 4 })
        );
        assert!(
            keys.next()
                .is_some_and(|set| set == ClosedInterval { min: 1, max: 14 })
        );
        assert!(
            keys.next()
                .is_some_and(|set| set == ClosedInterval { min: 10, max: 17 })
        );
        assert!(
            keys.next()
                .is_some_and(|set| set == ClosedInterval { min: 11, max: 18 })
        );
        assert!(keys.next().is_none());
        assert!(keys.next().is_none());
        assert!(keys.next().is_none());
    }
    #[test]
    fn contains() {
        let mut map = SupersetMap::new();
        _ = map.insert(ClosedInterval { min: 0, max: 3 }, ());
        _ = map.insert(ClosedInterval { min: 0, max: 3 }, ());
        _ = map.insert(ClosedInterval { min: 0, max: 4 }, ());
        _ = map.insert(ClosedInterval { min: 1, max: 4 }, ());
        _ = map.insert(ClosedInterval { min: 4, max: 6 }, ());
        _ = map.insert(ClosedInterval { min: 2, max: 7 }, ());
        _ = map.insert(ClosedInterval { min: 10, max: 17 }, ());
        assert!(map.contains_proper_subset(&ClosedInterval { min: 0, max: 10 }));
        assert!(!map.contains_proper_subset(&ClosedInterval { min: 10, max: 17 }));
        assert!(!map.contains_proper_subset(&ClosedInterval { min: 210, max: 217 }));
        assert!(map.contains_proper_superset(&ClosedInterval { min: 0, max: 1 }));
        assert!(!map.contains_proper_superset(&ClosedInterval { min: 10, max: 17 }));
        assert!(!map.contains_proper_superset(&ClosedInterval { min: 210, max: 217 }));
        assert!(map.contains_subset(&ClosedInterval { min: 0, max: 10 }));
        assert!(map.contains_subset(&ClosedInterval { min: 10, max: 17 }));
        assert!(!map.contains_subset(&ClosedInterval { min: 210, max: 217 }));
        assert!(map.contains_superset(&ClosedInterval { min: 0, max: 1 }));
        assert!(map.contains_superset(&ClosedInterval { min: 10, max: 17 }));
        assert!(!map.contains_superset(&ClosedInterval { min: 210, max: 217 }));
    }
    #[test]
    fn get() {
        let mut map = SupersetMap::new();
        _ = map.insert(ClosedInterval { min: 0, max: 3 }, ());
        _ = map.insert(ClosedInterval { min: 0, max: 3 }, ());
        _ = map.insert(ClosedInterval { min: 0, max: 4 }, ());
        _ = map.insert(ClosedInterval { min: 1, max: 4 }, ());
        _ = map.insert(ClosedInterval { min: 4, max: 6 }, ());
        _ = map.insert(ClosedInterval { min: 2, max: 7 }, ());
        _ = map.insert(ClosedInterval { min: 10, max: 17 }, ());
        assert!(
            map.get_greatest_proper_subset_key_value(&ClosedInterval { min: 0, max: 10 })
                .is_some_and(|info| *info.0 == ClosedInterval { min: 2, max: 7 })
        );
        assert!(
            map.get_greatest_proper_subset_key_value(&ClosedInterval { min: 10, max: 17 })
                .is_none()
        );
        assert!(
            map.get_greatest_proper_subset_key_value(&ClosedInterval { min: 210, max: 217 })
                .is_none()
        );
        assert!(
            map.get_least_proper_superset_key_value(&ClosedInterval { min: 3, max: 4 })
                .is_some_and(|info| *info.0 == ClosedInterval { min: 0, max: 4 })
        );
        assert!(
            map.get_least_proper_superset_key_value(&ClosedInterval { min: 10, max: 17 })
                .is_none()
        );
        assert!(
            map.get_least_proper_superset_key_value(&ClosedInterval { min: 210, max: 217 })
                .is_none()
        );
        assert!(
            map.get_greatest_subset_key_value(&ClosedInterval { min: 0, max: 10 })
                .is_some_and(|info| *info.0 == ClosedInterval { min: 2, max: 7 })
        );
        assert!(
            map.get_greatest_subset_key_value(&ClosedInterval { min: 10, max: 17 })
                .is_some_and(|info| *info.0 == ClosedInterval { min: 10, max: 17 })
        );
        assert!(
            map.get_greatest_subset_key_value(&ClosedInterval { min: 210, max: 217 })
                .is_none()
        );
        assert!(
            map.get_least_superset_key_value(&ClosedInterval { min: 3, max: 4 })
                .is_some_and(|info| *info.0 == ClosedInterval { min: 0, max: 4 })
        );
        assert!(
            map.get_least_superset_key_value(&ClosedInterval { min: 10, max: 17 })
                .is_some_and(|info| *info.0 == ClosedInterval { min: 10, max: 17 })
        );
        assert!(
            map.get_least_superset_key_value(&ClosedInterval { min: 210, max: 217 })
                .is_none()
        );
    }
    #[test]
    fn remove() {
        let mut map = SupersetMap::new();
        _ = map.insert(ClosedInterval { min: 0, max: 3 }, ());
        _ = map.insert(ClosedInterval { min: 0, max: 3 }, ());
        _ = map.insert(ClosedInterval { min: 0, max: 4 }, ());
        _ = map.insert(ClosedInterval { min: 1, max: 4 }, ());
        _ = map.insert(ClosedInterval { min: 4, max: 6 }, ());
        _ = map.insert(ClosedInterval { min: 2, max: 7 }, ());
        _ = map.insert(ClosedInterval { min: 10, max: 17 }, ());
        assert!(
            map.remove_greatest_proper_subset(&ClosedInterval { min: 0, max: 10 })
                .is_some_and(|info| info.0 == ClosedInterval { min: 2, max: 7 })
        );
        assert!(
            map.remove_greatest_proper_subset(&ClosedInterval { min: 10, max: 17 })
                .is_none()
        );
        assert!(
            map.remove_greatest_proper_subset(&ClosedInterval { min: 210, max: 217 })
                .is_none()
        );
        assert!(
            map.remove_least_proper_superset(&ClosedInterval { min: 3, max: 4 })
                .is_some_and(|info| info.0 == ClosedInterval { min: 0, max: 4 })
        );
        assert!(
            map.remove_least_proper_superset(&ClosedInterval { min: 10, max: 17 })
                .is_none()
        );
        assert!(
            map.remove_least_proper_superset(&ClosedInterval { min: 210, max: 217 })
                .is_none()
        );
        assert!(
            map.remove_greatest_subset(&ClosedInterval { min: 0, max: 10 })
                .is_none()
        );
        assert!(
            map.remove_greatest_subset(&ClosedInterval { min: 10, max: 17 })
                .is_some_and(|info| info.0 == ClosedInterval { min: 10, max: 17 })
        );
        assert!(
            map.remove_greatest_subset(&ClosedInterval { min: 210, max: 217 })
                .is_none()
        );
        assert!(
            map.remove_least_superset(&ClosedInterval { min: 3, max: 4 })
                .is_none()
        );
        assert!(
            map.remove_least_superset(&ClosedInterval { min: 10, max: 17 })
                .is_none()
        );
        assert!(
            map.remove_least_superset(&ClosedInterval { min: 210, max: 217 })
                .is_none()
        );
        let mut map2 = SupersetMap::new();
        _ = map2.insert(ClosedInterval { min: 0, max: 3 }, ());
        _ = map2.insert(ClosedInterval { min: 0, max: 3 }, ());
        _ = map2.insert(ClosedInterval { min: 0, max: 4 }, ());
        _ = map2.insert(ClosedInterval { min: 1, max: 4 }, ());
        _ = map2.insert(ClosedInterval { min: 4, max: 6 }, ());
        _ = map2.insert(ClosedInterval { min: 2, max: 7 }, ());
        _ = map2.insert(ClosedInterval { min: 10, max: 17 }, ());
        assert!(map2.remove_supersets(&ClosedInterval { min: 0, max: 20 }) == 0);
        assert!(map2.remove_subsets(&ClosedInterval { min: 0, max: 1 }) == 0);
        assert!(map2.remove_subsets(&ClosedInterval { min: 0, max: 20 }) == 3);
        _ = map2.insert(ClosedInterval { min: 0, max: 3 }, ());
        _ = map2.insert(ClosedInterval { min: 0, max: 3 }, ());
        _ = map2.insert(ClosedInterval { min: 0, max: 4 }, ());
        _ = map2.insert(ClosedInterval { min: 1, max: 4 }, ());
        _ = map2.insert(ClosedInterval { min: 4, max: 6 }, ());
        _ = map2.insert(ClosedInterval { min: 2, max: 7 }, ());
        _ = map2.insert(ClosedInterval { min: 10, max: 17 }, ());
        assert!(map2.remove_supersets(&ClosedInterval { min: 3, max: 4 }) == 2);
    }
}