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: &T, _)) = 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: T| (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: T| (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: &'a T, _value: &'a ())| 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: T, _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 {}
317