1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

//! [`Archive`](crate::Archive) implementation for B-tree sets.

use crate::collections::btree_map::{ArchivedBTreeMap, BTreeMapResolver, Keys};
use core::{borrow::Borrow, fmt};

/// An archived `BTreeSet`. This is a wrapper around a B-tree map with the same key and a value of
/// `()`.
#[cfg_attr(feature = "validation", derive(bytecheck::CheckBytes))]
#[derive(Eq, Hash, Ord, PartialEq, PartialOrd)]
#[repr(transparent)]
pub struct ArchivedBTreeSet<K>(ArchivedBTreeMap<K, ()>);

impl<K> ArchivedBTreeSet<K> {
    /// Returns `true` if the set contains a value for the specified key.
    ///
    /// The key may be any borrowed form of the set's key type, but the ordering on the borrowed
    /// form _must_ match the ordering on the key type.
    #[inline]
    pub fn contains_key<Q: Ord + ?Sized>(&self, key: &Q) -> bool
    where
        K: Borrow<Q> + Ord,
    {
        self.0.contains_key(key)
    }

    /// Returns a reference to the value int he set, if any, that is equal to the given value.
    ///
    /// The value may be any borrowed form of the set's value type, but the ordering on the borrowed
    /// form _must_ match the ordering on the value type.
    #[inline]
    pub fn get<Q: Ord + ?Sized>(&self, value: &Q) -> Option<&K>
    where
        K: Borrow<Q> + Ord,
    {
        self.0.get_key_value(value).map(|(key, _)| key)
    }

    /// Returns `true` if the set contains no elements.
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.0.is_empty()
    }

    /// Gets an iterator over the keys of the set, in sorted order.
    #[inline]
    pub fn iter(&self) -> Keys<K, ()> {
        self.0.keys()
    }

    /// Returns the number of items in the archived B-tree set.
    #[inline]
    pub fn len(&self) -> usize {
        self.0.len()
    }

    /// Resolves a B-tree set from its length.
    ///
    /// # Safety
    ///
    /// - `len` must be the number of elements that were serialized
    /// - `pos` must be the position of `out` within the archive
    /// - `resolver` must be the result of serializing a B-tree set
    #[inline]
    pub unsafe fn resolve_from_len(
        len: usize,
        pos: usize,
        resolver: BTreeSetResolver,
        out: *mut Self,
    ) {
        let (fp, fo) = out_field!(out.0);
        ArchivedBTreeMap::resolve_from_len(len, pos + fp, resolver.0, fo);
    }
}

#[cfg(feature = "alloc")]
const _: () = {
    use crate::{ser::Serializer, Serialize};

    impl<K> ArchivedBTreeSet<K> {
        /// Serializes an ordered iterator of key-value pairs as a B-tree map.
        ///
        /// # Safety
        ///
        /// - Keys returned by the iterator must be unique
        /// - Keys must be in reverse sorted order from last to first
        pub unsafe fn serialize_from_reverse_iter<'a, UK, S, I>(
            iter: I,
            serializer: &mut S,
        ) -> Result<BTreeSetResolver, S::Error>
        where
            UK: 'a + Serialize<S, Archived = K>,
            S: Serializer + ?Sized,
            I: ExactSizeIterator<Item = &'a UK>,
        {
            Ok(BTreeSetResolver(
                ArchivedBTreeMap::serialize_from_reverse_iter(iter.map(|x| (x, &())), serializer)?,
            ))
        }
    }
};

impl<K: fmt::Debug> fmt::Debug for ArchivedBTreeSet<K> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_set().entries(self.iter()).finish()
    }
}

impl<'a, K> IntoIterator for &'a ArchivedBTreeSet<K> {
    type Item = &'a K;
    type IntoIter = Keys<'a, K, ()>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

/// The resolver for archived B-tree sets.
pub struct BTreeSetResolver(BTreeMapResolver);