superset_map

superset_map.rs (36991B)

---

 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() {
             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.
     #[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) {
                 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) {
                 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) {
                 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.
     #[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) {
                 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) {
                         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::{num_bigint::BigUint, BoundedCardinality, Cardinality, Set},
         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;
         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);
     }
 }