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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174

//! Archived index set implementation.
//!
//! During archiving, index sets are built into minimal perfect index sets using
//! [compress, hash and displace](http://cmph.sourceforge.net/papers/esa09.pdf).

use crate::{
    collections::{
        hash_index::HashBuilder,
        index_map::{ArchivedIndexMap, IndexMapResolver, Keys},
    },
    out_field,
};
use core::{borrow::Borrow, fmt, hash::Hash};

/// An archived `IndexSet`.
#[cfg_attr(feature = "validation", derive(bytecheck::CheckBytes))]
#[repr(transparent)]
pub struct ArchivedIndexSet<K> {
    inner: ArchivedIndexMap<K, ()>,
}

impl<K> ArchivedIndexSet<K> {
    /// Returns whether a key is present in the hash set.
    #[inline]
    pub fn contains<Q: ?Sized>(&self, k: &Q) -> bool
    where
        K: Borrow<Q>,
        Q: Hash + Eq,
    {
        self.inner.contains_key(k)
    }

    /// Returns the first key.
    #[inline]
    pub fn first(&self) -> Option<&K> {
        self.inner.first().map(|(k, _)| k)
    }

    /// Returns the value stored in the set, if any.
    #[inline]
    pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&K>
    where
        K: Borrow<Q>,
        Q: Hash + Eq,
    {
        self.inner.get_full(k).map(|(_, k, _)| k)
    }

    /// Returns the item index and value stored in the set, if any.
    #[inline]
    pub fn get_full<Q: ?Sized>(&self, k: &Q) -> Option<(usize, &K)>
    where
        K: Borrow<Q>,
        Q: Hash + Eq,
    {
        self.inner.get_full(k).map(|(i, k, _)| (i, k))
    }

    /// Gets a key by index.
    #[inline]
    pub fn get_index(&self, index: usize) -> Option<&K> {
        self.inner.get_index(index).map(|(k, _)| k)
    }

    /// Returns the index of a key if it exists in the set.
    #[inline]
    pub fn get_index_of<Q: ?Sized>(&self, key: &Q) -> Option<usize>
    where
        K: Borrow<Q>,
        Q: Hash + Eq,
    {
        self.inner.get_index_of(key)
    }

    /// Gets the hasher for this index set.
    #[inline]
    pub fn hasher(&self) -> HashBuilder {
        self.inner.hasher()
    }

    /// Returns whether the index set contains no values.
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.inner.is_empty()
    }

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

    /// Returns the last key.
    #[inline]
    pub fn last(&self) -> Option<&K> {
        self.inner.last().map(|(k, _)| k)
    }

    /// Returns the number of elements in the index set.
    #[inline]
    pub fn len(&self) -> usize {
        self.inner.len()
    }

    /// Resolves an archived index map from a given length and parameters.
    ///
    /// # 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 hash map
    #[inline]
    pub unsafe fn resolve_from_len(
        len: usize,
        pos: usize,
        resolver: IndexSetResolver,
        out: *mut Self,
    ) {
        let (fp, fo) = out_field!(out.inner);
        ArchivedIndexMap::resolve_from_len(len, pos + fp, resolver.0, fo);
    }
}

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

    impl<K> ArchivedIndexSet<K> {
        /// Serializes an iterator of keys as an index set.
        ///
        /// # Safety
        ///
        /// - The keys returned by the iterator must be unique
        /// - The index function must return the index of the given key within the iterator
        #[inline]
        pub unsafe fn serialize_from_iter_index<'a, UK, I, F, S>(
            iter: I,
            index: F,
            serializer: &mut S,
        ) -> Result<IndexSetResolver, S::Error>
        where
            UK: 'a + Hash + Eq + Serialize<S, Archived = K>,
            I: Clone + ExactSizeIterator<Item = &'a UK>,
            F: Fn(&UK) -> usize,
            S: ScratchSpace + Serializer + ?Sized,
        {
            Ok(IndexSetResolver(
                ArchivedIndexMap::serialize_from_iter_index(
                    iter.map(|k| (k, &())),
                    index,
                    serializer,
                )?,
            ))
        }
    }
};

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

impl<K: PartialEq> PartialEq for ArchivedIndexSet<K> {
    fn eq(&self, other: &Self) -> bool {
        self.iter().eq(other.iter())
    }
}

/// The resolver for `IndexSet`.
pub struct IndexSetResolver(IndexMapResolver);