ixa/data_structures/
entity_vec.rs

1/*!
2
3An `EntityVec<E: Entity, V>` is a vector of values of type `V` that can only be indexed by keys of
4type `EntityId<E>`.
5
6An `EntityVec<E: Entity, V>` is a thin wrapper around a `Vec<V>` that enforces type safety of the
7indexing (key) values. The most common `Vec<V>` methods are implemented.
8
9Importantly, while `EntityVec<E: Entity, V>` can be _indexed_ by an `EntityId<E>` value, it cannot
10construct an `EntityId<E>` value itself, because it does not guarantee that its length does not
11exceed the range of valid `EntityId<E>` values. This allows methods like `EntityVec::push` and
12`EntityVec::extend` that extend the length of the vector to remain unconstrained. If you need to be
13able to retrieve the `EntityId<E>` that a value is associated with (e.g. by iterating over
14(entity ID, value) pairs), use an [`EntityMap`](super::entity_map::EntityMap) instead.
15
16For a hash-map-like API, see [`EntityMap`](super::entity_map::EntityMap).
17
18## Example
19
20Imagine you have a `Person` entity, and you want an efficient way to store for each `PersonId` a
21`Vec<Itinerary>` representing different itineraries associated with that person. You might
22initialize `itineraries_by_person: EntityVec<Person, Vec<Itinerary>>` during population creation, by
23subscribing to the `EntityCreationEvent<Person>` event, or as a separate iteration over an existing
24population.
25
26```rust,ignore
27use ixa::data_structures::entity_vec::EntityVec;
28
29let mut itineraries_by_person: EntityVec<Person, Vec<Itinerary>> = EntityVec::new();
30
31// Populate in entity-id order. For example, this could be done while creating people
32// or while iterating over an existing population.
33for person_id in context.get_entity_iterator::<Person>() {
34    let itinerary_list = compute_itineraries_for_person(person_id);
35    itineraries_by_person.push(itinerary_list);
36}
37
38// Later, given an existing PersonId:
39let person_id: PersonId = /* fetch the `PersonId` somehow. */;
40
41if let Some(itineraries) = itineraries_by_person.get_mut(person_id) {
42    itineraries.push(/* some Itinerary */);
43}
44```
45
46*/
47
48use std::fmt::{self, Debug};
49use std::marker::PhantomData;
50use std::ops::{Index, IndexMut};
51
52use crate::entity::{Entity, EntityId};
53
54/**
55A `Vec`-backed collection indexed by `EntityId<E>`.
56*/
57#[derive(Clone, PartialEq, Eq, Hash)]
58pub struct EntityVec<E: Entity, V> {
59    data: Vec<V>,
60    _phantom: PhantomData<E>,
61}
62
63impl<E: Entity, V> EntityVec<E, V> {
64    /// Creates an empty `EntityVec`.
65    #[must_use]
66    pub fn new() -> Self {
67        Self {
68            data: Vec::new(),
69            _phantom: PhantomData,
70        }
71    }
72
73    /// Creates an empty `EntityVec` with space for at least `capacity` items.
74    #[must_use]
75    pub fn with_capacity(capacity: usize) -> Self {
76        Self {
77            data: Vec::with_capacity(capacity),
78            _phantom: PhantomData,
79        }
80    }
81
82    /// Returns the number of values stored.
83    #[inline]
84    #[must_use]
85    pub fn len(&self) -> usize {
86        self.data.len()
87    }
88
89    /// Returns the capacity of the backing vector.
90    #[inline]
91    #[must_use]
92    pub fn capacity(&self) -> usize {
93        self.data.capacity()
94    }
95
96    /// Returns `true` if no values are stored.
97    #[inline]
98    #[must_use]
99    pub fn is_empty(&self) -> bool {
100        self.data.is_empty()
101    }
102
103    /// Reserves capacity for at least `additional` more values.
104    pub fn reserve(&mut self, additional: usize) {
105        self.data.reserve(additional);
106    }
107
108    /// Shrinks the backing vector to fit its length.
109    pub fn shrink_to_fit(&mut self) {
110        self.data.shrink_to_fit();
111    }
112
113    /// Appends `value` to the end of the vector.
114    pub fn push(&mut self, value: V) {
115        self.data.push(value);
116    }
117
118    /// Removes and returns the last value, or `None` if empty.
119    #[must_use]
120    pub fn pop(&mut self) -> Option<V> {
121        self.data.pop()
122    }
123
124    /// Returns the value for `entity_id`, or `None` if this vector is not long enough.
125    #[must_use]
126    pub fn get(&self, entity_id: EntityId<E>) -> Option<&V> {
127        self.data.get(entity_id.0)
128    }
129
130    /// Returns the mutable value for `entity_id`, or `None` if this vector is not long enough.
131    #[must_use]
132    pub fn get_mut(&mut self, entity_id: EntityId<E>) -> Option<&mut V> {
133        self.data.get_mut(entity_id.0)
134    }
135
136    /// Returns the last value, or `None` if empty.
137    #[must_use]
138    pub fn last(&self) -> Option<&V> {
139        self.data.last()
140    }
141
142    /// Returns the last value mutably, or `None` if empty.
143    #[must_use]
144    pub fn last_mut(&mut self) -> Option<&mut V> {
145        self.data.last_mut()
146    }
147
148    /// Returns the backing slice.
149    #[must_use]
150    pub fn as_slice(&self) -> &[V] {
151        &self.data
152    }
153
154    /// Returns the backing slice mutably.
155    #[must_use]
156    pub fn as_mut_slice(&mut self) -> &mut [V] {
157        &mut self.data
158    }
159
160    /// Returns an iterator over the stored values.
161    pub fn iter(&self) -> std::slice::Iter<'_, V> {
162        self.data.iter()
163    }
164
165    /// Returns a mutable iterator over the stored values.
166    pub fn iter_mut(&mut self) -> std::slice::IterMut<'_, V> {
167        self.data.iter_mut()
168    }
169
170    /// Clears the vector, removing all values.
171    pub fn clear(&mut self) {
172        self.data.clear();
173    }
174
175    /// Truncates the vector to `len` items.
176    pub fn truncate(&mut self, len: usize) {
177        self.data.truncate(len);
178    }
179
180    /// Extends the vector with values from `iter`, assigning contiguous IDs to new items.
181    pub fn extend<I>(&mut self, iter: I)
182    where
183        I: IntoIterator<Item = V>,
184    {
185        self.data.extend(iter);
186    }
187
188    /// Resizes the vector to `new_len`, cloning `value` as needed.
189    pub fn resize(&mut self, new_len: usize, value: V)
190    where
191        V: Clone,
192    {
193        self.data.resize(new_len, value);
194    }
195
196    /// Resizes the vector to `new_len`, generating values with `f` as needed.
197    pub fn resize_with<F>(&mut self, new_len: usize, f: F)
198    where
199        F: FnMut() -> V,
200    {
201        self.data.resize_with(new_len, f);
202    }
203
204    /// Returns `true` if the vector contains `value`.
205    #[must_use]
206    pub fn contains(&self, value: &V) -> bool
207    where
208        V: PartialEq,
209    {
210        self.data.contains(value)
211    }
212
213    /// Consumes the `EntityVec` and returns the backing `Vec`.
214    #[must_use]
215    pub fn into_vec(self) -> Vec<V> {
216        self.data
217    }
218}
219
220impl<E: Entity, V> Default for EntityVec<E, V> {
221    fn default() -> Self {
222        Self::new()
223    }
224}
225
226impl<E: Entity, V: Debug> Debug for EntityVec<E, V> {
227    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
228        self.data.fmt(f)
229    }
230}
231
232impl<E: Entity, V> From<Vec<V>> for EntityVec<E, V> {
233    fn from(data: Vec<V>) -> Self {
234        Self {
235            data,
236            _phantom: PhantomData,
237        }
238    }
239}
240
241impl<E: Entity, V> From<EntityVec<E, V>> for Vec<V> {
242    fn from(value: EntityVec<E, V>) -> Self {
243        value.data
244    }
245}
246
247impl<E: Entity, V> FromIterator<V> for EntityVec<E, V> {
248    fn from_iter<I: IntoIterator<Item = V>>(iter: I) -> Self {
249        Self::from(Vec::from_iter(iter))
250    }
251}
252
253impl<E: Entity, V> Extend<V> for EntityVec<E, V> {
254    fn extend<I: IntoIterator<Item = V>>(&mut self, iter: I) {
255        self.data.extend(iter);
256    }
257}
258
259impl<E: Entity, V> Index<EntityId<E>> for EntityVec<E, V> {
260    type Output = V;
261
262    fn index(&self, index: EntityId<E>) -> &Self::Output {
263        &self.data[index.0]
264    }
265}
266
267impl<E: Entity, V> IndexMut<EntityId<E>> for EntityVec<E, V> {
268    fn index_mut(&mut self, index: EntityId<E>) -> &mut Self::Output {
269        &mut self.data[index.0]
270    }
271}
272
273impl<E: Entity, V> IntoIterator for EntityVec<E, V> {
274    type Item = V;
275    type IntoIter = std::vec::IntoIter<V>;
276
277    fn into_iter(self) -> Self::IntoIter {
278        self.data.into_iter()
279    }
280}
281
282impl<'a, E: Entity, V> IntoIterator for &'a EntityVec<E, V> {
283    type Item = &'a V;
284    type IntoIter = std::slice::Iter<'a, V>;
285
286    fn into_iter(self) -> Self::IntoIter {
287        self.iter()
288    }
289}
290
291impl<'a, E: Entity, V> IntoIterator for &'a mut EntityVec<E, V> {
292    type Item = &'a mut V;
293    type IntoIter = std::slice::IterMut<'a, V>;
294
295    fn into_iter(self) -> Self::IntoIter {
296        self.iter_mut()
297    }
298}
299
300#[cfg(test)]
301mod tests {
302    use super::EntityVec;
303    use crate::define_entity;
304    use crate::entity::EntityId;
305
306    define_entity!(TestEntity);
307    #[test]
308    fn new_is_empty() {
309        let vec = EntityVec::<TestEntity, i32>::new();
310        assert_eq!(vec.len(), 0);
311        assert!(vec.is_empty());
312        assert_eq!(vec.capacity(), 0);
313    }
314
315    #[test]
316    fn with_capacity_sets_initial_capacity() {
317        let vec = EntityVec::<TestEntity, i32>::with_capacity(8);
318        assert_eq!(vec.len(), 0);
319        assert!(vec.capacity() >= 8);
320    }
321
322    #[test]
323    fn push_appends_values_in_order() {
324        let mut vec = EntityVec::<TestEntity, &'static str>::new();
325        vec.push("zero");
326        vec.push("one");
327        vec.push("two");
328
329        assert_eq!(vec.len(), 3);
330        assert_eq!(vec[EntityId::new(0)], "zero");
331        assert_eq!(vec[EntityId::new(1)], "one");
332        assert_eq!(vec[EntityId::new(2)], "two");
333    }
334
335    #[test]
336    fn get_and_get_mut_are_bounds_checked() {
337        let mut vec = EntityVec::<TestEntity, i32>::new();
338        vec.push(10);
339        vec.push(20);
340        let id0 = EntityId::new(0);
341        let id1 = EntityId::new(1);
342
343        assert_eq!(vec.get(id0), Some(&10));
344        assert_eq!(vec.get(id1), Some(&20));
345        assert_eq!(vec.get(EntityId::new(2)), None);
346
347        *vec.get_mut(id1).unwrap() = 99;
348        assert_eq!(vec.get(id1), Some(&99));
349        assert_eq!(vec.get_mut(EntityId::new(2)), None);
350    }
351
352    #[test]
353    fn index_and_index_mut_use_entity_ids() {
354        let mut vec = EntityVec::<TestEntity, i32>::new();
355        vec.push(1);
356        vec.push(2);
357        let id0 = EntityId::new(0);
358        let id1 = EntityId::new(1);
359
360        vec[id1] = 7;
361
362        assert_eq!(vec[id0], 1);
363        assert_eq!(vec[id1], 7);
364    }
365
366    #[test]
367    fn pop_last_last_mut_and_clear_work() {
368        let mut vec = EntityVec::<TestEntity, String>::new();
369        vec.push(String::from("a"));
370        vec.push(String::from("b"));
371
372        assert_eq!(vec.last().map(String::as_str), Some("b"));
373        vec.last_mut().unwrap().push('!');
374        assert_eq!(vec.last().map(String::as_str), Some("b!"));
375        assert_eq!(vec.pop(), Some(String::from("b!")));
376        assert_eq!(vec.pop(), Some(String::from("a")));
377        assert_eq!(vec.pop(), None);
378
379        vec.push(String::from("c"));
380        vec.clear();
381        assert!(vec.is_empty());
382        assert_eq!(vec.last(), None);
383        assert_eq!(vec.last_mut(), None);
384    }
385
386    #[test]
387    fn reserve_and_shrink_to_fit_forward_to_backing_vec() {
388        let mut vec = EntityVec::<TestEntity, i32>::new();
389        vec.reserve(16);
390        assert!(vec.capacity() >= 16);
391
392        vec.extend(0..4);
393        vec.shrink_to_fit();
394        assert!(vec.capacity() >= vec.len());
395    }
396
397    #[test]
398    fn as_slice_and_as_mut_slice_expose_backing_storage() {
399        let mut vec = EntityVec::<TestEntity, i32>::from(vec![1, 2, 3]);
400        assert_eq!(vec.as_slice(), &[1, 2, 3]);
401
402        vec.as_mut_slice()[1] = 9;
403        assert_eq!(vec.as_slice(), &[1, 9, 3]);
404    }
405
406    #[test]
407    fn iter_and_iter_mut_visit_values_in_order() {
408        let mut vec = EntityVec::<TestEntity, i32>::from(vec![1, 2, 3]);
409        let values: Vec<_> = vec.iter().copied().collect();
410        assert_eq!(values, vec![1, 2, 3]);
411
412        for value in vec.iter_mut() {
413            *value *= 2;
414        }
415
416        assert_eq!(vec.as_slice(), &[2, 4, 6]);
417    }
418
419    #[test]
420    fn truncate_removes_trailing_items() {
421        let mut vec = EntityVec::<TestEntity, i32>::from(vec![1, 2, 3, 4]);
422        vec.truncate(2);
423
424        assert_eq!(vec.len(), 2);
425        assert_eq!(vec.get(EntityId::new(0)), Some(&1));
426        assert_eq!(vec.get(EntityId::new(1)), Some(&2));
427        assert_eq!(vec.get(EntityId::new(2)), None);
428    }
429
430    #[test]
431    fn contains_checks_values() {
432        let vec = EntityVec::<TestEntity, i32>::from(vec![3, 5, 8]);
433        assert!(vec.contains(&5));
434        assert!(!vec.contains(&13));
435    }
436
437    #[test]
438    fn from_iter_and_inherent_extend_append_in_order() {
439        let mut vec: EntityVec<TestEntity, i32> = [1, 2].into_iter().collect();
440        EntityVec::extend(&mut vec, [3, 4]);
441
442        assert_eq!(vec.as_slice(), &[1, 2, 3, 4]);
443        vec.push(5);
444        assert_eq!(vec[EntityId::new(4)], 5);
445    }
446
447    #[test]
448    fn trait_extend_appends_values() {
449        let mut vec = EntityVec::<TestEntity, i32>::new();
450        <EntityVec<TestEntity, i32> as Extend<i32>>::extend(&mut vec, [7, 8, 9]);
451        assert_eq!(vec.as_slice(), &[7, 8, 9]);
452    }
453
454    #[test]
455    fn into_vec_and_from_vec_round_trip() {
456        let vec = EntityVec::<TestEntity, i32>::from(vec![4, 5, 6]);
457        let raw = vec.into_vec();
458        assert_eq!(raw, vec![4, 5, 6]);
459
460        let wrapped = EntityVec::<TestEntity, i32>::from(raw.clone());
461        let round_trip: Vec<_> = wrapped.into();
462        assert_eq!(round_trip, raw);
463    }
464
465    #[test]
466    fn into_iterator_variants_match_backing_vec_order() {
467        let mut vec = EntityVec::<TestEntity, i32>::from(vec![1, 2, 3]);
468
469        let shared: Vec<_> = (&vec).into_iter().copied().collect();
470        assert_eq!(shared, vec![1, 2, 3]);
471
472        for value in &mut vec {
473            *value += 10;
474        }
475        assert_eq!(vec.as_slice(), &[11, 12, 13]);
476
477        let owned: Vec<_> = vec.into_iter().collect();
478        assert_eq!(owned, vec![11, 12, 13]);
479    }
480
481    #[test]
482    fn debug_delegates_to_backing_vec() {
483        let vec = EntityVec::<TestEntity, i32>::from(vec![1, 2, 3]);
484        assert_eq!(format!("{vec:?}"), "[1, 2, 3]");
485    }
486
487    #[test]
488    fn clone_and_eq_compare_stored_values() {
489        let vec = EntityVec::<TestEntity, i32>::from(vec![1, 2, 3]);
490        let clone = vec.clone();
491
492        assert_eq!(vec, clone);
493        assert_ne!(vec, EntityVec::<TestEntity, i32>::from(vec![1, 2]));
494    }
495
496    #[test]
497    fn resize_and_resize_with_extend_storage_by_index() {
498        let mut vec = EntityVec::<TestEntity, i32>::new();
499        vec.resize(3, 7);
500        assert_eq!(vec.as_slice(), &[7, 7, 7]);
501
502        let mut next = 10;
503        vec.resize_with(5, || {
504            let value = next;
505            next += 1;
506            value
507        });
508
509        assert_eq!(vec.as_slice(), &[7, 7, 7, 10, 11]);
510    }
511}
ixa/data_structures/entity_vec.rs

ixa/data_structures/
entity_vec.rs
