kempt/
set.rs

1use core::fmt::{self, Debug};
2
3use crate::map::{self, Field, OwnedOrRef};
4use crate::{Map, Sort};
5
6/// An iterator over the vakyes in a [`Set`].
7pub type Iter<'a, T> = map::Keys<'a, T, ()>;
8/// An iterator that converts a [`Set`] into its owned values.
9pub type IntoIter<T> = map::IntoKeys<T, ()>;
10
11/// An ordered collection of unique `T`s.
12///
13/// This data type only allows each unique value to be stored once.
14///
15/// ```rust
16/// use kempt::Set;
17///
18/// let mut set = Set::new();
19/// set.insert(1);
20/// assert!(!set.insert(1));
21/// assert_eq!(set.len(), 1);
22/// ```
23///
24/// The values in the collection are automatically sorted using `T`'s [`Ord`]
25/// implementation.
26///
27/// ```rust
28/// use kempt::Set;
29///
30/// let mut set = Set::new();
31/// set.insert(1);
32/// set.insert(3);
33/// set.insert(2);
34/// assert_eq!(set.member(0), Some(&1));
35/// assert_eq!(set.member(1), Some(&2));
36/// assert_eq!(set.member(2), Some(&3));
37/// ```
38#[derive(Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
39pub struct Set<T>(Map<T, ()>)
40where
41    T: Sort<T>;
42
43impl<T> Default for Set<T>
44where
45    T: Sort<T>,
46{
47    #[inline]
48    fn default() -> Self {
49        Self::new()
50    }
51}
52
53impl<T> Set<T>
54where
55    T: Sort<T>,
56{
57    /// Returns an empty set.
58    #[must_use]
59    #[inline]
60    pub const fn new() -> Self {
61        Self(Map::new())
62    }
63
64    /// Returns an empty set with enough allocated memory to store `capacity`
65    /// values without reallocating.
66    #[must_use]
67    #[inline]
68    pub fn with_capacity(capacity: usize) -> Self {
69        Self(Map::with_capacity(capacity))
70    }
71
72    /// Returns the current capacity this map can hold before it must
73    /// reallocate.
74    #[must_use]
75    #[inline]
76    pub fn capacity(&self) -> usize {
77        self.0.capacity()
78    }
79
80    /// Inserts or replaces `value` in the set, returning `true` if the
81    /// collection is modified. If a previously contained value returns
82    /// [`Ordering::Equal`](core::cmp::Ordering::Equal) from [`Ord::cmp`], the
83    /// collection will not be modified and `false` will be returned.
84    #[inline]
85    pub fn insert(&mut self, value: T) -> bool {
86        self.0.insert_with(value, || ()).is_none()
87    }
88
89    /// Inserts or replaces `value` in the set. If a previously contained value
90    /// returns [`Ordering::Equal`](core::cmp::Ordering::Equal) from
91    /// [`Ord::cmp`], the new value will overwrite the stored value and it will
92    /// be returned.
93    #[inline]
94    pub fn replace(&mut self, value: T) -> Option<T> {
95        self.0.insert(value, ()).map(|field| field.into_parts().0)
96    }
97
98    /// Returns true if the set contains a matching `value`.
99    #[inline]
100    pub fn contains<SearchFor>(&self, value: &SearchFor) -> bool
101    where
102        T: Sort<SearchFor>,
103        SearchFor: ?Sized,
104    {
105        self.0.contains(value)
106    }
107
108    /// Returns the contained value that matches `value`.
109    #[inline]
110    pub fn get<SearchFor>(&self, value: &SearchFor) -> Option<&T>
111    where
112        T: Sort<SearchFor>,
113        SearchFor: ?Sized,
114    {
115        self.0.get_field(value).map(Field::key)
116    }
117
118    /// Removes a value from the set, returning the value if it was removed.
119    #[inline]
120    pub fn remove<SearchFor>(&mut self, value: &SearchFor) -> Option<T>
121    where
122        T: Sort<SearchFor>,
123        SearchFor: ?Sized,
124    {
125        self.0.remove(value).map(|field| field.into_parts().0)
126    }
127
128    /// Returns the member at `index` inside of this ordered set. Returns `None`
129    /// if `index` is greater than or equal to the set's length.
130    #[inline]
131    pub fn member(&self, index: usize) -> Option<&T> {
132        self.0.field(index).map(Field::key)
133    }
134
135    /// Removes the member at `index`.
136    ///
137    /// # Panics
138    ///
139    /// A panic will occur if `index` is greater than or equal to the set's
140    /// length.
141    #[inline]
142    pub fn remove_member(&mut self, index: usize) -> T {
143        self.0.remove_by_index(index).into_key()
144    }
145
146    /// Returns the number of members in this set.
147    #[must_use]
148    #[inline]
149    pub fn len(&self) -> usize {
150        self.0.len()
151    }
152
153    /// Returns true if there are no members in this set.
154    #[must_use]
155    #[inline]
156    pub fn is_empty(&self) -> bool {
157        self.0.is_empty()
158    }
159
160    /// Returns an iterator over the members in this set.
161    #[must_use]
162    #[inline]
163    pub fn iter(&self) -> Iter<'_, T> {
164        self.into_iter()
165    }
166
167    /// Returns an iterator that yields a single reference to all members found
168    /// in either `self` or `other`.
169    ///
170    /// This iterator is guaranteed to return results in the sort order of the
171    /// `Key` type.
172    #[must_use]
173    #[inline]
174    pub fn union<'a>(&'a self, other: &'a Set<T>) -> Union<'a, T> {
175        Union(self.0.union(&other.0))
176    }
177
178    /// Returns an iterator that yields a single reference to all members found
179    /// in both `self` and `other`.
180    ///
181    /// This iterator is guaranteed to return results in the sort order of the
182    /// `Key` type.
183    #[must_use]
184    #[inline]
185    pub fn intersection<'a>(&'a self, other: &'a Set<T>) -> Intersection<'a, T> {
186        Intersection(self.0.intersection(&other.0))
187    }
188
189    /// Returns an iterator that yields a single reference to all members found
190    /// in `self` but not `other`.
191    ///
192    /// This iterator is guaranteed to return results in the sort order of the
193    /// `Key` type.
194    #[must_use]
195    #[inline]
196    pub fn difference<'a>(&'a self, other: &'a Set<T>) -> Difference<'a, T> {
197        Difference(self.0.difference(&other.0))
198    }
199
200    /// Returns an iterator over the contents of this set. After the iterator is
201    /// dropped, this set will be empty.
202    #[inline]
203    pub fn drain(&mut self) -> Drain<'_, T> {
204        Drain(self.0.drain())
205    }
206
207    /// Clears the contents of this collection.
208    ///
209    /// This does not return any allocated memory to the OS.
210    #[inline]
211    pub fn clear(&mut self) {
212        self.0.clear();
213    }
214
215    /// Resizes this collection to fit its contents exactly.
216    ///
217    /// This function will reallocate its internal storage to fit the contents
218    /// of this collection's current size. If the allocation is already the
219    /// correct size, this is a no-op.
220    #[inline]
221    pub fn shrink_to_fit(&mut self) {
222        self.0.shrink_to_fit();
223    }
224
225    /// Resizes this collection to be able to hold `min_capacity`.
226    ///
227    /// This function will reallocate its internal storage to fit the contents
228    /// of this collection's current size. If the allocation is already the
229    /// correct size, this is a no-op.
230    ///
231    /// If the length of this collection is larger than `min_capacity`, this
232    /// function will behave identically to
233    /// [`shrink_to_fit()`](Self::shrink_to_fit).
234    #[inline]
235    pub fn shrink_to(&mut self, min_capacity: usize) {
236        self.0.shrink_to(min_capacity);
237    }
238}
239
240impl<T> Debug for Set<T>
241where
242    T: Sort<T> + Debug,
243{
244    #[inline]
245    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
246        let mut s = f.debug_set();
247        for member in self {
248            s.entry(member);
249        }
250        s.finish()
251    }
252}
253
254impl<'a, T> IntoIterator for &'a Set<T>
255where
256    T: Sort<T>,
257{
258    type IntoIter = Iter<'a, T>;
259    type Item = &'a T;
260
261    #[inline]
262    fn into_iter(self) -> Self::IntoIter {
263        self.0.keys()
264    }
265}
266
267impl<T> FromIterator<T> for Set<T>
268where
269    T: Sort<T>,
270{
271    #[inline]
272    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
273        Self(iter.into_iter().map(|t| (t, ())).collect())
274    }
275}
276
277/// An iterator that yields a single reference to all members found in either
278/// [`Set`] being unioned.
279///
280/// This iterator is guaranteed to return results in the sort order of the `Key`
281/// type.
282pub struct Union<'a, T>(map::Union<'a, T, ()>)
283where
284    T: Sort<T>;
285
286impl<'a, T> Iterator for Union<'a, T>
287where
288    T: Sort<T>,
289{
290    type Item = &'a T;
291
292    #[inline]
293    fn next(&mut self) -> Option<Self::Item> {
294        self.0
295            .next()
296            .map(|unioned| unioned.map_both(|_, (), ()| OwnedOrRef::Owned(())).key)
297    }
298
299    #[inline]
300    fn size_hint(&self) -> (usize, Option<usize>) {
301        self.0.size_hint()
302    }
303}
304
305/// An iterator that yields a single reference to all members found in both
306/// [`Set`]s being intersected.
307///
308/// This iterator is guaranteed to return results in the sort order of the `Key`
309/// type.
310pub struct Intersection<'a, T>(map::Intersection<'a, T, ()>)
311where
312    T: Sort<T>;
313
314impl<'a, T> Iterator for Intersection<'a, T>
315where
316    T: Sort<T>,
317{
318    type Item = &'a T;
319
320    #[inline]
321    fn next(&mut self) -> Option<Self::Item> {
322        self.0.next().map(|(k, (), ())| k)
323    }
324
325    #[inline]
326    fn size_hint(&self) -> (usize, Option<usize>) {
327        self.0.size_hint()
328    }
329}
330
331/// An iterator that yields a single reference to all members found in one
332/// [`Set`], but not another.
333///
334/// This iterator is guaranteed to return results in the sort order of the `Key`
335/// type.
336pub struct Difference<'a, T>(map::Difference<'a, T, ()>)
337where
338    T: Sort<T>;
339
340impl<'a, T> Iterator for Difference<'a, T>
341where
342    T: Sort<T>,
343{
344    type Item = &'a T;
345
346    #[inline]
347    fn next(&mut self) -> Option<Self::Item> {
348        self.0.next().map(|(k, ())| k)
349    }
350
351    #[inline]
352    fn size_hint(&self) -> (usize, Option<usize>) {
353        self.0.size_hint()
354    }
355}
356
357/// An iterator that drains the contents of a [`Set`].
358///
359/// When this is dropped, the remaining contents are drained.
360pub struct Drain<'a, T>(map::Drain<'a, T, ()>);
361
362impl<T> Iterator for Drain<'_, T> {
363    type Item = T;
364
365    #[inline]
366    fn next(&mut self) -> Option<Self::Item> {
367        self.0.next().map(map::Field::into_key)
368    }
369}
370
371#[test]
372fn basics() {
373    let mut set = Set::default();
374    assert!(set.is_empty());
375    assert!(set.insert(1));
376    assert!(set.contains(&1));
377    assert_eq!(set.replace(1), Some(1));
378    assert!(set.insert(0));
379
380    assert_eq!(set.member(0), Some(&0));
381    assert_eq!(set.member(1), Some(&1));
382
383    assert_eq!(set.len(), 2);
384    assert_eq!(set.remove(&0), Some(0));
385    assert_eq!(set.len(), 1);
386    assert_eq!(set.remove(&1), Some(1));
387    assert_eq!(set.len(), 0);
388}
389
390#[test]
391fn union() {
392    use alloc::vec::Vec;
393    let a = [1, 3, 5].into_iter().collect::<Set<u8>>();
394    let b = [2, 3, 4].into_iter().collect::<Set<u8>>();
395    assert_eq!(a.union(&b).copied().collect::<Vec<_>>(), [1, 2, 3, 4, 5]);
396
397    let b = [2, 3, 6].into_iter().collect::<Set<u8>>();
398    assert_eq!(a.union(&b).copied().collect::<Vec<_>>(), [1, 2, 3, 5, 6]);
399}
400
401#[test]
402fn intersection() {
403    use alloc::vec::Vec;
404    let a = [1, 3, 5].into_iter().collect::<Set<u8>>();
405    let b = [2, 3, 4].into_iter().collect::<Set<u8>>();
406    assert_eq!(a.intersection(&b).copied().collect::<Vec<_>>(), [3]);
407
408    let b = [2, 3, 6].into_iter().collect::<Set<u8>>();
409    assert_eq!(a.intersection(&b).copied().collect::<Vec<_>>(), [3]);
410}
411
412#[test]
413fn difference() {
414    use alloc::vec::Vec;
415    let a = [1, 3, 5].into_iter().collect::<Set<u8>>();
416    let b = [2, 3, 4].into_iter().collect::<Set<u8>>();
417    assert_eq!(a.difference(&b).copied().collect::<Vec<_>>(), [1, 5]);
418
419    let b = [2, 5, 6].into_iter().collect::<Set<u8>>();
420    assert_eq!(a.difference(&b).copied().collect::<Vec<_>>(), [1, 3]);
421}
422
423#[test]
424fn lookup() {
425    let mut set = Set::with_capacity(1);
426    let key = alloc::string::String::from("hello");
427    let key_ptr = key.as_ptr();
428    set.insert(key);
429    assert_eq!(set.get("hello").unwrap().as_ptr(), key_ptr);
430}
431
432#[test]
433fn iteration() {
434    use alloc::vec::Vec;
435    let mut set = Set::with_capacity(3);
436    set.insert(1);
437    set.insert(3);
438    set.insert(2);
439    assert_eq!(set.iter().copied().collect::<Vec<_>>(), &[1, 2, 3]);
440}
kempt/set.rs

kempt/
set.rs
