1 | use super::{ |
2 | Bucket, Entries, IndexMap, IntoIter, IntoKeys, IntoValues, Iter, IterMut, Keys, Values, |
3 | ValuesMut, |
4 | }; |
5 | use crate::util::try_simplify_range; |
6 | |
7 | use alloc::boxed::Box; |
8 | use alloc::vec::Vec; |
9 | use core::cmp::Ordering; |
10 | use core::fmt; |
11 | use core::hash::{Hash, Hasher}; |
12 | use 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)] |
22 | pub 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)] |
29 | impl<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 | |
47 | impl<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 | |
206 | impl<'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 | |
215 | impl<'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 | |
224 | impl<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 | |
233 | impl<K, V> Default for &'_ Slice<K, V> { |
234 | fn default() -> Self { |
235 | Slice::from_slice(&[]) |
236 | } |
237 | } |
238 | |
239 | impl<K, V> Default for &'_ mut Slice<K, V> { |
240 | fn default() -> Self { |
241 | Slice::from_mut_slice(&mut []) |
242 | } |
243 | } |
244 | |
245 | impl<K, V> Default for Box<Slice<K, V>> { |
246 | fn default() -> Self { |
247 | Slice::from_boxed(entries:Box::default()) |
248 | } |
249 | } |
250 | |
251 | impl<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 | |
257 | impl<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 | |
263 | impl<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 | |
269 | impl<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 | |
275 | impl<K: Eq, V: Eq> Eq for Slice<K, V> {} |
276 | |
277 | impl<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 | |
283 | impl<K: Ord, V: Ord> Ord for Slice<K, V> { |
284 | fn cmp(&self, other: &Self) -> Ordering { |
285 | self.iter().cmp(other) |
286 | } |
287 | } |
288 | |
289 | impl<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 | |
299 | impl<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 | |
307 | impl<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. |
316 | macro_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 | } |
347 | impl_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)] |
358 | mod 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 | |