tests.rs (7418B)
1 extern crate alloc; 2 use super::Range; 3 use super::{ 4 super::zfc::{BoundedCardinality, Cardinality, Set, num_bigint::BigUint}, 5 SetOrd, SupersetSet, 6 }; 7 use alloc::collections::btree_map::BTreeMap; 8 use core::{borrow::Borrow, cmp::Ordering}; 9 #[derive(Eq, PartialEq)] 10 struct ClosedInterval { 11 min: usize, 12 max: usize, 13 } 14 impl PartialOrd<Self> for ClosedInterval { 15 fn partial_cmp(&self, other: &Self) -> Option<Ordering> { 16 Some(self.cmp(other)) 17 } 18 } 19 impl Ord for ClosedInterval { 20 fn cmp(&self, other: &Self) -> Ordering { 21 match self.min.cmp(&other.min) { 22 Ordering::Less => { 23 if self.max >= other.max { 24 Ordering::Greater 25 } else { 26 Ordering::Less 27 } 28 } 29 Ordering::Equal => self.max.cmp(&other.max), 30 Ordering::Greater => { 31 if self.max > other.max { 32 Ordering::Greater 33 } else { 34 Ordering::Less 35 } 36 } 37 } 38 } 39 } 40 impl Set for ClosedInterval { 41 type Elem = usize; 42 #[expect(clippy::panic, reason = "want to crash when there is a bug")] 43 #[expect( 44 clippy::arithmetic_side_effects, 45 reason = "comment justifies correctness" 46 )] 47 fn bounded_cardinality(&self) -> BoundedCardinality { 48 BoundedCardinality::from_biguint_exact( 49 // `BigUint`s can always be added together. 50 BigUint::from(self.max.checked_sub(self.min).unwrap_or_else(|| { 51 panic!("superset_set::test::ClosedInterval must have max >= min") 52 })) + BigUint::from(1usize), 53 ) 54 } 55 #[expect(clippy::panic, reason = "want to crash when there is a bug")] 56 #[expect( 57 clippy::arithmetic_side_effects, 58 reason = "comment justifies correctness" 59 )] 60 fn cardinality(&self) -> Option<Cardinality> { 61 Some(Cardinality::Finite( 62 // `BigUint`s can always be added together. 63 BigUint::from(self.max.checked_sub(self.min).unwrap_or_else(|| { 64 panic!("superset_set::test::ClosedInterval must have max >= min") 65 })) + BigUint::from(1usize), 66 )) 67 } 68 fn contains<Q>(&self, elem: &Q) -> bool 69 where 70 Q: ?Sized + Borrow<Self::Elem> + Eq, 71 { 72 self.min <= *elem.borrow() && self.max >= *elem.borrow() 73 } 74 fn is_proper_subset(&self, val: &Self) -> bool { 75 match self.min.cmp(&val.min) { 76 Ordering::Less => false, 77 Ordering::Equal => self.max < val.max, 78 Ordering::Greater => self.max <= val.max, 79 } 80 } 81 fn is_subset(&self, val: &Self) -> bool { 82 self.min >= val.min && self.max <= val.max 83 } 84 } 85 impl SetOrd for ClosedInterval {} 86 #[test] 87 fn union() { 88 let mut set1 = SupersetSet::new(); 89 _ = set1.insert(ClosedInterval { min: 14, max: 19 }); 90 _ = set1.insert(ClosedInterval { min: 10, max: 12 }); 91 _ = set1.insert(ClosedInterval { min: 0, max: 3 }); 92 _ = set1.insert(ClosedInterval { min: 0, max: 2 }); 93 _ = set1.insert(ClosedInterval { min: 1, max: 4 }); 94 _ = set1.insert(ClosedInterval { min: 20, max: 22 }); 95 _ = set1.insert(ClosedInterval { min: 25, max: 26 }); 96 _ = set1.insert(ClosedInterval { min: 26, max: 27 }); 97 let mut set2 = SupersetSet::new(); 98 _ = set2.insert(ClosedInterval { min: 10, max: 12 }); 99 _ = set2.insert(ClosedInterval { min: 14, max: 16 }); 100 _ = set2.insert(ClosedInterval { min: 0, max: 3 }); 101 _ = set2.insert(ClosedInterval { min: 3, max: 4 }); 102 _ = set2.insert(ClosedInterval { min: 23, max: 25 }); 103 _ = set2.insert(ClosedInterval { min: 25, max: 27 }); 104 let mut union = set1.union(&set2); 105 assert!(union.next() == Some(&ClosedInterval { min: 0, max: 3 })); 106 assert!(union.next() == Some(&ClosedInterval { min: 1, max: 4 })); 107 assert!(union.next() == Some(&ClosedInterval { min: 10, max: 12 })); 108 assert!(union.next() == Some(&ClosedInterval { min: 14, max: 19 })); 109 assert!(union.next() == Some(&ClosedInterval { min: 20, max: 22 })); 110 assert!(union.next() == Some(&ClosedInterval { min: 23, max: 25 })); 111 assert!(union.next() == Some(&ClosedInterval { min: 25, max: 27 })); 112 assert!(union.next().is_none()); 113 assert!(union.next().is_none()); 114 assert!(union.next().is_none()); 115 } 116 #[test] 117 fn intersection() { 118 let mut set1 = SupersetSet::new(); 119 _ = set1.insert(ClosedInterval { min: 14, max: 19 }); 120 _ = set1.insert(ClosedInterval { min: 10, max: 12 }); 121 _ = set1.insert(ClosedInterval { min: 0, max: 3 }); 122 _ = set1.insert(ClosedInterval { min: 0, max: 2 }); 123 _ = set1.insert(ClosedInterval { min: 1, max: 4 }); 124 _ = set1.insert(ClosedInterval { min: 20, max: 22 }); 125 _ = set1.insert(ClosedInterval { min: 25, max: 26 }); 126 _ = set1.insert(ClosedInterval { min: 26, max: 27 }); 127 let mut set2 = SupersetSet::new(); 128 _ = set2.insert(ClosedInterval { min: 10, max: 12 }); 129 _ = set2.insert(ClosedInterval { min: 14, max: 16 }); 130 _ = set2.insert(ClosedInterval { min: 0, max: 3 }); 131 _ = set2.insert(ClosedInterval { min: 3, max: 4 }); 132 _ = set2.insert(ClosedInterval { min: 23, max: 25 }); 133 _ = set2.insert(ClosedInterval { min: 25, max: 27 }); 134 let mut intersection = set1.intersection(&set2); 135 assert!(intersection.next() == Some(&ClosedInterval { min: 0, max: 3 })); 136 assert!(intersection.next() == Some(&ClosedInterval { min: 3, max: 4 })); 137 assert!(intersection.next() == Some(&ClosedInterval { min: 10, max: 12 })); 138 assert!(intersection.next() == Some(&ClosedInterval { min: 14, max: 16 })); 139 assert!(intersection.next() == Some(&ClosedInterval { min: 25, max: 26 })); 140 assert!(intersection.next() == Some(&ClosedInterval { min: 26, max: 27 })); 141 assert!(intersection.next().is_none()); 142 assert!(intersection.next().is_none()); 143 assert!(intersection.next().is_none()); 144 } 145 #[test] 146 fn replace() { 147 let mut set = SupersetSet::new(); 148 _ = set.insert(ClosedInterval { min: 14, max: 19 }); 149 _ = set.insert(ClosedInterval { min: 10, max: 12 }); 150 _ = set.insert(ClosedInterval { min: 0, max: 3 }); 151 _ = set.insert(ClosedInterval { min: 0, max: 2 }); 152 _ = set.insert(ClosedInterval { min: 1, max: 4 }); 153 _ = set.insert(ClosedInterval { min: 20, max: 22 }); 154 _ = set.insert(ClosedInterval { min: 25, max: 26 }); 155 _ = set.insert(ClosedInterval { min: 26, max: 27 }); 156 // Does not replace proper supersets. 157 assert!( 158 set.replace(ClosedInterval { min: 20, max: 21 }).is_none() 159 && set.contains(&ClosedInterval { min: 20, max: 22 }) 160 && set.contains_proper_superset(&ClosedInterval { min: 20, max: 21 }) 161 && !set.contains(&ClosedInterval { min: 20, max: 21 }) 162 ); 163 // Successful replace. 164 assert!( 165 set.replace(ClosedInterval { min: 0, max: 3 }) == Some(ClosedInterval { min: 0, max: 3 }) 166 && set.contains(&ClosedInterval { min: 0, max: 3 }) 167 ); 168 // Replace is just an insert when a superset does not exist. 169 assert!( 170 set.replace(ClosedInterval { min: 100, max: 300 }).is_none() 171 && set.contains(&ClosedInterval { min: 100, max: 300 }) 172 ); 173 } 174 #[expect(clippy::zero_sized_map_values, reason = "set is defined as it")] 175 #[ignore = "silence lint"] 176 #[test] 177 fn range() { 178 _ = Range { 179 iter: BTreeMap::<u32, ()>::new().range(..), 180 }; 181 }