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, FusedIterator}; 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 pub(crate) map: IndexMap<T, (), S>, 65 } 66 #[cfg(not(has_std))] 67 pub struct IndexSet<T, S> { 68 pub(crate) 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`. 159 /// 160 /// This function is `const`, so it 161 /// can be called in `static` contexts. with_hasher(hash_builder: S) -> Self162 pub const fn with_hasher(hash_builder: S) -> Self { 163 IndexSet { 164 map: IndexMap::with_hasher(hash_builder), 165 } 166 } 167 168 /// Computes in **O(1)** time. capacity(&self) -> usize169 pub fn capacity(&self) -> usize { 170 self.map.capacity() 171 } 172 173 /// Return a reference to the set's `BuildHasher`. hasher(&self) -> &S174 pub fn hasher(&self) -> &S { 175 self.map.hasher() 176 } 177 178 /// Return the number of elements in the set. 179 /// 180 /// Computes in **O(1)** time. len(&self) -> usize181 pub fn len(&self) -> usize { 182 self.map.len() 183 } 184 185 /// Returns true if the set contains no elements. 186 /// 187 /// Computes in **O(1)** time. is_empty(&self) -> bool188 pub fn is_empty(&self) -> bool { 189 self.map.is_empty() 190 } 191 192 /// Return an iterator over the values of the set, in their order iter(&self) -> Iter<'_, T>193 pub fn iter(&self) -> Iter<'_, T> { 194 Iter { 195 iter: self.map.keys().iter, 196 } 197 } 198 199 /// Remove all elements in the set, while preserving its capacity. 200 /// 201 /// Computes in **O(n)** time. clear(&mut self)202 pub fn clear(&mut self) { 203 self.map.clear(); 204 } 205 206 /// Shortens the set, keeping the first `len` elements and dropping the rest. 207 /// 208 /// If `len` is greater than the set's current length, this has no effect. truncate(&mut self, len: usize)209 pub fn truncate(&mut self, len: usize) { 210 self.map.truncate(len); 211 } 212 213 /// Clears the `IndexSet` in the given index range, returning those values 214 /// as a drain iterator. 215 /// 216 /// The range may be any type that implements `RangeBounds<usize>`, 217 /// including all of the `std::ops::Range*` types, or even a tuple pair of 218 /// `Bound` start and end values. To drain the set entirely, use `RangeFull` 219 /// like `set.drain(..)`. 220 /// 221 /// This shifts down all entries following the drained range to fill the 222 /// gap, and keeps the allocated memory for reuse. 223 /// 224 /// ***Panics*** if the starting point is greater than the end point or if 225 /// the end point is greater than the length of the set. drain<R>(&mut self, range: R) -> Drain<'_, T> where R: RangeBounds<usize>,226 pub fn drain<R>(&mut self, range: R) -> Drain<'_, T> 227 where 228 R: RangeBounds<usize>, 229 { 230 Drain { 231 iter: self.map.drain(range).iter, 232 } 233 } 234 235 /// Splits the collection into two at the given index. 236 /// 237 /// Returns a newly allocated set containing the elements in the range 238 /// `[at, len)`. After the call, the original set will be left containing 239 /// the elements `[0, at)` with its previous capacity unchanged. 240 /// 241 /// ***Panics*** if `at > len`. split_off(&mut self, at: usize) -> Self where S: Clone,242 pub fn split_off(&mut self, at: usize) -> Self 243 where 244 S: Clone, 245 { 246 Self { 247 map: self.map.split_off(at), 248 } 249 } 250 } 251 252 impl<T, S> IndexSet<T, S> 253 where 254 T: Hash + Eq, 255 S: BuildHasher, 256 { 257 /// Reserve capacity for `additional` more values. 258 /// 259 /// Computes in **O(n)** time. reserve(&mut self, additional: usize)260 pub fn reserve(&mut self, additional: usize) { 261 self.map.reserve(additional); 262 } 263 264 /// Shrink the capacity of the set as much as possible. 265 /// 266 /// Computes in **O(n)** time. shrink_to_fit(&mut self)267 pub fn shrink_to_fit(&mut self) { 268 self.map.shrink_to_fit(); 269 } 270 271 /// Insert the value into the set. 272 /// 273 /// If an equivalent item already exists in the set, it returns 274 /// `false` leaving the original value in the set and without 275 /// altering its insertion order. Otherwise, it inserts the new 276 /// item and returns `true`. 277 /// 278 /// Computes in **O(1)** time (amortized average). insert(&mut self, value: T) -> bool279 pub fn insert(&mut self, value: T) -> bool { 280 self.map.insert(value, ()).is_none() 281 } 282 283 /// Insert the value into the set, and get its index. 284 /// 285 /// If an equivalent item already exists in the set, it returns 286 /// the index of the existing item and `false`, leaving the 287 /// original value in the set and without altering its insertion 288 /// order. Otherwise, it inserts the new item and returns the index 289 /// of the inserted item and `true`. 290 /// 291 /// Computes in **O(1)** time (amortized average). insert_full(&mut self, value: T) -> (usize, bool)292 pub fn insert_full(&mut self, value: T) -> (usize, bool) { 293 use super::map::Entry::*; 294 295 match self.map.entry(value) { 296 Occupied(e) => (e.index(), false), 297 Vacant(e) => { 298 let index = e.index(); 299 e.insert(()); 300 (index, true) 301 } 302 } 303 } 304 305 /// Return an iterator over the values that are in `self` but not `other`. 306 /// 307 /// 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,308 pub fn difference<'a, S2>(&'a self, other: &'a IndexSet<T, S2>) -> Difference<'a, T, S2> 309 where 310 S2: BuildHasher, 311 { 312 Difference { 313 iter: self.iter(), 314 other, 315 } 316 } 317 318 /// Return an iterator over the values that are in `self` or `other`, 319 /// but not in both. 320 /// 321 /// Values from `self` are produced in their original order, followed by 322 /// 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,323 pub fn symmetric_difference<'a, S2>( 324 &'a self, 325 other: &'a IndexSet<T, S2>, 326 ) -> SymmetricDifference<'a, T, S, S2> 327 where 328 S2: BuildHasher, 329 { 330 SymmetricDifference { 331 iter: self.difference(other).chain(other.difference(self)), 332 } 333 } 334 335 /// Return an iterator over the values that are in both `self` and `other`. 336 /// 337 /// 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,338 pub fn intersection<'a, S2>(&'a self, other: &'a IndexSet<T, S2>) -> Intersection<'a, T, S2> 339 where 340 S2: BuildHasher, 341 { 342 Intersection { 343 iter: self.iter(), 344 other, 345 } 346 } 347 348 /// Return an iterator over all values that are in `self` or `other`. 349 /// 350 /// Values from `self` are produced in their original order, followed by 351 /// 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,352 pub fn union<'a, S2>(&'a self, other: &'a IndexSet<T, S2>) -> Union<'a, T, S> 353 where 354 S2: BuildHasher, 355 { 356 Union { 357 iter: self.iter().chain(other.difference(self)), 358 } 359 } 360 361 /// Return `true` if an equivalent to `value` exists in the set. 362 /// 363 /// Computes in **O(1)** time (average). contains<Q: ?Sized>(&self, value: &Q) -> bool where Q: Hash + Equivalent<T>,364 pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool 365 where 366 Q: Hash + Equivalent<T>, 367 { 368 self.map.contains_key(value) 369 } 370 371 /// Return a reference to the value stored in the set, if it is present, 372 /// else `None`. 373 /// 374 /// Computes in **O(1)** time (average). get<Q: ?Sized>(&self, value: &Q) -> Option<&T> where Q: Hash + Equivalent<T>,375 pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T> 376 where 377 Q: Hash + Equivalent<T>, 378 { 379 self.map.get_key_value(value).map(|(x, &())| x) 380 } 381 382 /// Return item index and value get_full<Q: ?Sized>(&self, value: &Q) -> Option<(usize, &T)> where Q: Hash + Equivalent<T>,383 pub fn get_full<Q: ?Sized>(&self, value: &Q) -> Option<(usize, &T)> 384 where 385 Q: Hash + Equivalent<T>, 386 { 387 self.map.get_full(value).map(|(i, x, &())| (i, x)) 388 } 389 390 /// Return item index, if it exists in the set get_index_of<Q: ?Sized>(&self, value: &Q) -> Option<usize> where Q: Hash + Equivalent<T>,391 pub fn get_index_of<Q: ?Sized>(&self, value: &Q) -> Option<usize> 392 where 393 Q: Hash + Equivalent<T>, 394 { 395 self.map.get_index_of(value) 396 } 397 398 /// Adds a value to the set, replacing the existing value, if any, that is 399 /// equal to the given one. Returns the replaced value. 400 /// 401 /// Computes in **O(1)** time (average). replace(&mut self, value: T) -> Option<T>402 pub fn replace(&mut self, value: T) -> Option<T> { 403 use super::map::Entry::*; 404 405 match self.map.entry(value) { 406 Vacant(e) => { 407 e.insert(()); 408 None 409 } 410 Occupied(e) => Some(e.replace_key()), 411 } 412 } 413 414 /// Remove the value from the set, and return `true` if it was present. 415 /// 416 /// **NOTE:** This is equivalent to `.swap_remove(value)`, if you want 417 /// to preserve the order of the values in the set, use `.shift_remove(value)`. 418 /// 419 /// Computes in **O(1)** time (average). remove<Q: ?Sized>(&mut self, value: &Q) -> bool where Q: Hash + Equivalent<T>,420 pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool 421 where 422 Q: Hash + Equivalent<T>, 423 { 424 self.swap_remove(value) 425 } 426 427 /// Remove the value from the set, and return `true` if it was present. 428 /// 429 /// Like `Vec::swap_remove`, the value is removed by swapping it with the 430 /// last element of the set and popping it off. **This perturbs 431 /// the position of what used to be the last element!** 432 /// 433 /// Return `false` if `value` was not in the set. 434 /// 435 /// Computes in **O(1)** time (average). swap_remove<Q: ?Sized>(&mut self, value: &Q) -> bool where Q: Hash + Equivalent<T>,436 pub fn swap_remove<Q: ?Sized>(&mut self, value: &Q) -> bool 437 where 438 Q: Hash + Equivalent<T>, 439 { 440 self.map.swap_remove(value).is_some() 441 } 442 443 /// Remove the value from the set, and return `true` if it was present. 444 /// 445 /// Like `Vec::remove`, the value is removed by shifting all of the 446 /// elements that follow it, preserving their relative order. 447 /// **This perturbs the index of all of those elements!** 448 /// 449 /// Return `false` if `value` was not in the set. 450 /// 451 /// Computes in **O(n)** time (average). shift_remove<Q: ?Sized>(&mut self, value: &Q) -> bool where Q: Hash + Equivalent<T>,452 pub fn shift_remove<Q: ?Sized>(&mut self, value: &Q) -> bool 453 where 454 Q: Hash + Equivalent<T>, 455 { 456 self.map.shift_remove(value).is_some() 457 } 458 459 /// Removes and returns the value in the set, if any, that is equal to the 460 /// given one. 461 /// 462 /// **NOTE:** This is equivalent to `.swap_take(value)`, if you need to 463 /// preserve the order of the values in the set, use `.shift_take(value)` 464 /// instead. 465 /// 466 /// Computes in **O(1)** time (average). take<Q: ?Sized>(&mut self, value: &Q) -> Option<T> where Q: Hash + Equivalent<T>,467 pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T> 468 where 469 Q: Hash + Equivalent<T>, 470 { 471 self.swap_take(value) 472 } 473 474 /// Removes and returns the value in the set, if any, that is equal to the 475 /// given one. 476 /// 477 /// Like `Vec::swap_remove`, the value is removed by swapping it with the 478 /// last element of the set and popping it off. **This perturbs 479 /// the position of what used to be the last element!** 480 /// 481 /// Return `None` if `value` was not in the set. 482 /// 483 /// Computes in **O(1)** time (average). swap_take<Q: ?Sized>(&mut self, value: &Q) -> Option<T> where Q: Hash + Equivalent<T>,484 pub fn swap_take<Q: ?Sized>(&mut self, value: &Q) -> Option<T> 485 where 486 Q: Hash + Equivalent<T>, 487 { 488 self.map.swap_remove_entry(value).map(|(x, ())| x) 489 } 490 491 /// Removes and returns the value in the set, if any, that is equal to the 492 /// given one. 493 /// 494 /// Like `Vec::remove`, the value is removed by shifting all of the 495 /// elements that follow it, preserving their relative order. 496 /// **This perturbs the index of all of those elements!** 497 /// 498 /// Return `None` if `value` was not in the set. 499 /// 500 /// Computes in **O(n)** time (average). shift_take<Q: ?Sized>(&mut self, value: &Q) -> Option<T> where Q: Hash + Equivalent<T>,501 pub fn shift_take<Q: ?Sized>(&mut self, value: &Q) -> Option<T> 502 where 503 Q: Hash + Equivalent<T>, 504 { 505 self.map.shift_remove_entry(value).map(|(x, ())| x) 506 } 507 508 /// Remove the value from the set return it and the index it had. 509 /// 510 /// Like `Vec::swap_remove`, the value is removed by swapping it with the 511 /// last element of the set and popping it off. **This perturbs 512 /// the position of what used to be the last element!** 513 /// 514 /// 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>,515 pub fn swap_remove_full<Q: ?Sized>(&mut self, value: &Q) -> Option<(usize, T)> 516 where 517 Q: Hash + Equivalent<T>, 518 { 519 self.map.swap_remove_full(value).map(|(i, x, ())| (i, x)) 520 } 521 522 /// Remove the value from the set return it and the index it had. 523 /// 524 /// Like `Vec::remove`, the value is removed by shifting all of the 525 /// elements that follow it, preserving their relative order. 526 /// **This perturbs the index of all of those elements!** 527 /// 528 /// 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>,529 pub fn shift_remove_full<Q: ?Sized>(&mut self, value: &Q) -> Option<(usize, T)> 530 where 531 Q: Hash + Equivalent<T>, 532 { 533 self.map.shift_remove_full(value).map(|(i, x, ())| (i, x)) 534 } 535 536 /// Remove the last value 537 /// 538 /// This preserves the order of the remaining elements. 539 /// 540 /// Computes in **O(1)** time (average). pop(&mut self) -> Option<T>541 pub fn pop(&mut self) -> Option<T> { 542 self.map.pop().map(|(x, ())| x) 543 } 544 545 /// Scan through each value in the set and keep those where the 546 /// closure `keep` returns `true`. 547 /// 548 /// The elements are visited in order, and remaining elements keep their 549 /// order. 550 /// 551 /// Computes in **O(n)** time (average). retain<F>(&mut self, mut keep: F) where F: FnMut(&T) -> bool,552 pub fn retain<F>(&mut self, mut keep: F) 553 where 554 F: FnMut(&T) -> bool, 555 { 556 self.map.retain(move |x, &mut ()| keep(x)) 557 } 558 559 /// Sort the set’s values by their default ordering. 560 /// 561 /// See [`sort_by`](Self::sort_by) for details. sort(&mut self) where T: Ord,562 pub fn sort(&mut self) 563 where 564 T: Ord, 565 { 566 self.map.sort_keys() 567 } 568 569 /// Sort the set’s values in place using the comparison function `cmp`. 570 /// 571 /// Computes in **O(n log n)** time and **O(n)** space. The sort is stable. sort_by<F>(&mut self, mut cmp: F) where F: FnMut(&T, &T) -> Ordering,572 pub fn sort_by<F>(&mut self, mut cmp: F) 573 where 574 F: FnMut(&T, &T) -> Ordering, 575 { 576 self.map.sort_by(move |a, _, b, _| cmp(a, b)); 577 } 578 579 /// Sort the values of the set and return a by-value iterator of 580 /// the values with the result. 581 /// 582 /// The sort is stable. sorted_by<F>(self, mut cmp: F) -> IntoIter<T> where F: FnMut(&T, &T) -> Ordering,583 pub fn sorted_by<F>(self, mut cmp: F) -> IntoIter<T> 584 where 585 F: FnMut(&T, &T) -> Ordering, 586 { 587 IntoIter { 588 iter: self.map.sorted_by(move |a, _, b, _| cmp(a, b)).iter, 589 } 590 } 591 592 /// Sort the set's values by their default ordering. 593 /// 594 /// See [`sort_unstable_by`](Self::sort_unstable_by) for details. sort_unstable(&mut self) where T: Ord,595 pub fn sort_unstable(&mut self) 596 where 597 T: Ord, 598 { 599 self.map.sort_unstable_keys() 600 } 601 602 /// Sort the set's values in place using the comparison funtion `cmp`. 603 /// 604 /// Computes in **O(n log n)** time. The sort is unstable. sort_unstable_by<F>(&mut self, mut cmp: F) where F: FnMut(&T, &T) -> Ordering,605 pub fn sort_unstable_by<F>(&mut self, mut cmp: F) 606 where 607 F: FnMut(&T, &T) -> Ordering, 608 { 609 self.map.sort_unstable_by(move |a, _, b, _| cmp(a, b)) 610 } 611 612 /// Sort the values of the set and return a by-value iterator of 613 /// the values with the result. sorted_unstable_by<F>(self, mut cmp: F) -> IntoIter<T> where F: FnMut(&T, &T) -> Ordering,614 pub fn sorted_unstable_by<F>(self, mut cmp: F) -> IntoIter<T> 615 where 616 F: FnMut(&T, &T) -> Ordering, 617 { 618 IntoIter { 619 iter: self 620 .map 621 .sorted_unstable_by(move |a, _, b, _| cmp(a, b)) 622 .iter, 623 } 624 } 625 626 /// Reverses the order of the set’s values in place. 627 /// 628 /// Computes in **O(n)** time and **O(1)** space. reverse(&mut self)629 pub fn reverse(&mut self) { 630 self.map.reverse() 631 } 632 } 633 634 impl<T, S> IndexSet<T, S> { 635 /// Get a value by index 636 /// 637 /// Valid indices are *0 <= index < self.len()* 638 /// 639 /// Computes in **O(1)** time. get_index(&self, index: usize) -> Option<&T>640 pub fn get_index(&self, index: usize) -> Option<&T> { 641 self.as_entries().get(index).map(Bucket::key_ref) 642 } 643 644 /// Get the first value 645 /// 646 /// Computes in **O(1)** time. first(&self) -> Option<&T>647 pub fn first(&self) -> Option<&T> { 648 self.as_entries().first().map(Bucket::key_ref) 649 } 650 651 /// Get the last value 652 /// 653 /// Computes in **O(1)** time. last(&self) -> Option<&T>654 pub fn last(&self) -> Option<&T> { 655 self.as_entries().last().map(Bucket::key_ref) 656 } 657 658 /// Remove the value by index 659 /// 660 /// Valid indices are *0 <= index < self.len()* 661 /// 662 /// Like `Vec::swap_remove`, the value is removed by swapping it with the 663 /// last element of the set and popping it off. **This perturbs 664 /// the position of what used to be the last element!** 665 /// 666 /// Computes in **O(1)** time (average). swap_remove_index(&mut self, index: usize) -> Option<T>667 pub fn swap_remove_index(&mut self, index: usize) -> Option<T> { 668 self.map.swap_remove_index(index).map(|(x, ())| x) 669 } 670 671 /// Remove the value by index 672 /// 673 /// Valid indices are *0 <= index < self.len()* 674 /// 675 /// Like `Vec::remove`, the value is removed by shifting all of the 676 /// elements that follow it, preserving their relative order. 677 /// **This perturbs the index of all of those elements!** 678 /// 679 /// Computes in **O(n)** time (average). shift_remove_index(&mut self, index: usize) -> Option<T>680 pub fn shift_remove_index(&mut self, index: usize) -> Option<T> { 681 self.map.shift_remove_index(index).map(|(x, ())| x) 682 } 683 684 /// Swaps the position of two values in the set. 685 /// 686 /// ***Panics*** if `a` or `b` are out of bounds. swap_indices(&mut self, a: usize, b: usize)687 pub fn swap_indices(&mut self, a: usize, b: usize) { 688 self.map.swap_indices(a, b) 689 } 690 } 691 692 /// Access `IndexSet` values at indexed positions. 693 /// 694 /// # Examples 695 /// 696 /// ``` 697 /// use indexmap::IndexSet; 698 /// 699 /// let mut set = IndexSet::new(); 700 /// for word in "Lorem ipsum dolor sit amet".split_whitespace() { 701 /// set.insert(word.to_string()); 702 /// } 703 /// assert_eq!(set[0], "Lorem"); 704 /// assert_eq!(set[1], "ipsum"); 705 /// set.reverse(); 706 /// assert_eq!(set[0], "amet"); 707 /// assert_eq!(set[1], "sit"); 708 /// set.sort(); 709 /// assert_eq!(set[0], "Lorem"); 710 /// assert_eq!(set[1], "amet"); 711 /// ``` 712 /// 713 /// ```should_panic 714 /// use indexmap::IndexSet; 715 /// 716 /// let mut set = IndexSet::new(); 717 /// set.insert("foo"); 718 /// println!("{:?}", set[10]); // panics! 719 /// ``` 720 impl<T, S> Index<usize> for IndexSet<T, S> { 721 type Output = T; 722 723 /// Returns a reference to the value at the supplied `index`. 724 /// 725 /// ***Panics*** if `index` is out of bounds. index(&self, index: usize) -> &T726 fn index(&self, index: usize) -> &T { 727 self.get_index(index) 728 .expect("IndexSet: index out of bounds") 729 } 730 } 731 732 /// An owning iterator over the items of a `IndexSet`. 733 /// 734 /// This `struct` is created by the [`into_iter`] method on [`IndexSet`] 735 /// (provided by the `IntoIterator` trait). See its documentation for more. 736 /// 737 /// [`IndexSet`]: struct.IndexSet.html 738 /// [`into_iter`]: struct.IndexSet.html#method.into_iter 739 pub struct IntoIter<T> { 740 iter: vec::IntoIter<Bucket<T>>, 741 } 742 743 impl<T> Iterator for IntoIter<T> { 744 type Item = T; 745 746 iterator_methods!(Bucket::key); 747 } 748 749 impl<T> DoubleEndedIterator for IntoIter<T> { 750 double_ended_iterator_methods!(Bucket::key); 751 } 752 753 impl<T> ExactSizeIterator for IntoIter<T> { len(&self) -> usize754 fn len(&self) -> usize { 755 self.iter.len() 756 } 757 } 758 759 impl<T> FusedIterator for IntoIter<T> {} 760 761 impl<T: fmt::Debug> fmt::Debug for IntoIter<T> { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result762 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 763 let iter = self.iter.as_slice().iter().map(Bucket::key_ref); 764 f.debug_list().entries(iter).finish() 765 } 766 } 767 768 /// An iterator over the items of a `IndexSet`. 769 /// 770 /// This `struct` is created by the [`iter`] method on [`IndexSet`]. 771 /// See its documentation for more. 772 /// 773 /// [`IndexSet`]: struct.IndexSet.html 774 /// [`iter`]: struct.IndexSet.html#method.iter 775 pub struct Iter<'a, T> { 776 iter: slice::Iter<'a, Bucket<T>>, 777 } 778 779 impl<'a, T> Iterator for Iter<'a, T> { 780 type Item = &'a T; 781 782 iterator_methods!(Bucket::key_ref); 783 } 784 785 impl<T> DoubleEndedIterator for Iter<'_, T> { 786 double_ended_iterator_methods!(Bucket::key_ref); 787 } 788 789 impl<T> ExactSizeIterator for Iter<'_, T> { len(&self) -> usize790 fn len(&self) -> usize { 791 self.iter.len() 792 } 793 } 794 795 impl<T> FusedIterator for Iter<'_, T> {} 796 797 impl<T> Clone for Iter<'_, T> { clone(&self) -> Self798 fn clone(&self) -> Self { 799 Iter { 800 iter: self.iter.clone(), 801 } 802 } 803 } 804 805 impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result806 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 807 f.debug_list().entries(self.clone()).finish() 808 } 809 } 810 811 /// A draining iterator over the items of a `IndexSet`. 812 /// 813 /// This `struct` is created by the [`drain`] method on [`IndexSet`]. 814 /// See its documentation for more. 815 /// 816 /// [`IndexSet`]: struct.IndexSet.html 817 /// [`drain`]: struct.IndexSet.html#method.drain 818 pub struct Drain<'a, T> { 819 iter: vec::Drain<'a, Bucket<T>>, 820 } 821 822 impl<T> Iterator for Drain<'_, T> { 823 type Item = T; 824 825 iterator_methods!(Bucket::key); 826 } 827 828 impl<T> DoubleEndedIterator for Drain<'_, T> { 829 double_ended_iterator_methods!(Bucket::key); 830 } 831 832 impl<T> ExactSizeIterator for Drain<'_, T> { len(&self) -> usize833 fn len(&self) -> usize { 834 self.iter.len() 835 } 836 } 837 838 impl<T> FusedIterator for Drain<'_, T> {} 839 840 impl<T: fmt::Debug> fmt::Debug for Drain<'_, T> { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result841 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 842 let iter = self.iter.as_slice().iter().map(Bucket::key_ref); 843 f.debug_list().entries(iter).finish() 844 } 845 } 846 847 impl<'a, T, S> IntoIterator for &'a IndexSet<T, S> { 848 type Item = &'a T; 849 type IntoIter = Iter<'a, T>; 850 into_iter(self) -> Self::IntoIter851 fn into_iter(self) -> Self::IntoIter { 852 self.iter() 853 } 854 } 855 856 impl<T, S> IntoIterator for IndexSet<T, S> { 857 type Item = T; 858 type IntoIter = IntoIter<T>; 859 into_iter(self) -> Self::IntoIter860 fn into_iter(self) -> Self::IntoIter { 861 IntoIter { 862 iter: self.map.into_iter().iter, 863 } 864 } 865 } 866 867 impl<T, S> FromIterator<T> for IndexSet<T, S> 868 where 869 T: Hash + Eq, 870 S: BuildHasher + Default, 871 { from_iter<I: IntoIterator<Item = T>>(iterable: I) -> Self872 fn from_iter<I: IntoIterator<Item = T>>(iterable: I) -> Self { 873 let iter = iterable.into_iter().map(|x| (x, ())); 874 IndexSet { 875 map: IndexMap::from_iter(iter), 876 } 877 } 878 } 879 880 #[cfg(all(has_std, rustc_1_51))] 881 impl<T, const N: usize> From<[T; N]> for IndexSet<T, RandomState> 882 where 883 T: Eq + Hash, 884 { 885 /// # Examples 886 /// 887 /// ``` 888 /// use indexmap::IndexSet; 889 /// 890 /// let set1 = IndexSet::from([1, 2, 3, 4]); 891 /// let set2: IndexSet<_> = [1, 2, 3, 4].into(); 892 /// assert_eq!(set1, set2); 893 /// ``` from(arr: [T; N]) -> Self894 fn from(arr: [T; N]) -> Self { 895 std::array::IntoIter::new(arr).collect() 896 } 897 } 898 899 impl<T, S> Extend<T> for IndexSet<T, S> 900 where 901 T: Hash + Eq, 902 S: BuildHasher, 903 { extend<I: IntoIterator<Item = T>>(&mut self, iterable: I)904 fn extend<I: IntoIterator<Item = T>>(&mut self, iterable: I) { 905 let iter = iterable.into_iter().map(|x| (x, ())); 906 self.map.extend(iter); 907 } 908 } 909 910 impl<'a, T, S> Extend<&'a T> for IndexSet<T, S> 911 where 912 T: Hash + Eq + Copy + 'a, 913 S: BuildHasher, 914 { extend<I: IntoIterator<Item = &'a T>>(&mut self, iterable: I)915 fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iterable: I) { 916 let iter = iterable.into_iter().copied(); 917 self.extend(iter); 918 } 919 } 920 921 impl<T, S> Default for IndexSet<T, S> 922 where 923 S: Default, 924 { 925 /// Return an empty `IndexSet` default() -> Self926 fn default() -> Self { 927 IndexSet { 928 map: IndexMap::default(), 929 } 930 } 931 } 932 933 impl<T, S1, S2> PartialEq<IndexSet<T, S2>> for IndexSet<T, S1> 934 where 935 T: Hash + Eq, 936 S1: BuildHasher, 937 S2: BuildHasher, 938 { eq(&self, other: &IndexSet<T, S2>) -> bool939 fn eq(&self, other: &IndexSet<T, S2>) -> bool { 940 self.len() == other.len() && self.is_subset(other) 941 } 942 } 943 944 impl<T, S> Eq for IndexSet<T, S> 945 where 946 T: Eq + Hash, 947 S: BuildHasher, 948 { 949 } 950 951 impl<T, S> IndexSet<T, S> 952 where 953 T: Eq + Hash, 954 S: BuildHasher, 955 { 956 /// Returns `true` if `self` has no elements in common with `other`. is_disjoint<S2>(&self, other: &IndexSet<T, S2>) -> bool where S2: BuildHasher,957 pub fn is_disjoint<S2>(&self, other: &IndexSet<T, S2>) -> bool 958 where 959 S2: BuildHasher, 960 { 961 if self.len() <= other.len() { 962 self.iter().all(move |value| !other.contains(value)) 963 } else { 964 other.iter().all(move |value| !self.contains(value)) 965 } 966 } 967 968 /// Returns `true` if all elements of `self` are contained in `other`. is_subset<S2>(&self, other: &IndexSet<T, S2>) -> bool where S2: BuildHasher,969 pub fn is_subset<S2>(&self, other: &IndexSet<T, S2>) -> bool 970 where 971 S2: BuildHasher, 972 { 973 self.len() <= other.len() && self.iter().all(move |value| other.contains(value)) 974 } 975 976 /// Returns `true` if all elements of `other` are contained in `self`. is_superset<S2>(&self, other: &IndexSet<T, S2>) -> bool where S2: BuildHasher,977 pub fn is_superset<S2>(&self, other: &IndexSet<T, S2>) -> bool 978 where 979 S2: BuildHasher, 980 { 981 other.is_subset(self) 982 } 983 } 984 985 /// A lazy iterator producing elements in the difference of `IndexSet`s. 986 /// 987 /// This `struct` is created by the [`difference`] method on [`IndexSet`]. 988 /// See its documentation for more. 989 /// 990 /// [`IndexSet`]: struct.IndexSet.html 991 /// [`difference`]: struct.IndexSet.html#method.difference 992 pub struct Difference<'a, T, S> { 993 iter: Iter<'a, T>, 994 other: &'a IndexSet<T, S>, 995 } 996 997 impl<'a, T, S> Iterator for Difference<'a, T, S> 998 where 999 T: Eq + Hash, 1000 S: BuildHasher, 1001 { 1002 type Item = &'a T; 1003 next(&mut self) -> Option<Self::Item>1004 fn next(&mut self) -> Option<Self::Item> { 1005 while let Some(item) = self.iter.next() { 1006 if !self.other.contains(item) { 1007 return Some(item); 1008 } 1009 } 1010 None 1011 } 1012 size_hint(&self) -> (usize, Option<usize>)1013 fn size_hint(&self) -> (usize, Option<usize>) { 1014 (0, self.iter.size_hint().1) 1015 } 1016 } 1017 1018 impl<T, S> DoubleEndedIterator for Difference<'_, T, S> 1019 where 1020 T: Eq + Hash, 1021 S: BuildHasher, 1022 { next_back(&mut self) -> Option<Self::Item>1023 fn next_back(&mut self) -> Option<Self::Item> { 1024 while let Some(item) = self.iter.next_back() { 1025 if !self.other.contains(item) { 1026 return Some(item); 1027 } 1028 } 1029 None 1030 } 1031 } 1032 1033 impl<T, S> FusedIterator for Difference<'_, T, S> 1034 where 1035 T: Eq + Hash, 1036 S: BuildHasher, 1037 { 1038 } 1039 1040 impl<T, S> Clone for Difference<'_, T, S> { clone(&self) -> Self1041 fn clone(&self) -> Self { 1042 Difference { 1043 iter: self.iter.clone(), 1044 ..*self 1045 } 1046 } 1047 } 1048 1049 impl<T, S> fmt::Debug for Difference<'_, T, S> 1050 where 1051 T: fmt::Debug + Eq + Hash, 1052 S: BuildHasher, 1053 { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1054 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 1055 f.debug_list().entries(self.clone()).finish() 1056 } 1057 } 1058 1059 /// A lazy iterator producing elements in the intersection of `IndexSet`s. 1060 /// 1061 /// This `struct` is created by the [`intersection`] method on [`IndexSet`]. 1062 /// See its documentation for more. 1063 /// 1064 /// [`IndexSet`]: struct.IndexSet.html 1065 /// [`intersection`]: struct.IndexSet.html#method.intersection 1066 pub struct Intersection<'a, T, S> { 1067 iter: Iter<'a, T>, 1068 other: &'a IndexSet<T, S>, 1069 } 1070 1071 impl<'a, T, S> Iterator for Intersection<'a, T, S> 1072 where 1073 T: Eq + Hash, 1074 S: BuildHasher, 1075 { 1076 type Item = &'a T; 1077 next(&mut self) -> Option<Self::Item>1078 fn next(&mut self) -> Option<Self::Item> { 1079 while let Some(item) = self.iter.next() { 1080 if self.other.contains(item) { 1081 return Some(item); 1082 } 1083 } 1084 None 1085 } 1086 size_hint(&self) -> (usize, Option<usize>)1087 fn size_hint(&self) -> (usize, Option<usize>) { 1088 (0, self.iter.size_hint().1) 1089 } 1090 } 1091 1092 impl<T, S> DoubleEndedIterator for Intersection<'_, T, S> 1093 where 1094 T: Eq + Hash, 1095 S: BuildHasher, 1096 { next_back(&mut self) -> Option<Self::Item>1097 fn next_back(&mut self) -> Option<Self::Item> { 1098 while let Some(item) = self.iter.next_back() { 1099 if self.other.contains(item) { 1100 return Some(item); 1101 } 1102 } 1103 None 1104 } 1105 } 1106 1107 impl<T, S> FusedIterator for Intersection<'_, T, S> 1108 where 1109 T: Eq + Hash, 1110 S: BuildHasher, 1111 { 1112 } 1113 1114 impl<T, S> Clone for Intersection<'_, T, S> { clone(&self) -> Self1115 fn clone(&self) -> Self { 1116 Intersection { 1117 iter: self.iter.clone(), 1118 ..*self 1119 } 1120 } 1121 } 1122 1123 impl<T, S> fmt::Debug for Intersection<'_, T, S> 1124 where 1125 T: fmt::Debug + Eq + Hash, 1126 S: BuildHasher, 1127 { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1128 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 1129 f.debug_list().entries(self.clone()).finish() 1130 } 1131 } 1132 1133 /// A lazy iterator producing elements in the symmetric difference of `IndexSet`s. 1134 /// 1135 /// This `struct` is created by the [`symmetric_difference`] method on 1136 /// [`IndexSet`]. See its documentation for more. 1137 /// 1138 /// [`IndexSet`]: struct.IndexSet.html 1139 /// [`symmetric_difference`]: struct.IndexSet.html#method.symmetric_difference 1140 pub struct SymmetricDifference<'a, T, S1, S2> { 1141 iter: Chain<Difference<'a, T, S2>, Difference<'a, T, S1>>, 1142 } 1143 1144 impl<'a, T, S1, S2> Iterator for SymmetricDifference<'a, T, S1, S2> 1145 where 1146 T: Eq + Hash, 1147 S1: BuildHasher, 1148 S2: BuildHasher, 1149 { 1150 type Item = &'a T; 1151 next(&mut self) -> Option<Self::Item>1152 fn next(&mut self) -> Option<Self::Item> { 1153 self.iter.next() 1154 } 1155 size_hint(&self) -> (usize, Option<usize>)1156 fn size_hint(&self) -> (usize, Option<usize>) { 1157 self.iter.size_hint() 1158 } 1159 fold<B, F>(self, init: B, f: F) -> B where F: FnMut(B, Self::Item) -> B,1160 fn fold<B, F>(self, init: B, f: F) -> B 1161 where 1162 F: FnMut(B, Self::Item) -> B, 1163 { 1164 self.iter.fold(init, f) 1165 } 1166 } 1167 1168 impl<T, S1, S2> DoubleEndedIterator for SymmetricDifference<'_, T, S1, S2> 1169 where 1170 T: Eq + Hash, 1171 S1: BuildHasher, 1172 S2: BuildHasher, 1173 { next_back(&mut self) -> Option<Self::Item>1174 fn next_back(&mut self) -> Option<Self::Item> { 1175 self.iter.next_back() 1176 } 1177 rfold<B, F>(self, init: B, f: F) -> B where F: FnMut(B, Self::Item) -> B,1178 fn rfold<B, F>(self, init: B, f: F) -> B 1179 where 1180 F: FnMut(B, Self::Item) -> B, 1181 { 1182 self.iter.rfold(init, f) 1183 } 1184 } 1185 1186 impl<T, S1, S2> FusedIterator for SymmetricDifference<'_, T, S1, S2> 1187 where 1188 T: Eq + Hash, 1189 S1: BuildHasher, 1190 S2: BuildHasher, 1191 { 1192 } 1193 1194 impl<T, S1, S2> Clone for SymmetricDifference<'_, T, S1, S2> { clone(&self) -> Self1195 fn clone(&self) -> Self { 1196 SymmetricDifference { 1197 iter: self.iter.clone(), 1198 } 1199 } 1200 } 1201 1202 impl<T, S1, S2> fmt::Debug for SymmetricDifference<'_, T, S1, S2> 1203 where 1204 T: fmt::Debug + Eq + Hash, 1205 S1: BuildHasher, 1206 S2: BuildHasher, 1207 { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1208 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 1209 f.debug_list().entries(self.clone()).finish() 1210 } 1211 } 1212 1213 /// A lazy iterator producing elements in the union of `IndexSet`s. 1214 /// 1215 /// This `struct` is created by the [`union`] method on [`IndexSet`]. 1216 /// See its documentation for more. 1217 /// 1218 /// [`IndexSet`]: struct.IndexSet.html 1219 /// [`union`]: struct.IndexSet.html#method.union 1220 pub struct Union<'a, T, S> { 1221 iter: Chain<Iter<'a, T>, Difference<'a, T, S>>, 1222 } 1223 1224 impl<'a, T, S> Iterator for Union<'a, T, S> 1225 where 1226 T: Eq + Hash, 1227 S: BuildHasher, 1228 { 1229 type Item = &'a T; 1230 next(&mut self) -> Option<Self::Item>1231 fn next(&mut self) -> Option<Self::Item> { 1232 self.iter.next() 1233 } 1234 size_hint(&self) -> (usize, Option<usize>)1235 fn size_hint(&self) -> (usize, Option<usize>) { 1236 self.iter.size_hint() 1237 } 1238 fold<B, F>(self, init: B, f: F) -> B where F: FnMut(B, Self::Item) -> B,1239 fn fold<B, F>(self, init: B, f: F) -> B 1240 where 1241 F: FnMut(B, Self::Item) -> B, 1242 { 1243 self.iter.fold(init, f) 1244 } 1245 } 1246 1247 impl<T, S> DoubleEndedIterator for Union<'_, T, S> 1248 where 1249 T: Eq + Hash, 1250 S: BuildHasher, 1251 { next_back(&mut self) -> Option<Self::Item>1252 fn next_back(&mut self) -> Option<Self::Item> { 1253 self.iter.next_back() 1254 } 1255 rfold<B, F>(self, init: B, f: F) -> B where F: FnMut(B, Self::Item) -> B,1256 fn rfold<B, F>(self, init: B, f: F) -> B 1257 where 1258 F: FnMut(B, Self::Item) -> B, 1259 { 1260 self.iter.rfold(init, f) 1261 } 1262 } 1263 1264 impl<T, S> FusedIterator for Union<'_, T, S> 1265 where 1266 T: Eq + Hash, 1267 S: BuildHasher, 1268 { 1269 } 1270 1271 impl<T, S> Clone for Union<'_, T, S> { clone(&self) -> Self1272 fn clone(&self) -> Self { 1273 Union { 1274 iter: self.iter.clone(), 1275 } 1276 } 1277 } 1278 1279 impl<T, S> fmt::Debug for Union<'_, T, S> 1280 where 1281 T: fmt::Debug + Eq + Hash, 1282 S: BuildHasher, 1283 { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1284 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 1285 f.debug_list().entries(self.clone()).finish() 1286 } 1287 } 1288 1289 impl<T, S1, S2> BitAnd<&IndexSet<T, S2>> for &IndexSet<T, S1> 1290 where 1291 T: Eq + Hash + Clone, 1292 S1: BuildHasher + Default, 1293 S2: BuildHasher, 1294 { 1295 type Output = IndexSet<T, S1>; 1296 1297 /// Returns the set intersection, cloned into a new set. 1298 /// 1299 /// Values are collected in the same order that they appear in `self`. bitand(self, other: &IndexSet<T, S2>) -> Self::Output1300 fn bitand(self, other: &IndexSet<T, S2>) -> Self::Output { 1301 self.intersection(other).cloned().collect() 1302 } 1303 } 1304 1305 impl<T, S1, S2> BitOr<&IndexSet<T, S2>> for &IndexSet<T, S1> 1306 where 1307 T: Eq + Hash + Clone, 1308 S1: BuildHasher + Default, 1309 S2: BuildHasher, 1310 { 1311 type Output = IndexSet<T, S1>; 1312 1313 /// Returns the set union, cloned into a new set. 1314 /// 1315 /// Values from `self` are collected in their original order, followed by 1316 /// values that are unique to `other` in their original order. bitor(self, other: &IndexSet<T, S2>) -> Self::Output1317 fn bitor(self, other: &IndexSet<T, S2>) -> Self::Output { 1318 self.union(other).cloned().collect() 1319 } 1320 } 1321 1322 impl<T, S1, S2> BitXor<&IndexSet<T, S2>> for &IndexSet<T, S1> 1323 where 1324 T: Eq + Hash + Clone, 1325 S1: BuildHasher + Default, 1326 S2: BuildHasher, 1327 { 1328 type Output = IndexSet<T, S1>; 1329 1330 /// Returns the set symmetric-difference, cloned into a new set. 1331 /// 1332 /// Values from `self` are collected in their original order, followed by 1333 /// values from `other` in their original order. bitxor(self, other: &IndexSet<T, S2>) -> Self::Output1334 fn bitxor(self, other: &IndexSet<T, S2>) -> Self::Output { 1335 self.symmetric_difference(other).cloned().collect() 1336 } 1337 } 1338 1339 impl<T, S1, S2> Sub<&IndexSet<T, S2>> for &IndexSet<T, S1> 1340 where 1341 T: Eq + Hash + Clone, 1342 S1: BuildHasher + Default, 1343 S2: BuildHasher, 1344 { 1345 type Output = IndexSet<T, S1>; 1346 1347 /// Returns the set difference, cloned into a new set. 1348 /// 1349 /// Values are collected in the same order that they appear in `self`. sub(self, other: &IndexSet<T, S2>) -> Self::Output1350 fn sub(self, other: &IndexSet<T, S2>) -> Self::Output { 1351 self.difference(other).cloned().collect() 1352 } 1353 } 1354 1355 #[cfg(test)] 1356 mod tests { 1357 use super::*; 1358 use crate::util::enumerate; 1359 use std::string::String; 1360 1361 #[test] it_works()1362 fn it_works() { 1363 let mut set = IndexSet::new(); 1364 assert_eq!(set.is_empty(), true); 1365 set.insert(1); 1366 set.insert(1); 1367 assert_eq!(set.len(), 1); 1368 assert!(set.get(&1).is_some()); 1369 assert_eq!(set.is_empty(), false); 1370 } 1371 1372 #[test] new()1373 fn new() { 1374 let set = IndexSet::<String>::new(); 1375 println!("{:?}", set); 1376 assert_eq!(set.capacity(), 0); 1377 assert_eq!(set.len(), 0); 1378 assert_eq!(set.is_empty(), true); 1379 } 1380 1381 #[test] insert()1382 fn insert() { 1383 let insert = [0, 4, 2, 12, 8, 7, 11, 5]; 1384 let not_present = [1, 3, 6, 9, 10]; 1385 let mut set = IndexSet::with_capacity(insert.len()); 1386 1387 for (i, &elt) in enumerate(&insert) { 1388 assert_eq!(set.len(), i); 1389 set.insert(elt); 1390 assert_eq!(set.len(), i + 1); 1391 assert_eq!(set.get(&elt), Some(&elt)); 1392 } 1393 println!("{:?}", set); 1394 1395 for &elt in ¬_present { 1396 assert!(set.get(&elt).is_none()); 1397 } 1398 } 1399 1400 #[test] insert_full()1401 fn insert_full() { 1402 let insert = vec![9, 2, 7, 1, 4, 6, 13]; 1403 let present = vec![1, 6, 2]; 1404 let mut set = IndexSet::with_capacity(insert.len()); 1405 1406 for (i, &elt) in enumerate(&insert) { 1407 assert_eq!(set.len(), i); 1408 let (index, success) = set.insert_full(elt); 1409 assert!(success); 1410 assert_eq!(Some(index), set.get_full(&elt).map(|x| x.0)); 1411 assert_eq!(set.len(), i + 1); 1412 } 1413 1414 let len = set.len(); 1415 for &elt in &present { 1416 let (index, success) = set.insert_full(elt); 1417 assert!(!success); 1418 assert_eq!(Some(index), set.get_full(&elt).map(|x| x.0)); 1419 assert_eq!(set.len(), len); 1420 } 1421 } 1422 1423 #[test] insert_2()1424 fn insert_2() { 1425 let mut set = IndexSet::with_capacity(16); 1426 1427 let mut values = vec![]; 1428 values.extend(0..16); 1429 values.extend(128..267); 1430 1431 for &i in &values { 1432 let old_set = set.clone(); 1433 set.insert(i); 1434 for value in old_set.iter() { 1435 if set.get(value).is_none() { 1436 println!("old_set: {:?}", old_set); 1437 println!("set: {:?}", set); 1438 panic!("did not find {} in set", value); 1439 } 1440 } 1441 } 1442 1443 for &i in &values { 1444 assert!(set.get(&i).is_some(), "did not find {}", i); 1445 } 1446 } 1447 1448 #[test] insert_dup()1449 fn insert_dup() { 1450 let mut elements = vec![0, 2, 4, 6, 8]; 1451 let mut set: IndexSet<u8> = elements.drain(..).collect(); 1452 { 1453 let (i, v) = set.get_full(&0).unwrap(); 1454 assert_eq!(set.len(), 5); 1455 assert_eq!(i, 0); 1456 assert_eq!(*v, 0); 1457 } 1458 { 1459 let inserted = set.insert(0); 1460 let (i, v) = set.get_full(&0).unwrap(); 1461 assert_eq!(set.len(), 5); 1462 assert_eq!(inserted, false); 1463 assert_eq!(i, 0); 1464 assert_eq!(*v, 0); 1465 } 1466 } 1467 1468 #[test] insert_order()1469 fn insert_order() { 1470 let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; 1471 let mut set = IndexSet::new(); 1472 1473 for &elt in &insert { 1474 set.insert(elt); 1475 } 1476 1477 assert_eq!(set.iter().count(), set.len()); 1478 assert_eq!(set.iter().count(), insert.len()); 1479 for (a, b) in insert.iter().zip(set.iter()) { 1480 assert_eq!(a, b); 1481 } 1482 for (i, v) in (0..insert.len()).zip(set.iter()) { 1483 assert_eq!(set.get_index(i).unwrap(), v); 1484 } 1485 } 1486 1487 #[test] grow()1488 fn grow() { 1489 let insert = [0, 4, 2, 12, 8, 7, 11]; 1490 let not_present = [1, 3, 6, 9, 10]; 1491 let mut set = IndexSet::with_capacity(insert.len()); 1492 1493 for (i, &elt) in enumerate(&insert) { 1494 assert_eq!(set.len(), i); 1495 set.insert(elt); 1496 assert_eq!(set.len(), i + 1); 1497 assert_eq!(set.get(&elt), Some(&elt)); 1498 } 1499 1500 println!("{:?}", set); 1501 for &elt in &insert { 1502 set.insert(elt * 10); 1503 } 1504 for &elt in &insert { 1505 set.insert(elt * 100); 1506 } 1507 for (i, &elt) in insert.iter().cycle().enumerate().take(100) { 1508 set.insert(elt * 100 + i as i32); 1509 } 1510 println!("{:?}", set); 1511 for &elt in ¬_present { 1512 assert!(set.get(&elt).is_none()); 1513 } 1514 } 1515 1516 #[test] reserve()1517 fn reserve() { 1518 let mut set = IndexSet::<usize>::new(); 1519 assert_eq!(set.capacity(), 0); 1520 set.reserve(100); 1521 let capacity = set.capacity(); 1522 assert!(capacity >= 100); 1523 for i in 0..capacity { 1524 assert_eq!(set.len(), i); 1525 set.insert(i); 1526 assert_eq!(set.len(), i + 1); 1527 assert_eq!(set.capacity(), capacity); 1528 assert_eq!(set.get(&i), Some(&i)); 1529 } 1530 set.insert(capacity); 1531 assert_eq!(set.len(), capacity + 1); 1532 assert!(set.capacity() > capacity); 1533 assert_eq!(set.get(&capacity), Some(&capacity)); 1534 } 1535 1536 #[test] shrink_to_fit()1537 fn shrink_to_fit() { 1538 let mut set = IndexSet::<usize>::new(); 1539 assert_eq!(set.capacity(), 0); 1540 for i in 0..100 { 1541 assert_eq!(set.len(), i); 1542 set.insert(i); 1543 assert_eq!(set.len(), i + 1); 1544 assert!(set.capacity() >= i + 1); 1545 assert_eq!(set.get(&i), Some(&i)); 1546 set.shrink_to_fit(); 1547 assert_eq!(set.len(), i + 1); 1548 assert_eq!(set.capacity(), i + 1); 1549 assert_eq!(set.get(&i), Some(&i)); 1550 } 1551 } 1552 1553 #[test] remove()1554 fn remove() { 1555 let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; 1556 let mut set = IndexSet::new(); 1557 1558 for &elt in &insert { 1559 set.insert(elt); 1560 } 1561 1562 assert_eq!(set.iter().count(), set.len()); 1563 assert_eq!(set.iter().count(), insert.len()); 1564 for (a, b) in insert.iter().zip(set.iter()) { 1565 assert_eq!(a, b); 1566 } 1567 1568 let remove_fail = [99, 77]; 1569 let remove = [4, 12, 8, 7]; 1570 1571 for &value in &remove_fail { 1572 assert!(set.swap_remove_full(&value).is_none()); 1573 } 1574 println!("{:?}", set); 1575 for &value in &remove { 1576 //println!("{:?}", set); 1577 let index = set.get_full(&value).unwrap().0; 1578 assert_eq!(set.swap_remove_full(&value), Some((index, value))); 1579 } 1580 println!("{:?}", set); 1581 1582 for value in &insert { 1583 assert_eq!(set.get(value).is_some(), !remove.contains(value)); 1584 } 1585 assert_eq!(set.len(), insert.len() - remove.len()); 1586 assert_eq!(set.iter().count(), insert.len() - remove.len()); 1587 } 1588 1589 #[test] swap_remove_index()1590 fn swap_remove_index() { 1591 let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23]; 1592 let mut set = IndexSet::new(); 1593 1594 for &elt in &insert { 1595 set.insert(elt); 1596 } 1597 1598 let mut vector = insert.to_vec(); 1599 let remove_sequence = &[3, 3, 10, 4, 5, 4, 3, 0, 1]; 1600 1601 // check that the same swap remove sequence on vec and set 1602 // have the same result. 1603 for &rm in remove_sequence { 1604 let out_vec = vector.swap_remove(rm); 1605 let out_set = set.swap_remove_index(rm).unwrap(); 1606 assert_eq!(out_vec, out_set); 1607 } 1608 assert_eq!(vector.len(), set.len()); 1609 for (a, b) in vector.iter().zip(set.iter()) { 1610 assert_eq!(a, b); 1611 } 1612 } 1613 1614 #[test] partial_eq_and_eq()1615 fn partial_eq_and_eq() { 1616 let mut set_a = IndexSet::new(); 1617 set_a.insert(1); 1618 set_a.insert(2); 1619 let mut set_b = set_a.clone(); 1620 assert_eq!(set_a, set_b); 1621 set_b.swap_remove(&1); 1622 assert_ne!(set_a, set_b); 1623 1624 let set_c: IndexSet<_> = set_b.into_iter().collect(); 1625 assert_ne!(set_a, set_c); 1626 assert_ne!(set_c, set_a); 1627 } 1628 1629 #[test] extend()1630 fn extend() { 1631 let mut set = IndexSet::new(); 1632 set.extend(vec![&1, &2, &3, &4]); 1633 set.extend(vec![5, 6]); 1634 assert_eq!(set.into_iter().collect::<Vec<_>>(), vec![1, 2, 3, 4, 5, 6]); 1635 } 1636 1637 #[test] comparisons()1638 fn comparisons() { 1639 let set_a: IndexSet<_> = (0..3).collect(); 1640 let set_b: IndexSet<_> = (3..6).collect(); 1641 let set_c: IndexSet<_> = (0..6).collect(); 1642 let set_d: IndexSet<_> = (3..9).collect(); 1643 1644 assert!(!set_a.is_disjoint(&set_a)); 1645 assert!(set_a.is_subset(&set_a)); 1646 assert!(set_a.is_superset(&set_a)); 1647 1648 assert!(set_a.is_disjoint(&set_b)); 1649 assert!(set_b.is_disjoint(&set_a)); 1650 assert!(!set_a.is_subset(&set_b)); 1651 assert!(!set_b.is_subset(&set_a)); 1652 assert!(!set_a.is_superset(&set_b)); 1653 assert!(!set_b.is_superset(&set_a)); 1654 1655 assert!(!set_a.is_disjoint(&set_c)); 1656 assert!(!set_c.is_disjoint(&set_a)); 1657 assert!(set_a.is_subset(&set_c)); 1658 assert!(!set_c.is_subset(&set_a)); 1659 assert!(!set_a.is_superset(&set_c)); 1660 assert!(set_c.is_superset(&set_a)); 1661 1662 assert!(!set_c.is_disjoint(&set_d)); 1663 assert!(!set_d.is_disjoint(&set_c)); 1664 assert!(!set_c.is_subset(&set_d)); 1665 assert!(!set_d.is_subset(&set_c)); 1666 assert!(!set_c.is_superset(&set_d)); 1667 assert!(!set_d.is_superset(&set_c)); 1668 } 1669 1670 #[test] iter_comparisons()1671 fn iter_comparisons() { 1672 use std::iter::empty; 1673 1674 fn check<'a, I1, I2>(iter1: I1, iter2: I2) 1675 where 1676 I1: Iterator<Item = &'a i32>, 1677 I2: Iterator<Item = i32>, 1678 { 1679 assert!(iter1.copied().eq(iter2)); 1680 } 1681 1682 let set_a: IndexSet<_> = (0..3).collect(); 1683 let set_b: IndexSet<_> = (3..6).collect(); 1684 let set_c: IndexSet<_> = (0..6).collect(); 1685 let set_d: IndexSet<_> = (3..9).rev().collect(); 1686 1687 check(set_a.difference(&set_a), empty()); 1688 check(set_a.symmetric_difference(&set_a), empty()); 1689 check(set_a.intersection(&set_a), 0..3); 1690 check(set_a.union(&set_a), 0..3); 1691 1692 check(set_a.difference(&set_b), 0..3); 1693 check(set_b.difference(&set_a), 3..6); 1694 check(set_a.symmetric_difference(&set_b), 0..6); 1695 check(set_b.symmetric_difference(&set_a), (3..6).chain(0..3)); 1696 check(set_a.intersection(&set_b), empty()); 1697 check(set_b.intersection(&set_a), empty()); 1698 check(set_a.union(&set_b), 0..6); 1699 check(set_b.union(&set_a), (3..6).chain(0..3)); 1700 1701 check(set_a.difference(&set_c), empty()); 1702 check(set_c.difference(&set_a), 3..6); 1703 check(set_a.symmetric_difference(&set_c), 3..6); 1704 check(set_c.symmetric_difference(&set_a), 3..6); 1705 check(set_a.intersection(&set_c), 0..3); 1706 check(set_c.intersection(&set_a), 0..3); 1707 check(set_a.union(&set_c), 0..6); 1708 check(set_c.union(&set_a), 0..6); 1709 1710 check(set_c.difference(&set_d), 0..3); 1711 check(set_d.difference(&set_c), (6..9).rev()); 1712 check( 1713 set_c.symmetric_difference(&set_d), 1714 (0..3).chain((6..9).rev()), 1715 ); 1716 check(set_d.symmetric_difference(&set_c), (6..9).rev().chain(0..3)); 1717 check(set_c.intersection(&set_d), 3..6); 1718 check(set_d.intersection(&set_c), (3..6).rev()); 1719 check(set_c.union(&set_d), (0..6).chain((6..9).rev())); 1720 check(set_d.union(&set_c), (3..9).rev().chain(0..3)); 1721 } 1722 1723 #[test] ops()1724 fn ops() { 1725 let empty = IndexSet::<i32>::new(); 1726 let set_a: IndexSet<_> = (0..3).collect(); 1727 let set_b: IndexSet<_> = (3..6).collect(); 1728 let set_c: IndexSet<_> = (0..6).collect(); 1729 let set_d: IndexSet<_> = (3..9).rev().collect(); 1730 1731 #[allow(clippy::eq_op)] 1732 { 1733 assert_eq!(&set_a & &set_a, set_a); 1734 assert_eq!(&set_a | &set_a, set_a); 1735 assert_eq!(&set_a ^ &set_a, empty); 1736 assert_eq!(&set_a - &set_a, empty); 1737 } 1738 1739 assert_eq!(&set_a & &set_b, empty); 1740 assert_eq!(&set_b & &set_a, empty); 1741 assert_eq!(&set_a | &set_b, set_c); 1742 assert_eq!(&set_b | &set_a, set_c); 1743 assert_eq!(&set_a ^ &set_b, set_c); 1744 assert_eq!(&set_b ^ &set_a, set_c); 1745 assert_eq!(&set_a - &set_b, set_a); 1746 assert_eq!(&set_b - &set_a, set_b); 1747 1748 assert_eq!(&set_a & &set_c, set_a); 1749 assert_eq!(&set_c & &set_a, set_a); 1750 assert_eq!(&set_a | &set_c, set_c); 1751 assert_eq!(&set_c | &set_a, set_c); 1752 assert_eq!(&set_a ^ &set_c, set_b); 1753 assert_eq!(&set_c ^ &set_a, set_b); 1754 assert_eq!(&set_a - &set_c, empty); 1755 assert_eq!(&set_c - &set_a, set_b); 1756 1757 assert_eq!(&set_c & &set_d, set_b); 1758 assert_eq!(&set_d & &set_c, set_b); 1759 assert_eq!(&set_c | &set_d, &set_a | &set_d); 1760 assert_eq!(&set_d | &set_c, &set_a | &set_d); 1761 assert_eq!(&set_c ^ &set_d, &set_a | &(&set_d - &set_b)); 1762 assert_eq!(&set_d ^ &set_c, &set_a | &(&set_d - &set_b)); 1763 assert_eq!(&set_c - &set_d, set_a); 1764 assert_eq!(&set_d - &set_c, &set_d - &set_b); 1765 } 1766 1767 #[test] 1768 #[cfg(all(has_std, rustc_1_51))] from_array()1769 fn from_array() { 1770 let set1 = IndexSet::from([1, 2, 3, 4]); 1771 let set2: IndexSet<_> = [1, 2, 3, 4].into(); 1772 1773 assert_eq!(set1, set2); 1774 } 1775 } 1776