Skip to main content

prjcombine_entity/
part.rs

1//! A partial map backed by a vector.
2use core::hash::Hash;
3use core::marker::PhantomData;
4use core::ops::{Index, IndexMut};
5
6use std::fmt;
7
8use crate::{EntityId, EntityVec};
9
10/// A partial map backed by a vector.
11///
12/// An `EntityPartVec` stores at most one value `V` for each index `I`. Conceptually, this is
13/// similar to e.g. a `BTreeMap<I, V>`.
14///
15/// Under the hood, this is backed by a `Vec<Option<V>>`. Thus, ideally the type `V` should have a
16/// niche in its layout.
17#[derive(Clone, Eq, PartialEq, Hash)]
18#[cfg_attr(feature = "bincode", derive(bincode::Encode, bincode::Decode))]
19pub struct EntityPartVec<I: EntityId, V> {
20    vals: Vec<Option<V>>,
21    ids: PhantomData<I>,
22}
23
24impl<I: EntityId, V> EntityPartVec<I, V> {
25    pub fn new() -> Self {
26        Self {
27            vals: Vec::new(),
28            ids: PhantomData,
29        }
30    }
31
32    pub fn with_capacity(cap: usize) -> Self {
33        Self {
34            vals: Vec::with_capacity(cap),
35            ids: PhantomData,
36        }
37    }
38
39    pub fn is_empty(&self) -> bool {
40        self.iter().next().is_none()
41    }
42
43    pub fn get(&self, id: I) -> Option<&V> {
44        let idx = id.to_idx();
45        self.vals.get(idx).and_then(|x| x.as_ref())
46    }
47
48    pub fn get_mut(&mut self, id: I) -> Option<&mut V> {
49        let idx = id.to_idx();
50        self.vals.get_mut(idx).and_then(|x| x.as_mut())
51    }
52
53    pub fn contains_id(&self, id: I) -> bool {
54        let idx = id.to_idx();
55        self.vals.get(idx).is_some_and(|x| x.is_some())
56    }
57
58    pub fn clear(&mut self) {
59        self.vals.clear()
60    }
61
62    /// Inserts the value `val` at position `id`, returning the previous value, if any.
63    pub fn insert(&mut self, id: I, val: V) -> Option<V> {
64        let idx = id.to_idx();
65        if idx >= self.vals.len() {
66            self.vals.resize_with(idx + 1, Default::default);
67        }
68        self.vals[idx].replace(val)
69    }
70
71    /// Remove the value at position `id`.
72    pub fn remove(&mut self, id: I) -> Option<V> {
73        let idx = id.to_idx();
74        let res = self.vals.get_mut(idx)?.take();
75        // We choose to trim None's here to avoid needlessly iterating over them later.
76        // Do note, however, that if an element at this index gets re-added later, we might
77        // need to clear this memory again. We consider that to be okay.
78        while let Some(None) = self.vals.last() {
79            self.vals.pop();
80        }
81        res
82    }
83
84    /// Returns iterator of IDs for which values are present.
85    pub fn ids(&self) -> Ids<'_, I, V> {
86        Ids { vals: self.iter() }
87    }
88
89    pub fn into_ids(self) -> IntoIds<I, V> {
90        IntoIds {
91            vals: self.into_iter(),
92        }
93    }
94
95    /// Returns an iterator of `(id, &value)` pairs.
96    ///
97    /// IDs not present are skipped entirely.
98    pub fn iter(&self) -> Iter<'_, I, V> {
99        Iter {
100            vals: self.vals.iter(),
101            pos: 0,
102            ids: PhantomData,
103        }
104    }
105
106    /// Returns an iterator of `(id, &mut value)` pairs.
107    ///
108    /// IDs not present are skipped entirely.
109    pub fn iter_mut(&mut self) -> IterMut<'_, I, V> {
110        IterMut {
111            vals: self.vals.iter_mut(),
112            pos: 0,
113            ids: PhantomData,
114        }
115    }
116
117    pub fn values(&self) -> Values<'_, I, V> {
118        Values { vals: self.iter() }
119    }
120
121    pub fn values_mut(&mut self) -> ValuesMut<'_, I, V> {
122        ValuesMut {
123            vals: self.iter_mut(),
124        }
125    }
126
127    pub fn into_values(self) -> IntoValues<I, V> {
128        IntoValues {
129            vals: self.into_iter(),
130        }
131    }
132
133    /// Converts into an [`EntityVec`] without holes.
134    ///
135    /// If values are present for all IDs between 0 and the highest ID present, that is, if there
136    /// aren't any "holes" in the middle, then convert to a [`EntityVec`] which expresses this fact
137    /// statically. Otherwise, panic.
138    #[track_caller]
139    pub fn into_full(mut self) -> EntityVec<I, V> {
140        while matches!(self.vals.last(), Some(None)) {
141            self.vals.pop();
142        }
143        self.vals.into_iter().map(Option::unwrap).collect()
144    }
145
146    /// Converts into an [`EntityVec`] without holes.
147    ///
148    /// If values are present for all IDs between 0 and the highest ID present, that is, if there
149    /// aren't any "holes" in the middle, then convert to a [`EntityVec`] which expresses this fact
150    /// statically. Otherwise, return the lowest ID at which a hole was found.
151    pub fn try_into_full(mut self) -> Result<EntityVec<I, V>, I> {
152        while matches!(self.vals.last(), Some(None)) {
153            self.vals.pop();
154        }
155        let mut res = EntityVec::new();
156        for val in self.vals {
157            if let Some(val) = val {
158                res.push(val);
159            } else {
160                return Err(res.next_id());
161            }
162        }
163        Ok(res)
164    }
165
166    pub fn map<O>(&self, mut f: impl FnMut(I, &V) -> O) -> EntityPartVec<I, O> {
167        self.iter().map(|(id, v)| (id, f(id, v))).collect()
168    }
169
170    pub fn map_values<O>(&self, mut f: impl FnMut(&V) -> O) -> EntityPartVec<I, O> {
171        self.iter().map(|(id, v)| (id, f(v))).collect()
172    }
173}
174
175impl<I: EntityId, V> Default for EntityPartVec<I, V> {
176    fn default() -> Self {
177        Self::new()
178    }
179}
180
181impl<I, V> fmt::Debug for EntityPartVec<I, V>
182where
183    I: EntityId,
184    V: fmt::Debug,
185{
186    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
187        fmt.debug_map().entries(self).finish()
188    }
189}
190
191impl<I: EntityId, V> IntoIterator for EntityPartVec<I, V> {
192    type Item = (I, V);
193    type IntoIter = IntoIter<I, V>;
194    fn into_iter(self) -> Self::IntoIter {
195        IntoIter {
196            vals: self.vals.into_iter(),
197            pos: 0,
198            ids: PhantomData,
199        }
200    }
201}
202
203impl<'a, I: EntityId, V> IntoIterator for &'a EntityPartVec<I, V> {
204    type Item = (I, &'a V);
205    type IntoIter = Iter<'a, I, V>;
206    fn into_iter(self) -> Self::IntoIter {
207        self.iter()
208    }
209}
210
211impl<'a, I: EntityId, V> IntoIterator for &'a mut EntityPartVec<I, V> {
212    type Item = (I, &'a mut V);
213    type IntoIter = IterMut<'a, I, V>;
214    fn into_iter(self) -> Self::IntoIter {
215        self.iter_mut()
216    }
217}
218
219impl<I: EntityId, V> Index<I> for EntityPartVec<I, V> {
220    type Output = V;
221    fn index(&self, index: I) -> &V {
222        self.vals[index.to_idx()].as_ref().unwrap()
223    }
224}
225
226impl<I: EntityId, V> IndexMut<I> for EntityPartVec<I, V> {
227    fn index_mut(&mut self, index: I) -> &mut V {
228        self.vals[index.to_idx()].as_mut().unwrap()
229    }
230}
231
232/// Iterator of `(id, &value)` pairs.
233#[derive(Clone, Debug)]
234pub struct Iter<'a, I, V> {
235    vals: core::slice::Iter<'a, Option<V>>,
236    pos: usize,
237    ids: PhantomData<I>,
238}
239
240impl<'a, I: EntityId, V> Iterator for Iter<'a, I, V> {
241    type Item = (I, &'a V);
242    fn next(&mut self) -> Option<(I, &'a V)> {
243        loop {
244            let id = I::from_idx(self.pos);
245            let val = self.vals.next()?;
246            self.pos += 1;
247            if let Some(val) = val {
248                return Some((id, val));
249            }
250        }
251    }
252}
253
254impl<'a, I: EntityId, V> DoubleEndedIterator for Iter<'a, I, V> {
255    fn next_back(&mut self) -> Option<(I, &'a V)> {
256        loop {
257            if let Some(val) = self.vals.next_back()? {
258                return Some((I::from_idx(self.pos + self.vals.len()), val));
259            }
260        }
261    }
262}
263
264/// Iterator of `(id, &mut value)` pairs.
265#[derive(Debug)]
266pub struct IterMut<'a, I, V> {
267    vals: core::slice::IterMut<'a, Option<V>>,
268    pos: usize,
269    ids: PhantomData<I>,
270}
271
272impl<'a, I: EntityId, V> Iterator for IterMut<'a, I, V> {
273    type Item = (I, &'a mut V);
274    fn next(&mut self) -> Option<(I, &'a mut V)> {
275        loop {
276            let id = I::from_idx(self.pos);
277            let val = self.vals.next()?;
278            self.pos += 1;
279            if let Some(val) = val {
280                return Some((id, val));
281            }
282        }
283    }
284}
285
286impl<'a, I: EntityId, V> DoubleEndedIterator for IterMut<'a, I, V> {
287    fn next_back(&mut self) -> Option<(I, &'a mut V)> {
288        loop {
289            if let Some(val) = self.vals.next_back()? {
290                return Some((I::from_idx(self.pos + self.vals.len()), val));
291            }
292        }
293    }
294}
295
296/// Iterator of `(id, value)` pairs.
297#[derive(Clone, Debug)]
298pub struct IntoIter<I, V> {
299    vals: std::vec::IntoIter<Option<V>>,
300    pos: usize,
301    ids: PhantomData<I>,
302}
303
304impl<I: EntityId, V> Iterator for IntoIter<I, V> {
305    type Item = (I, V);
306    fn next(&mut self) -> Option<(I, V)> {
307        loop {
308            let id = I::from_idx(self.pos);
309            let val = self.vals.next()?;
310            self.pos += 1;
311            if let Some(val) = val {
312                return Some((id, val));
313            }
314        }
315    }
316}
317
318impl<I: EntityId, V> DoubleEndedIterator for IntoIter<I, V> {
319    fn next_back(&mut self) -> Option<(I, V)> {
320        loop {
321            if let Some(val) = self.vals.next_back()? {
322                return Some((I::from_idx(self.pos + self.vals.len()), val));
323            }
324        }
325    }
326}
327
328#[derive(Clone, Debug)]
329pub struct Ids<'a, I, V> {
330    vals: Iter<'a, I, V>,
331}
332
333impl<'a, I: EntityId, V> Iterator for Ids<'a, I, V> {
334    type Item = I;
335    fn next(&mut self) -> Option<I> {
336        self.vals.next().map(|x| x.0)
337    }
338}
339
340impl<'a, I: EntityId, V> DoubleEndedIterator for Ids<'a, I, V> {
341    fn next_back(&mut self) -> Option<I> {
342        self.vals.next_back().map(|x| x.0)
343    }
344}
345
346#[derive(Clone, Debug)]
347pub struct IntoIds<I, V> {
348    vals: IntoIter<I, V>,
349}
350
351impl<I: EntityId, V> Iterator for IntoIds<I, V> {
352    type Item = I;
353    fn next(&mut self) -> Option<I> {
354        self.vals.next().map(|x| x.0)
355    }
356}
357
358impl<I: EntityId, V> DoubleEndedIterator for IntoIds<I, V> {
359    fn next_back(&mut self) -> Option<I> {
360        self.vals.next_back().map(|x| x.0)
361    }
362}
363
364#[derive(Clone, Debug)]
365pub struct Values<'a, I, V> {
366    vals: Iter<'a, I, V>,
367}
368
369impl<'a, I: EntityId, V> Iterator for Values<'a, I, V> {
370    type Item = &'a V;
371    fn next(&mut self) -> Option<&'a V> {
372        self.vals.next().map(|x| x.1)
373    }
374}
375
376impl<'a, I: EntityId, V> DoubleEndedIterator for Values<'a, I, V> {
377    fn next_back(&mut self) -> Option<&'a V> {
378        self.vals.next_back().map(|x| x.1)
379    }
380}
381
382#[derive(Debug)]
383pub struct ValuesMut<'a, I, V> {
384    vals: IterMut<'a, I, V>,
385}
386
387impl<'a, I: EntityId, V> Iterator for ValuesMut<'a, I, V> {
388    type Item = &'a mut V;
389    fn next(&mut self) -> Option<&'a mut V> {
390        self.vals.next().map(|x| x.1)
391    }
392}
393
394impl<'a, I: EntityId, V> DoubleEndedIterator for ValuesMut<'a, I, V> {
395    fn next_back(&mut self) -> Option<&'a mut V> {
396        self.vals.next_back().map(|x| x.1)
397    }
398}
399
400#[derive(Clone, Debug)]
401pub struct IntoValues<I, V> {
402    vals: IntoIter<I, V>,
403}
404
405impl<I: EntityId, V> Iterator for IntoValues<I, V> {
406    type Item = V;
407    fn next(&mut self) -> Option<V> {
408        self.vals.next().map(|x| x.1)
409    }
410}
411
412impl<I: EntityId, V> DoubleEndedIterator for IntoValues<I, V> {
413    fn next_back(&mut self) -> Option<V> {
414        self.vals.next_back().map(|x| x.1)
415    }
416}
417
418impl<I: EntityId, V> FromIterator<(I, V)> for EntityPartVec<I, V> {
419    fn from_iter<T>(iter: T) -> Self
420    where
421        T: IntoIterator<Item = (I, V)>,
422    {
423        let mut res = Self::new();
424        for (k, v) in iter {
425            res.insert(k, v);
426        }
427        res
428    }
429}
430
431impl<I: EntityId, V> Extend<(I, V)> for EntityPartVec<I, V> {
432    fn extend<T>(&mut self, iter: T)
433    where
434        T: IntoIterator<Item = (I, V)>,
435    {
436        for (k, v) in iter {
437            self.insert(k, v);
438        }
439    }
440}