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