indexmap_nostd/
set.rs

1//! An ordered set based on a B-Tree that keeps insertion order of elements.
2
3use super::SlotIndex;
4use alloc::collections::{btree_map, BTreeMap};
5use alloc::vec::IntoIter as VecIntoIter;
6use alloc::vec::Vec;
7use core::borrow::Borrow;
8use core::iter::FusedIterator;
9use core::ops::Index;
10use core::slice::Iter as SliceIter;
11
12/// A b-tree set where the iteration order of the values
13/// is independent of the ordering of the values.
14///
15/// The interface is closely compatible with the [`indexmap` crate]
16/// and a subset of the features that is relevant for the
17/// [`wasmparser-nostd` crate].
18///
19/// # Differences to original `IndexSet`
20///
21/// Since the goal of this crate was to maintain a simple
22/// `no_std` compatible fork of the [`indexmap` crate] there are some
23/// downsides and differences.
24///
25/// - Some operations such as `IndexSet::insert` now require `K: Clone`.
26/// - It is to be expected that this fork performs worse than the original
27/// [`indexmap` crate] implementation.
28/// - The implementation is based on `BTreeMap` internally instead of
29/// `HashMap` which has the effect that methods no longer require `K: Hash`
30/// but `K: Ord` instead.
31///
32/// [`indexmap` crate]: https://crates.io/crates/indexmap
33/// [`wasmparser-nostd` crate]: https://crates.io/crates/wasmparser-nostd
34#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
35pub struct IndexSet<T> {
36    /// A mapping from keys to slot indices.
37    key2slot: BTreeMap<T, SlotIndex>,
38    /// A vector holding all keys.
39    slots: Vec<T>,
40}
41
42impl<T> Default for IndexSet<T> {
43    fn default() -> Self {
44        Self::new()
45    }
46}
47
48impl<T> IndexSet<T> {
49    /// Makes a new, empty `IndexSet`.
50    ///
51    /// Does not allocate anything on its own.
52    pub fn new() -> Self {
53        Self {
54            key2slot: BTreeMap::new(),
55            slots: Vec::new(),
56        }
57    }
58
59    /// Constructs a new, empty [`IndexSet`] with at least the specified capacity.
60    ///
61    /// Does not allocate if `capacity` is zero.
62    pub fn with_capacity(capacity: usize) -> Self {
63        Self {
64            key2slot: BTreeMap::new(),
65            slots: Vec::with_capacity(capacity),
66        }
67    }
68
69    /// Reserve capacity for at least `additional` more values.
70    pub fn reserve(&mut self, additional: usize) {
71        self.slots.reserve(additional);
72    }
73
74    /// Returns the number of elements in the set.
75    pub fn len(&self) -> usize {
76        self.slots.len()
77    }
78
79    /// Returns `true` if the set contains no elements.
80    pub fn is_empty(&self) -> bool {
81        self.len() != 0
82    }
83
84    /// Returns `true` if `self` has no elements in common with `other`.
85    /// This is equivalent to checking for an empty intersection.
86    pub fn is_disjoint(&self, other: &Self) -> bool
87    where
88        T: Ord,
89    {
90        self.iter().all(|value| !other.contains(value))
91            && other.iter().all(|value| !self.contains(value))
92    }
93
94    /// Returns `true` if the set is a subset of another,
95    /// i.e., `other` contains at least all the elements in `self`.
96    pub fn is_subset(&self, other: &Self) -> bool
97    where
98        T: Ord,
99    {
100        self.iter().all(|value| other.contains(value))
101    }
102
103    /// Returns `true` if the set is a superset of another,
104    /// i.e., `self` contains at least all the elements in `other`.
105    pub fn is_superset(&self, other: &Self) -> bool
106    where
107        T: Ord,
108    {
109        other.is_subset(self)
110    }
111
112    /// Returns `true` if the set contains an element equal to the value.
113    ///
114    /// The value may be any borrowed form of the set's element type,
115    /// but the ordering on the borrowed form *must* match the
116    /// ordering on the element type.
117    pub fn contains<Q: ?Sized>(&self, key: &Q) -> bool
118    where
119        T: Borrow<Q> + Ord,
120        Q: Ord,
121    {
122        self.key2slot.contains_key(key)
123    }
124
125    /// Returns a reference to the element in the set, if any, that is equal to
126    /// the value.
127    ///
128    /// The value may be any borrowed form of the set's element type,
129    /// but the ordering on the borrowed form *must* match the
130    /// ordering on the element type.
131    pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T>
132    where
133        T: Borrow<Q> + Ord,
134        Q: Ord,
135    {
136        self.key2slot
137            .get(value)
138            .map(|index| &self.slots[index.index()])
139    }
140
141    /// Returns the index-value pair corresponding to the supplied value.
142    ///
143    /// The supplied key may be any borrowed form of the map's key type,
144    /// but the ordering on the borrowed form *must* match the ordering
145    /// on the key type.
146    pub fn get_full<Q: ?Sized>(&self, key: &Q) -> Option<(usize, &T)>
147    where
148        T: Borrow<Q> + Ord,
149        Q: Ord,
150    {
151        self.key2slot
152            .get_key_value(key)
153            .map(|(key, slot)| (slot.index(), key))
154    }
155
156    /// Returns the unique index corresponding to the supplied value.
157    ///
158    /// The supplied key may be any borrowed form of the map's key type,
159    /// but the ordering on the borrowed form *must* match the ordering
160    /// on the key type.
161    pub fn get_index_of<Q: ?Sized>(&self, key: &Q) -> Option<usize>
162    where
163        T: Borrow<Q> + Ord,
164        Q: Ord,
165    {
166        self.key2slot.get(key).copied().map(SlotIndex::index)
167    }
168
169    /// Returns a shared reference to the value at the given index.
170    pub fn get_index(&self, index: usize) -> Option<&T> {
171        self.slots.get(index)
172    }
173
174    /// Adds a value to the set.
175    ///
176    /// Returns whether the value was newly inserted. That is:
177    ///
178    /// - If the set did not previously contain an equal value, `true` is
179    ///   returned.
180    /// - If the set already contained an equal value, `false` is returned, and
181    ///   the entry is not updated.
182    pub fn insert(&mut self, value: T) -> bool
183    where
184        T: Ord + Clone,
185    {
186        let (_index, inserted) = self.insert_full(value);
187        inserted
188    }
189
190    /// Adds a value to the set.
191    ///
192    /// Returns the unique index to the value as well as a `bool` flag telling
193    /// whether the value was newly inserted. That is:
194    ///
195    /// - If the set did not previously contain an equal value, `true` is
196    ///   returned.
197    /// - If the set already contained an equal value, `false` is returned, and
198    ///   the entry is not updated.
199    pub fn insert_full(&mut self, value: T) -> (usize, bool)
200    where
201        T: Ord + Clone,
202    {
203        match self.key2slot.entry(value.clone()) {
204            btree_map::Entry::Vacant(entry) => {
205                let index = self.slots.len();
206                entry.insert(SlotIndex(index));
207                self.slots.push(value);
208                (index, true)
209            }
210            btree_map::Entry::Occupied(entry) => {
211                let index = entry.get().index();
212                self.slots[index] = value;
213                (index, false)
214            }
215        }
216    }
217
218    /// Gets an iterator that visits the elements in the [`IndexSet`]
219    /// in the order in which they have been inserted into the set unless
220    /// there have been removals.
221    pub fn iter(&self) -> Iter<T> {
222        Iter {
223            iter: self.slots.iter(),
224        }
225    }
226
227    /// Clears the set, removing all elements.
228    pub fn clear(&mut self) {
229        self.key2slot.clear();
230        self.slots.clear();
231    }
232}
233
234impl<T> Index<usize> for IndexSet<T> {
235    type Output = T;
236
237    fn index(&self, index: usize) -> &Self::Output {
238        self.get_index(index)
239            .expect("IndexSet: index out of bounds")
240    }
241}
242
243impl<'a, T> Extend<&'a T> for IndexSet<T>
244where
245    T: Ord + Copy,
246{
247    #[allow(clippy::map_clone)] // lifetime issue: seems to be a clippy bug
248    fn extend<I>(&mut self, iter: I)
249    where
250        I: IntoIterator<Item = &'a T>,
251    {
252        self.extend(iter.into_iter().map(|value| *value))
253    }
254}
255
256impl<T> Extend<T> for IndexSet<T>
257where
258    T: Ord + Clone,
259{
260    fn extend<I>(&mut self, iter: I)
261    where
262        I: IntoIterator<Item = T>,
263    {
264        iter.into_iter().for_each(move |value| {
265            self.insert(value);
266        });
267    }
268}
269
270impl<T> FromIterator<T> for IndexSet<T>
271where
272    T: Ord + Clone,
273{
274    fn from_iter<I>(iter: I) -> Self
275    where
276        I: IntoIterator<Item = T>,
277    {
278        let mut set = IndexSet::new();
279        set.extend(iter);
280        set
281    }
282}
283
284impl<T, const N: usize> From<[T; N]> for IndexSet<T>
285where
286    T: Ord + Clone,
287{
288    fn from(items: [T; N]) -> Self {
289        items.into_iter().collect()
290    }
291}
292
293impl<'a, T> IntoIterator for &'a IndexSet<T> {
294    type Item = &'a T;
295    type IntoIter = Iter<'a, T>;
296
297    fn into_iter(self) -> Self::IntoIter {
298        self.iter()
299    }
300}
301
302impl<T> IntoIterator for IndexSet<T> {
303    type Item = T;
304    type IntoIter = IntoIter<T>;
305
306    fn into_iter(self) -> Self::IntoIter {
307        IntoIter {
308            iter: self.slots.into_iter(),
309        }
310    }
311}
312
313/// An iterator over the items of a [`IndexSet`].
314///
315/// This `struct` is created by the [`iter`] method on [`IndexSet`].
316///
317/// [`iter`]: IndexSet::iter
318#[derive(Debug, Clone)]
319pub struct Iter<'a, T> {
320    iter: SliceIter<'a, T>,
321}
322
323impl<'a, T> Iterator for Iter<'a, T> {
324    type Item = &'a T;
325
326    fn size_hint(&self) -> (usize, Option<usize>) {
327        self.iter.size_hint()
328    }
329
330    fn count(self) -> usize {
331        self.iter.count()
332    }
333
334    fn next(&mut self) -> Option<Self::Item> {
335        self.iter.next()
336    }
337}
338
339impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
340    fn next_back(&mut self) -> Option<Self::Item> {
341        self.iter.next_back()
342    }
343}
344
345impl<'a, T> ExactSizeIterator for Iter<'a, T> {
346    fn len(&self) -> usize {
347        self.iter.len()
348    }
349}
350
351impl<'a, T> FusedIterator for Iter<'a, T> {}
352
353/// An owning iterator over the items of a [`IndexSet`].
354///
355/// This `struct` is created by the [`into_iter`] method on [`IndexSet`]
356/// (provided by the [`IntoIterator`] trait).
357///
358/// [`into_iter`]: IntoIterator::into_iter
359/// [`IntoIterator`]: core::iter::IntoIterator
360#[derive(Debug)]
361pub struct IntoIter<T> {
362    iter: VecIntoIter<T>,
363}
364
365impl<T> Iterator for IntoIter<T> {
366    type Item = T;
367
368    fn size_hint(&self) -> (usize, Option<usize>) {
369        self.iter.size_hint()
370    }
371
372    fn count(self) -> usize {
373        self.iter.count()
374    }
375
376    fn next(&mut self) -> Option<Self::Item> {
377        self.iter.next()
378    }
379}
380
381impl<T> DoubleEndedIterator for IntoIter<T> {
382    fn next_back(&mut self) -> Option<Self::Item> {
383        self.iter.next_back()
384    }
385}
386
387impl<T> ExactSizeIterator for IntoIter<T> {
388    fn len(&self) -> usize {
389        self.iter.len()
390    }
391}
392
393impl<T> FusedIterator for IntoIter<T> {}
indexmap_nostd/set.rs

indexmap_nostd/
set.rs
