n_key_set.rs
1 //! Declaration for an n-keyed set type, allowing access to each of its members by each of N different keys. 2 3 // Re-export dependencies that we use to make this macro work. 4 #[doc(hidden)] 5 pub mod deps { 6 pub use paste::paste; 7 pub use slab::Slab; 8 } 9 10 /// Declare a structure that can hold elements with multiple unique keys. 11 /// 12 /// Each element can be looked up or removed by any of its keys. The keys 13 /// themselves can be any type that supports `Hash`, `Eq`, and `Clone`. Elements 14 /// can have multiple keys of the same type: for example, a person can have a 15 /// username `String` and an irc_handle `String`. 16 /// 17 /// All keys in the set must be unique: if a new element is inserted that has 18 /// the same value for any key as a previous element, the old element is 19 /// removed. 20 /// 21 /// Keys may be accessed from elements either by field access or by an accessor 22 /// function. 23 /// 24 /// Keys may be optional. If all keys are optional, then we require 25 /// additionally that every element must have at least one key. 26 /// 27 /// # Examples 28 /// 29 /// ``` 30 /// use tor_basic_utils::n_key_set; 31 /// 32 /// // We declare a person struct with several different fields. 33 /// pub struct Person { 34 /// username: String, 35 /// irc_handle: String, 36 /// student_id: Option<u64>, 37 /// favorite_joke: Option<String>, 38 /// } 39 /// 40 /// n_key_set! { 41 /// pub struct PersonSet for Person { 42 /// // See note on "Key syntax" below. The ".foo" syntax 43 /// // here means that the value for the key is returned 44 /// // by accessing a given field. 45 /// username: String { .username }, 46 /// irc_handle: String { .irc_handle }, 47 /// (Option) student_id: u64 { .student_id } 48 /// } 49 /// } 50 /// 51 /// let mut people = PersonSet::new(); 52 /// people.insert(Person { 53 /// username: "mina".into(), 54 /// irc_handle: "pashMina".into(), 55 /// student_id: None, 56 /// favorite_joke: None 57 /// }); 58 /// assert!(people.by_username("mina").is_some()); 59 /// assert!(people.by_irc_handle("pashMina").is_some()); 60 /// ``` 61 /// 62 /// # Key syntax 63 /// 64 /// You can tell the map to access the keys of an element in any of several ways. 65 /// 66 /// * `name : type { func() }` - A key whose name is `name` and type is `type`, 67 /// that can be accessed from a given element by calling `element.func()`. 68 /// * `name : type { .field }` - A key whose name is `name` and type is `type`, 69 /// that can be accessed from a given element by calling `&element.field`. 70 /// * `name : type` - Short for as `name : type { name() }`. 71 /// 72 /// If a key declaration is preceded with `(Option)`, then the 73 /// key is treated as optional, and accessor functions are expected to return 74 /// `Option<&Type>`. 75 /// 76 /// # Additional features 77 /// 78 /// You can put generic parameters and `where` constraints on your structure. 79 /// The `where` clause (if present) must be wrapped in square brackets. 80 /// 81 /// If you need to use const generics or lifetimes in your structure, you 82 /// need to use square brackets instead of angle brackets, and specify both the 83 /// generic parameters *and* the type that you are implementing. (This is due to 84 /// limitations in the Rust macro system.) For example: 85 /// 86 /// ``` 87 /// # use tor_basic_utils::n_key_set; 88 /// n_key_set!{ 89 /// struct['a, T, const N: usize] ArrayMap2['a, T, N] for (String, [&'a T;N]) 90 /// [ where T: Clone + 'a ] 91 /// { 92 /// name: String { .0 } 93 /// } 94 /// } 95 /// ``` 96 #[macro_export] 97 macro_rules! n_key_set { 98 { 99 $(#[$meta:meta])* 100 $vis:vis struct $mapname:ident $(<$($P:ident),*>)? for $V:ty 101 $( where [ $($constr:tt)+ ] )? 102 { 103 $($body:tt)+ 104 } 105 } => { 106 n_key_set!{ 107 $(#[$meta])* 108 $vis struct [$($($P),*)?] $mapname [$($($P),*)?] for $V 109 $( [ where $($constr)+ ] )? 110 { 111 $( $body )+ 112 } 113 } 114 }; 115 { 116 $(#[$meta:meta])* 117 $vis:vis struct [$($($G:tt)+)?] $mapname:ident [$($($P:tt)+)?] for $V:ty 118 $( [ where $($constr:tt)+ ])? 119 { 120 $( $(( $($flag:ident)+ ))? $key:ident : $KEY:ty $({ $($source:tt)+ })? ),+ 121 $(,)? 122 } 123 } => { 124 $crate::n_key_set::deps::paste!{ 125 $( #[$meta] )* 126 #[doc = concat!( 127 "A set of elements of type ", stringify!($V), " whose members can be accessed by multiple keys.", 128 "\n\nThe keys are:", 129 $( " * `", stringify!($key), "` (`",stringify!($KEY),"`)\n" , 130 $(" (", stringify!($($flag)+), ")", )? 131 )+ 132 "\ 133 Each member has a value for *each* required key, and up to one value 134 for *each* optional key. 135 The set contains at most one member for any value of a given key. 136 137 # Requirements 138 139 Key types must have consistent `Hash` and `Eq` implementations, as 140 they will be used as keys in a `HashMap`. 141 142 If all keys are optional, then every element in this set 143 must have at least one non-None key. 144 145 An element must not change its keys over time through interior 146 mutability. 147 148 ⚠️ If *any* of these rules is violated, the consequences are unspecified, 149 and could include panics or wrong answers (but not memory-unsafety). 150 151 # Limitations 152 153 This could be more efficient in space and time. 154 ", 155 )] 156 $vis struct $mapname $(<$($G)*>)? 157 where $( $KEY : std::hash::Hash + Eq + Clone , )+ $($($constr)+)? 158 { 159 // The $key fields here are a set of maps from each of the key values to 160 // the position of that value within the Slab. 161 // 162 // Invariants: 163 // * There is an entry K=>idx in the map `$key` if and only if 164 // values[idx].$accessor() == K. 165 // * Every value in `values` has at least one key. 166 // 167 // TODO: Dare we have these HashMaps key based on a reference to V 168 // instead? That would create a self-referential structure and require 169 // unsafety. Probably best to avoid that for now. 170 $([<$key _map>]: std::collections::HashMap<$KEY, usize> , )+ 171 172 // A map from the indices to the values. 173 values: $crate::n_key_set::deps::Slab<$V>, 174 } 175 176 #[allow(dead_code)] // May be needed if this is not public. 177 impl $(<$($G)*>)? $mapname $(<$($P)*>)? 178 where $( $KEY : std::hash::Hash + Eq + Clone , )+ $($($constr)+)? 179 { 180 #[doc = concat!("Construct a new ", stringify!($mapname))] 181 $vis fn new() -> Self { 182 Self::with_capacity(0) 183 } 184 #[doc = concat!("Construct a new ", stringify!($mapname), " with a given capacity.")] 185 186 $vis fn with_capacity(n: usize) -> Self { 187 Self { 188 $([<$key _map>]: std::collections::HashMap::with_capacity(n),)* 189 values: $crate::n_key_set::deps::Slab::with_capacity(n), 190 } 191 } 192 $( 193 #[doc = concat!("Return a reference to the element whose `", stringify!($key), "` is `key`.")] 194 /// 195 /// Return None if there is no such element. 196 $vis fn [<by_ $key>] <BorrowAsKey_>(&self, key: &BorrowAsKey_) -> Option<&$V> 197 where $KEY : std::borrow::Borrow<BorrowAsKey_>, 198 BorrowAsKey_: std::hash::Hash + Eq + ?Sized 199 { 200 self.[<$key _map>].get(key).map(|idx| self.values.get(*idx).expect("inconsistent state")) 201 } 202 203 #[doc = concat!("Return a mutable reference to the element whose `", stringify!($key), 204 "` is `key`.")] 205 /// 206 /// Return None if there is no such element. 207 /// 208 /// # Correctness hazard! 209 /// 210 /// This function can put this set into an inconsistent state if the 211 /// mutable reference is used to change any of the keys. Doing this does 212 /// not risk Rust safety violations (such as undefined behavior), but it 213 /// may nonetheless make your program incorrect by causing other 214 /// functions on this object to panic or give incorrect results. 215 /// 216 /// If you cannot prove to yourself that this won't happen, then you 217 /// should use `modify_by_*` instead. 218 $vis fn [<by_ $key _mut_hazardous>] <BorrowAsKey_>( 219 &mut self, 220 key: &BorrowAsKey_ 221 ) -> Option<&mut $V> 222 where $KEY : std::borrow::Borrow<BorrowAsKey_>, 223 BorrowAsKey_: std::hash::Hash + Eq + ?Sized 224 { 225 self.[<$key _map>] 226 .get(key) 227 .map(|idx| self.values.get_mut(*idx).expect("inconsistent state")) 228 } 229 230 #[doc = concat!("Return true if this set contains an element whose `", stringify!($key), 231 "` is `key`.")] 232 $vis fn [<contains_ $key>] <BorrowAsKey_>(&mut self, $key: &BorrowAsKey_) -> bool 233 where $KEY : std::borrow::Borrow<BorrowAsKey_>, 234 BorrowAsKey_: std::hash::Hash + Eq + ?Sized 235 { 236 self.[<$key _map>].get($key).is_some() 237 } 238 239 #[doc = concat!("Remove the element whose `", stringify!($key), "` is `key`")] 240 /// 241 /// Return that element on success, and None if there is no such element. 242 $vis fn [<remove_by_ $key>] <BorrowAsKey_>(&mut self, $key: &BorrowAsKey_) -> Option<$V> 243 where $KEY : std::borrow::Borrow<BorrowAsKey_>, 244 BorrowAsKey_: std::hash::Hash + Eq + ?Sized 245 { 246 self.[<$key _map>] 247 .get($key) 248 .copied() 249 .map(|old_idx| self.remove_at(old_idx).expect("inconsistent state")) 250 } 251 252 253 #[doc = concat!("Modify the element with the given value for `", stringify!($key), 254 " by applying `func` to it.")] 255 /// 256 /// `func` is allowed to change the keys for this value. All indices 257 /// are updated to refer to the new keys. If the new keys conflict with 258 /// any previous values, those values are replaced and returned in a 259 /// vector. 260 /// 261 /// If `func` causes the value to have no keys at all, then the value 262 /// itself is also removed and returned in the result vector. 263 /// 264 /// Note that because this function needs to copy all key values and check whether 265 /// they have changed, it is not terribly efficient. 266 $vis fn [<modify_by_$key>] <BorrowAsKey_, F_>( 267 &mut self, 268 $key: &BorrowAsKey_, 269 func: F_) -> Vec<$V> 270 where 271 $KEY : std::borrow::Borrow<BorrowAsKey_>, 272 BorrowAsKey_: std::hash::Hash + Eq + ?Sized, 273 F_: FnOnce(&mut $V) 274 { 275 if let Some(idx) = self.[<$key _map>].get($key) { 276 self.modify_at(*idx, func) 277 } else { 278 Vec::new() 279 } 280 } 281 )+ 282 283 /// Return an iterator over the elements in this container. 284 $vis fn values(&self) -> impl Iterator<Item=&$V> + '_ { 285 self.values.iter().map(|(_, v)| v) 286 } 287 288 /// Consume this container and return an iterator of its values. 289 $vis fn into_values(self) -> impl Iterator<Item=$V> { 290 self.values.into_iter().map(|(_, v)| v) 291 } 292 293 /// Try to insert the value `value`. 294 /// 295 /// Remove any previous values that shared any keys with `value`, and 296 /// return them in a vector on success. 297 /// 298 /// Return `Err(Error::NoKeys)` if all the keys are optional, 299 /// and `value` has no keys at all. 300 $vis fn try_insert(&mut self, value: $V) -> Result<Vec<$V>, $crate::n_key_set::Error> { 301 if self.capacity() > 32 && self.len() < self.capacity() / 4 { 302 // We're have the opportunity to free up a fair amount of space; let's take it. 303 self.compact() 304 } 305 306 // First, remove all the elements that have at least one key in common with `value`. 307 let mut replaced = Vec::new(); 308 $( 309 replaced.extend( 310 $crate::n_key_set!( @access(value, ($($($flag)+)?) $key : $KEY $({$($source)+})?) ) 311 .and_then(|key| self.[<remove_by_$key>](key)) 312 ); 313 )* 314 315 // Now insert the new value, and add it to all of the maps. 316 let new_idx = self.values.insert(value); 317 let value_ref = self.values.get(new_idx).expect("we just inserted this"); 318 let mut some_key_found = false; 319 $( 320 $crate::n_key_set!( @access(value_ref, ($($($flag)+)?) $key : $KEY $({$($source)+})?) ) 321 .map(|key| { 322 self.[<$key _map>].insert(key.to_owned(), new_idx); 323 some_key_found = true; 324 }); 325 )* 326 // If we didn't find any key on the newly added value, that's 327 // an invariant violation. 328 if ! some_key_found { 329 self.values.remove(new_idx); // Restore the set to a correct state. 330 return Err($crate::n_key_set::Error::NoKeys); 331 } 332 333 Ok(replaced) 334 } 335 336 /// Try to insert the value `value`. 337 /// 338 /// Remove any previous values that shared any keys with `value`, and 339 /// return them in a vector. 340 /// 341 /// # Panics 342 /// 343 /// Panics if all the keys are optional, and `value` has no keys at all. 344 $vis fn insert(&mut self, value: $V) -> Vec<$V> { 345 self.try_insert(value) 346 .expect("Tried to add a value with no key!") 347 } 348 349 /// Return the number of elements in this container. 350 $vis fn len(&self) -> usize { 351 self.values.len() 352 } 353 354 /// Return true if there are no elements in this container. 355 $vis fn is_empty(&self) -> bool { 356 self.values.len() == 0 357 } 358 359 /// Return the number of elements for which this container has allocated 360 /// storage. 361 $vis fn capacity(&self) -> usize { 362 self.values.capacity() 363 } 364 365 /// Remove every element that does not satisfy the predicate `pred`. 366 $vis fn retain<F>(&mut self, mut pred: F) 367 where F: FnMut(&$V) -> bool, 368 { 369 for idx in 0..self.values.capacity() { 370 if self.values.get(idx).map(&mut pred) == Some(false) { 371 self.remove_at(idx); 372 } 373 } 374 } 375 376 /// Helper: remove the item stored at index `idx`, and remove it from 377 /// every key map. 378 /// 379 /// If there was no element at `idx`, do nothing. 380 /// 381 /// Return the element removed (if any). 382 fn remove_at(&mut self, idx: usize) -> Option<$V> { 383 if let Some(removed) = self.values.try_remove(idx) { 384 $( 385 let $key = $crate::n_key_set!( @access(removed, ($($($flag)+)?) $key : $KEY $({$($source)+})?) ); 386 if let Some($key) = $key { 387 let old_idx = self.[<$key _map>].remove($key); 388 assert_eq!(old_idx, Some(idx)); 389 } 390 )* 391 Some(removed) 392 } else { 393 None 394 } 395 } 396 397 /// Change the value at `idx` by applying `func` to it. 398 /// 399 /// `func` is allowed to change the keys for this value. All indices 400 /// are updated to refer to the new keys. If the new keys conflict with 401 /// any previous values, those values are replaced and returned in a 402 /// vector. 403 /// 404 /// If `func` causes the value to have no keys at all, then the value 405 /// itself is also removed and returned in the result vector. 406 /// 407 /// # Panics 408 /// 409 /// Panics if `idx` is not present in this set. 410 fn modify_at<F_>(&mut self, idx: usize, func: F_) -> Vec<$V> 411 where 412 F_: FnOnce(&mut $V) 413 { 414 let value = self.values.get_mut(idx).expect("invalid index"); 415 $( 416 let [<orig_$key>] = $crate::n_key_set!( @access(value, ($($($flag)+)?) $key : $KEY $({$($source)+})?) ) 417 .map(|elt| elt.to_owned()) ; 418 )+ 419 420 func(value); 421 422 // Check whether any keys have changed, and whether there still are 423 // any keys. 424 $( 425 let [<new_$key>] = $crate::n_key_set!( @access( value, ($($($flag)+)?) $key : $KEY $({$($source)+})?) ) ; 426 )+ 427 let keys_changed = $( 428 [<orig_$key>].as_ref().map(std::borrow::Borrow::borrow) != [<new_$key>] 429 )||+ ; 430 431 if keys_changed { 432 let found_any_keys = $( [<new_$key>].is_some() )||+ ; 433 434 // Remove this value from every place that it was before. 435 // 436 // We can't use remove_at, since we have changed the keys in the 437 // value: we have to remove them manually from each index 438 // instead. 439 $( 440 if let Some(orig) = [<orig_ $key>] { 441 let removed = self.[<$key _map>].remove(&orig); 442 assert_eq!(removed, Some(idx)); 443 } 444 )+ 445 // Remove the value from its previous place in the index. (This 446 // results in an extra copy when we call insert(), but if we 447 // didn't do it, we'd need to reimplement `insert()`.) 448 let removed = self.values.remove(idx); 449 if found_any_keys { 450 // This item belongs: put it back and return the vector of 451 // whatever was replaced.j 452 self.insert(removed) 453 } else { 454 // This item does not belong any longer, since all its keys 455 // were removed. 456 vec![removed] 457 } 458 } else { 459 // We did not change any keys, so we know we have not replaced 460 // any items. 461 vec![] 462 } 463 } 464 465 /// Re-index all the values in this map, so that the map can use a more 466 /// compact representation. 467 /// 468 /// This should be done infrequently; it's expensive. 469 fn compact(&mut self) { 470 let old_value = std::mem::replace(self, Self::with_capacity(self.len())); 471 for item in old_value.into_values() { 472 self.insert(item); 473 } 474 } 475 476 /// Assert that this set appears to be in an internally consistent state. 477 /// 478 /// This method can be somewhat expensive, and it should never fail unless 479 /// your code has a bug. 480 /// 481 /// # Panics 482 /// 483 /// Panics if it finds bugs in this object, or constraint violations in 484 /// its elements. See the (type documentation)[Self#Requirements] for a 485 /// list of constraints. 486 $vis fn check_invariants(&self) { 487 #![allow(noop_method_call)] // permit borrow when it does nothing. 488 use std::borrow::Borrow; 489 // Make sure that every entry in the $key map points to a 490 // value with the right value for that $key. 491 $( 492 for (k,idx) in self.[<$key _map>].iter() { 493 let val = self.values.get(*idx).expect("Dangling entry in hashmap."); 494 // Can't use assert_eq!; k might not implement Debug. 495 assert!( 496 Some((k).borrow()) == 497 $crate::n_key_set!( @access(val, ($($($flag)+)?) $key : $KEY $({$($source)+})?) ), 498 "Inconsistent key between hashmap and value." 499 ) 500 } 501 )+ 502 503 // Make sure that every value has an entry in the $key map that 504 // points to it, for each of its keys. 505 // 506 // This is slightly redundant, but we don't care too much about 507 // efficiency here. 508 for (idx, val) in self.values.iter() { 509 let mut found_any_key = false; 510 $( 511 if let Some(k) = $crate::n_key_set!( @access(val, ($($($flag)+)?) $key : $KEY $({$($source)+})?) ) { 512 found_any_key = true; 513 assert!( 514 self.[<$key _map>].get(k) == Some(&idx), 515 "Value not found at correct index" 516 ) 517 } 518 stringify!($key); 519 )+ 520 assert!(found_any_key, "Found a value with no keys."); 521 } 522 } 523 } 524 525 impl $(<$($G)*>)? Default for $mapname $(<$($P)*>)? 526 where $( $KEY : std::hash::Hash + Eq + Clone , )* $($($constr)+)? 527 { 528 fn default() -> Self { 529 $mapname::new() 530 } 531 } 532 533 impl $(<$($G)*>)? FromIterator<$V> for $mapname $(<$($P)*>)? 534 where $( $KEY : std::hash::Hash + Eq + Clone , )* $($($constr)+)? 535 { 536 fn from_iter<IntoIter_>(iter: IntoIter_) -> Self 537 where 538 IntoIter_: IntoIterator<Item = $V> 539 { 540 let iter = iter.into_iter(); 541 let mut set = Self::with_capacity(iter.size_hint().0); 542 for value in iter { 543 set.insert(value); 544 } 545 set 546 } 547 } 548 } 549 }; 550 551 // Helper: Generate an expression to access a specific key and return 552 // an Option<&TYPE> for that key. This is the part of the macro 553 // that parses key descriptions. 554 555 { @access($ex:expr, (Option) $key:ident : $t:ty ) } => { 556 $ex.key() 557 }; 558 { @access($ex:expr, () $key:ident : $t:ty) } => { 559 Some($ex.key()) 560 }; 561 { @access($ex:expr, (Option) $key:ident : $t:ty { . $field:tt } ) } => { 562 $ex.$field.as_ref() 563 }; 564 { @access($ex:expr, () $key:ident : $t:ty { . $field:tt } ) } => { 565 Some(&$ex.$field) 566 }; 567 { @access($ex:expr, (Option) $key:ident : $t:ty { $func:ident () } ) } => { 568 $ex.$func() 569 }; 570 { @access($ex:expr, () $key:ident : $t:ty { $func:ident () } ) } => { 571 Some($ex.$func()) 572 }; 573 } 574 575 /// An error returned from an operation on an `n_key_set`. 576 #[derive(Clone, Debug, thiserror::Error)] 577 #[non_exhaustive] 578 pub enum Error { 579 /// We tried to insert a value into a set where all keys were optional, but 580 /// every key on that value was `None`. 581 #[error("Tried to insert a value with no keys")] 582 NoKeys, 583 } 584 585 #[cfg(test)] 586 mod test { 587 // @@ begin test lint list maintained by maint/add_warning @@ 588 #![allow(clippy::bool_assert_comparison)] 589 #![allow(clippy::clone_on_copy)] 590 #![allow(clippy::dbg_macro)] 591 #![allow(clippy::mixed_attributes_style)] 592 #![allow(clippy::print_stderr)] 593 #![allow(clippy::print_stdout)] 594 #![allow(clippy::single_char_pattern)] 595 #![allow(clippy::unwrap_used)] 596 #![allow(clippy::unchecked_duration_subtraction)] 597 #![allow(clippy::useless_vec)] 598 #![allow(clippy::needless_pass_by_value)] 599 //! <!-- @@ end test lint list maintained by maint/add_warning @@ --> 600 601 n_key_set! { 602 #[derive(Clone, Debug)] 603 struct Tuple2Set<A,B> for (A,B) { 604 first: A { .0 }, 605 second: B { .1 }, 606 } 607 } 608 609 #[test] 610 fn basic() { 611 let mut set = Tuple2Set::new(); 612 assert!(set.is_empty()); 613 614 set.insert((0_u32, 99_u16)); 615 assert_eq!(set.contains_first(&0), true); 616 assert_eq!(set.contains_second(&99), true); 617 assert_eq!(set.contains_first(&99), false); 618 assert_eq!(set.contains_second(&0), false); 619 assert_eq!(set.by_first(&0), Some(&(0, 99))); 620 assert_eq!(set.by_second(&99), Some(&(0, 99))); 621 assert_eq!(set.by_first(&99), None); 622 assert_eq!(set.by_second(&0), None); 623 624 assert_eq!(set.insert((12, 34)), vec![]); 625 assert_eq!(set.len(), 2); 626 assert!(set.capacity() >= 2); 627 assert_eq!(set.by_first(&0), Some(&(0, 99))); 628 assert_eq!(set.by_first(&12), Some(&(12, 34))); 629 assert_eq!(set.remove_by_second(&99), Some((0, 99))); 630 assert_eq!(set.len(), 1); 631 632 // no overlap in these next few inserts. 633 set.insert((34, 56)); 634 set.insert((56, 78)); 635 set.insert((78, 90)); 636 assert_eq!(set.len(), 4); 637 // This insert replaces (12, 34) 638 assert_eq!(set.insert((12, 123)), vec![(12, 34)]); 639 // This one replaces (12,123) and (34,56). 640 let mut replaced = set.insert((12, 56)); 641 replaced.sort(); 642 assert_eq!(replaced, vec![(12, 123), (34, 56)]); 643 assert_eq!(set.len(), 3); 644 assert_eq!(set.is_empty(), false); 645 set.check_invariants(); 646 647 // Test our iterators 648 let mut all_members: Vec<_> = set.values().collect(); 649 all_members.sort(); 650 assert_eq!(all_members, vec![&(12, 56), &(56, 78), &(78, 90)]); 651 652 let mut drained_members: Vec<_> = set.into_values().collect(); 653 drained_members.sort(); 654 assert_eq!(drained_members, vec![(12, 56), (56, 78), (78, 90)]); 655 } 656 657 #[test] 658 fn retain_and_compact() { 659 let mut set: Tuple2Set<String, String> = (1..=1000) 660 .map(|idx| (format!("A={}", idx), format!("B={}", idx))) 661 .collect(); 662 663 assert_eq!(set.len(), 1000); 664 let cap_orig = set.capacity(); 665 assert!(cap_orig >= set.len()); 666 667 // Retain only the values whose first key is 3 characters long. 668 // That's 9 values out of 1000. 669 set.retain(|(a, _)| a.len() <= 3); 670 assert_eq!(set.len(), 9); 671 // We don't shrink till we next insert. 672 assert_eq!(set.capacity(), cap_orig); 673 set.check_invariants(); 674 675 assert!(set 676 .insert(("A=0".to_string(), "B=0".to_string())) 677 .is_empty()); 678 assert!(set.capacity() < cap_orig); 679 assert_eq!(set.len(), 10); 680 for idx in 0..=9 { 681 assert!(set.contains_first(&format!("A={}", idx))); 682 } 683 set.check_invariants(); 684 } 685 686 #[test] 687 fn modify_value() { 688 let mut set: Tuple2Set<i32, i32> = (1..=100).map(|idx| (idx, idx * idx)).collect(); 689 set.check_invariants(); 690 691 let v = set.modify_by_first(&30, |elt| elt.1 = 256); 692 set.check_invariants(); 693 // one element was replaced. 694 assert_eq!(v.len(), 1); 695 assert_eq!(v[0], (16, 256)); 696 assert_eq!(set.by_second(&256).unwrap(), &(30, 256)); 697 assert_eq!(set.by_first(&30).unwrap(), &(30, 256)); 698 699 let v = set.modify_by_first(&30, |elt| *elt = (-100, -100)); 700 set.check_invariants(); 701 // no elements were replaced. 702 assert_eq!(v.len(), 0); 703 assert_eq!(set.by_first(&30), None); 704 assert_eq!(set.by_second(&256), None); 705 assert_eq!(set.by_first(&-100).unwrap(), &(-100, -100)); 706 assert_eq!(set.by_second(&-100).unwrap(), &(-100, -100)); 707 708 set.check_invariants(); 709 } 710 711 #[allow(dead_code)] 712 struct Weekday { 713 dow: u8, 714 name: &'static str, 715 lucky_number: Option<u16>, 716 } 717 #[allow(dead_code)] 718 impl Weekday { 719 // TODO: I wish this could return u8 720 fn dow(&self) -> &u8 { 721 &self.dow 722 } 723 fn name(&self) -> &str { 724 self.name 725 } 726 // TODO: I wish this could return Option<u16> 727 fn lucky_number(&self) -> Option<&u16> { 728 self.lucky_number.as_ref() 729 } 730 } 731 n_key_set! { 732 struct WeekdaySet for Weekday { 733 idx: u8 { dow() }, 734 (Option) lucky: u16 { lucky_number() }, 735 name: String { name() } 736 } 737 } 738 739 n_key_set! { 740 struct['a] ArrayMap['a] for (String, [&'a u32;10]) { 741 name: String { .0 } 742 } 743 } 744 745 n_key_set! { 746 struct['a, const N:usize] ArrayMap2['a, N] for (String, [&'a u32;N]) { 747 name: String { .0 } 748 } 749 } 750 }