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(pub(crate) 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 the number of elements in the set.
47    pub fn len(&self) -> usize {
48        self.0.len()
49    }
50
51    /// Returns `true` if the set contains no elements.
52    pub fn is_empty(&self) -> bool {
53        self.0.is_empty()
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
213/// An iterator over the items of an [`EntityHashSet`].
214///
215/// This struct is created by the [`iter`] method on [`EntityHashSet`]. See its documentation for more.
216///
217/// [`iter`]: EntityHashSet::iter
218pub struct Iter<'a, S = EntityHash>(hash_set::Iter<'a, Entity>, PhantomData<S>);
219
220impl<'a> Iter<'a> {
221    /// Returns the inner [`Iter`](hash_set::Iter).
222    pub fn into_inner(self) -> hash_set::Iter<'a, Entity> {
223        self.0
224    }
225}
226
227impl<'a> Deref for Iter<'a> {
228    type Target = hash_set::Iter<'a, Entity>;
229
230    fn deref(&self) -> &Self::Target {
231        &self.0
232    }
233}
234
235impl<'a> Iterator for Iter<'a> {
236    type Item = &'a Entity;
237
238    fn next(&mut self) -> Option<Self::Item> {
239        self.0.next()
240    }
241
242    fn size_hint(&self) -> (usize, Option<usize>) {
243        self.0.size_hint()
244    }
245}
246
247impl ExactSizeIterator for Iter<'_> {}
248
249impl FusedIterator for Iter<'_> {}
250
251impl Clone for Iter<'_> {
252    fn clone(&self) -> Self {
253        Self(self.0.clone(), PhantomData)
254    }
255}
256
257impl Debug for Iter<'_> {
258    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
259        f.debug_tuple("Iter").field(&self.0).field(&self.1).finish()
260    }
261}
262
263impl Default for Iter<'_> {
264    fn default() -> Self {
265        Self(Default::default(), PhantomData)
266    }
267}
268
269// SAFETY: Iter stems from a correctly behaving `HashSet<Entity, EntityHash>`.
270unsafe impl EntitySetIterator for Iter<'_> {}
271
272/// Owning iterator over the items of an [`EntityHashSet`].
273///
274/// This struct is created by the [`into_iter`] method on [`EntityHashSet`] (provided by the [`IntoIterator`] trait). See its documentation for more.
275///
276/// [`into_iter`]: EntityHashSet::into_iter
277pub struct IntoIter<S = EntityHash>(hash_set::IntoIter<Entity>, PhantomData<S>);
278
279impl IntoIter {
280    /// Returns the inner [`IntoIter`](hash_set::IntoIter).
281    pub fn into_inner(self) -> hash_set::IntoIter<Entity> {
282        self.0
283    }
284}
285
286impl Deref for IntoIter {
287    type Target = hash_set::IntoIter<Entity>;
288
289    fn deref(&self) -> &Self::Target {
290        &self.0
291    }
292}
293
294impl Iterator for IntoIter {
295    type Item = Entity;
296
297    fn next(&mut self) -> Option<Self::Item> {
298        self.0.next()
299    }
300
301    fn size_hint(&self) -> (usize, Option<usize>) {
302        self.0.size_hint()
303    }
304}
305
306impl ExactSizeIterator for IntoIter {}
307
308impl FusedIterator for IntoIter {}
309
310impl Debug for IntoIter {
311    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
312        f.debug_tuple("IntoIter")
313            .field(&self.0)
314            .field(&self.1)
315            .finish()
316    }
317}
318
319impl Default for IntoIter {
320    fn default() -> Self {
321        Self(Default::default(), PhantomData)
322    }
323}
324
325// SAFETY: IntoIter stems from a correctly behaving `HashSet<Entity, EntityHash>`.
326unsafe impl EntitySetIterator for IntoIter {}
327
328/// A draining iterator over the items of an [`EntityHashSet`].
329///
330/// This struct is created by the [`drain`] method on [`EntityHashSet`]. See its documentation for more.
331///
332/// [`drain`]: EntityHashSet::drain
333pub struct Drain<'a, S = EntityHash>(hash_set::Drain<'a, Entity>, PhantomData<S>);
334
335impl<'a> Drain<'a> {
336    /// Returns the inner [`Drain`](hash_set::Drain).
337    pub fn into_inner(self) -> hash_set::Drain<'a, Entity> {
338        self.0
339    }
340}
341
342impl<'a> Deref for Drain<'a> {
343    type Target = hash_set::Drain<'a, Entity>;
344
345    fn deref(&self) -> &Self::Target {
346        &self.0
347    }
348}
349
350impl<'a> Iterator for Drain<'a> {
351    type Item = Entity;
352
353    fn next(&mut self) -> Option<Self::Item> {
354        self.0.next()
355    }
356
357    fn size_hint(&self) -> (usize, Option<usize>) {
358        self.0.size_hint()
359    }
360}
361
362impl ExactSizeIterator for Drain<'_> {}
363
364impl FusedIterator for Drain<'_> {}
365
366impl Debug for Drain<'_> {
367    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
368        f.debug_tuple("Drain")
369            .field(&self.0)
370            .field(&self.1)
371            .finish()
372    }
373}
374
375// SAFETY: Drain stems from a correctly behaving `HashSet<Entity, EntityHash>`.
376unsafe impl EntitySetIterator for Drain<'_> {}
377
378/// A draining iterator over entries of a [`EntityHashSet`] which don't satisfy the predicate `f`.
379///
380/// This struct is created by the [`extract_if`] method on [`EntityHashSet`]. See its documentation for more.
381///
382/// [`extract_if`]: EntityHashSet::extract_if
383pub struct ExtractIf<'a, F: FnMut(&Entity) -> bool, S = EntityHash>(
384    hash_set::ExtractIf<'a, Entity, F>,
385    PhantomData<S>,
386);
387
388impl<'a, F: FnMut(&Entity) -> bool> ExtractIf<'a, F> {
389    /// Returns the inner [`ExtractIf`](hash_set::ExtractIf).
390    pub fn into_inner(self) -> hash_set::ExtractIf<'a, Entity, F> {
391        self.0
392    }
393}
394
395impl<'a, F: FnMut(&Entity) -> bool> Deref for ExtractIf<'a, F> {
396    type Target = hash_set::ExtractIf<'a, Entity, F>;
397
398    fn deref(&self) -> &Self::Target {
399        &self.0
400    }
401}
402
403impl<'a, F: FnMut(&Entity) -> bool> Iterator for ExtractIf<'a, F> {
404    type Item = Entity;
405
406    fn next(&mut self) -> Option<Self::Item> {
407        self.0.next()
408    }
409
410    fn size_hint(&self) -> (usize, Option<usize>) {
411        self.0.size_hint()
412    }
413}
414
415impl<F: FnMut(&Entity) -> bool> FusedIterator for ExtractIf<'_, F> {}
416
417impl<F: FnMut(&Entity) -> bool> Debug for ExtractIf<'_, F> {
418    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
419        f.debug_tuple("ExtractIf").finish()
420    }
421}
422
423// SAFETY: ExtractIf stems from a correctly behaving `HashSet<Entity, EntityHash>`.
424unsafe impl<F: FnMut(&Entity) -> bool> EntitySetIterator for ExtractIf<'_, F> {}
425
426// SAFETY: Difference stems from two correctly behaving `HashSet<Entity, EntityHash>`s.
427unsafe impl EntitySetIterator for hash_set::Difference<'_, Entity, EntityHash> {}
428
429// SAFETY: Intersection stems from two correctly behaving `HashSet<Entity, EntityHash>`s.
430unsafe impl EntitySetIterator for hash_set::Intersection<'_, Entity, EntityHash> {}
431
432// SAFETY: SymmetricDifference stems from two correctly behaving `HashSet<Entity, EntityHash>`s.
433unsafe impl EntitySetIterator for hash_set::SymmetricDifference<'_, Entity, EntityHash> {}
434
435// SAFETY: Union stems from two correctly behaving `HashSet<Entity, EntityHash>`s.
436unsafe impl EntitySetIterator for hash_set::Union<'_, Entity, EntityHash> {}
bevy_ecs/entity/hash_set.rs

bevy_ecs/entity/
hash_set.rs
