1//! A hash set implemented using `IndexMap`
2
3mod iter;
4mod slice;
5
6#[cfg(test)]
7mod tests;
8
9pub use self::iter::{Difference, Drain, Intersection, IntoIter, Iter, SymmetricDifference, Union};
10pub use self::slice::Slice;
11
12#[cfg(feature = "rayon")]
13pub use crate::rayon::set as rayon;
14use crate::TryReserveError;
15
16#[cfg(feature = "std")]
17use std::collections::hash_map::RandomState;
18
19use crate::util::try_simplify_range;
20use alloc::boxed::Box;
21use alloc::vec::Vec;
22use core::cmp::Ordering;
23use core::fmt;
24use core::hash::{BuildHasher, Hash};
25use core::ops::{BitAnd, BitOr, BitXor, Index, RangeBounds, Sub};
26
27use super::{Entries, Equivalent, IndexMap};
28
29type Bucket<T> = super::Bucket<T, ()>;
30
31/// A hash set where the iteration order of the values is independent of their
32/// hash values.
33///
34/// The interface is closely compatible with the standard `HashSet`, but also
35/// has additional features.
36///
37/// # Order
38///
39/// The values have a consistent order that is determined by the sequence of
40/// insertion and removal calls on the set. The order does not depend on the
41/// values or the hash function at all. Note that insertion order and value
42/// are not affected if a re-insertion is attempted once an element is
43/// already present.
44///
45/// All iterators traverse the set *in order*. Set operation iterators like
46/// `union` produce a concatenated order, as do their matching "bitwise"
47/// operators. See their documentation for specifics.
48///
49/// The insertion order is preserved, with **notable exceptions** like the
50/// `.remove()` or `.swap_remove()` methods. Methods such as `.sort_by()` of
51/// course result in a new order, depending on the sorting order.
52///
53/// # Indices
54///
55/// The values are indexed in a compact range without holes in the range
56/// `0..self.len()`. For example, the method `.get_full` looks up the index for
57/// a value, and the method `.get_index` looks up the value by index.
58///
59/// # Examples
60///
61/// ```
62/// use indexmap::IndexSet;
63///
64/// // Collects which letters appear in a sentence.
65/// let letters: IndexSet<_> = "a short treatise on fungi".chars().collect();
66///
67/// assert!(letters.contains(&'s'));
68/// assert!(letters.contains(&'t'));
69/// assert!(letters.contains(&'u'));
70/// assert!(!letters.contains(&'y'));
71/// ```
72#[cfg(feature = "std")]
73pub struct IndexSet<T, S = RandomState> {
74 pub(crate) map: IndexMap<T, (), S>,
75}
76#[cfg(not(feature = "std"))]
77pub struct IndexSet<T, S> {
78 pub(crate) map: IndexMap<T, (), S>,
79}
80
81impl<T, S> Clone for IndexSet<T, S>
82where
83 T: Clone,
84 S: Clone,
85{
86 fn clone(&self) -> Self {
87 IndexSet {
88 map: self.map.clone(),
89 }
90 }
91
92 fn clone_from(&mut self, other: &Self) {
93 self.map.clone_from(&other.map);
94 }
95}
96
97impl<T, S> Entries for IndexSet<T, S> {
98 type Entry = Bucket<T>;
99
100 #[inline]
101 fn into_entries(self) -> Vec<Self::Entry> {
102 self.map.into_entries()
103 }
104
105 #[inline]
106 fn as_entries(&self) -> &[Self::Entry] {
107 self.map.as_entries()
108 }
109
110 #[inline]
111 fn as_entries_mut(&mut self) -> &mut [Self::Entry] {
112 self.map.as_entries_mut()
113 }
114
115 fn with_entries<F>(&mut self, f: F)
116 where
117 F: FnOnce(&mut [Self::Entry]),
118 {
119 self.map.with_entries(f);
120 }
121}
122
123impl<T, S> fmt::Debug for IndexSet<T, S>
124where
125 T: fmt::Debug,
126{
127 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
128 if cfg!(not(feature = "test_debug")) {
129 f.debug_set().entries(self.iter()).finish()
130 } else {
131 // Let the inner `IndexMap` print all of its details
132 f.debug_struct("IndexSet").field(name:"map", &self.map).finish()
133 }
134 }
135}
136
137#[cfg(feature = "std")]
138#[cfg_attr(docsrs, doc(cfg(feature = "std")))]
139impl<T> IndexSet<T> {
140 /// Create a new set. (Does not allocate.)
141 pub fn new() -> Self {
142 IndexSet {
143 map: IndexMap::new(),
144 }
145 }
146
147 /// Create a new set with capacity for `n` elements.
148 /// (Does not allocate if `n` is zero.)
149 ///
150 /// Computes in **O(n)** time.
151 pub fn with_capacity(n: usize) -> Self {
152 IndexSet {
153 map: IndexMap::with_capacity(n),
154 }
155 }
156}
157
158impl<T, S> IndexSet<T, S> {
159 /// Create a new set with capacity for `n` elements.
160 /// (Does not allocate if `n` is zero.)
161 ///
162 /// Computes in **O(n)** time.
163 pub fn with_capacity_and_hasher(n: usize, hash_builder: S) -> Self {
164 IndexSet {
165 map: IndexMap::with_capacity_and_hasher(n, hash_builder),
166 }
167 }
168
169 /// Create a new set with `hash_builder`.
170 ///
171 /// This function is `const`, so it
172 /// can be called in `static` contexts.
173 pub const fn with_hasher(hash_builder: S) -> Self {
174 IndexSet {
175 map: IndexMap::with_hasher(hash_builder),
176 }
177 }
178
179 /// Return the number of elements the set can hold without reallocating.
180 ///
181 /// This number is a lower bound; the set might be able to hold more,
182 /// but is guaranteed to be able to hold at least this many.
183 ///
184 /// Computes in **O(1)** time.
185 pub fn capacity(&self) -> usize {
186 self.map.capacity()
187 }
188
189 /// Return a reference to the set's `BuildHasher`.
190 pub fn hasher(&self) -> &S {
191 self.map.hasher()
192 }
193
194 /// Return the number of elements in the set.
195 ///
196 /// Computes in **O(1)** time.
197 pub fn len(&self) -> usize {
198 self.map.len()
199 }
200
201 /// Returns true if the set contains no elements.
202 ///
203 /// Computes in **O(1)** time.
204 pub fn is_empty(&self) -> bool {
205 self.map.is_empty()
206 }
207
208 /// Return an iterator over the values of the set, in their order
209 pub fn iter(&self) -> Iter<'_, T> {
210 Iter::new(self.as_entries())
211 }
212
213 /// Remove all elements in the set, while preserving its capacity.
214 ///
215 /// Computes in **O(n)** time.
216 pub fn clear(&mut self) {
217 self.map.clear();
218 }
219
220 /// Shortens the set, keeping the first `len` elements and dropping the rest.
221 ///
222 /// If `len` is greater than the set's current length, this has no effect.
223 pub fn truncate(&mut self, len: usize) {
224 self.map.truncate(len);
225 }
226
227 /// Clears the `IndexSet` in the given index range, returning those values
228 /// as a drain iterator.
229 ///
230 /// The range may be any type that implements `RangeBounds<usize>`,
231 /// including all of the `std::ops::Range*` types, or even a tuple pair of
232 /// `Bound` start and end values. To drain the set entirely, use `RangeFull`
233 /// like `set.drain(..)`.
234 ///
235 /// This shifts down all entries following the drained range to fill the
236 /// gap, and keeps the allocated memory for reuse.
237 ///
238 /// ***Panics*** if the starting point is greater than the end point or if
239 /// the end point is greater than the length of the set.
240 pub fn drain<R>(&mut self, range: R) -> Drain<'_, T>
241 where
242 R: RangeBounds<usize>,
243 {
244 Drain::new(self.map.core.drain(range))
245 }
246
247 /// Splits the collection into two at the given index.
248 ///
249 /// Returns a newly allocated set containing the elements in the range
250 /// `[at, len)`. After the call, the original set will be left containing
251 /// the elements `[0, at)` with its previous capacity unchanged.
252 ///
253 /// ***Panics*** if `at > len`.
254 pub fn split_off(&mut self, at: usize) -> Self
255 where
256 S: Clone,
257 {
258 Self {
259 map: self.map.split_off(at),
260 }
261 }
262}
263
264impl<T, S> IndexSet<T, S>
265where
266 T: Hash + Eq,
267 S: BuildHasher,
268{
269 /// Reserve capacity for `additional` more values.
270 ///
271 /// Computes in **O(n)** time.
272 pub fn reserve(&mut self, additional: usize) {
273 self.map.reserve(additional);
274 }
275
276 /// Reserve capacity for `additional` more values, without over-allocating.
277 ///
278 /// Unlike `reserve`, this does not deliberately over-allocate the entry capacity to avoid
279 /// frequent re-allocations. However, the underlying data structures may still have internal
280 /// capacity requirements, and the allocator itself may give more space than requested, so this
281 /// cannot be relied upon to be precisely minimal.
282 ///
283 /// Computes in **O(n)** time.
284 pub fn reserve_exact(&mut self, additional: usize) {
285 self.map.reserve_exact(additional);
286 }
287
288 /// Try to reserve capacity for `additional` more values.
289 ///
290 /// Computes in **O(n)** time.
291 pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
292 self.map.try_reserve(additional)
293 }
294
295 /// Try to reserve capacity for `additional` more values, without over-allocating.
296 ///
297 /// Unlike `try_reserve`, this does not deliberately over-allocate the entry capacity to avoid
298 /// frequent re-allocations. However, the underlying data structures may still have internal
299 /// capacity requirements, and the allocator itself may give more space than requested, so this
300 /// cannot be relied upon to be precisely minimal.
301 ///
302 /// Computes in **O(n)** time.
303 pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> {
304 self.map.try_reserve_exact(additional)
305 }
306
307 /// Shrink the capacity of the set as much as possible.
308 ///
309 /// Computes in **O(n)** time.
310 pub fn shrink_to_fit(&mut self) {
311 self.map.shrink_to_fit();
312 }
313
314 /// Shrink the capacity of the set with a lower limit.
315 ///
316 /// Computes in **O(n)** time.
317 pub fn shrink_to(&mut self, min_capacity: usize) {
318 self.map.shrink_to(min_capacity);
319 }
320
321 /// Insert the value into the set.
322 ///
323 /// If an equivalent item already exists in the set, it returns
324 /// `false` leaving the original value in the set and without
325 /// altering its insertion order. Otherwise, it inserts the new
326 /// item and returns `true`.
327 ///
328 /// Computes in **O(1)** time (amortized average).
329 pub fn insert(&mut self, value: T) -> bool {
330 self.map.insert(value, ()).is_none()
331 }
332
333 /// Insert the value into the set, and get its index.
334 ///
335 /// If an equivalent item already exists in the set, it returns
336 /// the index of the existing item and `false`, leaving the
337 /// original value in the set and without altering its insertion
338 /// order. Otherwise, it inserts the new item and returns the index
339 /// of the inserted item and `true`.
340 ///
341 /// Computes in **O(1)** time (amortized average).
342 pub fn insert_full(&mut self, value: T) -> (usize, bool) {
343 let (index, existing) = self.map.insert_full(value, ());
344 (index, existing.is_none())
345 }
346
347 /// Return an iterator over the values that are in `self` but not `other`.
348 ///
349 /// Values are produced in the same order that they appear in `self`.
350 pub fn difference<'a, S2>(&'a self, other: &'a IndexSet<T, S2>) -> Difference<'a, T, S2>
351 where
352 S2: BuildHasher,
353 {
354 Difference::new(self, other)
355 }
356
357 /// Return an iterator over the values that are in `self` or `other`,
358 /// but not in both.
359 ///
360 /// Values from `self` are produced in their original order, followed by
361 /// values from `other` in their original order.
362 pub fn symmetric_difference<'a, S2>(
363 &'a self,
364 other: &'a IndexSet<T, S2>,
365 ) -> SymmetricDifference<'a, T, S, S2>
366 where
367 S2: BuildHasher,
368 {
369 SymmetricDifference::new(self, other)
370 }
371
372 /// Return an iterator over the values that are in both `self` and `other`.
373 ///
374 /// Values are produced in the same order that they appear in `self`.
375 pub fn intersection<'a, S2>(&'a self, other: &'a IndexSet<T, S2>) -> Intersection<'a, T, S2>
376 where
377 S2: BuildHasher,
378 {
379 Intersection::new(self, other)
380 }
381
382 /// Return an iterator over all values that are in `self` or `other`.
383 ///
384 /// Values from `self` are produced in their original order, followed by
385 /// values that are unique to `other` in their original order.
386 pub fn union<'a, S2>(&'a self, other: &'a IndexSet<T, S2>) -> Union<'a, T, S>
387 where
388 S2: BuildHasher,
389 {
390 Union::new(self, other)
391 }
392
393 /// Return `true` if an equivalent to `value` exists in the set.
394 ///
395 /// Computes in **O(1)** time (average).
396 pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool
397 where
398 Q: Hash + Equivalent<T>,
399 {
400 self.map.contains_key(value)
401 }
402
403 /// Return a reference to the value stored in the set, if it is present,
404 /// else `None`.
405 ///
406 /// Computes in **O(1)** time (average).
407 pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T>
408 where
409 Q: Hash + Equivalent<T>,
410 {
411 self.map.get_key_value(value).map(|(x, &())| x)
412 }
413
414 /// Return item index and value
415 pub fn get_full<Q: ?Sized>(&self, value: &Q) -> Option<(usize, &T)>
416 where
417 Q: Hash + Equivalent<T>,
418 {
419 self.map.get_full(value).map(|(i, x, &())| (i, x))
420 }
421
422 /// Return item index, if it exists in the set
423 pub fn get_index_of<Q: ?Sized>(&self, value: &Q) -> Option<usize>
424 where
425 Q: Hash + Equivalent<T>,
426 {
427 self.map.get_index_of(value)
428 }
429
430 /// Adds a value to the set, replacing the existing value, if any, that is
431 /// equal to the given one, without altering its insertion order. Returns
432 /// the replaced value.
433 ///
434 /// Computes in **O(1)** time (average).
435 pub fn replace(&mut self, value: T) -> Option<T> {
436 self.replace_full(value).1
437 }
438
439 /// Adds a value to the set, replacing the existing value, if any, that is
440 /// equal to the given one, without altering its insertion order. Returns
441 /// the index of the item and its replaced value.
442 ///
443 /// Computes in **O(1)** time (average).
444 pub fn replace_full(&mut self, value: T) -> (usize, Option<T>) {
445 use super::map::Entry::*;
446
447 match self.map.entry(value) {
448 Vacant(e) => {
449 let index = e.index();
450 e.insert(());
451 (index, None)
452 }
453 Occupied(e) => (e.index(), Some(e.replace_key())),
454 }
455 }
456
457 /// Remove the value from the set, and return `true` if it was present.
458 ///
459 /// **NOTE:** This is equivalent to `.swap_remove(value)`, if you want
460 /// to preserve the order of the values in the set, use `.shift_remove(value)`.
461 ///
462 /// Computes in **O(1)** time (average).
463 pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool
464 where
465 Q: Hash + Equivalent<T>,
466 {
467 self.swap_remove(value)
468 }
469
470 /// Remove the value from the set, and return `true` if it was present.
471 ///
472 /// Like `Vec::swap_remove`, the value is removed by swapping it with the
473 /// last element of the set and popping it off. **This perturbs
474 /// the position of what used to be the last element!**
475 ///
476 /// Return `false` if `value` was not in the set.
477 ///
478 /// Computes in **O(1)** time (average).
479 pub fn swap_remove<Q: ?Sized>(&mut self, value: &Q) -> bool
480 where
481 Q: Hash + Equivalent<T>,
482 {
483 self.map.swap_remove(value).is_some()
484 }
485
486 /// Remove the value from the set, and return `true` if it was present.
487 ///
488 /// Like `Vec::remove`, the value is removed by shifting all of the
489 /// elements that follow it, preserving their relative order.
490 /// **This perturbs the index of all of those elements!**
491 ///
492 /// Return `false` if `value` was not in the set.
493 ///
494 /// Computes in **O(n)** time (average).
495 pub fn shift_remove<Q: ?Sized>(&mut self, value: &Q) -> bool
496 where
497 Q: Hash + Equivalent<T>,
498 {
499 self.map.shift_remove(value).is_some()
500 }
501
502 /// Removes and returns the value in the set, if any, that is equal to the
503 /// given one.
504 ///
505 /// **NOTE:** This is equivalent to `.swap_take(value)`, if you need to
506 /// preserve the order of the values in the set, use `.shift_take(value)`
507 /// instead.
508 ///
509 /// Computes in **O(1)** time (average).
510 pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T>
511 where
512 Q: Hash + Equivalent<T>,
513 {
514 self.swap_take(value)
515 }
516
517 /// Removes and returns the value in the set, if any, that is equal to the
518 /// given one.
519 ///
520 /// Like `Vec::swap_remove`, the value is removed by swapping it with the
521 /// last element of the set and popping it off. **This perturbs
522 /// the position of what used to be the last element!**
523 ///
524 /// Return `None` if `value` was not in the set.
525 ///
526 /// Computes in **O(1)** time (average).
527 pub fn swap_take<Q: ?Sized>(&mut self, value: &Q) -> Option<T>
528 where
529 Q: Hash + Equivalent<T>,
530 {
531 self.map.swap_remove_entry(value).map(|(x, ())| x)
532 }
533
534 /// Removes and returns the value in the set, if any, that is equal to the
535 /// given one.
536 ///
537 /// Like `Vec::remove`, the value is removed by shifting all of the
538 /// elements that follow it, preserving their relative order.
539 /// **This perturbs the index of all of those elements!**
540 ///
541 /// Return `None` if `value` was not in the set.
542 ///
543 /// Computes in **O(n)** time (average).
544 pub fn shift_take<Q: ?Sized>(&mut self, value: &Q) -> Option<T>
545 where
546 Q: Hash + Equivalent<T>,
547 {
548 self.map.shift_remove_entry(value).map(|(x, ())| x)
549 }
550
551 /// Remove the value from the set return it and the index it had.
552 ///
553 /// Like `Vec::swap_remove`, the value is removed by swapping it with the
554 /// last element of the set and popping it off. **This perturbs
555 /// the position of what used to be the last element!**
556 ///
557 /// Return `None` if `value` was not in the set.
558 pub fn swap_remove_full<Q: ?Sized>(&mut self, value: &Q) -> Option<(usize, T)>
559 where
560 Q: Hash + Equivalent<T>,
561 {
562 self.map.swap_remove_full(value).map(|(i, x, ())| (i, x))
563 }
564
565 /// Remove the value from the set return it and the index it had.
566 ///
567 /// Like `Vec::remove`, the value is removed by shifting all of the
568 /// elements that follow it, preserving their relative order.
569 /// **This perturbs the index of all of those elements!**
570 ///
571 /// Return `None` if `value` was not in the set.
572 pub fn shift_remove_full<Q: ?Sized>(&mut self, value: &Q) -> Option<(usize, T)>
573 where
574 Q: Hash + Equivalent<T>,
575 {
576 self.map.shift_remove_full(value).map(|(i, x, ())| (i, x))
577 }
578
579 /// Remove the last value
580 ///
581 /// This preserves the order of the remaining elements.
582 ///
583 /// Computes in **O(1)** time (average).
584 pub fn pop(&mut self) -> Option<T> {
585 self.map.pop().map(|(x, ())| x)
586 }
587
588 /// Scan through each value in the set and keep those where the
589 /// closure `keep` returns `true`.
590 ///
591 /// The elements are visited in order, and remaining elements keep their
592 /// order.
593 ///
594 /// Computes in **O(n)** time (average).
595 pub fn retain<F>(&mut self, mut keep: F)
596 where
597 F: FnMut(&T) -> bool,
598 {
599 self.map.retain(move |x, &mut ()| keep(x))
600 }
601
602 /// Sort the set’s values by their default ordering.
603 ///
604 /// See [`sort_by`](Self::sort_by) for details.
605 pub fn sort(&mut self)
606 where
607 T: Ord,
608 {
609 self.map.sort_keys()
610 }
611
612 /// Sort the set’s values in place using the comparison function `cmp`.
613 ///
614 /// Computes in **O(n log n)** time and **O(n)** space. The sort is stable.
615 pub fn sort_by<F>(&mut self, mut cmp: F)
616 where
617 F: FnMut(&T, &T) -> Ordering,
618 {
619 self.map.sort_by(move |a, _, b, _| cmp(a, b));
620 }
621
622 /// Sort the values of the set and return a by-value iterator of
623 /// the values with the result.
624 ///
625 /// The sort is stable.
626 pub fn sorted_by<F>(self, mut cmp: F) -> IntoIter<T>
627 where
628 F: FnMut(&T, &T) -> Ordering,
629 {
630 let mut entries = self.into_entries();
631 entries.sort_by(move |a, b| cmp(&a.key, &b.key));
632 IntoIter::new(entries)
633 }
634
635 /// Sort the set's values by their default ordering.
636 ///
637 /// See [`sort_unstable_by`](Self::sort_unstable_by) for details.
638 pub fn sort_unstable(&mut self)
639 where
640 T: Ord,
641 {
642 self.map.sort_unstable_keys()
643 }
644
645 /// Sort the set's values in place using the comparison function `cmp`.
646 ///
647 /// Computes in **O(n log n)** time. The sort is unstable.
648 pub fn sort_unstable_by<F>(&mut self, mut cmp: F)
649 where
650 F: FnMut(&T, &T) -> Ordering,
651 {
652 self.map.sort_unstable_by(move |a, _, b, _| cmp(a, b))
653 }
654
655 /// Sort the values of the set and return a by-value iterator of
656 /// the values with the result.
657 pub fn sorted_unstable_by<F>(self, mut cmp: F) -> IntoIter<T>
658 where
659 F: FnMut(&T, &T) -> Ordering,
660 {
661 let mut entries = self.into_entries();
662 entries.sort_unstable_by(move |a, b| cmp(&a.key, &b.key));
663 IntoIter::new(entries)
664 }
665
666 /// Sort the set’s values in place using a key extraction function.
667 ///
668 /// During sorting, the function is called at most once per entry, by using temporary storage
669 /// to remember the results of its evaluation. The order of calls to the function is
670 /// unspecified and may change between versions of `indexmap` or the standard library.
671 ///
672 /// Computes in **O(m n + n log n + c)** time () and **O(n)** space, where the function is
673 /// **O(m)**, *n* is the length of the map, and *c* the capacity. The sort is stable.
674 pub fn sort_by_cached_key<K, F>(&mut self, mut sort_key: F)
675 where
676 K: Ord,
677 F: FnMut(&T) -> K,
678 {
679 self.with_entries(move |entries| {
680 entries.sort_by_cached_key(move |a| sort_key(&a.key));
681 });
682 }
683
684 /// Reverses the order of the set’s values in place.
685 ///
686 /// Computes in **O(n)** time and **O(1)** space.
687 pub fn reverse(&mut self) {
688 self.map.reverse()
689 }
690}
691
692impl<T, S> IndexSet<T, S> {
693 /// Returns a slice of all the values in the set.
694 ///
695 /// Computes in **O(1)** time.
696 pub fn as_slice(&self) -> &Slice<T> {
697 Slice::from_slice(self.as_entries())
698 }
699
700 /// Converts into a boxed slice of all the values in the set.
701 ///
702 /// Note that this will drop the inner hash table and any excess capacity.
703 pub fn into_boxed_slice(self) -> Box<Slice<T>> {
704 Slice::from_boxed(self.into_entries().into_boxed_slice())
705 }
706
707 /// Get a value by index
708 ///
709 /// Valid indices are *0 <= index < self.len()*
710 ///
711 /// Computes in **O(1)** time.
712 pub fn get_index(&self, index: usize) -> Option<&T> {
713 self.as_entries().get(index).map(Bucket::key_ref)
714 }
715
716 /// Returns a slice of values in the given range of indices.
717 ///
718 /// Valid indices are *0 <= index < self.len()*
719 ///
720 /// Computes in **O(1)** time.
721 pub fn get_range<R: RangeBounds<usize>>(&self, range: R) -> Option<&Slice<T>> {
722 let entries = self.as_entries();
723 let range = try_simplify_range(range, entries.len())?;
724 entries.get(range).map(Slice::from_slice)
725 }
726
727 /// Get the first value
728 ///
729 /// Computes in **O(1)** time.
730 pub fn first(&self) -> Option<&T> {
731 self.as_entries().first().map(Bucket::key_ref)
732 }
733
734 /// Get the last value
735 ///
736 /// Computes in **O(1)** time.
737 pub fn last(&self) -> Option<&T> {
738 self.as_entries().last().map(Bucket::key_ref)
739 }
740
741 /// Remove the value by index
742 ///
743 /// Valid indices are *0 <= index < self.len()*
744 ///
745 /// Like `Vec::swap_remove`, the value is removed by swapping it with the
746 /// last element of the set and popping it off. **This perturbs
747 /// the position of what used to be the last element!**
748 ///
749 /// Computes in **O(1)** time (average).
750 pub fn swap_remove_index(&mut self, index: usize) -> Option<T> {
751 self.map.swap_remove_index(index).map(|(x, ())| x)
752 }
753
754 /// Remove the value by index
755 ///
756 /// Valid indices are *0 <= index < self.len()*
757 ///
758 /// Like `Vec::remove`, the value is removed by shifting all of the
759 /// elements that follow it, preserving their relative order.
760 /// **This perturbs the index of all of those elements!**
761 ///
762 /// Computes in **O(n)** time (average).
763 pub fn shift_remove_index(&mut self, index: usize) -> Option<T> {
764 self.map.shift_remove_index(index).map(|(x, ())| x)
765 }
766
767 /// Moves the position of a value from one index to another
768 /// by shifting all other values in-between.
769 ///
770 /// * If `from < to`, the other values will shift down while the targeted value moves up.
771 /// * If `from > to`, the other values will shift up while the targeted value moves down.
772 ///
773 /// ***Panics*** if `from` or `to` are out of bounds.
774 ///
775 /// Computes in **O(n)** time (average).
776 pub fn move_index(&mut self, from: usize, to: usize) {
777 self.map.move_index(from, to)
778 }
779
780 /// Swaps the position of two values in the set.
781 ///
782 /// ***Panics*** if `a` or `b` are out of bounds.
783 pub fn swap_indices(&mut self, a: usize, b: usize) {
784 self.map.swap_indices(a, b)
785 }
786}
787
788/// Access `IndexSet` values at indexed positions.
789///
790/// # Examples
791///
792/// ```
793/// use indexmap::IndexSet;
794///
795/// let mut set = IndexSet::new();
796/// for word in "Lorem ipsum dolor sit amet".split_whitespace() {
797/// set.insert(word.to_string());
798/// }
799/// assert_eq!(set[0], "Lorem");
800/// assert_eq!(set[1], "ipsum");
801/// set.reverse();
802/// assert_eq!(set[0], "amet");
803/// assert_eq!(set[1], "sit");
804/// set.sort();
805/// assert_eq!(set[0], "Lorem");
806/// assert_eq!(set[1], "amet");
807/// ```
808///
809/// ```should_panic
810/// use indexmap::IndexSet;
811///
812/// let mut set = IndexSet::new();
813/// set.insert("foo");
814/// println!("{:?}", set[10]); // panics!
815/// ```
816impl<T, S> Index<usize> for IndexSet<T, S> {
817 type Output = T;
818
819 /// Returns a reference to the value at the supplied `index`.
820 ///
821 /// ***Panics*** if `index` is out of bounds.
822 fn index(&self, index: usize) -> &T {
823 self.get_index(index)
824 .expect(msg:"IndexSet: index out of bounds")
825 }
826}
827
828impl<T, S> FromIterator<T> for IndexSet<T, S>
829where
830 T: Hash + Eq,
831 S: BuildHasher + Default,
832{
833 fn from_iter<I: IntoIterator<Item = T>>(iterable: I) -> Self {
834 let iter: impl Iterator = iterable.into_iter().map(|x: T| (x, ()));
835 IndexSet {
836 map: IndexMap::from_iter(iter),
837 }
838 }
839}
840
841#[cfg(feature = "std")]
842#[cfg_attr(docsrs, doc(cfg(feature = "std")))]
843impl<T, const N: usize> From<[T; N]> for IndexSet<T, RandomState>
844where
845 T: Eq + Hash,
846{
847 /// # Examples
848 ///
849 /// ```
850 /// use indexmap::IndexSet;
851 ///
852 /// let set1 = IndexSet::from([1, 2, 3, 4]);
853 /// let set2: IndexSet<_> = [1, 2, 3, 4].into();
854 /// assert_eq!(set1, set2);
855 /// ```
856 fn from(arr: [T; N]) -> Self {
857 Self::from_iter(arr)
858 }
859}
860
861impl<T, S> Extend<T> for IndexSet<T, S>
862where
863 T: Hash + Eq,
864 S: BuildHasher,
865{
866 fn extend<I: IntoIterator<Item = T>>(&mut self, iterable: I) {
867 let iter: impl Iterator = iterable.into_iter().map(|x: T| (x, ()));
868 self.map.extend(iter);
869 }
870}
871
872impl<'a, T, S> Extend<&'a T> for IndexSet<T, S>
873where
874 T: Hash + Eq + Copy + 'a,
875 S: BuildHasher,
876{
877 fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iterable: I) {
878 let iter: impl Iterator = iterable.into_iter().copied();
879 self.extend(iter);
880 }
881}
882
883impl<T, S> Default for IndexSet<T, S>
884where
885 S: Default,
886{
887 /// Return an empty `IndexSet`
888 fn default() -> Self {
889 IndexSet {
890 map: IndexMap::default(),
891 }
892 }
893}
894
895impl<T, S1, S2> PartialEq<IndexSet<T, S2>> for IndexSet<T, S1>
896where
897 T: Hash + Eq,
898 S1: BuildHasher,
899 S2: BuildHasher,
900{
901 fn eq(&self, other: &IndexSet<T, S2>) -> bool {
902 self.len() == other.len() && self.is_subset(other)
903 }
904}
905
906impl<T, S> Eq for IndexSet<T, S>
907where
908 T: Eq + Hash,
909 S: BuildHasher,
910{
911}
912
913impl<T, S> IndexSet<T, S>
914where
915 T: Eq + Hash,
916 S: BuildHasher,
917{
918 /// Returns `true` if `self` has no elements in common with `other`.
919 pub fn is_disjoint<S2>(&self, other: &IndexSet<T, S2>) -> bool
920 where
921 S2: BuildHasher,
922 {
923 if self.len() <= other.len() {
924 self.iter().all(move |value| !other.contains(value))
925 } else {
926 other.iter().all(move |value| !self.contains(value))
927 }
928 }
929
930 /// Returns `true` if all elements of `self` are contained in `other`.
931 pub fn is_subset<S2>(&self, other: &IndexSet<T, S2>) -> bool
932 where
933 S2: BuildHasher,
934 {
935 self.len() <= other.len() && self.iter().all(move |value| other.contains(value))
936 }
937
938 /// Returns `true` if all elements of `other` are contained in `self`.
939 pub fn is_superset<S2>(&self, other: &IndexSet<T, S2>) -> bool
940 where
941 S2: BuildHasher,
942 {
943 other.is_subset(self)
944 }
945}
946
947impl<T, S1, S2> BitAnd<&IndexSet<T, S2>> for &IndexSet<T, S1>
948where
949 T: Eq + Hash + Clone,
950 S1: BuildHasher + Default,
951 S2: BuildHasher,
952{
953 type Output = IndexSet<T, S1>;
954
955 /// Returns the set intersection, cloned into a new set.
956 ///
957 /// Values are collected in the same order that they appear in `self`.
958 fn bitand(self, other: &IndexSet<T, S2>) -> Self::Output {
959 self.intersection(other).cloned().collect()
960 }
961}
962
963impl<T, S1, S2> BitOr<&IndexSet<T, S2>> for &IndexSet<T, S1>
964where
965 T: Eq + Hash + Clone,
966 S1: BuildHasher + Default,
967 S2: BuildHasher,
968{
969 type Output = IndexSet<T, S1>;
970
971 /// Returns the set union, cloned into a new set.
972 ///
973 /// Values from `self` are collected in their original order, followed by
974 /// values that are unique to `other` in their original order.
975 fn bitor(self, other: &IndexSet<T, S2>) -> Self::Output {
976 self.union(other).cloned().collect()
977 }
978}
979
980impl<T, S1, S2> BitXor<&IndexSet<T, S2>> for &IndexSet<T, S1>
981where
982 T: Eq + Hash + Clone,
983 S1: BuildHasher + Default,
984 S2: BuildHasher,
985{
986 type Output = IndexSet<T, S1>;
987
988 /// Returns the set symmetric-difference, cloned into a new set.
989 ///
990 /// Values from `self` are collected in their original order, followed by
991 /// values from `other` in their original order.
992 fn bitxor(self, other: &IndexSet<T, S2>) -> Self::Output {
993 self.symmetric_difference(other).cloned().collect()
994 }
995}
996
997impl<T, S1, S2> Sub<&IndexSet<T, S2>> for &IndexSet<T, S1>
998where
999 T: Eq + Hash + Clone,
1000 S1: BuildHasher + Default,
1001 S2: BuildHasher,
1002{
1003 type Output = IndexSet<T, S1>;
1004
1005 /// Returns the set difference, cloned into a new set.
1006 ///
1007 /// Values are collected in the same order that they appear in `self`.
1008 fn sub(self, other: &IndexSet<T, S2>) -> Self::Output {
1009 self.difference(other).cloned().collect()
1010 }
1011}
1012