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