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