weak_table/
weak_hash_set.rs

1//! A hash set where the elements are held by weak pointers and compared by value.
2
3use crate::compat::*;
4
5use super::traits::*;
6use super::weak_key_hash_map as base;
7
8pub use super::WeakHashSet;
9
10impl <T: WeakKey> WeakHashSet<T, RandomState> {
11    /// Creates an empty `WeakHashSet`.
12    ///
13    /// *O*(1) time
14    pub fn new() -> Self {
15        WeakHashSet(base::WeakKeyHashMap::new())
16    }
17
18    /// Creates an empty `WeakHashSet` with the given capacity.
19    ///
20    /// *O*(*n*) time
21    pub fn with_capacity(capacity: usize) -> Self {
22        WeakHashSet(base::WeakKeyHashMap::with_capacity(capacity))
23    }
24}
25
26impl <T: WeakKey, S: BuildHasher> WeakHashSet<T, S> {
27    /// Creates an empty `WeakHashSet` with the given capacity and hasher.
28    ///
29    /// *O*(*n*) time
30    pub fn with_hasher(hash_builder: S) -> Self {
31        WeakHashSet(base::WeakKeyHashMap::with_hasher(hash_builder))
32    }
33
34    /// Creates an empty `WeakHashSet` with the given capacity and hasher.
35    ///
36    /// *O*(*n*) time
37    pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
38        WeakHashSet(base::WeakKeyHashMap::with_capacity_and_hasher(capacity, hash_builder))
39    }
40
41    /// Returns a reference to the map's `BuildHasher`.
42    ///
43    /// *O*(1) time
44    pub fn hasher(&self) -> &S {
45        self.0.hasher()
46    }
47
48    /// Returns the number of elements the map can hold without reallocating.
49    ///
50    /// *O*(1) time
51    pub fn capacity(&self) -> usize {
52        self.0.capacity()
53    }
54
55    /// Removes all mappings whose keys have expired.
56    ///
57    /// *O*(*n*) time
58    pub fn remove_expired(&mut self) {
59        self.0.remove_expired()
60    }
61
62    /// Reserves room for additional elements.
63    ///
64    /// *O*(*n*) time
65    pub fn reserve(&mut self, additional_capacity: usize) {
66        self.0.reserve(additional_capacity)
67    }
68
69    /// Shrinks the capacity to the minimum allowed to hold the current number of elements.
70    ///
71    /// *O*(*n*) time
72    pub fn shrink_to_fit(&mut self) {
73        self.0.shrink_to_fit()
74    }
75
76    /// Returns an over-approximation of the number of elements.
77    ///
78    /// *O*(1) time
79    pub fn len(&self) -> usize {
80        self.0.len()
81    }
82
83    /// Is the set empty?
84    ///
85    /// Note that this may return false even if all keys in the set have
86    /// expired, if they haven't been collected yet.
87    ///
88    /// *O*(1) time
89    pub fn is_empty(&self) -> bool {
90        self.0.is_empty()
91    }
92
93    /// The proportion of buckets that are used.
94    ///
95    /// This is an over-approximation because of expired elements.
96    ///
97    /// *O*(1) time
98    pub fn load_factor(&self) -> f32 {
99        self.0.load_factor()
100    }
101
102    /// Removes all associations from the map.
103    ///
104    /// *O*(*n*) time
105    pub fn clear(&mut self) {
106        self.0.clear()
107    }
108
109    // Non-ptr WeakHashSet should probably have `get` method.
110
111    /// Returns true if the map contains the specified key.
112    ///
113    /// expected *O*(1) time; worst-case *O*(*p*) time
114    pub fn contains<Q>(&self, key: &Q) -> bool
115        where Q: ?Sized + Eq + Hash,
116              T::Key: Borrow<Q>
117    {
118        self.0.contains_key(key)
119    }
120
121    /// Gets a strong reference to the given key, if found.
122    ///
123    /// # Examples
124    ///
125    /// ```
126    /// use weak_table::WeakHashSet;
127    /// use std::rc::{Rc, Weak};
128    /// use std::ops::Deref;
129    ///
130    /// let mut set: WeakHashSet<Weak<String>> = WeakHashSet::new();
131    ///
132    /// let a = Rc::new("a".to_owned());
133    /// set.insert(a.clone());
134    ///
135    /// let also_a = set.get("a").unwrap();
136    ///
137    /// assert!(Rc::ptr_eq( &a, &also_a ));
138    /// ```
139    ///
140    /// expected *O*(1) time; worst-case *O*(*p*) time
141    pub fn get<Q>(&self, key: &Q) -> Option<T::Strong>
142        where Q: ?Sized + Eq + Hash,
143              T::Key: Borrow<Q>
144    {
145        self.0.get_key(key)
146    }
147
148    /// Unconditionally inserts the value, returning the old value if already present. Does not
149    /// replace the key.
150    ///
151    /// expected *O*(1) time; worst-case *O*(*p*) time
152    pub fn insert(&mut self, key: T::Strong) -> bool {
153        self.0.insert(key, ()).is_some()
154    }
155
156    /// Removes the entry with the given key, if it exists, and returns the value.
157    ///
158    /// expected *O*(1) time; worst-case *O*(*p*) time
159    pub fn remove<Q>(&mut self, key: &Q) -> bool
160        where Q: ?Sized + Eq + Hash,
161              T::Key: Borrow<Q>
162    {
163        self.0.remove(key).is_some()
164    }
165
166    /// Removes all mappings not satisfying the given predicate.
167    ///
168    /// Also removes any expired mappings.
169    ///
170    /// *O*(*n*) time
171    pub fn retain<F>(&mut self, mut f: F)
172        where F: FnMut(T::Strong) -> bool
173    {
174        self.0.retain(|k, _| f(k))
175    }
176
177    /// Is self a subset of other?
178    ///
179    /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
180    /// `self.capacity()` and *q* is the length of the probe sequences
181    /// in `other`)
182    pub fn is_subset<S1>(&self, other: &WeakHashSet<T, S1>) -> bool
183        where S1: BuildHasher
184    {
185        self.0.domain_is_subset(&other.0)
186    }
187}
188
189/// An iterator over the elements of a set.
190pub struct Iter<'a, T: 'a>(base::Keys<'a, T, ()>);
191
192impl<'a, T: WeakElement> Iterator for Iter<'a, T> {
193    type Item = T::Strong;
194
195    fn next(&mut self) -> Option<Self::Item> {
196        self.0.next()
197    }
198
199    fn size_hint(&self) -> (usize, Option<usize>) {
200        self.0.size_hint()
201    }
202}
203
204/// An iterator over the elements of a set.
205pub struct IntoIter<T>(base::IntoIter<T, ()>);
206
207impl<T: WeakElement> Iterator for IntoIter<T> {
208    type Item = T::Strong;
209
210    fn next(&mut self) -> Option<Self::Item> {
211        self.0.next().map(|pair| pair.0)
212    }
213
214    fn size_hint(&self) -> (usize, Option<usize>) {
215        self.0.size_hint()
216    }
217}
218
219/// A draining iterator over the elements of a set.
220pub struct Drain<'a, T: 'a>(base::Drain<'a, T, ()>);
221
222impl<'a, T: WeakElement> Iterator for Drain<'a, T> {
223    type Item = T::Strong;
224
225    fn next(&mut self) -> Option<Self::Item> {
226        self.0.next().map(|pair| pair.0)
227    }
228
229    fn size_hint(&self) -> (usize, Option<usize>) {
230        self.0.size_hint()
231    }
232}
233
234impl<T: WeakKey, S> WeakHashSet<T, S> {
235    /// Gets an iterator over the keys and values.
236    ///
237    /// *O*(1) time
238    pub fn iter(&self) -> Iter<T> {
239        Iter(self.0.keys())
240    }
241
242    /// Gets a draining iterator, which removes all the values but retains the storage.
243    ///
244    /// *O*(1) time (and *O*(*n*) time to dispose of the result)
245    pub fn drain(&mut self) -> Drain<T> {
246        Drain(self.0.drain())
247    }
248}
249
250impl<T, S, S1> PartialEq<WeakHashSet<T, S1>> for WeakHashSet<T, S>
251    where T: WeakKey,
252          S: BuildHasher,
253          S1: BuildHasher
254{
255    fn eq(&self, other: &WeakHashSet<T, S1>) -> bool {
256        self.0 == other.0
257    }
258}
259
260impl<T: WeakKey, S: BuildHasher> Eq for WeakHashSet<T, S>
261    where T::Key: Eq
262{ }
263
264impl<T: WeakKey, S: BuildHasher + Default> Default for WeakHashSet<T, S> {
265    fn default() -> Self {
266        WeakHashSet(base::WeakKeyHashMap::<T, (), S>::default())
267    }
268}
269
270impl<T, S> FromIterator<T::Strong> for WeakHashSet<T, S>
271    where T: WeakKey,
272          S: BuildHasher + Default
273{
274    fn from_iter<I: IntoIterator<Item=T::Strong>>(iter: I) -> Self {
275        WeakHashSet(base::WeakKeyHashMap::<T, (), S>::from_iter(
276            iter.into_iter().map(|k| (k, ()))))
277    }
278}
279
280impl<T: WeakKey, S: BuildHasher> Extend<T::Strong> for WeakHashSet<T, S> {
281    fn extend<I: IntoIterator<Item=T::Strong>>(&mut self, iter: I) {
282        self.0.extend(iter.into_iter().map(|k| (k, ())))
283    }
284}
285
286impl<T: WeakKey, S> Debug for WeakHashSet<T, S>
287    where T::Strong: Debug
288{
289    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
290        self.0.fmt(f)
291    }
292}
293
294impl<T: WeakKey, S> IntoIterator for WeakHashSet<T, S> {
295    type Item = T::Strong;
296    type IntoIter = IntoIter<T>;
297
298    /// Creates an owning iterator from `self`.
299    ///
300    /// *O*(1) time (and *O*(*n*) time to dispose of the result)
301    fn into_iter(self) -> Self::IntoIter {
302        IntoIter(self.0.into_iter())
303    }
304}
305
306impl<'a, T: WeakKey, S> IntoIterator for &'a WeakHashSet<T, S> {
307    type Item = T::Strong;
308    type IntoIter = Iter<'a, T>;
309
310    /// Creates a borrowing iterator from `self`.
311    ///
312    /// *O*(1) time
313    fn into_iter(self) -> Self::IntoIter {
314        Iter(self.0.keys())
315    }
316}
weak_table/weak_hash_set.rs

weak_table/
weak_hash_set.rs
