4 use super::map::SsoHashMap;
6 /// Small-storage-optimized implementation of a set.
8 /// Stores elements in a small array up to a certain length
9 /// and switches to `HashSet` when that length is exceeded.
11 // FIXME: Implements subset of HashSet API.
13 // Missing HashSet API:
16 // shrink_to (unstable)
17 // drain_filter (unstable)
19 // get_or_insert/get_or_insert_owned/get_or_insert_with (unstable)
20 // difference/symmetric_difference/intersection/union
21 // is_disjoint/is_subset/is_superset
22 // PartialEq/Eq (requires SsoHashMap implementation)
23 // BitOr/BitAnd/BitXor/Sub
25 pub struct SsoHashSet<T> {
26 map: SsoHashMap<T, ()>,
29 /// Adapter function used to return
30 /// result if SsoHashMap functions into
31 /// result SsoHashSet should return.
33 fn entry_to_key<K, V>((k, _v): (K, V)) -> K {
37 impl<T> SsoHashSet<T> {
38 /// Creates an empty `SsoHashSet`.
40 pub fn new() -> Self {
41 Self { map: SsoHashMap::new() }
44 /// Creates an empty `SsoHashSet` with the specified capacity.
46 pub fn with_capacity(cap: usize) -> Self {
47 Self { map: SsoHashMap::with_capacity(cap) }
50 /// Clears the set, removing all values.
52 pub fn clear(&mut self) {
56 /// Returns the number of elements the set can hold without reallocating.
58 pub fn capacity(&self) -> usize {
62 /// Returns the number of elements in the set.
64 pub fn len(&self) -> usize {
68 /// Returns `true` if the set contains no elements.
70 pub fn is_empty(&self) -> bool {
74 /// An iterator visiting all elements in arbitrary order.
75 /// The iterator element type is `&'a T`.
77 pub fn iter(&self) -> impl Iterator<Item = &T> {
81 /// Clears the set, returning all elements in an iterator.
83 pub fn drain(&mut self) -> impl Iterator<Item = T> + '_ {
84 self.map.drain().map(entry_to_key)
88 impl<T: Eq + Hash> SsoHashSet<T> {
89 /// Reserves capacity for at least `additional` more elements to be inserted
90 /// in the `SsoHashSet`. The collection may reserve more space to avoid
91 /// frequent reallocations.
93 pub fn reserve(&mut self, additional: usize) {
94 self.map.reserve(additional)
97 /// Shrinks the capacity of the set as much as possible. It will drop
98 /// down as much as possible while maintaining the internal rules
99 /// and possibly leaving some space in accordance with the resize policy.
101 pub fn shrink_to_fit(&mut self) {
102 self.map.shrink_to_fit()
105 /// Retains only the elements specified by the predicate.
107 pub fn retain<F>(&mut self, mut f: F)
109 F: FnMut(&T) -> bool,
111 self.map.retain(|k, _v| f(k))
114 /// Removes and returns the value in the set, if any, that is equal to the given one.
116 pub fn take(&mut self, value: &T) -> Option<T> {
117 self.map.remove_entry(value).map(entry_to_key)
120 /// Returns a reference to the value in the set, if any, that is equal to the given value.
122 pub fn get(&self, value: &T) -> Option<&T> {
123 self.map.get_key_value(value).map(entry_to_key)
126 /// Adds a value to the set.
128 /// Returns whether the value was newly inserted. That is:
130 /// - If the set did not previously contain this value, `true` is returned.
131 /// - If the set already contained this value, `false` is returned.
133 pub fn insert(&mut self, elem: T) -> bool {
134 self.map.insert(elem, ()).is_none()
137 /// Removes a value from the set. Returns whether the value was
138 /// present in the set.
140 pub fn remove(&mut self, value: &T) -> bool {
141 self.map.remove(value).is_some()
144 /// Returns `true` if the set contains a value.
146 pub fn contains(&self, value: &T) -> bool {
147 self.map.contains_key(value)
151 impl<T: Eq + Hash> FromIterator<T> for SsoHashSet<T> {
152 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> SsoHashSet<T> {
153 let mut set: SsoHashSet<T> = Default::default();
159 impl<T> Default for SsoHashSet<T> {
161 fn default() -> Self {
166 impl<T: Eq + Hash> Extend<T> for SsoHashSet<T> {
167 fn extend<I>(&mut self, iter: I)
169 I: IntoIterator<Item = T>,
171 for val in iter.into_iter() {
177 fn extend_one(&mut self, item: T) {
182 fn extend_reserve(&mut self, additional: usize) {
183 self.map.extend_reserve(additional)
187 impl<'a, T> Extend<&'a T> for SsoHashSet<T>
189 T: 'a + Eq + Hash + Copy,
192 fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
193 self.extend(iter.into_iter().cloned());
197 fn extend_one(&mut self, &item: &'a T) {
202 fn extend_reserve(&mut self, additional: usize) {
203 Extend::<T>::extend_reserve(self, additional)
207 impl<T> IntoIterator for SsoHashSet<T> {
208 type IntoIter = std::iter::Map<<SsoHashMap<T, ()> as IntoIterator>::IntoIter, fn((T, ())) -> T>;
209 type Item = <Self::IntoIter as Iterator>::Item;
212 fn into_iter(self) -> Self::IntoIter {
213 self.map.into_iter().map(entry_to_key)
217 impl<'a, T> IntoIterator for &'a SsoHashSet<T> {
218 type IntoIter = std::iter::Map<
219 <&'a SsoHashMap<T, ()> as IntoIterator>::IntoIter,
220 fn((&'a T, &'a ())) -> &'a T,
222 type Item = <Self::IntoIter as Iterator>::Item;
225 fn into_iter(self) -> Self::IntoIter {
226 self.map.iter().map(entry_to_key)
230 impl<T> fmt::Debug for SsoHashSet<T>
234 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
235 f.debug_set().entries(self.iter()).finish()