rpds/set/red_black_tree_set/
mod.rs

1use crate::RedBlackTreeMap;
2use crate::map::red_black_tree_map;
3use archery::{ArcTK, RcK, SharedPointerKind};
4use core::borrow::Borrow;
5use core::cmp::Ordering;
6use core::fmt::Display;
7use core::hash::{Hash, Hasher};
8use core::iter::FromIterator;
9use core::ops::RangeBounds;
10
11// TODO Use impl trait instead of this when available.
12pub type Iter<'a, T, P> = red_black_tree_map::IterKeys<'a, T, (), P>;
13pub type RangeIter<'a, T, RB, Q, P> =
14    core::iter::Map<red_black_tree_map::RangeIter<'a, T, (), RB, Q, P>, fn((&'a T, &())) -> &'a T>;
15
16/// Creates a [`RedBlackTreeSet`](crate::RedBlackTreeSet) containing the given arguments:
17///
18/// ```
19/// # use rpds::*;
20/// #
21/// let s = RedBlackTreeSet::new()
22///     .insert(1)
23///     .insert(2)
24///     .insert(3);
25///
26/// assert_eq!(rbt_set![1, 2, 3], s);
27/// ```
28#[macro_export]
29macro_rules! rbt_set {
30    ($($e:expr),*) => {
31        {
32            #[allow(unused_mut)]
33            let mut s = $crate::RedBlackTreeSet::new();
34            $(
35                s.insert_mut($e);
36            )*
37            s
38        }
39    };
40}
41
42/// Creates a [`RedBlackTreeSet`](crate::RedBlackTreeSet) containing the given arguments:
43///
44/// ```
45/// # use rpds::*;
46/// #
47/// let s = RedBlackTreeSet::new_sync()
48///     .insert(1)
49///     .insert(2)
50///     .insert(3);
51///
52/// assert_eq!(rbt_set_sync![1, 2, 3], s);
53/// ```
54#[macro_export]
55macro_rules! rbt_set_sync {
56    ($($e:expr),*) => {
57        {
58            #[allow(unused_mut)]
59            let mut s = $crate::RedBlackTreeSet::new_sync();
60            $(
61                s.insert_mut($e);
62            )*
63            s
64        }
65    };
66}
67
68/// A persistent set with structural sharing.  This implementation uses a
69/// [red-black tree](https://en.wikipedia.org/wiki/Red-Black_tree).
70///
71/// # Complexity
72///
73/// Let *n* be the number of elements in the set.
74///
75/// ## Temporal complexity
76///
77/// | Operation                  | Average   | Worst case  |
78/// |:-------------------------- | ---------:| -----------:|
79/// | `new()`                    |      Θ(1) |        Θ(1) |
80/// | `insert()`                 | Θ(log(n)) |   Θ(log(n)) |
81/// | `remove()`                 | Θ(log(n)) |   Θ(log(n)) |
82/// | `get()`                    | Θ(log(n)) |   Θ(log(n)) |
83/// | `contains()`               | Θ(log(n)) |   Θ(log(n)) |
84/// | `size()`                   |      Θ(1) |        Θ(1) |
85/// | `clone()`                  |      Θ(1) |        Θ(1) |
86/// | iterator creation          | Θ(log(n)) |   Θ(log(n)) |
87/// | iterator step              |      Θ(1) |   Θ(log(n)) |
88/// | iterator full              |      Θ(n) |        Θ(n) |
89///
90/// # Implementation details
91///
92/// This is a thin wrapper around a [`RedBlackTreeMap`](crate::RedBlackTreeMap).
93#[derive(Debug)]
94pub struct RedBlackTreeSet<T, P = RcK>
95where
96    T: Ord,
97    P: SharedPointerKind,
98{
99    map: RedBlackTreeMap<T, (), P>,
100}
101
102pub type RedBlackTreeSetSync<T> = RedBlackTreeSet<T, ArcTK>;
103
104impl<T> RedBlackTreeSetSync<T>
105where
106    T: Ord,
107{
108    #[must_use]
109    pub fn new_sync() -> RedBlackTreeSetSync<T> {
110        RedBlackTreeSet::new_with_ptr_kind()
111    }
112}
113
114impl<T> RedBlackTreeSet<T>
115where
116    T: Ord,
117{
118    #[must_use]
119    pub fn new() -> RedBlackTreeSet<T> {
120        RedBlackTreeSet { map: RedBlackTreeMap::new_with_ptr_kind() }
121    }
122}
123
124impl<T, P> RedBlackTreeSet<T, P>
125where
126    T: Ord,
127    P: SharedPointerKind,
128{
129    #[must_use]
130    pub fn new_with_ptr_kind() -> RedBlackTreeSet<T, P> {
131        RedBlackTreeSet { map: RedBlackTreeMap::new_with_ptr_kind() }
132    }
133
134    #[must_use]
135    pub fn insert(&self, v: T) -> RedBlackTreeSet<T, P> {
136        RedBlackTreeSet { map: self.map.insert(v, ()) }
137    }
138
139    pub fn insert_mut(&mut self, v: T) {
140        self.map.insert_mut(v, ());
141    }
142
143    #[must_use]
144    pub fn remove<V: ?Sized>(&self, v: &V) -> RedBlackTreeSet<T, P>
145    where
146        T: Borrow<V>,
147        V: Ord,
148    {
149        RedBlackTreeSet { map: self.map.remove(v) }
150    }
151
152    pub fn remove_mut<V: ?Sized>(&mut self, v: &V) -> bool
153    where
154        T: Borrow<V>,
155        V: Ord,
156    {
157        self.map.remove_mut(v)
158    }
159
160    #[must_use]
161    pub fn get<V: ?Sized>(&self, v: &V) -> Option<&T>
162    where
163        T: Borrow<V>,
164        V: Ord,
165    {
166        self.map.get_key_value(v).map(|(k, ())| k)
167    }
168
169    #[must_use]
170    pub fn contains<V: ?Sized>(&self, v: &V) -> bool
171    where
172        T: Borrow<V>,
173        V: Ord,
174    {
175        self.map.contains_key(v)
176    }
177
178    #[must_use]
179    pub fn first(&self) -> Option<&T> {
180        self.map.first().map(|(k, ())| k)
181    }
182
183    #[must_use]
184    pub fn last(&self) -> Option<&T> {
185        self.map.last().map(|(k, ())| k)
186    }
187
188    #[must_use]
189    pub fn is_disjoint<PO>(&self, other: &RedBlackTreeSet<T, PO>) -> bool
190    where
191        PO: SharedPointerKind,
192    {
193        let mut self_it = self.iter();
194        let mut other_it = other.iter();
195
196        let mut v_opt = self_it.next();
197        let mut u_opt = other_it.next();
198
199        while let (Some(v), Some(u)) = (v_opt, u_opt) {
200            match v.cmp(u) {
201                Ordering::Less => v_opt = self_it.next(),
202                Ordering::Equal => return false,
203                Ordering::Greater => u_opt = other_it.next(),
204            }
205        }
206
207        true
208    }
209
210    /// Test whether the two sets refer to the same content in memory.
211    ///
212    /// This would return true if you’re comparing a set to itself,
213    /// or if you’re comparing a set to a fresh clone of itself.
214    fn ptr_eq<PO: SharedPointerKind>(&self, other: &RedBlackTreeSet<T, PO>) -> bool {
215        self.map.ptr_eq(&other.map)
216    }
217
218    #[must_use]
219    pub fn is_subset<PO>(&self, other: &RedBlackTreeSet<T, PO>) -> bool
220    where
221        PO: SharedPointerKind,
222    {
223        if self.ptr_eq(other) {
224            return true;
225        }
226        if self.size() > other.size() {
227            return false;
228        }
229        let mut other_it = other.iter();
230
231        for v in self {
232            loop {
233                match other_it.next() {
234                    Some(u) => match u.cmp(v) {
235                        Ordering::Less => (),
236                        Ordering::Equal => break,
237                        Ordering::Greater => return false,
238                    },
239                    None => return false,
240                }
241            }
242        }
243
244        true
245    }
246
247    #[must_use]
248    pub fn is_superset<PO>(&self, other: &RedBlackTreeSet<T, PO>) -> bool
249    where
250        PO: SharedPointerKind,
251    {
252        other.is_subset(self)
253    }
254
255    #[must_use]
256    #[inline]
257    pub fn size(&self) -> usize {
258        self.map.size()
259    }
260
261    #[must_use]
262    #[inline]
263    pub fn is_empty(&self) -> bool {
264        self.size() == 0
265    }
266
267    pub fn iter(&self) -> Iter<'_, T, P> {
268        self.map.keys()
269    }
270
271    pub fn range<Q, RB>(&self, range: RB) -> RangeIter<'_, T, RB, Q, P>
272    where
273        T: Borrow<Q>,
274        Q: Ord + ?Sized,
275        RB: RangeBounds<Q>,
276    {
277        self.map.range(range).map(|(k, ())| k)
278    }
279}
280
281impl<T, P> Clone for RedBlackTreeSet<T, P>
282where
283    T: Ord,
284    P: SharedPointerKind,
285{
286    fn clone(&self) -> RedBlackTreeSet<T, P> {
287        RedBlackTreeSet { map: self.map.clone() }
288    }
289}
290
291impl<T, P> Default for RedBlackTreeSet<T, P>
292where
293    T: Ord,
294    P: SharedPointerKind,
295{
296    fn default() -> RedBlackTreeSet<T, P> {
297        RedBlackTreeSet::new_with_ptr_kind()
298    }
299}
300
301impl<T, P, PO> PartialEq<RedBlackTreeSet<T, PO>> for RedBlackTreeSet<T, P>
302where
303    T: Ord,
304    P: SharedPointerKind,
305    PO: SharedPointerKind,
306{
307    fn eq(&self, other: &RedBlackTreeSet<T, PO>) -> bool {
308        self.map.eq(&other.map)
309    }
310}
311
312impl<T, P> Eq for RedBlackTreeSet<T, P>
313where
314    T: Ord,
315    P: SharedPointerKind,
316{
317}
318
319impl<T: Ord, P, PO> PartialOrd<RedBlackTreeSet<T, PO>> for RedBlackTreeSet<T, P>
320where
321    P: SharedPointerKind,
322    PO: SharedPointerKind,
323{
324    fn partial_cmp(&self, other: &RedBlackTreeSet<T, PO>) -> Option<Ordering> {
325        self.iter().partial_cmp(other.iter())
326    }
327}
328
329impl<T: Ord, P> Ord for RedBlackTreeSet<T, P>
330where
331    P: SharedPointerKind,
332{
333    fn cmp(&self, other: &RedBlackTreeSet<T, P>) -> Ordering {
334        self.iter().cmp(other.iter())
335    }
336}
337
338impl<T: Hash, P: SharedPointerKind> Hash for RedBlackTreeSet<T, P>
339where
340    T: Ord,
341{
342    fn hash<H: Hasher>(&self, state: &mut H) {
343        // Add the hash of length so that if two collections are added one after the other it
344        // doesn't hash to the same thing as a single collection with the same elements in the same
345        // order.
346        self.size().hash(state);
347
348        for e in self {
349            e.hash(state);
350        }
351    }
352}
353
354impl<T, P> Display for RedBlackTreeSet<T, P>
355where
356    T: Ord + Display,
357    P: SharedPointerKind,
358{
359    fn fmt(&self, fmt: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
360        let mut first = true;
361
362        fmt.write_str("{")?;
363
364        for v in self {
365            if !first {
366                fmt.write_str(", ")?;
367            }
368            v.fmt(fmt)?;
369            first = false;
370        }
371
372        fmt.write_str("}")
373    }
374}
375
376impl<'a, T, P> IntoIterator for &'a RedBlackTreeSet<T, P>
377where
378    T: Ord,
379    P: SharedPointerKind,
380{
381    type Item = &'a T;
382    type IntoIter = Iter<'a, T, P>;
383
384    fn into_iter(self) -> Iter<'a, T, P> {
385        self.iter()
386    }
387}
388
389// TODO This can be improved to create a perfectly balanced tree.
390impl<T, P> FromIterator<T> for RedBlackTreeSet<T, P>
391where
392    T: Ord,
393    P: SharedPointerKind,
394{
395    fn from_iter<I: IntoIterator<Item = T>>(into_iter: I) -> RedBlackTreeSet<T, P> {
396        let mut set = RedBlackTreeSet::new_with_ptr_kind();
397
398        for v in into_iter {
399            set.insert_mut(v);
400        }
401
402        set
403    }
404}
405
406#[cfg(feature = "serde")]
407pub mod serde {
408    use super::*;
409    use ::serde::de::{Deserialize, Deserializer, SeqAccess, Visitor};
410    use ::serde::ser::{Serialize, Serializer};
411    use core::fmt;
412    use core::marker::PhantomData;
413
414    impl<T, P> Serialize for RedBlackTreeSet<T, P>
415    where
416        T: Ord + Serialize,
417        P: SharedPointerKind,
418    {
419        fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
420            serializer.collect_seq(self)
421        }
422    }
423
424    impl<'de, T, P> Deserialize<'de> for RedBlackTreeSet<T, P>
425    where
426        T: Ord + Deserialize<'de>,
427        P: SharedPointerKind,
428    {
429        fn deserialize<D: Deserializer<'de>>(
430            deserializer: D,
431        ) -> Result<RedBlackTreeSet<T, P>, D::Error> {
432            deserializer.deserialize_seq(RedBlackTreeSetVisitor {
433                _phantom_t: PhantomData,
434                _phantom_p: PhantomData,
435            })
436        }
437    }
438
439    struct RedBlackTreeSetVisitor<T, P> {
440        _phantom_t: PhantomData<T>,
441        _phantom_p: PhantomData<P>,
442    }
443
444    impl<'de, T, P> Visitor<'de> for RedBlackTreeSetVisitor<T, P>
445    where
446        T: Ord + Deserialize<'de>,
447        P: SharedPointerKind,
448    {
449        type Value = RedBlackTreeSet<T, P>;
450
451        fn expecting(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
452            formatter.write_str("a sequence")
453        }
454
455        fn visit_seq<A>(self, mut seq: A) -> Result<RedBlackTreeSet<T, P>, A::Error>
456        where
457            A: SeqAccess<'de>,
458        {
459            let mut set = RedBlackTreeSet::new_with_ptr_kind();
460
461            while let Some(value) = seq.next_element()? {
462                set.insert_mut(value);
463            }
464
465            Ok(set)
466        }
467    }
468}
469
470#[cfg(test)]
471mod test;
rpds/set/red_black_tree_set/mod.rs

rpds/set/red_black_tree_set/
mod.rs
