superset_map.rs - superset_map

superset_map.rs (25082B)
      1 extern crate alloc;
      2 /// Unit tests.
      3 #[cfg(test)]
      4 mod tests;
      5 use crate::SetOrd;
      6 use alloc::collections::btree_map::{
      7     BTreeMap, CursorMut, IntoIter, IntoKeys, IntoValues, Iter, IterMut, Keys, OccupiedEntry, Range,
      8     RangeMut, Values, ValuesMut,
      9 };
     10 use core::{
     11     borrow::Borrow,
     12     ops::{Bound, Index, RangeBounds},
     13 };
     14 /// A minimal collection of `(K, V)`s.
     15 ///
     16 /// Internally it is based on a [`BTreeMap`]. When a `(K, V)` is [`SupersetMap::insert`]ed, it won't actually be
     17 /// inserted unless there isn't a `K` already in the map that is a superset of it. In such event, all `K`s that
     18 /// are subsets of the to-be-inserted `K` are removed before inserting the `K`.
     19 ///
     20 /// Note this can have quite good performance due to the fact that a single search is necessary to detect if
     21 /// insertion should occur; furthermore since all subsets occur immediately before where the key will be inserted,
     22 /// a simple linear scan is sufficient to remove subsets avoiding the need to search the entire map.
     23 #[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
     24 pub struct SupersetMap<K, V> {
     25     /// Collection of `(K, V)`s.
     26     map: BTreeMap<K, V>,
     27 }
     28 impl<K, V> Default for SupersetMap<K, V> {
     29     #[inline]
     30     fn default() -> Self {
     31         Self::new()
     32     }
     33 }
     34 impl<K, V> SupersetMap<K, V> {
     35     /// Read [`BTreeMap::clear`].
     36     #[inline]
     37     pub fn clear(&mut self) {
     38         self.map.clear();
     39     }
     40     /// Read [`BTreeMap::into_keys`].
     41     #[inline]
     42     pub fn into_keys(self) -> IntoKeys<K, V> {
     43         self.map.into_keys()
     44     }
     45     /// Read [`BTreeMap::into_values`].
     46     #[inline]
     47     pub fn into_values(self) -> IntoValues<K, V> {
     48         self.map.into_values()
     49     }
     50     /// Read [`BTreeMap::is_empty`].
     51     #[inline]
     52     #[must_use]
     53     pub fn is_empty(&self) -> bool {
     54         self.map.is_empty()
     55     }
     56     /// Read [`BTreeMap::iter`].
     57     #[inline]
     58     pub fn iter(&self) -> Iter<'_, K, V> {
     59         self.map.iter()
     60     }
     61     /// Read [`BTreeMap::iter_mut`].
     62     #[inline]
     63     pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
     64         self.map.iter_mut()
     65     }
     66     /// Read [`BTreeMap::keys`].
     67     #[inline]
     68     pub fn keys(&self) -> Keys<'_, K, V> {
     69         self.map.keys()
     70     }
     71     /// Read [`BTreeMap::len`].
     72     #[inline]
     73     #[must_use]
     74     pub fn len(&self) -> usize {
     75         self.map.len()
     76     }
     77     /// Makes a new, empty `SupersetMap`.
     78     /// Does not allocate anything on its own.
     79     #[inline]
     80     #[must_use]
     81     pub const fn new() -> Self {
     82         Self {
     83             map: BTreeMap::new(),
     84         }
     85     }
     86     /// Read [`BTreeMap::values`].
     87     #[inline]
     88     pub fn values(&self) -> Values<'_, K, V> {
     89         self.map.values()
     90     }
     91     /// Read [`BTreeMap::values_mut`].
     92     #[inline]
     93     pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
     94         self.map.values_mut()
     95     }
     96 }
     97 impl<K, V> SupersetMap<K, V>
     98 where
     99     K: Ord,
    100 {
    101     /// Read [`BTreeMap::contains_key`].
    102     #[inline]
    103     pub fn contains_key<Q>(&self, key: &Q) -> bool
    104     where
    105         K: Borrow<Q>,
    106         Q: Ord + ?Sized,
    107     {
    108         self.map.contains_key(key)
    109     }
    110     /// Read [`BTreeMap::first_entry`].
    111     #[inline]
    112     pub fn first_entry(&mut self) -> Option<OccupiedEntry<'_, K, V>> {
    113         self.map.first_entry()
    114     }
    115     /// Read [`BTreeMap::first_key_value`].
    116     #[inline]
    117     #[must_use]
    118     pub fn first_key_value(&self) -> Option<(&K, &V)> {
    119         self.map.first_key_value()
    120     }
    121     /// Read [`BTreeMap::get`].
    122     #[inline]
    123     pub fn get<Q>(&self, key: &Q) -> Option<&V>
    124     where
    125         K: Borrow<Q>,
    126         Q: Ord + ?Sized,
    127     {
    128         self.map.get(key)
    129     }
    130     /// Read [`BTreeMap::get_key_value`].
    131     #[inline]
    132     pub fn get_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
    133     where
    134         K: Borrow<Q>,
    135         Q: Ord + ?Sized,
    136     {
    137         self.map.get_key_value(key)
    138     }
    139     /// Read [`BTreeMap::get_mut`].
    140     #[inline]
    141     pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
    142     where
    143         K: Borrow<Q>,
    144         Q: Ord + ?Sized,
    145     {
    146         self.map.get_mut(key)
    147     }
    148     /// Read [`BTreeMap::last_entry`].
    149     #[inline]
    150     pub fn last_entry(&mut self) -> Option<OccupiedEntry<'_, K, V>> {
    151         self.map.last_entry()
    152     }
    153     /// Read [`BTreeMap::last_key_value`].
    154     #[inline]
    155     #[must_use]
    156     pub fn last_key_value(&self) -> Option<(&K, &V)> {
    157         self.map.last_key_value()
    158     }
    159     /// Read [`BTreeMap::pop_first`].
    160     #[inline]
    161     pub fn pop_first(&mut self) -> Option<(K, V)> {
    162         self.map.pop_first()
    163     }
    164     /// Read [`BTreeMap::pop_last`].
    165     #[inline]
    166     pub fn pop_last(&mut self) -> Option<(K, V)> {
    167         self.map.pop_last()
    168     }
    169     /// Read [`BTreeMap::range`].
    170     #[inline]
    171     pub fn range<T, R>(&self, range: R) -> Range<'_, K, V>
    172     where
    173         K: Borrow<T>,
    174         T: Ord + ?Sized,
    175         R: RangeBounds<T>,
    176     {
    177         self.map.range(range)
    178     }
    179     /// Read [`BTreeMap::range_mut`].
    180     #[inline]
    181     pub fn range_mut<T, R>(&mut self, range: R) -> RangeMut<'_, K, V>
    182     where
    183         K: Borrow<T>,
    184         T: Ord + ?Sized,
    185         R: RangeBounds<T>,
    186     {
    187         self.map.range_mut(range)
    188     }
    189     /// Read [`BTreeMap::remove`].
    190     #[inline]
    191     pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
    192     where
    193         K: Borrow<Q>,
    194         Q: Ord + ?Sized,
    195     {
    196         self.map.remove(key)
    197     }
    198     /// Read [`BTreeMap::remove_entry`].
    199     #[inline]
    200     pub fn remove_entry<Q>(&mut self, key: &Q) -> Option<(K, V)>
    201     where
    202         K: Borrow<Q>,
    203         Q: Ord + ?Sized,
    204     {
    205         self.map.remove_entry(key)
    206     }
    207     /// Read [`BTreeMap::split_off`].
    208     #[inline]
    209     #[must_use]
    210     pub fn split_off<Q>(&mut self, key: &Q) -> Self
    211     where
    212         K: Borrow<Q>,
    213         Q: Ord + ?Sized,
    214     {
    215         Self {
    216             map: self.map.split_off(key),
    217         }
    218     }
    219 }
    220 impl<K, V> SupersetMap<K, V>
    221 where
    222     K: SetOrd,
    223 {
    224     /// Moves all elements from `other` into `self`, consuming `other`.
    225     /// 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
    226     /// the key and value from `other`.
    227     /// If a key from `other` is a subset of a key in `self`, it won't be inserted.
    228     #[inline]
    229     pub fn append(&mut self, other: Self) {
    230         if self.is_empty() {
    231             *self = other;
    232         } else {
    233             other.into_iter().fold((), |(), (key, val)| {
    234                 _ = self.insert(key, val);
    235             });
    236         }
    237     }
    238     /// Returns `true` if the map contains a value for a proper subset of the specified key.
    239     /// 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.
    240     #[inline]
    241     pub fn contains_proper_subset<Q>(&self, key: &Q) -> bool
    242     where
    243         K: Borrow<Q>,
    244         Q: SetOrd + ?Sized,
    245     {
    246         self.get_greatest_proper_subset(key).is_some()
    247     }
    248     /// Returns `true` if the map contains a value for a proper superset of the specified key.
    249     /// 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.
    250     #[inline]
    251     pub fn contains_proper_superset<Q>(&self, key: &Q) -> bool
    252     where
    253         K: Borrow<Q>,
    254         Q: SetOrd + ?Sized,
    255     {
    256         self.get_least_proper_superset(key).is_some()
    257     }
    258     /// Returns `true` if the map contains a value for a subset of the specified key.
    259     /// 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.
    260     #[inline]
    261     pub fn contains_subset<Q>(&self, key: &Q) -> bool
    262     where
    263         K: Borrow<Q>,
    264         Q: SetOrd + ?Sized,
    265     {
    266         self.get_greatest_subset(key).is_some()
    267     }
    268     /// Returns `true` if the map contains a value for a superset of the specified key.
    269     /// 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.
    270     #[inline]
    271     pub fn contains_superset<Q>(&self, key: &Q) -> bool
    272     where
    273         K: Borrow<Q>,
    274         Q: SetOrd + ?Sized,
    275     {
    276         self.get_least_superset(key).is_some()
    277     }
    278     /// Returns a reference to the value corresponding to the greatest proper subset of key.
    279     /// 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.
    280     #[inline]
    281     pub fn get_greatest_proper_subset<Q>(&self, key: &Q) -> Option<&V>
    282     where
    283         K: Borrow<Q>,
    284         Q: SetOrd + ?Sized,
    285     {
    286         self.get_greatest_proper_subset_key_value(key)
    287             .map(|(_, val)| val)
    288     }
    289     /// Returns a reference to the key-value pair corresponding to the greatest proper subset of the supplied key.
    290     /// 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.
    291     #[inline]
    292     pub fn get_greatest_proper_subset_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
    293     where
    294         K: Borrow<Q>,
    295         Q: SetOrd + ?Sized,
    296     {
    297         self.map
    298             .upper_bound(Bound::Excluded(key))
    299             .peek_prev()
    300             .and_then(|pair| pair.0.borrow().is_proper_subset(key).then_some(pair))
    301     }
    302     /// Returns a reference to the value corresponding to the greatest subset of key.
    303     /// 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.
    304     #[inline]
    305     pub fn get_greatest_subset<Q>(&self, key: &Q) -> Option<&V>
    306     where
    307         K: Borrow<Q>,
    308         Q: SetOrd + ?Sized,
    309     {
    310         self.get_greatest_subset_key_value(key).map(|(_, val)| val)
    311     }
    312     /// Returns a reference to the key-value pair corresponding to the greatest subset of the supplied key.
    313     /// 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.
    314     #[inline]
    315     pub fn get_greatest_subset_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
    316     where
    317         K: Borrow<Q>,
    318         Q: SetOrd + ?Sized,
    319     {
    320         self.map
    321             .upper_bound(Bound::Included(key))
    322             .peek_prev()
    323             .and_then(|pair| pair.0.borrow().is_subset(key).then_some(pair))
    324     }
    325     /// Returns a reference to the value corresponding to the least proper superset of key.
    326     /// 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.
    327     #[inline]
    328     pub fn get_least_proper_superset<Q>(&self, key: &Q) -> Option<&V>
    329     where
    330         K: Borrow<Q>,
    331         Q: SetOrd + ?Sized,
    332     {
    333         self.get_least_proper_superset_key_value(key)
    334             .map(|(_, val)| val)
    335     }
    336     /// Returns a reference to the key-value pair corresponding to the least proper superset of the supplied key.
    337     /// 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.
    338     #[inline]
    339     pub fn get_least_proper_superset_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
    340     where
    341         K: Borrow<Q>,
    342         Q: SetOrd + ?Sized,
    343     {
    344         self.map
    345             .lower_bound(Bound::Excluded(key))
    346             .peek_next()
    347             .and_then(|pair| pair.0.borrow().is_proper_superset(key).then_some(pair))
    348     }
    349     /// Returns a reference to the value corresponding to the least superset of key.
    350     /// 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.
    351     #[inline]
    352     pub fn get_least_superset<Q>(&self, key: &Q) -> Option<&V>
    353     where
    354         K: Borrow<Q>,
    355         Q: SetOrd + ?Sized,
    356     {
    357         self.get_least_superset_key_value(key).map(|(_, val)| val)
    358     }
    359     /// Returns a reference to the key-value pair corresponding to the least superset of the supplied key.
    360     /// 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.
    361     #[inline]
    362     pub fn get_least_superset_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
    363     where
    364         K: Borrow<Q>,
    365         Q: SetOrd + ?Sized,
    366     {
    367         self.map
    368             .lower_bound(Bound::Included(key))
    369             .peek_next()
    370             .and_then(|pair| pair.0.borrow().is_superset(key).then_some(pair))
    371     }
    372     /// `(key, value)` is inserted iff there doesn't already
    373     /// exist a `K` that is a superset of `key`.
    374     /// In the event `(key, value)` will be inserted, all `(K, V)`s
    375     /// where the `K` is a subset of `key` are first removed before
    376     /// inserting.
    377     #[expect(
    378         unsafe_code,
    379         reason = "we rely on CursorMut::insert_before_unchecked since we verify it is safe to do so"
    380     )]
    381     #[inline]
    382     pub fn insert(&mut self, key: K, value: V) -> bool {
    383         // Since the only way to `insert` a `(K, V)` is via this function,
    384         // the following is true:
    385         // The smallest value greater than or equal to `key` will be a superset
    386         // of `key` iff there exists a superset of `key`.
    387         // This means that we simply have to check this one value to decide
    388         // if `(key, value)` needs to be inserted; furthermore, in the event `(key, value)`
    389         // does need to be inserted, we only have to traverse backwards until
    390         // the beginning of `map` or a `K` is not a subset of `key`
    391         // removing all `(K, V)`s where the `K` is a subset before we insert `(key, value)`.
    392         let mut cursor = self.map.lower_bound_mut(Bound::Included(&key));
    393         if let Some(ge) = cursor.peek_next()
    394             && ge.0.is_superset(&key)
    395         {
    396             false
    397         } else {
    398             loop {
    399                 match cursor.prev() {
    400                     None => break,
    401                     Some(lt) => {
    402                         if key.is_proper_superset(lt.0) {
    403                             drop(cursor.remove_next());
    404                         } else {
    405                             _ = cursor.next();
    406                             break;
    407                         }
    408                     }
    409                 }
    410             }
    411             // SAFETY:
    412             // If `key` already existed in the map, then cursor
    413             // would begin pointing at it. Since `Set::is_superset`
    414             // returns true when both values are the same, we would
    415             // immediately return from this function. This guarantees
    416             // that `key` is unique before inserting.
    417             // Since we only move to smaller values and each time we do
    418             // we remove said value (or stop), the insert of `key` will occur after
    419             // all smaller values and before larger values ensuring the sorted
    420             // order of `map` is retained.
    421             // Note that due to the requirements of `SetOrd`, a `K` that
    422             // `is_proper_superset` another `K` is also strictly greater.
    423             unsafe {
    424                 cursor.insert_before_unchecked(key, value);
    425             }
    426             true
    427         }
    428     }
    429     /// Allows for `SupersetSet::replace` to be implemented for supersets.
    430     #[inline]
    431     pub(crate) fn lower_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V>
    432     where
    433         K: Borrow<Q>,
    434         Q: SetOrd + ?Sized,
    435     {
    436         self.map.lower_bound_mut(bound)
    437     }
    438     /// Removes the greatest proper subset of key from the map, returning the key and value if such a subset exists.
    439     /// 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.
    440     #[inline]
    441     pub fn remove_greatest_proper_subset<Q>(&mut self, key: &Q) -> Option<(K, V)>
    442     where
    443         K: Borrow<Q>,
    444         Q: SetOrd + ?Sized,
    445     {
    446         let mut cursor = self.map.upper_bound_mut(Bound::Excluded(key));
    447         if let Some(lt) = cursor.peek_prev()
    448             && lt.0.borrow().is_proper_subset(key)
    449         {
    450             cursor.remove_prev()
    451         } else {
    452             None
    453         }
    454     }
    455     /// Removes the greatest subset of key from the map, returning the key and value if such a subset exists.
    456     /// 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.
    457     #[inline]
    458     pub fn remove_greatest_subset<Q>(&mut self, key: &Q) -> Option<(K, V)>
    459     where
    460         K: Borrow<Q>,
    461         Q: SetOrd + ?Sized,
    462     {
    463         let mut cursor = self.map.upper_bound_mut(Bound::Included(key));
    464         if let Some(le) = cursor.peek_prev()
    465             && le.0.borrow().is_subset(key)
    466         {
    467             cursor.remove_prev()
    468         } else {
    469             None
    470         }
    471     }
    472     /// Removes the least proper superset of key from the map, returning the key and value if such a superset exists.
    473     /// 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.
    474     #[inline]
    475     pub fn remove_least_proper_superset<Q>(&mut self, key: &Q) -> Option<(K, V)>
    476     where
    477         K: Borrow<Q>,
    478         Q: SetOrd + ?Sized,
    479     {
    480         let mut cursor = self.map.lower_bound_mut(Bound::Excluded(key));
    481         if let Some(gt) = cursor.peek_next()
    482             && gt.0.borrow().is_proper_superset(key)
    483         {
    484             cursor.remove_next()
    485         } else {
    486             None
    487         }
    488     }
    489     /// Removes the least superset of key from the map, returning the key and value if such a superset exists.
    490     /// 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.
    491     #[inline]
    492     pub fn remove_least_superset<Q>(&mut self, key: &Q) -> Option<(K, V)>
    493     where
    494         K: Borrow<Q>,
    495         Q: SetOrd + ?Sized,
    496     {
    497         let mut cursor = self.map.lower_bound_mut(Bound::Included(key));
    498         if let Some(ge) = cursor.peek_next()
    499             && ge.0.borrow().is_superset(key)
    500         {
    501             cursor.remove_next()
    502         } else {
    503             None
    504         }
    505     }
    506     /// Removes all proper subsets of key from the map, returning the count removed.
    507     /// The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match
    508     /// the ordering on the key type.
    509     #[expect(
    510         clippy::arithmetic_side_effects,
    511         reason = "we count how many items are removed which can never exceed the length"
    512     )]
    513     #[inline]
    514     pub fn remove_proper_subsets<Q>(&mut self, key: &Q) -> usize
    515     where
    516         K: Borrow<Q>,
    517         Q: SetOrd + ?Sized,
    518     {
    519         let mut cursor = self.map.upper_bound_mut(Bound::Excluded(key));
    520         let mut count = 0;
    521         while let Some(lt) = cursor.prev() {
    522             if lt.0.borrow().is_proper_subset(key) {
    523                 drop(cursor.remove_next());
    524                 count += 1;
    525             } else {
    526                 return count;
    527             }
    528         }
    529         count
    530     }
    531     /// Removes all proper supersets of key from the map, returning the count removed.
    532     /// The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match
    533     /// the ordering on the key type.
    534     #[expect(
    535         clippy::arithmetic_side_effects,
    536         reason = "we count how many items are removed which can never exceed the length"
    537     )]
    538     #[inline]
    539     pub fn remove_proper_supersets<Q>(&mut self, key: &Q) -> usize
    540     where
    541         K: Borrow<Q>,
    542         Q: SetOrd + ?Sized,
    543     {
    544         let mut cursor = self.map.lower_bound_mut(Bound::Excluded(key));
    545         let mut count = 0;
    546         while let Some(gt) = cursor.next() {
    547             if gt.0.borrow().is_proper_superset(key) {
    548                 drop(cursor.remove_prev());
    549                 count += 1;
    550             } else {
    551                 return count;
    552             }
    553         }
    554         count
    555     }
    556     /// Removes all subsets of key from the map, returning the count removed.
    557     /// The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match
    558     /// the ordering on the key type.
    559     #[expect(
    560         clippy::arithmetic_side_effects,
    561         reason = "we count how many items are removed which can never exceed the length"
    562     )]
    563     #[inline]
    564     pub fn remove_subsets<Q>(&mut self, key: &Q) -> usize
    565     where
    566         K: Borrow<Q>,
    567         Q: SetOrd + ?Sized,
    568     {
    569         let mut cursor = self.map.upper_bound_mut(Bound::Included(key));
    570         let mut count = 0;
    571         // To avoid unnecessary checks for equivalence,
    572         // we separately call `is_subset` on the first element
    573         // while calling `is_proper_subset` on the other elements.
    574         if let Some(le) = cursor.prev() {
    575             if le.0.borrow().is_subset(key) {
    576                 drop(cursor.remove_next());
    577                 count += 1;
    578                 while let Some(lt) = cursor.prev() {
    579                     if lt.0.borrow().is_proper_subset(key) {
    580                         drop(cursor.remove_next());
    581                         count += 1;
    582                     } else {
    583                         return count;
    584                     }
    585                 }
    586             } else {
    587                 return count;
    588             }
    589         }
    590         count
    591     }
    592     /// Removes all supersets of key from the map, returning the count removed.
    593     /// The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must
    594     /// match the ordering on the key type.
    595     #[expect(
    596         clippy::arithmetic_side_effects,
    597         reason = "we count how many items are removed which can never exceed the length"
    598     )]
    599     #[inline]
    600     pub fn remove_supersets<Q>(&mut self, key: &Q) -> usize
    601     where
    602         K: Borrow<Q>,
    603         Q: SetOrd + ?Sized,
    604     {
    605         let mut cursor = self.map.lower_bound_mut(Bound::Included(key));
    606         let mut count = 0;
    607         // To avoid unnecessary checks for equivalence, // we separately call `is_superset` on the first element
    608         // while calling `is_proper_superset` on the other elements.
    609         if let Some(ge) = cursor.next() {
    610             if ge.0.borrow().is_superset(key) {
    611                 drop(cursor.remove_prev());
    612                 // `count` never exceeds `self.map.len()`; thus overflow is no worry.
    613                 count += 1;
    614                 while let Some(gt) = cursor.next() {
    615                     if gt.0.borrow().is_proper_superset(key) {
    616                         drop(cursor.remove_prev());
    617                         // `count` never exceeds `self.map.len()`; thus overflow is no worry.
    618                         count += 1;
    619                     } else {
    620                         return count;
    621                     }
    622                 }
    623             } else {
    624                 return count;
    625             }
    626         }
    627         count
    628     }
    629     /// Retains only the elements specified by the predicate.
    630     /// In other words, remove all pairs `(k, v)` for which `f(&k, &mut v)` returns `false`. The elements are visited in ascending key order.
    631     #[inline]
    632     pub fn retain<F>(&mut self, f: F)
    633     where
    634         F: FnMut(&K, &mut V) -> bool,
    635     {
    636         self.map.retain(f);
    637     }
    638 }
    639 impl<K, V> Extend<(K, V)> for SupersetMap<K, V>
    640 where
    641     K: SetOrd,
    642 {
    643     #[inline]
    644     fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
    645         iter.into_iter().fold((), |(), (k, v)| {
    646             _ = self.insert(k, v);
    647         });
    648     }
    649 }
    650 impl<'a, K, V> Extend<(&'a K, &'a V)> for SupersetMap<K, V>
    651 where
    652     K: SetOrd + Copy,
    653     V: Copy,
    654 {
    655     #[inline]
    656     fn extend<T: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: T) {
    657         iter.into_iter().fold((), |(), (k, v)| {
    658             _ = self.insert(*k, *v);
    659         });
    660     }
    661 }
    662 impl<K, V, const N: usize> From<[(K, V); N]> for SupersetMap<K, V>
    663 where
    664     K: SetOrd,
    665 {
    666     #[inline]
    667     fn from(value: [(K, V); N]) -> Self {
    668         let mut map = Self::new();
    669         map.extend(value);
    670         map
    671     }
    672 }
    673 impl<K, V> FromIterator<(K, V)> for SupersetMap<K, V>
    674 where
    675     K: SetOrd,
    676 {
    677     #[inline]
    678     fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
    679         let mut map = Self::new();
    680         map.extend(iter);
    681         map
    682     }
    683 }
    684 impl<K, Q, V> Index<&Q> for SupersetMap<K, V>
    685 where
    686     K: Borrow<Q> + Ord,
    687     Q: Ord + ?Sized,
    688 {
    689     type Output = V;
    690     #[inline]
    691     fn index(&self, index: &Q) -> &Self::Output {
    692         self.map.index(index)
    693     }
    694 }
    695 impl<K, V> IntoIterator for SupersetMap<K, V> {
    696     type Item = (K, V);
    697     type IntoIter = IntoIter<K, V>;
    698     #[inline]
    699     fn into_iter(self) -> Self::IntoIter {
    700         self.map.into_iter()
    701     }
    702 }
    703 impl<'a, K, V> IntoIterator for &'a SupersetMap<K, V> {
    704     type Item = (&'a K, &'a V);
    705     type IntoIter = Iter<'a, K, V>;
    706     #[inline]
    707     fn into_iter(self) -> Self::IntoIter {
    708         self.iter()
    709     }
    710 }
    711 impl<'a, K, V> IntoIterator for &'a mut SupersetMap<K, V> {
    712     type Item = (&'a K, &'a mut V);
    713     type IntoIter = IterMut<'a, K, V>;
    714     #[inline]
    715     fn into_iter(self) -> Self::IntoIter {
    716         self.iter_mut()
    717     }
    718 }
	superset_map B-tree-backed map whose keys are distinct supersets.
	git clone https://git.philomathiclife.com/repos/superset_map
	Log \| Files \| Refs \| README