#![deny(
    unsafe_code,
    unused,
    warnings,
    clippy::all,
    clippy::cargo,
    clippy::complexity,
    clippy::correctness,
    clippy::nursery,
    clippy::pedantic,
    clippy::perf,
    clippy::restriction,
    clippy::style,
    clippy::suspicious
)]
#![allow(
    clippy::blanket_clippy_restriction_lints,
    clippy::implicit_return,
    clippy::min_ident_chars,
    clippy::missing_trait_methods,
    clippy::semicolon_outside_block,
    clippy::single_char_lifetime_names
)]
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;
use core::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.
    #[inline]
    #[allow(unsafe_code)]
    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() {
            if ge.0.is_superset(&key) {
                return false;
            }
        }
        loop {
            match cursor.prev() {
                None => break,
                Some(lt) => {
                    if key.is_proper_superset(lt.0) {
                        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() {
            if lt.0.borrow().is_proper_subset(key) {
                return cursor.remove_prev();
            }
        }
        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() {
            if le.0.borrow().is_subset(key) {
                return cursor.remove_prev();
            }
        }
        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() {
            if gt.0.borrow().is_proper_superset(key) {
                return cursor.remove_next();
            }
        }
        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() {
            if ge.0.borrow().is_superset(key) {
                return cursor.remove_next();
            }
        }
        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.
    /// # 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]
    #[allow(clippy::arithmetic_side_effects)]
    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) {
                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.
    /// # 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]
    #[allow(clippy::arithmetic_side_effects)]
    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) {
                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.
    /// # 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]
    #[allow(clippy::arithmetic_side_effects)]
    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) {
                cursor.remove_next();
                count += 1;
                while let Some(lt) = cursor.prev() {
                    if lt.0.borrow().is_proper_subset(key) {
                        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.
    /// # 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]
    #[allow(clippy::arithmetic_side_effects)]
    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) {
                cursor.remove_prev();
                count += 1;
                while let Some(gt) = cursor.next() {
                    if gt.0.borrow().is_proper_superset(key) {
                        cursor.remove_prev();
                        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::SupersetMap;
    use crate::SetOrd;
    use core::borrow::Borrow;
    use core::cmp::Ordering;
    use num_bigint::BigUint;
    use zfc::{BoundedCardinality, Cardinality, Set};
    #[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;
        fn bounded_cardinality(&self) -> BoundedCardinality {
            BoundedCardinality::from_biguint_exact(
                BigUint::from(self.max - self.min) + BigUint::from(1usize),
            )
        }
        fn cardinality(&self) -> Option<Cardinality> {
            Some(Cardinality::Finite(
                BigUint::from(self.max - self.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 test_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()
            .map_or(false, |set| set == ClosedInterval { min: 0, max: 4 }));
        assert!(keys
            .next()
            .map_or(false, |set| set == ClosedInterval { min: 2, max: 7 }));
        assert!(keys
            .next()
            .map_or(false, |set| set == ClosedInterval { min: 10, max: 17 }));
        assert!(keys.next().is_none());
        assert!(keys.next().is_none());
        assert!(keys.next().is_none());
    }
    #[test]
    fn test_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()
            .map_or(false, |set| set == ClosedInterval { min: 0, max: 4 }));
        assert!(keys
            .next()
            .map_or(false, |set| set == ClosedInterval { min: 1, max: 14 }));
        assert!(keys
            .next()
            .map_or(false, |set| set == ClosedInterval { min: 10, max: 17 }));
        assert!(keys
            .next()
            .map_or(false, |set| set == ClosedInterval { min: 11, max: 18 }));
        assert!(keys.next().is_none());
        assert!(keys.next().is_none());
        assert!(keys.next().is_none());
    }
    #[test]
    fn test_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 test_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 })
            .map_or(false, |(key, _)| *key == ClosedInterval { min: 2, max: 7 }));
        assert!(map
            .get_greatest_proper_subset_key_value(&ClosedInterval { min: 10, max: 17 })
            .map_or(true, |_| false));
        assert!(map
            .get_greatest_proper_subset_key_value(&ClosedInterval { min: 210, max: 217 })
            .map_or(true, |_| false));
        assert!(map
            .get_least_proper_superset_key_value(&ClosedInterval { min: 3, max: 4 })
            .map_or(false, |(key, _)| *key == ClosedInterval { min: 0, max: 4 }));
        assert!(map
            .get_least_proper_superset_key_value(&ClosedInterval { min: 10, max: 17 })
            .map_or(true, |_| false));
        assert!(map
            .get_least_proper_superset_key_value(&ClosedInterval { min: 210, max: 217 })
            .map_or(true, |_| false));
        assert!(map
            .get_greatest_subset_key_value(&ClosedInterval { min: 0, max: 10 })
            .map_or(false, |(key, _)| *key == ClosedInterval { min: 2, max: 7 }));
        assert!(map
            .get_greatest_subset_key_value(&ClosedInterval { min: 10, max: 17 })
            .map_or(false, |(key, _)| *key
                == ClosedInterval { min: 10, max: 17 }));
        assert!(map
            .get_greatest_subset_key_value(&ClosedInterval { min: 210, max: 217 })
            .map_or(true, |_| false));
        assert!(map
            .get_least_superset_key_value(&ClosedInterval { min: 3, max: 4 })
            .map_or(false, |(key, _)| *key == ClosedInterval { min: 0, max: 4 }));
        assert!(map
            .get_least_superset_key_value(&ClosedInterval { min: 10, max: 17 })
            .map_or(false, |(key, _)| *key
                == ClosedInterval { min: 10, max: 17 }));
        assert!(map
            .get_least_superset_key_value(&ClosedInterval { min: 210, max: 217 })
            .map_or(true, |_| false));
    }
    #[test]
    fn test_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 })
            .map_or(false, |(key, _)| key == ClosedInterval { min: 2, max: 7 }));
        assert!(map
            .remove_greatest_proper_subset(&ClosedInterval { min: 10, max: 17 })
            .map_or(true, |_| false));
        assert!(map
            .remove_greatest_proper_subset(&ClosedInterval { min: 210, max: 217 })
            .map_or(true, |_| false));
        assert!(map
            .remove_least_proper_superset(&ClosedInterval { min: 3, max: 4 })
            .map_or(false, |(key, _)| key == ClosedInterval { min: 0, max: 4 }));
        assert!(map
            .remove_least_proper_superset(&ClosedInterval { min: 10, max: 17 })
            .map_or(true, |_| false));
        assert!(map
            .remove_least_proper_superset(&ClosedInterval { min: 210, max: 217 })
            .map_or(true, |_| false));
        assert!(map
            .remove_greatest_subset(&ClosedInterval { min: 0, max: 10 })
            .map_or(true, |_| false));
        assert!(map
            .remove_greatest_subset(&ClosedInterval { min: 10, max: 17 })
            .map_or(false, |(key, _)| key == ClosedInterval { min: 10, max: 17 }));
        assert!(map
            .remove_greatest_subset(&ClosedInterval { min: 210, max: 217 })
            .map_or(true, |_| false));
        assert!(map
            .remove_least_superset(&ClosedInterval { min: 3, max: 4 })
            .map_or(true, |_| false));
        assert!(map
            .remove_least_superset(&ClosedInterval { min: 10, max: 17 })
            .map_or(true, |_| false));
        assert!(map
            .remove_least_superset(&ClosedInterval { min: 210, max: 217 })
            .map_or(true, |_| false));
        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);
    }
}