Skip to main content

prjcombine_entity/
map.rs

1//! An [`IndexMap`] with strongly-typed indices.
2use core::hash::{BuildHasher, Hash};
3use core::marker::PhantomData;
4use core::ops::{Index, IndexMut};
5
6use std::collections::hash_map::RandomState;
7use std::fmt;
8
9use indexmap::Equivalent;
10use indexmap::map::{self as inner, IndexMap};
11
12use crate::id::EntityRange;
13use crate::{EntityId, EntityVec};
14
15/// An [`IndexMap`] with strongly-typed indices.
16///
17/// An `EntityMap` assigns sequential IDs to each inserted `(K, V)` pair. Entries may be looked up
18/// either by the key `K`, or the index `I` (by means of the [`Index`] trait).
19///
20/// ## Accessors at a glance
21///
22/// | **Accessor**                    | *Requires* | *Obtains*             |
23/// |---------------------------------|------------|-----------------------|
24/// | `&map[id]`                      | `I`        | `&V`                  |
25/// | `&mut map[id]`                  | `I`        | `&mut V`              |
26/// | [`key`][EntityMap::key]         | `I`        | `&K`                  |
27/// | [`get`][EntityMap::get]         | `&K`       | `Option<(I, &V)>`     |
28/// | [`get_mut`][EntityMap::get_mut] | `&K`       | `Option<(I, &mut V)>` |
29#[derive(Clone)]
30pub struct EntityMap<I: EntityId, K: Hash + Eq, V, RS: BuildHasher = RandomState> {
31    map: IndexMap<K, V, RS>,
32    ids: PhantomData<I>,
33}
34
35impl<I, K, V, RS> EntityMap<I, K, V, RS>
36where
37    I: EntityId,
38    K: Hash + Eq,
39    RS: BuildHasher,
40{
41    pub fn with_hasher(h: RS) -> Self {
42        Self {
43            map: IndexMap::with_hasher(h),
44            ids: PhantomData,
45        }
46    }
47
48    pub fn with_capacity_and_hasher(n: usize, h: RS) -> Self {
49        Self {
50            map: IndexMap::with_capacity_and_hasher(n, h),
51            ids: PhantomData,
52        }
53    }
54
55    pub fn len(&self) -> usize {
56        self.map.len()
57    }
58
59    pub fn is_empty(&self) -> bool {
60        self.map.is_empty()
61    }
62
63    pub fn next_id(&self) -> I {
64        self.ids().end()
65    }
66
67    pub fn clear(&mut self) {
68        self.map.clear()
69    }
70
71    pub fn insert(&mut self, k: K, v: V) -> (I, Option<V>) {
72        let (i, v) = self.map.insert_full(k, v);
73        (I::from_idx(i), v)
74    }
75
76    #[track_caller]
77    pub fn insert_new(&mut self, k: K, v: V) -> I {
78        let (i, f) = self.insert(k, v);
79        assert!(f.is_none(), "key already present in EntityMap");
80        i
81    }
82
83    pub fn key(&self, id: I) -> &K {
84        self.map.get_index(id.to_idx()).unwrap().0
85    }
86
87    pub fn get<Q>(&self, key: &Q) -> Option<(I, &V)>
88    where
89        Q: ?Sized + Hash + Equivalent<K>,
90    {
91        let (i, _, v) = self.map.get_full(key)?;
92        Some((I::from_idx(i), v))
93    }
94
95    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<(I, &mut V)>
96    where
97        Q: ?Sized + Hash + Equivalent<K>,
98    {
99        let (i, _, v) = self.map.get_full_mut(key)?;
100        Some((I::from_idx(i), v))
101    }
102
103    pub fn get_full<Q>(&self, key: &Q) -> Option<(I, &K, &V)>
104    where
105        Q: ?Sized + Hash + Equivalent<K>,
106    {
107        let (i, k, v) = self.map.get_full(key)?;
108        Some((I::from_idx(i), k, v))
109    }
110
111    pub fn get_full_mut<Q>(&mut self, key: &Q) -> Option<(I, &K, &mut V)>
112    where
113        Q: ?Sized + Hash + Equivalent<K>,
114    {
115        let (i, k, v) = self.map.get_full_mut(key)?;
116        Some((I::from_idx(i), k, v))
117    }
118
119    pub fn entry(&mut self, key: K) -> Entry<'_, I, K, V> {
120        match self.map.entry(key) {
121            inner::Entry::Occupied(entry) => Entry::Occupied(OccupiedEntry(entry, PhantomData)),
122            inner::Entry::Vacant(entry) => Entry::Vacant(VacantEntry(entry, PhantomData)),
123        }
124    }
125
126    pub fn contains_key<Q>(&self, key: &Q) -> bool
127    where
128        Q: ?Sized + Hash + Equivalent<K>,
129    {
130        self.map.contains_key(key)
131    }
132
133    pub fn ids(&self) -> EntityRange<I> {
134        EntityRange::new(0, self.len())
135    }
136
137    pub fn iter(&self) -> Iter<'_, I, K, V> {
138        Iter {
139            vals: self.map.iter(),
140            pos: 0,
141            ids: PhantomData,
142        }
143    }
144
145    pub fn iter_mut(&mut self) -> IterMut<'_, I, K, V> {
146        IterMut {
147            vals: self.map.iter_mut(),
148            pos: 0,
149            ids: PhantomData,
150        }
151    }
152
153    pub fn keys(&self) -> indexmap::map::Keys<'_, K, V> {
154        self.map.keys()
155    }
156
157    pub fn into_keys(self) -> indexmap::map::IntoKeys<K, V> {
158        self.map.into_keys()
159    }
160
161    pub fn values(&self) -> indexmap::map::Values<'_, K, V> {
162        self.map.values()
163    }
164
165    pub fn values_mut(&mut self) -> indexmap::map::ValuesMut<'_, K, V> {
166        self.map.values_mut()
167    }
168
169    pub fn into_values(self) -> indexmap::map::IntoValues<K, V> {
170        self.map.into_values()
171    }
172
173    pub fn into_vec(self) -> EntityVec<I, (K, V)> {
174        self.into_iter().map(|(_, k, v)| (k, v)).collect()
175    }
176}
177
178impl<I, K, V> EntityMap<I, K, V>
179where
180    I: EntityId,
181    K: Hash + Eq,
182{
183    pub fn new() -> Self {
184        Self {
185            map: IndexMap::new(),
186            ids: PhantomData,
187        }
188    }
189
190    pub fn with_capacity(n: usize) -> Self {
191        Self {
192            map: IndexMap::with_capacity(n),
193            ids: PhantomData,
194        }
195    }
196}
197
198impl<I, K, V> Default for EntityMap<I, K, V>
199where
200    I: EntityId,
201    K: Hash + Eq,
202{
203    fn default() -> Self {
204        Self::new()
205    }
206}
207
208impl<I, K, V, RS> fmt::Debug for EntityMap<I, K, V, RS>
209where
210    I: EntityId,
211    K: Hash + Eq + fmt::Debug,
212    V: fmt::Debug,
213    RS: BuildHasher,
214{
215    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
216        fmt.debug_map()
217            .entries(self.iter().map(|(i, k, v)| (i, (k, v))))
218            .finish()
219    }
220}
221
222impl<I, K, V, RS, RS2> PartialEq<EntityMap<I, K, V, RS2>> for EntityMap<I, K, V, RS>
223where
224    I: EntityId,
225    K: Hash + Eq,
226    V: PartialEq,
227    RS: BuildHasher,
228    RS2: BuildHasher,
229{
230    fn eq(&self, other: &EntityMap<I, K, V, RS2>) -> bool {
231        self.iter().eq(other.iter())
232    }
233}
234
235impl<I, K, V, RS> Eq for EntityMap<I, K, V, RS>
236where
237    I: EntityId,
238    K: Hash + Eq,
239    V: Eq,
240    RS: BuildHasher,
241{
242}
243
244impl<I, K, V, RS> IntoIterator for EntityMap<I, K, V, RS>
245where
246    I: EntityId,
247    K: Hash + Eq,
248    RS: BuildHasher,
249{
250    type Item = (I, K, V);
251    type IntoIter = IntoIter<I, K, V>;
252    fn into_iter(self) -> Self::IntoIter {
253        IntoIter {
254            vals: self.map.into_iter(),
255            pos: 0,
256            ids: PhantomData,
257        }
258    }
259}
260
261impl<'a, I, K, V, RS> IntoIterator for &'a EntityMap<I, K, V, RS>
262where
263    I: EntityId,
264    K: Hash + Eq,
265    RS: BuildHasher,
266{
267    type Item = (I, &'a K, &'a V);
268    type IntoIter = Iter<'a, I, K, V>;
269    fn into_iter(self) -> Self::IntoIter {
270        self.iter()
271    }
272}
273
274impl<'a, I, K, V, RS> IntoIterator for &'a mut EntityMap<I, K, V, RS>
275where
276    I: EntityId,
277    K: Hash + Eq,
278    RS: BuildHasher,
279{
280    type Item = (I, &'a K, &'a mut V);
281    type IntoIter = IterMut<'a, I, K, V>;
282    fn into_iter(self) -> Self::IntoIter {
283        self.iter_mut()
284    }
285}
286
287impl<I, K, V, RS> Index<I> for EntityMap<I, K, V, RS>
288where
289    I: EntityId,
290    K: Hash + Eq,
291    RS: BuildHasher,
292{
293    type Output = V;
294    fn index(&self, index: I) -> &V {
295        self.map.index(index.to_idx())
296    }
297}
298
299impl<I, K, V, RS> IndexMut<I> for EntityMap<I, K, V, RS>
300where
301    I: EntityId,
302    K: Hash + Eq,
303    RS: BuildHasher,
304{
305    fn index_mut(&mut self, index: I) -> &mut V {
306        self.map.index_mut(index.to_idx())
307    }
308}
309
310#[derive(Clone, Debug)]
311pub struct Iter<'a, I, K: Hash, V> {
312    vals: indexmap::map::Iter<'a, K, V>,
313    pos: usize,
314    ids: PhantomData<I>,
315}
316
317impl<'a, I, K, V> Iterator for Iter<'a, I, K, V>
318where
319    I: EntityId,
320    K: Hash,
321{
322    type Item = (I, &'a K, &'a V);
323    fn next(&mut self) -> Option<(I, &'a K, &'a V)> {
324        let (key, val) = self.vals.next()?;
325        let id = I::from_idx(self.pos);
326        self.pos += 1;
327        Some((id, key, val))
328    }
329}
330
331impl<'a, I, K, V> DoubleEndedIterator for Iter<'a, I, K, V>
332where
333    I: EntityId,
334    K: Hash,
335{
336    fn next_back(&mut self) -> Option<(I, &'a K, &'a V)> {
337        let (key, val) = self.vals.next_back()?;
338        Some((I::from_idx(self.pos + self.vals.len()), key, val))
339    }
340}
341
342impl<'a, I, K, V> ExactSizeIterator for Iter<'a, I, K, V>
343where
344    I: EntityId,
345    K: Hash,
346{
347    fn len(&self) -> usize {
348        self.vals.len()
349    }
350}
351
352pub struct IterMut<'a, I, K: Hash, V> {
353    vals: indexmap::map::IterMut<'a, K, V>,
354    pos: usize,
355    ids: PhantomData<I>,
356}
357
358impl<'a, I, K, V> Iterator for IterMut<'a, I, K, V>
359where
360    I: EntityId,
361    K: Hash,
362{
363    type Item = (I, &'a K, &'a mut V);
364    fn next(&mut self) -> Option<(I, &'a K, &'a mut V)> {
365        let (key, val) = self.vals.next()?;
366        let id = I::from_idx(self.pos);
367        self.pos += 1;
368        Some((id, key, val))
369    }
370}
371
372impl<'a, I, K, V> DoubleEndedIterator for IterMut<'a, I, K, V>
373where
374    I: EntityId,
375    K: Hash,
376{
377    fn next_back(&mut self) -> Option<(I, &'a K, &'a mut V)> {
378        let (key, val) = self.vals.next_back()?;
379        Some((I::from_idx(self.pos + self.vals.len()), key, val))
380    }
381}
382
383impl<'a, I, K, V> ExactSizeIterator for IterMut<'a, I, K, V>
384where
385    I: EntityId,
386    K: Hash,
387{
388    fn len(&self) -> usize {
389        self.vals.len()
390    }
391}
392
393#[derive(Debug)]
394pub struct IntoIter<I, K: Hash, V> {
395    vals: indexmap::map::IntoIter<K, V>,
396    pos: usize,
397    ids: PhantomData<I>,
398}
399
400impl<I, K, V> Iterator for IntoIter<I, K, V>
401where
402    I: EntityId,
403    K: Hash,
404{
405    type Item = (I, K, V);
406    fn next(&mut self) -> Option<(I, K, V)> {
407        let (key, val) = self.vals.next()?;
408        let id = I::from_idx(self.pos);
409        self.pos += 1;
410        Some((id, key, val))
411    }
412}
413
414impl<I, K, V> DoubleEndedIterator for IntoIter<I, K, V>
415where
416    I: EntityId,
417    K: Hash,
418{
419    fn next_back(&mut self) -> Option<(I, K, V)> {
420        let (key, val) = self.vals.next_back()?;
421        Some((I::from_idx(self.pos + self.vals.len()), key, val))
422    }
423}
424
425impl<I, K, V> ExactSizeIterator for IntoIter<I, K, V>
426where
427    I: EntityId,
428    K: Hash,
429{
430    fn len(&self) -> usize {
431        self.vals.len()
432    }
433}
434
435impl<I, K, V, RS> FromIterator<(K, V)> for EntityMap<I, K, V, RS>
436where
437    I: EntityId,
438    K: Hash + Eq,
439    RS: BuildHasher + Default,
440{
441    fn from_iter<T>(iter: T) -> Self
442    where
443        T: IntoIterator<Item = (K, V)>,
444    {
445        Self {
446            map: IndexMap::from_iter(iter),
447            ids: PhantomData,
448        }
449    }
450}
451
452impl<I, K, V, RS> Extend<(K, V)> for EntityMap<I, K, V, RS>
453where
454    I: EntityId,
455    K: Hash + Eq,
456    RS: BuildHasher + Default,
457{
458    fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
459        self.map.extend(iter);
460    }
461}
462
463#[cfg(feature = "bincode")]
464mod bincode;
465
466pub enum Entry<'a, I, K, V> {
467    Occupied(OccupiedEntry<'a, I, K, V>),
468    Vacant(VacantEntry<'a, I, K, V>),
469}
470
471pub struct OccupiedEntry<'a, I, K, V>(inner::OccupiedEntry<'a, K, V>, PhantomData<I>);
472pub struct VacantEntry<'a, I, K, V>(inner::VacantEntry<'a, K, V>, PhantomData<I>);
473
474impl<'a, I: EntityId, K, V> OccupiedEntry<'a, I, K, V> {
475    /// Return the index of the key-value pair.
476    #[inline]
477    pub fn index(&self) -> I {
478        I::from_idx(self.0.index())
479    }
480
481    #[inline]
482    pub fn key(&self) -> &K {
483        self.0.key()
484    }
485
486    #[inline]
487    pub fn get(&self) -> &V {
488        self.0.get()
489    }
490
491    #[inline]
492    pub fn get_mut(&mut self) -> &mut V {
493        self.0.get_mut()
494    }
495
496    #[inline]
497    pub fn into_mut(self) -> &'a mut V {
498        self.0.into_mut()
499    }
500
501    /// Sets the value of the entry to `value`, and returns the entry's old value.
502    #[inline]
503    pub fn insert(&mut self, value: V) -> V {
504        self.0.insert(value)
505    }
506}
507
508impl<'a, I: EntityId, K, V> VacantEntry<'a, I, K, V> {
509    /// Return the index where the key-value pair may be inserted.
510    #[inline]
511    pub fn index(&self) -> I {
512        I::from_idx(self.0.index())
513    }
514
515    #[inline]
516    pub fn key(&self) -> &K {
517        self.0.key()
518    }
519
520    #[inline]
521    pub fn into_key(self) -> K {
522        self.0.into_key()
523    }
524
525    #[inline]
526    pub fn insert(self, value: V) -> &'a mut V {
527        self.0.insert(value)
528    }
529
530    #[inline]
531    pub fn insert_entry(self, value: V) -> OccupiedEntry<'a, I, K, V> {
532        OccupiedEntry(self.0.insert_entry(value), PhantomData)
533    }
534}
535
536impl<'a, I: EntityId, K, V> Entry<'a, I, K, V> {
537    #[inline]
538    pub fn index(&self) -> I {
539        match self {
540            Entry::Occupied(entry) => entry.index(),
541            Entry::Vacant(entry) => entry.index(),
542        }
543    }
544
545    /// Sets the value of the entry (after inserting if vacant), and returns an `OccupiedEntry`.
546    ///
547    /// If the entry is already occupied, the old value will be discarded.
548    #[inline]
549    pub fn insert_entry(self, value: V) -> OccupiedEntry<'a, I, K, V> {
550        match self {
551            Entry::Occupied(mut entry) => {
552                entry.insert(value);
553                entry
554            }
555            Entry::Vacant(entry) => entry.insert_entry(value),
556        }
557    }
558
559    /// Inserts the given default value in the entry if it is vacant and returns a mutable
560    /// reference to it. Otherwise a mutable reference to an already existent value is returned.
561    #[inline]
562    pub fn or_insert(self, default: V) -> &'a mut V {
563        match self {
564            Entry::Occupied(entry) => entry.into_mut(),
565            Entry::Vacant(entry) => entry.insert(default),
566        }
567    }
568
569    /// Like [`or_insert`][Self::or_insert], but allows constructing the default value lazily.
570    #[inline]
571    pub fn or_insert_with<F>(self, f: F) -> &'a mut V
572    where
573        F: FnOnce() -> V,
574    {
575        match self {
576            Entry::Occupied(entry) => entry.into_mut(),
577            Entry::Vacant(entry) => entry.insert(f()),
578        }
579    }
580
581    /// Like [`or_insert_with`][Self::or_insert_with], but also provides a reference to the key.
582    #[inline]
583    pub fn or_insert_with_key<F>(self, f: F) -> &'a mut V
584    where
585        F: FnOnce(&K) -> V,
586    {
587        match self {
588            Entry::Occupied(entry) => entry.into_mut(),
589            Entry::Vacant(entry) => {
590                let value = f(entry.key());
591                entry.insert(value)
592            }
593        }
594    }
595
596    #[inline]
597    pub fn key(&self) -> &K {
598        match self {
599            Entry::Occupied(entry) => entry.key(),
600            Entry::Vacant(entry) => entry.key(),
601        }
602    }
603
604    /// Modifies the entry if it is occupied.
605    #[inline]
606    pub fn and_modify<F>(mut self, f: F) -> Self
607    where
608        F: FnOnce(&mut V),
609    {
610        if let Entry::Occupied(entry) = &mut self {
611            f(entry.get_mut());
612        }
613        self
614    }
615
616    /// Inserts a default-constructed value in the entry if it is vacant and returns a mutable
617    /// reference to it. Otherwise a mutable reference to an already existent value is returned.
618    pub fn or_default(self) -> &'a mut V
619    where
620        V: Default,
621    {
622        match self {
623            Entry::Occupied(entry) => entry.into_mut(),
624            Entry::Vacant(entry) => entry.insert(V::default()),
625        }
626    }
627}