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

//! 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 core::{
    borrow::Borrow,
    fmt,
    hash::{Hash, Hasher},
};

use rancor::{Error, Fallible};

use crate::{
    collections::swiss_table::{
        index_map::Keys, ArchivedIndexMap, IndexMapResolver,
    },
    hash::FxHasher64,
    ser::{Allocator, Writer},
    Portable, Serialize,
};

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

impl<K, H> ArchivedIndexSet<K, H> {
    /// 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 number of elements in the index set.
    #[inline]
    pub fn len(&self) -> usize {
        self.inner.len()
    }
}

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

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

    /// Resolves an archived index map from a given length and parameters.
    ///
    /// # Safety
    ///
    /// `out` must point to a `Self` that properly aligned and valid for writes.
    #[inline]
    pub unsafe fn resolve_from_len(
        len: usize,
        load_factor: (usize, usize),
        pos: usize,
        resolver: IndexSetResolver,
        out: *mut Self,
    ) {
        let (fp, fo) = out_field!(out.inner);
        ArchivedIndexMap::resolve_from_len(
            len,
            load_factor,
            pos + fp,
            resolver.0,
            fo,
        );
    }

    /// Serializes an iterator of keys as an index set.
    #[inline]
    pub fn serialize_from_iter<'a, I, UK, S>(
        iter: I,
        load_factor: (usize, usize),
        serializer: &mut S,
    ) -> Result<IndexSetResolver, S::Error>
    where
        I: Clone + ExactSizeIterator<Item = &'a UK>,
        UK: 'a + Serialize<S, Archived = K> + Hash + Eq,
        S: Fallible + Writer + Allocator + ?Sized,
        S::Error: Error,
    {
        Ok(IndexSetResolver(
            ArchivedIndexMap::<K, (), H>::serialize_from_iter(
                iter.map(|x| (x, &())),
                load_factor,
                serializer,
            )?,
        ))
    }
}

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

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

impl<K: Eq, H> Eq for ArchivedIndexSet<K, H> {}

/// The resolver for archived index sets.
pub struct IndexSetResolver(IndexMapResolver);