linked_hash_table/
set.rs

1//! [`LinkedHashSet`] - an insertion-ordered hash set.
2//!
3//! Implemented as a thin wrapper around [`LinkedHashMap<T, ()>`].
4//!
5//! | Iterator type | Created by | Yields |
6//! |---------------|-----------|--------|
7//! | [`SetIter`] | [`iter`] | `&T` |
8//! | [`SetDrain`] | [`drain`] | `T` - empties the set |
9//! | [`SetIntoIter`] | [`into_iter`] | `T` - consumes the set |
10//!
11//! [`iter`]: LinkedHashSet::iter
12//! [`drain`]: LinkedHashSet::drain
13//! [`into_iter`]: LinkedHashSet::into_iter
14
15use std::borrow::Borrow;
16use std::fmt;
17use std::hash::{BuildHasher, Hash, RandomState};
18
19use crate::LinkedHashMap;
20use crate::iter::{Drain as MapDrain, IntoIter as MapIntoIter, Keys};
21
22/// A hash set that preserves **insertion order** and exposes a
23/// [`VecDeque`]-like API with [`insert_back`], [`insert_front`],
24/// [`pop_front`], and [`pop_back`].
25///
26/// Implemented as a thin wrapper around [`LinkedHashMap<T, ()>`].
27///
28/// Elements require only [`Hash`] + [`Eq`].  They do **not** need to be
29/// [`Clone`] or [`Copy`] — including heap-owning types such as `String`,
30/// `Vec<T>`, or `Box<T>`.
31///
32/// ## Ordering contract
33///
34/// `insert_back` and `insert_front` on an element that **already exists**
35/// are a **no-op** - the element keeps its current position.  Use
36/// [`move_to_back`] / [`move_to_front`] to explicitly reorder an element.
37///
38/// ## Example
39///
40/// ```rust
41/// use linked_hash_table::LinkedHashSet;
42///
43/// let mut s = LinkedHashSet::new();
44/// s.insert_back("a");
45/// s.insert_back("b");
46/// s.insert_back("c");
47/// assert_eq!(s.pop_front(), Some("a"));
48/// assert_eq!(s.pop_back(),  Some("c"));
49/// ```
50///
51/// [`VecDeque`]: std::collections::VecDeque
52/// [`insert_back`]: LinkedHashSet::insert_back
53/// [`insert_front`]: LinkedHashSet::insert_front
54/// [`move_to_back`]: LinkedHashSet::move_to_back
55/// [`move_to_front`]: LinkedHashSet::move_to_front
56pub struct LinkedHashSet<T, S = RandomState> {
57    map: LinkedHashMap<T, (), S>,
58}
59
60impl<T> LinkedHashSet<T> {
61    /// Creates an empty `LinkedHashSet`.
62    pub fn new() -> Self {
63        Self {
64            map: LinkedHashMap::new(),
65        }
66    }
67
68    /// Creates an empty `LinkedHashSet` with the specified initial capacity.
69    pub fn with_capacity(capacity: usize) -> Self {
70        Self {
71            map: LinkedHashMap::with_capacity(capacity),
72        }
73    }
74}
75
76impl<T, S> LinkedHashSet<T, S> {
77    /// Creates an empty `LinkedHashSet` using the supplied hasher builder.
78    pub fn with_hasher(hash_builder: S) -> Self {
79        Self {
80            map: LinkedHashMap::with_hasher(hash_builder),
81        }
82    }
83
84    /// Creates an empty `LinkedHashSet` with the given capacity and hasher.
85    pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
86        Self {
87            map: LinkedHashMap::with_capacity_and_hasher(capacity, hash_builder),
88        }
89    }
90
91    /// Returns the number of elements in the set.
92    #[inline]
93    pub fn len(&self) -> usize {
94        self.map.len()
95    }
96
97    /// Returns `true` if the set contains no elements.
98    #[inline]
99    pub fn is_empty(&self) -> bool {
100        self.map.is_empty()
101    }
102
103    /// Returns the number of elements the set can hold without reallocating.
104    #[inline]
105    pub fn capacity(&self) -> usize {
106        self.map.capacity()
107    }
108
109    /// Returns a reference to the set's [`BuildHasher`].
110    #[inline]
111    pub fn hasher(&self) -> &S {
112        self.map.hasher()
113    }
114}
115
116impl<T, S> LinkedHashSet<T, S>
117where
118    T: Hash + Eq,
119    S: BuildHasher,
120{
121    /// Inserts `value` at the **back** (most-recently-inserted end).
122    ///
123    /// Returns `true` if the value was newly inserted.  If the value already
124    /// exists its position is **preserved** (no-op) and `false` is returned.
125    pub fn insert_back(&mut self, value: T) -> bool {
126        self.map.insert_back(value, ()).is_none()
127    }
128
129    /// Inserts `value` at the **front** (least-recently-inserted end).
130    ///
131    /// Returns `true` if the value was newly inserted.  If the value already
132    /// exists its position is **preserved** (no-op) and `false` is returned.
133    pub fn insert_front(&mut self, value: T) -> bool {
134        self.map.insert_front(value, ()).is_none()
135    }
136
137    /// Alias for [`insert_back`] - matches the [`HashSet::insert`] signature.
138    ///
139    /// [`insert_back`]: LinkedHashSet::insert_back
140    /// [`HashSet::insert`]: std::collections::HashSet::insert
141    #[inline]
142    pub fn insert(&mut self, value: T) -> bool {
143        self.insert_back(value)
144    }
145
146    /// Returns `true` if the set contains `value`.
147    #[inline]
148    pub fn contains<Q>(&self, value: &Q) -> bool
149    where
150        T: Borrow<Q>,
151        Q: Hash + Eq + ?Sized,
152    {
153        self.map.contains_key(value)
154    }
155
156    /// Returns a reference to the element in the set that equals `value`,
157    /// or `None` if it is not present.
158    pub fn get<Q>(&self, value: &Q) -> Option<&T>
159    where
160        T: Borrow<Q>,
161        Q: Hash + Eq + ?Sized,
162    {
163        self.map.get_key_value(value).map(|(k, _)| k)
164    }
165
166    /// Returns a reference to the **front** (oldest) element, or `None` if
167    /// the set is empty.
168    pub fn front(&self) -> Option<&T> {
169        self.map.front().map(|(k, _)| k)
170    }
171
172    /// Returns a reference to the **back** (most recently inserted) element,
173    /// or `None` if the set is empty.
174    pub fn back(&self) -> Option<&T> {
175        self.map.back().map(|(k, _)| k)
176    }
177
178    /// Removes and returns the **front** (oldest) element, or `None`.
179    pub fn pop_front(&mut self) -> Option<T> {
180        self.map.pop_front().map(|(k, _)| k)
181    }
182
183    /// Removes and returns the **back** (newest) element, or `None`.
184    pub fn pop_back(&mut self) -> Option<T> {
185        self.map.pop_back().map(|(k, _)| k)
186    }
187
188    /// Removes `value` from the set.
189    /// Returns `true` if the element was present.
190    pub fn remove<Q>(&mut self, value: &Q) -> bool
191    where
192        T: Borrow<Q>,
193        Q: Hash + Eq + ?Sized,
194    {
195        self.map.remove(value).is_some()
196    }
197
198    /// Removes the element equal to `value` and returns it, if present.
199    pub fn take<Q>(&mut self, value: &Q) -> Option<T>
200    where
201        T: Borrow<Q>,
202        Q: Hash + Eq + ?Sized,
203    {
204        self.map.remove_entry(value).map(|(k, _)| k)
205    }
206
207    /// Retains only the elements for which `f` returns `true`.
208    /// Elements are visited in **insertion order** (front → back).
209    pub fn retain<F>(&mut self, mut f: F)
210    where
211        F: FnMut(&T) -> bool,
212    {
213        self.map.retain(|k, _| f(k));
214    }
215
216    /// Removes all elements from the set.
217    pub fn clear(&mut self) {
218        self.map.clear();
219    }
220
221    /// Moves `value` to the **back** of the ordering.
222    /// Returns `true` if the element was found.
223    pub fn move_to_back<Q>(&mut self, value: &Q) -> bool
224    where
225        T: Borrow<Q>,
226        Q: Hash + Eq + ?Sized,
227    {
228        self.map.move_to_back(value)
229    }
230
231    /// Moves `value` to the **front** of the ordering.
232    /// Returns `true` if the element was found.
233    pub fn move_to_front<Q>(&mut self, value: &Q) -> bool
234    where
235        T: Borrow<Q>,
236        Q: Hash + Eq + ?Sized,
237    {
238        self.map.move_to_front(value)
239    }
240
241    /// Removes all elements in **insertion order**, returning them via an
242    /// iterator.  The set is empty after this call (even if the iterator is
243    /// dropped before it is fully consumed).
244    pub fn drain(&mut self) -> SetDrain<'_, T> {
245        SetDrain {
246            inner: self.map.drain(),
247        }
248    }
249
250    /// Returns `true` if every element of `self` is also contained in `other`.
251    pub fn is_subset<S2: BuildHasher>(&self, other: &LinkedHashSet<T, S2>) -> bool {
252        self.len() <= other.len() && self.iter().all(|v| other.contains(v))
253    }
254
255    /// Returns `true` if every element of `other` is also contained in `self`.
256    pub fn is_superset<S2: BuildHasher>(&self, other: &LinkedHashSet<T, S2>) -> bool {
257        other.is_subset(self)
258    }
259
260    /// Returns `true` if `self` and `other` share no elements.
261    pub fn is_disjoint<S2: BuildHasher>(&self, other: &LinkedHashSet<T, S2>) -> bool {
262        if self.len() <= other.len() {
263            self.iter().all(|v| !other.contains(v))
264        } else {
265            other.iter().all(|v| !self.contains(v))
266        }
267    }
268}
269
270impl<T, S> LinkedHashSet<T, S> {
271    /// Returns an iterator over elements in **insertion order**.
272    pub fn iter<'a>(&'a self) -> SetIter<'a, T> {
273        SetIter {
274            inner: self.map.keys(),
275        }
276    }
277}
278
279impl<T> Default for LinkedHashSet<T> {
280    fn default() -> Self {
281        Self::new()
282    }
283}
284
285impl<T: fmt::Debug, S> fmt::Debug for LinkedHashSet<T, S> {
286    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
287        f.debug_set().entries(self.iter()).finish()
288    }
289}
290
291impl<T: PartialEq, S1, S2> PartialEq<LinkedHashSet<T, S2>> for LinkedHashSet<T, S1> {
292    /// Two sets are equal only when they contain **the same elements in the
293    /// same order**.
294    fn eq(&self, other: &LinkedHashSet<T, S2>) -> bool {
295        if self.len() != other.len() {
296            return false;
297        }
298        self.iter().zip(other.iter()).all(|(a, b)| a == b)
299    }
300}
301
302impl<T: PartialEq + Eq, S> Eq for LinkedHashSet<T, S> {}
303
304impl<T: Clone + Hash + Eq, S: BuildHasher + Clone> Clone for LinkedHashSet<T, S> {
305    fn clone(&self) -> Self {
306        let mut new_set = Self::with_capacity_and_hasher(self.len(), self.map.hasher().clone());
307        for v in self.iter() {
308            new_set.insert_back(v.clone());
309        }
310        new_set
311    }
312}
313
314impl<T: Hash + Eq> FromIterator<T> for LinkedHashSet<T> {
315    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
316        let iter = iter.into_iter();
317        let (lower, _) = iter.size_hint();
318        let mut set = Self::with_capacity(lower);
319        for v in iter {
320            set.insert_back(v);
321        }
322        set
323    }
324}
325
326impl<T: Hash + Eq, S: BuildHasher> Extend<T> for LinkedHashSet<T, S> {
327    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
328        for v in iter {
329            self.insert_back(v);
330        }
331    }
332}
333
334/// Consuming iterator: yields all elements in insertion order.
335impl<T, S> IntoIterator for LinkedHashSet<T, S> {
336    type Item = T;
337    type IntoIter = SetIntoIter<T>;
338
339    fn into_iter(self) -> SetIntoIter<T> {
340        SetIntoIter {
341            inner: self.map.into_iter(),
342        }
343    }
344}
345
346/// Shared-reference iterator: yields `&T` in insertion order.
347impl<'a, T, S> IntoIterator for &'a LinkedHashSet<T, S> {
348    type Item = &'a T;
349    type IntoIter = SetIter<'a, T>;
350
351    #[inline]
352    fn into_iter(self) -> SetIter<'a, T> {
353        self.iter()
354    }
355}
356
357/// Iterator over `&T` elements in insertion order.
358///
359/// Created by [`LinkedHashSet::iter`].
360pub struct SetIter<'a, T> {
361    inner: Keys<'a, T, ()>,
362}
363
364impl<'a, T> Iterator for SetIter<'a, T> {
365    type Item = &'a T;
366
367    #[inline]
368    fn next(&mut self) -> Option<&'a T> {
369        self.inner.next()
370    }
371
372    #[inline]
373    fn size_hint(&self) -> (usize, Option<usize>) {
374        self.inner.size_hint()
375    }
376}
377
378impl<'a, T> DoubleEndedIterator for SetIter<'a, T> {
379    #[inline]
380    fn next_back(&mut self) -> Option<&'a T> {
381        self.inner.next_back()
382    }
383}
384
385impl<T> ExactSizeIterator for SetIter<'_, T> {}
386
387/// Draining iterator - removes and yields every element in insertion order,
388/// leaving the set empty.
389///
390/// If the iterator is dropped before it is fully consumed, the remaining
391/// elements are freed and the set is left in a valid empty state.
392///
393/// Created by [`LinkedHashSet::drain`].
394pub struct SetDrain<'a, T> {
395    inner: MapDrain<'a, T, ()>,
396}
397
398impl<T> Iterator for SetDrain<'_, T> {
399    type Item = T;
400
401    #[inline]
402    fn next(&mut self) -> Option<T> {
403        self.inner.next().map(|(k, _)| k)
404    }
405
406    #[inline]
407    fn size_hint(&self) -> (usize, Option<usize>) {
408        self.inner.size_hint()
409    }
410}
411
412impl<T> ExactSizeIterator for SetDrain<'_, T> {}
413
414/// Consuming iterator - yields every element in insertion order.
415///
416/// Created by calling `.into_iter()` on a [`LinkedHashSet`].
417pub struct SetIntoIter<T> {
418    inner: MapIntoIter<T, ()>,
419}
420
421impl<T> Iterator for SetIntoIter<T> {
422    type Item = T;
423
424    #[inline]
425    fn next(&mut self) -> Option<T> {
426        self.inner.next().map(|(k, _)| k)
427    }
428
429    #[inline]
430    fn size_hint(&self) -> (usize, Option<usize>) {
431        self.inner.size_hint()
432    }
433}
434
435impl<T> ExactSizeIterator for SetIntoIter<T> {}
436
437#[cfg(not(coverage))]
438const _: () = {
439    /// `SetIter<'long, T>` is covariant in `'a` and `T`.
440    fn _check_set_iter<'long: 'short, 'short, T>(x: SetIter<'long, T>) -> SetIter<'short, T> {
441        x
442    }
443};
linked_hash_table/set.rs

linked_hash_table/
set.rs
