#![cfg_attr(all(doc, CHANNEL_NIGHTLY), feature(doc_auto_cfg))]
#![no_std]
#![deny(
future_incompatible,
let_underscore,
missing_docs,
nonstandard_style,
rust_2018_compatibility,
rust_2018_idioms,
rust_2021_compatibility,
rust_2024_compatibility,
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::exhaustive_structs,
clippy::implicit_return,
clippy::missing_trait_methods,
clippy::ref_patterns,
clippy::single_char_lifetime_names
)]
extern crate alloc;
use alloc::collections::BTreeSet;
use core::borrow::Borrow;
use core::cmp::Ordering;
use core::fmt::{self, Display, Formatter};
use core::ops::{Range, RangeInclusive, Sub};
use num_bigint::BigUint;
#[derive(Clone, Eq, Hash, Ord, PartialEq, PartialOrd)]
#[allow(clippy::exhaustive_enums)]
pub enum Cardinality {
Finite(BigUint),
Transfinite(BigUint),
}
impl Cardinality {
#[inline]
#[must_use]
pub const fn as_biguint(&self) -> &BigUint {
match *self {
Self::Finite(ref val) | Self::Transfinite(ref val) => val,
}
}
#[inline]
#[must_use]
pub const fn from_biguint(value: BigUint) -> Self {
Self::Finite(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,
}
}
#[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,
}
}
#[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,
}
}
#[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,
}
}
#[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,
}
}
#[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,
}
}
#[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)]
#[inline]
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
match *self {
Self::Finite(ref val) => val.fmt(f),
Self::Transfinite(ref val) => write!(f, "\u{2135}_{val}"),
}
}
}
impl fmt::Debug for Cardinality {
#[allow(clippy::min_ident_chars)]
#[inline]
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
<Self as Display>::fmt(self, f)
}
}
impl From<BigUint> for Cardinality {
#[inline]
fn from(value: BigUint) -> Self {
Self::from_biguint(value)
}
}
impl TryFrom<BoundedCardinality> for Cardinality {
type Error = CardinalityErr;
#[inline]
fn try_from(value: BoundedCardinality) -> Result<Self, Self::Error> {
if value.lower == value.upper {
Ok(value.lower)
} else {
Err(CardinalityErr)
}
}
}
impl From<Cardinality> for BigUint {
#[inline]
fn from(value: Cardinality) -> Self {
match value {
Cardinality::Finite(val) | Cardinality::Transfinite(val) => val,
}
}
}
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))
}
}
#[derive(Clone, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub struct BoundedErr;
impl Display for BoundedErr {
#[allow(clippy::min_ident_chars)]
#[inline]
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
f.write_str("upper bound is greater than lower bound")
}
}
#[derive(Clone, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub struct CardinalityErr;
impl Display for CardinalityErr {
#[allow(clippy::min_ident_chars)]
#[inline]
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
f.write_str("lower bound of the BoundedCardinality is less than the upper bound")
}
}
#[derive(Clone, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub struct BoundedCardinality {
lower: Cardinality,
upper: Cardinality,
}
impl BoundedCardinality {
#[inline]
#[must_use]
pub fn new(lower: Cardinality, upper: Cardinality) -> Option<Self> {
if lower > upper {
None
} else {
Some(Self { lower, upper })
}
}
#[inline]
#[must_use]
pub fn new_exact(exact: Cardinality) -> Self {
Self {
lower: exact.clone(),
upper: exact,
}
}
#[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),
})
}
}
#[inline]
#[must_use]
pub fn from_biguint_exact(exact: BigUint) -> Self {
Self {
lower: Cardinality::Finite(exact.clone()),
upper: Cardinality::Finite(exact),
}
}
#[allow(unsafe_code)]
#[inline]
#[must_use]
pub const unsafe fn new_unsafe(lower: Cardinality, upper: Cardinality) -> Self {
Self { 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),
}
}
#[inline]
#[must_use]
pub const fn lower(&self) -> &Cardinality {
&self.lower
}
#[inline]
#[must_use]
pub fn to_lower(self) -> Cardinality {
self.lower
}
#[inline]
#[must_use]
pub const fn upper(&self) -> &Cardinality {
&self.upper
}
#[inline]
#[must_use]
pub fn to_upper(self) -> Cardinality {
self.upper
}
#[inline]
#[must_use]
pub const fn lower_upper(&self) -> (&Cardinality, &Cardinality) {
(&self.lower, &self.upper)
}
#[inline]
#[must_use]
pub const fn lower_biguint(&self) -> &BigUint {
self.lower.as_biguint()
}
#[inline]
#[must_use]
pub fn to_lower_biguint(self) -> BigUint {
self.lower.into()
}
#[inline]
#[must_use]
pub const fn upper_biguint(&self) -> &BigUint {
self.upper.as_biguint()
}
#[inline]
#[must_use]
pub fn to_upper_biguint(self) -> BigUint {
self.upper.into()
}
#[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 From<BigUint> for BoundedCardinality {
#[inline]
fn from(value: BigUint) -> Self {
Self::from_biguint_exact(value)
}
}
impl From<Cardinality> for BoundedCardinality {
#[inline]
fn from(value: Cardinality) -> Self {
Self {
lower: value.clone(),
upper: value,
}
}
}
impl TryFrom<(Cardinality, Cardinality)> for BoundedCardinality {
type Error = BoundedErr;
#[inline]
fn try_from(value: (Cardinality, Cardinality)) -> Result<Self, Self::Error> {
Self::new(value.0, value.1).ok_or(BoundedErr)
}
}
impl TryFrom<(BigUint, BigUint)> for BoundedCardinality {
type Error = BoundedErr;
#[inline]
fn try_from(value: (BigUint, BigUint)) -> Result<Self, Self::Error> {
Self::from_biguint(value.0, value.1).ok_or(BoundedErr)
}
}
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())
}
}
pub trait Set {
type Elem: Eq + ?Sized;
#[inline]
fn cardinality(&self) -> Option<Cardinality> {
let bound = self.bounded_cardinality();
if bound.lower < bound.upper {
None
} else {
Some(bound.lower)
}
}
fn bounded_cardinality(&self) -> BoundedCardinality;
fn contains<Q>(&self, elem: &Q) -> bool
where
Q: Borrow<Self::Elem> + Eq + ?Sized;
fn is_proper_subset(&self, val: &Self) -> bool;
fn is_subset(&self, val: &Self) -> bool;
#[inline]
fn is_proper_superset(&self, val: &Self) -> bool {
val.is_proper_subset(self)
}
#[inline]
fn is_superset(&self, val: &Self) -> bool {
val.is_subset(self)
}
#[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)
}
#[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)
}
#[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)
}
#[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) -> 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
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) -> 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
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) -> 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
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")]
use std::error::Error;
#[cfg(feature = "std")]
impl<T, S> Set for HashSet<T, S>
where
T: Eq + Hash,
S: BuildHasher,
{
type Elem = T;
#[inline]
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
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()
}
}
#[cfg(feature = "std")]
impl Error for BoundedErr {}
#[cfg(feature = "std")]
impl Error for CardinalityErr {}