commit 93f87d9457f5eee1b2dd318804db59ecba7a64b6
parent e81c0b442b32a4b537b541bef4fd7a997a514644
Author: Zack Newman <zack@philomathiclife.com>
Date: Tue, 5 Sep 2023 15:55:05 -0600
added boundedcardinality to set. impl more traits and methods.
Diffstat:
| M | Cargo.toml | | | 2 | +- |
| M | src/lib.rs | | | 430 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--- |
2 files changed, 418 insertions(+), 14 deletions(-)
diff --git a/Cargo.toml b/Cargo.toml
@@ -9,7 +9,7 @@ license = "MIT OR Apache-2.0"
name = "zfc"
readme = "README.md"
repository = "https://git.philomathiclife.com/repos/zfc/"
-version = "0.1.1"
+version = "0.2.0"
[lib]
name = "zfc"
diff --git a/src/lib.rs b/src/lib.rs
@@ -34,10 +34,10 @@ use core::fmt::{self, Display, Formatter};
use core::ops::{Range, RangeInclusive, Sub};
use num_bigint::BigUint;
/// Represents the quantity of elements in a [`Set`].
-#[derive(Clone, PartialEq, Eq, PartialOrd, Ord)]
+#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
#[allow(clippy::exhaustive_enums)]
pub enum Cardinality {
- /// The contained [`BigUint`] represents the quantity of elements in a finite `Set`.
+ /// The contained `BigUint` represents the quantity of elements in a finite `Set`.
Finite(BigUint),
/// The contained `BigUint` represents the [aleph number](https://en.wikipedia.org/wiki/Aleph_number) of a transfinite `Set`.
Transfinite(BigUint),
@@ -51,6 +51,89 @@ impl Cardinality {
Self::Finite(ref val) | Self::Transfinite(ref val) => val,
}
}
+ /// Creates a `Cardinality::Finite` containing `value`.
+ #[inline]
+ #[must_use]
+ pub const fn from_biguint(value: BigUint) -> Self {
+ Self::Finite(value)
+ }
+ /// `Cardinality::Transfinite` is always greater.
+ /// For `Cardinality::Finite` the contained `BigUint`
+ /// is compared to `value`.
+ #[inline]
+ #[must_use]
+ pub fn cmp_u8(&self, value: &u8) -> Ordering {
+ match *self {
+ Self::Finite(ref card) => card.cmp(&(*value).into()),
+ Self::Transfinite(_) => Ordering::Greater,
+ }
+ }
+ /// `Cardinality::Transfinite` is always greater.
+ /// For `Cardinality::Finite` the contained `BigUint`
+ /// is compared to `value`.
+ #[inline]
+ #[must_use]
+ pub fn cmp_u16(&self, value: &u16) -> Ordering {
+ match *self {
+ Self::Finite(ref card) => card.cmp(&(*value).into()),
+ Self::Transfinite(_) => Ordering::Greater,
+ }
+ }
+ /// `Cardinality::Transfinite` is always greater.
+ /// For `Cardinality::Finite` the contained `BigUint`
+ /// is compared to `value`.
+ #[inline]
+ #[must_use]
+ pub fn cmp_u32(&self, value: &u32) -> Ordering {
+ match *self {
+ Self::Finite(ref card) => card.cmp(&(*value).into()),
+ Self::Transfinite(_) => Ordering::Greater,
+ }
+ }
+ /// `Cardinality::Transfinite` is always greater.
+ /// For `Cardinality::Finite` the contained `BigUint`
+ /// is compared to `value`.
+ #[inline]
+ #[must_use]
+ pub fn cmp_u64(&self, value: &u64) -> Ordering {
+ match *self {
+ Self::Finite(ref card) => card.cmp(&(*value).into()),
+ Self::Transfinite(_) => Ordering::Greater,
+ }
+ }
+ /// `Cardinality::Transfinite` is always greater.
+ /// For `Cardinality::Finite` the contained `BigUint`
+ /// is compared to `value`.
+ #[inline]
+ #[must_use]
+ pub fn cmp_u128(&self, value: &u128) -> Ordering {
+ match *self {
+ Self::Finite(ref card) => card.cmp(&(*value).into()),
+ Self::Transfinite(_) => Ordering::Greater,
+ }
+ }
+ /// `Cardinality::Transfinite` is always greater.
+ /// For `Cardinality::Finite` the contained `BigUint`
+ /// is compared to `value`.
+ #[inline]
+ #[must_use]
+ pub fn cmp_usize(&self, value: &usize) -> Ordering {
+ match *self {
+ Self::Finite(ref card) => card.cmp(&(*value).into()),
+ Self::Transfinite(_) => Ordering::Greater,
+ }
+ }
+ /// `Cardinality::Transfinite` is always greater.
+ /// For `Cardinality::Finite` the contained `BigUint`
+ /// is compared to `value`.
+ #[inline]
+ #[must_use]
+ pub fn cmp_biguint(&self, value: &BigUint) -> Ordering {
+ match *self {
+ Self::Finite(ref card) => card.cmp(value),
+ Self::Transfinite(_) => Ordering::Greater,
+ }
+ }
}
impl Display for Cardinality {
#[allow(clippy::min_ident_chars)]
@@ -72,7 +155,7 @@ impl fmt::Debug for Cardinality {
impl From<BigUint> for Cardinality {
#[inline]
fn from(value: BigUint) -> Self {
- Self::Finite(value)
+ Self::from_biguint(value)
}
}
impl From<Cardinality> for BigUint {
@@ -83,6 +166,278 @@ impl From<Cardinality> for BigUint {
}
}
}
+impl PartialEq<u8> for Cardinality {
+ #[inline]
+ fn eq(&self, other: &u8) -> bool {
+ match *self {
+ Self::Finite(ref card) => *card == BigUint::from(*other),
+ Self::Transfinite(_) => false,
+ }
+ }
+}
+impl PartialEq<u16> for Cardinality {
+ #[inline]
+ fn eq(&self, other: &u16) -> bool {
+ match *self {
+ Self::Finite(ref card) => *card == BigUint::from(*other),
+ Self::Transfinite(_) => false,
+ }
+ }
+}
+impl PartialEq<u32> for Cardinality {
+ #[inline]
+ fn eq(&self, other: &u32) -> bool {
+ match *self {
+ Self::Finite(ref card) => *card == BigUint::from(*other),
+ Self::Transfinite(_) => false,
+ }
+ }
+}
+impl PartialEq<u64> for Cardinality {
+ #[inline]
+ fn eq(&self, other: &u64) -> bool {
+ match *self {
+ Self::Finite(ref card) => *card == BigUint::from(*other),
+ Self::Transfinite(_) => false,
+ }
+ }
+}
+impl PartialEq<u128> for Cardinality {
+ #[inline]
+ fn eq(&self, other: &u128) -> bool {
+ match *self {
+ Self::Finite(ref card) => *card == BigUint::from(*other),
+ Self::Transfinite(_) => false,
+ }
+ }
+}
+impl PartialEq<usize> for Cardinality {
+ #[inline]
+ fn eq(&self, other: &usize) -> bool {
+ match *self {
+ Self::Finite(ref card) => *card == BigUint::from(*other),
+ Self::Transfinite(_) => false,
+ }
+ }
+}
+impl PartialEq<BigUint> for Cardinality {
+ #[inline]
+ fn eq(&self, other: &BigUint) -> bool {
+ match *self {
+ Self::Finite(ref card) => card == other,
+ Self::Transfinite(_) => false,
+ }
+ }
+}
+impl PartialOrd<u8> for Cardinality {
+ #[inline]
+ fn partial_cmp(&self, other: &u8) -> Option<Ordering> {
+ Some(self.cmp_u8(other))
+ }
+}
+impl PartialOrd<u16> for Cardinality {
+ #[inline]
+ fn partial_cmp(&self, other: &u16) -> Option<Ordering> {
+ Some(self.cmp_u16(other))
+ }
+}
+impl PartialOrd<u32> for Cardinality {
+ #[inline]
+ fn partial_cmp(&self, other: &u32) -> Option<Ordering> {
+ Some(self.cmp_u32(other))
+ }
+}
+impl PartialOrd<u64> for Cardinality {
+ #[inline]
+ fn partial_cmp(&self, other: &u64) -> Option<Ordering> {
+ Some(self.cmp_u64(other))
+ }
+}
+impl PartialOrd<u128> for Cardinality {
+ #[inline]
+ fn partial_cmp(&self, other: &u128) -> Option<Ordering> {
+ Some(self.cmp_u128(other))
+ }
+}
+impl PartialOrd<usize> for Cardinality {
+ #[inline]
+ fn partial_cmp(&self, other: &usize) -> Option<Ordering> {
+ Some(self.cmp_usize(other))
+ }
+}
+impl PartialOrd<BigUint> for Cardinality {
+ #[inline]
+ fn partial_cmp(&self, other: &BigUint) -> Option<Ordering> {
+ Some(self.cmp_biguint(other))
+ }
+}
+/// Contains a lower and upper bound
+/// [`Cardinality`] used to bound the cardinality
+/// of a [`Set`].
+#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
+pub struct BoundedCardinality {
+ /// Lower bound.
+ lower: Cardinality,
+ /// Upper bound.
+ upper: Cardinality,
+}
+impl BoundedCardinality {
+ /// Creates an instance of `BoundedCardinality`.
+ /// Returns `None` iff `lower > upper`.
+ #[inline]
+ #[must_use]
+ pub fn new(lower: Cardinality, upper: Cardinality) -> Option<Self> {
+ if lower > upper {
+ None
+ } else {
+ Some(Self { lower, upper })
+ }
+ }
+ /// Creates an instance of `BoundedCardinality`
+ /// with the lower and upper bounds as `Cardinality::Finite`
+ /// of their respective values.
+ /// Returns `None` iff `lower > upper`.
+ #[inline]
+ #[must_use]
+ pub fn from_biguint(lower: BigUint, upper: BigUint) -> Option<Self> {
+ if lower > upper {
+ None
+ } else {
+ Some(Self {
+ lower: Cardinality::Finite(lower),
+ upper: Cardinality::Finite(upper),
+ })
+ }
+ }
+ /// Creates an instance of `BoundedCardinality`
+ /// without verifying `lower <= upper`.
+ ///
+ /// # Safety
+ ///
+ /// `lower <= upper`.
+ #[allow(unsafe_code)]
+ #[inline]
+ #[must_use]
+ pub const unsafe fn new_unsafe(lower: Cardinality, upper: Cardinality) -> Self {
+ Self { lower, upper }
+ }
+ /// Creates an instance of `BoundedCardinality`
+ /// with the lower and upper bounds as `Cardinality::Finite`
+ /// of their respective values without verifying `lower <= upper`.
+ ///
+ /// # Safety
+ ///
+ /// `lower <= upper`.
+ #[allow(unsafe_code)]
+ #[inline]
+ #[must_use]
+ pub const unsafe fn from_biguint_unsafe(lower: BigUint, upper: BigUint) -> Self {
+ Self {
+ lower: Cardinality::Finite(lower),
+ upper: Cardinality::Finite(upper),
+ }
+ }
+ /// Returns a reference to the lower bound.
+ #[inline]
+ #[must_use]
+ pub const fn lower(&self) -> &Cardinality {
+ &self.lower
+ }
+ /// Returns the lower bound.
+ #[inline]
+ #[must_use]
+ pub fn to_lower(self) -> Cardinality {
+ self.lower
+ }
+ /// Returns a reference to the upper bound.
+ #[inline]
+ #[must_use]
+ pub const fn upper(&self) -> &Cardinality {
+ &self.upper
+ }
+ /// Returns the upper bound.
+ #[inline]
+ #[must_use]
+ pub fn to_upper(self) -> Cardinality {
+ self.upper
+ }
+ /// Returns a tuple containing the references to the lower and upper bounds respectively.
+ #[inline]
+ #[must_use]
+ pub const fn lower_upper(&self) -> (&Cardinality, &Cardinality) {
+ (&self.lower, &self.upper)
+ }
+ /// Returns a reference to the contained `BigUint` of `self.lower()`.
+ #[inline]
+ #[must_use]
+ pub const fn lower_biguint(&self) -> &BigUint {
+ self.lower.as_biguint()
+ }
+ /// Returns the lower bound as a `BigUint`.
+ #[inline]
+ #[must_use]
+ pub fn to_lower_biguint(self) -> BigUint {
+ self.lower.into()
+ }
+ /// Returns a reference to the contained `BigUint` of `self.upper()`.
+ #[inline]
+ #[must_use]
+ pub const fn upper_biguint(&self) -> &BigUint {
+ self.upper.as_biguint()
+ }
+ /// Returns the upper bound as a `BigUint`.
+ #[inline]
+ #[must_use]
+ pub fn to_upper_biguint(self) -> BigUint {
+ self.upper.into()
+ }
+ /// Returns a tuple of references to the contained `BigUint`s of `self.lower()` and `self.upper()` respectively.
+ #[inline]
+ #[must_use]
+ pub const fn lower_upper_biguint(&self) -> (&BigUint, &BigUint) {
+ (self.lower_biguint(), self.upper_biguint())
+ }
+}
+impl Display for BoundedCardinality {
+ #[allow(clippy::min_ident_chars)]
+ #[inline]
+ fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
+ write!(f, "({}, {})", self.lower, self.upper)
+ }
+}
+impl fmt::Debug for BoundedCardinality {
+ #[allow(clippy::min_ident_chars)]
+ #[inline]
+ fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
+ <Self as Display>::fmt(self, f)
+ }
+}
+impl TryFrom<(Cardinality, Cardinality)> for BoundedCardinality {
+ type Error = ();
+ #[inline]
+ fn try_from(value: (Cardinality, Cardinality)) -> Result<Self, Self::Error> {
+ Self::new(value.0, value.1).ok_or(())
+ }
+}
+impl TryFrom<(BigUint, BigUint)> for BoundedCardinality {
+ type Error = ();
+ #[inline]
+ fn try_from(value: (BigUint, BigUint)) -> Result<Self, Self::Error> {
+ Self::from_biguint(value.0, value.1).ok_or(())
+ }
+}
+impl From<BoundedCardinality> for (Cardinality, Cardinality) {
+ #[inline]
+ fn from(value: BoundedCardinality) -> Self {
+ (value.lower, value.upper)
+ }
+}
+impl From<BoundedCardinality> for (BigUint, BigUint) {
+ #[inline]
+ fn from(value: BoundedCardinality) -> Self {
+ (value.lower.into(), value.upper.into())
+ }
+}
/// Represents a set according to [Zermelo–Fraenkel set theory with the axiom of choice (ZFC)](https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory).
/// Note that elements in a `Set` must not be distinguishable by order or frequency, so care must be taken in its implementation if the implementing type
/// exposes an API that distinguishes between the order or frequency of `Elem` (e.g., [`Vec<T>`](https://doc.rust-lang.org/alloc/vec/struct.Vec.html) where `Elem` = `T`).
@@ -90,8 +445,22 @@ pub trait Set {
/// The elements that make up the set.
/// Per ZFC, this must not be the same type as `Self` nor a recursive type based on `Self`.
type Elem: Eq + ?Sized;
- /// Returns the cardinality of `self`.
- fn cardinality(&self) -> Cardinality;
+ /// Returns the cardinality of `self` if it is known exactly.
+ ///
+ /// The following properties must be true:
+ /// * `self.cardinality().is_none()` ⇔ `self.bounded_cardinality().lower() < self.bounded_cardinality().upper()`.
+ /// * `self.cardinality().is_some()` ⇔ `self.cardinality().unwrap() == self.bounded_cardinality().lower()`.
+ #[inline]
+ fn cardinality(&self) -> Option<Cardinality> {
+ let bound = self.bounded_cardinality();
+ if bound.lower < bound.upper {
+ None
+ } else {
+ Some(bound.lower)
+ }
+ }
+ /// Returns the bounded cardinality of `self`.
+ fn bounded_cardinality(&self) -> BoundedCardinality;
/// Returns `true` iff `Self` contains `elem`.
fn contains<Q>(&self, elem: &Q) -> bool
where
@@ -205,8 +574,16 @@ where
{
type Elem = T;
#[inline]
- fn cardinality(&self) -> Cardinality {
- Cardinality::Finite(self.len().into())
+ fn cardinality(&self) -> Option<Cardinality> {
+ Some(Cardinality::Finite(self.len().into()))
+ }
+ #[inline]
+ fn bounded_cardinality(&self) -> BoundedCardinality {
+ let card = Cardinality::from_biguint(self.len().into());
+ BoundedCardinality {
+ lower: card.clone(),
+ upper: card,
+ }
}
#[inline]
fn contains<Q>(&self, elem: &Q) -> bool
@@ -232,8 +609,16 @@ where
{
type Elem = T;
#[inline]
- fn cardinality(&self) -> Cardinality {
- Cardinality::Finite((&self.end - &self.start).into())
+ fn cardinality(&self) -> Option<Cardinality> {
+ Some(Cardinality::Finite((&self.end - &self.start).into()))
+ }
+ #[inline]
+ fn bounded_cardinality(&self) -> BoundedCardinality {
+ let card = Cardinality::Finite((&self.end - &self.start).into());
+ BoundedCardinality {
+ lower: card.clone(),
+ upper: card,
+ }
}
#[inline]
fn contains<Q>(&self, elem: &Q) -> bool
@@ -263,8 +648,19 @@ where
{
type Elem = T;
#[inline]
- fn cardinality(&self) -> Cardinality {
- Cardinality::Finite((self.end() - self.start()).into() + BigUint::new(alloc::vec![1]))
+ fn cardinality(&self) -> Option<Cardinality> {
+ Some(Cardinality::Finite(
+ (self.end() - self.start()).into() + BigUint::new(alloc::vec![1]),
+ ))
+ }
+ #[inline]
+ fn bounded_cardinality(&self) -> BoundedCardinality {
+ let card =
+ Cardinality::Finite((self.end() - self.start()).into() + BigUint::new(alloc::vec![1]));
+ BoundedCardinality {
+ lower: card.clone(),
+ upper: card,
+ }
}
#[inline]
fn contains<Q>(&self, elem: &Q) -> bool
@@ -300,8 +696,16 @@ where
{
type Elem = T;
#[inline]
- fn cardinality(&self) -> Cardinality {
- Cardinality::Finite(self.len().into())
+ fn cardinality(&self) -> Option<Cardinality> {
+ Some(Cardinality::Finite(self.len().into()))
+ }
+ #[inline]
+ fn bounded_cardinality(&self) -> BoundedCardinality {
+ let card = Cardinality::Finite(self.len().into());
+ BoundedCardinality {
+ lower: card.clone(),
+ upper: card,
+ }
}
#[inline]
fn contains<Q>(&self, elem: &Q) -> bool
