lib.rs - zfc | Philomathic Life

lib.rs (25659B)
      1 //! [![git]](https://git.philomathiclife.com/zfc/log.html)&ensp;[![crates-io]](https://crates.io/crates/zfc)&ensp;[![docs-rs]](crate)
      2 //!
      3 //! [git]: https://git.philomathiclife.com/git_badge.svg
      4 //! [crates-io]: https://img.shields.io/badge/crates.io-fc8d62?style=for-the-badge&labelColor=555555&logo=rust
      5 //! [docs-rs]: https://img.shields.io/badge/docs.rs-66c2a5?style=for-the-badge&labelColor=555555&logo=docs.rs
      6 //!
      7 //! `zfc` is a library for sets according to
      8 //! [Zermelo–Fraenkel set theory with the axiom of choice (ZFC)](https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory).
      9 #![cfg_attr(docsrs, feature(doc_cfg))]
     10 #![no_std]
     11 extern crate alloc;
     12 use alloc::{collections::BTreeSet, vec::Vec};
     13 use core::borrow::Borrow;
     14 use core::cmp::Ordering;
     15 use core::error::Error;
     16 use core::fmt::{self, Display, Formatter};
     17 use core::ops::{Range, RangeInclusive, Sub};
     18 pub use num_bigint;
     19 use num_bigint::BigUint;
     20 /// Represents the quantity of elements in a [`Set`].
     21 #[derive(Clone, Eq, Hash, Ord, PartialEq, PartialOrd)]
     22 pub enum Cardinality {
     23     /// The contained `BigUint` represents the quantity of elements in a finite `Set`.
     24     Finite(BigUint),
     25     /// The contained `BigUint` represents the [aleph number](https://en.wikipedia.org/wiki/Aleph_number) of a transfinite `Set`.
     26     Transfinite(BigUint),
     27 }
     28 impl Cardinality {
     29     /// Returns a reference to the contained `BigUint`.
     30     #[inline]
     31     #[must_use]
     32     pub const fn as_biguint(&self) -> &BigUint {
     33         match *self {
     34             Self::Finite(ref val) | Self::Transfinite(ref val) => val,
     35         }
     36     }
     37     /// Creates a `Cardinality::Finite` containing `value`.
     38     #[inline]
     39     #[must_use]
     40     pub const fn from_biguint(value: BigUint) -> Self {
     41         Self::Finite(value)
     42     }
     43     /// `Cardinality::Transfinite` is always greater.
     44     /// For `Cardinality::Finite` the contained `BigUint`
     45     /// is compared to `value`.
     46     #[inline]
     47     #[must_use]
     48     pub fn cmp_u8(&self, value: &u8) -> Ordering {
     49         match *self {
     50             Self::Finite(ref card) => card.cmp(&(*value).into()),
     51             Self::Transfinite(_) => Ordering::Greater,
     52         }
     53     }
     54     /// `Cardinality::Transfinite` is always greater.
     55     /// For `Cardinality::Finite` the contained `BigUint`
     56     /// is compared to `value`.
     57     #[inline]
     58     #[must_use]
     59     pub fn cmp_u16(&self, value: &u16) -> Ordering {
     60         match *self {
     61             Self::Finite(ref card) => card.cmp(&(*value).into()),
     62             Self::Transfinite(_) => Ordering::Greater,
     63         }
     64     }
     65     /// `Cardinality::Transfinite` is always greater.
     66     /// For `Cardinality::Finite` the contained `BigUint`
     67     /// is compared to `value`.
     68     #[inline]
     69     #[must_use]
     70     pub fn cmp_u32(&self, value: &u32) -> Ordering {
     71         match *self {
     72             Self::Finite(ref card) => card.cmp(&(*value).into()),
     73             Self::Transfinite(_) => Ordering::Greater,
     74         }
     75     }
     76     /// `Cardinality::Transfinite` is always greater.
     77     /// For `Cardinality::Finite` the contained `BigUint`
     78     /// is compared to `value`.
     79     #[inline]
     80     #[must_use]
     81     pub fn cmp_u64(&self, value: &u64) -> Ordering {
     82         match *self {
     83             Self::Finite(ref card) => card.cmp(&(*value).into()),
     84             Self::Transfinite(_) => Ordering::Greater,
     85         }
     86     }
     87     /// `Cardinality::Transfinite` is always greater.
     88     /// For `Cardinality::Finite` the contained `BigUint`
     89     /// is compared to `value`.
     90     #[inline]
     91     #[must_use]
     92     pub fn cmp_u128(&self, value: &u128) -> Ordering {
     93         match *self {
     94             Self::Finite(ref card) => card.cmp(&(*value).into()),
     95             Self::Transfinite(_) => Ordering::Greater,
     96         }
     97     }
     98     /// `Cardinality::Transfinite` is always greater.
     99     /// For `Cardinality::Finite` the contained `BigUint`
    100     /// is compared to `value`.
    101     #[inline]
    102     #[must_use]
    103     pub fn cmp_usize(&self, value: &usize) -> Ordering {
    104         match *self {
    105             Self::Finite(ref card) => card.cmp(&(*value).into()),
    106             Self::Transfinite(_) => Ordering::Greater,
    107         }
    108     }
    109     /// `Cardinality::Transfinite` is always greater.
    110     /// For `Cardinality::Finite` the contained `BigUint`
    111     /// is compared to `value`.
    112     #[inline]
    113     #[must_use]
    114     pub fn cmp_biguint(&self, value: &BigUint) -> Ordering {
    115         match *self {
    116             Self::Finite(ref card) => card.cmp(value),
    117             Self::Transfinite(_) => Ordering::Greater,
    118         }
    119     }
    120 }
    121 impl Display for Cardinality {
    122     #[inline]
    123     fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
    124         match *self {
    125             Self::Finite(ref val) => val.fmt(f),
    126             Self::Transfinite(ref val) => write!(f, "\u{2135}_{val}"),
    127         }
    128     }
    129 }
    130 impl fmt::Debug for Cardinality {
    131     #[inline]
    132     fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
    133         <Self as Display>::fmt(self, f)
    134     }
    135 }
    136 impl From<BigUint> for Cardinality {
    137     #[inline]
    138     fn from(value: BigUint) -> Self {
    139         Self::from_biguint(value)
    140     }
    141 }
    142 impl TryFrom<BoundedCardinality> for Cardinality {
    143     type Error = CardinalityErr;
    144     #[inline]
    145     fn try_from(value: BoundedCardinality) -> Result<Self, Self::Error> {
    146         if value.lower == value.upper {
    147             Ok(value.lower)
    148         } else {
    149             Err(CardinalityErr)
    150         }
    151     }
    152 }
    153 impl From<Cardinality> for BigUint {
    154     #[inline]
    155     fn from(value: Cardinality) -> Self {
    156         match value {
    157             Cardinality::Finite(val) | Cardinality::Transfinite(val) => val,
    158         }
    159     }
    160 }
    161 impl PartialEq<u8> for Cardinality {
    162     #[inline]
    163     fn eq(&self, other: &u8) -> bool {
    164         match *self {
    165             Self::Finite(ref card) => *card == BigUint::from(*other),
    166             Self::Transfinite(_) => false,
    167         }
    168     }
    169 }
    170 impl PartialEq<u16> for Cardinality {
    171     #[inline]
    172     fn eq(&self, other: &u16) -> bool {
    173         match *self {
    174             Self::Finite(ref card) => *card == BigUint::from(*other),
    175             Self::Transfinite(_) => false,
    176         }
    177     }
    178 }
    179 impl PartialEq<u32> for Cardinality {
    180     #[inline]
    181     fn eq(&self, other: &u32) -> bool {
    182         match *self {
    183             Self::Finite(ref card) => *card == BigUint::from(*other),
    184             Self::Transfinite(_) => false,
    185         }
    186     }
    187 }
    188 impl PartialEq<u64> for Cardinality {
    189     #[inline]
    190     fn eq(&self, other: &u64) -> bool {
    191         match *self {
    192             Self::Finite(ref card) => *card == BigUint::from(*other),
    193             Self::Transfinite(_) => false,
    194         }
    195     }
    196 }
    197 impl PartialEq<u128> for Cardinality {
    198     #[inline]
    199     fn eq(&self, other: &u128) -> bool {
    200         match *self {
    201             Self::Finite(ref card) => *card == BigUint::from(*other),
    202             Self::Transfinite(_) => false,
    203         }
    204     }
    205 }
    206 impl PartialEq<usize> for Cardinality {
    207     #[inline]
    208     fn eq(&self, other: &usize) -> bool {
    209         match *self {
    210             Self::Finite(ref card) => *card == BigUint::from(*other),
    211             Self::Transfinite(_) => false,
    212         }
    213     }
    214 }
    215 impl PartialEq<BigUint> for Cardinality {
    216     #[inline]
    217     fn eq(&self, other: &BigUint) -> bool {
    218         match *self {
    219             Self::Finite(ref card) => card == other,
    220             Self::Transfinite(_) => false,
    221         }
    222     }
    223 }
    224 impl PartialOrd<u8> for Cardinality {
    225     #[inline]
    226     fn partial_cmp(&self, other: &u8) -> Option<Ordering> {
    227         Some(self.cmp_u8(other))
    228     }
    229 }
    230 impl PartialOrd<u16> for Cardinality {
    231     #[inline]
    232     fn partial_cmp(&self, other: &u16) -> Option<Ordering> {
    233         Some(self.cmp_u16(other))
    234     }
    235 }
    236 impl PartialOrd<u32> for Cardinality {
    237     #[inline]
    238     fn partial_cmp(&self, other: &u32) -> Option<Ordering> {
    239         Some(self.cmp_u32(other))
    240     }
    241 }
    242 impl PartialOrd<u64> for Cardinality {
    243     #[inline]
    244     fn partial_cmp(&self, other: &u64) -> Option<Ordering> {
    245         Some(self.cmp_u64(other))
    246     }
    247 }
    248 impl PartialOrd<u128> for Cardinality {
    249     #[inline]
    250     fn partial_cmp(&self, other: &u128) -> Option<Ordering> {
    251         Some(self.cmp_u128(other))
    252     }
    253 }
    254 impl PartialOrd<usize> for Cardinality {
    255     #[inline]
    256     fn partial_cmp(&self, other: &usize) -> Option<Ordering> {
    257         Some(self.cmp_usize(other))
    258     }
    259 }
    260 impl PartialOrd<BigUint> for Cardinality {
    261     #[inline]
    262     fn partial_cmp(&self, other: &BigUint) -> Option<Ordering> {
    263         Some(self.cmp_biguint(other))
    264     }
    265 }
    266 /// Error returned when attempting to create a [`BoundedCardinality`] from a pair of [`BigUint`]s
    267 /// or [`Cardinality`]s such that the upper bound is strictly less than the lower bound.
    268 #[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
    269 pub struct BoundedErr;
    270 impl Display for BoundedErr {
    271     #[inline]
    272     fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
    273         f.write_str("upper bound is greater than lower bound")
    274     }
    275 }
    276 impl Error for BoundedErr {}
    277 /// Error returned when attempting to create a [`Cardinality`] from a [`BoundedCardinality`] such that
    278 /// the lower bound is less than the upper bound.
    279 #[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
    280 pub struct CardinalityErr;
    281 impl Display for CardinalityErr {
    282     #[inline]
    283     fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
    284         f.write_str("lower bound of the BoundedCardinality is less than the upper bound")
    285     }
    286 }
    287 impl Error for CardinalityErr {}
    288 /// Contains a lower and upper bound [`Cardinality`] used to bound the cardinality of a [`Set`].
    289 #[derive(Clone, Eq, Hash, Ord, PartialEq, PartialOrd)]
    290 pub struct BoundedCardinality {
    291     /// Lower bound.
    292     lower: Cardinality,
    293     /// Upper bound.
    294     upper: Cardinality,
    295 }
    296 impl BoundedCardinality {
    297     /// Creates an instance of `BoundedCardinality`.
    298     ///
    299     /// Returns `None` iff `lower > upper`.
    300     #[inline]
    301     #[must_use]
    302     pub fn new(lower: Cardinality, upper: Cardinality) -> Option<Self> {
    303         if lower > upper {
    304             None
    305         } else {
    306             Some(Self { lower, upper })
    307         }
    308     }
    309     /// Creates an instance of `BoundedCardinality` with the lower and upper bounds both set to `exact`.
    310     #[inline]
    311     #[must_use]
    312     pub fn new_exact(exact: Cardinality) -> Self {
    313         Self {
    314             lower: exact.clone(),
    315             upper: exact,
    316         }
    317     }
    318     /// Creates an instance of `BoundedCardinality` with the lower and upper bounds as `Cardinality::Finite`
    319     /// of their respective values.
    320     ///
    321     /// Returns `None` iff `lower > upper`.
    322     #[inline]
    323     #[must_use]
    324     pub fn from_biguint(lower: BigUint, upper: BigUint) -> Option<Self> {
    325         if lower > upper {
    326             None
    327         } else {
    328             Some(Self {
    329                 lower: Cardinality::Finite(lower),
    330                 upper: Cardinality::Finite(upper),
    331             })
    332         }
    333     }
    334     /// Creates an instance of `BoundedCardinality` with the lower and upper bounds as `Cardinality::Finite(exact)`.
    335     #[inline]
    336     #[must_use]
    337     pub fn from_biguint_exact(exact: BigUint) -> Self {
    338         Self {
    339             lower: Cardinality::Finite(exact.clone()),
    340             upper: Cardinality::Finite(exact),
    341         }
    342     }
    343     /// Creates an instance of `BoundedCardinality` without verifying `lower <= upper`.
    344     ///
    345     /// # Safety
    346     ///
    347     /// `lower <= upper`.
    348     #[expect(
    349         unsafe_code,
    350         reason = "when literal values are used, code can reasonably bypass checks"
    351     )]
    352     #[inline]
    353     #[must_use]
    354     pub const unsafe fn new_unsafe(lower: Cardinality, upper: Cardinality) -> Self {
    355         Self { lower, upper }
    356     }
    357     /// Creates an instance of `BoundedCardinality` with the lower and upper bounds as `Cardinality::Finite`
    358     /// of their respective values without verifying `lower <= upper`.
    359     ///
    360     /// # Safety
    361     ///
    362     /// `lower <= upper`.
    363     #[expect(
    364         unsafe_code,
    365         reason = "when literal values are used, code can reasonably bypass checks"
    366     )]
    367     #[inline]
    368     #[must_use]
    369     pub const unsafe fn from_biguint_unsafe(lower: BigUint, upper: BigUint) -> Self {
    370         Self {
    371             lower: Cardinality::Finite(lower),
    372             upper: Cardinality::Finite(upper),
    373         }
    374     }
    375     /// Returns a reference to the lower bound.
    376     #[inline]
    377     #[must_use]
    378     pub const fn lower(&self) -> &Cardinality {
    379         &self.lower
    380     }
    381     /// Returns the lower bound.
    382     #[inline]
    383     #[must_use]
    384     pub fn to_lower(self) -> Cardinality {
    385         self.lower
    386     }
    387     /// Returns a reference to the upper bound.
    388     #[inline]
    389     #[must_use]
    390     pub const fn upper(&self) -> &Cardinality {
    391         &self.upper
    392     }
    393     /// Returns the upper bound.
    394     #[inline]
    395     #[must_use]
    396     pub fn to_upper(self) -> Cardinality {
    397         self.upper
    398     }
    399     /// Returns a tuple containing the references to the lower and upper bounds respectively.
    400     #[inline]
    401     #[must_use]
    402     pub const fn lower_upper(&self) -> (&Cardinality, &Cardinality) {
    403         (&self.lower, &self.upper)
    404     }
    405     /// Returns a reference to the contained `BigUint` of `self.lower()`.
    406     #[inline]
    407     #[must_use]
    408     pub const fn lower_biguint(&self) -> &BigUint {
    409         self.lower.as_biguint()
    410     }
    411     /// Returns the lower bound as a `BigUint`.
    412     #[inline]
    413     #[must_use]
    414     pub fn to_lower_biguint(self) -> BigUint {
    415         self.lower.into()
    416     }
    417     /// Returns a reference to the contained `BigUint` of `self.upper()`.
    418     #[inline]
    419     #[must_use]
    420     pub const fn upper_biguint(&self) -> &BigUint {
    421         self.upper.as_biguint()
    422     }
    423     /// Returns the upper bound as a `BigUint`.
    424     #[inline]
    425     #[must_use]
    426     pub fn to_upper_biguint(self) -> BigUint {
    427         self.upper.into()
    428     }
    429     /// Returns a tuple of references to the contained `BigUint`s of `self.lower()` and `self.upper()` respectively.
    430     #[inline]
    431     #[must_use]
    432     pub const fn lower_upper_biguint(&self) -> (&BigUint, &BigUint) {
    433         (self.lower_biguint(), self.upper_biguint())
    434     }
    435 }
    436 impl Display for BoundedCardinality {
    437     #[inline]
    438     fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
    439         write!(f, "({}, {})", self.lower, self.upper)
    440     }
    441 }
    442 impl fmt::Debug for BoundedCardinality {
    443     #[inline]
    444     fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
    445         <Self as Display>::fmt(self, f)
    446     }
    447 }
    448 impl From<BigUint> for BoundedCardinality {
    449     #[inline]
    450     fn from(value: BigUint) -> Self {
    451         Self::from_biguint_exact(value)
    452     }
    453 }
    454 impl From<Cardinality> for BoundedCardinality {
    455     #[inline]
    456     fn from(value: Cardinality) -> Self {
    457         Self {
    458             lower: value.clone(),
    459             upper: value,
    460         }
    461     }
    462 }
    463 impl TryFrom<(Cardinality, Cardinality)> for BoundedCardinality {
    464     type Error = BoundedErr;
    465     #[inline]
    466     fn try_from(value: (Cardinality, Cardinality)) -> Result<Self, Self::Error> {
    467         Self::new(value.0, value.1).ok_or(BoundedErr)
    468     }
    469 }
    470 impl TryFrom<(BigUint, BigUint)> for BoundedCardinality {
    471     type Error = BoundedErr;
    472     #[inline]
    473     fn try_from(value: (BigUint, BigUint)) -> Result<Self, Self::Error> {
    474         Self::from_biguint(value.0, value.1).ok_or(BoundedErr)
    475     }
    476 }
    477 impl From<BoundedCardinality> for (Cardinality, Cardinality) {
    478     #[inline]
    479     fn from(value: BoundedCardinality) -> Self {
    480         (value.lower, value.upper)
    481     }
    482 }
    483 impl From<BoundedCardinality> for (BigUint, BigUint) {
    484     #[inline]
    485     fn from(value: BoundedCardinality) -> Self {
    486         (value.lower.into(), value.upper.into())
    487     }
    488 }
    489 /// Represents a set according to
    490 /// [Zermelo–Fraenkel set theory with the axiom of choice (ZFC)](https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory).
    491 ///
    492 /// Note that elements in a `Set` must not be distinguishable by order or frequency, so care must be taken in its
    493 /// implementation if the implementing type exposes an API that distinguishes between the order or frequency of
    494 /// `Elem` (e.g., [`Vec<T>`](https://doc.rust-lang.org/alloc/vec/struct.Vec.html) where `Elem` = `T`).
    495 pub trait Set {
    496     /// The elements that make up the set.
    497     ///
    498     /// Per ZFC, this must not be the same type as `Self` nor a recursive type based on `Self`.
    499     type Elem: Eq + ?Sized;
    500     /// Returns the cardinality of `self` if it is known exactly.
    501     ///
    502     /// The following property must be true:
    503     /// * `self.cardinality().unwrap() == self.bounded_cardinality().lower()` ⇔ `self.bounded_cardinality().lower() == self.bounded_cardinality().upper()`.
    504     #[inline]
    505     fn cardinality(&self) -> Option<Cardinality> {
    506         let bound = self.bounded_cardinality();
    507         if bound.lower < bound.upper {
    508             None
    509         } else {
    510             Some(bound.lower)
    511         }
    512     }
    513     /// Returns the bounded cardinality of `self`.
    514     fn bounded_cardinality(&self) -> BoundedCardinality;
    515     /// Returns `true` iff `Self` contains `elem`.
    516     fn contains<Q>(&self, elem: &Q) -> bool
    517     where
    518         Q: Borrow<Self::Elem> + Eq + ?Sized;
    519     /// Must conform to the following properties:
    520     /// * Irreflexivity.
    521     /// * Antisymmetry.
    522     /// * Transitivity.
    523     /// * ∀`a`, `b`: `Self`, `a.is_proper_subset(b)`⇒  ∀`e`: `Elem` | `a.contains(e)`, `b.contains(e)` ∧ ∃`f`: `Elem`, `b.contains(f) && !a.contains(f)`.
    524     /// * ∀`a`, `b`: `Self`, `a.is_proper_subset(b)` ⇒ `a.is_subset(b)`.
    525     /// * ∀`a`, `b`: `Self`, `a.is_proper_subset(b)` ⇔ `b.is_proper_superset(a)`.
    526     fn is_proper_subset(&self, val: &Self) -> bool;
    527     /// Must conform to the following properties:
    528     /// * Reflexivity.
    529     /// * Antisymmetry.
    530     /// * Transitivity.
    531     /// * ∀`a`, `b`: `Self`, `a.is_subset(b)`⇒  ∀`e`: `Elem` | `a.contains(e)`, `b.contains(e)`.
    532     /// * ∀`a`, `b`: `Self`, `a.is_subset(b)` ⇔ `b.is_superset(a)`.
    533     fn is_subset(&self, val: &Self) -> bool;
    534     /// Must conform to the following properties:
    535     /// * Irreflexivity.
    536     /// * Antisymmetry.
    537     /// * Transitivity.
    538     /// * ∀`a`, `b`: `Self`, `a.is_proper_superset(b)` ⇒ `a.is_superset(b)`.
    539     #[inline]
    540     fn is_proper_superset(&self, val: &Self) -> bool {
    541         val.is_proper_subset(self)
    542     }
    543     /// Must conform to the following properties:
    544     /// * Reflexivity.
    545     /// * Antisymmetry.
    546     /// * Transitivity.
    547     #[inline]
    548     fn is_superset(&self, val: &Self) -> bool {
    549         val.is_subset(self)
    550     }
    551     /// Read [`Set::is_proper_subset`].
    552     #[inline]
    553     fn is_proper_subset_iter<T>(&self, val: &T) -> bool
    554     where
    555         Self::Elem: Borrow<T::Elem> + PartialEq<T::Elem>,
    556         for<'a> &'a Self: IntoIterator<Item = &'a Self::Elem>,
    557         T: Set + ?Sized,
    558         T::Elem: PartialEq<Self::Elem>,
    559     {
    560         self.cardinality() < val.cardinality()
    561             && self
    562                 .into_iter()
    563                 .try_fold(
    564                     (),
    565                     |(), elem| {
    566                         if val.contains(elem) { Ok(()) } else { Err(()) }
    567                     },
    568                 )
    569                 .is_ok_and(|()| true)
    570     }
    571     /// Read [`Set::is_subset`].
    572     #[inline]
    573     fn is_subset_iter<T>(&self, val: &T) -> bool
    574     where
    575         Self::Elem: Borrow<T::Elem> + PartialEq<T::Elem>,
    576         for<'a> &'a Self: IntoIterator<Item = &'a Self::Elem>,
    577         T: Set + ?Sized,
    578         T::Elem: PartialEq<Self::Elem>,
    579     {
    580         self.cardinality() <= val.cardinality()
    581             && self
    582                 .into_iter()
    583                 .try_fold(
    584                     (),
    585                     |(), elem| {
    586                         if val.contains(elem) { Ok(()) } else { Err(()) }
    587                     },
    588                 )
    589                 .is_ok_and(|()| true)
    590     }
    591     /// Read [`Set::is_proper_superset`].
    592     #[inline]
    593     fn is_proper_superset_iter<T>(&self, val: &T) -> bool
    594     where
    595         Self::Elem: PartialEq<T::Elem>,
    596         T: Set + ?Sized,
    597         for<'a> &'a T: IntoIterator<Item = &'a T::Elem>,
    598         T::Elem: Borrow<Self::Elem> + PartialEq<Self::Elem>,
    599     {
    600         val.is_proper_subset_iter(self)
    601     }
    602     /// Read [`Set::is_superset`].
    603     #[inline]
    604     fn is_superset_iter<T>(&self, val: &T) -> bool
    605     where
    606         Self::Elem: PartialEq<T::Elem>,
    607         T: Set + ?Sized,
    608         for<'a> &'a T: IntoIterator<Item = &'a T::Elem>,
    609         T::Elem: Borrow<Self::Elem> + PartialEq<Self::Elem>,
    610     {
    611         val.is_subset_iter(self)
    612     }
    613 }
    614 impl<T> Set for BTreeSet<T>
    615 where
    616     T: Ord,
    617 {
    618     type Elem = T;
    619     #[inline]
    620     fn cardinality(&self) -> Option<Cardinality> {
    621         Some(Cardinality::Finite(self.len().into()))
    622     }
    623     #[inline]
    624     fn bounded_cardinality(&self) -> BoundedCardinality {
    625         let card = Cardinality::from_biguint(self.len().into());
    626         BoundedCardinality {
    627             lower: card.clone(),
    628             upper: card,
    629         }
    630     }
    631     #[inline]
    632     fn contains<Q>(&self, elem: &Q) -> bool
    633     where
    634         Q: Borrow<Self::Elem> + Eq + ?Sized,
    635     {
    636         self.contains(elem.borrow())
    637     }
    638     #[inline]
    639     fn is_proper_subset(&self, val: &Self) -> bool {
    640         self.len() < val.len() && self.intersection(val).count() == val.len()
    641     }
    642     #[inline]
    643     fn is_subset(&self, val: &Self) -> bool {
    644         self.len() <= val.len() && self.intersection(val).count() == val.len()
    645     }
    646 }
    647 impl<T> Set for Range<T>
    648 where
    649     T: Ord,
    650     for<'a, 'b> &'a T: Sub<&'b T>,
    651     for<'a, 'b> <&'a T as Sub<&'b T>>::Output: Into<BigUint>,
    652 {
    653     type Elem = T;
    654     #[expect(
    655         clippy::arithmetic_side_effects,
    656         reason = "we need to calculate the cardinality, and we avoid underflow"
    657     )]
    658     #[inline]
    659     fn cardinality(&self) -> Option<Cardinality> {
    660         Some(Cardinality::Finite(if self.end >= self.start {
    661             (&self.end - &self.start).into()
    662         } else {
    663             BigUint::new(Vec::new())
    664         }))
    665     }
    666     #[expect(
    667         clippy::arithmetic_side_effects,
    668         reason = "we need to calculate the cardinality, and we avoid underflow"
    669     )]
    670     #[inline]
    671     fn bounded_cardinality(&self) -> BoundedCardinality {
    672         let card = Cardinality::Finite(if self.end >= self.start {
    673             (&self.end - &self.start).into()
    674         } else {
    675             BigUint::new(Vec::new())
    676         });
    677         BoundedCardinality {
    678             lower: card.clone(),
    679             upper: card,
    680         }
    681     }
    682     #[inline]
    683     fn contains<Q>(&self, elem: &Q) -> bool
    684     where
    685         Q: Borrow<Self::Elem> + Eq + ?Sized,
    686     {
    687         self.contains(elem.borrow())
    688     }
    689     #[inline]
    690     fn is_proper_subset(&self, val: &Self) -> bool {
    691         match self.start.cmp(&val.start) {
    692             Ordering::Less => false,
    693             Ordering::Equal => self.end < val.end,
    694             Ordering::Greater => self.end <= val.end,
    695         }
    696     }
    697     #[inline]
    698     fn is_subset(&self, val: &Self) -> bool {
    699         self.start >= val.start && self.end <= val.end
    700     }
    701 }
    702 impl<T> Set for RangeInclusive<T>
    703 where
    704     T: Ord,
    705     for<'a, 'b> &'a T: Sub<&'b T>,
    706     for<'a, 'b> <&'a T as Sub<&'b T>>::Output: Into<BigUint>,
    707 {
    708     type Elem = T;
    709     #[expect(
    710         clippy::arithmetic_side_effects,
    711         reason = "we need to calculate the cardinality, and we avoid underflow. Overflow is no worry since we use BigUint."
    712     )]
    713     #[inline]
    714     fn cardinality(&self) -> Option<Cardinality> {
    715         Some(Cardinality::Finite(if self.end() >= self.start() {
    716             (self.end() - self.start()).into() + BigUint::new(alloc::vec![1])
    717         } else {
    718             BigUint::new(Vec::new())
    719         }))
    720     }
    721     #[expect(
    722         clippy::arithmetic_side_effects,
    723         reason = "we need to calculate the cardinality, and we avoid underflow. Overflow is no worry since we use BigUint."
    724     )]
    725     #[inline]
    726     fn bounded_cardinality(&self) -> BoundedCardinality {
    727         let card = Cardinality::Finite(if self.end() >= self.start() {
    728             (self.end() - self.start()).into() + BigUint::new(alloc::vec![1])
    729         } else {
    730             BigUint::new(Vec::new())
    731         });
    732         BoundedCardinality {
    733             lower: card.clone(),
    734             upper: card,
    735         }
    736     }
    737     #[inline]
    738     fn contains<Q>(&self, elem: &Q) -> bool
    739     where
    740         Q: Borrow<Self::Elem> + Eq + ?Sized,
    741     {
    742         self.contains(elem.borrow())
    743     }
    744     #[inline]
    745     fn is_proper_subset(&self, val: &Self) -> bool {
    746         match self.start().cmp(val.start()) {
    747             Ordering::Less => false,
    748             Ordering::Equal => self.end() < val.end(),
    749             Ordering::Greater => self.end() <= val.end(),
    750         }
    751     }
    752     #[inline]
    753     fn is_subset(&self, val: &Self) -> bool {
    754         self.start() >= val.start() && self.end() <= val.end()
    755     }
    756 }
    757 #[cfg(feature = "std")]
    758 extern crate std;
    759 #[cfg(feature = "std")]
    760 use core::hash::{BuildHasher, Hash};
    761 #[cfg(feature = "std")]
    762 use std::collections::HashSet;
    763 #[cfg(feature = "std")]
    764 #[cfg_attr(docsrs, doc(cfg(feature = "std")))]
    765 impl<T, S> Set for HashSet<T, S>
    766 where
    767     T: Eq + Hash,
    768     S: BuildHasher,
    769 {
    770     type Elem = T;
    771     #[inline]
    772     fn cardinality(&self) -> Option<Cardinality> {
    773         Some(Cardinality::Finite(self.len().into()))
    774     }
    775     #[inline]
    776     fn bounded_cardinality(&self) -> BoundedCardinality {
    777         let card = Cardinality::Finite(self.len().into());
    778         BoundedCardinality {
    779             lower: card.clone(),
    780             upper: card,
    781         }
    782     }
    783     #[inline]
    784     fn contains<Q>(&self, elem: &Q) -> bool
    785     where
    786         Q: Borrow<Self::Elem> + Eq + ?Sized,
    787     {
    788         self.contains(elem.borrow())
    789     }
    790     #[inline]
    791     fn is_proper_subset(&self, val: &Self) -> bool {
    792         self.len() < val.len() && self.intersection(val).count() == val.len()
    793     }
    794     #[inline]
    795     fn is_subset(&self, val: &Self) -> bool {
    796         self.len() <= val.len() && self.intersection(val).count() == val.len()
    797     }
    798 }
	zfc Library for sets according to ZFC.
	git clone https://git.philomathiclife.com/repos/zfc
	Log \| Files \| Refs \| README