1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873
//! This module contains utility functionality needed for this crate. Most //! prominently, it contains the definition of the [USizeSet] used for storing //! cell options for strategies. use std::mem; use std::ops::{ BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Sub, SubAssign }; use std::slice::Iter; /// A set of `usize` that is implemented as a bit vector. Each `usize` that is /// in the range of possible elements is represented by one bit in a vector of /// numbers. This generally has better performance than a `HashSet`. #[derive(Clone, Debug, Eq, PartialEq)] pub struct USizeSet { min: usize, max: usize, len: usize, content: Vec<u64> } /// An enumeration of the errors that can happen when using a [USizeSet]. #[derive(Debug, Eq, PartialEq)] pub enum USizeSetError { /// Indicates that the bounds provided in the constructor are invalid, that /// is, the minimum is greater than the maximum. InvalidBounds, /// Indicates that an operation was performed on two or more `USizeSet`s /// with different bounds. DifferentBounds, /// Indicates that a number that was queried to be inserted or removed is /// out of the bounds of the `USizeSet` in question. OutOfBounds } /// Syntactic sugar for `Result<V, USizeSetError>`. pub type USizeSetResult<V> = Result<V, USizeSetError>; struct BitIterator { bit_index: usize, value: u64 } impl BitIterator { fn new(value: u64) -> BitIterator { BitIterator { bit_index: 0, value } } fn progress(&mut self) { let diff = self.value.trailing_zeros() as usize; self.value >>= diff; self.bit_index += diff; } } impl Iterator for BitIterator { type Item = usize; fn next(&mut self) -> Option<usize> { if self.value != 0 && (self.value & 1) == 0 { self.progress(); } let result = if self.value == 0 { None } else { Some(self.bit_index) }; self.value &= 0xfffffffffffffffe; result } } /// An iterator over the content of a [USizeSet]. pub struct USizeSetIter<'a> { offset: usize, current: BitIterator, content: Iter<'a, u64> } impl<'a> USizeSetIter<'a> { fn new(set: &'a USizeSet) -> USizeSetIter<'a> { let mut iter = set.content.iter(); let first_bit_iterator = if let Some(&first) = iter.next() { BitIterator::new(first) } else { BitIterator::new(0) }; USizeSetIter { offset: set.min, current: first_bit_iterator, content: iter } } } const USIZE_BIT_SIZE: usize = mem::size_of::<usize>() * 8; impl<'a> Iterator for USizeSetIter<'a> { type Item = usize; fn next(&mut self) -> Option<usize> { loop { if let Some(bit_index) = self.current.next() { return Some(self.offset + bit_index); } if let Some(&next_content) = self.content.next() { self.current = BitIterator::new(next_content); self.offset += USIZE_BIT_SIZE; } else { return None; } } } } impl USizeSet { /// Creates a new, empty `USizeSet` with the given (inclusive) bounds. /// /// # Arguments /// /// * `min`: The minimum value that can be contained in the created set. /// Any values lower than that will yield a `USizeSetError::OutOfBounds` if /// inserted or removed. Must be less than or equal to `max`. /// * `max`: The maximum value that can be contained in the created set. /// Any values higher than that will yield a `USizeSetError::OutOfBounds` /// if inserted or removed. Must be greater than or equal to `min`. /// /// # Errors /// /// If `min > max`. In that case, a `USizeSetError::InvalidBounds` is /// returned. pub fn new(min: usize, max: usize) -> USizeSetResult<USizeSet> { if min > max { Err(USizeSetError::InvalidBounds) } else { let required_words = (max - min + 64) >> 6; Ok(USizeSet { min, max, len: 0, content: vec![0u64; required_words] }) } } /// Creates a new singleton `USizeSet` with the given (inclusive) bounds. /// The set contains one element, which is specified by `content`. /// /// # Arguments /// /// * `min`: The minimum value that can be contained in the created set. /// Any values lower than that will yield a `USizeSetError::OutOfBounds` if /// inserted or removed. Must be less than or equal to `max`. /// * `max`: The maximum value that can be contained in the created set. /// Any values higher than that will yield a `USizeSetError::OutOfBounds` /// if inserted or removed. Must be greater than or equal to `min`. /// * `content`: The only element contained by the created set. Must be /// within the bounds. /// /// # Errors /// /// * `USizeSetError::InvalidBounds`: If `min > max`. /// * `USizeSetError::OutOfBounds`: If `content < min` or `content > max`. pub fn singleton(min: usize, max: usize, content: usize) -> USizeSetResult<USizeSet> { let mut result = USizeSet::new(min, max)?; result.insert(content)?; Ok(result) } /// Creates a new `USizeSet` that includes all numbers in the given /// (inclusive) bounds. Note that these bounds also apply later. /// /// # Arguments /// /// * `min`: The minimum value contained in the created set, which is also /// the minimum that can be contained. Any values lower than this will /// yield a `USizeSetError::OutOfBounds` if inserted or removed. Must be /// less than or equal to `max`. /// * `max`: The maximum value contained in the created set, which is also /// the maximum value that can be contained. Any values higher than this /// will yield a `USizeSetError::OutOfBounds` if inserted or removed. Must /// be greater than or equal to `min`. /// /// # Errors /// /// If `min > max`. In that case, a `USizeSetError::InvalidBounds` is /// returned. pub fn range(min: usize, max: usize) -> USizeSetResult<USizeSet> { if min > max { Err(USizeSetError::InvalidBounds) } else { let mut content = Vec::new(); let ones = max - min + 1; let ones_words = ones >> 6; for _ in 1..ones_words { content.push(!0); } let remaining_ones = ones - (ones_words << 6); if remaining_ones > 0 { content.push((1 << remaining_ones) - 1); } Ok(USizeSet { min, max, len: ones, content }) } } fn compute_index(&self, number: usize) -> USizeSetResult<(usize, u64)> { if number < self.min || number > self.max { Err(USizeSetError::OutOfBounds) } else { let index = number - self.min; let word_index = index >> 6; let sub_word_index = index & 63; let mask = 1u64 << sub_word_index; Ok((word_index, mask)) } } /// Returns the minimum value that this set can contain (inclusive). pub fn min(&self) -> usize { self.min } /// Returns the maximum value that this set can contain (inclusive). pub fn max(&self) -> usize { self.max } /// Indicates whether this set contains the given number, in which case /// this method returns `true`. If it is not contained or outside the /// bounds, `false` will be returned. pub fn contains(&self, number: usize) -> bool { if let Ok((word_index, mask)) = self.compute_index(number) { (self.content[word_index] & mask) > 0 } else { false } } /// Inserts the given number into this set, such that [USizeSet::contains] /// returns `true` for this number afterwards. Note that it must be within /// the bounds provided at construction time. /// /// This method returns `true` if the set has changed (i.e. the number was /// not present before) and `false` otherwise. /// /// # Errors /// /// If `number` is less than [USizeSet::min] or greater than /// [USizeSet::max]. In that case, `USizeSetError::OutOfBounds` is /// returned. pub fn insert(&mut self, number: usize) -> USizeSetResult<bool> { let (word_index, mask) = self.compute_index(number)?; let word = &mut self.content[word_index]; if *word & mask == 0 { self.len += 1; *word |= mask; Ok(true) } else { Ok(false) } } /// Removes the given number from this set, such that [USizeSet::contains] /// returns `false` for this number afterwards. Note that it must be within /// the bounds provided at construction time. /// /// This method returns `true` if the set has changed (i.e. the number was /// present before) and `false` otherwise. /// /// # Errors /// /// If `number` is less than [USizeSet::min] or greater than /// [USizeSet::max]. In that case, `USizeSetError::OutOfBounds` is /// returned. pub fn remove(&mut self, number: usize) -> USizeSetResult<bool> { let (word_index, mask) = self.compute_index(number)?; let word = &mut self.content[word_index]; if *word & mask > 0 { *word &= !mask; self.len -= 1; Ok(true) } else { Ok(false) } } /// Removes all numbers from this set, such that [USizeSet::contains] will /// return `false` for all inputs and [USizeSet::is_empty] will return /// `true`. pub fn clear(&mut self) { for i in 0..self.content.len() { self.content[i] = 0; } self.len = 0; } /// Returns an iterator over the numbers contained in this set in ascending /// order. pub fn iter(&self) -> USizeSetIter<'_> { USizeSetIter::new(self) } /// Indicates whether this set is empty, i.e. contains no numbers. If this /// method returns `true`, [USizeSet::contains] will return `false` for all /// inputs. pub fn is_empty(&self) -> bool { self.len == 0 } /// Returns the number of elements contained in this set. pub fn len(&self) -> usize { self.len } fn count(&self) -> usize { self.content.iter() .map(|c| c.count_ones() as usize) .sum() } fn op_assign(&mut self, other: &USizeSet, op: impl Fn(u64, u64) -> u64) -> USizeSetResult<bool> { if self.min() != other.min() || self.max() != other.max() { Err(USizeSetError::DifferentBounds) } else { let contents = self.content.iter_mut().zip(other.content.iter()); let mut changed = false; for (self_u64, &other_u64) in contents { let self_before = *self_u64; *self_u64 = op(self_before, other_u64); changed |= self_before != *self_u64; } self.len = self.count(); Ok(changed) } } fn op(&self, other: &USizeSet, op_assign: impl Fn(&mut USizeSet, &USizeSet) -> USizeSetResult<bool>) -> USizeSetResult<USizeSet> { let mut clone = self.clone(); op_assign(&mut clone, other)?; Ok(clone) } /// Computes the set union between this and the given set and stores the /// result in this set. The bounds of this set and `other` must be equal. /// /// `USizeSet` implements [BitOrAssign] as syntactic sugar for this /// operation. Note that that implementation panics instead of returning /// potential errors. /// /// # Returns /// /// True, if and only if this set changed as a result of the operation. /// /// # Errors /// /// If either the minimum or maximum of this set and `other` are different. /// In that case, `USizeError::DifferentBounds` is returned. pub fn union_assign(&mut self, other: &USizeSet) -> USizeSetResult<bool> { self.op_assign(other, u64::bitor) } /// Computes the set union between this and the given set and stores the /// result in a new set which is returned. The bounds of this set and /// `other` must be equal. /// /// `USizeSet` implements [BitOr] as syntactic sugar for this operation. /// Note that that implementation panics instead of returning potential /// errors. /// /// # Errors /// /// If the minimum or maximum of this set and `other` are different. In /// that case, `USizeError::DifferentBounds` is returned. pub fn union(&self, other: &USizeSet) -> USizeSetResult<USizeSet> { self.op(other, USizeSet::union_assign) } /// Computes the set intersection between this and the given set and stores /// the result in this set. The bounds of this set and `other` must be /// equal. /// /// `USizeSet` implements [BitAndAssign] as syntactic sugar for this /// operation. Note that that implementation panics instead of returning /// potential errors. /// /// # Returns /// /// True, if and only if this set changed as a result of the operation. /// /// # Errors /// /// If the minimum or maximum of this set and `other` are different. In /// that case, `USizeError::DifferentBounds` is returned. pub fn intersect_assign(&mut self, other: &USizeSet) -> USizeSetResult<bool> { self.op_assign(other, u64::bitand) } /// Computes the set intersection between this and the given set and stores /// the result in a new set which is returned. The bounds of this set and /// `other` must be equal. /// /// `USizeSet` implements [BitAnd] as syntactic sugar for this operation. /// Note that that implementation panics instead of returning potential /// errors. /// /// # Errors /// /// If the minimum or maximum of this set and `other` are different. In /// that case, `USizeError::DifferentBounds` is returned. pub fn intersect(&self, other: &USizeSet) -> USizeSetResult<USizeSet> { self.op(other, USizeSet::intersect_assign) } /// Computes the set difference between this and the given set and stores /// the result in this set. The bounds of this set and `other` must be /// equal. `other` acts as the right-hand-side, meaning its elements are /// removed from the result. /// /// `USizeSet` implements [SubAssign] as syntactic sugar for this /// operation. Note that that implementation panics instead of returning /// potential errors. /// /// # Returns /// /// True, if and only if this set changed as a result of the operation. /// /// # Errors /// /// If the minimum or maximum of this set and `other` are different. In /// that case, `USizeError::DifferentBounds` is returned. pub fn difference_assign(&mut self, other: &USizeSet) -> USizeSetResult<bool> { self.op_assign(other, |a, b| a & !b) } /// Computes the set difference between this and the given set and stores /// the result in a new set which is returned. The bounds of this set and /// `other` must be equal. /// /// `USizeSet` implements [Sub] as syntactic sugar for this operation. Note /// that that implementation panics instead of returning potential errors. /// /// # Errors /// /// If the minimum or maximum of this set and `other` are different. In /// that case, `USizeError::DifferentBounds` is returned. pub fn difference(&self, other: &USizeSet) -> USizeSetResult<USizeSet> { self.op(other, USizeSet::difference_assign) } /// Computes the symmetric set difference between this and the given set /// and stores the result in this set. The bounds of this set and `other` /// must be equal. /// /// `USizeSet` implements [BitXorAssign] as syntactic sugar for this /// operation. Note that that implementation panics instead of returning /// potential errors. /// /// # Returns /// /// True, if and only if this set changed as a result of the operation. /// /// # Errors /// /// If the minimum or maximum of this set and `other` are different. In /// that case, `USizeError::DifferentBounds` is returned. pub fn symmetric_difference_assign(&mut self, other: &USizeSet) -> USizeSetResult<bool> { self.op_assign(other, u64::bitxor) } /// Computes the symmetric set difference between this and the given set /// and stores the result in a new set which is returned. The bounds of /// this set and `other` must be equal. /// /// `USizeSet` implements [BitXor] as syntactic sugar for this operation. /// Note that that implementation panics instead of returning potential /// errors. /// /// # Errors /// /// If the minimum or maximum of this set and `other` are different. In /// that case, `USizeError::DifferentBounds` is returned. pub fn symmetric_difference(&self, other: &USizeSet) -> USizeSetResult<USizeSet> { self.op(other, USizeSet::symmetric_difference_assign) } } /// Creates a new [USizeSet] that contains the specified elements. First, the /// minimum and maximum values must be specified. Then, after a semicolon, a /// comma-separated list of the contained values must be provided. For empty /// sets, [USizeSet.new()] can be used. /// /// An example usage of this macro looks as follows: /// /// ``` /// use sudoku_variants::set; /// use sudoku_variants::util::USizeSet; /// /// let set = set!(1, 5; 2, 4); /// assert_eq!(1, set.min()); /// assert_eq!(5, set.max()); /// assert!(set.contains(2)); /// assert!(!set.contains(3)); /// ``` #[macro_export] macro_rules! set { ($set:expr; $e:expr) => { ($set).insert($e).unwrap() }; ($set:expr; $e:expr, $($es:expr),+) => { set!($set; $e); set!($set; $($es),+) }; ($min:expr, $max:expr; $($es:expr),+) => { { let mut set = USizeSet::new($min, $max).unwrap(); set!(set; $($es),+); set } }; } impl BitAnd<&USizeSet> for USizeSet { type Output = USizeSet; fn bitand(mut self, rhs: &USizeSet) -> USizeSet { self.intersect_assign(rhs).unwrap(); self } } impl BitOr<&USizeSet> for USizeSet { type Output = USizeSet; fn bitor(mut self, rhs: &USizeSet) -> USizeSet { self.union_assign(rhs).unwrap(); self } } impl Sub<&USizeSet> for USizeSet { type Output = USizeSet; fn sub(mut self, rhs: &USizeSet) -> USizeSet { self.difference_assign(rhs).unwrap(); self } } impl BitXor<&USizeSet> for USizeSet { type Output = USizeSet; fn bitxor(mut self, rhs: &USizeSet) -> USizeSet { self.symmetric_difference_assign(rhs).unwrap(); self } } impl BitAnd for &USizeSet { type Output = USizeSet; fn bitand(self, rhs: &USizeSet) -> USizeSet { self.intersect(rhs).unwrap() } } impl BitOr for &USizeSet { type Output = USizeSet; fn bitor(self, rhs: &USizeSet) -> USizeSet { self.union(rhs).unwrap() } } impl Sub for &USizeSet { type Output = USizeSet; fn sub(self, rhs: &USizeSet) -> USizeSet { self.difference(rhs).unwrap() } } impl BitXor for &USizeSet { type Output = USizeSet; fn bitxor(self, rhs: &USizeSet) -> USizeSet { self.symmetric_difference(rhs).unwrap() } } impl BitAndAssign<&USizeSet> for USizeSet { fn bitand_assign(&mut self, rhs: &USizeSet) { self.intersect_assign(rhs).unwrap(); } } impl BitOrAssign<&USizeSet> for USizeSet { fn bitor_assign(&mut self, rhs: &USizeSet) { self.union_assign(rhs).unwrap(); } } impl SubAssign<&USizeSet> for USizeSet { fn sub_assign(&mut self, rhs: &USizeSet) { self.difference_assign(rhs).unwrap(); } } impl BitXorAssign<&USizeSet> for USizeSet { fn bitxor_assign(&mut self, rhs: &USizeSet) { self.symmetric_difference_assign(rhs).unwrap(); } } impl BitAndAssign<&USizeSet> for &mut USizeSet { fn bitand_assign(&mut self, rhs: &USizeSet) { self.intersect_assign(rhs).unwrap(); } } impl BitOrAssign<&USizeSet> for &mut USizeSet { fn bitor_assign(&mut self, rhs: &USizeSet) { self.union_assign(rhs).unwrap(); } } impl SubAssign<&USizeSet> for &mut USizeSet { fn sub_assign(&mut self, rhs: &USizeSet) { self.difference_assign(rhs).unwrap(); } } impl BitXorAssign<&USizeSet> for &mut USizeSet { fn bitxor_assign(&mut self, rhs: &USizeSet) { self.symmetric_difference_assign(rhs).unwrap(); } } #[cfg(test)] mod tests { use super::*; #[test] fn new_set_is_empty() { let set = USizeSet::new(1, 9).unwrap(); assert!(set.is_empty()); assert!(!set.contains(1)); assert!(!set.contains(3)); assert!(!set.contains(9)); assert_eq!(0, set.len()); } #[test] fn range_set_is_full() { let set = USizeSet::range(1, 9).unwrap(); assert!(!set.is_empty()); assert!(set.contains(1)); assert!(set.contains(3)); assert!(set.contains(9)); assert_eq!(9, set.len()); } #[test] fn singleton_set_contains_only_given_element() { let set = USizeSet::singleton(1, 9, 3).unwrap(); assert!(!set.is_empty()); assert!(!set.contains(1)); assert!(set.contains(3)); assert!(!set.contains(9)); assert_eq!(1, set.len()); } #[test] fn set_macro_has_specified_range() { let set = set!(2, 5; 3); assert_eq!(2, set.min()); assert_eq!(5, set.max()); } #[test] fn set_macro_contains_specified_elements() { let set = set!(2, 8; 3, 7, 8); assert_eq!(3, set.len()); assert!(set.contains(3)); assert!(set.contains(7)); assert!(set.contains(8)); assert!(!set.contains(5)); } #[test] fn set_creation_error() { assert_eq!(Err(USizeSetError::InvalidBounds), USizeSet::new(1, 0)); assert_eq!(Err(USizeSetError::InvalidBounds), USizeSet::new(5, 3)); } #[test] fn set_insertion_error() { let mut set = USizeSet::new(1, 5).unwrap(); assert_eq!(Err(USizeSetError::OutOfBounds), set.insert(0)); assert_eq!(Err(USizeSetError::OutOfBounds), set.insert(6)); } #[test] fn set_operation_error() { let set_1 = USizeSet::new(1, 9).unwrap(); let set_2 = USizeSet::new(1, 6).unwrap(); assert_eq!(Err(USizeSetError::DifferentBounds), set_1.union(&set_2)); assert_eq!(Err(USizeSetError::DifferentBounds), set_2.intersect(&set_1)); } #[test] fn manipulation() { let mut set = USizeSet::new(1, 9).unwrap(); set.insert(2).unwrap(); set.insert(4).unwrap(); set.insert(6).unwrap(); assert!(!set.is_empty()); assert!(set.contains(2)); assert!(set.contains(4)); assert!(set.contains(6)); assert_eq!(3, set.len()); set.remove(4).unwrap(); assert!(!set.is_empty()); assert!(set.contains(2)); assert!(!set.contains(4)); assert!(set.contains(6)); assert_eq!(2, set.len()); set.clear(); assert!(set.is_empty()); assert!(!set.contains(2)); assert!(!set.contains(4)); assert!(!set.contains(6)); assert_eq!(0, set.len()); } #[test] fn iteration() { let mut set = USizeSet::new(1, 100).unwrap(); set.insert(1).unwrap(); set.insert(12).unwrap(); set.insert(23).unwrap(); set.insert(36).unwrap(); set.insert(42).unwrap(); set.insert(64).unwrap(); set.insert(65).unwrap(); set.insert(97).unwrap(); set.insert(100).unwrap(); let mut iter = set.iter(); assert_eq!(Some(1), iter.next()); assert_eq!(Some(12), iter.next()); assert_eq!(Some(23), iter.next()); assert_eq!(Some(36), iter.next()); assert_eq!(Some(42), iter.next()); assert_eq!(Some(64), iter.next()); assert_eq!(Some(65), iter.next()); assert_eq!(Some(97), iter.next()); assert_eq!(Some(100), iter.next()); assert_eq!(None, iter.next()); } #[test] fn double_insert() { let mut set = USizeSet::new(1, 9).unwrap(); assert!(set.insert(3).unwrap()); assert!(set.insert(4).unwrap()); assert!(!set.insert(3).unwrap()); assert!(set.contains(3)); assert_eq!(2, set.len()); } #[test] fn double_remove() { let mut set = USizeSet::range(1, 9).unwrap(); assert!(set.remove(3).unwrap()); assert!(set.remove(5).unwrap()); assert!(!set.remove(3).unwrap()); assert!(!set.contains(3)); assert_eq!(7, set.len()); } fn op_test_lhs() -> USizeSet { set!(1, 4; 2, 4) } fn op_test_rhs() -> USizeSet { set!(1, 4; 3, 4) } #[test] fn union() { let result = op_test_lhs() | &op_test_rhs(); let expected = set!(1, 4; 2, 3, 4); assert_eq!(expected, result); } #[test] fn intersection() { let result = op_test_lhs() & &op_test_rhs(); let expected = set!(1, 4; 4); assert_eq!(expected, result); } #[test] fn difference() { let result = op_test_lhs() - &op_test_rhs(); let expected = set!(1, 4; 2); assert_eq!(expected, result); } #[test] fn symmetric_difference() { let result = op_test_lhs() ^ &op_test_rhs(); let expected = set!(1, 4; 2, 3); assert_eq!(expected, result); } }