flat_multimap/
set.rs

1#[cfg(feature = "rayon")]
2pub use crate::rayon::set as rayon;
3
4use crate::map::{self, FlatMultimap, IntoKeys, Keys};
5use hashbrown::TryReserveError;
6use std::borrow::Borrow;
7use std::collections::hash_map::RandomState;
8use std::fmt::{self, Debug};
9use std::hash::{BuildHasher, Hash};
10use std::iter::FusedIterator;
11
12/// Multiset implementation where items are stored as a flattened hash set.
13///
14/// # Examples
15///
16/// ```
17/// use flat_multimap::FlatMultiset;
18///
19/// let mut set = FlatMultiset::new();
20/// set.insert(1);
21/// set.insert(1);
22/// set.insert(2);
23///
24/// assert_eq!(set.len(), 3);
25/// ```
26#[derive(Clone)]
27pub struct FlatMultiset<T, S = RandomState> {
28    pub(crate) map: FlatMultimap<T, (), S>,
29}
30
31impl<T> FlatMultiset<T, RandomState> {
32    /// Creates an empty `FlatMultiset` with a capacity of 0,
33    /// so it will not allocate until it is first inserted into.
34    ///
35    /// # Examples
36    ///
37    /// ```
38    /// use flat_multimap::FlatMultiset;
39    ///
40    /// let mut set: FlatMultiset<i32> = FlatMultiset::new();
41    ///
42    /// assert_eq!(set.capacity(), 0);
43    /// ```
44    #[must_use]
45    pub fn new() -> Self {
46        Self {
47            map: FlatMultimap::new(),
48        }
49    }
50
51    /// Creates an empty `FlatMultiset` with at least the specified capacity.
52    #[must_use]
53    pub fn with_capacity(capacity: usize) -> Self {
54        Self {
55            map: FlatMultimap::with_capacity(capacity),
56        }
57    }
58}
59
60impl<T, S> FlatMultiset<T, S> {
61    /// Creates an empty `FlatMultiset` with default capacity which will use the given hash builder to hash keys.
62    pub const fn with_hasher(hash_builder: S) -> Self {
63        Self {
64            map: FlatMultimap::with_hasher(hash_builder),
65        }
66    }
67
68    /// Creates an empty `FlatMultiset` with at least the specified capacity, using the given hash builder to hash keys.
69    pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
70        Self {
71            map: FlatMultimap::with_capacity_and_hasher(capacity, hash_builder),
72        }
73    }
74
75    /// Returns the number of elements the map can hold without reallocating.
76    pub fn capacity(&self) -> usize {
77        self.map.capacity()
78    }
79
80    /// Returns a reference to the set's [`BuildHasher`].
81    pub const fn hasher(&self) -> &S {
82        self.map.hasher()
83    }
84
85    /// Returns the number of elements in the set.
86    pub fn len(&self) -> usize {
87        self.map.len()
88    }
89
90    /// Returns `true` if the set contains no elements.
91    pub fn is_empty(&self) -> bool {
92        self.map.is_empty()
93    }
94
95    /// Clears the set, returning all elements as an iterator.
96    pub fn drain(&mut self) -> Drain<'_, T> {
97        Drain {
98            iter: self.map.drain(),
99        }
100    }
101
102    /// Retains only the elements specified by the predicate.
103    pub fn retain<F>(&mut self, mut f: F)
104    where
105        F: FnMut(&T) -> bool,
106    {
107        self.map.retain(|k, _| f(k));
108    }
109
110    /// Clears the set, removing all values.
111    pub fn clear(&mut self) {
112        self.map.clear();
113    }
114
115    /// An iterator visiting all elements in arbitrary order. The iterator element type is `&'a T`.
116    pub fn iter(&self) -> Iter<'_, T> {
117        Iter {
118            iter: self.map.keys(),
119        }
120    }
121}
122
123impl<T, S> FlatMultiset<T, S>
124where
125    T: Eq + Hash,
126    S: BuildHasher,
127{
128    /// Reserves capacity for at least additional more elements to be inserted in the `FlatMultset`.
129    pub fn reserve(&mut self, additional: usize) {
130        self.map.reserve(additional);
131    }
132
133    /// Tries to reserve capacity for at least additional more elements to be inserted in the `FlatMultset`.
134    pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
135        self.map.try_reserve(additional)
136    }
137
138    /// Shrinks the capacity of the set as much as possible.
139    pub fn shrink_to_fit(&mut self) {
140        self.map.shrink_to_fit();
141    }
142
143    /// Shrinks the capacity of the set with a lower limit.
144    pub fn shrink_to(&mut self, min_capacity: usize) {
145        self.map.shrink_to(min_capacity);
146    }
147
148    /// Adds a value to the set.
149    pub fn insert(&mut self, value: T) {
150        self.map.insert(value, ());
151    }
152
153    /// Removes a value from the set. Returns whether the value was present in the set.
154    ///
155    /// # Examples
156    ///
157    /// ```
158    /// use flat_multimap::FlatMultiset;
159    ///
160    /// let mut set = FlatMultiset::new();
161    /// set.insert(1);
162    /// set.insert(1);
163    ///
164    /// assert!(set.remove(&1));
165    /// assert!(set.remove(&1));
166    /// assert!(!set.remove(&1));
167    /// ```
168    pub fn remove<Q>(&mut self, value: &Q) -> bool
169    where
170        T: Borrow<Q>,
171        Q: ?Sized + Hash + Eq,
172    {
173        self.map.remove(value).is_some()
174    }
175
176    /// Returns `true` if the set contains the value.
177    pub fn contains<Q>(&mut self, value: &Q) -> bool
178    where
179        T: Borrow<Q>,
180        Q: ?Sized + Hash + Eq,
181    {
182        self.map.contains_key(value)
183    }
184}
185
186impl<T, S> FromIterator<T> for FlatMultiset<T, S>
187where
188    T: Eq + Hash,
189    S: BuildHasher + Default,
190{
191    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
192        let mut set = Self::with_hasher(Default::default());
193        set.extend(iter);
194        set
195    }
196}
197
198impl<T, S> Extend<T> for FlatMultiset<T, S>
199where
200    T: Eq + Hash,
201    S: BuildHasher,
202{
203    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
204        self.map.extend(iter.into_iter().map(|k| (k, ())));
205    }
206}
207
208impl<'a, T, S> Extend<&'a T> for FlatMultiset<T, S>
209where
210    T: 'a + Eq + Hash + Copy,
211    S: BuildHasher,
212{
213    fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
214        self.extend(iter.into_iter().copied());
215    }
216}
217
218impl<'a, T, S> IntoIterator for &'a FlatMultiset<T, S> {
219    type Item = &'a T;
220    type IntoIter = Iter<'a, T>;
221
222    fn into_iter(self) -> Iter<'a, T> {
223        self.iter()
224    }
225}
226
227impl<T, S> IntoIterator for FlatMultiset<T, S> {
228    type Item = T;
229    type IntoIter = IntoIter<T>;
230
231    fn into_iter(self) -> IntoIter<T> {
232        IntoIter {
233            iter: self.map.into_keys(),
234        }
235    }
236}
237
238impl<T, S> Default for FlatMultiset<T, S>
239where
240    S: Default,
241{
242    fn default() -> Self {
243        FlatMultiset {
244            map: FlatMultimap::default(),
245        }
246    }
247}
248
249impl<T, S> Debug for FlatMultiset<T, S>
250where
251    T: Debug,
252{
253    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
254        f.debug_set().entries(self.iter()).finish()
255    }
256}
257
258impl<T, const N: usize> From<[T; N]> for FlatMultiset<T, RandomState>
259where
260    T: Eq + Hash,
261{
262    fn from(arr: [T; N]) -> Self {
263        arr.into_iter().collect()
264    }
265}
266
267/// A draining iterator over the items of a `FlatMultiset`.
268pub struct Drain<'a, T> {
269    iter: map::Drain<'a, T, ()>,
270}
271
272impl<T> Iterator for Drain<'_, T> {
273    type Item = T;
274
275    fn next(&mut self) -> Option<T> {
276        self.iter.next().map(|(v, _)| v)
277    }
278
279    fn size_hint(&self) -> (usize, Option<usize>) {
280        self.iter.size_hint()
281    }
282}
283
284impl<T> ExactSizeIterator for Drain<'_, T> {
285    fn len(&self) -> usize {
286        self.iter.len()
287    }
288}
289
290impl<T> FusedIterator for Drain<'_, T> {}
291
292impl<T: Debug> Debug for Drain<'_, T> {
293    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
294        let entries_iter = self.iter.iter().map(|(k, _)| k);
295        f.debug_list().entries(entries_iter).finish()
296    }
297}
298
299/// An iterator over the items of a `FlatMultiset`.
300pub struct Iter<'a, T> {
301    iter: Keys<'a, T, ()>,
302}
303
304impl<T> Clone for Iter<'_, T> {
305    fn clone(&self) -> Self {
306        Self {
307            iter: self.iter.clone(),
308        }
309    }
310}
311
312impl<'a, T> Iterator for Iter<'a, T> {
313    type Item = &'a T;
314
315    fn next(&mut self) -> Option<&'a T> {
316        self.iter.next()
317    }
318
319    fn size_hint(&self) -> (usize, Option<usize>) {
320        self.iter.size_hint()
321    }
322}
323
324impl<T> ExactSizeIterator for Iter<'_, T> {
325    fn len(&self) -> usize {
326        self.iter.len()
327    }
328}
329
330impl<T> FusedIterator for Iter<'_, T> {}
331
332impl<T: Debug> Debug for Iter<'_, T> {
333    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
334        f.debug_list().entries(self.clone()).finish()
335    }
336}
337
338/// An owning iterator over the items of a `FlatMultiset`.
339pub struct IntoIter<T> {
340    iter: IntoKeys<T, ()>,
341}
342
343impl<T> Iterator for IntoIter<T> {
344    type Item = T;
345
346    fn next(&mut self) -> Option<T> {
347        self.iter.next()
348    }
349
350    fn size_hint(&self) -> (usize, Option<usize>) {
351        self.iter.size_hint()
352    }
353}
354
355impl<T> ExactSizeIterator for IntoIter<T> {
356    fn len(&self) -> usize {
357        self.iter.len()
358    }
359}
360
361impl<T> FusedIterator for IntoIter<T> {}
362
363impl<T: Debug> Debug for IntoIter<T> {
364    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
365        f.debug_list().entries(self.iter.iter()).finish()
366    }
367}
flat_multimap/set.rs

flat_multimap/
set.rs
