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    pub fn new() -> Self {
66        Self {
67            data: Vec::new(),
68            _phantom: PhantomData,
69        }
70    }
71
72    /// Creates an empty `EntityVec` with space for at least `capacity` items.
73    pub fn with_capacity(capacity: usize) -> Self {
74        Self {
75            data: Vec::with_capacity(capacity),
76            _phantom: PhantomData,
77        }
78    }
79
80    /// Returns the number of values stored.
81    #[inline]
82    pub fn len(&self) -> usize {
83        self.data.len()
84    }
85
86    /// Returns the capacity of the backing vector.
87    #[inline]
88    pub fn capacity(&self) -> usize {
89        self.data.capacity()
90    }
91
92    /// Returns `true` if no values are stored.
93    #[inline]
94    pub fn is_empty(&self) -> bool {
95        self.data.is_empty()
96    }
97
98    /// Reserves capacity for at least `additional` more values.
99    pub fn reserve(&mut self, additional: usize) {
100        self.data.reserve(additional);
101    }
102
103    /// Shrinks the backing vector to fit its length.
104    pub fn shrink_to_fit(&mut self) {
105        self.data.shrink_to_fit();
106    }
107
108    /// Appends `value` to the end of the vector.
109    pub fn push(&mut self, value: V) {
110        self.data.push(value);
111    }
112
113    /// Removes and returns the last value, or `None` if empty.
114    pub fn pop(&mut self) -> Option<V> {
115        self.data.pop()
116    }
117
118    /// Returns the value for `entity_id`, or `None` if this vector is not long enough.
119    pub fn get(&self, entity_id: EntityId<E>) -> Option<&V> {
120        self.data.get(entity_id.0)
121    }
122
123    /// Returns the mutable value for `entity_id`, or `None` if this vector is not long enough.
124    pub fn get_mut(&mut self, entity_id: EntityId<E>) -> Option<&mut V> {
125        self.data.get_mut(entity_id.0)
126    }
127
128    /// Returns the last value, or `None` if empty.
129    pub fn last(&self) -> Option<&V> {
130        self.data.last()
131    }
132
133    /// Returns the last value mutably, or `None` if empty.
134    pub fn last_mut(&mut self) -> Option<&mut V> {
135        self.data.last_mut()
136    }
137
138    /// Returns the backing slice.
139    pub fn as_slice(&self) -> &[V] {
140        &self.data
141    }
142
143    /// Returns the backing slice mutably.
144    pub fn as_mut_slice(&mut self) -> &mut [V] {
145        &mut self.data
146    }
147
148    /// Returns an iterator over the stored values.
149    pub fn iter(&self) -> std::slice::Iter<'_, V> {
150        self.data.iter()
151    }
152
153    /// Returns a mutable iterator over the stored values.
154    pub fn iter_mut(&mut self) -> std::slice::IterMut<'_, V> {
155        self.data.iter_mut()
156    }
157
158    /// Clears the vector, removing all values.
159    pub fn clear(&mut self) {
160        self.data.clear();
161    }
162
163    /// Truncates the vector to `len` items.
164    pub fn truncate(&mut self, len: usize) {
165        self.data.truncate(len);
166    }
167
168    /// Extends the vector with values from `iter`, assigning contiguous IDs to new items.
169    pub fn extend<I>(&mut self, iter: I)
170    where
171        I: IntoIterator<Item = V>,
172    {
173        self.data.extend(iter);
174    }
175
176    /// Resizes the vector to `new_len`, cloning `value` as needed.
177    pub fn resize(&mut self, new_len: usize, value: V)
178    where
179        V: Clone,
180    {
181        self.data.resize(new_len, value);
182    }
183
184    /// Resizes the vector to `new_len`, generating values with `f` as needed.
185    pub fn resize_with<F>(&mut self, new_len: usize, f: F)
186    where
187        F: FnMut() -> V,
188    {
189        self.data.resize_with(new_len, f);
190    }
191
192    /// Returns `true` if the vector contains `value`.
193    pub fn contains(&self, value: &V) -> bool
194    where
195        V: PartialEq,
196    {
197        self.data.contains(value)
198    }
199
200    /// Consumes the `EntityVec` and returns the backing `Vec`.
201    pub fn into_vec(self) -> Vec<V> {
202        self.data
203    }
204}
205
206impl<E: Entity, V> Default for EntityVec<E, V> {
207    fn default() -> Self {
208        Self::new()
209    }
210}
211
212impl<E: Entity, V: Debug> Debug for EntityVec<E, V> {
213    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
214        self.data.fmt(f)
215    }
216}
217
218impl<E: Entity, V> From<Vec<V>> for EntityVec<E, V> {
219    fn from(data: Vec<V>) -> Self {
220        Self {
221            data,
222            _phantom: PhantomData,
223        }
224    }
225}
226
227impl<E: Entity, V> From<EntityVec<E, V>> for Vec<V> {
228    fn from(value: EntityVec<E, V>) -> Self {
229        value.data
230    }
231}
232
233impl<E: Entity, V> FromIterator<V> for EntityVec<E, V> {
234    fn from_iter<I: IntoIterator<Item = V>>(iter: I) -> Self {
235        Self::from(Vec::from_iter(iter))
236    }
237}
238
239impl<E: Entity, V> Extend<V> for EntityVec<E, V> {
240    fn extend<I: IntoIterator<Item = V>>(&mut self, iter: I) {
241        self.data.extend(iter);
242    }
243}
244
245impl<E: Entity, V> Index<EntityId<E>> for EntityVec<E, V> {
246    type Output = V;
247
248    fn index(&self, index: EntityId<E>) -> &Self::Output {
249        &self.data[index.0]
250    }
251}
252
253impl<E: Entity, V> IndexMut<EntityId<E>> for EntityVec<E, V> {
254    fn index_mut(&mut self, index: EntityId<E>) -> &mut Self::Output {
255        &mut self.data[index.0]
256    }
257}
258
259impl<E: Entity, V> IntoIterator for EntityVec<E, V> {
260    type Item = V;
261    type IntoIter = std::vec::IntoIter<V>;
262
263    fn into_iter(self) -> Self::IntoIter {
264        self.data.into_iter()
265    }
266}
267
268impl<'a, E: Entity, V> IntoIterator for &'a EntityVec<E, V> {
269    type Item = &'a V;
270    type IntoIter = std::slice::Iter<'a, V>;
271
272    fn into_iter(self) -> Self::IntoIter {
273        self.iter()
274    }
275}
276
277impl<'a, E: Entity, V> IntoIterator for &'a mut EntityVec<E, V> {
278    type Item = &'a mut V;
279    type IntoIter = std::slice::IterMut<'a, V>;
280
281    fn into_iter(self) -> Self::IntoIter {
282        self.iter_mut()
283    }
284}
285
286#[cfg(test)]
287mod tests {
288    use super::EntityVec;
289    use crate::define_entity;
290    use crate::entity::EntityId;
291
292    define_entity!(TestEntity);
293    #[test]
294    fn new_is_empty() {
295        let vec = EntityVec::<TestEntity, i32>::new();
296        assert_eq!(vec.len(), 0);
297        assert!(vec.is_empty());
298        assert_eq!(vec.capacity(), 0);
299    }
300
301    #[test]
302    fn with_capacity_sets_initial_capacity() {
303        let vec = EntityVec::<TestEntity, i32>::with_capacity(8);
304        assert_eq!(vec.len(), 0);
305        assert!(vec.capacity() >= 8);
306    }
307
308    #[test]
309    fn push_appends_values_in_order() {
310        let mut vec = EntityVec::<TestEntity, &'static str>::new();
311        vec.push("zero");
312        vec.push("one");
313        vec.push("two");
314
315        assert_eq!(vec.len(), 3);
316        assert_eq!(vec[EntityId::new(0)], "zero");
317        assert_eq!(vec[EntityId::new(1)], "one");
318        assert_eq!(vec[EntityId::new(2)], "two");
319    }
320
321    #[test]
322    fn get_and_get_mut_are_bounds_checked() {
323        let mut vec = EntityVec::<TestEntity, i32>::new();
324        vec.push(10);
325        vec.push(20);
326        let id0 = EntityId::new(0);
327        let id1 = EntityId::new(1);
328
329        assert_eq!(vec.get(id0), Some(&10));
330        assert_eq!(vec.get(id1), Some(&20));
331        assert_eq!(vec.get(EntityId::new(2)), None);
332
333        *vec.get_mut(id1).unwrap() = 99;
334        assert_eq!(vec.get(id1), Some(&99));
335        assert_eq!(vec.get_mut(EntityId::new(2)), None);
336    }
337
338    #[test]
339    fn index_and_index_mut_use_entity_ids() {
340        let mut vec = EntityVec::<TestEntity, i32>::new();
341        vec.push(1);
342        vec.push(2);
343        let id0 = EntityId::new(0);
344        let id1 = EntityId::new(1);
345
346        vec[id1] = 7;
347
348        assert_eq!(vec[id0], 1);
349        assert_eq!(vec[id1], 7);
350    }
351
352    #[test]
353    fn pop_last_last_mut_and_clear_work() {
354        let mut vec = EntityVec::<TestEntity, String>::new();
355        vec.push(String::from("a"));
356        vec.push(String::from("b"));
357
358        assert_eq!(vec.last().map(String::as_str), Some("b"));
359        vec.last_mut().unwrap().push('!');
360        assert_eq!(vec.last().map(String::as_str), Some("b!"));
361        assert_eq!(vec.pop(), Some(String::from("b!")));
362        assert_eq!(vec.pop(), Some(String::from("a")));
363        assert_eq!(vec.pop(), None);
364
365        vec.push(String::from("c"));
366        vec.clear();
367        assert!(vec.is_empty());
368        assert_eq!(vec.last(), None);
369        assert_eq!(vec.last_mut(), None);
370    }
371
372    #[test]
373    fn reserve_and_shrink_to_fit_forward_to_backing_vec() {
374        let mut vec = EntityVec::<TestEntity, i32>::new();
375        vec.reserve(16);
376        assert!(vec.capacity() >= 16);
377
378        vec.extend(0..4);
379        vec.shrink_to_fit();
380        assert!(vec.capacity() >= vec.len());
381    }
382
383    #[test]
384    fn as_slice_and_as_mut_slice_expose_backing_storage() {
385        let mut vec = EntityVec::<TestEntity, i32>::from(vec![1, 2, 3]);
386        assert_eq!(vec.as_slice(), &[1, 2, 3]);
387
388        vec.as_mut_slice()[1] = 9;
389        assert_eq!(vec.as_slice(), &[1, 9, 3]);
390    }
391
392    #[test]
393    fn iter_and_iter_mut_visit_values_in_order() {
394        let mut vec = EntityVec::<TestEntity, i32>::from(vec![1, 2, 3]);
395        let values: Vec<_> = vec.iter().copied().collect();
396        assert_eq!(values, vec![1, 2, 3]);
397
398        for value in vec.iter_mut() {
399            *value *= 2;
400        }
401
402        assert_eq!(vec.as_slice(), &[2, 4, 6]);
403    }
404
405    #[test]
406    fn truncate_removes_trailing_items() {
407        let mut vec = EntityVec::<TestEntity, i32>::from(vec![1, 2, 3, 4]);
408        vec.truncate(2);
409
410        assert_eq!(vec.len(), 2);
411        assert_eq!(vec.get(EntityId::new(0)), Some(&1));
412        assert_eq!(vec.get(EntityId::new(1)), Some(&2));
413        assert_eq!(vec.get(EntityId::new(2)), None);
414    }
415
416    #[test]
417    fn contains_checks_values() {
418        let vec = EntityVec::<TestEntity, i32>::from(vec![3, 5, 8]);
419        assert!(vec.contains(&5));
420        assert!(!vec.contains(&13));
421    }
422
423    #[test]
424    fn from_iter_and_inherent_extend_append_in_order() {
425        let mut vec: EntityVec<TestEntity, i32> = [1, 2].into_iter().collect();
426        EntityVec::extend(&mut vec, [3, 4]);
427
428        assert_eq!(vec.as_slice(), &[1, 2, 3, 4]);
429        vec.push(5);
430        assert_eq!(vec[EntityId::new(4)], 5);
431    }
432
433    #[test]
434    fn trait_extend_appends_values() {
435        let mut vec = EntityVec::<TestEntity, i32>::new();
436        <EntityVec<TestEntity, i32> as Extend<i32>>::extend(&mut vec, [7, 8, 9]);
437        assert_eq!(vec.as_slice(), &[7, 8, 9]);
438    }
439
440    #[test]
441    fn into_vec_and_from_vec_round_trip() {
442        let vec = EntityVec::<TestEntity, i32>::from(vec![4, 5, 6]);
443        let raw = vec.into_vec();
444        assert_eq!(raw, vec![4, 5, 6]);
445
446        let wrapped = EntityVec::<TestEntity, i32>::from(raw.clone());
447        let round_trip: Vec<_> = wrapped.into();
448        assert_eq!(round_trip, raw);
449    }
450
451    #[test]
452    fn into_iterator_variants_match_backing_vec_order() {
453        let mut vec = EntityVec::<TestEntity, i32>::from(vec![1, 2, 3]);
454
455        let shared: Vec<_> = (&vec).into_iter().copied().collect();
456        assert_eq!(shared, vec![1, 2, 3]);
457
458        for value in &mut vec {
459            *value += 10;
460        }
461        assert_eq!(vec.as_slice(), &[11, 12, 13]);
462
463        let owned: Vec<_> = vec.into_iter().collect();
464        assert_eq!(owned, vec![11, 12, 13]);
465    }
466
467    #[test]
468    fn debug_delegates_to_backing_vec() {
469        let vec = EntityVec::<TestEntity, i32>::from(vec![1, 2, 3]);
470        assert_eq!(format!("{vec:?}"), "[1, 2, 3]");
471    }
472
473    #[test]
474    fn clone_and_eq_compare_stored_values() {
475        let vec = EntityVec::<TestEntity, i32>::from(vec![1, 2, 3]);
476        let clone = vec.clone();
477
478        assert_eq!(vec, clone);
479        assert_ne!(vec, EntityVec::<TestEntity, i32>::from(vec![1, 2]));
480    }
481
482    #[test]
483    fn resize_and_resize_with_extend_storage_by_index() {
484        let mut vec = EntityVec::<TestEntity, i32>::new();
485        vec.resize(3, 7);
486        assert_eq!(vec.as_slice(), &[7, 7, 7]);
487
488        let mut next = 10;
489        vec.resize_with(5, || {
490            let value = next;
491            next += 1;
492            value
493        });
494
495        assert_eq!(vec.as_slice(), &[7, 7, 7, 10, 11]);
496    }
497}
ixa/data_structures/entity_vec.rs

ixa/data_structures/
entity_vec.rs
