indexmap/set/
slice.rs

1use alloc::{boxed::Box, vec::Vec};
2use core::{
3    cmp::Ordering,
4    fmt,
5    hash::{Hash, Hasher},
6    ops::{self, Bound, Index, RangeBounds},
7};
8
9use super::{Bucket, IndexSet, IntoIter, Iter};
10use crate::util::{slice_eq, try_simplify_range};
11
12/// A dynamically-sized slice of values in an [`IndexSet`].
13///
14/// This supports indexed operations much like a `[T]` slice,
15/// but not any hashed operations on the values.
16///
17/// Unlike `IndexSet`, `Slice` does consider the order for [`PartialEq`]
18/// and [`Eq`], and it also implements [`PartialOrd`], [`Ord`], and [`Hash`].
19#[repr(transparent)]
20pub struct Slice<T> {
21    pub(crate) entries: [Bucket<T>],
22}
23
24// SAFETY: `Slice<T>` is a transparent wrapper around `[Bucket<T>]`,
25// and reference lifetimes are bound together in function signatures.
26#[allow(unsafe_code)]
27impl<T> Slice<T> {
28    pub(super) const fn from_slice(entries: &[Bucket<T>]) -> &Self {
29        unsafe { &*(entries as *const [Bucket<T>] as *const Self) }
30    }
31
32    pub(super) fn from_boxed(entries: Box<[Bucket<T>]>) -> Box<Self> {
33        unsafe { Box::from_raw(Box::into_raw(entries) as *mut Self) }
34    }
35
36    fn into_boxed(self: Box<Self>) -> Box<[Bucket<T>]> {
37        unsafe { Box::from_raw(Box::into_raw(self) as *mut [Bucket<T>]) }
38    }
39}
40
41impl<T> Slice<T> {
42    pub(crate) fn into_entries(self: Box<Self>) -> Vec<Bucket<T>> {
43        self.into_boxed().into_vec()
44    }
45
46    /// Returns an empty slice.
47    pub const fn new<'a>() -> &'a Self {
48        Self::from_slice(&[])
49    }
50
51    /// Return the number of elements in the set slice.
52    pub const fn len(&self) -> usize {
53        self.entries.len()
54    }
55
56    /// Returns true if the set slice contains no elements.
57    pub const fn is_empty(&self) -> bool {
58        self.entries.is_empty()
59    }
60
61    /// Get a value by index.
62    ///
63    /// Valid indices are `0 <= index < self.len()`.
64    pub fn get_index(&self, index: usize) -> Option<&T> {
65        self.entries.get(index).map(Bucket::key_ref)
66    }
67
68    /// Returns a slice of values in the given range of indices.
69    ///
70    /// Valid indices are `0 <= index < self.len()`.
71    pub fn get_range<R: RangeBounds<usize>>(&self, range: R) -> Option<&Self> {
72        let range = try_simplify_range(range, self.entries.len())?;
73        self.entries.get(range).map(Self::from_slice)
74    }
75
76    /// Get the first value.
77    pub const fn first(&self) -> Option<&T> {
78        if let [first, ..] = &self.entries {
79            Some(&first.key)
80        } else {
81            None
82        }
83    }
84
85    /// Get the last value.
86    pub const fn last(&self) -> Option<&T> {
87        if let [.., last] = &self.entries {
88            Some(&last.key)
89        } else {
90            None
91        }
92    }
93
94    /// Divides one slice into two at an index.
95    ///
96    /// ***Panics*** if `index > len`.
97    /// For a non-panicking alternative see [`split_at_checked`][Self::split_at_checked].
98    #[track_caller]
99    pub const fn split_at(&self, index: usize) -> (&Self, &Self) {
100        let (first, second) = self.entries.split_at(index);
101        (Self::from_slice(first), Self::from_slice(second))
102    }
103
104    /// Divides one slice into two at an index.
105    ///
106    /// Returns `None` if `index > len`.
107    pub const fn split_at_checked(&self, index: usize) -> Option<(&Self, &Self)> {
108        if let Some((first, second)) = self.entries.split_at_checked(index) {
109            Some((Self::from_slice(first), Self::from_slice(second)))
110        } else {
111            None
112        }
113    }
114
115    /// Returns the first value and the rest of the slice,
116    /// or `None` if it is empty.
117    pub const fn split_first(&self) -> Option<(&T, &Self)> {
118        if let [first, rest @ ..] = &self.entries {
119            Some((&first.key, Self::from_slice(rest)))
120        } else {
121            None
122        }
123    }
124
125    /// Returns the last value and the rest of the slice,
126    /// or `None` if it is empty.
127    pub const fn split_last(&self) -> Option<(&T, &Self)> {
128        if let [rest @ .., last] = &self.entries {
129            Some((&last.key, Self::from_slice(rest)))
130        } else {
131            None
132        }
133    }
134
135    /// Return an iterator over the values of the set slice.
136    pub fn iter(&self) -> Iter<'_, T> {
137        Iter::new(&self.entries)
138    }
139
140    /// Search over a sorted set for a value.
141    ///
142    /// Returns the position where that value is present, or the position where it can be inserted
143    /// to maintain the sort. See [`slice::binary_search`] for more details.
144    ///
145    /// Computes in **O(log(n))** time, which is notably less scalable than looking the value up in
146    /// the set this is a slice from using [`IndexSet::get_index_of`], but this can also position
147    /// missing values.
148    pub fn binary_search(&self, x: &T) -> Result<usize, usize>
149    where
150        T: Ord,
151    {
152        self.binary_search_by(|p| p.cmp(x))
153    }
154
155    /// Search over a sorted set with a comparator function.
156    ///
157    /// Returns the position where that value is present, or the position where it can be inserted
158    /// to maintain the sort. See [`slice::binary_search_by`] for more details.
159    ///
160    /// Computes in **O(log(n))** time.
161    #[inline]
162    pub fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result<usize, usize>
163    where
164        F: FnMut(&'a T) -> Ordering,
165    {
166        self.entries.binary_search_by(move |a| f(&a.key))
167    }
168
169    /// Search over a sorted set with an extraction function.
170    ///
171    /// Returns the position where that value is present, or the position where it can be inserted
172    /// to maintain the sort. See [`slice::binary_search_by_key`] for more details.
173    ///
174    /// Computes in **O(log(n))** time.
175    #[inline]
176    pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, mut f: F) -> Result<usize, usize>
177    where
178        F: FnMut(&'a T) -> B,
179        B: Ord,
180    {
181        self.binary_search_by(|k| f(k).cmp(b))
182    }
183
184    /// Checks if the values of this slice are sorted.
185    #[inline]
186    pub fn is_sorted(&self) -> bool
187    where
188        T: PartialOrd,
189    {
190        self.entries.is_sorted_by(|a, b| a.key <= b.key)
191    }
192
193    /// Checks if this slice is sorted using the given comparator function.
194    #[inline]
195    pub fn is_sorted_by<'a, F>(&'a self, mut cmp: F) -> bool
196    where
197        F: FnMut(&'a T, &'a T) -> bool,
198    {
199        self.entries.is_sorted_by(move |a, b| cmp(&a.key, &b.key))
200    }
201
202    /// Checks if this slice is sorted using the given sort-key function.
203    #[inline]
204    pub fn is_sorted_by_key<'a, F, K>(&'a self, mut sort_key: F) -> bool
205    where
206        F: FnMut(&'a T) -> K,
207        K: PartialOrd,
208    {
209        self.entries.is_sorted_by_key(move |a| sort_key(&a.key))
210    }
211
212    /// Returns the index of the partition point of a sorted set according to the given predicate
213    /// (the index of the first element of the second partition).
214    ///
215    /// See [`slice::partition_point`] for more details.
216    ///
217    /// Computes in **O(log(n))** time.
218    #[must_use]
219    pub fn partition_point<P>(&self, mut pred: P) -> usize
220    where
221        P: FnMut(&T) -> bool,
222    {
223        self.entries.partition_point(move |a| pred(&a.key))
224    }
225}
226
227impl<'a, T> IntoIterator for &'a Slice<T> {
228    type IntoIter = Iter<'a, T>;
229    type Item = &'a T;
230
231    fn into_iter(self) -> Self::IntoIter {
232        self.iter()
233    }
234}
235
236impl<T> IntoIterator for Box<Slice<T>> {
237    type IntoIter = IntoIter<T>;
238    type Item = T;
239
240    fn into_iter(self) -> Self::IntoIter {
241        IntoIter::new(self.into_entries())
242    }
243}
244
245impl<T> Default for &'_ Slice<T> {
246    fn default() -> Self {
247        Slice::from_slice(&[])
248    }
249}
250
251impl<T> Default for Box<Slice<T>> {
252    fn default() -> Self {
253        Slice::from_boxed(Box::default())
254    }
255}
256
257impl<T: Clone> Clone for Box<Slice<T>> {
258    fn clone(&self) -> Self {
259        Slice::from_boxed(self.entries.to_vec().into_boxed_slice())
260    }
261}
262
263impl<T: Copy> From<&Slice<T>> for Box<Slice<T>> {
264    fn from(slice: &Slice<T>) -> Self {
265        Slice::from_boxed(Box::from(&slice.entries))
266    }
267}
268
269impl<T: fmt::Debug> fmt::Debug for Slice<T> {
270    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
271        f.debug_list().entries(self).finish()
272    }
273}
274
275impl<T, U> PartialEq<Slice<U>> for Slice<T>
276where
277    T: PartialEq<U>,
278{
279    fn eq(&self, other: &Slice<U>) -> bool {
280        slice_eq(&self.entries, &other.entries, |b1, b2| b1.key == b2.key)
281    }
282}
283
284impl<T, U> PartialEq<[U]> for Slice<T>
285where
286    T: PartialEq<U>,
287{
288    fn eq(&self, other: &[U]) -> bool {
289        slice_eq(&self.entries, other, |b, o| b.key == *o)
290    }
291}
292
293impl<T, U> PartialEq<Slice<U>> for [T]
294where
295    T: PartialEq<U>,
296{
297    fn eq(&self, other: &Slice<U>) -> bool {
298        slice_eq(self, &other.entries, |o, b| *o == b.key)
299    }
300}
301
302impl<T, U, const N: usize> PartialEq<[U; N]> for Slice<T>
303where
304    T: PartialEq<U>,
305{
306    fn eq(&self, other: &[U; N]) -> bool {
307        <Self as PartialEq<[U]>>::eq(self, other)
308    }
309}
310
311impl<T, const N: usize, U> PartialEq<Slice<U>> for [T; N]
312where
313    T: PartialEq<U>,
314{
315    fn eq(&self, other: &Slice<U>) -> bool {
316        <[T] as PartialEq<Slice<U>>>::eq(self, other)
317    }
318}
319
320impl<T: Eq> Eq for Slice<T> {}
321
322impl<T: PartialOrd> PartialOrd for Slice<T> {
323    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
324        self.iter().partial_cmp(other)
325    }
326}
327
328impl<T: Ord> Ord for Slice<T> {
329    fn cmp(&self, other: &Self) -> Ordering {
330        self.iter().cmp(other)
331    }
332}
333
334impl<T: Hash> Hash for Slice<T> {
335    fn hash<H: Hasher>(&self, state: &mut H) {
336        self.len().hash(state);
337        for value in self {
338            value.hash(state);
339        }
340    }
341}
342
343impl<T> Index<usize> for Slice<T> {
344    type Output = T;
345
346    fn index(&self, index: usize) -> &Self::Output {
347        &self.entries[index].key
348    }
349}
350
351// We can't have `impl<I: RangeBounds<usize>> Index<I>` because that conflicts with `Index<usize>`.
352// Instead, we repeat the implementations for all the core range types.
353macro_rules! impl_index {
354    ($($range:ty),*) => {$(
355        impl<T, S> Index<$range> for IndexSet<T, S> {
356            type Output = Slice<T>;
357
358            fn index(&self, range: $range) -> &Self::Output {
359                Slice::from_slice(&self.as_entries()[range])
360            }
361        }
362
363        impl<T> Index<$range> for Slice<T> {
364            type Output = Self;
365
366            fn index(&self, range: $range) -> &Self::Output {
367                Slice::from_slice(&self.entries[range])
368            }
369        }
370    )*}
371}
372impl_index!(
373    ops::Range<usize>,
374    ops::RangeFrom<usize>,
375    ops::RangeFull,
376    ops::RangeInclusive<usize>,
377    ops::RangeTo<usize>,
378    ops::RangeToInclusive<usize>,
379    (Bound<usize>, Bound<usize>)
380);
381
382#[cfg(test)]
383mod tests {
384    use super::*;
385
386    #[test]
387    fn slice_index() {
388        fn check(vec_slice: &[i32], set_slice: &Slice<i32>, sub_slice: &Slice<i32>) {
389            assert_eq!(set_slice as *const _, sub_slice as *const _);
390            assert!(vec_slice.iter().eq(set_slice));
391        }
392
393        let vec: Vec<i32> = (0..10).map(|i| i * i).collect();
394        let set: IndexSet<i32> = vec.iter().cloned().collect();
395        let slice = set.as_slice();
396
397        // RangeFull
398        #[expect(clippy::redundant_slicing)]
399        check(&vec[..], &set[..], &slice[..]);
400
401        for i in 0usize..10 {
402            // Index
403            assert_eq!(vec[i], set[i]);
404            assert_eq!(vec[i], slice[i]);
405
406            // RangeFrom
407            check(&vec[i..], &set[i..], &slice[i..]);
408
409            // RangeTo
410            check(&vec[..i], &set[..i], &slice[..i]);
411
412            // RangeToInclusive
413            check(&vec[..=i], &set[..=i], &slice[..=i]);
414
415            // (Bound<usize>, Bound<usize>)
416            let bounds = (Bound::Excluded(i), Bound::Unbounded);
417            check(&vec[i + 1..], &set[bounds], &slice[bounds]);
418
419            for j in i..=10 {
420                // Range
421                check(&vec[i..j], &set[i..j], &slice[i..j]);
422            }
423
424            for j in i..10 {
425                // RangeInclusive
426                check(&vec[i..=j], &set[i..=j], &slice[i..=j]);
427            }
428        }
429    }
430}
indexmap/set/slice.rs

indexmap/set/
slice.rs
