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