bevy_ecs/entity/
hash_set.rs

1//! Contains the [`EntityEquivalentHashSet`] type, a [`HashSet`] pre-configured to use [`EntityHash`] hashing.
2//!
3//! This module is a lightweight wrapper around Bevy's [`HashSet`] that is more performant for [`Entity`] keys.
4
5use core::{
6    fmt::{self, Debug, Formatter},
7    hash::Hash,
8    iter::FusedIterator,
9    marker::PhantomData,
10    ops::{
11        BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Deref, DerefMut, Sub,
12        SubAssign,
13    },
14};
15
16use bevy_platform::collections::hash_set::{self, HashSet};
17#[cfg(feature = "bevy_reflect")]
18use bevy_reflect::Reflect;
19
20use super::{
21    Entity, EntityEquivalent, EntityHash, EntitySet, EntitySetIterator, FromEntitySetIterator,
22};
23
24/// A [`HashSet`] pre-configured to use [`EntityHash`] hashing.
25#[cfg_attr(feature = "bevy_reflect", derive(Reflect))]
26#[cfg_attr(feature = "serialize", derive(serde::Deserialize, serde::Serialize))]
27#[derive(Debug, Clone, PartialEq, Eq)]
28pub struct EntityEquivalentHashSet<K: EntityEquivalent + Hash>(HashSet<K, EntityHash>);
29
30/// An [`HashSet`] pre-configured to use [`EntityHash`] hashing with an [`Entity`].
31pub type EntityHashSet = EntityEquivalentHashSet<Entity>;
32
33impl<K: EntityEquivalent + Hash> EntityEquivalentHashSet<K> {
34    /// Creates an empty `EntityEquivalentHashSet`.
35    ///
36    /// Equivalent to [`HashSet::with_hasher(EntityHash)`].
37    ///
38    /// [`HashSet::with_hasher(EntityHash)`]: HashSet::with_hasher
39    pub const fn new() -> Self {
40        Self(HashSet::with_hasher(EntityHash))
41    }
42
43    /// Creates an empty `EntityEquivalentHashSet` with the specified capacity.
44    ///
45    /// Equivalent to [`HashSet::with_capacity_and_hasher(n, EntityHash)`].
46    ///
47    /// [`HashSet::with_capacity_and_hasher(n, EntityHash)`]: HashSet::with_capacity_and_hasher
48    pub fn with_capacity(n: usize) -> Self {
49        Self(HashSet::with_capacity_and_hasher(n, EntityHash))
50    }
51
52    /// Returns `true` if the set contains no elements.
53    pub fn is_empty(&self) -> bool {
54        self.0.is_empty()
55    }
56
57    /// Constructs an `EntityHashSet` from an [`HashSet`].
58    pub const fn from_hash_set(set: HashSet<K, EntityHash>) -> Self {
59        Self(set)
60    }
61
62    /// Returns the inner [`HashSet`].
63    pub fn into_inner(self) -> HashSet<K, EntityHash> {
64        self.0
65    }
66
67    /// Clears the set, returning all elements in an iterator.
68    ///
69    /// Equivalent to [`HashSet::drain`].
70    pub fn drain(&mut self) -> Drain<'_, K> {
71        Drain(self.0.drain(), PhantomData)
72    }
73
74    /// An iterator visiting all elements in arbitrary order.
75    /// The iterator element type is `&'a Entity`.
76    ///
77    /// Equivalent to [`HashSet::iter`].
78    pub fn iter(&self) -> Iter<'_, K> {
79        Iter(self.0.iter(), PhantomData)
80    }
81
82    /// Drains elements which are true under the given predicate,
83    /// and returns an iterator over the removed items.
84    ///
85    /// Equivalent to [`HashSet::extract_if`].
86    pub fn extract_if<F: FnMut(&K) -> bool>(&mut self, f: F) -> ExtractIf<'_, K, F> {
87        ExtractIf(self.0.extract_if(f), PhantomData)
88    }
89}
90
91impl<K: EntityEquivalent + Hash> Deref for EntityEquivalentHashSet<K> {
92    type Target = HashSet<K, EntityHash>;
93
94    fn deref(&self) -> &Self::Target {
95        &self.0
96    }
97}
98
99impl<K: EntityEquivalent + Hash> DerefMut for EntityEquivalentHashSet<K> {
100    fn deref_mut(&mut self) -> &mut Self::Target {
101        &mut self.0
102    }
103}
104
105impl<'a, K: EntityEquivalent + Hash> IntoIterator for &'a EntityEquivalentHashSet<K> {
106    type Item = &'a K;
107
108    type IntoIter = Iter<'a, K>;
109
110    fn into_iter(self) -> Self::IntoIter {
111        Iter((&self.0).into_iter(), PhantomData)
112    }
113}
114
115impl<K: EntityEquivalent + Hash> IntoIterator for EntityEquivalentHashSet<K> {
116    type Item = K;
117
118    type IntoIter = IntoIter<K>;
119
120    fn into_iter(self) -> Self::IntoIter {
121        IntoIter(self.0.into_iter(), PhantomData)
122    }
123}
124
125impl<K: EntityEquivalent + Hash> Default for EntityEquivalentHashSet<K> {
126    fn default() -> Self {
127        Self(Default::default())
128    }
129}
130
131impl<K: EntityEquivalent + Hash + Clone> BitAnd for &EntityEquivalentHashSet<K> {
132    type Output = EntityEquivalentHashSet<K>;
133
134    fn bitand(self, rhs: Self) -> Self::Output {
135        EntityEquivalentHashSet(self.0.bitand(&rhs.0))
136    }
137}
138
139impl<K: EntityEquivalent + Hash + Clone> BitAndAssign<&EntityEquivalentHashSet<K>>
140    for EntityEquivalentHashSet<K>
141{
142    fn bitand_assign(&mut self, rhs: &Self) {
143        self.0.bitand_assign(&rhs.0);
144    }
145}
146
147impl<K: EntityEquivalent + Hash + Clone> BitOr for &EntityEquivalentHashSet<K> {
148    type Output = EntityEquivalentHashSet<K>;
149
150    fn bitor(self, rhs: Self) -> Self::Output {
151        EntityEquivalentHashSet(self.0.bitor(&rhs.0))
152    }
153}
154
155impl<K: EntityEquivalent + Hash + Clone> BitOrAssign<&EntityEquivalentHashSet<K>>
156    for EntityEquivalentHashSet<K>
157{
158    fn bitor_assign(&mut self, rhs: &Self) {
159        self.0.bitor_assign(&rhs.0);
160    }
161}
162
163impl<K: EntityEquivalent + Hash + Clone> BitXor for &EntityEquivalentHashSet<K> {
164    type Output = EntityEquivalentHashSet<K>;
165
166    fn bitxor(self, rhs: Self) -> Self::Output {
167        EntityEquivalentHashSet(self.0.bitxor(&rhs.0))
168    }
169}
170
171impl<K: EntityEquivalent + Hash + Clone> BitXorAssign<&EntityEquivalentHashSet<K>>
172    for EntityEquivalentHashSet<K>
173{
174    fn bitxor_assign(&mut self, rhs: &Self) {
175        self.0.bitxor_assign(&rhs.0);
176    }
177}
178
179impl<K: EntityEquivalent + Hash + Clone> Sub for &EntityEquivalentHashSet<K> {
180    type Output = EntityEquivalentHashSet<K>;
181
182    fn sub(self, rhs: Self) -> Self::Output {
183        EntityEquivalentHashSet(self.0.sub(&rhs.0))
184    }
185}
186
187impl<K: EntityEquivalent + Hash + Clone> SubAssign<&EntityEquivalentHashSet<K>>
188    for EntityEquivalentHashSet<K>
189{
190    fn sub_assign(&mut self, rhs: &Self) {
191        self.0.sub_assign(&rhs.0);
192    }
193}
194
195impl<'a, K: EntityEquivalent + Hash + Copy> Extend<&'a K> for EntityEquivalentHashSet<K> {
196    fn extend<I: IntoIterator<Item = &'a K>>(&mut self, iter: I) {
197        self.0.extend(iter);
198    }
199}
200
201impl<K: EntityEquivalent + Hash> Extend<K> for EntityEquivalentHashSet<K> {
202    fn extend<I: IntoIterator<Item = K>>(&mut self, iter: I) {
203        self.0.extend(iter);
204    }
205}
206
207impl<K: EntityEquivalent + Hash, const N: usize> From<[K; N]> for EntityEquivalentHashSet<K> {
208    fn from(value: [K; N]) -> Self {
209        Self(HashSet::from_iter(value))
210    }
211}
212
213impl<K: EntityEquivalent + Hash> FromIterator<K> for EntityEquivalentHashSet<K> {
214    fn from_iter<I: IntoIterator<Item = K>>(iterable: I) -> Self {
215        Self(HashSet::from_iter(iterable))
216    }
217}
218
219impl<K: EntityEquivalent + Hash> FromEntitySetIterator<K> for EntityEquivalentHashSet<K> {
220    fn from_entity_set_iter<I: EntitySet<Item = K>>(set_iter: I) -> Self {
221        let iter = set_iter.into_iter();
222        let set = EntityEquivalentHashSet::with_capacity(iter.size_hint().0);
223        iter.fold(set, |mut set, e| {
224            // SAFETY: Every element in self is unique.
225            unsafe {
226                set.insert_unique_unchecked(e);
227            }
228            set
229        })
230    }
231}
232
233impl<K: EntityEquivalent + Hash> From<HashSet<K, EntityHash>> for EntityEquivalentHashSet<K> {
234    fn from(value: HashSet<K, EntityHash>) -> Self {
235        Self(value)
236    }
237}
238
239/// An iterator over the items of an [`EntityEquivalentHashSet`].
240///
241/// This struct is created by the [`iter`] method on [`EntityEquivalentHashSet`]. See its documentation for more.
242///
243/// [`iter`]: EntityEquivalentHashSet::iter
244pub struct Iter<'a, K: EntityEquivalent + Hash, S = EntityHash>(
245    hash_set::Iter<'a, K>,
246    PhantomData<S>,
247);
248
249impl<'a, K: EntityEquivalent + Hash> Iter<'a, K> {
250    /// Constructs a [`Iter<'a, K, S>`] from a [`hash_set::Iter<'a, K>`] unsafely.
251    ///
252    /// # Safety
253    ///
254    /// `iter` must either be empty, or have been obtained from a
255    /// [`hash_set::HashSet`] using the `S` hasher.
256    pub const unsafe fn from_iter_unchecked<S>(iter: hash_set::Iter<'a, K>) -> Iter<'a, K, S> {
257        Iter(iter, PhantomData)
258    }
259
260    /// Returns the inner [`Iter`](hash_set::Iter).
261    pub const fn into_inner(self) -> hash_set::Iter<'a, K> {
262        self.0
263    }
264}
265
266impl<'a, K: EntityEquivalent + Hash> Deref for Iter<'a, K> {
267    type Target = hash_set::Iter<'a, K>;
268
269    fn deref(&self) -> &Self::Target {
270        &self.0
271    }
272}
273
274impl<'a, K: EntityEquivalent + Hash> Iterator for Iter<'a, K> {
275    type Item = &'a K;
276
277    fn next(&mut self) -> Option<Self::Item> {
278        self.0.next()
279    }
280
281    fn size_hint(&self) -> (usize, Option<usize>) {
282        self.0.size_hint()
283    }
284
285    fn fold<B, F>(self, init: B, f: F) -> B
286    where
287        Self: Sized,
288        F: FnMut(B, Self::Item) -> B,
289    {
290        self.0.fold(init, f)
291    }
292}
293
294impl<K: EntityEquivalent + Hash> ExactSizeIterator for Iter<'_, K> {}
295
296impl<K: EntityEquivalent + Hash> FusedIterator for Iter<'_, K> {}
297
298impl<K: EntityEquivalent + Hash> Clone for Iter<'_, K> {
299    fn clone(&self) -> Self {
300        // SAFETY: We are cloning an already valid `Iter`.
301        unsafe { Self::from_iter_unchecked(self.0.clone()) }
302    }
303}
304
305impl<K: EntityEquivalent + Hash + Debug> Debug for Iter<'_, K> {
306    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
307        f.debug_tuple("Iter").field(&self.0).field(&self.1).finish()
308    }
309}
310
311impl<K: EntityEquivalent + Hash> Default for Iter<'_, K> {
312    fn default() -> Self {
313        // SAFETY: `Iter` is empty.
314        unsafe { Self::from_iter_unchecked(Default::default()) }
315    }
316}
317
318// SAFETY: Iter stems from a correctly behaving `HashSet<Entity, EntityHash>`.
319unsafe impl<K: EntityEquivalent + Hash> EntitySetIterator for Iter<'_, K> {}
320
321/// Owning iterator over the items of an [`EntityEquivalentHashSet`].
322///
323/// This struct is created by the [`into_iter`] method on [`EntityEquivalentHashSet`] (provided by the [`IntoIterator`] trait). See its documentation for more.
324///
325/// [`into_iter`]: EntityEquivalentHashSet::into_iter
326pub struct IntoIter<K: EntityEquivalent + Hash, S = EntityHash>(
327    hash_set::IntoIter<K>,
328    PhantomData<S>,
329);
330
331impl<K: EntityEquivalent + Hash> IntoIter<K> {
332    /// Constructs a [`IntoIter<K, S>`] from a [`hash_set::IntoIter<K>`] unsafely.
333    ///
334    /// # Safety
335    ///
336    /// `into_iter` must either be empty, or have been obtained from a
337    /// [`hash_set::HashSet`] using the `S` hasher.
338    pub const unsafe fn from_into_iter_unchecked<S>(
339        into_iter: hash_set::IntoIter<K>,
340    ) -> IntoIter<K, S> {
341        IntoIter(into_iter, PhantomData)
342    }
343
344    /// Returns the inner [`IntoIter`](hash_set::IntoIter).
345    pub fn into_inner(self) -> hash_set::IntoIter<K> {
346        self.0
347    }
348}
349
350impl<K: EntityEquivalent + Hash> Deref for IntoIter<K> {
351    type Target = hash_set::IntoIter<K>;
352
353    fn deref(&self) -> &Self::Target {
354        &self.0
355    }
356}
357
358impl<K: EntityEquivalent + Hash> Iterator for IntoIter<K> {
359    type Item = K;
360
361    fn next(&mut self) -> Option<Self::Item> {
362        self.0.next()
363    }
364
365    fn size_hint(&self) -> (usize, Option<usize>) {
366        self.0.size_hint()
367    }
368
369    fn fold<B, F>(self, init: B, f: F) -> B
370    where
371        Self: Sized,
372        F: FnMut(B, Self::Item) -> B,
373    {
374        self.0.fold(init, f)
375    }
376}
377
378impl<K: EntityEquivalent + Hash> ExactSizeIterator for IntoIter<K> {}
379
380impl<K: EntityEquivalent + Hash> FusedIterator for IntoIter<K> {}
381
382impl<K: EntityEquivalent + Hash + Debug> Debug for IntoIter<K> {
383    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
384        f.debug_tuple("IntoIter")
385            .field(&self.0)
386            .field(&self.1)
387            .finish()
388    }
389}
390
391impl<K: EntityEquivalent + Hash> Default for IntoIter<K> {
392    fn default() -> Self {
393        // SAFETY: `IntoIter` is empty.
394        unsafe { Self::from_into_iter_unchecked(Default::default()) }
395    }
396}
397
398// SAFETY: IntoIter stems from a correctly behaving `HashSet<Entity, EntityHash>`.
399unsafe impl<K: EntityEquivalent + Hash> EntitySetIterator for IntoIter<K> {}
400
401/// A draining iterator over the items of an [`EntityEquivalentHashSet`].
402///
403/// This struct is created by the [`drain`] method on [`EntityEquivalentHashSet`]. See its documentation for more.
404///
405/// [`drain`]: EntityEquivalentHashSet::drain
406pub struct Drain<'a, K: EntityEquivalent + Hash, S = EntityHash>(
407    hash_set::Drain<'a, K>,
408    PhantomData<S>,
409);
410
411impl<'a, K: EntityEquivalent + Hash> Drain<'a, K> {
412    /// Constructs a [`Drain<'a, K, S>`] from a [`hash_set::Drain<'a, K>`] unsafely.
413    ///
414    /// # Safety
415    ///
416    /// `drain` must either be empty, or have been obtained from a
417    /// [`hash_set::HashSet`] using the `S` hasher.
418    pub const unsafe fn from_drain_unchecked<S>(drain: hash_set::Drain<'a, K>) -> Drain<'a, K, S> {
419        Drain(drain, PhantomData)
420    }
421
422    /// Returns the inner [`Drain`](hash_set::Drain).
423    pub fn into_inner(self) -> hash_set::Drain<'a, K> {
424        self.0
425    }
426}
427
428impl<'a, K: EntityEquivalent + Hash> Deref for Drain<'a, K> {
429    type Target = hash_set::Drain<'a, K>;
430
431    fn deref(&self) -> &Self::Target {
432        &self.0
433    }
434}
435
436impl<'a, K: EntityEquivalent + Hash> Iterator for Drain<'a, K> {
437    type Item = K;
438
439    fn next(&mut self) -> Option<Self::Item> {
440        self.0.next()
441    }
442
443    fn size_hint(&self) -> (usize, Option<usize>) {
444        self.0.size_hint()
445    }
446
447    fn fold<B, F>(self, init: B, f: F) -> B
448    where
449        Self: Sized,
450        F: FnMut(B, Self::Item) -> B,
451    {
452        self.0.fold(init, f)
453    }
454}
455
456impl<K: EntityEquivalent + Hash> ExactSizeIterator for Drain<'_, K> {}
457
458impl<K: EntityEquivalent + Hash> FusedIterator for Drain<'_, K> {}
459
460impl<K: EntityEquivalent + Hash + Debug> Debug for Drain<'_, K> {
461    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
462        f.debug_tuple("Drain")
463            .field(&self.0)
464            .field(&self.1)
465            .finish()
466    }
467}
468
469// SAFETY: Drain stems from a correctly behaving `HashSet<Entity, EntityHash>`.
470unsafe impl<K: EntityEquivalent + Hash> EntitySetIterator for Drain<'_, K> {}
471
472/// A draining iterator over entries of a [`EntityEquivalentHashSet`] which don't satisfy the predicate `f`.
473///
474/// This struct is created by the [`extract_if`] method on [`EntityEquivalentHashSet`]. See its documentation for more.
475///
476/// [`extract_if`]: EntityEquivalentHashSet::extract_if
477pub struct ExtractIf<'a, K: EntityEquivalent + Hash, F: FnMut(&K) -> bool, S = EntityHash>(
478    hash_set::ExtractIf<'a, K, F>,
479    PhantomData<S>,
480);
481
482impl<'a, K: EntityEquivalent + Hash, F: FnMut(&K) -> bool> ExtractIf<'a, K, F> {
483    /// Constructs a [`ExtractIf<'a, K, F, S>`] from a [`hash_set::ExtractIf<'a, K, F>`] unsafely.
484    ///
485    /// # Safety
486    ///
487    /// `extract_if` must either be empty, or have been obtained from a
488    /// [`hash_set::HashSet`] using the `S` hasher.
489    pub const unsafe fn from_extract_if_unchecked<S>(
490        extract_if: hash_set::ExtractIf<'a, K, F>,
491    ) -> ExtractIf<'a, K, F, S> {
492        ExtractIf(extract_if, PhantomData)
493    }
494
495    /// Returns the inner [`ExtractIf`](hash_set::ExtractIf).
496    pub fn into_inner(self) -> hash_set::ExtractIf<'a, K, F> {
497        self.0
498    }
499}
500
501impl<'a, K: EntityEquivalent + Hash, F: FnMut(&K) -> bool> Deref for ExtractIf<'a, K, F> {
502    type Target = hash_set::ExtractIf<'a, K, F>;
503
504    fn deref(&self) -> &Self::Target {
505        &self.0
506    }
507}
508
509impl<'a, K: EntityEquivalent + Hash, F: FnMut(&K) -> bool> Iterator for ExtractIf<'a, K, F> {
510    type Item = K;
511
512    fn next(&mut self) -> Option<Self::Item> {
513        self.0.next()
514    }
515
516    fn size_hint(&self) -> (usize, Option<usize>) {
517        self.0.size_hint()
518    }
519}
520
521impl<K: EntityEquivalent + Hash, F: FnMut(&K) -> bool> FusedIterator for ExtractIf<'_, K, F> {}
522
523impl<K: EntityEquivalent + Hash, F: FnMut(&K) -> bool> Debug for ExtractIf<'_, K, F> {
524    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
525        f.debug_tuple("ExtractIf").finish()
526    }
527}
528
529// SAFETY: ExtractIf stems from a correctly behaving `HashSet<Entity, EntityHash>`.
530unsafe impl<K: EntityEquivalent + Hash, F: FnMut(&K) -> bool> EntitySetIterator
531    for ExtractIf<'_, K, F>
532{
533}
534
535// SAFETY: Difference stems from two correctly behaving `HashSet<Entity, EntityHash>`s.
536unsafe impl<K: EntityEquivalent + Hash> EntitySetIterator
537    for hash_set::Difference<'_, K, EntityHash>
538{
539}
540
541// SAFETY: Intersection stems from two correctly behaving `HashSet<Entity, EntityHash>`s.
542unsafe impl<K: EntityEquivalent + Hash> EntitySetIterator
543    for hash_set::Intersection<'_, K, EntityHash>
544{
545}
546
547// SAFETY: SymmetricDifference stems from two correctly behaving `HashSet<Entity, EntityHash>`s.
548unsafe impl<K: EntityEquivalent + Hash> EntitySetIterator
549    for hash_set::SymmetricDifference<'_, K, EntityHash>
550{
551}
552
553// SAFETY: Union stems from two correctly behaving `HashSet<Entity, EntityHash>`s.
554unsafe impl<K: EntityEquivalent + Hash> EntitySetIterator for hash_set::Union<'_, K, EntityHash> {}
bevy_ecs/entity/hash_set.rs

bevy_ecs/entity/
hash_set.rs
