1 //! A hash set implemented using `IndexMap` 2 3 #[cfg(feature = "rayon")] 4 pub use crate::rayon::set as rayon; 5 6 #[cfg(has_std)] 7 use std::collections::hash_map::RandomState; 8 9 use crate::vec::{self, Vec}; 10 use core::cmp::Ordering; 11 use core::fmt; 12 use core::hash::{BuildHasher, Hash}; 13 use core::iter::{Chain, FromIterator}; 14 use core::ops::{BitAnd, BitOr, BitXor, Index, RangeBounds, Sub}; 15 use core::slice; 16 17 use super::{Entries, Equivalent, IndexMap}; 18 19 type Bucket<T> = super::Bucket<T, ()>; 20 21 /// A hash set where the iteration order of the values is independent of their 22 /// hash values. 23 /// 24 /// The interface is closely compatible with the standard `HashSet`, but also 25 /// has additional features. 26 /// 27 /// # Order 28 /// 29 /// The values have a consistent order that is determined by the sequence of 30 /// insertion and removal calls on the set. The order does not depend on the 31 /// values or the hash function at all. Note that insertion order and value 32 /// are not affected if a re-insertion is attempted once an element is 33 /// already present. 34 /// 35 /// All iterators traverse the set *in order*. Set operation iterators like 36 /// `union` produce a concatenated order, as do their matching "bitwise" 37 /// operators. See their documentation for specifics. 38 /// 39 /// The insertion order is preserved, with **notable exceptions** like the 40 /// `.remove()` or `.swap_remove()` methods. Methods such as `.sort_by()` of 41 /// course result in a new order, depending on the sorting order. 42 /// 43 /// # Indices 44 /// 45 /// The values are indexed in a compact range without holes in the range 46 /// `0..self.len()`. For example, the method `.get_full` looks up the index for 47 /// a value, and the method `.get_index` looks up the value by index. 48 /// 49 /// # Examples 50 /// 51 /// ``` 52 /// use indexmap::IndexSet; 53 /// 54 /// // Collects which letters appear in a sentence. 55 /// let letters: IndexSet<_> = "a short treatise on fungi".chars().collect(); 56 /// 57 /// assert!(letters.contains(&'s')); 58 /// assert!(letters.contains(&'t')); 59 /// assert!(letters.contains(&'u')); 60 /// assert!(!letters.contains(&'y')); 61 /// ``` 62 #[cfg(has_std)] 63 pub struct IndexSet<T, S = RandomState> { 64 map: IndexMap<T, (), S>, 65 } 66 #[cfg(not(has_std))] 67 pub struct IndexSet<T, S> { 68 map: IndexMap<T, (), S>, 69 } 70 71 impl<T, S> Clone for IndexSet<T, S> 72 where 73 T: Clone, 74 S: Clone, 75 { clone(&self) -> Self76 fn clone(&self) -> Self { 77 IndexSet { 78 map: self.map.clone(), 79 } 80 } 81 clone_from(&mut self, other: &Self)82 fn clone_from(&mut self, other: &Self) { 83 self.map.clone_from(&other.map); 84 } 85 } 86 87 impl<T, S> Entries for IndexSet<T, S> { 88 type Entry = Bucket<T>; 89 90 #[inline] into_entries(self) -> Vec<Self::Entry>91 fn into_entries(self) -> Vec<Self::Entry> { 92 self.map.into_entries() 93 } 94 95 #[inline] as_entries(&self) -> &[Self::Entry]96 fn as_entries(&self) -> &[Self::Entry] { 97 self.map.as_entries() 98 } 99 100 #[inline] as_entries_mut(&mut self) -> &mut [Self::Entry]101 fn as_entries_mut(&mut self) -> &mut [Self::Entry] { 102 self.map.as_entries_mut() 103 } 104 with_entries<F>(&mut self, f: F) where F: FnOnce(&mut [Self::Entry]),105 fn with_entries<F>(&mut self, f: F) 106 where 107 F: FnOnce(&mut [Self::Entry]), 108 { 109 self.map.with_entries(f); 110 } 111 } 112 113 impl<T, S> fmt::Debug for IndexSet<T, S> 114 where 115 T: fmt::Debug, 116 { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result117 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 118 if cfg!(not(feature = "test_debug")) { 119 f.debug_set().entries(self.iter()).finish() 120 } else { 121 // Let the inner `IndexMap` print all of its details 122 f.debug_struct("IndexSet").field("map", &self.map).finish() 123 } 124 } 125 } 126 127 #[cfg(has_std)] 128 impl<T> IndexSet<T> { 129 /// Create a new set. (Does not allocate.) new() -> Self130 pub fn new() -> Self { 131 IndexSet { 132 map: IndexMap::new(), 133 } 134 } 135 136 /// Create a new set with capacity for `n` elements. 137 /// (Does not allocate if `n` is zero.) 138 /// 139 /// Computes in **O(n)** time. with_capacity(n: usize) -> Self140 pub fn with_capacity(n: usize) -> Self { 141 IndexSet { 142 map: IndexMap::with_capacity(n), 143 } 144 } 145 } 146 147 impl<T, S> IndexSet<T, S> { 148 /// Create a new set with capacity for `n` elements. 149 /// (Does not allocate if `n` is zero.) 150 /// 151 /// Computes in **O(n)** time. with_capacity_and_hasher(n: usize, hash_builder: S) -> Self152 pub fn with_capacity_and_hasher(n: usize, hash_builder: S) -> Self { 153 IndexSet { 154 map: IndexMap::with_capacity_and_hasher(n, hash_builder), 155 } 156 } 157 158 /// Create a new set with `hash_builder` with_hasher(hash_builder: S) -> Self159 pub fn with_hasher(hash_builder: S) -> Self { 160 IndexSet { 161 map: IndexMap::with_hasher(hash_builder), 162 } 163 } 164 165 /// Computes in **O(1)** time. capacity(&self) -> usize166 pub fn capacity(&self) -> usize { 167 self.map.capacity() 168 } 169 170 /// Return a reference to the set's `BuildHasher`. hasher(&self) -> &S171 pub fn hasher(&self) -> &S { 172 self.map.hasher() 173 } 174 175 /// Return the number of elements in the set. 176 /// 177 /// Computes in **O(1)** time. len(&self) -> usize178 pub fn len(&self) -> usize { 179 self.map.len() 180 } 181 182 /// Returns true if the set contains no elements. 183 /// 184 /// Computes in **O(1)** time. is_empty(&self) -> bool185 pub fn is_empty(&self) -> bool { 186 self.map.is_empty() 187 } 188 189 /// Return an iterator over the values of the set, in their order iter(&self) -> Iter<'_, T>190 pub fn iter(&self) -> Iter<'_, T> { 191 Iter { 192 iter: self.map.keys().iter, 193 } 194 } 195 196 /// Remove all elements in the set, while preserving its capacity. 197 /// 198 /// Computes in **O(n)** time. clear(&mut self)199 pub fn clear(&mut self) { 200 self.map.clear(); 201 } 202 203 /// Clears the `IndexSet` in the given index range, returning those values 204 /// as a drain iterator. 205 /// 206 /// The range may be any type that implements `RangeBounds<usize>`, 207 /// including all of the `std::ops::Range*` types, or even a tuple pair of 208 /// `Bound` start and end values. To drain the set entirely, use `RangeFull` 209 /// like `set.drain(..)`. 210 /// 211 /// This shifts down all entries following the drained range to fill the 212 /// gap, and keeps the allocated memory for reuse. 213 /// 214 /// ***Panics*** if the starting point is greater than the end point or if 215 /// the end point is greater than the length of the set. drain<R>(&mut self, range: R) -> Drain<'_, T> where R: RangeBounds<usize>,216 pub fn drain<R>(&mut self, range: R) -> Drain<'_, T> 217 where 218 R: RangeBounds<usize>, 219 { 220 Drain { 221 iter: self.map.drain(range).iter, 222 } 223 } 224 } 225 226 impl<T, S> IndexSet<T, S> 227 where 228 T: Hash + Eq, 229 S: BuildHasher, 230 { 231 /// Reserve capacity for `additional` more values. 232 /// 233 /// Computes in **O(n)** time. reserve(&mut self, additional: usize)234 pub fn reserve(&mut self, additional: usize) { 235 self.map.reserve(additional); 236 } 237 238 /// Shrink the capacity of the set as much as possible. 239 /// 240 /// Computes in **O(n)** time. shrink_to_fit(&mut self)241 pub fn shrink_to_fit(&mut self) { 242 self.map.shrink_to_fit(); 243 } 244 245 /// Insert the value into the set. 246 /// 247 /// If an equivalent item already exists in the set, it returns 248 /// `false` leaving the original value in the set and without 249 /// altering its insertion order. Otherwise, it inserts the new 250 /// item and returns `true`. 251 /// 252 /// Computes in **O(1)** time (amortized average). insert(&mut self, value: T) -> bool253 pub fn insert(&mut self, value: T) -> bool { 254 self.map.insert(value, ()).is_none() 255 } 256 257 /// Insert the value into the set, and get its index. 258 /// 259 /// If an equivalent item already exists in the set, it returns 260 /// the index of the existing item and `false`, leaving the 261 /// original value in the set and without altering its insertion 262 /// order. Otherwise, it inserts the new item and returns the index 263 /// of the inserted item and `true`. 264 /// 265 /// Computes in **O(1)** time (amortized average). insert_full(&mut self, value: T) -> (usize, bool)266 pub fn insert_full(&mut self, value: T) -> (usize, bool) { 267 use super::map::Entry::*; 268 269 match self.map.entry(value) { 270 Occupied(e) => (e.index(), false), 271 Vacant(e) => { 272 let index = e.index(); 273 e.insert(()); 274 (index, true) 275 } 276 } 277 } 278 279 /// Return an iterator over the values that are in `self` but not `other`. 280 /// 281 /// Values are produced in the same order that they appear in `self`. difference<'a, S2>(&'a self, other: &'a IndexSet<T, S2>) -> Difference<'a, T, S2> where S2: BuildHasher,282 pub fn difference<'a, S2>(&'a self, other: &'a IndexSet<T, S2>) -> Difference<'a, T, S2> 283 where 284 S2: BuildHasher, 285 { 286 Difference { 287 iter: self.iter(), 288 other, 289 } 290 } 291 292 /// Return an iterator over the values that are in `self` or `other`, 293 /// but not in both. 294 /// 295 /// Values from `self` are produced in their original order, followed by 296 /// values from `other` in their original order. symmetric_difference<'a, S2>( &'a self, other: &'a IndexSet<T, S2>, ) -> SymmetricDifference<'a, T, S, S2> where S2: BuildHasher,297 pub fn symmetric_difference<'a, S2>( 298 &'a self, 299 other: &'a IndexSet<T, S2>, 300 ) -> SymmetricDifference<'a, T, S, S2> 301 where 302 S2: BuildHasher, 303 { 304 SymmetricDifference { 305 iter: self.difference(other).chain(other.difference(self)), 306 } 307 } 308 309 /// Return an iterator over the values that are in both `self` and `other`. 310 /// 311 /// Values are produced in the same order that they appear in `self`. intersection<'a, S2>(&'a self, other: &'a IndexSet<T, S2>) -> Intersection<'a, T, S2> where S2: BuildHasher,312 pub fn intersection<'a, S2>(&'a self, other: &'a IndexSet<T, S2>) -> Intersection<'a, T, S2> 313 where 314 S2: BuildHasher, 315 { 316 Intersection { 317 iter: self.iter(), 318 other, 319 } 320 } 321 322 /// Return an iterator over all values that are in `self` or `other`. 323 /// 324 /// Values from `self` are produced in their original order, followed by 325 /// values that are unique to `other` in their original order. union<'a, S2>(&'a self, other: &'a IndexSet<T, S2>) -> Union<'a, T, S> where S2: BuildHasher,326 pub fn union<'a, S2>(&'a self, other: &'a IndexSet<T, S2>) -> Union<'a, T, S> 327 where 328 S2: BuildHasher, 329 { 330 Union { 331 iter: self.iter().chain(other.difference(self)), 332 } 333 } 334 335 /// Return `true` if an equivalent to `value` exists in the set. 336 /// 337 /// Computes in **O(1)** time (average). contains<Q: ?Sized>(&self, value: &Q) -> bool where Q: Hash + Equivalent<T>,338 pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool 339 where 340 Q: Hash + Equivalent<T>, 341 { 342 self.map.contains_key(value) 343 } 344 345 /// Return a reference to the value stored in the set, if it is present, 346 /// else `None`. 347 /// 348 /// Computes in **O(1)** time (average). get<Q: ?Sized>(&self, value: &Q) -> Option<&T> where Q: Hash + Equivalent<T>,349 pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T> 350 where 351 Q: Hash + Equivalent<T>, 352 { 353 self.map.get_key_value(value).map(|(x, &())| x) 354 } 355 356 /// Return item index and value get_full<Q: ?Sized>(&self, value: &Q) -> Option<(usize, &T)> where Q: Hash + Equivalent<T>,357 pub fn get_full<Q: ?Sized>(&self, value: &Q) -> Option<(usize, &T)> 358 where 359 Q: Hash + Equivalent<T>, 360 { 361 self.map.get_full(value).map(|(i, x, &())| (i, x)) 362 } 363 364 /// Return item index, if it exists in the set get_index_of<Q: ?Sized>(&self, value: &Q) -> Option<usize> where Q: Hash + Equivalent<T>,365 pub fn get_index_of<Q: ?Sized>(&self, value: &Q) -> Option<usize> 366 where 367 Q: Hash + Equivalent<T>, 368 { 369 self.map.get_index_of(value) 370 } 371 372 /// Adds a value to the set, replacing the existing value, if any, that is 373 /// equal to the given one. Returns the replaced value. 374 /// 375 /// Computes in **O(1)** time (average). replace(&mut self, value: T) -> Option<T>376 pub fn replace(&mut self, value: T) -> Option<T> { 377 use super::map::Entry::*; 378 379 match self.map.entry(value) { 380 Vacant(e) => { 381 e.insert(()); 382 None 383 } 384 Occupied(e) => Some(e.replace_key()), 385 } 386 } 387 388 /// Remove the value from the set, and return `true` if it was present. 389 /// 390 /// **NOTE:** This is equivalent to `.swap_remove(value)`, if you want 391 /// to preserve the order of the values in the set, use `.shift_remove(value)`. 392 /// 393 /// Computes in **O(1)** time (average). remove<Q: ?Sized>(&mut self, value: &Q) -> bool where Q: Hash + Equivalent<T>,394 pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool 395 where 396 Q: Hash + Equivalent<T>, 397 { 398 self.swap_remove(value) 399 } 400 401 /// Remove the value from the set, and return `true` if it was present. 402 /// 403 /// Like `Vec::swap_remove`, the value is removed by swapping it with the 404 /// last element of the set and popping it off. **This perturbs 405 /// the postion of what used to be the last element!** 406 /// 407 /// Return `false` if `value` was not in the set. 408 /// 409 /// Computes in **O(1)** time (average). swap_remove<Q: ?Sized>(&mut self, value: &Q) -> bool where Q: Hash + Equivalent<T>,410 pub fn swap_remove<Q: ?Sized>(&mut self, value: &Q) -> bool 411 where 412 Q: Hash + Equivalent<T>, 413 { 414 self.map.swap_remove(value).is_some() 415 } 416 417 /// Remove the value from the set, and return `true` if it was present. 418 /// 419 /// Like `Vec::remove`, the value is removed by shifting all of the 420 /// elements that follow it, preserving their relative order. 421 /// **This perturbs the index of all of those elements!** 422 /// 423 /// Return `false` if `value` was not in the set. 424 /// 425 /// Computes in **O(n)** time (average). shift_remove<Q: ?Sized>(&mut self, value: &Q) -> bool where Q: Hash + Equivalent<T>,426 pub fn shift_remove<Q: ?Sized>(&mut self, value: &Q) -> bool 427 where 428 Q: Hash + Equivalent<T>, 429 { 430 self.map.shift_remove(value).is_some() 431 } 432 433 /// Removes and returns the value in the set, if any, that is equal to the 434 /// given one. 435 /// 436 /// **NOTE:** This is equivalent to `.swap_take(value)`, if you need to 437 /// preserve the order of the values in the set, use `.shift_take(value)` 438 /// instead. 439 /// 440 /// Computes in **O(1)** time (average). take<Q: ?Sized>(&mut self, value: &Q) -> Option<T> where Q: Hash + Equivalent<T>,441 pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T> 442 where 443 Q: Hash + Equivalent<T>, 444 { 445 self.swap_take(value) 446 } 447 448 /// Removes and returns the value in the set, if any, that is equal to the 449 /// given one. 450 /// 451 /// Like `Vec::swap_remove`, the value is removed by swapping it with the 452 /// last element of the set and popping it off. **This perturbs 453 /// the postion of what used to be the last element!** 454 /// 455 /// Return `None` if `value` was not in the set. 456 /// 457 /// Computes in **O(1)** time (average). swap_take<Q: ?Sized>(&mut self, value: &Q) -> Option<T> where Q: Hash + Equivalent<T>,458 pub fn swap_take<Q: ?Sized>(&mut self, value: &Q) -> Option<T> 459 where 460 Q: Hash + Equivalent<T>, 461 { 462 self.map.swap_remove_entry(value).map(|(x, ())| x) 463 } 464 465 /// Removes and returns the value in the set, if any, that is equal to the 466 /// given one. 467 /// 468 /// Like `Vec::remove`, the value is removed by shifting all of the 469 /// elements that follow it, preserving their relative order. 470 /// **This perturbs the index of all of those elements!** 471 /// 472 /// Return `None` if `value` was not in the set. 473 /// 474 /// Computes in **O(n)** time (average). shift_take<Q: ?Sized>(&mut self, value: &Q) -> Option<T> where Q: Hash + Equivalent<T>,475 pub fn shift_take<Q: ?Sized>(&mut self, value: &Q) -> Option<T> 476 where 477 Q: Hash + Equivalent<T>, 478 { 479 self.map.shift_remove_entry(value).map(|(x, ())| x) 480 } 481 482 /// Remove the value from the set return it and the index it had. 483 /// 484 /// Like `Vec::swap_remove`, the value is removed by swapping it with the 485 /// last element of the set and popping it off. **This perturbs 486 /// the postion of what used to be the last element!** 487 /// 488 /// Return `None` if `value` was not in the set. swap_remove_full<Q: ?Sized>(&mut self, value: &Q) -> Option<(usize, T)> where Q: Hash + Equivalent<T>,489 pub fn swap_remove_full<Q: ?Sized>(&mut self, value: &Q) -> Option<(usize, T)> 490 where 491 Q: Hash + Equivalent<T>, 492 { 493 self.map.swap_remove_full(value).map(|(i, x, ())| (i, x)) 494 } 495 496 /// Remove the value from the set return it and the index it had. 497 /// 498 /// Like `Vec::remove`, the value is removed by shifting all of the 499 /// elements that follow it, preserving their relative order. 500 /// **This perturbs the index of all of those elements!** 501 /// 502 /// Return `None` if `value` was not in the set. shift_remove_full<Q: ?Sized>(&mut self, value: &Q) -> Option<(usize, T)> where Q: Hash + Equivalent<T>,503 pub fn shift_remove_full<Q: ?Sized>(&mut self, value: &Q) -> Option<(usize, T)> 504 where 505 Q: Hash + Equivalent<T>, 506 { 507 self.map.shift_remove_full(value).map(|(i, x, ())| (i, x)) 508 } 509 510 /// Remove the last value 511 /// 512 /// Computes in **O(1)** time (average). pop(&mut self) -> Option<T>513 pub fn pop(&mut self) -> Option<T> { 514 self.map.pop().map(|(x, ())| x) 515 } 516 517 /// Scan through each value in the set and keep those where the 518 /// closure `keep` returns `true`. 519 /// 520 /// The elements are visited in order, and remaining elements keep their 521 /// order. 522 /// 523 /// Computes in **O(n)** time (average). retain<F>(&mut self, mut keep: F) where F: FnMut(&T) -> bool,524 pub fn retain<F>(&mut self, mut keep: F) 525 where 526 F: FnMut(&T) -> bool, 527 { 528 self.map.retain(move |x, &mut ()| keep(x)) 529 } 530 531 /// Sort the set’s values by their default ordering. 532 /// 533 /// See `sort_by` for details. sort(&mut self) where T: Ord,534 pub fn sort(&mut self) 535 where 536 T: Ord, 537 { 538 self.map.sort_keys() 539 } 540 541 /// Sort the set’s values in place using the comparison function `compare`. 542 /// 543 /// Computes in **O(n log n)** time and **O(n)** space. The sort is stable. sort_by<F>(&mut self, mut compare: F) where F: FnMut(&T, &T) -> Ordering,544 pub fn sort_by<F>(&mut self, mut compare: F) 545 where 546 F: FnMut(&T, &T) -> Ordering, 547 { 548 self.map.sort_by(move |a, _, b, _| compare(a, b)); 549 } 550 551 /// Sort the values of the set and return a by value iterator of 552 /// the values with the result. 553 /// 554 /// The sort is stable. sorted_by<F>(self, mut cmp: F) -> IntoIter<T> where F: FnMut(&T, &T) -> Ordering,555 pub fn sorted_by<F>(self, mut cmp: F) -> IntoIter<T> 556 where 557 F: FnMut(&T, &T) -> Ordering, 558 { 559 IntoIter { 560 iter: self.map.sorted_by(move |a, &(), b, &()| cmp(a, b)).iter, 561 } 562 } 563 564 /// Reverses the order of the set’s values in place. 565 /// 566 /// Computes in **O(n)** time and **O(1)** space. reverse(&mut self)567 pub fn reverse(&mut self) { 568 self.map.reverse() 569 } 570 } 571 572 impl<T, S> IndexSet<T, S> { 573 /// Get a value by index 574 /// 575 /// Valid indices are *0 <= index < self.len()* 576 /// 577 /// Computes in **O(1)** time. get_index(&self, index: usize) -> Option<&T>578 pub fn get_index(&self, index: usize) -> Option<&T> { 579 self.map.get_index(index).map(|(x, &())| x) 580 } 581 582 /// Remove the key-value pair by index 583 /// 584 /// Valid indices are *0 <= index < self.len()* 585 /// 586 /// Like `Vec::swap_remove`, the value is removed by swapping it with the 587 /// last element of the set and popping it off. **This perturbs 588 /// the postion of what used to be the last element!** 589 /// 590 /// Computes in **O(1)** time (average). swap_remove_index(&mut self, index: usize) -> Option<T>591 pub fn swap_remove_index(&mut self, index: usize) -> Option<T> { 592 self.map.swap_remove_index(index).map(|(x, ())| x) 593 } 594 595 /// Remove the key-value pair by index 596 /// 597 /// Valid indices are *0 <= index < self.len()* 598 /// 599 /// Like `Vec::remove`, the value is removed by shifting all of the 600 /// elements that follow it, preserving their relative order. 601 /// **This perturbs the index of all of those elements!** 602 /// 603 /// Computes in **O(n)** time (average). shift_remove_index(&mut self, index: usize) -> Option<T>604 pub fn shift_remove_index(&mut self, index: usize) -> Option<T> { 605 self.map.shift_remove_index(index).map(|(x, ())| x) 606 } 607 } 608 609 /// Access `IndexSet` values at indexed positions. 610 /// 611 /// # Examples 612 /// 613 /// ``` 614 /// use indexmap::IndexSet; 615 /// 616 /// let mut set = IndexSet::new(); 617 /// for word in "Lorem ipsum dolor sit amet".split_whitespace() { 618 /// set.insert(word.to_string()); 619 /// } 620 /// assert_eq!(set[0], "Lorem"); 621 /// assert_eq!(set[1], "ipsum"); 622 /// set.reverse(); 623 /// assert_eq!(set[0], "amet"); 624 /// assert_eq!(set[1], "sit"); 625 /// set.sort(); 626 /// assert_eq!(set[0], "Lorem"); 627 /// assert_eq!(set[1], "amet"); 628 /// ``` 629 /// 630 /// ```should_panic 631 /// use indexmap::IndexSet; 632 /// 633 /// let mut set = IndexSet::new(); 634 /// set.insert("foo"); 635 /// println!("{:?}", set[10]); // panics! 636 /// ``` 637 impl<T, S> Index<usize> for IndexSet<T, S> { 638 type Output = T; 639 640 /// Returns a reference to the value at the supplied `index`. 641 /// 642 /// ***Panics*** if `index` is out of bounds. index(&self, index: usize) -> &T643 fn index(&self, index: usize) -> &T { 644 self.get_index(index) 645 .expect("IndexSet: index out of bounds") 646 } 647 } 648 649 /// An owning iterator over the items of a `IndexSet`. 650 /// 651 /// This `struct` is created by the [`into_iter`] method on [`IndexSet`] 652 /// (provided by the `IntoIterator` trait). See its documentation for more. 653 /// 654 /// [`IndexSet`]: struct.IndexSet.html 655 /// [`into_iter`]: struct.IndexSet.html#method.into_iter 656 pub struct IntoIter<T> { 657 iter: vec::IntoIter<Bucket<T>>, 658 } 659 660 impl<T> Iterator for IntoIter<T> { 661 type Item = T; 662 663 iterator_methods!(Bucket::key); 664 } 665 666 impl<T> DoubleEndedIterator for IntoIter<T> { next_back(&mut self) -> Option<Self::Item>667 fn next_back(&mut self) -> Option<Self::Item> { 668 self.iter.next_back().map(Bucket::key) 669 } 670 } 671 672 impl<T> ExactSizeIterator for IntoIter<T> { len(&self) -> usize673 fn len(&self) -> usize { 674 self.iter.len() 675 } 676 } 677 678 impl<T: fmt::Debug> fmt::Debug for IntoIter<T> { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result679 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 680 let iter = self.iter.as_slice().iter().map(Bucket::key_ref); 681 f.debug_list().entries(iter).finish() 682 } 683 } 684 685 /// An iterator over the items of a `IndexSet`. 686 /// 687 /// This `struct` is created by the [`iter`] method on [`IndexSet`]. 688 /// See its documentation for more. 689 /// 690 /// [`IndexSet`]: struct.IndexSet.html 691 /// [`iter`]: struct.IndexSet.html#method.iter 692 pub struct Iter<'a, T> { 693 iter: slice::Iter<'a, Bucket<T>>, 694 } 695 696 impl<'a, T> Iterator for Iter<'a, T> { 697 type Item = &'a T; 698 699 iterator_methods!(Bucket::key_ref); 700 } 701 702 impl<T> DoubleEndedIterator for Iter<'_, T> { next_back(&mut self) -> Option<Self::Item>703 fn next_back(&mut self) -> Option<Self::Item> { 704 self.iter.next_back().map(Bucket::key_ref) 705 } 706 } 707 708 impl<T> ExactSizeIterator for Iter<'_, T> { len(&self) -> usize709 fn len(&self) -> usize { 710 self.iter.len() 711 } 712 } 713 714 impl<T> Clone for Iter<'_, T> { clone(&self) -> Self715 fn clone(&self) -> Self { 716 Iter { 717 iter: self.iter.clone(), 718 } 719 } 720 } 721 722 impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result723 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 724 f.debug_list().entries(self.clone()).finish() 725 } 726 } 727 728 /// A draining iterator over the items of a `IndexSet`. 729 /// 730 /// This `struct` is created by the [`drain`] method on [`IndexSet`]. 731 /// See its documentation for more. 732 /// 733 /// [`IndexSet`]: struct.IndexSet.html 734 /// [`drain`]: struct.IndexSet.html#method.drain 735 pub struct Drain<'a, T> { 736 iter: vec::Drain<'a, Bucket<T>>, 737 } 738 739 impl<T> Iterator for Drain<'_, T> { 740 type Item = T; 741 742 iterator_methods!(Bucket::key); 743 } 744 745 impl<T> DoubleEndedIterator for Drain<'_, T> { 746 double_ended_iterator_methods!(Bucket::key); 747 } 748 749 impl<'a, T, S> IntoIterator for &'a IndexSet<T, S> { 750 type Item = &'a T; 751 type IntoIter = Iter<'a, T>; 752 into_iter(self) -> Self::IntoIter753 fn into_iter(self) -> Self::IntoIter { 754 self.iter() 755 } 756 } 757 758 impl<T, S> IntoIterator for IndexSet<T, S> { 759 type Item = T; 760 type IntoIter = IntoIter<T>; 761 into_iter(self) -> Self::IntoIter762 fn into_iter(self) -> Self::IntoIter { 763 IntoIter { 764 iter: self.map.into_iter().iter, 765 } 766 } 767 } 768 769 impl<T, S> FromIterator<T> for IndexSet<T, S> 770 where 771 T: Hash + Eq, 772 S: BuildHasher + Default, 773 { from_iter<I: IntoIterator<Item = T>>(iterable: I) -> Self774 fn from_iter<I: IntoIterator<Item = T>>(iterable: I) -> Self { 775 let iter = iterable.into_iter().map(|x| (x, ())); 776 IndexSet { 777 map: IndexMap::from_iter(iter), 778 } 779 } 780 } 781 782 impl<T, S> Extend<T> for IndexSet<T, S> 783 where 784 T: Hash + Eq, 785 S: BuildHasher, 786 { extend<I: IntoIterator<Item = T>>(&mut self, iterable: I)787 fn extend<I: IntoIterator<Item = T>>(&mut self, iterable: I) { 788 let iter = iterable.into_iter().map(|x| (x, ())); 789 self.map.extend(iter); 790 } 791 } 792 793 impl<'a, T, S> Extend<&'a T> for IndexSet<T, S> 794 where 795 T: Hash + Eq + Copy + 'a, 796 S: BuildHasher, 797 { extend<I: IntoIterator<Item = &'a T>>(&mut self, iterable: I)798 fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iterable: I) { 799 let iter = iterable.into_iter().cloned(); // FIXME: use `copied` in Rust 1.36 800 self.extend(iter); 801 } 802 } 803 804 impl<T, S> Default for IndexSet<T, S> 805 where 806 S: Default, 807 { 808 /// Return an empty `IndexSet` default() -> Self809 fn default() -> Self { 810 IndexSet { 811 map: IndexMap::default(), 812 } 813 } 814 } 815 816 impl<T, S1, S2> PartialEq<IndexSet<T, S2>> for IndexSet<T, S1> 817 where 818 T: Hash + Eq, 819 S1: BuildHasher, 820 S2: BuildHasher, 821 { eq(&self, other: &IndexSet<T, S2>) -> bool822 fn eq(&self, other: &IndexSet<T, S2>) -> bool { 823 self.len() == other.len() && self.is_subset(other) 824 } 825 } 826 827 impl<T, S> Eq for IndexSet<T, S> 828 where 829 T: Eq + Hash, 830 S: BuildHasher, 831 { 832 } 833 834 impl<T, S> IndexSet<T, S> 835 where 836 T: Eq + Hash, 837 S: BuildHasher, 838 { 839 /// Returns `true` if `self` has no elements in common with `other`. is_disjoint<S2>(&self, other: &IndexSet<T, S2>) -> bool where S2: BuildHasher,840 pub fn is_disjoint<S2>(&self, other: &IndexSet<T, S2>) -> bool 841 where 842 S2: BuildHasher, 843 { 844 if self.len() <= other.len() { 845 self.iter().all(move |value| !other.contains(value)) 846 } else { 847 other.iter().all(move |value| !self.contains(value)) 848 } 849 } 850 851 /// Returns `true` if all elements of `self` are contained in `other`. is_subset<S2>(&self, other: &IndexSet<T, S2>) -> bool where S2: BuildHasher,852 pub fn is_subset<S2>(&self, other: &IndexSet<T, S2>) -> bool 853 where 854 S2: BuildHasher, 855 { 856 self.len() <= other.len() && self.iter().all(move |value| other.contains(value)) 857 } 858 859 /// Returns `true` if all elements of `other` are contained in `self`. is_superset<S2>(&self, other: &IndexSet<T, S2>) -> bool where S2: BuildHasher,860 pub fn is_superset<S2>(&self, other: &IndexSet<T, S2>) -> bool 861 where 862 S2: BuildHasher, 863 { 864 other.is_subset(self) 865 } 866 } 867 868 /// A lazy iterator producing elements in the difference of `IndexSet`s. 869 /// 870 /// This `struct` is created by the [`difference`] method on [`IndexSet`]. 871 /// See its documentation for more. 872 /// 873 /// [`IndexSet`]: struct.IndexSet.html 874 /// [`difference`]: struct.IndexSet.html#method.difference 875 pub struct Difference<'a, T, S> { 876 iter: Iter<'a, T>, 877 other: &'a IndexSet<T, S>, 878 } 879 880 impl<'a, T, S> Iterator for Difference<'a, T, S> 881 where 882 T: Eq + Hash, 883 S: BuildHasher, 884 { 885 type Item = &'a T; 886 next(&mut self) -> Option<Self::Item>887 fn next(&mut self) -> Option<Self::Item> { 888 while let Some(item) = self.iter.next() { 889 if !self.other.contains(item) { 890 return Some(item); 891 } 892 } 893 None 894 } 895 size_hint(&self) -> (usize, Option<usize>)896 fn size_hint(&self) -> (usize, Option<usize>) { 897 (0, self.iter.size_hint().1) 898 } 899 } 900 901 impl<T, S> DoubleEndedIterator for Difference<'_, T, S> 902 where 903 T: Eq + Hash, 904 S: BuildHasher, 905 { next_back(&mut self) -> Option<Self::Item>906 fn next_back(&mut self) -> Option<Self::Item> { 907 while let Some(item) = self.iter.next_back() { 908 if !self.other.contains(item) { 909 return Some(item); 910 } 911 } 912 None 913 } 914 } 915 916 impl<T, S> Clone for Difference<'_, T, S> { clone(&self) -> Self917 fn clone(&self) -> Self { 918 Difference { 919 iter: self.iter.clone(), 920 ..*self 921 } 922 } 923 } 924 925 impl<T, S> fmt::Debug for Difference<'_, T, S> 926 where 927 T: fmt::Debug + Eq + Hash, 928 S: BuildHasher, 929 { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result930 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 931 f.debug_list().entries(self.clone()).finish() 932 } 933 } 934 935 /// A lazy iterator producing elements in the intersection of `IndexSet`s. 936 /// 937 /// This `struct` is created by the [`intersection`] method on [`IndexSet`]. 938 /// See its documentation for more. 939 /// 940 /// [`IndexSet`]: struct.IndexSet.html 941 /// [`intersection`]: struct.IndexSet.html#method.intersection 942 pub struct Intersection<'a, T, S> { 943 iter: Iter<'a, T>, 944 other: &'a IndexSet<T, S>, 945 } 946 947 impl<'a, T, S> Iterator for Intersection<'a, T, S> 948 where 949 T: Eq + Hash, 950 S: BuildHasher, 951 { 952 type Item = &'a T; 953 next(&mut self) -> Option<Self::Item>954 fn next(&mut self) -> Option<Self::Item> { 955 while let Some(item) = self.iter.next() { 956 if self.other.contains(item) { 957 return Some(item); 958 } 959 } 960 None 961 } 962 size_hint(&self) -> (usize, Option<usize>)963 fn size_hint(&self) -> (usize, Option<usize>) { 964 (0, self.iter.size_hint().1) 965 } 966 } 967 968 impl<T, S> DoubleEndedIterator for Intersection<'_, T, S> 969 where 970 T: Eq + Hash, 971 S: BuildHasher, 972 { next_back(&mut self) -> Option<Self::Item>973 fn next_back(&mut self) -> Option<Self::Item> { 974 while let Some(item) = self.iter.next_back() { 975 if self.other.contains(item) { 976 return Some(item); 977 } 978 } 979 None 980 } 981 } 982 983 impl<T, S> Clone for Intersection<'_, T, S> { clone(&self) -> Self984 fn clone(&self) -> Self { 985 Intersection { 986 iter: self.iter.clone(), 987 ..*self 988 } 989 } 990 } 991 992 impl<T, S> fmt::Debug for Intersection<'_, T, S> 993 where 994 T: fmt::Debug + Eq + Hash, 995 S: BuildHasher, 996 { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result997 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 998 f.debug_list().entries(self.clone()).finish() 999 } 1000 } 1001 1002 /// A lazy iterator producing elements in the symmetric difference of `IndexSet`s. 1003 /// 1004 /// This `struct` is created by the [`symmetric_difference`] method on 1005 /// [`IndexSet`]. See its documentation for more. 1006 /// 1007 /// [`IndexSet`]: struct.IndexSet.html 1008 /// [`symmetric_difference`]: struct.IndexSet.html#method.symmetric_difference 1009 pub struct SymmetricDifference<'a, T, S1, S2> { 1010 iter: Chain<Difference<'a, T, S2>, Difference<'a, T, S1>>, 1011 } 1012 1013 impl<'a, T, S1, S2> Iterator for SymmetricDifference<'a, T, S1, S2> 1014 where 1015 T: Eq + Hash, 1016 S1: BuildHasher, 1017 S2: BuildHasher, 1018 { 1019 type Item = &'a T; 1020 next(&mut self) -> Option<Self::Item>1021 fn next(&mut self) -> Option<Self::Item> { 1022 self.iter.next() 1023 } 1024 size_hint(&self) -> (usize, Option<usize>)1025 fn size_hint(&self) -> (usize, Option<usize>) { 1026 self.iter.size_hint() 1027 } 1028 fold<B, F>(self, init: B, f: F) -> B where F: FnMut(B, Self::Item) -> B,1029 fn fold<B, F>(self, init: B, f: F) -> B 1030 where 1031 F: FnMut(B, Self::Item) -> B, 1032 { 1033 self.iter.fold(init, f) 1034 } 1035 } 1036 1037 impl<T, S1, S2> DoubleEndedIterator for SymmetricDifference<'_, T, S1, S2> 1038 where 1039 T: Eq + Hash, 1040 S1: BuildHasher, 1041 S2: BuildHasher, 1042 { next_back(&mut self) -> Option<Self::Item>1043 fn next_back(&mut self) -> Option<Self::Item> { 1044 self.iter.next_back() 1045 } 1046 } 1047 1048 impl<T, S1, S2> Clone for SymmetricDifference<'_, T, S1, S2> { clone(&self) -> Self1049 fn clone(&self) -> Self { 1050 SymmetricDifference { 1051 iter: self.iter.clone(), 1052 } 1053 } 1054 } 1055 1056 impl<T, S1, S2> fmt::Debug for SymmetricDifference<'_, T, S1, S2> 1057 where 1058 T: fmt::Debug + Eq + Hash, 1059 S1: BuildHasher, 1060 S2: BuildHasher, 1061 { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1062 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 1063 f.debug_list().entries(self.clone()).finish() 1064 } 1065 } 1066 1067 /// A lazy iterator producing elements in the union of `IndexSet`s. 1068 /// 1069 /// This `struct` is created by the [`union`] method on [`IndexSet`]. 1070 /// See its documentation for more. 1071 /// 1072 /// [`IndexSet`]: struct.IndexSet.html 1073 /// [`union`]: struct.IndexSet.html#method.union 1074 pub struct Union<'a, T, S> { 1075 iter: Chain<Iter<'a, T>, Difference<'a, T, S>>, 1076 } 1077 1078 impl<'a, T, S> Iterator for Union<'a, T, S> 1079 where 1080 T: Eq + Hash, 1081 S: BuildHasher, 1082 { 1083 type Item = &'a T; 1084 next(&mut self) -> Option<Self::Item>1085 fn next(&mut self) -> Option<Self::Item> { 1086 self.iter.next() 1087 } 1088 size_hint(&self) -> (usize, Option<usize>)1089 fn size_hint(&self) -> (usize, Option<usize>) { 1090 self.iter.size_hint() 1091 } 1092 fold<B, F>(self, init: B, f: F) -> B where F: FnMut(B, Self::Item) -> B,1093 fn fold<B, F>(self, init: B, f: F) -> B 1094 where 1095 F: FnMut(B, Self::Item) -> B, 1096 { 1097 self.iter.fold(init, f) 1098 } 1099 } 1100 1101 impl<T, S> DoubleEndedIterator for Union<'_, T, S> 1102 where 1103 T: Eq + Hash, 1104 S: BuildHasher, 1105 { next_back(&mut self) -> Option<Self::Item>1106 fn next_back(&mut self) -> Option<Self::Item> { 1107 self.iter.next_back() 1108 } 1109 } 1110 1111 impl<T, S> Clone for Union<'_, T, S> { clone(&self) -> Self1112 fn clone(&self) -> Self { 1113 Union { 1114 iter: self.iter.clone(), 1115 } 1116 } 1117 } 1118 1119 impl<T, S> fmt::Debug for Union<'_, T, S> 1120 where 1121 T: fmt::Debug + Eq + Hash, 1122 S: BuildHasher, 1123 { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1124 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 1125 f.debug_list().entries(self.clone()).finish() 1126 } 1127 } 1128 1129 impl<T, S1, S2> BitAnd<&IndexSet<T, S2>> for &IndexSet<T, S1> 1130 where 1131 T: Eq + Hash + Clone, 1132 S1: BuildHasher + Default, 1133 S2: BuildHasher, 1134 { 1135 type Output = IndexSet<T, S1>; 1136 1137 /// Returns the set intersection, cloned into a new set. 1138 /// 1139 /// Values are collected in the same order that they appear in `self`. bitand(self, other: &IndexSet<T, S2>) -> Self::Output1140 fn bitand(self, other: &IndexSet<T, S2>) -> Self::Output { 1141 self.intersection(other).cloned().collect() 1142 } 1143 } 1144 1145 impl<T, S1, S2> BitOr<&IndexSet<T, S2>> for &IndexSet<T, S1> 1146 where 1147 T: Eq + Hash + Clone, 1148 S1: BuildHasher + Default, 1149 S2: BuildHasher, 1150 { 1151 type Output = IndexSet<T, S1>; 1152 1153 /// Returns the set union, cloned into a new set. 1154 /// 1155 /// Values from `self` are collected in their original order, followed by 1156 /// values that are unique to `other` in their original order. bitor(self, other: &IndexSet<T, S2>) -> Self::Output1157 fn bitor(self, other: &IndexSet<T, S2>) -> Self::Output { 1158 self.union(other).cloned().collect() 1159 } 1160 } 1161 1162 impl<T, S1, S2> BitXor<&IndexSet<T, S2>> for &IndexSet<T, S1> 1163 where 1164 T: Eq + Hash + Clone, 1165 S1: BuildHasher + Default, 1166 S2: BuildHasher, 1167 { 1168 type Output = IndexSet<T, S1>; 1169 1170 /// Returns the set symmetric-difference, cloned into a new set. 1171 /// 1172 /// Values from `self` are collected in their original order, followed by 1173 /// values from `other` in their original order. bitxor(self, other: &IndexSet<T, S2>) -> Self::Output1174 fn bitxor(self, other: &IndexSet<T, S2>) -> Self::Output { 1175 self.symmetric_difference(other).cloned().collect() 1176 } 1177 } 1178 1179 impl<T, S1, S2> Sub<&IndexSet<T, S2>> for &IndexSet<T, S1> 1180 where 1181 T: Eq + Hash + Clone, 1182 S1: BuildHasher + Default, 1183 S2: BuildHasher, 1184 { 1185 type Output = IndexSet<T, S1>; 1186 1187 /// Returns the set difference, cloned into a new set. 1188 /// 1189 /// Values are collected in the same order that they appear in `self`. sub(self, other: &IndexSet<T, S2>) -> Self::Output1190 fn sub(self, other: &IndexSet<T, S2>) -> Self::Output { 1191 self.difference(other).cloned().collect() 1192 } 1193 } 1194 1195 #[cfg(test)] 1196 mod tests { 1197 use super::*; 1198 use crate::util::enumerate; 1199 use std::string::String; 1200 1201 #[test] it_works()1202 fn it_works() { 1203 let mut set = IndexSet::new(); 1204 assert_eq!(set.is_empty(), true); 1205 set.insert(1); 1206 set.insert(1); 1207 assert_eq!(set.len(), 1); 1208 assert!(set.get(&1).is_some()); 1209 assert_eq!(set.is_empty(), false); 1210 } 1211 1212 #[test] new()1213 fn new() { 1214 let set = IndexSet::<String>::new(); 1215 println!("{:?}", set); 1216 assert_eq!(set.capacity(), 0); 1217 assert_eq!(set.len(), 0); 1218 assert_eq!(set.is_empty(), true); 1219 } 1220 1221 #[test] insert()1222 fn insert() { 1223 let insert = [0, 4, 2, 12, 8, 7, 11, 5]; 1224 let not_present = [1, 3, 6, 9, 10]; 1225 let mut set = IndexSet::with_capacity(insert.len()); 1226 1227 for (i, &elt) in enumerate(&insert) { 1228 assert_eq!(set.len(), i); 1229 set.insert(elt); 1230 assert_eq!(set.len(), i + 1); 1231 assert_eq!(set.get(&elt), Some(&elt)); 1232 } 1233 println!("{:?}", set); 1234 1235 for &elt in ¬_present { 1236 assert!(set.get(&elt).is_none()); 1237 } 1238 } 1239 1240 #[test] insert_full()1241 fn insert_full() { 1242 let insert = vec![9, 2, 7, 1, 4, 6, 13]; 1243 let present = vec![1, 6, 2]; 1244 let mut set = IndexSet::with_capacity(insert.len()); 1245 1246 for (i, &elt) in enumerate(&insert) { 1247 assert_eq!(set.len(), i); 1248 let (index, success) = set.insert_full(elt); 1249 assert!(success); 1250 assert_eq!(Some(index), set.get_full(&elt).map(|x| x.0)); 1251 assert_eq!(set.len(), i + 1); 1252 } 1253 1254 let len = set.len(); 1255 for &elt in &present { 1256 let (index, success) = set.insert_full(elt); 1257 assert!(!success); 1258 assert_eq!(Some(index), set.get_full(&elt).map(|x| x.0)); 1259 assert_eq!(set.len(), len); 1260 } 1261 } 1262 1263 #[test] insert_2()1264 fn insert_2() { 1265 let mut set = IndexSet::with_capacity(16); 1266 1267 let mut values = vec![]; 1268 values.extend(0..16); 1269 values.extend(128..267); 1270 1271 for &i in &values { 1272 let old_set = set.clone(); 1273 set.insert(i); 1274 for value in old_set.iter() { 1275 if set.get(value).is_none() { 1276 println!("old_set: {:?}", old_set); 1277 println!("set: {:?}", set); 1278 panic!("did not find {} in set", value); 1279 } 1280 } 1281 } 1282 1283 for &i in &values { 1284 assert!(set.get(&i).is_some(), "did not find {}", i); 1285 } 1286 } 1287 1288 #[test] insert_dup()1289 fn insert_dup() { 1290 let mut elements = vec![0, 2, 4, 6, 8]; 1291 let mut set: IndexSet<u8> = elements.drain(..).collect(); 1292 { 1293 let (i, v) = set.get_full(&0).unwrap(); 1294 assert_eq!(set.len(), 5); 1295 assert_eq!(i, 0); 1296 assert_eq!(*v, 0); 1297 } 1298 { 1299 let inserted = set.insert(0); 1300 let (i, v) = set.get_full(&0).unwrap(); 1301 assert_eq!(set.len(), 5); 1302 assert_eq!(inserted, false); 1303 assert_eq!(i, 0); 1304 assert_eq!(*v, 0); 1305 } 1306 } 1307 1308 #[test] insert_order()1309 fn insert_order() { 1310 let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; 1311 let mut set = IndexSet::new(); 1312 1313 for &elt in &insert { 1314 set.insert(elt); 1315 } 1316 1317 assert_eq!(set.iter().count(), set.len()); 1318 assert_eq!(set.iter().count(), insert.len()); 1319 for (a, b) in insert.iter().zip(set.iter()) { 1320 assert_eq!(a, b); 1321 } 1322 for (i, v) in (0..insert.len()).zip(set.iter()) { 1323 assert_eq!(set.get_index(i).unwrap(), v); 1324 } 1325 } 1326 1327 #[test] grow()1328 fn grow() { 1329 let insert = [0, 4, 2, 12, 8, 7, 11]; 1330 let not_present = [1, 3, 6, 9, 10]; 1331 let mut set = IndexSet::with_capacity(insert.len()); 1332 1333 for (i, &elt) in enumerate(&insert) { 1334 assert_eq!(set.len(), i); 1335 set.insert(elt); 1336 assert_eq!(set.len(), i + 1); 1337 assert_eq!(set.get(&elt), Some(&elt)); 1338 } 1339 1340 println!("{:?}", set); 1341 for &elt in &insert { 1342 set.insert(elt * 10); 1343 } 1344 for &elt in &insert { 1345 set.insert(elt * 100); 1346 } 1347 for (i, &elt) in insert.iter().cycle().enumerate().take(100) { 1348 set.insert(elt * 100 + i as i32); 1349 } 1350 println!("{:?}", set); 1351 for &elt in ¬_present { 1352 assert!(set.get(&elt).is_none()); 1353 } 1354 } 1355 1356 #[test] reserve()1357 fn reserve() { 1358 let mut set = IndexSet::<usize>::new(); 1359 assert_eq!(set.capacity(), 0); 1360 set.reserve(100); 1361 let capacity = set.capacity(); 1362 assert!(capacity >= 100); 1363 for i in 0..capacity { 1364 assert_eq!(set.len(), i); 1365 set.insert(i); 1366 assert_eq!(set.len(), i + 1); 1367 assert_eq!(set.capacity(), capacity); 1368 assert_eq!(set.get(&i), Some(&i)); 1369 } 1370 set.insert(capacity); 1371 assert_eq!(set.len(), capacity + 1); 1372 assert!(set.capacity() > capacity); 1373 assert_eq!(set.get(&capacity), Some(&capacity)); 1374 } 1375 1376 #[test] shrink_to_fit()1377 fn shrink_to_fit() { 1378 let mut set = IndexSet::<usize>::new(); 1379 assert_eq!(set.capacity(), 0); 1380 for i in 0..100 { 1381 assert_eq!(set.len(), i); 1382 set.insert(i); 1383 assert_eq!(set.len(), i + 1); 1384 assert!(set.capacity() >= i + 1); 1385 assert_eq!(set.get(&i), Some(&i)); 1386 set.shrink_to_fit(); 1387 assert_eq!(set.len(), i + 1); 1388 assert_eq!(set.capacity(), i + 1); 1389 assert_eq!(set.get(&i), Some(&i)); 1390 } 1391 } 1392 1393 #[test] remove()1394 fn remove() { 1395 let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; 1396 let mut set = IndexSet::new(); 1397 1398 for &elt in &insert { 1399 set.insert(elt); 1400 } 1401 1402 assert_eq!(set.iter().count(), set.len()); 1403 assert_eq!(set.iter().count(), insert.len()); 1404 for (a, b) in insert.iter().zip(set.iter()) { 1405 assert_eq!(a, b); 1406 } 1407 1408 let remove_fail = [99, 77]; 1409 let remove = [4, 12, 8, 7]; 1410 1411 for &value in &remove_fail { 1412 assert!(set.swap_remove_full(&value).is_none()); 1413 } 1414 println!("{:?}", set); 1415 for &value in &remove { 1416 //println!("{:?}", set); 1417 let index = set.get_full(&value).unwrap().0; 1418 assert_eq!(set.swap_remove_full(&value), Some((index, value))); 1419 } 1420 println!("{:?}", set); 1421 1422 for value in &insert { 1423 assert_eq!(set.get(value).is_some(), !remove.contains(value)); 1424 } 1425 assert_eq!(set.len(), insert.len() - remove.len()); 1426 assert_eq!(set.iter().count(), insert.len() - remove.len()); 1427 } 1428 1429 #[test] swap_remove_index()1430 fn swap_remove_index() { 1431 let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; 1432 let mut set = IndexSet::new(); 1433 1434 for &elt in &insert { 1435 set.insert(elt); 1436 } 1437 1438 let mut vector = insert.to_vec(); 1439 let remove_sequence = &[3, 3, 10, 4, 5, 4, 3, 0, 1]; 1440 1441 // check that the same swap remove sequence on vec and set 1442 // have the same result. 1443 for &rm in remove_sequence { 1444 let out_vec = vector.swap_remove(rm); 1445 let out_set = set.swap_remove_index(rm).unwrap(); 1446 assert_eq!(out_vec, out_set); 1447 } 1448 assert_eq!(vector.len(), set.len()); 1449 for (a, b) in vector.iter().zip(set.iter()) { 1450 assert_eq!(a, b); 1451 } 1452 } 1453 1454 #[test] partial_eq_and_eq()1455 fn partial_eq_and_eq() { 1456 let mut set_a = IndexSet::new(); 1457 set_a.insert(1); 1458 set_a.insert(2); 1459 let mut set_b = set_a.clone(); 1460 assert_eq!(set_a, set_b); 1461 set_b.swap_remove(&1); 1462 assert_ne!(set_a, set_b); 1463 1464 let set_c: IndexSet<_> = set_b.into_iter().collect(); 1465 assert_ne!(set_a, set_c); 1466 assert_ne!(set_c, set_a); 1467 } 1468 1469 #[test] extend()1470 fn extend() { 1471 let mut set = IndexSet::new(); 1472 set.extend(vec![&1, &2, &3, &4]); 1473 set.extend(vec![5, 6]); 1474 assert_eq!(set.into_iter().collect::<Vec<_>>(), vec![1, 2, 3, 4, 5, 6]); 1475 } 1476 1477 #[test] comparisons()1478 fn comparisons() { 1479 let set_a: IndexSet<_> = (0..3).collect(); 1480 let set_b: IndexSet<_> = (3..6).collect(); 1481 let set_c: IndexSet<_> = (0..6).collect(); 1482 let set_d: IndexSet<_> = (3..9).collect(); 1483 1484 assert!(!set_a.is_disjoint(&set_a)); 1485 assert!(set_a.is_subset(&set_a)); 1486 assert!(set_a.is_superset(&set_a)); 1487 1488 assert!(set_a.is_disjoint(&set_b)); 1489 assert!(set_b.is_disjoint(&set_a)); 1490 assert!(!set_a.is_subset(&set_b)); 1491 assert!(!set_b.is_subset(&set_a)); 1492 assert!(!set_a.is_superset(&set_b)); 1493 assert!(!set_b.is_superset(&set_a)); 1494 1495 assert!(!set_a.is_disjoint(&set_c)); 1496 assert!(!set_c.is_disjoint(&set_a)); 1497 assert!(set_a.is_subset(&set_c)); 1498 assert!(!set_c.is_subset(&set_a)); 1499 assert!(!set_a.is_superset(&set_c)); 1500 assert!(set_c.is_superset(&set_a)); 1501 1502 assert!(!set_c.is_disjoint(&set_d)); 1503 assert!(!set_d.is_disjoint(&set_c)); 1504 assert!(!set_c.is_subset(&set_d)); 1505 assert!(!set_d.is_subset(&set_c)); 1506 assert!(!set_c.is_superset(&set_d)); 1507 assert!(!set_d.is_superset(&set_c)); 1508 } 1509 1510 #[test] iter_comparisons()1511 fn iter_comparisons() { 1512 use std::iter::empty; 1513 1514 fn check<'a, I1, I2>(iter1: I1, iter2: I2) 1515 where 1516 I1: Iterator<Item = &'a i32>, 1517 I2: Iterator<Item = i32>, 1518 { 1519 assert!(iter1.cloned().eq(iter2)); 1520 } 1521 1522 let set_a: IndexSet<_> = (0..3).collect(); 1523 let set_b: IndexSet<_> = (3..6).collect(); 1524 let set_c: IndexSet<_> = (0..6).collect(); 1525 let set_d: IndexSet<_> = (3..9).rev().collect(); 1526 1527 check(set_a.difference(&set_a), empty()); 1528 check(set_a.symmetric_difference(&set_a), empty()); 1529 check(set_a.intersection(&set_a), 0..3); 1530 check(set_a.union(&set_a), 0..3); 1531 1532 check(set_a.difference(&set_b), 0..3); 1533 check(set_b.difference(&set_a), 3..6); 1534 check(set_a.symmetric_difference(&set_b), 0..6); 1535 check(set_b.symmetric_difference(&set_a), (3..6).chain(0..3)); 1536 check(set_a.intersection(&set_b), empty()); 1537 check(set_b.intersection(&set_a), empty()); 1538 check(set_a.union(&set_b), 0..6); 1539 check(set_b.union(&set_a), (3..6).chain(0..3)); 1540 1541 check(set_a.difference(&set_c), empty()); 1542 check(set_c.difference(&set_a), 3..6); 1543 check(set_a.symmetric_difference(&set_c), 3..6); 1544 check(set_c.symmetric_difference(&set_a), 3..6); 1545 check(set_a.intersection(&set_c), 0..3); 1546 check(set_c.intersection(&set_a), 0..3); 1547 check(set_a.union(&set_c), 0..6); 1548 check(set_c.union(&set_a), 0..6); 1549 1550 check(set_c.difference(&set_d), 0..3); 1551 check(set_d.difference(&set_c), (6..9).rev()); 1552 check( 1553 set_c.symmetric_difference(&set_d), 1554 (0..3).chain((6..9).rev()), 1555 ); 1556 check(set_d.symmetric_difference(&set_c), (6..9).rev().chain(0..3)); 1557 check(set_c.intersection(&set_d), 3..6); 1558 check(set_d.intersection(&set_c), (3..6).rev()); 1559 check(set_c.union(&set_d), (0..6).chain((6..9).rev())); 1560 check(set_d.union(&set_c), (3..9).rev().chain(0..3)); 1561 } 1562 1563 #[test] ops()1564 fn ops() { 1565 let empty = IndexSet::<i32>::new(); 1566 let set_a: IndexSet<_> = (0..3).collect(); 1567 let set_b: IndexSet<_> = (3..6).collect(); 1568 let set_c: IndexSet<_> = (0..6).collect(); 1569 let set_d: IndexSet<_> = (3..9).rev().collect(); 1570 1571 // FIXME: #[allow(clippy::eq_op)] in Rust 1.31 1572 #[cfg_attr(feature = "cargo-clippy", allow(renamed_and_removed_lints, eq_op))] 1573 { 1574 assert_eq!(&set_a & &set_a, set_a); 1575 assert_eq!(&set_a | &set_a, set_a); 1576 assert_eq!(&set_a ^ &set_a, empty); 1577 assert_eq!(&set_a - &set_a, empty); 1578 } 1579 1580 assert_eq!(&set_a & &set_b, empty); 1581 assert_eq!(&set_b & &set_a, empty); 1582 assert_eq!(&set_a | &set_b, set_c); 1583 assert_eq!(&set_b | &set_a, set_c); 1584 assert_eq!(&set_a ^ &set_b, set_c); 1585 assert_eq!(&set_b ^ &set_a, set_c); 1586 assert_eq!(&set_a - &set_b, set_a); 1587 assert_eq!(&set_b - &set_a, set_b); 1588 1589 assert_eq!(&set_a & &set_c, set_a); 1590 assert_eq!(&set_c & &set_a, set_a); 1591 assert_eq!(&set_a | &set_c, set_c); 1592 assert_eq!(&set_c | &set_a, set_c); 1593 assert_eq!(&set_a ^ &set_c, set_b); 1594 assert_eq!(&set_c ^ &set_a, set_b); 1595 assert_eq!(&set_a - &set_c, empty); 1596 assert_eq!(&set_c - &set_a, set_b); 1597 1598 assert_eq!(&set_c & &set_d, set_b); 1599 assert_eq!(&set_d & &set_c, set_b); 1600 assert_eq!(&set_c | &set_d, &set_a | &set_d); 1601 assert_eq!(&set_d | &set_c, &set_a | &set_d); 1602 assert_eq!(&set_c ^ &set_d, &set_a | &(&set_d - &set_b)); 1603 assert_eq!(&set_d ^ &set_c, &set_a | &(&set_d - &set_b)); 1604 assert_eq!(&set_c - &set_d, set_a); 1605 assert_eq!(&set_d - &set_c, &set_d - &set_b); 1606 } 1607 } 1608