1//! A linked hash set implementation based on the `linked_hash_map` crate.
2//! See [`LinkedHashSet`](struct.LinkedHashSet.html).
3//!
4//! # Examples
5//!
6//! ```
7//! let mut set = linked_hash_set::LinkedHashSet::new();
8//! assert!(set.insert(234));
9//! assert!(set.insert(123));
10//! assert!(set.insert(345));
11//! assert!(!set.insert(123)); // Also see `insert_if_absent` which won't change order
12//!
13//! assert_eq!(set.into_iter().collect::<Vec<_>>(), vec![234, 345, 123]);
14//! ```
15#[cfg(feature = "serde")]
16pub mod serde;
17
18use linked_hash_map as map;
19use linked_hash_map::{Keys, LinkedHashMap};
20use std::{
21 borrow::Borrow,
22 collections::hash_map::RandomState,
23 fmt,
24 hash::{BuildHasher, Hash, Hasher},
25 iter::{Chain, FromIterator},
26 ops::{BitAnd, BitOr, BitXor, Sub},
27};
28
29// Note: This implementation is adapted from std `HashSet` implementation ~2017-10
30// parts relying on std `HashMap` functionality that is not present in `LinkedHashMap` or
31// relying on private access to map internals have been removed.
32
33/// A linked hash set implemented as a `linked_hash_map::LinkedHashMap` where the value is
34/// `()`, in a similar way std `HashSet` is implemented from `HashMap`.
35///
36/// General usage is very similar to a std `HashSet`. However, a `LinkedHashSet` **maintains
37/// insertion order** using a doubly-linked list running through its entries. As such methods
38/// [`front()`], [`pop_front()`], [`back()`] and [`pop_back()`] are provided.
39///
40/// # Examples
41///
42/// ```
43/// use linked_hash_set::LinkedHashSet;
44/// // Type inference lets us omit an explicit type signature (which
45/// // would be `LinkedHashSet<&str>` in this example).
46/// let mut books = LinkedHashSet::new();
47///
48/// // Add some books.
49/// books.insert("A Dance With Dragons");
50/// books.insert("To Kill a Mockingbird");
51/// books.insert("The Odyssey");
52/// books.insert("The Great Gatsby");
53///
54/// // Check for a specific one.
55/// if !books.contains("The Winds of Winter") {
56/// println!(
57/// "We have {} books, but The Winds of Winter ain't one.",
58/// books.len()
59/// );
60/// }
61///
62/// // Remove a book.
63/// books.remove("The Odyssey");
64///
65/// // Remove the first inserted book.
66/// books.pop_front();
67///
68/// // Iterate over the remaining books in insertion order.
69/// for book in &books {
70/// println!("{}", book);
71/// }
72///
73/// assert_eq!(
74/// books.into_iter().collect::<Vec<_>>(),
75/// vec!["To Kill a Mockingbird", "The Great Gatsby"]
76/// );
77/// ```
78///
79/// The easiest way to use `LinkedHashSet` with a custom type is to derive
80/// `Eq` and `Hash`. We must also derive `PartialEq`, this will in the
81/// future be implied by `Eq`.
82///
83/// ```
84/// use linked_hash_set::LinkedHashSet;
85/// #[derive(Hash, Eq, PartialEq, Debug)]
86/// struct Viking<'a> {
87/// name: &'a str,
88/// power: usize,
89/// }
90///
91/// let mut vikings = LinkedHashSet::new();
92///
93/// vikings.insert(Viking {
94/// name: "Einar",
95/// power: 9,
96/// });
97/// vikings.insert(Viking {
98/// name: "Einar",
99/// power: 9,
100/// });
101/// vikings.insert(Viking {
102/// name: "Olaf",
103/// power: 4,
104/// });
105/// vikings.insert(Viking {
106/// name: "Harald",
107/// power: 8,
108/// });
109///
110/// // Use derived implementation to print the vikings.
111/// for x in &vikings {
112/// println!("{:?}", x);
113/// }
114/// ```
115///
116/// A `LinkedHashSet` with fixed list of elements can be initialized from an array:
117///
118/// ```
119/// use linked_hash_set::LinkedHashSet;
120///
121/// let viking_names: LinkedHashSet<&str> = ["Einar", "Olaf", "Harald"].into_iter().collect();
122/// // use the values stored in the set
123/// ```
124///
125/// [`front()`]: struct.LinkedHashSet.html#method.front
126/// [`pop_front()`]: struct.LinkedHashSet.html#method.pop_front
127/// [`back()`]: struct.LinkedHashSet.html#method.back
128/// [`pop_back()`]: struct.LinkedHashSet.html#method.pop_back
129pub struct LinkedHashSet<T, S = RandomState> {
130 map: LinkedHashMap<T, (), S>,
131}
132
133impl<T: Hash + Eq> LinkedHashSet<T, RandomState> {
134 /// Creates an empty `LinkedHashSet`.
135 ///
136 /// # Examples
137 ///
138 /// ```
139 /// use linked_hash_set::LinkedHashSet;
140 /// let set: LinkedHashSet<i32> = LinkedHashSet::new();
141 /// ```
142 #[inline]
143 pub fn new() -> LinkedHashSet<T, RandomState> {
144 LinkedHashSet {
145 map: LinkedHashMap::new(),
146 }
147 }
148
149 /// Creates an empty `LinkedHashSet` with the specified capacity.
150 ///
151 /// The hash set will be able to hold at least `capacity` elements without
152 /// reallocating. If `capacity` is 0, the hash set will not allocate.
153 ///
154 /// # Examples
155 ///
156 /// ```
157 /// use linked_hash_set::LinkedHashSet;
158 /// let set: LinkedHashSet<i32> = LinkedHashSet::with_capacity(10);
159 /// assert!(set.capacity() >= 10);
160 /// ```
161 #[inline]
162 pub fn with_capacity(capacity: usize) -> LinkedHashSet<T, RandomState> {
163 LinkedHashSet {
164 map: LinkedHashMap::with_capacity(capacity),
165 }
166 }
167}
168
169impl<T, S> LinkedHashSet<T, S>
170where
171 T: Eq + Hash,
172 S: BuildHasher,
173{
174 /// Creates a new empty hash set which will use the given hasher to hash
175 /// keys.
176 ///
177 /// The hash set is also created with the default initial capacity.
178 ///
179 /// Warning: `hasher` is normally randomly generated, and
180 /// is designed to allow `LinkedHashSet`s to be resistant to attacks that
181 /// cause many collisions and very poor performance. Setting it
182 /// manually using this function can expose a DoS attack vector.
183 ///
184 /// # Examples
185 ///
186 /// ```
187 /// use linked_hash_set::LinkedHashSet;
188 /// use std::collections::hash_map::RandomState;
189 ///
190 /// let s = RandomState::new();
191 /// let mut set = LinkedHashSet::with_hasher(s);
192 /// set.insert(2);
193 /// ```
194 #[inline]
195 pub fn with_hasher(hasher: S) -> LinkedHashSet<T, S> {
196 LinkedHashSet {
197 map: LinkedHashMap::with_hasher(hasher),
198 }
199 }
200
201 /// Creates an empty `LinkedHashSet` with with the specified capacity, using
202 /// `hasher` to hash the keys.
203 ///
204 /// The hash set will be able to hold at least `capacity` elements without
205 /// reallocating. If `capacity` is 0, the hash set will not allocate.
206 ///
207 /// Warning: `hasher` is normally randomly generated, and
208 /// is designed to allow `LinkedHashSet`s to be resistant to attacks that
209 /// cause many collisions and very poor performance. Setting it
210 /// manually using this function can expose a DoS attack vector.
211 ///
212 /// # Examples
213 ///
214 /// ```
215 /// use linked_hash_set::LinkedHashSet;
216 /// use std::collections::hash_map::RandomState;
217 ///
218 /// let s = RandomState::new();
219 /// let mut set = LinkedHashSet::with_capacity_and_hasher(10, s);
220 /// set.insert(1);
221 /// ```
222 #[inline]
223 pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> LinkedHashSet<T, S> {
224 LinkedHashSet {
225 map: LinkedHashMap::with_capacity_and_hasher(capacity, hasher),
226 }
227 }
228
229 /// Returns a reference to the set's `BuildHasher`.
230 ///
231 /// # Examples
232 ///
233 /// ```
234 /// use linked_hash_set::LinkedHashSet;
235 /// use std::collections::hash_map::RandomState;
236 ///
237 /// let hasher = RandomState::new();
238 /// let set: LinkedHashSet<i32> = LinkedHashSet::with_hasher(hasher);
239 /// let hasher: &RandomState = set.hasher();
240 /// ```
241 pub fn hasher(&self) -> &S {
242 self.map.hasher()
243 }
244
245 /// Returns the number of elements the set can hold without reallocating.
246 ///
247 /// # Examples
248 ///
249 /// ```
250 /// use linked_hash_set::LinkedHashSet;
251 /// let set: LinkedHashSet<i32> = LinkedHashSet::with_capacity(100);
252 /// assert!(set.capacity() >= 100);
253 /// ```
254 #[inline]
255 pub fn capacity(&self) -> usize {
256 self.map.capacity()
257 }
258
259 /// Reserves capacity for at least `additional` more elements to be inserted
260 /// in the `LinkedHashSet`. The collection may reserve more space to avoid
261 /// frequent reallocations.
262 ///
263 /// # Panics
264 ///
265 /// Panics if the new allocation size overflows `usize`.
266 ///
267 /// # Examples
268 ///
269 /// ```
270 /// use linked_hash_set::LinkedHashSet;
271 /// let mut set: LinkedHashSet<i32> = LinkedHashSet::new();
272 /// set.reserve(10);
273 /// assert!(set.capacity() >= 10);
274 /// ```
275 pub fn reserve(&mut self, additional: usize) {
276 self.map.reserve(additional)
277 }
278
279 /// Shrinks the capacity of the set as much as possible. It will drop
280 /// down as much as possible while maintaining the internal rules
281 /// and possibly leaving some space in accordance with the resize policy.
282 ///
283 /// # Examples
284 ///
285 /// ```
286 /// use linked_hash_set::LinkedHashSet;
287 ///
288 /// let mut set = LinkedHashSet::with_capacity(100);
289 /// set.insert(1);
290 /// set.insert(2);
291 /// assert!(set.capacity() >= 100);
292 /// set.shrink_to_fit();
293 /// assert!(set.capacity() >= 2);
294 /// ```
295 pub fn shrink_to_fit(&mut self) {
296 self.map.shrink_to_fit()
297 }
298
299 /// An iterator visiting all elements in insertion order.
300 /// The iterator element type is `&'a T`.
301 ///
302 /// # Examples
303 ///
304 /// ```
305 /// use linked_hash_set::LinkedHashSet;
306 /// let mut set = LinkedHashSet::new();
307 /// set.insert("a");
308 /// set.insert("b");
309 ///
310 /// // Will print in an insertion order.
311 /// for x in set.iter() {
312 /// println!("{}", x);
313 /// }
314 /// ```
315 pub fn iter(&self) -> Iter<'_, T> {
316 Iter {
317 iter: self.map.keys(),
318 }
319 }
320
321 /// Visits the values representing the difference,
322 /// i.e. the values that are in `self` but not in `other`.
323 ///
324 /// # Examples
325 ///
326 /// ```
327 /// use linked_hash_set::LinkedHashSet;
328 /// let a: LinkedHashSet<_> = [1, 2, 3].into_iter().collect();
329 /// let b: LinkedHashSet<_> = [4, 2, 3, 4].into_iter().collect();
330 ///
331 /// // Can be seen as `a - b`.
332 /// for x in a.difference(&b) {
333 /// println!("{}", x); // Print 1
334 /// }
335 ///
336 /// let diff: LinkedHashSet<_> = a.difference(&b).collect();
337 /// assert_eq!(diff, [1].iter().collect());
338 ///
339 /// // Note that difference is not symmetric,
340 /// // and `b - a` means something else:
341 /// let diff: LinkedHashSet<_> = b.difference(&a).collect();
342 /// assert_eq!(diff, [4].iter().collect());
343 /// ```
344 pub fn difference<'a>(&'a self, other: &'a LinkedHashSet<T, S>) -> Difference<'a, T, S> {
345 Difference {
346 iter: self.iter(),
347 other,
348 }
349 }
350
351 /// Visits the values representing the symmetric difference,
352 /// i.e. the values that are in `self` or in `other` but not in both.
353 ///
354 /// # Examples
355 ///
356 /// ```
357 /// use linked_hash_set::LinkedHashSet;
358 /// let a: LinkedHashSet<_> = [1, 2, 3].into_iter().collect();
359 /// let b: LinkedHashSet<_> = [4, 2, 3, 4].into_iter().collect();
360 ///
361 /// // Print 1, 4 in insertion order.
362 /// for x in a.symmetric_difference(&b) {
363 /// println!("{}", x);
364 /// }
365 ///
366 /// let diff1: LinkedHashSet<_> = a.symmetric_difference(&b).collect();
367 /// let diff2: LinkedHashSet<_> = b.symmetric_difference(&a).collect();
368 ///
369 /// assert_eq!(diff1, diff2);
370 /// assert_eq!(diff1, [1, 4].iter().collect());
371 /// ```
372 pub fn symmetric_difference<'a>(
373 &'a self,
374 other: &'a LinkedHashSet<T, S>,
375 ) -> SymmetricDifference<'a, T, S> {
376 SymmetricDifference {
377 iter: self.difference(other).chain(other.difference(self)),
378 }
379 }
380
381 /// Visits the values representing the intersection,
382 /// i.e. the values that are both in `self` and `other`.
383 ///
384 /// # Examples
385 ///
386 /// ```
387 /// use linked_hash_set::LinkedHashSet;
388 /// let a: LinkedHashSet<_> = [1, 2, 3].into_iter().collect();
389 /// let b: LinkedHashSet<_> = [4, 2, 3, 4].into_iter().collect();
390 ///
391 /// // Print 2, 3 in insertion order.
392 /// for x in a.intersection(&b) {
393 /// println!("{}", x);
394 /// }
395 ///
396 /// let intersection: LinkedHashSet<_> = a.intersection(&b).collect();
397 /// assert_eq!(intersection, [2, 3].iter().collect());
398 /// ```
399 pub fn intersection<'a>(&'a self, other: &'a LinkedHashSet<T, S>) -> Intersection<'a, T, S> {
400 Intersection {
401 iter: self.iter(),
402 other,
403 }
404 }
405
406 /// Visits the values representing the union,
407 /// i.e. all the values in `self` or `other`, without duplicates.
408 ///
409 /// # Examples
410 ///
411 /// ```
412 /// use linked_hash_set::LinkedHashSet;
413 /// let a: LinkedHashSet<_> = [1, 2, 3].into_iter().collect();
414 /// let b: LinkedHashSet<_> = [4, 2, 3, 4].into_iter().collect();
415 ///
416 /// // Print 1, 2, 3, 4 in insertion order.
417 /// for x in a.union(&b) {
418 /// println!("{}", x);
419 /// }
420 ///
421 /// let union: LinkedHashSet<_> = a.union(&b).collect();
422 /// assert_eq!(union, [1, 2, 3, 4].iter().collect());
423 /// ```
424 pub fn union<'a>(&'a self, other: &'a LinkedHashSet<T, S>) -> Union<'a, T, S> {
425 Union {
426 iter: self.iter().chain(other.difference(self)),
427 }
428 }
429
430 /// Returns the number of elements in the set.
431 ///
432 /// # Examples
433 ///
434 /// ```
435 /// use linked_hash_set::LinkedHashSet;
436 ///
437 /// let mut v = LinkedHashSet::new();
438 /// assert_eq!(v.len(), 0);
439 /// v.insert(1);
440 /// assert_eq!(v.len(), 1);
441 /// ```
442 pub fn len(&self) -> usize {
443 self.map.len()
444 }
445
446 /// Returns true if the set contains no elements.
447 ///
448 /// # Examples
449 ///
450 /// ```
451 /// use linked_hash_set::LinkedHashSet;
452 ///
453 /// let mut v = LinkedHashSet::new();
454 /// assert!(v.is_empty());
455 /// v.insert(1);
456 /// assert!(!v.is_empty());
457 /// ```
458 pub fn is_empty(&self) -> bool {
459 self.map.is_empty()
460 }
461
462 /// Clears the set, returning all elements in an iterator.
463 ///
464 /// # Examples
465 ///
466 /// ```
467 /// use linked_hash_set::LinkedHashSet;
468 ///
469 /// let mut set: LinkedHashSet<_> = [1, 2, 3].into_iter().collect();
470 /// assert!(!set.is_empty());
471 ///
472 /// // print 1, 2, 3 in an insertion order
473 /// for i in set.drain() {
474 /// println!("{}", i);
475 /// }
476 ///
477 /// assert!(set.is_empty());
478 /// ```
479 #[inline]
480 pub fn drain(&mut self) -> Drain<T> {
481 Drain {
482 iter: self.map.drain(),
483 }
484 }
485
486 /// Clears the set, removing all values.
487 ///
488 /// # Examples
489 ///
490 /// ```
491 /// use linked_hash_set::LinkedHashSet;
492 ///
493 /// let mut v = LinkedHashSet::new();
494 /// v.insert(1);
495 /// v.clear();
496 /// assert!(v.is_empty());
497 /// ```
498 pub fn clear(&mut self) {
499 self.map.clear()
500 }
501
502 /// Returns `true` if the set contains a value.
503 ///
504 /// The value may be any borrowed form of the set's value type, but
505 /// `Hash` and `Eq` on the borrowed form *must* match those for
506 /// the value type.
507 ///
508 /// # Examples
509 ///
510 /// ```
511 /// use linked_hash_set::LinkedHashSet;
512 ///
513 /// let set: LinkedHashSet<_> = [1, 2, 3].into_iter().collect();
514 /// assert_eq!(set.contains(&1), true);
515 /// assert_eq!(set.contains(&4), false);
516 /// ```
517 pub fn contains<Q>(&self, value: &Q) -> bool
518 where
519 T: Borrow<Q>,
520 Q: Hash + Eq,
521 Q: ?Sized,
522 {
523 self.map.contains_key(value)
524 }
525
526 /// If already present, moves a value to the end of the ordering.
527 ///
528 /// If the set did have this value present, `true` is returned.
529 ///
530 /// If the set did not have this value present, `false` is returned.
531 ///
532 /// Similar to `LinkedHashMap::get_refresh`.
533 ///
534 /// # Examples
535 ///
536 /// ```
537 /// use linked_hash_set::LinkedHashSet;
538 ///
539 /// let mut set: LinkedHashSet<_> = [1, 2, 3].into_iter().collect();
540 /// let was_refreshed = set.refresh(&2);
541 ///
542 /// assert_eq!(was_refreshed, true);
543 /// assert_eq!(set.into_iter().collect::<Vec<_>>(), vec![1, 3, 2]);
544 /// ```
545 pub fn refresh<Q>(&mut self, value: &Q) -> bool
546 where
547 T: Borrow<Q>,
548 Q: Hash + Eq,
549 Q: ?Sized,
550 {
551 self.map.get_refresh(value).is_some()
552 }
553
554 // TODO Non-trivial port without private access to map
555 // /// Returns a reference to the value in the set, if any, that is equal to the given value.
556 // ///
557 // /// The value may be any borrowed form of the set's value type, but
558 // /// `Hash` and `Eq` on the borrowed form *must* match those for
559 // /// the value type.
560 // pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T>
561 // where T: Borrow<Q>,
562 // Q: Hash + Eq
563 // {
564 // Recover::get(&self.map, value)
565 // }
566
567 /// Returns `true` if `self` has no elements in common with `other`.
568 /// This is equivalent to checking for an empty intersection.
569 ///
570 /// # Examples
571 ///
572 /// ```
573 /// use linked_hash_set::LinkedHashSet;
574 ///
575 /// let a: LinkedHashSet<_> = [1, 2, 3].into_iter().collect();
576 /// let mut b = LinkedHashSet::new();
577 ///
578 /// assert_eq!(a.is_disjoint(&b), true);
579 /// b.insert(4);
580 /// assert_eq!(a.is_disjoint(&b), true);
581 /// b.insert(1);
582 /// assert_eq!(a.is_disjoint(&b), false);
583 /// ```
584 pub fn is_disjoint(&self, other: &LinkedHashSet<T, S>) -> bool {
585 self.iter().all(|v| !other.contains(v))
586 }
587
588 /// Returns `true` if the set is a subset of another,
589 /// i.e. `other` contains at least all the values in `self`.
590 ///
591 /// # Examples
592 ///
593 /// ```
594 /// use linked_hash_set::LinkedHashSet;
595 ///
596 /// let sup: LinkedHashSet<_> = [1, 2, 3].into_iter().collect();
597 /// let mut set = LinkedHashSet::new();
598 ///
599 /// assert_eq!(set.is_subset(&sup), true);
600 /// set.insert(2);
601 /// assert_eq!(set.is_subset(&sup), true);
602 /// set.insert(4);
603 /// assert_eq!(set.is_subset(&sup), false);
604 /// ```
605 pub fn is_subset(&self, other: &LinkedHashSet<T, S>) -> bool {
606 self.iter().all(|v| other.contains(v))
607 }
608
609 /// Returns `true` if the set is a superset of another,
610 /// i.e. `self` contains at least all the values in `other`.
611 ///
612 /// # Examples
613 ///
614 /// ```
615 /// use linked_hash_set::LinkedHashSet;
616 ///
617 /// let sub: LinkedHashSet<_> = [1, 2].into_iter().collect();
618 /// let mut set = LinkedHashSet::new();
619 ///
620 /// assert_eq!(set.is_superset(&sub), false);
621 ///
622 /// set.insert(0);
623 /// set.insert(1);
624 /// assert_eq!(set.is_superset(&sub), false);
625 ///
626 /// set.insert(2);
627 /// assert_eq!(set.is_superset(&sub), true);
628 /// ```
629 #[inline]
630 pub fn is_superset(&self, other: &LinkedHashSet<T, S>) -> bool {
631 other.is_subset(self)
632 }
633
634 /// Adds a value to the set.
635 ///
636 /// If the set did not have this value present, `true` is returned.
637 ///
638 /// If the set did have this value present, `false` is returned.
639 ///
640 /// Note that performing this action will always place the value at the end of the ordering
641 /// whether the set already contained the value or not. Also see
642 /// [`insert_if_absent`](#method.insert_if_absent).
643 ///
644 /// # Examples
645 ///
646 /// ```
647 /// use linked_hash_set::LinkedHashSet;
648 ///
649 /// let mut set = LinkedHashSet::new();
650 ///
651 /// assert_eq!(set.insert(2), true);
652 /// assert_eq!(set.insert(2), false);
653 /// assert_eq!(set.len(), 1);
654 /// ```
655 pub fn insert(&mut self, value: T) -> bool {
656 self.map.insert(value, ()).is_none()
657 }
658
659 /// Adds a value to the set, if not already present. The distinction with `insert` is that
660 /// order of elements is unaffected when calling this method for a value already contained.
661 ///
662 /// If the set did not have this value present, `true` is returned.
663 ///
664 /// If the set did have this value present, `false` is returned.
665 ///
666 /// # Examples
667 ///
668 /// ```
669 /// use linked_hash_set::LinkedHashSet;
670 ///
671 /// let mut set = LinkedHashSet::new();
672 ///
673 /// assert_eq!(set.insert_if_absent(2), true);
674 /// assert_eq!(set.insert_if_absent(2), false);
675 /// assert_eq!(set.len(), 1);
676 /// ```
677 pub fn insert_if_absent(&mut self, value: T) -> bool {
678 if !self.map.contains_key(&value) {
679 self.map.insert(value, ()).is_none()
680 } else {
681 false
682 }
683 }
684
685 // TODO Non-trivial port without private access to map
686 // /// Adds a value to the set, replacing the existing value, if any, that is equal to the given
687 // /// one. Returns the replaced value.
688 // pub fn replace(&mut self, value: T) -> Option<T> {
689 // Recover::replace(&mut self.map, value)
690 // }
691
692 /// Removes a value from the set. Returns `true` if the value was
693 /// present in the set.
694 ///
695 /// The value may be any borrowed form of the set's value type, but
696 /// `Hash` and `Eq` on the borrowed form *must* match those for
697 /// the value type.
698 ///
699 /// This operation will not affect the ordering of the other elements.
700 ///
701 /// # Examples
702 ///
703 /// ```
704 /// use linked_hash_set::LinkedHashSet;
705 ///
706 /// let mut set = LinkedHashSet::new();
707 ///
708 /// set.insert(2);
709 /// assert_eq!(set.remove(&2), true);
710 /// assert_eq!(set.remove(&2), false);
711 /// ```
712 pub fn remove<Q>(&mut self, value: &Q) -> bool
713 where
714 T: Borrow<Q>,
715 Q: Hash + Eq,
716 Q: ?Sized,
717 {
718 self.map.remove(value).is_some()
719 }
720
721 // TODO Non-trivial port without private access to map
722 // /// Removes and returns the value in the set, if any, that is equal to the given one.
723 // ///
724 // /// The value may be any borrowed form of the set's value type, but
725 // /// `Hash` and `Eq` on the borrowed form *must* match those for
726 // /// the value type.
727 // pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T>
728 // where T: Borrow<Q>,
729 // Q: Hash + Eq
730 // {
731 // Recover::take(&mut self.map, value)
732 // }
733
734 // TODO not in linked_hash_map
735 // /// Retains only the elements specified by the predicate.
736 // ///
737 // /// In other words, remove all elements `e` such that `f(&e)` returns `false`.
738 // ///
739 // /// # Examples
740 // ///
741 // /// ```
742 // /// use linked_hash_set::LinkedHashSet;
743 // ///
744 // /// let xs = [1,2,3,4,5,6];
745 // /// let mut set: LinkedHashSet<isize> = xs.iter().cloned().collect();
746 // /// set.retain(|&k| k % 2 == 0);
747 // /// assert_eq!(set.len(), 3);
748 // /// ```
749 // pub fn retain<F>(&mut self, mut f: F)
750 // where F: FnMut(&T) -> bool
751 // {
752 // self.map.retain(|k, _| f(k));
753 // }
754
755 /// Gets the first entry.
756 pub fn front(&self) -> Option<&T> {
757 self.map.front().map(|(k, _)| k)
758 }
759
760 /// Removes the first entry.
761 pub fn pop_front(&mut self) -> Option<T> {
762 self.map.pop_front().map(|(k, _)| k)
763 }
764
765 /// Gets the last entry.
766 pub fn back(&self) -> Option<&T> {
767 self.map.back().map(|(k, _)| k)
768 }
769
770 /// Removes the last entry.
771 pub fn pop_back(&mut self) -> Option<T> {
772 self.map.pop_back().map(|(k, _)| k)
773 }
774}
775
776impl<T: Hash + Eq + Clone, S: BuildHasher + Clone> Clone for LinkedHashSet<T, S> {
777 fn clone(&self) -> Self {
778 let map: LinkedHashMap = self.map.clone();
779 Self { map }
780 }
781}
782
783impl<T, S> PartialEq for LinkedHashSet<T, S>
784where
785 T: Eq + Hash,
786 S: BuildHasher,
787{
788 fn eq(&self, other: &LinkedHashSet<T, S>) -> bool {
789 if self.len() != other.len() {
790 return false;
791 }
792
793 self.iter().all(|key: &T| other.contains(key))
794 }
795}
796
797impl<T, S> Hash for LinkedHashSet<T, S>
798where
799 T: Eq + Hash,
800 S: BuildHasher,
801{
802 fn hash<H: Hasher>(&self, state: &mut H) {
803 for e: &T in self {
804 e.hash(state);
805 }
806 }
807}
808
809impl<T, S> Eq for LinkedHashSet<T, S>
810where
811 T: Eq + Hash,
812 S: BuildHasher,
813{
814}
815
816impl<T, S> fmt::Debug for LinkedHashSet<T, S>
817where
818 T: Eq + Hash + fmt::Debug,
819 S: BuildHasher,
820{
821 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
822 f.debug_set().entries(self.iter()).finish()
823 }
824}
825
826impl<T, S> FromIterator<T> for LinkedHashSet<T, S>
827where
828 T: Eq + Hash,
829 S: BuildHasher + Default,
830{
831 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> LinkedHashSet<T, S> {
832 let mut set: LinkedHashSet = LinkedHashSet::with_hasher(Default::default());
833 set.extend(iter);
834 set
835 }
836}
837
838impl<T, S> Extend<T> for LinkedHashSet<T, S>
839where
840 T: Eq + Hash,
841 S: BuildHasher,
842{
843 fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
844 self.map.extend(iter.into_iter().map(|k: T| (k, ())));
845 }
846}
847
848impl<'a, T, S> Extend<&'a T> for LinkedHashSet<T, S>
849where
850 T: 'a + Eq + Hash + Copy,
851 S: BuildHasher,
852{
853 fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
854 self.extend(iter.into_iter().cloned());
855 }
856}
857
858impl<T, S> Default for LinkedHashSet<T, S>
859where
860 T: Eq + Hash,
861 S: BuildHasher + Default,
862{
863 /// Creates an empty `LinkedHashSet<T, S>` with the `Default` value for the hasher.
864 fn default() -> LinkedHashSet<T, S> {
865 LinkedHashSet {
866 map: LinkedHashMap::default(),
867 }
868 }
869}
870
871impl<T, S> BitOr<&LinkedHashSet<T, S>> for &LinkedHashSet<T, S>
872where
873 T: Eq + Hash + Clone,
874 S: BuildHasher + Default,
875{
876 type Output = LinkedHashSet<T, S>;
877
878 /// Returns the union of `self` and `rhs` as a new `LinkedHashSet<T, S>`.
879 ///
880 /// # Examples
881 ///
882 /// ```
883 /// use linked_hash_set::LinkedHashSet;
884 ///
885 /// let a: LinkedHashSet<_> = vec![1, 2, 3].into_iter().collect();
886 /// let b: LinkedHashSet<_> = vec![3, 4, 5].into_iter().collect();
887 ///
888 /// let set = &a | &b;
889 ///
890 /// let mut i = 0;
891 /// let expected = [1, 2, 3, 4, 5];
892 /// for x in &set {
893 /// assert!(expected.contains(x));
894 /// i += 1;
895 /// }
896 /// assert_eq!(i, expected.len());
897 /// ```
898 fn bitor(self, rhs: &LinkedHashSet<T, S>) -> LinkedHashSet<T, S> {
899 self.union(rhs).cloned().collect()
900 }
901}
902
903impl<T, S> BitAnd<&LinkedHashSet<T, S>> for &LinkedHashSet<T, S>
904where
905 T: Eq + Hash + Clone,
906 S: BuildHasher + Default,
907{
908 type Output = LinkedHashSet<T, S>;
909
910 /// Returns the intersection of `self` and `rhs` as a new `LinkedHashSet<T, S>`.
911 ///
912 /// # Examples
913 ///
914 /// ```
915 /// use linked_hash_set::LinkedHashSet;
916 ///
917 /// let a: LinkedHashSet<_> = vec![1, 2, 3].into_iter().collect();
918 /// let b: LinkedHashSet<_> = vec![2, 3, 4].into_iter().collect();
919 ///
920 /// let set = &a & &b;
921 ///
922 /// let mut i = 0;
923 /// let expected = [2, 3];
924 /// for x in &set {
925 /// assert!(expected.contains(x));
926 /// i += 1;
927 /// }
928 /// assert_eq!(i, expected.len());
929 /// ```
930 fn bitand(self, rhs: &LinkedHashSet<T, S>) -> LinkedHashSet<T, S> {
931 self.intersection(rhs).cloned().collect()
932 }
933}
934
935impl<T, S> BitXor<&LinkedHashSet<T, S>> for &LinkedHashSet<T, S>
936where
937 T: Eq + Hash + Clone,
938 S: BuildHasher + Default,
939{
940 type Output = LinkedHashSet<T, S>;
941
942 /// Returns the symmetric difference of `self` and `rhs` as a new `LinkedHashSet<T, S>`.
943 ///
944 /// # Examples
945 ///
946 /// ```
947 /// use linked_hash_set::LinkedHashSet;
948 ///
949 /// let a: LinkedHashSet<_> = vec![1, 2, 3].into_iter().collect();
950 /// let b: LinkedHashSet<_> = vec![3, 4, 5].into_iter().collect();
951 ///
952 /// let set = &a ^ &b;
953 ///
954 /// let mut i = 0;
955 /// let expected = [1, 2, 4, 5];
956 /// for x in &set {
957 /// assert!(expected.contains(x));
958 /// i += 1;
959 /// }
960 /// assert_eq!(i, expected.len());
961 /// ```
962 fn bitxor(self, rhs: &LinkedHashSet<T, S>) -> LinkedHashSet<T, S> {
963 self.symmetric_difference(rhs).cloned().collect()
964 }
965}
966
967impl<T, S> Sub<&LinkedHashSet<T, S>> for &LinkedHashSet<T, S>
968where
969 T: Eq + Hash + Clone,
970 S: BuildHasher + Default,
971{
972 type Output = LinkedHashSet<T, S>;
973
974 /// Returns the difference of `self` and `rhs` as a new `LinkedHashSet<T, S>`.
975 ///
976 /// # Examples
977 ///
978 /// ```
979 /// use linked_hash_set::LinkedHashSet;
980 ///
981 /// let a: LinkedHashSet<_> = vec![1, 2, 3].into_iter().collect();
982 /// let b: LinkedHashSet<_> = vec![3, 4, 5].into_iter().collect();
983 ///
984 /// let set = &a - &b;
985 ///
986 /// let mut i = 0;
987 /// let expected = [1, 2];
988 /// for x in &set {
989 /// assert!(expected.contains(x));
990 /// i += 1;
991 /// }
992 /// assert_eq!(i, expected.len());
993 /// ```
994 fn sub(self, rhs: &LinkedHashSet<T, S>) -> LinkedHashSet<T, S> {
995 self.difference(rhs).cloned().collect()
996 }
997}
998
999/// An iterator over the items of a `LinkedHashSet`.
1000///
1001/// This `struct` is created by the [`iter`] method on [`LinkedHashSet`].
1002/// See its documentation for more.
1003/// [`LinkedHashSet`]: struct.LinkedHashSet.html
1004/// [`iter`]: struct.LinkedHashSet.html#method.iter
1005pub struct Iter<'a, K> {
1006 iter: Keys<'a, K, ()>,
1007}
1008
1009/// An owning iterator over the items of a `LinkedHashSet`.
1010///
1011/// This `struct` is created by the [`into_iter`] method on [`LinkedHashSet`][`LinkedHashSet`]
1012/// (provided by the `IntoIterator` trait). See its documentation for more.
1013///
1014/// [`LinkedHashSet`]: struct.LinkedHashSet.html
1015/// [`into_iter`]: struct.LinkedHashSet.html#method.into_iter
1016pub struct IntoIter<K> {
1017 iter: map::IntoIter<K, ()>,
1018}
1019
1020/// A draining iterator over the items of a `LinkedHashSet`.
1021///
1022/// This `struct` is created by the [`drain`] method on [`LinkedHashSet`].
1023/// See its documentation for more.
1024///
1025/// [`LinkedHashSet`]: struct.LinkedHashSet.html
1026/// [`drain`]: struct.LinkedHashSet.html#method.drain
1027pub struct Drain<'a, K: 'a> {
1028 iter: map::Drain<'a, K, ()>,
1029}
1030
1031/// A lazy iterator producing elements in the intersection of `LinkedHashSet`s.
1032///
1033/// This `struct` is created by the [`intersection`] method on [`LinkedHashSet`].
1034/// See its documentation for more.
1035///
1036/// [`LinkedHashSet`]: struct.LinkedHashSet.html
1037/// [`intersection`]: struct.LinkedHashSet.html#method.intersection
1038pub struct Intersection<'a, T, S> {
1039 // iterator of the first set
1040 iter: Iter<'a, T>,
1041 // the second set
1042 other: &'a LinkedHashSet<T, S>,
1043}
1044
1045/// A lazy iterator producing elements in the difference of `LinkedHashSet`s.
1046///
1047/// This `struct` is created by the [`difference`] method on [`LinkedHashSet`].
1048/// See its documentation for more.
1049///
1050/// [`LinkedHashSet`]: struct.LinkedHashSet.html
1051/// [`difference`]: struct.LinkedHashSet.html#method.difference
1052pub struct Difference<'a, T, S> {
1053 // iterator of the first set
1054 iter: Iter<'a, T>,
1055 // the second set
1056 other: &'a LinkedHashSet<T, S>,
1057}
1058
1059/// A lazy iterator producing elements in the symmetric difference of `LinkedHashSet`s.
1060///
1061/// This `struct` is created by the [`symmetric_difference`] method on
1062/// [`LinkedHashSet`]. See its documentation for more.
1063///
1064/// [`LinkedHashSet`]: struct.LinkedHashSet.html
1065/// [`symmetric_difference`]: struct.LinkedHashSet.html#method.symmetric_difference
1066pub struct SymmetricDifference<'a, T, S> {
1067 iter: Chain<Difference<'a, T, S>, Difference<'a, T, S>>,
1068}
1069
1070/// A lazy iterator producing elements in the union of `LinkedHashSet`s.
1071///
1072/// This `struct` is created by the [`union`] method on [`LinkedHashSet`].
1073/// See its documentation for more.
1074///
1075/// [`LinkedHashSet`]: struct.LinkedHashSet.html
1076/// [`union`]: struct.LinkedHashSet.html#method.union
1077pub struct Union<'a, T, S> {
1078 iter: Chain<Iter<'a, T>, Difference<'a, T, S>>,
1079}
1080
1081impl<'a, T, S> IntoIterator for &'a LinkedHashSet<T, S>
1082where
1083 T: Eq + Hash,
1084 S: BuildHasher,
1085{
1086 type Item = &'a T;
1087 type IntoIter = Iter<'a, T>;
1088
1089 fn into_iter(self) -> Iter<'a, T> {
1090 self.iter()
1091 }
1092}
1093
1094impl<T, S> IntoIterator for LinkedHashSet<T, S>
1095where
1096 T: Eq + Hash,
1097 S: BuildHasher,
1098{
1099 type Item = T;
1100 type IntoIter = IntoIter<T>;
1101
1102 /// Creates a consuming iterator, that is, one that moves each value out
1103 /// of the set in insertion order. The set cannot be used after calling
1104 /// this.
1105 ///
1106 /// # Examples
1107 ///
1108 /// ```
1109 /// use linked_hash_set::LinkedHashSet;
1110 /// let mut set = LinkedHashSet::new();
1111 /// set.insert("a".to_string());
1112 /// set.insert("b".to_string());
1113 ///
1114 /// // Not possible to collect to a Vec<String> with a regular `.iter()`.
1115 /// let v: Vec<String> = set.into_iter().collect();
1116 ///
1117 /// // Will print in an insertion order.
1118 /// for x in &v {
1119 /// println!("{}", x);
1120 /// }
1121 /// ```
1122 fn into_iter(self) -> IntoIter<T> {
1123 IntoIter {
1124 iter: self.map.into_iter(),
1125 }
1126 }
1127}
1128
1129impl<'a, K> Clone for Iter<'a, K> {
1130 fn clone(&self) -> Iter<'a, K> {
1131 Iter {
1132 iter: self.iter.clone(),
1133 }
1134 }
1135}
1136impl<'a, K> Iterator for Iter<'a, K> {
1137 type Item = &'a K;
1138
1139 fn next(&mut self) -> Option<&'a K> {
1140 self.iter.next()
1141 }
1142 fn size_hint(&self) -> (usize, Option<usize>) {
1143 self.iter.size_hint()
1144 }
1145}
1146impl<K> ExactSizeIterator for Iter<'_, K> {
1147 fn len(&self) -> usize {
1148 self.iter.len()
1149 }
1150}
1151impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
1152 fn next_back(&mut self) -> Option<&'a T> {
1153 self.iter.next_back()
1154 }
1155}
1156
1157impl<K: fmt::Debug> fmt::Debug for Iter<'_, K> {
1158 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1159 f.debug_list().entries(self.clone()).finish()
1160 }
1161}
1162
1163impl<K> Iterator for IntoIter<K> {
1164 type Item = K;
1165
1166 fn next(&mut self) -> Option<K> {
1167 self.iter.next().map(|(k: K, _)| k)
1168 }
1169 fn size_hint(&self) -> (usize, Option<usize>) {
1170 self.iter.size_hint()
1171 }
1172}
1173impl<K> ExactSizeIterator for IntoIter<K> {
1174 fn len(&self) -> usize {
1175 self.iter.len()
1176 }
1177}
1178impl<K> DoubleEndedIterator for IntoIter<K> {
1179 fn next_back(&mut self) -> Option<K> {
1180 self.iter.next_back().map(|(k: K, _)| k)
1181 }
1182}
1183
1184// TODO Non-trivial port without private access to map
1185// impl<K: fmt::Debug> fmt::Debug for IntoIter<K> {
1186// fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1187// let entries_iter = self.iter
1188// .inner
1189// .iter()
1190// .map(|(k, _)| k);
1191// f.debug_list().entries(entries_iter).finish()
1192// }
1193// }
1194
1195impl<K> Iterator for Drain<'_, K> {
1196 type Item = K;
1197
1198 fn next(&mut self) -> Option<K> {
1199 self.iter.next().map(|(k: K, _)| k)
1200 }
1201 fn size_hint(&self) -> (usize, Option<usize>) {
1202 self.iter.size_hint()
1203 }
1204}
1205
1206impl<K> ExactSizeIterator for Drain<'_, K> {
1207 fn len(&self) -> usize {
1208 self.iter.len()
1209 }
1210}
1211
1212// TODO Non-trivial port without private access to map
1213// impl<'a, K: fmt::Debug> fmt::Debug for Drain<'a, K> {
1214// fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1215// let entries_iter = self.iter
1216// .inner
1217// .iter()
1218// .map(|(k, _)| k);
1219// f.debug_list().entries(entries_iter).finish()
1220// }
1221// }
1222
1223impl<'a, T, S> Clone for Intersection<'a, T, S> {
1224 fn clone(&self) -> Intersection<'a, T, S> {
1225 Intersection {
1226 iter: self.iter.clone(),
1227 ..*self
1228 }
1229 }
1230}
1231
1232impl<'a, T, S> Iterator for Intersection<'a, T, S>
1233where
1234 T: Eq + Hash,
1235 S: BuildHasher,
1236{
1237 type Item = &'a T;
1238
1239 fn next(&mut self) -> Option<&'a T> {
1240 loop {
1241 match self.iter.next() {
1242 None => return None,
1243 Some(elt: &'a T) => {
1244 if self.other.contains(elt) {
1245 return Some(elt);
1246 }
1247 }
1248 }
1249 }
1250 }
1251
1252 fn size_hint(&self) -> (usize, Option<usize>) {
1253 let (_, upper: Option) = self.iter.size_hint();
1254 (0, upper)
1255 }
1256}
1257
1258impl<T, S> fmt::Debug for Intersection<'_, T, S>
1259where
1260 T: fmt::Debug + Eq + Hash,
1261 S: BuildHasher,
1262{
1263 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1264 f.debug_list().entries(self.clone()).finish()
1265 }
1266}
1267
1268impl<'a, T, S> Clone for Difference<'a, T, S> {
1269 fn clone(&self) -> Difference<'a, T, S> {
1270 Difference {
1271 iter: self.iter.clone(),
1272 ..*self
1273 }
1274 }
1275}
1276
1277impl<'a, T, S> Iterator for Difference<'a, T, S>
1278where
1279 T: Eq + Hash,
1280 S: BuildHasher,
1281{
1282 type Item = &'a T;
1283
1284 fn next(&mut self) -> Option<&'a T> {
1285 loop {
1286 match self.iter.next() {
1287 None => return None,
1288 Some(elt: &'a T) => {
1289 if !self.other.contains(elt) {
1290 return Some(elt);
1291 }
1292 }
1293 }
1294 }
1295 }
1296
1297 fn size_hint(&self) -> (usize, Option<usize>) {
1298 let (_, upper: Option) = self.iter.size_hint();
1299 (0, upper)
1300 }
1301}
1302
1303impl<T, S> fmt::Debug for Difference<'_, T, S>
1304where
1305 T: fmt::Debug + Eq + Hash,
1306 S: BuildHasher,
1307{
1308 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1309 f.debug_list().entries(self.clone()).finish()
1310 }
1311}
1312
1313impl<'a, T, S> Clone for SymmetricDifference<'a, T, S> {
1314 fn clone(&self) -> SymmetricDifference<'a, T, S> {
1315 SymmetricDifference {
1316 iter: self.iter.clone(),
1317 }
1318 }
1319}
1320
1321impl<'a, T, S> Iterator for SymmetricDifference<'a, T, S>
1322where
1323 T: Eq + Hash,
1324 S: BuildHasher,
1325{
1326 type Item = &'a T;
1327
1328 fn next(&mut self) -> Option<&'a T> {
1329 self.iter.next()
1330 }
1331 fn size_hint(&self) -> (usize, Option<usize>) {
1332 self.iter.size_hint()
1333 }
1334}
1335
1336impl<T, S> fmt::Debug for SymmetricDifference<'_, T, S>
1337where
1338 T: fmt::Debug + Eq + Hash,
1339 S: BuildHasher,
1340{
1341 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1342 f.debug_list().entries(self.clone()).finish()
1343 }
1344}
1345
1346impl<'a, T, S> Clone for Union<'a, T, S> {
1347 fn clone(&self) -> Union<'a, T, S> {
1348 Union {
1349 iter: self.iter.clone(),
1350 }
1351 }
1352}
1353
1354impl<T, S> fmt::Debug for Union<'_, T, S>
1355where
1356 T: fmt::Debug + Eq + Hash,
1357 S: BuildHasher,
1358{
1359 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1360 f.debug_list().entries(self.clone()).finish()
1361 }
1362}
1363
1364impl<'a, T, S> Iterator for Union<'a, T, S>
1365where
1366 T: Eq + Hash,
1367 S: BuildHasher,
1368{
1369 type Item = &'a T;
1370
1371 fn next(&mut self) -> Option<&'a T> {
1372 self.iter.next()
1373 }
1374 fn size_hint(&self) -> (usize, Option<usize>) {
1375 self.iter.size_hint()
1376 }
1377}
1378
1379// TODO does not currently work like HashSet-HashMap with linked_hash_map
1380// #[allow(dead_code)]
1381// fn assert_covariance() {
1382// fn set<'new>(v: LinkedHashSet<&'static str>) -> LinkedHashSet<&'new str> {
1383// v
1384// }
1385// fn iter<'a, 'new>(v: Iter<'a, &'static str>) -> Iter<'a, &'new str> {
1386// v
1387// }
1388// fn into_iter<'new>(v: IntoIter<&'static str>) -> IntoIter<&'new str> {
1389// v
1390// }
1391// fn difference<'a, 'new>(v: Difference<'a, &'static str, RandomState>)
1392// -> Difference<'a, &'new str, RandomState> {
1393// v
1394// }
1395// fn symmetric_difference<'a, 'new>(v: SymmetricDifference<'a, &'static str, RandomState>)
1396// -> SymmetricDifference<'a, &'new str, RandomState> {
1397// v
1398// }
1399// fn intersection<'a, 'new>(v: Intersection<'a, &'static str, RandomState>)
1400// -> Intersection<'a, &'new str, RandomState> {
1401// v
1402// }
1403// fn union<'a, 'new>(v: Union<'a, &'static str, RandomState>)
1404// -> Union<'a, &'new str, RandomState> {
1405// v
1406// }
1407// fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
1408// d
1409// }
1410// }
1411
1412// Tests in common with `HashSet`
1413#[cfg(test)]
1414mod test_set {
1415 use super::*;
1416
1417 #[test]
1418 fn test_zero_capacities() {
1419 type HS = LinkedHashSet<i32>;
1420
1421 let s = HS::new();
1422 assert_eq!(s.capacity(), 0);
1423
1424 let s = HS::default();
1425 assert_eq!(s.capacity(), 0);
1426
1427 let s = HS::with_hasher(RandomState::new());
1428 assert_eq!(s.capacity(), 0);
1429
1430 let s = HS::with_capacity(0);
1431 assert_eq!(s.capacity(), 0);
1432
1433 let s = HS::with_capacity_and_hasher(0, RandomState::new());
1434 assert_eq!(s.capacity(), 0);
1435
1436 let mut s = HS::new();
1437 s.insert(1);
1438 s.insert(2);
1439 s.remove(&1);
1440 s.remove(&2);
1441 s.shrink_to_fit();
1442 assert_eq!(s.capacity(), 0);
1443
1444 let mut s = HS::new();
1445 s.reserve(0);
1446 assert_eq!(s.capacity(), 0);
1447 }
1448
1449 #[test]
1450 fn test_disjoint() {
1451 let mut xs = LinkedHashSet::new();
1452 let mut ys = LinkedHashSet::new();
1453 assert!(xs.is_disjoint(&ys));
1454 assert!(ys.is_disjoint(&xs));
1455 assert!(xs.insert(5));
1456 assert!(ys.insert(11));
1457 assert!(xs.is_disjoint(&ys));
1458 assert!(ys.is_disjoint(&xs));
1459 assert!(xs.insert(7));
1460 assert!(xs.insert(19));
1461 assert!(xs.insert(4));
1462 assert!(ys.insert(2));
1463 assert!(ys.insert(-11));
1464 assert!(xs.is_disjoint(&ys));
1465 assert!(ys.is_disjoint(&xs));
1466 assert!(ys.insert(7));
1467 assert!(!xs.is_disjoint(&ys));
1468 assert!(!ys.is_disjoint(&xs));
1469 }
1470
1471 #[test]
1472 fn test_subset_and_superset() {
1473 let mut a = LinkedHashSet::new();
1474 assert!(a.insert(0));
1475 assert!(a.insert(5));
1476 assert!(a.insert(11));
1477 assert!(a.insert(7));
1478
1479 let mut b = LinkedHashSet::new();
1480 assert!(b.insert(0));
1481 assert!(b.insert(7));
1482 assert!(b.insert(19));
1483 assert!(b.insert(250));
1484 assert!(b.insert(11));
1485 assert!(b.insert(200));
1486
1487 assert!(!a.is_subset(&b));
1488 assert!(!a.is_superset(&b));
1489 assert!(!b.is_subset(&a));
1490 assert!(!b.is_superset(&a));
1491
1492 assert!(b.insert(5));
1493
1494 assert!(a.is_subset(&b));
1495 assert!(!a.is_superset(&b));
1496 assert!(!b.is_subset(&a));
1497 assert!(b.is_superset(&a));
1498 }
1499
1500 #[test]
1501 fn test_iterate() {
1502 let mut a = LinkedHashSet::new();
1503 for i in 0..32 {
1504 assert!(a.insert(i));
1505 }
1506 let mut observed: u32 = 0;
1507 for k in &a {
1508 observed |= 1 << *k;
1509 }
1510 assert_eq!(observed, 0xFFFF_FFFF);
1511 }
1512
1513 #[test]
1514 fn test_intersection() {
1515 let mut a = LinkedHashSet::new();
1516 let mut b = LinkedHashSet::new();
1517
1518 assert!(a.insert(11));
1519 assert!(a.insert(1));
1520 assert!(a.insert(3));
1521 assert!(a.insert(77));
1522 assert!(a.insert(103));
1523 assert!(a.insert(5));
1524 assert!(a.insert(-5));
1525
1526 assert!(b.insert(2));
1527 assert!(b.insert(11));
1528 assert!(b.insert(77));
1529 assert!(b.insert(-9));
1530 assert!(b.insert(-42));
1531 assert!(b.insert(5));
1532 assert!(b.insert(3));
1533
1534 let mut i = 0;
1535 let expected = [3, 5, 11, 77];
1536 for x in a.intersection(&b) {
1537 assert!(expected.contains(x));
1538 i += 1
1539 }
1540 assert_eq!(i, expected.len());
1541 }
1542
1543 #[test]
1544 fn test_difference() {
1545 let mut a = LinkedHashSet::new();
1546 let mut b = LinkedHashSet::new();
1547
1548 assert!(a.insert(1));
1549 assert!(a.insert(3));
1550 assert!(a.insert(5));
1551 assert!(a.insert(9));
1552 assert!(a.insert(11));
1553
1554 assert!(b.insert(3));
1555 assert!(b.insert(9));
1556
1557 let mut i = 0;
1558 let expected = [1, 5, 11];
1559 for x in a.difference(&b) {
1560 assert!(expected.contains(x));
1561 i += 1
1562 }
1563 assert_eq!(i, expected.len());
1564 }
1565
1566 #[test]
1567 fn test_symmetric_difference() {
1568 let mut a = LinkedHashSet::new();
1569 let mut b = LinkedHashSet::new();
1570
1571 assert!(a.insert(1));
1572 assert!(a.insert(3));
1573 assert!(a.insert(5));
1574 assert!(a.insert(9));
1575 assert!(a.insert(11));
1576
1577 assert!(b.insert(-2));
1578 assert!(b.insert(3));
1579 assert!(b.insert(9));
1580 assert!(b.insert(14));
1581 assert!(b.insert(22));
1582
1583 let mut i = 0;
1584 let expected = [-2, 1, 5, 11, 14, 22];
1585 for x in a.symmetric_difference(&b) {
1586 assert!(expected.contains(x));
1587 i += 1
1588 }
1589 assert_eq!(i, expected.len());
1590 }
1591
1592 #[test]
1593 fn test_union() {
1594 let mut a = LinkedHashSet::new();
1595 let mut b = LinkedHashSet::new();
1596
1597 assert!(a.insert(1));
1598 assert!(a.insert(3));
1599 assert!(a.insert(5));
1600 assert!(a.insert(9));
1601 assert!(a.insert(11));
1602 assert!(a.insert(16));
1603 assert!(a.insert(19));
1604 assert!(a.insert(24));
1605
1606 assert!(b.insert(-2));
1607 assert!(b.insert(1));
1608 assert!(b.insert(5));
1609 assert!(b.insert(9));
1610 assert!(b.insert(13));
1611 assert!(b.insert(19));
1612
1613 let mut i = 0;
1614 let expected = [-2, 1, 3, 5, 9, 11, 13, 16, 19, 24];
1615 for x in a.union(&b) {
1616 assert!(expected.contains(x));
1617 i += 1
1618 }
1619 assert_eq!(i, expected.len());
1620 }
1621
1622 #[test]
1623 fn test_from_iter() {
1624 let xs = [1, 2, 3, 4, 5, 6, 7, 8, 9];
1625
1626 let set: LinkedHashSet<_> = xs.iter().cloned().collect();
1627
1628 for x in &xs {
1629 assert!(set.contains(x));
1630 }
1631 }
1632
1633 #[test]
1634 fn test_move_iter() {
1635 let hs = {
1636 let mut hs = LinkedHashSet::new();
1637
1638 hs.insert('a');
1639 hs.insert('b');
1640
1641 hs
1642 };
1643
1644 let v = hs.into_iter().collect::<Vec<char>>();
1645 assert!(v == ['a', 'b'] || v == ['b', 'a']);
1646 }
1647
1648 #[test]
1649 fn test_eq() {
1650 // These constants once happened to expose a bug in insert().
1651 // I'm keeping them around to prevent a regression.
1652 let mut s1 = LinkedHashSet::new();
1653
1654 s1.insert(1);
1655 s1.insert(2);
1656 s1.insert(3);
1657
1658 let mut s2 = LinkedHashSet::new();
1659
1660 s2.insert(1);
1661 s2.insert(2);
1662
1663 assert!(s1 != s2);
1664
1665 s2.insert(3);
1666
1667 assert_eq!(s1, s2);
1668 }
1669
1670 #[test]
1671 fn test_show() {
1672 let mut set = LinkedHashSet::new();
1673 let empty = LinkedHashSet::<i32>::new();
1674
1675 set.insert(1);
1676 set.insert(2);
1677
1678 let set_str = format!("{:?}", set);
1679
1680 assert!(set_str == "{1, 2}" || set_str == "{2, 1}");
1681 assert_eq!(format!("{:?}", empty), "{}");
1682 }
1683
1684 #[test]
1685 fn test_trivial_drain() {
1686 let mut s = LinkedHashSet::<i32>::new();
1687 for _ in s.drain() {}
1688 assert!(s.is_empty());
1689 drop(s);
1690
1691 let mut s = LinkedHashSet::<i32>::new();
1692 drop(s.drain());
1693 assert!(s.is_empty());
1694 }
1695
1696 #[test]
1697 fn test_drain() {
1698 let mut s: LinkedHashSet<_> = (1..100).collect();
1699
1700 // try this a bunch of times to make sure we don't screw up internal state.
1701 for _ in 0..20 {
1702 assert_eq!(s.len(), 99);
1703
1704 {
1705 let mut last_i = 0;
1706 let mut d = s.drain();
1707 for (i, x) in d.by_ref().take(50).enumerate() {
1708 last_i = i;
1709 assert!(x != 0);
1710 }
1711 assert_eq!(last_i, 49);
1712 }
1713
1714 assert!(s.is_empty(), "{s:?}");
1715
1716 // reset to try again.
1717 s.extend(1..100);
1718 }
1719 }
1720
1721 // #[test]
1722 // fn test_replace() {
1723 // use std::hash;
1724
1725 // #[derive(Debug)]
1726 // struct Foo(&'static str, i32);
1727
1728 // impl PartialEq for Foo {
1729 // fn eq(&self, other: &Self) -> bool {
1730 // self.0 == other.0
1731 // }
1732 // }
1733
1734 // impl Eq for Foo {}
1735
1736 // impl hash::Hash for Foo {
1737 // fn hash<H: hash::Hasher>(&self, h: &mut H) {
1738 // self.0.hash(h);
1739 // }
1740 // }
1741
1742 // let mut s = LinkedHashSet::new();
1743 // assert_eq!(s.replace(Foo("a", 1)), None);
1744 // assert_eq!(s.len(), 1);
1745 // assert_eq!(s.replace(Foo("a", 2)), Some(Foo("a", 1)));
1746 // assert_eq!(s.len(), 1);
1747
1748 // let mut it = s.iter();
1749 // assert_eq!(it.next(), Some(&Foo("a", 2)));
1750 // assert_eq!(it.next(), None);
1751 // }
1752
1753 #[test]
1754 fn test_extend_ref() {
1755 let mut a = LinkedHashSet::new();
1756 a.insert(1);
1757
1758 a.extend(&[2, 3, 4]);
1759
1760 assert_eq!(a.len(), 4);
1761 assert!(a.contains(&1));
1762 assert!(a.contains(&2));
1763 assert!(a.contains(&3));
1764 assert!(a.contains(&4));
1765
1766 let mut b = LinkedHashSet::new();
1767 b.insert(5);
1768 b.insert(6);
1769
1770 a.extend(&b);
1771
1772 assert_eq!(a.len(), 6);
1773 assert!(a.contains(&1));
1774 assert!(a.contains(&2));
1775 assert!(a.contains(&3));
1776 assert!(a.contains(&4));
1777 assert!(a.contains(&5));
1778 assert!(a.contains(&6));
1779 }
1780
1781 // #[test]
1782 // fn test_retain() {
1783 // let xs = [1, 2, 3, 4, 5, 6];
1784 // let mut set: LinkedHashSet<isize> = xs.iter().cloned().collect();
1785 // set.retain(|&k| k % 2 == 0);
1786 // assert_eq!(set.len(), 3);
1787 // assert!(set.contains(&2));
1788 // assert!(set.contains(&4));
1789 // assert!(set.contains(&6));
1790 // }
1791}
1792
1793// Tests for `LinkedHashSet` functionality over `HashSet`
1794#[cfg(test)]
1795mod test_linked {
1796 use super::*;
1797
1798 macro_rules! set {
1799 ($($el:expr),*) => {{
1800 let mut set = LinkedHashSet::new();
1801 $(
1802 set.insert($el);
1803 )*
1804 set
1805 }}
1806 }
1807
1808 #[test]
1809 fn order_is_maintained() {
1810 let set = set![123, 234, 56, 677];
1811 assert_eq!(set.into_iter().collect::<Vec<_>>(), vec![123, 234, 56, 677]);
1812 }
1813
1814 #[test]
1815 fn clone_order_is_maintained() {
1816 let set = set![123, 234, 56, 677];
1817 assert_eq!(set.into_iter().collect::<Vec<_>>(), vec![123, 234, 56, 677]);
1818 }
1819
1820 #[test]
1821 fn delegate_front() {
1822 let set = set![123, 234, 56, 677];
1823 assert_eq!(set.front(), Some(&123));
1824 }
1825
1826 #[test]
1827 fn delegate_pop_front() {
1828 let mut set = set![123, 234, 56, 677];
1829 assert_eq!(set.pop_front(), Some(123));
1830 assert_eq!(set.into_iter().collect::<Vec<_>>(), vec![234, 56, 677]);
1831 }
1832
1833 #[test]
1834 fn delegate_back() {
1835 let set = set![123, 234, 56, 677];
1836 assert_eq!(set.back(), Some(&677));
1837 }
1838
1839 #[test]
1840 fn delegate_pop_back() {
1841 let mut set = set![123, 234, 56, 677];
1842 assert_eq!(set.pop_back(), Some(677));
1843 assert_eq!(set.into_iter().collect::<Vec<_>>(), vec![123, 234, 56]);
1844 }
1845
1846 #[test]
1847 fn double_ended_iter() {
1848 let set = set![123, 234, 56, 677];
1849 let mut iter = set.iter();
1850
1851 assert_eq!(iter.next(), Some(&123));
1852 assert_eq!(iter.next(), Some(&234));
1853 assert_eq!(iter.next_back(), Some(&677));
1854 assert_eq!(iter.next_back(), Some(&56));
1855
1856 assert_eq!(iter.next(), None);
1857 assert_eq!(iter.next_back(), None);
1858 }
1859
1860 #[test]
1861 fn double_ended_into_iter() {
1862 let mut iter = set![123, 234, 56, 677].into_iter();
1863
1864 assert_eq!(iter.next(), Some(123));
1865 assert_eq!(iter.next_back(), Some(677));
1866 assert_eq!(iter.next_back(), Some(56));
1867 assert_eq!(iter.next_back(), Some(234));
1868
1869 assert_eq!(iter.next(), None);
1870 assert_eq!(iter.next_back(), None);
1871 }
1872
1873 #[test]
1874 fn linked_set_equality() {
1875 let mut set1 = LinkedHashSet::new();
1876 assert!(set1.insert(234));
1877 assert!(set1.insert(123));
1878 assert!(set1.insert(345));
1879
1880 let mut set2 = LinkedHashSet::new();
1881 assert!(set2.insert(123));
1882 assert!(set2.insert(345));
1883 assert!(set2.insert(234));
1884
1885 assert_eq!(set1, set2);
1886
1887 /// Returns true if the given sets are equal and have identical iteration order.
1888 fn equal_and_same_order(a: &LinkedHashSet<i32>, b: &LinkedHashSet<i32>) -> bool {
1889 a.len() == b.len() && a.iter().eq(b)
1890 }
1891
1892 assert!(!equal_and_same_order(&set1, &set2));
1893
1894 let mut set3 = LinkedHashSet::new();
1895 assert!(set3.insert(234));
1896 assert!(set3.insert(123));
1897 assert!(set3.insert(345));
1898
1899 assert!(equal_and_same_order(&set1, &set3));
1900 }
1901}
1902