superset_set.rs (28603B)
1 extern crate alloc; 2 /// Unit tests. 3 #[cfg(test)] 4 mod tests; 5 use crate::{ 6 SetOrd, SupersetMap, 7 zfc::{BoundedCardinality, Cardinality, Set}, 8 }; 9 use alloc::collections::btree_map::{self, IntoKeys, Keys}; 10 use core::{ 11 borrow::Borrow, 12 hash::{Hash, Hasher}, 13 iter::FusedIterator, 14 ops::{BitAnd, BitOr, Bound, RangeBounds}, 15 }; 16 /// A lazy iterator producing elements in the intersection of `SupersetSet`s. 17 /// 18 /// This `struct` is created by [`SupersetSet::intersection`]. 19 #[expect(missing_debug_implementations, reason = "Iter does not, so we do not")] 20 #[derive(Clone)] 21 pub struct Intersection<'a, T> { 22 /// Iterator for the first `SupersetSet`. 23 iter_1: Iter<'a, T>, 24 /// Iterator for the second `SupersetSet`. 25 iter_2: Iter<'a, T>, 26 /// Previous value iterated from `iter_1`. 27 /// `prev_1` and `prev_2` will never both be `Some`. 28 prev_1: Option<&'a T>, 29 /// Previous value iterated from `iter_2`. 30 prev_2: Option<&'a T>, 31 } 32 impl<T> FusedIterator for Intersection<'_, T> where T: SetOrd {} 33 impl<'a, T> Iterator for Intersection<'a, T> 34 where 35 T: SetOrd, 36 { 37 type Item = &'a T; 38 #[inline] 39 fn next(&mut self) -> Option<Self::Item> { 40 loop { 41 if let Some(prev1) = self.prev_1 { 42 if let Some(cur2) = self.iter_2.next() { 43 if prev1 <= cur2 { 44 self.prev_1 = None; 45 self.prev_2 = Some(cur2); 46 if prev1.is_subset(cur2) { 47 return Some(prev1); 48 } 49 } else if cur2.is_proper_subset(prev1) { 50 return Some(cur2); 51 } else { 52 // Do nothing. 53 } 54 } else { 55 self.prev_1 = None; 56 return None; 57 } 58 } else if let Some(prev2) = self.prev_2 { 59 if let Some(cur1) = self.iter_1.next() { 60 if prev2 <= cur1 { 61 self.prev_2 = None; 62 self.prev_1 = Some(cur1); 63 if prev2.is_subset(cur1) { 64 return Some(prev2); 65 } 66 } else if cur1.is_proper_subset(prev2) { 67 return Some(cur1); 68 } else { 69 // Do nothing. 70 } 71 } else { 72 self.prev_1 = None; 73 return None; 74 } 75 } else if let Some(cur1) = self.iter_1.next() { 76 if let Some(cur2) = self.iter_2.next() { 77 if cur1 <= cur2 { 78 self.prev_2 = Some(cur2); 79 if cur1.is_subset(cur2) { 80 return Some(cur1); 81 } 82 } else if cur2.is_proper_subset(cur1) { 83 self.prev_1 = Some(cur1); 84 return Some(cur2); 85 } else { 86 // Do nothing. 87 } 88 } else { 89 return None; 90 } 91 } else { 92 return None; 93 } 94 } 95 } 96 } 97 /// An owning iterator over the items of a `SupersetSet`. 98 /// 99 /// This `struct` is created by [`SupersetSet::into_iter`] (provided by [`IntoIterator`]). 100 #[derive(Debug)] 101 pub struct IntoIter<T> { 102 /// Iterator of the values in a `SupersetSet`. 103 iter: IntoKeys<T, ()>, 104 } 105 impl<T> Default for IntoIter<T> { 106 #[inline] 107 fn default() -> Self { 108 Self { 109 iter: IntoKeys::default(), 110 } 111 } 112 } 113 impl<T> DoubleEndedIterator for IntoIter<T> { 114 #[inline] 115 fn next_back(&mut self) -> Option<Self::Item> { 116 self.iter.next_back() 117 } 118 } 119 impl<T> ExactSizeIterator for IntoIter<T> { 120 #[inline] 121 fn len(&self) -> usize { 122 self.iter.len() 123 } 124 } 125 impl<T> FusedIterator for IntoIter<T> {} 126 impl<T> Iterator for IntoIter<T> { 127 type Item = T; 128 #[inline] 129 fn next(&mut self) -> Option<Self::Item> { 130 self.iter.next() 131 } 132 } 133 /// An iterator over the items of a `SupersetSet`. 134 /// 135 /// This `struct` is created by [`SupersetSet::iter`]. 136 #[derive(Clone, Debug)] 137 pub struct Iter<'a, T> { 138 /// Iterator of the values in a `SupersetSet`. 139 iter: Keys<'a, T, ()>, 140 } 141 impl<T> Default for Iter<'_, T> { 142 #[inline] 143 fn default() -> Self { 144 Self { 145 iter: Keys::default(), 146 } 147 } 148 } 149 impl<T> DoubleEndedIterator for Iter<'_, T> { 150 #[inline] 151 fn next_back(&mut self) -> Option<Self::Item> { 152 self.iter.next_back() 153 } 154 } 155 impl<T> ExactSizeIterator for Iter<'_, T> { 156 #[inline] 157 fn len(&self) -> usize { 158 self.iter.len() 159 } 160 } 161 impl<T> FusedIterator for Iter<'_, T> {} 162 impl<'a, T> Iterator for Iter<'a, T> { 163 type Item = &'a T; 164 #[inline] 165 fn next(&mut self) -> Option<Self::Item> { 166 self.iter.next() 167 } 168 } 169 /// An iterator over a sub-range of items in a `SupersetSet`. 170 /// 171 /// This `struct` is created by [`SupersetSet::range`]. 172 #[derive(Clone, Debug)] 173 pub struct Range<'a, T> { 174 /// Range iterator for a `SupersetSet`. 175 iter: btree_map::Range<'a, T, ()>, 176 } 177 impl<T> Default for Range<'_, T> { 178 #[inline] 179 fn default() -> Self { 180 Self { 181 iter: btree_map::Range::default(), 182 } 183 } 184 } 185 impl<T> DoubleEndedIterator for Range<'_, T> { 186 #[inline] 187 fn next_back(&mut self) -> Option<Self::Item> { 188 self.iter.next_back().map(|(key, &())| key) 189 } 190 } 191 impl<T> FusedIterator for Range<'_, T> {} 192 impl<'a, T> Iterator for Range<'a, T> { 193 type Item = &'a T; 194 #[inline] 195 fn next(&mut self) -> Option<Self::Item> { 196 self.iter.next().map(|(key, &())| key) 197 } 198 } 199 /// A minimal collection of `T`s. 200 /// 201 /// Internally it is based on a [`SupersetMap`]. When a `T` is [`SupersetSet::insert`]ed, it won't actually be 202 /// inserted unless there isn't a `T` already in the set that is a superset of it. In such event, all `T`s that 203 /// are subsets of the to-be-inserted `T` are removed before inserting the `T`. 204 /// 205 /// Note this can have quite good performance due to the fact that a single search is necessary to detect if 206 /// insertion should occur; furthermore since all subsets occur immediately before where the value will be inserted, 207 /// a simple linear scan is sufficient to remove subsets avoiding the need to search the entire set. 208 #[derive(Clone, Debug, Eq, Ord, PartialEq, PartialOrd)] 209 pub struct SupersetSet<T> { 210 /// Collection of `T`s. 211 map: SupersetMap<T, ()>, 212 } 213 impl<T> SupersetSet<T> { 214 /// Read [`BTreeSet::clear`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.clear). 215 #[inline] 216 pub fn clear(&mut self) { 217 self.map.clear(); 218 } 219 /// Read [`BTreeSet::is_empty`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.is_empty). 220 #[inline] 221 #[must_use] 222 pub fn is_empty(&self) -> bool { 223 self.map.is_empty() 224 } 225 /// Read [`BTreeSet::iter`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.iter). 226 #[inline] 227 #[must_use] 228 pub fn iter(&self) -> Iter<'_, T> { 229 Iter { 230 iter: self.map.keys(), 231 } 232 } 233 /// Read [`BTreeSet::len`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.len). 234 #[inline] 235 #[must_use] 236 pub fn len(&self) -> usize { 237 self.map.len() 238 } 239 /// Makes a new, empty `SupersetSet`. 240 /// Does not allocate anything on its own. 241 #[inline] 242 #[must_use] 243 pub const fn new() -> Self { 244 Self { 245 map: SupersetMap::new(), 246 } 247 } 248 } 249 impl<T> SupersetSet<T> 250 where 251 T: Ord, 252 { 253 /// Read [`BTreeSet::contains`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.contains). 254 #[expect(clippy::same_name_method, reason = "consistent with BTreeSet")] 255 #[inline] 256 pub fn contains<Q>(&self, value: &Q) -> bool 257 where 258 T: Borrow<Q>, 259 Q: Ord + ?Sized, 260 { 261 self.map.contains_key(value) 262 } 263 /// Read [`BTreeSet::first`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.first). 264 #[inline] 265 #[must_use] 266 pub fn first(&self) -> Option<&T> { 267 self.map.first_key_value().map(|(key, &())| key) 268 } 269 /// Read [`BTreeSet::get`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.get). 270 #[inline] 271 pub fn get<Q>(&self, value: &Q) -> Option<&T> 272 where 273 T: Borrow<Q>, 274 Q: Ord + ?Sized, 275 { 276 self.map.get_key_value(value).map(|(key, &())| key) 277 } 278 /// Read [`BTreeSet::last`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.last). 279 #[inline] 280 #[must_use] 281 pub fn last(&self) -> Option<&T> { 282 self.map.last_key_value().map(|(key, &())| key) 283 } 284 /// Read [`BTreeSet::pop_first`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.pop_first). 285 #[inline] 286 pub fn pop_first(&mut self) -> Option<T> { 287 self.map.pop_first().map(|(key, ())| key) 288 } 289 /// Read [`BTreeSet::pop_last`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.pop_last). 290 #[inline] 291 pub fn pop_last(&mut self) -> Option<T> { 292 self.map.pop_last().map(|(key, ())| key) 293 } 294 /// Read [`BTreeSet::range`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.range). 295 #[inline] 296 pub fn range<K, R>(&self, range: R) -> Range<'_, T> 297 where 298 T: Borrow<K>, 299 K: Ord + ?Sized, 300 R: RangeBounds<K>, 301 { 302 Range { 303 iter: self.map.range(range), 304 } 305 } 306 /// Read [`BTreeSet::remove`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.remove). 307 #[inline] 308 pub fn remove<Q>(&mut self, value: &Q) -> bool 309 where 310 T: Borrow<Q>, 311 Q: Ord + ?Sized, 312 { 313 self.map.remove(value).is_some() 314 } 315 /// Read [`BTreeSet::split_off`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.split_off). 316 #[inline] 317 #[must_use] 318 pub fn split_off<Q>(&mut self, value: &Q) -> Self 319 where 320 T: Borrow<Q>, 321 Q: Ord + ?Sized, 322 { 323 Self { 324 map: self.map.split_off(value), 325 } 326 } 327 /// Read [`BTreeSet::take`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.take). 328 #[inline] 329 pub fn take<Q>(&mut self, value: &Q) -> Option<T> 330 where 331 T: Borrow<Q>, 332 Q: Ord + ?Sized, 333 { 334 self.map.remove_entry(value).map(|(key, ())| key) 335 } 336 } 337 impl<T> SupersetSet<T> 338 where 339 T: SetOrd, 340 { 341 /// Moves all elements from `other` into `self`, consuming `other`. 342 /// If a value from `other` is a proper superset of a value in `self`, the respective value from `self` will be removed before inserting 343 /// the value from `other`. 344 /// If a value from `other` is a subset of a value in `self`, it won't be inserted. 345 #[inline] 346 pub fn append(&mut self, other: Self) { 347 self.map.append(other.map); 348 } 349 /// Returns `true` if the set contains a proper subset of the specified value. 350 /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type. 351 #[inline] 352 pub fn contains_proper_subset<Q>(&self, value: &Q) -> bool 353 where 354 T: Borrow<Q>, 355 Q: SetOrd + ?Sized, 356 { 357 self.map.contains_proper_subset(value) 358 } 359 /// Returns `true` if the set contains a proper superset of the specified value. 360 /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type. 361 #[inline] 362 pub fn contains_proper_superset<Q>(&self, value: &Q) -> bool 363 where 364 T: Borrow<Q>, 365 Q: SetOrd + ?Sized, 366 { 367 self.map.contains_proper_superset(value) 368 } 369 /// Returns `true` if the set contains a subset of the specified value. 370 /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type. 371 #[inline] 372 pub fn contains_subset<Q>(&self, value: &Q) -> bool 373 where 374 T: Borrow<Q>, 375 Q: SetOrd + ?Sized, 376 { 377 self.map.contains_subset(value) 378 } 379 /// Returns `true` if the set contains a superset of the specified value. 380 /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type. 381 #[inline] 382 pub fn contains_superset<Q>(&self, value: &Q) -> bool 383 where 384 T: Borrow<Q>, 385 Q: SetOrd + ?Sized, 386 { 387 self.map.contains_superset(value) 388 } 389 /// Returns a reference to the value corresponding to the greatest proper subset of the passed value. 390 /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type. 391 #[inline] 392 pub fn get_greatest_proper_subset<Q>(&self, value: &Q) -> Option<&T> 393 where 394 T: Borrow<Q>, 395 Q: SetOrd + ?Sized, 396 { 397 self.map 398 .get_greatest_proper_subset_key_value(value) 399 .map(|(key, &())| key) 400 } 401 /// Returns a reference to the value corresponding to the greatest subset of the passed value. 402 /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type. 403 #[inline] 404 pub fn get_greatest_subset<Q>(&self, value: &Q) -> Option<&T> 405 where 406 T: Borrow<Q>, 407 Q: SetOrd + ?Sized, 408 { 409 self.map 410 .get_greatest_subset_key_value(value) 411 .map(|(key, &())| key) 412 } 413 /// Returns a reference to the value corresponding to the least proper superset of the passed value. 414 /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type. 415 #[inline] 416 pub fn get_least_proper_superset<Q>(&self, value: &Q) -> Option<&T> 417 where 418 T: Borrow<Q>, 419 Q: SetOrd + ?Sized, 420 { 421 self.map 422 .get_least_proper_superset_key_value(value) 423 .map(|(key, &())| key) 424 } 425 /// Returns a reference to the value corresponding to the least superset of the passed value. 426 /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type. 427 #[inline] 428 pub fn get_least_superset<Q>(&self, value: &Q) -> Option<&T> 429 where 430 T: Borrow<Q>, 431 Q: SetOrd + ?Sized, 432 { 433 self.map 434 .get_least_superset_key_value(value) 435 .map(|(key, &())| key) 436 } 437 /// `value` is inserted iff there doesn't already 438 /// exist a `T` that is a superset of `value`. 439 /// In the event `value` will be inserted, all `T`s 440 /// where the `T` is a subset of `value` are first removed before 441 /// inserting. 442 #[inline] 443 pub fn insert(&mut self, value: T) -> bool { 444 self.map.insert(value, ()) 445 } 446 /// Visits the elements representing the intersection, i.e., the subsets of elements that are both in `self` and `other`, in ascending order. 447 /// For example if `self` contains a sequence of sets each of which being a subset of the same set in `other`, then only the subsets in `self` will be iterated. 448 #[inline] 449 #[must_use] 450 pub fn intersection<'a>(&'a self, other: &'a Self) -> Intersection<'a, T> { 451 Intersection { 452 iter_1: self.into_iter(), 453 iter_2: other.into_iter(), 454 prev_1: None, 455 prev_2: None, 456 } 457 } 458 /// Removes the greatest proper subset of value from the set, returning the value if one existed. 459 /// The value may be any borrowed form of the set's value type, but the ordering on the borrowed form must match the ordering on the value type. 460 #[inline] 461 pub fn remove_greatest_proper_subset<Q>(&mut self, value: &Q) -> Option<T> 462 where 463 T: Borrow<Q>, 464 Q: SetOrd + ?Sized, 465 { 466 self.map 467 .remove_greatest_proper_subset(value) 468 .map(|(key, ())| key) 469 } 470 /// Removes the greatest subset of value from the set, returning the value if one existed. 471 /// The value may be any borrowed form of the set's value type, but the ordering on the borrowed form must match the ordering on the value type. 472 #[inline] 473 pub fn remove_greatest_subset<Q>(&mut self, value: &Q) -> Option<T> 474 where 475 T: Borrow<Q>, 476 Q: SetOrd + ?Sized, 477 { 478 self.map.remove_greatest_subset(value).map(|(key, ())| key) 479 } 480 /// Removes the least proper superset of value from the set, returning the value if one existed. 481 /// The value may be any borrowed form of the set's value type, but the ordering on the borrowed form must match the ordering on the value type. 482 #[inline] 483 pub fn remove_least_proper_superset<Q>(&mut self, value: &Q) -> Option<T> 484 where 485 T: Borrow<Q>, 486 Q: SetOrd + ?Sized, 487 { 488 self.map 489 .remove_least_proper_superset(value) 490 .map(|(key, ())| key) 491 } 492 /// Removes the least superset of value from the set, returning the value if one existed. 493 /// The value may be any borrowed form of the set's value type, but the ordering on the borrowed form must match the ordering on the value type. 494 #[inline] 495 pub fn remove_least_superset<Q>(&mut self, value: &Q) -> Option<T> 496 where 497 T: Borrow<Q>, 498 Q: SetOrd + ?Sized, 499 { 500 self.map.remove_least_superset(value).map(|(key, ())| key) 501 } 502 /// Removes all proper subsets of value from the set, returning the count removed. 503 /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type. 504 /// # Overflow Behavior 505 /// 506 /// The method does no guarding against overflows, so the removal of more than `usize::MAX` elements either produces the wrong result or panics. If debug assertions are enabled, a panic is guaranteed. 507 /// # Panics 508 /// 509 /// This function might panic if the number of elements removed is greater than `usize::MAX`. 510 #[inline] 511 pub fn remove_proper_subsets<Q>(&mut self, value: &Q) -> usize 512 where 513 T: Borrow<Q>, 514 Q: SetOrd + ?Sized, 515 { 516 self.map.remove_proper_subsets(value) 517 } 518 /// Removes all proper supersets of value from the set, returning the count removed. 519 /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type. 520 /// # Overflow Behavior 521 /// 522 /// The method does no guarding against overflows, so the removal of more than `usize::MAX` elements either produces the wrong result or panics. If debug assertions are enabled, a panic is guaranteed. 523 /// # Panics 524 /// 525 /// This function might panic if the number of elements removed is greater than `usize::MAX`. 526 #[inline] 527 pub fn remove_proper_supersets<Q>(&mut self, value: &Q) -> usize 528 where 529 T: Borrow<Q>, 530 Q: SetOrd + ?Sized, 531 { 532 self.map.remove_proper_supersets(value) 533 } 534 /// Removes all subsets of value from the set, returning the count removed. 535 /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type. 536 /// # Overflow Behavior 537 /// 538 /// The method does no guarding against overflows, so the removal of more than `usize::MAX` elements either produces the wrong result or panics. If debug assertions are enabled, a panic is guaranteed. 539 /// # Panics 540 /// 541 /// This function might panic if the number of elements removed is greater than `usize::MAX`. 542 #[inline] 543 pub fn remove_subsets<Q>(&mut self, value: &Q) -> usize 544 where 545 T: Borrow<Q>, 546 Q: SetOrd + ?Sized, 547 { 548 self.map.remove_subsets(value) 549 } 550 /// Removes all supersets of value from the set, returning the count removed. 551 /// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type. 552 /// # Overflow Behavior 553 /// 554 /// The method does no guarding against overflows, so the removal of more than `usize::MAX` elements either produces the wrong result or panics. If debug assertions are enabled, a panic is guaranteed. 555 /// # Panics 556 /// 557 /// This function might panic if the number of elements removed is greater than `usize::MAX`. 558 #[inline] 559 pub fn remove_supersets<Q>(&mut self, value: &Q) -> usize 560 where 561 T: Borrow<Q>, 562 Q: SetOrd + ?Sized, 563 { 564 self.map.remove_supersets(value) 565 } 566 /// Adds a value to the set iff there doesn't already exist a proper superset of it. 567 /// In the event a value that is equal to it already exists, then it is replaced and returned. 568 #[inline] 569 pub fn replace(&mut self, value: T) -> Option<T> { 570 let prev = { 571 let mut cursor = self.map.lower_bound_mut(Bound::Included(&value)); 572 if let Some(ge) = cursor.next() { 573 if *ge.0 == value { 574 cursor.remove_prev().map(|(key, ())| key) 575 } else { 576 None 577 } 578 } else { 579 None 580 } 581 }; 582 _ = self.insert(value); 583 prev 584 } 585 /// Retains only the elements specified by the predicate. 586 /// In other words, remove all `t`s for which `f(&t)` returns `false`. The elements are visited in ascending value order. 587 #[inline] 588 pub fn retain<F>(&mut self, mut f: F) 589 where 590 F: FnMut(&T) -> bool, 591 { 592 self.map.retain(|key, &mut ()| f(key)); 593 } 594 /// Visits the elements representing the union, i.e., the supersets of elements that are in `self` or `other`, in ascending order. 595 /// For example if `self` contains a sequence of sets each of which being a subset of the same set in `other`, then only the superset in `other` will be iterated. 596 /// The items iterated and the order in which they are iterated will match exactly as if one iterated `self` after `append`ing `other` to it. 597 #[inline] 598 #[must_use] 599 pub fn union<'a>(&'a self, other: &'a Self) -> Union<'a, T> { 600 Union { 601 iter_1: self.into_iter(), 602 iter_2: other.into_iter(), 603 prev_1: None, 604 prev_2: None, 605 } 606 } 607 } 608 impl<T> BitAnd<Self> for &SupersetSet<T> 609 where 610 T: Clone + SetOrd, 611 { 612 type Output = SupersetSet<T>; 613 #[inline] 614 fn bitand(self, rhs: Self) -> Self::Output { 615 self.intersection(rhs).cloned().collect() 616 } 617 } 618 impl<T> BitOr<Self> for &SupersetSet<T> 619 where 620 T: Clone + SetOrd, 621 { 622 type Output = SupersetSet<T>; 623 #[inline] 624 fn bitor(self, rhs: Self) -> Self::Output { 625 self.union(rhs).cloned().collect() 626 } 627 } 628 impl<T> Default for SupersetSet<T> { 629 #[inline] 630 fn default() -> Self { 631 Self::new() 632 } 633 } 634 impl<T> Extend<T> for SupersetSet<T> 635 where 636 T: SetOrd, 637 { 638 #[inline] 639 fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) { 640 self.map.extend(iter.into_iter().map(|val| (val, ()))); 641 } 642 } 643 impl<'a, T> Extend<&'a T> for SupersetSet<T> 644 where 645 T: SetOrd + Copy, 646 { 647 #[inline] 648 fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) { 649 self.map.extend(iter.into_iter().map(|val| (val, &()))); 650 } 651 } 652 impl<T, const N: usize> From<[T; N]> for SupersetSet<T> 653 where 654 T: SetOrd, 655 { 656 #[inline] 657 fn from(value: [T; N]) -> Self { 658 let mut set = Self::new(); 659 set.extend(value); 660 set 661 } 662 } 663 impl<T> FromIterator<T> for SupersetSet<T> 664 where 665 T: SetOrd, 666 { 667 #[inline] 668 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self { 669 let mut set = Self::new(); 670 set.extend(iter); 671 set 672 } 673 } 674 impl<T> Hash for SupersetSet<T> 675 where 676 T: Hash, 677 { 678 #[inline] 679 fn hash<H: Hasher>(&self, state: &mut H) { 680 self.map.hash(state); 681 } 682 } 683 impl<T> IntoIterator for SupersetSet<T> { 684 type Item = T; 685 type IntoIter = IntoIter<T>; 686 #[inline] 687 fn into_iter(self) -> Self::IntoIter { 688 IntoIter { 689 iter: self.map.into_keys(), 690 } 691 } 692 } 693 impl<'a, T> IntoIterator for &'a SupersetSet<T> { 694 type Item = &'a T; 695 type IntoIter = Iter<'a, T>; 696 #[inline] 697 fn into_iter(self) -> Self::IntoIter { 698 self.iter() 699 } 700 } 701 impl<T> Set for SupersetSet<T> 702 where 703 T: SetOrd, 704 { 705 type Elem = T; 706 #[inline] 707 fn bounded_cardinality(&self) -> BoundedCardinality { 708 BoundedCardinality::from_biguint_exact(self.len().into()) 709 } 710 #[inline] 711 fn cardinality(&self) -> Option<Cardinality> { 712 Some(Cardinality::Finite(self.len().into())) 713 } 714 #[inline] 715 fn contains<Q>(&self, elem: &Q) -> bool 716 where 717 Q: Borrow<Self::Elem> + Eq + ?Sized, 718 { 719 self.contains(elem.borrow()) 720 } 721 #[inline] 722 fn is_proper_subset(&self, val: &Self) -> bool { 723 self.len() < val.len() && self.intersection(val).count() == val.len() 724 } 725 #[inline] 726 fn is_subset(&self, val: &Self) -> bool { 727 self.len() <= val.len() && self.intersection(val).count() == val.len() 728 } 729 } 730 /// A lazy iterator producing elements in the union of `SupersetSet`s. 731 /// 732 /// This `struct` is created by [`SupersetSet::union`]. 733 #[expect(missing_debug_implementations, reason = "Iter does not, so we do not")] 734 #[derive(Clone)] 735 pub struct Union<'a, T> { 736 /// Iterator from the first `SupersetSet`. 737 iter_1: Iter<'a, T>, 738 /// Iterator from the second `SupersetSet`. 739 iter_2: Iter<'a, T>, 740 /// Previous value iterated form `iter_1`. 741 /// `prev_1` and `prev_2` are never both `Some`. 742 prev_1: Option<&'a T>, 743 /// Previous value iterated form `iter_2`. 744 prev_2: Option<&'a T>, 745 } 746 impl<T> FusedIterator for Union<'_, T> where T: SetOrd {} 747 impl<'a, T> Iterator for Union<'a, T> 748 where 749 T: SetOrd, 750 { 751 type Item = &'a T; 752 #[inline] 753 fn next(&mut self) -> Option<Self::Item> { 754 loop { 755 if let Some(prev1) = self.prev_1 { 756 if let Some(cur2) = self.iter_2.next() { 757 if prev1 >= cur2 { 758 if !prev1.is_superset(cur2) { 759 return Some(cur2); 760 } 761 } else if cur2.is_proper_superset(prev1) { 762 self.prev_1 = None; 763 self.prev_2 = Some(cur2); 764 } else { 765 self.prev_2 = Some(cur2); 766 return self.prev_1.take(); 767 } 768 } else { 769 return self.prev_1.take(); 770 } 771 } else if let Some(prev2) = self.prev_2 { 772 if let Some(cur1) = self.iter_1.next() { 773 if prev2 >= cur1 { 774 if !prev2.is_superset(cur1) { 775 return Some(cur1); 776 } 777 } else if cur1.is_proper_superset(prev2) { 778 self.prev_1 = Some(cur1); 779 self.prev_2 = None; 780 } else { 781 self.prev_1 = Some(cur1); 782 return self.prev_2.take(); 783 } 784 } else { 785 return self.prev_2.take(); 786 } 787 } else if let Some(cur1) = self.iter_1.next() { 788 if let Some(cur2) = self.iter_2.next() { 789 if cur1 >= cur2 { 790 self.prev_1 = Some(cur1); 791 if !cur1.is_superset(cur2) { 792 return Some(cur2); 793 } 794 } else if cur2.is_proper_superset(cur1) { 795 self.prev_2 = Some(cur2); 796 } else { 797 self.prev_2 = Some(cur2); 798 return Some(cur1); 799 } 800 } else { 801 return Some(cur1); 802 } 803 } else { 804 return self.iter_2.next(); 805 } 806 } 807 } 808 }