superset_map

B-tree-backed map whose keys are distinct supersets.
git clone https://git.philomathiclife.com/repos/superset_map
Log | Files | Refs | README

superset_set.rs (35328B)


      1 extern crate alloc;
      2 use crate::{
      3     zfc::{BoundedCardinality, Cardinality, Set},
      4     SetOrd, SupersetMap,
      5 };
      6 use alloc::collections::btree_map::{self, IntoKeys, Keys};
      7 use core::{
      8     borrow::Borrow,
      9     hash::{Hash, Hasher},
     10     iter::FusedIterator,
     11     ops::{BitAnd, BitOr, Bound, RangeBounds},
     12 };
     13 /// A lazy iterator producing elements in the intersection of `SupersetSet`s.
     14 ///
     15 /// This `struct` is created by [`SupersetSet::intersection`].
     16 #[derive(Clone)]
     17 pub struct Intersection<'a, T> {
     18     /// Iterator for the first `SupersetSet`.
     19     iter_1: Iter<'a, T>,
     20     /// Iterator for the second `SupersetSet`.
     21     iter_2: Iter<'a, T>,
     22     /// Previous value iterated from `iter_1`.
     23     /// `prev_1` and `prev_2` will never both be `Some`.
     24     prev_1: Option<&'a T>,
     25     /// Previous value iterated from `iter_2`.
     26     prev_2: Option<&'a T>,
     27 }
     28 impl<'a, T> FusedIterator for Intersection<'a, T> where T: SetOrd {}
     29 impl<'a, T> Iterator for Intersection<'a, T>
     30 where
     31     T: SetOrd,
     32 {
     33     type Item = &'a T;
     34     #[inline]
     35     fn next(&mut self) -> Option<Self::Item> {
     36         loop {
     37             if let Some(prev1) = self.prev_1 {
     38                 if let Some(cur2) = self.iter_2.next() {
     39                     if prev1 <= cur2 {
     40                         self.prev_1 = None;
     41                         self.prev_2 = Some(cur2);
     42                         if prev1.is_subset(cur2) {
     43                             return Some(prev1);
     44                         }
     45                     } else if cur2.is_proper_subset(prev1) {
     46                         return Some(cur2);
     47                     } else {
     48                         // Do nothing.
     49                     }
     50                 } else {
     51                     self.prev_1 = None;
     52                     return None;
     53                 }
     54             } else if let Some(prev2) = self.prev_2 {
     55                 if let Some(cur1) = self.iter_1.next() {
     56                     if prev2 <= cur1 {
     57                         self.prev_2 = None;
     58                         self.prev_1 = Some(cur1);
     59                         if prev2.is_subset(cur1) {
     60                             return Some(prev2);
     61                         }
     62                     } else if cur1.is_proper_subset(prev2) {
     63                         return Some(cur1);
     64                     } else {
     65                         // Do nothing.
     66                     }
     67                 } else {
     68                     self.prev_1 = None;
     69                     return None;
     70                 }
     71             } else if let Some(cur1) = self.iter_1.next() {
     72                 if let Some(cur2) = self.iter_2.next() {
     73                     if cur1 <= cur2 {
     74                         self.prev_2 = Some(cur2);
     75                         if cur1.is_subset(cur2) {
     76                             return Some(cur1);
     77                         }
     78                     } else if cur2.is_proper_subset(cur1) {
     79                         self.prev_1 = Some(cur1);
     80                         return Some(cur2);
     81                     } else {
     82                         // Do nothing.
     83                     }
     84                 } else {
     85                     return None;
     86                 }
     87             } else {
     88                 return None;
     89             }
     90         }
     91     }
     92 }
     93 /// An owning iterator over the items of a `SupersetSet`.
     94 ///
     95 /// This `struct` is created by [`SupersetSet::into_iter`] (provided by [`IntoIterator`]).
     96 pub struct IntoIter<T> {
     97     /// Iterator of the values in a `SupersetSet`.
     98     iter: IntoKeys<T, ()>,
     99 }
    100 impl<T> Default for IntoIter<T> {
    101     #[inline]
    102     fn default() -> Self {
    103         Self {
    104             iter: IntoKeys::default(),
    105         }
    106     }
    107 }
    108 impl<T> DoubleEndedIterator for IntoIter<T> {
    109     #[inline]
    110     fn next_back(&mut self) -> Option<Self::Item> {
    111         self.iter.next_back()
    112     }
    113 }
    114 impl<T> ExactSizeIterator for IntoIter<T> {
    115     #[inline]
    116     fn len(&self) -> usize {
    117         self.iter.len()
    118     }
    119 }
    120 impl<T> FusedIterator for IntoIter<T> {}
    121 impl<T> Iterator for IntoIter<T> {
    122     type Item = T;
    123     #[inline]
    124     fn next(&mut self) -> Option<Self::Item> {
    125         self.iter.next()
    126     }
    127 }
    128 /// An iterator over the items of a `SupersetSet`.
    129 ///
    130 /// This `struct` is created by [`SupersetSet::iter`].
    131 #[derive(Clone)]
    132 pub struct Iter<'a, T> {
    133     /// Iterator of the values in a `SupersetSet`.
    134     iter: Keys<'a, T, ()>,
    135 }
    136 impl<'a, T> Default for Iter<'a, T> {
    137     #[inline]
    138     fn default() -> Self {
    139         Self {
    140             iter: Keys::default(),
    141         }
    142     }
    143 }
    144 impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
    145     #[inline]
    146     fn next_back(&mut self) -> Option<Self::Item> {
    147         self.iter.next_back()
    148     }
    149 }
    150 impl<'a, T> ExactSizeIterator for Iter<'a, T> {
    151     #[inline]
    152     fn len(&self) -> usize {
    153         self.iter.len()
    154     }
    155 }
    156 impl<'a, T> FusedIterator for Iter<'a, T> {}
    157 impl<'a, T> Iterator for Iter<'a, T> {
    158     type Item = &'a T;
    159     #[inline]
    160     fn next(&mut self) -> Option<Self::Item> {
    161         self.iter.next()
    162     }
    163 }
    164 /// An iterator over a sub-range of items in a `SupersetSet`.
    165 ///
    166 /// This `struct` is created by [`SupersetSet::range`].
    167 #[derive(Clone)]
    168 pub struct Range<'a, T> {
    169     /// Range iterator for a `SupersetSet`.
    170     iter: btree_map::Range<'a, T, ()>,
    171 }
    172 impl<'a, T> Default for Range<'a, T> {
    173     #[inline]
    174     fn default() -> Self {
    175         Self {
    176             iter: btree_map::Range::default(),
    177         }
    178     }
    179 }
    180 impl<'a, T> DoubleEndedIterator for Range<'a, T> {
    181     #[inline]
    182     fn next_back(&mut self) -> Option<Self::Item> {
    183         self.iter.next_back().map(|(key, &())| key)
    184     }
    185 }
    186 impl<'a, T> FusedIterator for Range<'a, T> {}
    187 impl<'a, T> Iterator for Range<'a, T> {
    188     type Item = &'a T;
    189     #[inline]
    190     fn next(&mut self) -> Option<Self::Item> {
    191         self.iter.next().map(|(key, &())| key)
    192     }
    193 }
    194 /// A minimal collection of `T`s.
    195 ///
    196 /// Internally it is based on a [`SupersetMap`]. When a `T` is [`SupersetSet::insert`]ed, it won't actually be
    197 /// inserted unless there isn't a `T` already in the set that is a superset of it. In such event, all `T`s that
    198 /// are subsets of the to-be-inserted `T` are removed before inserting the `T`.
    199 ///
    200 /// Note this can have quite good performance due to the fact that a single search is necessary to detect if
    201 /// insertion should occur; furthermore since all subsets occur immediately before where the value will be inserted,
    202 /// a simple linear scan is sufficient to remove subsets avoiding the need to search the entire set.
    203 #[derive(Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]
    204 pub struct SupersetSet<T> {
    205     /// Collection of `T`s.
    206     map: SupersetMap<T, ()>,
    207 }
    208 impl<T> SupersetSet<T> {
    209     /// Read [`BTreeSet::clear`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.clear).
    210     #[inline]
    211     pub fn clear(&mut self) {
    212         self.map.clear();
    213     }
    214     /// Read [`BTreeSet::is_empty`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.is_empty).
    215     #[inline]
    216     #[must_use]
    217     pub fn is_empty(&self) -> bool {
    218         self.map.is_empty()
    219     }
    220     /// Read [`BTreeSet::iter`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.iter).
    221     #[inline]
    222     #[must_use]
    223     pub fn iter(&self) -> Iter<'_, T> {
    224         Iter {
    225             iter: self.map.keys(),
    226         }
    227     }
    228     /// Read [`BTreeSet::len`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.len).
    229     #[inline]
    230     #[must_use]
    231     pub fn len(&self) -> usize {
    232         self.map.len()
    233     }
    234     /// Makes a new, empty `SupersetSet`.
    235     /// Does not allocate anything on its own.
    236     #[inline]
    237     #[must_use]
    238     pub const fn new() -> Self {
    239         Self {
    240             map: SupersetMap::new(),
    241         }
    242     }
    243 }
    244 impl<T> SupersetSet<T>
    245 where
    246     T: Ord,
    247 {
    248     /// Read [`BTreeSet::contains`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.contains).
    249     #[expect(clippy::same_name_method, reason = "consistent with BTreeSet")]
    250     #[inline]
    251     pub fn contains<Q>(&self, value: &Q) -> bool
    252     where
    253         T: Borrow<Q>,
    254         Q: Ord + ?Sized,
    255     {
    256         self.map.contains_key(value)
    257     }
    258     /// Read [`BTreeSet::first`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.first).
    259     #[inline]
    260     #[must_use]
    261     pub fn first(&self) -> Option<&T> {
    262         self.map.first_key_value().map(|(key, &())| key)
    263     }
    264     /// Read [`BTreeSet::get`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.get).
    265     #[inline]
    266     pub fn get<Q>(&self, value: &Q) -> Option<&T>
    267     where
    268         T: Borrow<Q>,
    269         Q: Ord + ?Sized,
    270     {
    271         self.map.get_key_value(value).map(|(key, &())| key)
    272     }
    273     /// Read [`BTreeSet::last`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.last).
    274     #[inline]
    275     #[must_use]
    276     pub fn last(&self) -> Option<&T> {
    277         self.map.last_key_value().map(|(key, &())| key)
    278     }
    279     /// Read [`BTreeSet::pop_first`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.pop_first).
    280     #[inline]
    281     pub fn pop_first(&mut self) -> Option<T> {
    282         self.map.pop_first().map(|(key, ())| key)
    283     }
    284     /// Read [`BTreeSet::pop_last`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.pop_last).
    285     #[inline]
    286     pub fn pop_last(&mut self) -> Option<T> {
    287         self.map.pop_last().map(|(key, ())| key)
    288     }
    289     /// Read [`BTreeSet::range`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.range).
    290     #[inline]
    291     pub fn range<K, R>(&self, range: R) -> Range<'_, T>
    292     where
    293         T: Borrow<K>,
    294         K: Ord + ?Sized,
    295         R: RangeBounds<K>,
    296     {
    297         Range {
    298             iter: self.map.range(range),
    299         }
    300     }
    301     /// Read [`BTreeSet::remove`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.remove).
    302     #[inline]
    303     pub fn remove<Q>(&mut self, value: &Q) -> bool
    304     where
    305         T: Borrow<Q>,
    306         Q: Ord + ?Sized,
    307     {
    308         self.map.remove(value).is_some()
    309     }
    310     /// Read [`BTreeSet::split_off`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.split_off).
    311     #[inline]
    312     #[must_use]
    313     pub fn split_off<Q>(&mut self, value: &Q) -> Self
    314     where
    315         T: Borrow<Q>,
    316         Q: Ord + ?Sized,
    317     {
    318         Self {
    319             map: self.map.split_off(value),
    320         }
    321     }
    322     /// Read [`BTreeSet::take`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.take).
    323     #[inline]
    324     pub fn take<Q>(&mut self, value: &Q) -> Option<T>
    325     where
    326         T: Borrow<Q>,
    327         Q: Ord + ?Sized,
    328     {
    329         self.map.remove_entry(value).map(|(key, ())| key)
    330     }
    331 }
    332 impl<T> SupersetSet<T>
    333 where
    334     T: SetOrd,
    335 {
    336     /// Moves all elements from `other` into `self`, consuming `other`.
    337     /// If a value from `other` is a proper superset of a value in `self`, the respective value from `self` will be removed before inserting
    338     /// the value from `other`.
    339     /// If a value from `other` is a subset of a value in `self`, it won't be inserted.
    340     #[inline]
    341     pub fn append(&mut self, other: Self) {
    342         self.map.append(other.map);
    343     }
    344     /// Returns `true` if the set contains a proper subset of the specified value.
    345     /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type.
    346     #[inline]
    347     pub fn contains_proper_subset<Q>(&self, value: &Q) -> bool
    348     where
    349         T: Borrow<Q>,
    350         Q: SetOrd + ?Sized,
    351     {
    352         self.map.contains_proper_subset(value)
    353     }
    354     /// Returns `true` if the set contains a proper superset of the specified value.
    355     /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type.
    356     #[inline]
    357     pub fn contains_proper_superset<Q>(&self, value: &Q) -> bool
    358     where
    359         T: Borrow<Q>,
    360         Q: SetOrd + ?Sized,
    361     {
    362         self.map.contains_proper_superset(value)
    363     }
    364     /// Returns `true` if the set contains a subset of the specified value.
    365     /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type.
    366     #[inline]
    367     pub fn contains_subset<Q>(&self, value: &Q) -> bool
    368     where
    369         T: Borrow<Q>,
    370         Q: SetOrd + ?Sized,
    371     {
    372         self.map.contains_subset(value)
    373     }
    374     /// Returns `true` if the set contains a superset of the specified value.
    375     /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type.
    376     #[inline]
    377     pub fn contains_superset<Q>(&self, value: &Q) -> bool
    378     where
    379         T: Borrow<Q>,
    380         Q: SetOrd + ?Sized,
    381     {
    382         self.map.contains_superset(value)
    383     }
    384     /// Returns a reference to the value corresponding to the greatest proper subset of the passed value.
    385     /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type.
    386     #[inline]
    387     pub fn get_greatest_proper_subset<Q>(&self, value: &Q) -> Option<&T>
    388     where
    389         T: Borrow<Q>,
    390         Q: SetOrd + ?Sized,
    391     {
    392         self.map
    393             .get_greatest_proper_subset_key_value(value)
    394             .map(|(key, &())| key)
    395     }
    396     /// Returns a reference to the value corresponding to the greatest subset of the passed value.
    397     /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type.
    398     #[inline]
    399     pub fn get_greatest_subset<Q>(&self, value: &Q) -> Option<&T>
    400     where
    401         T: Borrow<Q>,
    402         Q: SetOrd + ?Sized,
    403     {
    404         self.map
    405             .get_greatest_subset_key_value(value)
    406             .map(|(key, &())| key)
    407     }
    408     /// Returns a reference to the value corresponding to the least proper superset of the passed value.
    409     /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type.
    410     #[inline]
    411     pub fn get_least_proper_superset<Q>(&self, value: &Q) -> Option<&T>
    412     where
    413         T: Borrow<Q>,
    414         Q: SetOrd + ?Sized,
    415     {
    416         self.map
    417             .get_least_proper_superset_key_value(value)
    418             .map(|(key, &())| key)
    419     }
    420     /// Returns a reference to the value corresponding to the least superset of the passed value.
    421     /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type.
    422     #[inline]
    423     pub fn get_least_superset<Q>(&self, value: &Q) -> Option<&T>
    424     where
    425         T: Borrow<Q>,
    426         Q: SetOrd + ?Sized,
    427     {
    428         self.map
    429             .get_least_superset_key_value(value)
    430             .map(|(key, &())| key)
    431     }
    432     /// `value` is inserted iff there doesn't already
    433     /// exist a `T` that is a superset of `value`.
    434     /// In the event `value` will be inserted, all `T`s
    435     /// where the `T` is a subset of `value` are first removed before
    436     /// inserting.
    437     #[inline]
    438     pub fn insert(&mut self, value: T) -> bool {
    439         self.map.insert(value, ())
    440     }
    441     /// Visits the elements representing the intersection, i.e., the subsets of elements that are both in `self` and `other`, in ascending order.
    442     /// For example if `self` contains a sequence of sets each of which being a subset of the same set in `other`, then only the subsets in `self` will be iterated.
    443     #[inline]
    444     #[must_use]
    445     pub fn intersection<'a>(&'a self, other: &'a Self) -> Intersection<'a, T> {
    446         Intersection {
    447             iter_1: self.into_iter(),
    448             iter_2: other.into_iter(),
    449             prev_1: None,
    450             prev_2: None,
    451         }
    452     }
    453     /// Removes the greatest proper subset of value from the set, returning the value if one existed.
    454     /// The value may be any borrowed form of the set's value type, but the ordering on the borrowed form must match the ordering on the value type.
    455     #[inline]
    456     pub fn remove_greatest_proper_subset<Q>(&mut self, value: &Q) -> Option<T>
    457     where
    458         T: Borrow<Q>,
    459         Q: SetOrd + ?Sized,
    460     {
    461         self.map
    462             .remove_greatest_proper_subset(value)
    463             .map(|(key, ())| key)
    464     }
    465     /// Removes the greatest subset of value from the set, returning the value if one existed.
    466     /// The value may be any borrowed form of the set's value type, but the ordering on the borrowed form must match the ordering on the value type.
    467     #[inline]
    468     pub fn remove_greatest_subset<Q>(&mut self, value: &Q) -> Option<T>
    469     where
    470         T: Borrow<Q>,
    471         Q: SetOrd + ?Sized,
    472     {
    473         self.map.remove_greatest_subset(value).map(|(key, ())| key)
    474     }
    475     /// Removes the least proper superset of value from the set, returning the value if one existed.
    476     /// The value may be any borrowed form of the set's value type, but the ordering on the borrowed form must match the ordering on the value type.
    477     #[inline]
    478     pub fn remove_least_proper_superset<Q>(&mut self, value: &Q) -> Option<T>
    479     where
    480         T: Borrow<Q>,
    481         Q: SetOrd + ?Sized,
    482     {
    483         self.map
    484             .remove_least_proper_superset(value)
    485             .map(|(key, ())| key)
    486     }
    487     /// Removes the least superset of value from the set, returning the value if one existed.
    488     /// The value may be any borrowed form of the set's value type, but the ordering on the borrowed form must match the ordering on the value type.
    489     #[inline]
    490     pub fn remove_least_superset<Q>(&mut self, value: &Q) -> Option<T>
    491     where
    492         T: Borrow<Q>,
    493         Q: SetOrd + ?Sized,
    494     {
    495         self.map.remove_least_superset(value).map(|(key, ())| key)
    496     }
    497     /// Removes all proper subsets of value from the set, returning the count removed.
    498     /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type.
    499     /// # Overflow Behavior
    500     ///
    501     /// 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.
    502     /// # Panics
    503     ///
    504     /// This function might panic if the number of elements removed is greater than `usize::MAX`.
    505     #[inline]
    506     pub fn remove_proper_subsets<Q>(&mut self, value: &Q) -> usize
    507     where
    508         T: Borrow<Q>,
    509         Q: SetOrd + ?Sized,
    510     {
    511         self.map.remove_proper_subsets(value)
    512     }
    513     /// Removes all proper supersets of value from the set, returning the count removed.
    514     /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type.
    515     /// # Overflow Behavior
    516     ///
    517     /// 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.
    518     /// # Panics
    519     ///
    520     /// This function might panic if the number of elements removed is greater than `usize::MAX`.
    521     #[inline]
    522     pub fn remove_proper_supersets<Q>(&mut self, value: &Q) -> usize
    523     where
    524         T: Borrow<Q>,
    525         Q: SetOrd + ?Sized,
    526     {
    527         self.map.remove_proper_supersets(value)
    528     }
    529     /// Removes all subsets of value from the set, returning the count removed.
    530     /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type.
    531     /// # Overflow Behavior
    532     ///
    533     /// 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.
    534     /// # Panics
    535     ///
    536     /// This function might panic if the number of elements removed is greater than `usize::MAX`.
    537     #[inline]
    538     pub fn remove_subsets<Q>(&mut self, value: &Q) -> usize
    539     where
    540         T: Borrow<Q>,
    541         Q: SetOrd + ?Sized,
    542     {
    543         self.map.remove_subsets(value)
    544     }
    545     /// Removes all supersets of value from the set, returning the count removed.
    546     /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type.
    547     /// # Overflow Behavior
    548     ///
    549     /// 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.
    550     /// # Panics
    551     ///
    552     /// This function might panic if the number of elements removed is greater than `usize::MAX`.
    553     #[inline]
    554     pub fn remove_supersets<Q>(&mut self, value: &Q) -> usize
    555     where
    556         T: Borrow<Q>,
    557         Q: SetOrd + ?Sized,
    558     {
    559         self.map.remove_supersets(value)
    560     }
    561     /// Adds a value to the set iff there doesn't already exist a proper superset of it.
    562     /// In the event a value that is equal to it already exists, then it is replaced and returned.
    563     #[inline]
    564     pub fn replace(&mut self, value: T) -> Option<T> {
    565         let prev = {
    566             let mut cursor = self.map.lower_bound_mut(Bound::Included(&value));
    567             if let Some(ge) = cursor.next() {
    568                 if *ge.0 == value {
    569                     cursor.remove_prev().map(|(key, ())| key)
    570                 } else {
    571                     None
    572                 }
    573             } else {
    574                 None
    575             }
    576         };
    577         self.insert(value);
    578         prev
    579     }
    580     /// Retains only the elements specified by the predicate.
    581     /// In other words, remove all `t`s for which `f(&t)` returns `false`. The elements are visited in ascending value order.
    582     #[inline]
    583     pub fn retain<F>(&mut self, mut f: F)
    584     where
    585         F: FnMut(&T) -> bool,
    586     {
    587         self.map.retain(|key, &mut ()| f(key));
    588     }
    589     /// Visits the elements representing the union, i.e., the supersets of elements that are in `self` or `other`, in ascending order.
    590     /// For example if `self` contains a sequence of sets each of which being a subset of the same set in `other`, then only the superset in `other` will be iterated.
    591     /// The items iterated and the order in which they are iterated will match exactly as if one iterated `self` after `append`ing `other` to it.
    592     #[inline]
    593     #[must_use]
    594     pub fn union<'a>(&'a self, other: &'a Self) -> Union<'a, T> {
    595         Union {
    596             iter_1: self.into_iter(),
    597             iter_2: other.into_iter(),
    598             prev_1: None,
    599             prev_2: None,
    600         }
    601     }
    602 }
    603 impl<T> BitAnd<Self> for &SupersetSet<T>
    604 where
    605     T: Clone + SetOrd,
    606 {
    607     type Output = SupersetSet<T>;
    608     #[inline]
    609     fn bitand(self, rhs: Self) -> Self::Output {
    610         self.intersection(rhs).cloned().collect()
    611     }
    612 }
    613 impl<T> BitOr<Self> for &SupersetSet<T>
    614 where
    615     T: Clone + SetOrd,
    616 {
    617     type Output = SupersetSet<T>;
    618     #[inline]
    619     fn bitor(self, rhs: Self) -> Self::Output {
    620         self.union(rhs).cloned().collect()
    621     }
    622 }
    623 impl<T> Default for SupersetSet<T> {
    624     #[inline]
    625     fn default() -> Self {
    626         Self::new()
    627     }
    628 }
    629 impl<T> Extend<T> for SupersetSet<T>
    630 where
    631     T: SetOrd,
    632 {
    633     #[inline]
    634     fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
    635         self.map.extend(iter.into_iter().map(|val| (val, ())));
    636     }
    637 }
    638 impl<'a, T> Extend<&'a T> for SupersetSet<T>
    639 where
    640     T: SetOrd + Copy,
    641 {
    642     #[inline]
    643     fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
    644         self.map.extend(iter.into_iter().map(|val| (val, &())));
    645     }
    646 }
    647 impl<T, const N: usize> From<[T; N]> for SupersetSet<T>
    648 where
    649     T: SetOrd,
    650 {
    651     #[inline]
    652     fn from(value: [T; N]) -> Self {
    653         let mut set = Self::new();
    654         set.extend(value);
    655         set
    656     }
    657 }
    658 impl<T> FromIterator<T> for SupersetSet<T>
    659 where
    660     T: SetOrd,
    661 {
    662     #[inline]
    663     fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
    664         let mut set = Self::new();
    665         set.extend(iter);
    666         set
    667     }
    668 }
    669 impl<T> Hash for SupersetSet<T>
    670 where
    671     T: Hash,
    672 {
    673     #[inline]
    674     fn hash<H: Hasher>(&self, state: &mut H) {
    675         self.map.hash(state);
    676     }
    677 }
    678 impl<T> IntoIterator for SupersetSet<T> {
    679     type Item = T;
    680     type IntoIter = IntoIter<T>;
    681     #[inline]
    682     fn into_iter(self) -> Self::IntoIter {
    683         IntoIter {
    684             iter: self.map.into_keys(),
    685         }
    686     }
    687 }
    688 impl<'a, T> IntoIterator for &'a SupersetSet<T> {
    689     type Item = &'a T;
    690     type IntoIter = Iter<'a, T>;
    691     #[inline]
    692     fn into_iter(self) -> Self::IntoIter {
    693         self.iter()
    694     }
    695 }
    696 impl<T> Set for SupersetSet<T>
    697 where
    698     T: SetOrd,
    699 {
    700     type Elem = T;
    701     #[inline]
    702     fn bounded_cardinality(&self) -> BoundedCardinality {
    703         BoundedCardinality::from_biguint_exact(self.len().into())
    704     }
    705     #[inline]
    706     fn cardinality(&self) -> Option<Cardinality> {
    707         Some(Cardinality::Finite(self.len().into()))
    708     }
    709     #[inline]
    710     fn contains<Q>(&self, elem: &Q) -> bool
    711     where
    712         Q: Borrow<Self::Elem> + Eq + ?Sized,
    713     {
    714         self.contains(elem.borrow())
    715     }
    716     #[inline]
    717     fn is_proper_subset(&self, val: &Self) -> bool {
    718         self.len() < val.len() && self.intersection(val).count() == val.len()
    719     }
    720     #[inline]
    721     fn is_subset(&self, val: &Self) -> bool {
    722         self.len() <= val.len() && self.intersection(val).count() == val.len()
    723     }
    724 }
    725 /// A lazy iterator producing elements in the union of `SupersetSet`s.
    726 ///
    727 /// This `struct` is created by [`SupersetSet::union`].
    728 #[derive(Clone)]
    729 pub struct Union<'a, T> {
    730     /// Iterator from the first `SupersetSet`.
    731     iter_1: Iter<'a, T>,
    732     /// Iterator from the second `SupersetSet`.
    733     iter_2: Iter<'a, T>,
    734     /// Previous value iterated form `iter_1`.
    735     /// `prev_1` and `prev_2` are never both `Some`.
    736     prev_1: Option<&'a T>,
    737     /// Previous value iterated form `iter_2`.
    738     prev_2: Option<&'a T>,
    739 }
    740 impl<'a, T> FusedIterator for Union<'a, T> where T: SetOrd {}
    741 impl<'a, T> Iterator for Union<'a, T>
    742 where
    743     T: SetOrd,
    744 {
    745     type Item = &'a T;
    746     #[inline]
    747     fn next(&mut self) -> Option<Self::Item> {
    748         loop {
    749             if let Some(prev1) = self.prev_1 {
    750                 if let Some(cur2) = self.iter_2.next() {
    751                     if prev1 >= cur2 {
    752                         if !prev1.is_superset(cur2) {
    753                             return Some(cur2);
    754                         }
    755                     } else if cur2.is_proper_superset(prev1) {
    756                         self.prev_1 = None;
    757                         self.prev_2 = Some(cur2);
    758                     } else {
    759                         self.prev_2 = Some(cur2);
    760                         return self.prev_1.take();
    761                     }
    762                 } else {
    763                     return self.prev_1.take();
    764                 }
    765             } else if let Some(prev2) = self.prev_2 {
    766                 if let Some(cur1) = self.iter_1.next() {
    767                     if prev2 >= cur1 {
    768                         if !prev2.is_superset(cur1) {
    769                             return Some(cur1);
    770                         }
    771                     } else if cur1.is_proper_superset(prev2) {
    772                         self.prev_1 = Some(cur1);
    773                         self.prev_2 = None;
    774                     } else {
    775                         self.prev_1 = Some(cur1);
    776                         return self.prev_2.take();
    777                     }
    778                 } else {
    779                     return self.prev_2.take();
    780                 }
    781             } else if let Some(cur1) = self.iter_1.next() {
    782                 if let Some(cur2) = self.iter_2.next() {
    783                     if cur1 >= cur2 {
    784                         self.prev_1 = Some(cur1);
    785                         if !cur1.is_superset(cur2) {
    786                             return Some(cur2);
    787                         }
    788                     } else if cur2.is_proper_superset(cur1) {
    789                         self.prev_2 = Some(cur2);
    790                     } else {
    791                         self.prev_2 = Some(cur2);
    792                         return Some(cur1);
    793                     }
    794                 } else {
    795                     return Some(cur1);
    796                 }
    797             } else {
    798                 return self.iter_2.next();
    799             }
    800         }
    801     }
    802 }
    803 #[cfg(test)]
    804 mod tests {
    805     use super::{
    806         super::zfc::{num_bigint::BigUint, BoundedCardinality, Cardinality, Set},
    807         SetOrd, SupersetSet,
    808     };
    809     use core::{borrow::Borrow, cmp::Ordering};
    810     #[derive(Eq, PartialEq)]
    811     struct ClosedInterval {
    812         min: usize,
    813         max: usize,
    814     }
    815     impl PartialOrd<Self> for ClosedInterval {
    816         fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
    817             Some(self.cmp(other))
    818         }
    819     }
    820     impl Ord for ClosedInterval {
    821         fn cmp(&self, other: &Self) -> Ordering {
    822             match self.min.cmp(&other.min) {
    823                 Ordering::Less => {
    824                     if self.max >= other.max {
    825                         Ordering::Greater
    826                     } else {
    827                         Ordering::Less
    828                     }
    829                 }
    830                 Ordering::Equal => self.max.cmp(&other.max),
    831                 Ordering::Greater => {
    832                     if self.max > other.max {
    833                         Ordering::Greater
    834                     } else {
    835                         Ordering::Less
    836                     }
    837                 }
    838             }
    839         }
    840     }
    841     impl Set for ClosedInterval {
    842         type Elem = usize;
    843         fn bounded_cardinality(&self) -> BoundedCardinality {
    844             BoundedCardinality::from_biguint_exact(
    845                 BigUint::from(self.max - self.min) + BigUint::from(1usize),
    846             )
    847         }
    848         fn cardinality(&self) -> Option<Cardinality> {
    849             Some(Cardinality::Finite(
    850                 BigUint::from(self.max - self.min) + BigUint::from(1usize),
    851             ))
    852         }
    853         fn contains<Q>(&self, elem: &Q) -> bool
    854         where
    855             Q: ?Sized + Borrow<Self::Elem> + Eq,
    856         {
    857             self.min <= *elem.borrow() && self.max >= *elem.borrow()
    858         }
    859         fn is_proper_subset(&self, val: &Self) -> bool {
    860             match self.min.cmp(&val.min) {
    861                 Ordering::Less => false,
    862                 Ordering::Equal => self.max < val.max,
    863                 Ordering::Greater => self.max <= val.max,
    864             }
    865         }
    866         fn is_subset(&self, val: &Self) -> bool {
    867             self.min >= val.min && self.max <= val.max
    868         }
    869     }
    870     impl SetOrd for ClosedInterval {}
    871     #[test]
    872     fn test_union() {
    873         let mut set1 = SupersetSet::new();
    874         set1.insert(ClosedInterval { min: 14, max: 19 });
    875         set1.insert(ClosedInterval { min: 10, max: 12 });
    876         set1.insert(ClosedInterval { min: 0, max: 3 });
    877         set1.insert(ClosedInterval { min: 0, max: 2 });
    878         set1.insert(ClosedInterval { min: 1, max: 4 });
    879         set1.insert(ClosedInterval { min: 20, max: 22 });
    880         set1.insert(ClosedInterval { min: 25, max: 26 });
    881         set1.insert(ClosedInterval { min: 26, max: 27 });
    882         let mut set2 = SupersetSet::new();
    883         set2.insert(ClosedInterval { min: 10, max: 12 });
    884         set2.insert(ClosedInterval { min: 14, max: 16 });
    885         set2.insert(ClosedInterval { min: 0, max: 3 });
    886         set2.insert(ClosedInterval { min: 3, max: 4 });
    887         set2.insert(ClosedInterval { min: 23, max: 25 });
    888         set2.insert(ClosedInterval { min: 25, max: 27 });
    889         let mut union = set1.union(&set2);
    890         assert!(union.next() == Some(&ClosedInterval { min: 0, max: 3 }));
    891         assert!(union.next() == Some(&ClosedInterval { min: 1, max: 4 }));
    892         assert!(union.next() == Some(&ClosedInterval { min: 10, max: 12 }));
    893         assert!(union.next() == Some(&ClosedInterval { min: 14, max: 19 }));
    894         assert!(union.next() == Some(&ClosedInterval { min: 20, max: 22 }));
    895         assert!(union.next() == Some(&ClosedInterval { min: 23, max: 25 }));
    896         assert!(union.next() == Some(&ClosedInterval { min: 25, max: 27 }));
    897         assert!(union.next().is_none());
    898         assert!(union.next().is_none());
    899         assert!(union.next().is_none());
    900     }
    901     #[test]
    902     fn test_intersection() {
    903         let mut set1 = SupersetSet::new();
    904         set1.insert(ClosedInterval { min: 14, max: 19 });
    905         set1.insert(ClosedInterval { min: 10, max: 12 });
    906         set1.insert(ClosedInterval { min: 0, max: 3 });
    907         set1.insert(ClosedInterval { min: 0, max: 2 });
    908         set1.insert(ClosedInterval { min: 1, max: 4 });
    909         set1.insert(ClosedInterval { min: 20, max: 22 });
    910         set1.insert(ClosedInterval { min: 25, max: 26 });
    911         set1.insert(ClosedInterval { min: 26, max: 27 });
    912         let mut set2 = SupersetSet::new();
    913         set2.insert(ClosedInterval { min: 10, max: 12 });
    914         set2.insert(ClosedInterval { min: 14, max: 16 });
    915         set2.insert(ClosedInterval { min: 0, max: 3 });
    916         set2.insert(ClosedInterval { min: 3, max: 4 });
    917         set2.insert(ClosedInterval { min: 23, max: 25 });
    918         set2.insert(ClosedInterval { min: 25, max: 27 });
    919         let mut intersection = set1.intersection(&set2);
    920         assert!(intersection.next() == Some(&ClosedInterval { min: 0, max: 3 }));
    921         assert!(intersection.next() == Some(&ClosedInterval { min: 3, max: 4 }));
    922         assert!(intersection.next() == Some(&ClosedInterval { min: 10, max: 12 }));
    923         assert!(intersection.next() == Some(&ClosedInterval { min: 14, max: 16 }));
    924         assert!(intersection.next() == Some(&ClosedInterval { min: 25, max: 26 }));
    925         assert!(intersection.next() == Some(&ClosedInterval { min: 26, max: 27 }));
    926         assert!(intersection.next().is_none());
    927         assert!(intersection.next().is_none());
    928         assert!(intersection.next().is_none());
    929     }
    930     #[test]
    931     fn test_replace() {
    932         let mut set = SupersetSet::new();
    933         set.insert(ClosedInterval { min: 14, max: 19 });
    934         set.insert(ClosedInterval { min: 10, max: 12 });
    935         set.insert(ClosedInterval { min: 0, max: 3 });
    936         set.insert(ClosedInterval { min: 0, max: 2 });
    937         set.insert(ClosedInterval { min: 1, max: 4 });
    938         set.insert(ClosedInterval { min: 20, max: 22 });
    939         set.insert(ClosedInterval { min: 25, max: 26 });
    940         set.insert(ClosedInterval { min: 26, max: 27 });
    941         // Does not replace proper supersets.
    942         assert!(
    943             set.replace(ClosedInterval { min: 20, max: 21 }).is_none()
    944                 && set.contains(&ClosedInterval { min: 20, max: 22 })
    945                 && set.contains_proper_superset(&ClosedInterval { min: 20, max: 21 })
    946                 && !set.contains(&ClosedInterval { min: 20, max: 21 })
    947         );
    948         // Successful replace.
    949         assert!(
    950             set.replace(ClosedInterval { min: 0, max: 3 })
    951                 == Some(ClosedInterval { min: 0, max: 3 })
    952                 && set.contains(&ClosedInterval { min: 0, max: 3 })
    953         );
    954         // Replace is just an insert when a superset does not exist.
    955         assert!(
    956             set.replace(ClosedInterval { min: 100, max: 300 }).is_none()
    957                 && set.contains(&ClosedInterval { min: 100, max: 300 })
    958         );
    959     }
    960 }