lib.rs - zfc | Philomathic Life

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