bevy_ecs/entity/
hash_set.rs

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

bevy_ecs/entity/
hash_set.rs
