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