rkyv/collections/btree/
set.rs

1//! [`Archive`](crate::Archive) implementation for B-tree sets.
2
3use core::{borrow::Borrow, fmt, ops::ControlFlow};
4
5use munge::munge;
6use rancor::{Fallible, Source};
7
8use crate::{
9    collections::btree_map::{ArchivedBTreeMap, BTreeMapResolver},
10    ser::{Allocator, Writer},
11    Place, Portable, Serialize,
12};
13
14/// An archived `BTreeSet`. This is a wrapper around a B-tree map with the same
15/// key and a value of `()`.
16#[cfg_attr(feature = "bytecheck", derive(bytecheck::CheckBytes))]
17#[derive(Portable)]
18#[rkyv(crate)]
19#[repr(transparent)]
20pub struct ArchivedBTreeSet<K, const E: usize = 5>(ArchivedBTreeMap<K, (), E>);
21
22impl<K, const E: usize> ArchivedBTreeSet<K, E> {
23    /// Returns `true` if the set contains a value for the specified key.
24    ///
25    /// The key may be any borrowed form of the set's key type, but the ordering
26    /// on the borrowed form _must_ match the ordering on the key type.
27    pub fn contains_key<Q: Ord + ?Sized>(&self, key: &Q) -> bool
28    where
29        K: Borrow<Q> + Ord,
30    {
31        self.0.contains_key(key)
32    }
33
34    /// Returns a reference to the value in the set, if any, that is equal to
35    /// the given value.
36    ///
37    /// The value may be any borrowed form of the set's value type, but the
38    /// ordering on the borrowed form _must_ match the ordering on the value
39    /// type.
40    pub fn get<Q: Ord + ?Sized>(&self, value: &Q) -> Option<&K>
41    where
42        K: Borrow<Q> + Ord,
43    {
44        self.0.get_key_value(value).map(|(key, _)| key)
45    }
46
47    /// Returns `true` if the set contains no elements.
48    pub fn is_empty(&self) -> bool {
49        self.0.is_empty()
50    }
51
52    /// Returns the number of items in the archived B-tree set.
53    pub fn len(&self) -> usize {
54        self.0.len()
55    }
56
57    /// Resolves a B-tree set from its length.
58    pub fn resolve_from_len(
59        len: usize,
60        resolver: BTreeSetResolver,
61        out: Place<Self>,
62    ) {
63        munge!(let ArchivedBTreeSet(inner) = out);
64        ArchivedBTreeMap::<K, (), E>::resolve_from_len(len, resolver.0, inner);
65    }
66
67    /// Serializes an `ArchivedBTreeSet` from the given iterator and serializer.
68    pub fn serialize_from_ordered_iter<I, KU, S>(
69        iter: I,
70        serializer: &mut S,
71    ) -> Result<BTreeSetResolver, S::Error>
72    where
73        I: ExactSizeIterator,
74        I::Item: Borrow<KU>,
75        KU: Serialize<S, Archived = K>,
76        S: Fallible + Allocator + Writer + ?Sized,
77        S::Error: Source,
78    {
79        ArchivedBTreeMap::<K, (), E>::serialize_from_ordered_iter::<
80            _,
81            _,
82            _,
83            _,
84            (),
85            _,
86        >(iter.map(|k| (k, &())), serializer)
87        .map(BTreeSetResolver)
88    }
89
90    /// Visits every key in the B-tree with a function.
91    ///
92    /// If `f` returns `ControlFlow::Break`, `visit` will return `Some` with the
93    /// broken value. If `f` returns `Continue` for every key in the tree,
94    /// `visit` will return `None`.
95    pub fn visit<T>(
96        &self,
97        mut f: impl FnMut(&K) -> ControlFlow<T>,
98    ) -> Option<T> {
99        self.0.visit(|k, _| f(k))
100    }
101}
102
103impl<K, const E: usize> fmt::Debug for ArchivedBTreeSet<K, E>
104where
105    K: fmt::Debug,
106{
107    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
108        let mut set = f.debug_set();
109        self.visit(|k| {
110            set.entry(k);
111            ControlFlow::<()>::Continue(())
112        });
113        set.finish()
114    }
115}
116
117/// The resolver for archived B-tree sets.
118pub struct BTreeSetResolver(BTreeMapResolver);
119
120#[cfg(feature = "alloc")]
121mod iter {
122    use core::iter::FusedIterator;
123
124    use super::ArchivedBTreeSet;
125    use crate::collections::btree_map;
126
127    pub struct Iter<'a, K, const E: usize> {
128        inner: btree_map::Keys<'a, K, (), E>,
129    }
130
131    impl<'a, K, const E: usize> Iterator for Iter<'a, K, E> {
132        type Item = &'a K;
133
134        fn next(&mut self) -> Option<Self::Item> {
135            self.inner.next()
136        }
137    }
138
139    impl<'a, K, const E: usize> ExactSizeIterator for Iter<'a, K, E> {}
140
141    impl<'a, K, const E: usize> FusedIterator for Iter<'a, K, E> {}
142
143    impl<K, const E: usize> ArchivedBTreeSet<K, E> {
144        /// Returns an iterator over the items of the archived B-tree set.
145        pub fn iter(&self) -> Iter<'_, K, E> {
146            Iter {
147                inner: self.0.keys(),
148            }
149        }
150    }
151}
rkyv/collections/btree/set.rs

rkyv/collections/btree/
set.rs
