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