lib.rs - zfc | Philomathic Life

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