weak_table/
ptr_weak_hash_set.rs

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

weak_table/
ptr_weak_hash_set.rs
