commit d0519057f07b1ae329711066f87a696be54a0a23
Author: Zack Newman <zack@philomathiclife.com>
Date: Thu, 24 Aug 2023 18:10:09 -0600
init
Diffstat:
5 files changed, 340 insertions(+), 0 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -0,0 +1,2 @@
+Cargo.lock
+target/**
diff --git a/Cargo.toml b/Cargo.toml
@@ -0,0 +1,37 @@
+[package]
+authors = ["Zack Newman <zack@philomathiclife.com>"]
+categories = ["mathematics", "no-std"]
+description = "Trait that represents a set according to Zermelo–Fraenkel set theory with the axiom of choice (ZFC)"
+documentation = "https://docs.rs/zfc/latest/zfc/index.html"
+edition = "2021"
+keywords = ["math", "set", "zfc"]
+license = "MIT OR Apache-2.0"
+name = "zfc"
+readme = "README.md"
+repository = "https://git.philomathiclife.com/repos/zfc/"
+version = "0.1.0"
+
+[lib]
+name = "zfc"
+path = "src/lib.rs"
+
+[build-dependencies]
+rustc_version = "0.4.0"
+
+[features]
+std = []
+
+[dependencies]
+num-bigint = { version = "0.4.4", default-features = false }
+
+[package.metadata.docs.rs]
+all-features = true
+rustdoc-args = ["--cfg", "docsrs"]
+
+[badges]
+maintenance = { status = "actively-developed" }
+
+[profile.release]
+lto = true
+panic = 'abort'
+strip = true
diff --git a/README.md b/README.md
@@ -0,0 +1,11 @@
+# `zfc`
+
+`zfc` is a library for sets according to [Zermelo–Fraenkel set theory with the axiom of choice (ZFC)](https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory).
+
+## Status
+
+This package will be actively maintained until it is deemed “feature complete”.
+
+The crates are only tested on the `x86_64-unknown-linux-gnu` and `x86_64-unknown-openbsd` targets, but
+they should work on any [Tier 1 with Host Tools](https://doc.rust-lang.org/beta/rustc/platform-support.html)
+target.
diff --git a/build.rs b/build.rs
@@ -0,0 +1,12 @@
+use rustc_version::{version_meta, Channel};
+
+fn main() {
+ // Set cfg flags depending on release channel
+ let channel = match version_meta().unwrap().channel {
+ Channel::Stable => "CHANNEL_STABLE",
+ Channel::Beta => "CHANNEL_BETA",
+ Channel::Nightly => "CHANNEL_NIGHTLY",
+ Channel::Dev => "CHANNEL_DEV",
+ };
+ println!("cargo:rustc-cfg={}", channel)
+}
diff --git a/src/lib.rs b/src/lib.rs
@@ -0,0 +1,278 @@
+//! # `zfc`
+//!
+//! `zfc` is a library for sets according to [Zermelo–Fraenkel set theory with the axiom of choice (ZFC)](https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory).
+#![cfg_attr(all(doc, CHANNEL_NIGHTLY), feature(doc_auto_cfg))]
+#![no_std]
+#![deny(
+ unsafe_code,
+ unused,
+ warnings,
+ clippy::all,
+ clippy::cargo,
+ clippy::complexity,
+ clippy::correctness,
+ clippy::nursery,
+ clippy::pedantic,
+ clippy::perf,
+ clippy::restriction,
+ clippy::style,
+ clippy::suspicious
+)]
+#![allow(
+ clippy::arithmetic_side_effects,
+ clippy::blanket_clippy_restriction_lints,
+ clippy::implicit_return,
+ clippy::missing_trait_methods,
+ clippy::single_char_lifetime_names
+)]
+extern crate alloc;
+use alloc::collections::BTreeSet;
+use core::borrow::Borrow;
+use core::cmp::Ordering;
+use core::ops::{Range, RangeInclusive, Sub};
+use num_bigint::BigUint;
+/// Represents the quantity of elements in a [`Set`].
+#[derive(Clone, PartialEq, Eq, PartialOrd, Ord)]
+#[allow(clippy::exhaustive_enums)]
+pub enum Cardinality {
+ /// 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),
+}
+/// 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`](https://doc.rust-lang.org/alloc/vec/struct.Vec.html) where `Elem` = `T`).
+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 `true` iff `Self` contains `elem`.
+ fn contains<Q>(&self, elem: &Q) -> bool
+ where
+ Q: Borrow<Self::Elem> + Eq + ?Sized;
+ /// Must conform to the following properties:
+ /// * Irreflexivity.
+ /// * Antisymmetry.
+ /// * Transitivity.
+ /// * ∀`a`, `b`: `Self`, `a.is_proper_subset(b)`⇒ ∀`e`: `Elem` | `a.contains(e)`, `b.contains(e)` ∧ ∃`f`: `Elem`, `b.contains(f) && !a.contains(f)`.
+ /// * ∀`a`, `b`: `Self`, `a.is_proper_subset(b)` ⇒ `a.is_subset(b)`.
+ /// * ∀`a`, `b`: `Self`, `a.is_proper_subset(b)` ⇔ `b.is_proper_superset(a)`.
+ fn is_proper_subset(&self, val: &Self) -> bool;
+ /// Must conform to the following properties:
+ /// * Reflexivity.
+ /// * Antisymmetry.
+ /// * Transitivity.
+ /// * ∀`a`, `b`: `Self`, `a.is_subset(b)`⇒ ∀`e`: `Elem` | `a.contains(e)`, `b.contains(e)`.
+ /// * ∀`a`, `b`: `Self`, `a.is_subset(b)` ⇔ `b.is_superset(a)`.
+ fn is_subset(&self, val: &Self) -> bool;
+ /// Must conform to the following properties:
+ /// * Irreflexivity.
+ /// * Antisymmetry.
+ /// * Transitivity.
+ /// * ∀`a`, `b`: `Self`, `a.is_proper_superset(b)` ⇒ `a.is_superset(b)`.
+ #[inline]
+ fn is_proper_superset(&self, val: &Self) -> bool {
+ val.is_proper_subset(self)
+ }
+ /// Must conform to the following properties:
+ /// * Reflexivity.
+ /// * Antisymmetry.
+ /// * Transitivity.
+ #[inline]
+ fn is_superset(&self, val: &Self) -> bool {
+ val.is_subset(self)
+ }
+ /// Read [`Set::is_proper_subset`].
+ #[inline]
+ fn is_proper_subset_iter<T>(&self, val: &T) -> bool
+ where
+ Self::Elem: Borrow<T::Elem> + PartialEq<T::Elem>,
+ for<'a> &'a Self: IntoIterator<Item = &'a Self::Elem>,
+ T: Set + ?Sized,
+ T::Elem: PartialEq<Self::Elem>,
+ {
+ self.cardinality() < val.cardinality()
+ && self
+ .into_iter()
+ .try_fold(
+ (),
+ |(), elem| {
+ if val.contains(elem) {
+ Ok(())
+ } else {
+ Err(())
+ }
+ },
+ )
+ .map_or(false, |()| true)
+ }
+ /// Read [`Set::is_subset`].
+ #[inline]
+ fn is_subset_iter<T>(&self, val: &T) -> bool
+ where
+ Self::Elem: Borrow<T::Elem> + PartialEq<T::Elem>,
+ for<'a> &'a Self: IntoIterator<Item = &'a Self::Elem>,
+ T: Set + ?Sized,
+ T::Elem: PartialEq<Self::Elem>,
+ {
+ self.cardinality() <= val.cardinality()
+ && self
+ .into_iter()
+ .try_fold(
+ (),
+ |(), elem| {
+ if val.contains(elem) {
+ Ok(())
+ } else {
+ Err(())
+ }
+ },
+ )
+ .map_or(false, |()| true)
+ }
+ /// Read [`Set::is_proper_superset`].
+ #[inline]
+ fn is_proper_superset_iter<T>(&self, val: &T) -> bool
+ where
+ Self::Elem: PartialEq<T::Elem>,
+ T: Set + ?Sized,
+ for<'a> &'a T: IntoIterator<Item = &'a T::Elem>,
+ T::Elem: Borrow<Self::Elem> + PartialEq<Self::Elem>,
+ {
+ val.is_proper_subset_iter(self)
+ }
+ /// Read [`Set::is_superset`].
+ #[inline]
+ fn is_superset_iter<T>(&self, val: &T) -> bool
+ where
+ Self::Elem: PartialEq<T::Elem>,
+ T: Set + ?Sized,
+ for<'a> &'a T: IntoIterator<Item = &'a T::Elem>,
+ T::Elem: Borrow<Self::Elem> + PartialEq<Self::Elem>,
+ {
+ val.is_subset_iter(self)
+ }
+}
+impl<T> Set for BTreeSet<T>
+where
+ T: Ord,
+{
+ type Elem = T;
+ #[inline]
+ fn cardinality(&self) -> Cardinality {
+ Cardinality::Finite(self.len().into())
+ }
+ #[inline]
+ fn contains<Q>(&self, elem: &Q) -> bool
+ where
+ Q: Borrow<Self::Elem> + Eq + ?Sized,
+ {
+ self.contains(elem.borrow())
+ }
+ #[inline]
+ fn is_proper_subset(&self, val: &Self) -> bool {
+ self.len() < val.len() && self.intersection(val).count() == val.len()
+ }
+ #[inline]
+ fn is_subset(&self, val: &Self) -> bool {
+ self.len() <= val.len() && self.intersection(val).count() == val.len()
+ }
+}
+impl<T> Set for Range<T>
+where
+ T: Ord,
+ for<'a, 'b> &'a T: Sub<&'b T>,
+ for<'a, 'b> <&'a T as Sub<&'b T>>::Output: Into<BigUint>,
+{
+ type Elem = T;
+ #[inline]
+ fn cardinality(&self) -> Cardinality {
+ Cardinality::Finite((&self.end - &self.start).into())
+ }
+ #[inline]
+ fn contains<Q>(&self, elem: &Q) -> bool
+ where
+ Q: Borrow<Self::Elem> + Eq + ?Sized,
+ {
+ self.contains(elem.borrow())
+ }
+ #[inline]
+ fn is_proper_subset(&self, val: &Self) -> bool {
+ match self.start.cmp(&val.start) {
+ Ordering::Less => false,
+ Ordering::Equal => self.end < val.end,
+ Ordering::Greater => self.end <= val.end,
+ }
+ }
+ #[inline]
+ fn is_subset(&self, val: &Self) -> bool {
+ self.start >= val.start && self.end <= val.end
+ }
+}
+impl<T> Set for RangeInclusive<T>
+where
+ T: Ord,
+ for<'a, 'b> &'a T: Sub<&'b T>,
+ for<'a, 'b> <&'a T as Sub<&'b T>>::Output: Into<BigUint>,
+{
+ type Elem = T;
+ #[inline]
+ fn cardinality(&self) -> Cardinality {
+ Cardinality::Finite((self.end() - self.start()).into() + BigUint::new(alloc::vec![1]))
+ }
+ #[inline]
+ fn contains<Q>(&self, elem: &Q) -> bool
+ where
+ Q: Borrow<Self::Elem> + Eq + ?Sized,
+ {
+ self.contains(elem.borrow())
+ }
+ #[inline]
+ fn is_proper_subset(&self, val: &Self) -> bool {
+ match self.start().cmp(val.start()) {
+ Ordering::Less => false,
+ Ordering::Equal => self.end() < val.end(),
+ Ordering::Greater => self.end() <= val.end(),
+ }
+ }
+ #[inline]
+ fn is_subset(&self, val: &Self) -> bool {
+ self.start() >= val.start() && self.end() <= val.end()
+ }
+}
+#[cfg(feature = "std")]
+extern crate std;
+#[cfg(feature = "std")]
+use core::hash::{BuildHasher, Hash};
+#[cfg(feature = "std")]
+use std::collections::HashSet;
+#[cfg(feature = "std")]
+impl<T, S> Set for HashSet<T, S>
+where
+ T: Eq + Hash,
+ S: BuildHasher,
+{
+ type Elem = T;
+ #[inline]
+ fn cardinality(&self) -> Cardinality {
+ Cardinality::Finite(self.len().into())
+ }
+ #[inline]
+ fn contains<Q>(&self, elem: &Q) -> bool
+ where
+ Q: Borrow<Self::Elem> + Eq + ?Sized,
+ {
+ self.contains(elem.borrow())
+ }
+ #[inline]
+ fn is_proper_subset(&self, val: &Self) -> bool {
+ self.len() < val.len() && self.intersection(val).count() == val.len()
+ }
+ #[inline]
+ fn is_subset(&self, val: &Self) -> bool {
+ self.len() <= val.len() && self.intersection(val).count() == val.len()
+ }
+}
