1 //! Boxed slices for `PrimaryMap`.
2 
3 use crate::EntityRef;
4 use crate::iter::{Iter, IterMut};
5 use crate::keys::Keys;
6 use alloc::boxed::Box;
7 use core::marker::PhantomData;
8 use core::ops::{Index, IndexMut};
9 use core::slice;
10 
11 /// A slice mapping `K -> V` allocating dense entity references.
12 ///
13 /// The `BoxedSlice` data structure uses the dense index space to implement a map with a boxed
14 /// slice.
15 #[derive(Debug, Clone)]
16 pub struct BoxedSlice<K, V>
17 where
18     K: EntityRef,
19 {
20     elems: Box<[V]>,
21     unused: PhantomData<K>,
22 }
23 
24 impl<K, V> BoxedSlice<K, V>
25 where
26     K: EntityRef,
27 {
28     /// Create a new slice from a raw pointer. A safer way to create slices is
29     /// to use `PrimaryMap::into_boxed_slice()`.
30     ///
31     /// # Safety
32     ///
33     /// This relies on `raw` pointing to a valid slice of `V`s.
from_raw(raw: *mut [V]) -> Self34     pub unsafe fn from_raw(raw: *mut [V]) -> Self {
35         Self {
36             elems: unsafe { Box::from_raw(raw) },
37             unused: PhantomData,
38         }
39     }
40 
41     /// Check if `k` is a valid key in the map.
is_valid(&self, k: K) -> bool42     pub fn is_valid(&self, k: K) -> bool {
43         k.index() < self.elems.len()
44     }
45 
46     /// Get the element at `k` if it exists.
get(&self, k: K) -> Option<&V>47     pub fn get(&self, k: K) -> Option<&V> {
48         self.elems.get(k.index())
49     }
50 
51     /// Get the element at `k` if it exists, mutable version.
get_mut(&mut self, k: K) -> Option<&mut V>52     pub fn get_mut(&mut self, k: K) -> Option<&mut V> {
53         self.elems.get_mut(k.index())
54     }
55 
56     /// Is this map completely empty?
is_empty(&self) -> bool57     pub fn is_empty(&self) -> bool {
58         self.elems.is_empty()
59     }
60 
61     /// Get the total number of entity references created.
len(&self) -> usize62     pub fn len(&self) -> usize {
63         self.elems.len()
64     }
65 
66     /// Iterate over all the keys in this map.
keys(&self) -> Keys<K>67     pub fn keys(&self) -> Keys<K> {
68         Keys::with_len(self.elems.len())
69     }
70 
71     /// Iterate over all the values in this map.
values(&self) -> slice::Iter<'_, V>72     pub fn values(&self) -> slice::Iter<'_, V> {
73         self.elems.iter()
74     }
75 
76     /// Iterate over all the values in this map, mutable edition.
values_mut(&mut self) -> slice::IterMut<'_, V>77     pub fn values_mut(&mut self) -> slice::IterMut<'_, V> {
78         self.elems.iter_mut()
79     }
80 
81     /// Iterate over all the keys and values in this map.
iter(&self) -> Iter<'_, K, V>82     pub fn iter(&self) -> Iter<'_, K, V> {
83         Iter::new(self.elems.iter())
84     }
85 
86     /// Iterate over all the keys and values in this map, mutable edition.
iter_mut(&mut self) -> IterMut<'_, K, V>87     pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
88         IterMut::new(self.elems.iter_mut())
89     }
90 
91     /// Returns the last element that was inserted in the map.
last(&self) -> Option<&V>92     pub fn last(&self) -> Option<&V> {
93         self.elems.last()
94     }
95 }
96 
97 /// Immutable indexing into a `BoxedSlice`.
98 /// The indexed value must be in the map.
99 impl<K, V> Index<K> for BoxedSlice<K, V>
100 where
101     K: EntityRef,
102 {
103     type Output = V;
104 
index(&self, k: K) -> &V105     fn index(&self, k: K) -> &V {
106         &self.elems[k.index()]
107     }
108 }
109 
110 /// Mutable indexing into a `BoxedSlice`.
111 impl<K, V> IndexMut<K> for BoxedSlice<K, V>
112 where
113     K: EntityRef,
114 {
index_mut(&mut self, k: K) -> &mut V115     fn index_mut(&mut self, k: K) -> &mut V {
116         &mut self.elems[k.index()]
117     }
118 }
119 
120 impl<'a, K, V> IntoIterator for &'a BoxedSlice<K, V>
121 where
122     K: EntityRef,
123 {
124     type Item = (K, &'a V);
125     type IntoIter = Iter<'a, K, V>;
126 
into_iter(self) -> Self::IntoIter127     fn into_iter(self) -> Self::IntoIter {
128         Iter::new(self.elems.iter())
129     }
130 }
131 
132 impl<'a, K, V> IntoIterator for &'a mut BoxedSlice<K, V>
133 where
134     K: EntityRef,
135 {
136     type Item = (K, &'a mut V);
137     type IntoIter = IterMut<'a, K, V>;
138 
into_iter(self) -> Self::IntoIter139     fn into_iter(self) -> Self::IntoIter {
140         IterMut::new(self.elems.iter_mut())
141     }
142 }
143 
144 #[cfg(test)]
145 mod tests {
146     use super::*;
147     use crate::primary::PrimaryMap;
148     use alloc::vec::Vec;
149 
150     // `EntityRef` impl for testing.
151     #[derive(Clone, Copy, Debug, PartialEq, Eq)]
152     struct E(u32);
153 
154     impl EntityRef for E {
new(i: usize) -> Self155         fn new(i: usize) -> Self {
156             E(i as u32)
157         }
index(self) -> usize158         fn index(self) -> usize {
159             self.0 as usize
160         }
161     }
162 
163     #[test]
basic()164     fn basic() {
165         let r0 = E(0);
166         let r1 = E(1);
167         let p = PrimaryMap::<E, isize>::new();
168         let m = p.into_boxed_slice();
169 
170         let v: Vec<E> = m.keys().collect();
171         assert_eq!(v, []);
172 
173         assert!(!m.is_valid(r0));
174         assert!(!m.is_valid(r1));
175     }
176 
177     #[test]
iter()178     fn iter() {
179         let mut p: PrimaryMap<E, usize> = PrimaryMap::new();
180         p.push(12);
181         p.push(33);
182         let mut m = p.into_boxed_slice();
183 
184         let mut i = 0;
185         for (key, value) in &m {
186             assert_eq!(key.index(), i);
187             match i {
188                 0 => assert_eq!(*value, 12),
189                 1 => assert_eq!(*value, 33),
190                 _ => panic!(),
191             }
192             i += 1;
193         }
194         i = 0;
195         for (key_mut, value_mut) in m.iter_mut() {
196             assert_eq!(key_mut.index(), i);
197             match i {
198                 0 => assert_eq!(*value_mut, 12),
199                 1 => assert_eq!(*value_mut, 33),
200                 _ => panic!(),
201             }
202             i += 1;
203         }
204     }
205 
206     #[test]
iter_rev()207     fn iter_rev() {
208         let mut p: PrimaryMap<E, usize> = PrimaryMap::new();
209         p.push(12);
210         p.push(33);
211         let mut m = p.into_boxed_slice();
212 
213         let mut i = 2;
214         for (key, value) in m.iter().rev() {
215             i -= 1;
216             assert_eq!(key.index(), i);
217             match i {
218                 0 => assert_eq!(*value, 12),
219                 1 => assert_eq!(*value, 33),
220                 _ => panic!(),
221             }
222         }
223 
224         i = 2;
225         for (key, value) in m.iter_mut().rev() {
226             i -= 1;
227             assert_eq!(key.index(), i);
228             match i {
229                 0 => assert_eq!(*value, 12),
230                 1 => assert_eq!(*value, 33),
231                 _ => panic!(),
232             }
233         }
234     }
235     #[test]
keys()236     fn keys() {
237         let mut p: PrimaryMap<E, usize> = PrimaryMap::new();
238         p.push(12);
239         p.push(33);
240         let m = p.into_boxed_slice();
241 
242         let mut i = 0;
243         for key in m.keys() {
244             assert_eq!(key.index(), i);
245             i += 1;
246         }
247     }
248 
249     #[test]
keys_rev()250     fn keys_rev() {
251         let mut p: PrimaryMap<E, usize> = PrimaryMap::new();
252         p.push(12);
253         p.push(33);
254         let m = p.into_boxed_slice();
255 
256         let mut i = 2;
257         for key in m.keys().rev() {
258             i -= 1;
259             assert_eq!(key.index(), i);
260         }
261     }
262 
263     #[test]
values()264     fn values() {
265         let mut p: PrimaryMap<E, usize> = PrimaryMap::new();
266         p.push(12);
267         p.push(33);
268         let mut m = p.into_boxed_slice();
269 
270         let mut i = 0;
271         for value in m.values() {
272             match i {
273                 0 => assert_eq!(*value, 12),
274                 1 => assert_eq!(*value, 33),
275                 _ => panic!(),
276             }
277             i += 1;
278         }
279         i = 0;
280         for value_mut in m.values_mut() {
281             match i {
282                 0 => assert_eq!(*value_mut, 12),
283                 1 => assert_eq!(*value_mut, 33),
284                 _ => panic!(),
285             }
286             i += 1;
287         }
288     }
289 
290     #[test]
values_rev()291     fn values_rev() {
292         let mut p: PrimaryMap<E, usize> = PrimaryMap::new();
293         p.push(12);
294         p.push(33);
295         let mut m = p.into_boxed_slice();
296 
297         let mut i = 2;
298         for value in m.values().rev() {
299             i -= 1;
300             match i {
301                 0 => assert_eq!(*value, 12),
302                 1 => assert_eq!(*value, 33),
303                 _ => panic!(),
304             }
305         }
306         i = 2;
307         for value_mut in m.values_mut().rev() {
308             i -= 1;
309             match i {
310                 0 => assert_eq!(*value_mut, 12),
311                 1 => assert_eq!(*value_mut, 33),
312                 _ => panic!(),
313             }
314         }
315     }
316 }
317