wasmparser/collections/
index_set.rs

1//! Type definitions for an ordered set.
2
3use crate::collections::IndexMap;
4use core::{borrow::Borrow, hash::Hash, iter::FusedIterator, ops::Index};
5
6/// A default set of values.
7///
8/// Provides an API compatible with both [`IndexSet`] and a custom implementation based on [`BTreeMap`].
9///
10/// [`IndexSet`]: indexmap::IndexSet
11/// [`BTreeMap`]: alloc::collections::BTreeMap
12#[derive(Debug, Clone)]
13pub struct IndexSet<T> {
14    inner: IndexMap<T, ()>,
15}
16
17impl<T> Default for IndexSet<T> {
18    #[inline]
19    fn default() -> Self {
20        Self {
21            inner: IndexMap::default(),
22        }
23    }
24}
25
26impl<T> IndexSet<T> {
27    /// Clears the [`IndexSet`], removing all elements.
28    #[inline]
29    pub fn clear(&mut self) {
30        self.inner.clear()
31    }
32
33    /// Returns the number of elements in the [`IndexSet`].
34    #[inline]
35    pub fn len(&self) -> usize {
36        self.inner.len()
37    }
38
39    /// Returns `true` if the [`IndexSet`] contains no elements.
40    #[inline]
41    pub fn is_empty(&self) -> bool {
42        self.inner.is_empty()
43    }
44
45    /// Returns an iterator that yields the items in the [`IndexSet`].
46    #[inline]
47    pub fn iter(&self) -> Iter<'_, T> {
48        Iter {
49            inner: self.inner.iter(),
50        }
51    }
52}
53
54impl<T> IndexSet<T>
55where
56    T: Eq + Hash + Ord + Clone,
57{
58    /// Reserves capacity for at least `additional` more elements to be inserted in the [`IndexSet`].
59    #[inline]
60    pub fn reserve(&mut self, additional: usize) {
61        self.inner.reserve(additional);
62    }
63
64    /// Returns true if the [`IndexSet`] contains an element equal to the `value`.
65    #[inline]
66    pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool
67    where
68        T: Borrow<Q>,
69        Q: Hash + Eq + Ord,
70    {
71        self.inner.contains_key(value)
72    }
73
74    /// Returns a reference to the element in the [`IndexSet`], if any, that is equal to the `value`.
75    #[inline]
76    pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T>
77    where
78        T: Borrow<Q>,
79        Q: Hash + Eq + Ord,
80    {
81        self.inner.get_key_value(value).map(|(x, &())| x)
82    }
83
84    /// Return the index of the item provided, if it exists.
85    pub fn get_index_of<Q>(&self, value: &Q) -> Option<usize>
86    where
87        T: Borrow<Q>,
88        Q: Hash + Eq + Ord + ?Sized,
89    {
90        let (index, _, _) = self.inner.get_full(value)?;
91        Some(index)
92    }
93
94    /// Adds `value` to the [`IndexSet`].
95    ///
96    /// Returns whether the value was newly inserted:
97    ///
98    /// - Returns `true` if the set did not previously contain an equal value.
99    /// - Returns `false` otherwise and the entry is not updated.
100    #[inline]
101    pub fn insert(&mut self, value: T) -> bool {
102        self.inner.insert(value, ()).is_none()
103    }
104
105    /// Remove the value from the [`IndexSet`], and return `true` if it was present.
106    ///
107    /// Like [`Vec::swap_remove`], the value is removed by swapping it with the
108    /// last element of the set and popping it off. **This perturbs
109    /// the position of what used to be the last element!**
110    ///
111    /// Return `false` if `value` was not in the set.
112    ///
113    /// Computes in **O(1)** time (average).
114    ///
115    /// [`Vec::swap_remove`]: alloc::vec::Vec::swap_remove
116    #[inline]
117    pub fn swap_remove<Q: ?Sized>(&mut self, value: &Q) -> bool
118    where
119        T: Borrow<Q>,
120        Q: Hash + Eq + Ord,
121    {
122        self.inner.swap_remove(value).is_some()
123    }
124
125    /// Adds a value to the [`IndexSet`], replacing the existing value, if any, that is equal to the given
126    /// one. Returns the replaced value.
127    pub fn replace(&mut self, value: T) -> Option<T> {
128        let removed = self.inner.swap_remove_entry(&value);
129        self.inner.insert(value, ());
130        removed.map(|(key, _value)| key)
131    }
132
133    /// Returns `true` if `self` has no elements in common with `other`.
134    /// This is equivalent to checking for an empty intersection.
135    pub fn is_disjoint(&self, other: &Self) -> bool {
136        if self.len() <= other.len() {
137            self.iter().all(move |value| !other.contains(value))
138        } else {
139            other.iter().all(move |value| !self.contains(value))
140        }
141    }
142
143    /// Returns `true` if the [`IndexSet`] is a subset of another,
144    /// i.e., `other` contains at least all the values in `self`.
145    pub fn is_subset(&self, other: &Self) -> bool {
146        self.len() <= other.len() && self.iter().all(move |value| other.contains(value))
147    }
148
149    /// Returns `true` if the [`IndexSet`] is a superset of another,
150    /// i.e., `self` contains at least all the values in `other`.
151    #[inline]
152    pub fn is_superset(&self, other: &Self) -> bool {
153        other.is_subset(self)
154    }
155}
156
157impl<T> Index<usize> for IndexSet<T>
158where
159    T: Hash + Eq + Ord,
160{
161    type Output = T;
162
163    #[inline]
164    fn index(&self, index: usize) -> &T {
165        let Some((value, _)) = self.inner.get_index(index) else {
166            panic!("out of bounds index: {index}");
167        };
168        value
169    }
170}
171
172impl<T> FromIterator<T> for IndexSet<T>
173where
174    T: Hash + Eq + Ord + Clone,
175{
176    fn from_iter<I>(iter: I) -> Self
177    where
178        I: IntoIterator<Item = T>,
179    {
180        Self {
181            inner: <IndexMap<T, ()>>::from_iter(iter.into_iter().map(|value| (value, ()))),
182        }
183    }
184}
185
186impl<'a, T> IntoIterator for &'a IndexSet<T> {
187    type Item = &'a T;
188    type IntoIter = Iter<'a, T>;
189
190    #[inline]
191    fn into_iter(self) -> Self::IntoIter {
192        self.iter()
193    }
194}
195
196impl<T> Extend<T> for IndexSet<T>
197where
198    T: Hash + Eq + Ord + Clone,
199{
200    fn extend<Iter: IntoIterator<Item = T>>(&mut self, iter: Iter) {
201        self.inner.extend(iter.into_iter().map(|value| (value, ())))
202    }
203}
204
205/// An iterator over the items of a [`IndexSet`].
206#[derive(Debug, Clone)]
207pub struct Iter<'a, T> {
208    inner: <&'a IndexMap<T, ()> as IntoIterator>::IntoIter,
209}
210
211impl<'a, T> Iterator for Iter<'a, T> {
212    type Item = &'a T;
213
214    #[inline]
215    fn size_hint(&self) -> (usize, Option<usize>) {
216        self.inner.size_hint()
217    }
218
219    #[inline]
220    fn next(&mut self) -> Option<Self::Item> {
221        self.inner.next().map(|(key, _value)| key)
222    }
223}
224
225impl<'a, T> ExactSizeIterator for Iter<'a, T> {
226    #[inline]
227    fn len(&self) -> usize {
228        self.inner.len()
229    }
230}
231
232impl<'a, T> FusedIterator for Iter<'a, T> {}
233
234impl<T> IntoIterator for IndexSet<T> {
235    type Item = T;
236    type IntoIter = IntoIter<T>;
237
238    #[inline]
239    fn into_iter(self) -> Self::IntoIter {
240        IntoIter {
241            inner: self.inner.into_iter(),
242        }
243    }
244}
245
246/// An iterator over the owned items of an [`IndexSet`].
247#[derive(Debug)]
248pub struct IntoIter<T> {
249    inner: <IndexMap<T, ()> as IntoIterator>::IntoIter,
250}
251
252impl<T> Iterator for IntoIter<T> {
253    type Item = T;
254
255    #[inline]
256    fn size_hint(&self) -> (usize, Option<usize>) {
257        self.inner.size_hint()
258    }
259
260    #[inline]
261    fn next(&mut self) -> Option<Self::Item> {
262        self.inner.next().map(|(key, _value)| key)
263    }
264}
265
266impl<T> ExactSizeIterator for IntoIter<T> {
267    #[inline]
268    fn len(&self) -> usize {
269        self.inner.len()
270    }
271}
272
273impl<T> FusedIterator for IntoIter<T> {}
274
275#[cfg(feature = "serde")]
276impl<T> serde::Serialize for IndexSet<T>
277where
278    T: serde::Serialize + Eq + Hash + Ord,
279{
280    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
281    where
282        S: serde::ser::Serializer,
283    {
284        serde::Serialize::serialize(&self.inner, serializer)
285    }
286}
287
288#[cfg(feature = "serde")]
289impl<'a, T> serde::Deserialize<'a> for IndexSet<T>
290where
291    T: serde::Deserialize<'a> + Eq + Hash + Ord + Clone,
292{
293    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
294    where
295        D: serde::de::Deserializer<'a>,
296    {
297        Ok(IndexSet {
298            inner: serde::Deserialize::deserialize(deserializer)?,
299        })
300    }
301}
302
303impl<T> PartialEq for IndexSet<T>
304where
305    T: PartialEq + Hash + Ord,
306{
307    fn eq(&self, other: &Self) -> bool {
308        self.inner == other.inner
309    }
310
311    fn ne(&self, other: &Self) -> bool {
312        self.inner != other.inner
313    }
314}
315
316impl<T> Eq for IndexSet<T> where T: Eq + Hash + Ord {}
wasmparser/collections/index_set.rs

wasmparser/collections/
index_set.rs
