Skip to main content

prjcombine_entity/
set.rs

1//! An [`indexmap::IndexSet`] with strongly-typed indices.
2use core::hash::{BuildHasher, Hash};
3use core::marker::PhantomData;
4use core::ops::Index;
5
6use std::collections::hash_map::RandomState;
7use std::fmt;
8
9use indexmap::Equivalent;
10use indexmap::set::IndexSet;
11
12use crate::id::EntityRange;
13use crate::{EntityId, EntityVec};
14
15/// An [`indexmap::IndexSet`] with strongly-typed indices.
16///
17/// An `EntitySet` assigns sequential IDs to each inserted value `V`. However, if a value which is
18/// already present is inserted again, the pre-existing ID will be reused.
19#[derive(Clone)]
20pub struct EntitySet<I: EntityId, V: Hash + Eq, RS: BuildHasher = RandomState> {
21    set: IndexSet<V, RS>,
22    ids: PhantomData<I>,
23}
24
25impl<I, V, RS> EntitySet<I, V, RS>
26where
27    I: EntityId,
28    V: Hash + Eq,
29    RS: BuildHasher,
30{
31    pub fn with_hasher(h: RS) -> Self {
32        Self {
33            set: IndexSet::with_hasher(h),
34            ids: PhantomData,
35        }
36    }
37
38    pub fn with_capacity_and_hasher(n: usize, h: RS) -> Self {
39        Self {
40            set: IndexSet::with_capacity_and_hasher(n, h),
41            ids: PhantomData,
42        }
43    }
44
45    pub fn len(&self) -> usize {
46        self.set.len()
47    }
48
49    pub fn is_empty(&self) -> bool {
50        self.set.is_empty()
51    }
52
53    pub fn next_id(&self) -> I {
54        self.ids().end()
55    }
56
57    pub fn clear(&mut self) {
58        self.set.clear()
59    }
60
61    /// Insert a value into the set.
62    ///
63    /// If the value was not previously present in the set, returns `(id, true)`. Otherwise,
64    /// returns `(id, false)`.
65    pub fn insert(&mut self, v: V) -> (I, bool) {
66        let (i, f) = self.set.insert_full(v);
67        (I::from_idx(i), f)
68    }
69
70    /// Insert a new value into the set.
71    ///
72    /// Panics if the value is already present in the set.
73    #[track_caller]
74    pub fn insert_new(&mut self, v: V) -> I {
75        let (i, f) = self.insert(v);
76        assert!(f, "value already present in EntitySet");
77        i
78    }
79
80    /// Returns the ID for a given value, if already present in the set.
81    pub fn get<Q>(&self, key: &Q) -> Option<I>
82    where
83        Q: ?Sized + Hash + Equivalent<V>,
84    {
85        let (i, _) = self.set.get_full(key)?;
86        Some(I::from_idx(i))
87    }
88
89    pub fn contains<Q>(&self, key: &Q) -> bool
90    where
91        Q: ?Sized + Hash + Equivalent<V>,
92    {
93        self.set.contains(key)
94    }
95
96    pub fn ids(&self) -> EntityRange<I> {
97        EntityRange::new(0, self.len())
98    }
99
100    pub fn iter(&self) -> Iter<'_, I, V> {
101        Iter {
102            vals: self.set.iter(),
103            pos: 0,
104            ids: PhantomData,
105        }
106    }
107
108    pub fn values(&self) -> indexmap::set::Iter<'_, V> {
109        self.set.iter()
110    }
111
112    pub fn into_values(self) -> indexmap::set::IntoIter<V> {
113        self.set.into_iter()
114    }
115
116    pub fn into_vec(self) -> EntityVec<I, V> {
117        self.into_values().collect()
118    }
119
120    /// Return an ID for a given value, whether pre-existing or newly allocated.
121    ///
122    /// This function allows providing a reference for the purpose of looking up the value. In this
123    /// case, the value is only cloned if necessary (by means of `ToOwned`).
124    pub fn get_or_insert(
125        &mut self,
126        key: &(impl ToOwned<Owned = V> + Hash + Equivalent<V> + ?Sized),
127    ) -> I {
128        match self.get(key) {
129            Some(i) => i,
130            None => self.insert_new(key.to_owned()),
131        }
132    }
133}
134
135impl<I, V> EntitySet<I, V>
136where
137    I: EntityId,
138    V: Hash + Eq,
139{
140    pub fn new() -> Self {
141        Self {
142            set: IndexSet::new(),
143            ids: PhantomData,
144        }
145    }
146
147    pub fn with_capacity(n: usize) -> Self {
148        Self {
149            set: IndexSet::with_capacity(n),
150            ids: PhantomData,
151        }
152    }
153}
154
155impl<I, V> Default for EntitySet<I, V>
156where
157    I: EntityId,
158    V: Hash + Eq,
159{
160    fn default() -> Self {
161        Self::new()
162    }
163}
164
165impl<I, V, RS> fmt::Debug for EntitySet<I, V, RS>
166where
167    I: EntityId,
168    V: Hash + Eq + fmt::Debug,
169    RS: BuildHasher,
170{
171    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
172        fmt.debug_map().entries(self).finish()
173    }
174}
175
176impl<I, V, RS, RS2> PartialEq<EntitySet<I, V, RS2>> for EntitySet<I, V, RS>
177where
178    I: EntityId,
179    V: Hash + Eq,
180    RS: BuildHasher,
181    RS2: BuildHasher,
182{
183    fn eq(&self, other: &EntitySet<I, V, RS2>) -> bool {
184        self.iter().eq(other.iter())
185    }
186}
187
188impl<I, V, RS> Eq for EntitySet<I, V, RS>
189where
190    I: EntityId,
191    V: Hash + Eq,
192    RS: BuildHasher,
193{
194}
195
196impl<I, V, RS> IntoIterator for EntitySet<I, V, RS>
197where
198    I: EntityId,
199    V: Hash + Eq,
200    RS: BuildHasher,
201{
202    type Item = (I, V);
203    type IntoIter = IntoIter<I, V>;
204    fn into_iter(self) -> Self::IntoIter {
205        IntoIter {
206            vals: self.set.into_iter(),
207            pos: 0,
208            ids: PhantomData,
209        }
210    }
211}
212
213impl<'a, I, V, RS> IntoIterator for &'a EntitySet<I, V, RS>
214where
215    I: EntityId,
216    V: Hash + Eq,
217    RS: BuildHasher,
218{
219    type Item = (I, &'a V);
220    type IntoIter = Iter<'a, I, V>;
221    fn into_iter(self) -> Self::IntoIter {
222        self.iter()
223    }
224}
225
226impl<I, V, RS> Index<I> for EntitySet<I, V, RS>
227where
228    I: EntityId,
229    V: Hash + Eq,
230    RS: BuildHasher,
231{
232    type Output = V;
233    fn index(&self, index: I) -> &V {
234        &self.set[index.to_idx()]
235    }
236}
237
238#[derive(Clone, Debug)]
239pub struct Iter<'a, I, V: Hash> {
240    vals: indexmap::set::Iter<'a, V>,
241    pos: usize,
242    ids: PhantomData<I>,
243}
244
245impl<'a, I, V> Iterator for Iter<'a, I, V>
246where
247    I: EntityId,
248    V: Hash,
249{
250    type Item = (I, &'a V);
251    fn next(&mut self) -> Option<(I, &'a V)> {
252        let val = self.vals.next()?;
253        let id = I::from_idx(self.pos);
254        self.pos += 1;
255        Some((id, val))
256    }
257}
258
259impl<'a, I, V> DoubleEndedIterator for Iter<'a, I, V>
260where
261    I: EntityId,
262    V: Hash,
263{
264    fn next_back(&mut self) -> Option<(I, &'a V)> {
265        let val = self.vals.next_back()?;
266        Some((I::from_idx(self.pos + self.vals.len()), val))
267    }
268}
269
270impl<'a, I, V> ExactSizeIterator for Iter<'a, I, V>
271where
272    I: EntityId,
273    V: Hash,
274{
275    fn len(&self) -> usize {
276        self.vals.len()
277    }
278}
279
280#[derive(Debug)]
281pub struct IntoIter<I, V: Hash> {
282    vals: indexmap::set::IntoIter<V>,
283    pos: usize,
284    ids: PhantomData<I>,
285}
286
287impl<I, V> Iterator for IntoIter<I, V>
288where
289    I: EntityId,
290    V: Hash,
291{
292    type Item = (I, V);
293    fn next(&mut self) -> Option<(I, V)> {
294        let val = self.vals.next()?;
295        let id = I::from_idx(self.pos);
296        self.pos += 1;
297        Some((id, val))
298    }
299}
300
301impl<I, V> DoubleEndedIterator for IntoIter<I, V>
302where
303    I: EntityId,
304    V: Hash,
305{
306    fn next_back(&mut self) -> Option<(I, V)> {
307        let val = self.vals.next_back()?;
308        Some((I::from_idx(self.pos + self.vals.len()), val))
309    }
310}
311
312impl<I, V> ExactSizeIterator for IntoIter<I, V>
313where
314    I: EntityId,
315    V: Hash,
316{
317    fn len(&self) -> usize {
318        self.vals.len()
319    }
320}
321
322impl<I, V, RS> FromIterator<V> for EntitySet<I, V, RS>
323where
324    I: EntityId,
325    V: Hash + Eq,
326    RS: BuildHasher + Default,
327{
328    fn from_iter<T>(iter: T) -> Self
329    where
330        T: IntoIterator<Item = V>,
331    {
332        Self {
333            set: IndexSet::from_iter(iter),
334            ids: PhantomData,
335        }
336    }
337}
338
339impl<I, V, RS> Extend<V> for EntitySet<I, V, RS>
340where
341    I: EntityId,
342    V: Hash + Eq,
343    RS: BuildHasher + Default,
344{
345    fn extend<T: IntoIterator<Item = V>>(&mut self, iter: T) {
346        self.set.extend(iter);
347    }
348}
349
350#[cfg(feature = "bincode")]
351mod bincode;