mod add_component;
mod bulk_add_entity;
mod delete_component;
mod drain;
mod metadata;
mod remove;
mod sparse_array;
mod window;
pub use drain::SparseSetDrain;
pub use sparse_array::SparseArray;
pub(crate) use add_component::AddComponent;
pub(crate) use bulk_add_entity::BulkAddEntity;
pub(crate) use delete_component::DeleteComponent;
pub(crate) use metadata::Metadata;
pub(crate) use remove::Remove;
pub(crate) use window::FullRawWindowMut;
use crate::entity_id::EntityId;
use crate::memory_usage::StorageMemoryUsage;
use crate::storage::Storage;
use alloc::vec::Vec;
use core::cmp::{Ord, Ordering};
pub(crate) const BUCKET_SIZE: usize = 256 / core::mem::size_of::<EntityId>();
pub struct SparseSet<T> {
pub(crate) sparse: SparseArray<[EntityId; BUCKET_SIZE]>,
pub(crate) dense: Vec<EntityId>,
pub(crate) data: Vec<T>,
pub(crate) metadata: Metadata<T>,
}
impl<T> SparseSet<T> {
#[inline]
pub(crate) fn new() -> Self {
SparseSet {
sparse: SparseArray::new(),
dense: Vec::new(),
data: Vec::new(),
metadata: Metadata::new(),
}
}
#[inline]
pub(crate) fn full_raw_window_mut(&mut self) -> FullRawWindowMut<'_, T> {
FullRawWindowMut::new(self)
}
#[inline]
pub fn as_slice(&self) -> &[T] {
&self.data
}
}
impl<T> SparseSet<T> {
#[inline]
pub fn contains(&self, entity: EntityId) -> bool {
self.index_of(entity).is_some()
}
#[inline]
pub fn len(&self) -> usize {
self.dense.len()
}
#[inline]
pub fn is_empty(&self) -> bool {
self.dense.is_empty()
}
}
impl<T> SparseSet<T> {
#[inline]
pub fn index_of(&self, entity: EntityId) -> Option<usize> {
self.sparse.get(entity).and_then(|sparse_entity| {
if entity.gen() == sparse_entity.gen() {
Some(sparse_entity.uindex())
} else {
None
}
})
}
#[inline]
pub unsafe fn index_of_unchecked(&self, entity: EntityId) -> usize {
self.sparse.get_unchecked(entity).uindex()
}
#[inline]
pub fn id_at(&self, index: usize) -> Option<EntityId> {
self.dense.get(index).copied()
}
fn id_of(&self, entity: EntityId) -> Option<EntityId> {
if let Some(index) = self.index_of(entity) {
Some(unsafe { *self.dense.get_unchecked(index) })
} else {
None
}
}
#[inline]
pub(crate) fn private_get(&self, entity: EntityId) -> Option<&T> {
self.index_of(entity)
.map(|index| unsafe { self.data.get_unchecked(index) })
}
#[inline]
pub(crate) fn private_get_mut(&mut self, entity: EntityId) -> Option<&mut T> {
let index = self.index_of(entity)?;
if self.metadata.track_modification {
unsafe {
let dense_entity = self.dense.get_unchecked_mut(index);
if !dense_entity.is_inserted() {
dense_entity.set_modified();
}
}
}
Some(unsafe { self.data.get_unchecked_mut(index) })
}
}
impl<T> SparseSet<T> {
pub(crate) fn insert(&mut self, mut entity: EntityId, value: T) -> Option<T> {
self.sparse.allocate_at(entity);
let sparse_entity = unsafe { self.sparse.get_mut_unchecked(entity) };
let old_component;
if sparse_entity.is_dead() {
*sparse_entity =
EntityId::new_from_parts(self.dense.len() as u64, entity.gen() as u16, 0);
if self.metadata.track_insertion {
entity.set_inserted();
} else {
entity.clear_meta();
}
self.dense.push(entity);
self.data.push(value);
old_component = None;
} else if entity.gen() >= sparse_entity.gen() {
let old_data = unsafe {
core::mem::replace(self.data.get_unchecked_mut(sparse_entity.uindex()), value)
};
if entity.gen() == sparse_entity.gen() {
old_component = Some(old_data);
} else {
old_component = None;
}
sparse_entity.copy_gen(entity);
let dense_entity = unsafe { self.dense.get_unchecked_mut(sparse_entity.uindex()) };
if self.metadata.track_modification && !dense_entity.is_inserted() {
dense_entity.set_modified();
}
dense_entity.copy_index_gen(entity);
} else {
old_component = None;
}
old_component
}
}
impl<T> SparseSet<T> {
#[inline]
pub fn remove(&mut self, entity: EntityId) -> Option<T>
where
T: 'static,
{
let component = self.actual_remove(entity);
if component.is_some() {
if let Some(removed) = &mut self.metadata.track_removal {
removed.push(entity);
}
}
component
}
#[inline]
pub(crate) fn actual_remove(&mut self, entity: EntityId) -> Option<T> {
let sparse_entity = self.sparse.get(entity)?;
if entity.gen() >= sparse_entity.gen() {
let sparse_entity = self.sparse.get(entity)?;
unsafe {
*self.sparse.get_mut_unchecked(entity) = EntityId::dead();
}
self.dense.swap_remove(sparse_entity.uindex());
let component = self.data.swap_remove(sparse_entity.uindex());
unsafe {
let last = *self.dense.get_unchecked(sparse_entity.uindex());
self.sparse
.get_mut_unchecked(last)
.copy_index(sparse_entity);
}
if entity.gen() == sparse_entity.gen() {
Some(component)
} else {
None
}
} else {
None
}
}
#[inline]
pub fn delete(&mut self, entity: EntityId) -> bool
where
T: 'static,
{
if let Some(component) = self.actual_remove(entity) {
if let Some(deleted) = &mut self.metadata.track_deletion {
deleted.push((entity, component));
}
true
} else {
false
}
}
}
impl<T> SparseSet<T> {
#[inline]
pub fn is_inserted(&self, entity: EntityId) -> bool {
if let Some(id) = self.id_of(entity) {
id.is_inserted()
} else {
false
}
}
#[inline]
pub fn is_modified(&self, entity: EntityId) -> bool {
if let Some(id) = self.id_of(entity) {
id.is_modified()
} else {
false
}
}
#[inline]
pub fn is_inserted_or_modified(&self, entity: EntityId) -> bool {
if let Some(id) = self.id_of(entity) {
id.is_inserted() || id.is_modified()
} else {
false
}
}
#[track_caller]
#[inline]
pub fn deleted(&self) -> &[(EntityId, T)] {
self.metadata
.track_deletion
.as_deref()
.expect("The storage does not track component deletion. Use `view_mut.track_deletion()` or `view_mut.track_all()` to start tracking.")
}
#[track_caller]
#[inline]
pub fn removed(&self) -> &[EntityId] {
self.metadata
.track_removal
.as_deref()
.expect("The storage does not track component removal. Use `view_mut.track_removal()` or `view_mut.track_all()` to start tracking.")
}
#[track_caller]
#[inline]
pub fn removed_or_deleted(&self) -> impl Iterator<Item = EntityId> + '_ {
fn map_id<T>((id, _): &(EntityId, T)) -> EntityId {
*id
}
match (
self.metadata.track_removal.as_ref(),
self.metadata.track_deletion.as_ref(),
) {
(Some(removed), Some(deleted)) => {
removed.iter().cloned().chain(deleted.iter().map(map_id))
}
(Some(removed), None) => removed.iter().cloned().chain([].iter().map(map_id)),
(None, Some(deleted)) => [].iter().cloned().chain(deleted.iter().map(map_id)),
(None, None) => {
panic!("The storage does not track component removal nor deletion. Use `view_mut.track_removal()`, `view_mut.track_deletion()` or `view_mut.track_all()` to start tracking.")
}
}
}
#[track_caller]
#[inline]
pub fn take_deleted(&mut self) -> Vec<(EntityId, T)> {
self.metadata
.track_deletion
.as_mut()
.expect("The storage does not track component deletion. Use `view_mut.track_deletion()` or `view_mut.track_all()` to start tracking.")
.drain(..).collect()
}
#[track_caller]
#[inline]
pub fn take_removed(&mut self) -> Vec<EntityId> {
self.metadata
.track_deletion
.as_mut()
.expect("The storage does not track component removal. Use `view_mut.track_removal()` or `view_mut.track_all()` to start tracking.")
.drain(..)
.map(|(id, _)| id)
.collect()
}
#[track_caller]
pub fn take_removed_and_deleted(&mut self) -> (Vec<EntityId>, Vec<(EntityId, T)>) {
match (
self.metadata.track_removal.as_mut(),
self.metadata.track_deletion.as_mut(),
) {
(Some(removed), Some(deleted)) => {
(removed.drain(..).collect(), deleted.drain(..).collect())
}
(Some(removed), None) => (removed.drain(..).collect(), Vec::new()),
(None, Some(deleted)) => (Vec::new(), deleted.drain(..).collect()),
(None, None) => {
panic!("The storage does not track component removal nor deletion. Use `view_mut.track_removal()`, `view_mut.track_deletion()` or `view_mut.track_all()` to start tracking.")
}
}
}
#[track_caller]
#[inline]
pub fn clear_inserted(&mut self, entity: EntityId) {
if self.metadata.track_insertion {
if let Some(id) = self.sparse.get(entity) {
let id = unsafe { self.dense.get_unchecked_mut(id.uindex()) };
if id.is_inserted() {
id.clear_meta();
}
}
} else {
panic!("The storage does not track component insertion. Use `view_mut.track_insertion()` or `view_mut.track_all()` to start tracking.");
}
}
#[track_caller]
pub fn clear_all_inserted(&mut self) {
if self.metadata.track_insertion {
for id in &mut *self.dense {
if id.is_inserted() {
id.clear_meta();
}
}
} else {
panic!("The storage does not track component insertion. Use `view_mut.track_insertion()` or `view_mut.track_all()` to start tracking.");
}
}
#[track_caller]
#[inline]
pub fn clear_modified(&mut self, entity: EntityId) {
if self.metadata.track_modification {
if let Some(id) = self.sparse.get(entity) {
let id = unsafe { self.dense.get_unchecked_mut(id.uindex()) };
if id.is_modified() {
id.clear_meta();
}
}
} else {
panic!("The storage does not track component modification. Use `view_mut.track_modification()` or `view_mut.track_all()` to start tracking.");
}
}
#[track_caller]
pub fn clear_all_modified(&mut self) {
if self.metadata.track_modification {
for id in &mut *self.dense {
if id.is_modified() {
id.clear_meta();
}
}
} else {
panic!("The storage does not track component modification. Use `view_mut.track_modification()` or `view_mut.track_all()` to start tracking.");
}
}
#[track_caller]
#[inline]
pub fn clear_inserted_and_modified(&mut self, entity: EntityId) {
if !self.is_tracking_insertion() && !self.is_tracking_modification() {
panic!("The storage does not track component insertion not modification. Use `view_mut.track_insertion()`, `view_mut.track_modification()` or `view_mut.track_all()` to start tracking.");
}
if let Some(id) = self.sparse.get(entity) {
unsafe {
self.dense.get_unchecked_mut(id.uindex()).clear_meta();
}
}
}
#[track_caller]
pub fn clear_all_inserted_and_modified(&mut self) {
if !self.is_tracking_insertion() && !self.is_tracking_modification() {
panic!("The storage does not track component insertion not modification. Use `view_mut.track_insertion()`, `view_mut.track_modification()` or `view_mut.track_all()` to start tracking.");
}
for id in &mut self.dense {
id.clear_meta();
}
}
pub fn track_insertion(&mut self) -> &mut Self {
self.metadata.track_insertion = true;
self
}
pub fn track_modification(&mut self) -> &mut Self {
self.metadata.track_modification = true;
self
}
pub fn track_deletion(&mut self) -> &mut Self {
if self.metadata.track_deletion.is_none() {
self.metadata.track_deletion = Some(Vec::new());
}
self
}
pub fn track_removal(&mut self) -> &mut Self {
if self.metadata.track_removal.is_none() {
self.metadata.track_removal = Some(Vec::new());
}
self
}
pub fn track_all(&mut self) {
self.track_insertion();
self.track_modification();
self.track_deletion();
self.track_removal();
}
pub fn is_tracking_insertion(&self) -> bool {
self.metadata.track_insertion
}
pub fn is_tracking_modification(&self) -> bool {
self.metadata.track_modification
}
pub fn is_tracking_deletion(&self) -> bool {
self.metadata.track_deletion.is_some()
}
pub fn is_tracking_removal(&self) -> bool {
self.metadata.track_removal.is_some()
}
pub fn is_tracking_any(&self) -> bool {
self.is_tracking_insertion()
|| self.is_tracking_modification()
|| self.is_tracking_deletion()
|| self.is_tracking_removal()
}
}
impl<T> SparseSet<T> {
#[inline]
pub fn reserve(&mut self, additional: usize) {
self.dense.reserve(additional);
self.data.reserve(additional);
}
pub fn clear(&mut self) {
for &id in &self.dense {
unsafe {
*self.sparse.get_mut_unchecked(id) = EntityId::dead();
}
}
if let Some(deleted) = &mut self.metadata.track_deletion {
deleted.extend(self.dense.drain(..).zip(self.data.drain(..)));
} else {
self.dense.clear();
self.data.clear();
}
}
#[track_caller]
#[inline]
pub fn apply<R, F: FnOnce(&mut T, &T) -> R>(&mut self, a: EntityId, b: EntityId, f: F) -> R {
let a_index = self.index_of(a).unwrap_or_else(move || {
panic!(
"Entity {:?} does not have any component in this storage.",
a
)
});
let b_index = self.index_of(b).unwrap_or_else(move || {
panic!(
"Entity {:?} does not have any component in this storage.",
b
)
});
if a_index != b_index {
if self.metadata.track_modification {
unsafe {
let a_dense = self.dense.get_unchecked_mut(a_index);
if !a_dense.is_inserted() {
a_dense.set_modified();
}
}
}
let a = unsafe { &mut *self.data.as_mut_ptr().add(a_index) };
let b = unsafe { &*self.data.as_mut_ptr().add(b_index) };
f(a, b)
} else {
panic!("Cannot use apply with identical components.");
}
}
#[track_caller]
#[inline]
pub fn apply_mut<R, F: FnOnce(&mut T, &mut T) -> R>(
&mut self,
a: EntityId,
b: EntityId,
f: F,
) -> R {
let a_index = self.index_of(a).unwrap_or_else(move || {
panic!(
"Entity {:?} does not have any component in this storage.",
a
)
});
let b_index = self.index_of(b).unwrap_or_else(move || {
panic!(
"Entity {:?} does not have any component in this storage.",
b
)
});
if a_index != b_index {
if self.metadata.track_modification {
unsafe {
let a_dense = self.dense.get_unchecked_mut(a_index);
if !a_dense.is_inserted() {
a_dense.set_modified();
}
let b_dense = self.dense.get_unchecked_mut(b_index);
if !b_dense.is_inserted() {
b_dense.set_modified();
}
}
}
let a = unsafe { &mut *self.data.as_mut_ptr().add(a_index) };
let b = unsafe { &mut *self.data.as_mut_ptr().add(b_index) };
f(a, b)
} else {
panic!("Cannot use apply with identical components.");
}
}
pub fn drain(&mut self) -> SparseSetDrain<'_, T> {
if let Some(removed) = &mut self.metadata.track_removal {
removed.extend_from_slice(&self.dense);
}
for id in &self.dense {
unsafe {
*self.sparse.get_mut_unchecked(*id) = EntityId::dead();
}
}
let dense_ptr = self.dense.as_ptr();
let dense_len = self.dense.len();
self.dense.clear();
SparseSetDrain {
dense_ptr,
dense_len,
data: self.data.drain(..),
}
}
pub fn sort_unstable_by<F: FnMut(&T, &T) -> Ordering>(&mut self, mut compare: F) {
let mut transform: Vec<usize> = (0..self.dense.len()).collect();
transform.sort_unstable_by(|&i, &j| {
compare(unsafe { self.data.get_unchecked(i) }, unsafe {
self.data.get_unchecked(j)
})
});
let mut pos;
for i in 0..transform.len() {
pos = unsafe { *transform.get_unchecked(i) };
while pos < i {
pos = unsafe { *transform.get_unchecked(pos) };
}
self.dense.swap(i, pos);
self.data.swap(i, pos);
}
for (i, id) in self.dense.iter().enumerate() {
unsafe {
self.sparse.get_mut_unchecked(*id).set_index(i as u64);
}
}
}
}
impl<T: Ord> SparseSet<T> {
pub fn sort_unstable(&mut self) {
self.sort_unstable_by(Ord::cmp)
}
}
impl<T> core::ops::Index<EntityId> for SparseSet<T> {
type Output = T;
#[track_caller]
#[inline]
fn index(&self, entity: EntityId) -> &Self::Output {
self.private_get(entity).unwrap()
}
}
impl<T> core::ops::IndexMut<EntityId> for SparseSet<T> {
#[track_caller]
#[inline]
fn index_mut(&mut self, entity: EntityId) -> &mut Self::Output {
self.private_get_mut(entity).unwrap()
}
}
impl<T: 'static> Storage for SparseSet<T> {
#[inline]
fn delete(&mut self, entity: EntityId) {
SparseSet::delete(self, entity);
}
#[inline]
fn clear(&mut self) {
<Self>::clear(self);
}
fn memory_usage(&self) -> Option<StorageMemoryUsage> {
Some(StorageMemoryUsage {
storage_name: core::any::type_name::<Self>().into(),
allocated_memory_bytes: self.sparse.reserved_memory()
+ (self.dense.capacity() * core::mem::size_of::<EntityId>())
+ (self.data.capacity() * core::mem::size_of::<T>())
+ self.metadata.used_memory()
+ core::mem::size_of::<Self>(),
used_memory_bytes: self.sparse.used_memory()
+ (self.dense.len() * core::mem::size_of::<EntityId>())
+ (self.data.len() * core::mem::size_of::<T>())
+ self.metadata.reserved_memory()
+ core::mem::size_of::<Self>(),
component_count: self.len(),
})
}
fn sparse_array(&self) -> Option<&SparseArray<[EntityId; 32]>> {
Some(&self.sparse)
}
}
#[test]
fn insert() {
let mut array = SparseSet::new();
assert!(array
.insert(EntityId::new_from_parts(0, 0, 0), "0")
.is_none());
assert_eq!(array.dense, &[EntityId::new_from_parts(0, 0, 0)]);
assert_eq!(array.data, &["0"]);
assert_eq!(
array.private_get(EntityId::new_from_parts(0, 0, 0)),
Some(&"0")
);
assert!(array
.insert(EntityId::new_from_parts(1, 0, 0), "1")
.is_none());
assert_eq!(
array.dense,
&[
EntityId::new_from_parts(0, 0, 0),
EntityId::new_from_parts(1, 0, 0)
]
);
assert_eq!(array.data, &["0", "1"]);
assert_eq!(
array.private_get(EntityId::new_from_parts(0, 0, 0)),
Some(&"0")
);
assert_eq!(
array.private_get(EntityId::new_from_parts(1, 0, 0)),
Some(&"1")
);
assert!(array
.insert(EntityId::new_from_parts(5, 0, 0), "5")
.is_none());
assert_eq!(
array.dense,
&[
EntityId::new_from_parts(0, 0, 0),
EntityId::new_from_parts(1, 0, 0),
EntityId::new_from_parts(5, 0, 0)
]
);
assert_eq!(array.data, &["0", "1", "5"]);
assert_eq!(
array.private_get_mut(EntityId::new_from_parts(5, 0, 0)),
Some(&mut "5")
);
assert_eq!(array.private_get(EntityId::new_from_parts(4, 0, 0)), None);
}
#[test]
fn remove() {
let mut array = SparseSet::new();
array.insert(EntityId::new_from_parts(0, 0, 0), "0");
array.insert(EntityId::new_from_parts(5, 0, 0), "5");
array.insert(EntityId::new_from_parts(10, 0, 0), "10");
assert_eq!(array.remove(EntityId::new_from_parts(0, 0, 0)), Some("0"));
assert_eq!(
array.dense,
&[
EntityId::new_from_parts(10, 0, 0),
EntityId::new_from_parts(5, 0, 0)
]
);
assert_eq!(array.data, &["10", "5"]);
assert_eq!(array.private_get(EntityId::new_from_parts(0, 0, 0)), None);
assert_eq!(
array.private_get(EntityId::new_from_parts(5, 0, 0)),
Some(&"5")
);
assert_eq!(
array.private_get(EntityId::new_from_parts(10, 0, 0)),
Some(&"10")
);
array.insert(EntityId::new_from_parts(3, 0, 0), "3");
array.insert(EntityId::new_from_parts(100, 0, 0), "100");
assert_eq!(
array.dense,
&[
EntityId::new_from_parts(10, 0, 0),
EntityId::new_from_parts(5, 0, 0),
EntityId::new_from_parts(3, 0, 0),
EntityId::new_from_parts(100, 0, 0)
]
);
assert_eq!(array.data, &["10", "5", "3", "100"]);
assert_eq!(array.private_get(EntityId::new_from_parts(0, 0, 0)), None);
assert_eq!(
array.private_get(EntityId::new_from_parts(3, 0, 0)),
Some(&"3")
);
assert_eq!(
array.private_get(EntityId::new_from_parts(5, 0, 0)),
Some(&"5")
);
assert_eq!(
array.private_get(EntityId::new_from_parts(10, 0, 0)),
Some(&"10")
);
assert_eq!(
array.private_get(EntityId::new_from_parts(100, 0, 0)),
Some(&"100")
);
assert_eq!(array.remove(EntityId::new_from_parts(3, 0, 0)), Some("3"));
assert_eq!(
array.dense,
&[
EntityId::new_from_parts(10, 0, 0),
EntityId::new_from_parts(5, 0, 0),
EntityId::new_from_parts(100, 0, 0)
]
);
assert_eq!(array.data, &["10", "5", "100"]);
assert_eq!(array.private_get(EntityId::new_from_parts(0, 0, 0)), None);
assert_eq!(array.private_get(EntityId::new_from_parts(3, 0, 0)), None);
assert_eq!(
array.private_get(EntityId::new_from_parts(5, 0, 0)),
Some(&"5")
);
assert_eq!(
array.private_get(EntityId::new_from_parts(10, 0, 0)),
Some(&"10")
);
assert_eq!(
array.private_get(EntityId::new_from_parts(100, 0, 0)),
Some(&"100")
);
assert_eq!(
array.remove(EntityId::new_from_parts(100, 0, 0)),
Some("100")
);
assert_eq!(
array.dense,
&[
EntityId::new_from_parts(10, 0, 0),
EntityId::new_from_parts(5, 0, 0)
]
);
assert_eq!(array.data, &["10", "5"]);
assert_eq!(array.private_get(EntityId::new_from_parts(0, 0, 0)), None);
assert_eq!(array.private_get(EntityId::new_from_parts(3, 0, 0)), None);
assert_eq!(
array.private_get(EntityId::new_from_parts(5, 0, 0)),
Some(&"5")
);
assert_eq!(
array.private_get(EntityId::new_from_parts(10, 0, 0)),
Some(&"10")
);
assert_eq!(array.private_get(EntityId::new_from_parts(100, 0, 0)), None);
}
#[test]
fn drain() {
let mut sparse_set = SparseSet::new();
sparse_set.insert(EntityId::new(0), 0);
sparse_set.insert(EntityId::new(1), 1);
let mut drain = sparse_set.drain();
assert_eq!(drain.next(), Some(0));
assert_eq!(drain.next(), Some(1));
assert_eq!(drain.next(), None);
drop(drain);
assert_eq!(sparse_set.len(), 0);
assert_eq!(sparse_set.private_get(EntityId::new(0)), None);
}
#[test]
fn drain_with_id() {
let mut sparse_set = SparseSet::new();
sparse_set.insert(EntityId::new(0), 0);
sparse_set.insert(EntityId::new(1), 1);
let mut drain = sparse_set.drain().with_id();
assert_eq!(drain.next(), Some((EntityId::new(0), 0)));
assert_eq!(drain.next(), Some((EntityId::new(1), 1)));
assert_eq!(drain.next(), None);
drop(drain);
assert_eq!(sparse_set.len(), 0);
assert_eq!(sparse_set.private_get(EntityId::new(0)), None);
}
#[test]
fn drain_empty() {
let mut sparse_set = SparseSet::<u32>::new();
assert_eq!(sparse_set.drain().next(), None);
assert_eq!(sparse_set.drain().with_id().next(), None);
assert_eq!(sparse_set.len(), 0);
}
#[test]
fn unstable_sort() {
let mut array = crate::sparse_set::SparseSet::new();
for i in (0..100).rev() {
let mut entity_id = crate::entity_id::EntityId::zero();
entity_id.set_index(100 - i);
array.insert(entity_id, i);
}
array.sort_unstable();
for window in array.data.windows(2) {
assert!(window[0] < window[1]);
}
for i in 0..100 {
let mut entity_id = crate::entity_id::EntityId::zero();
entity_id.set_index(100 - i);
assert_eq!(array.private_get(entity_id), Some(&i));
}
}
#[test]
fn partially_sorted_unstable_sort() {
let mut array = crate::sparse_set::SparseSet::new();
for i in 0..20 {
let mut entity_id = crate::entity_id::EntityId::zero();
entity_id.set_index(i);
assert!(array.insert(entity_id, i).is_none());
}
for i in (20..100).rev() {
let mut entity_id = crate::entity_id::EntityId::zero();
entity_id.set_index(100 - i + 20);
assert!(array.insert(entity_id, i).is_none());
}
array.sort_unstable();
for window in array.data.windows(2) {
assert!(window[0] < window[1]);
}
for i in 0..20 {
let mut entity_id = crate::entity_id::EntityId::zero();
entity_id.set_index(i);
assert_eq!(array.private_get(entity_id), Some(&i));
}
for i in 20..100 {
let mut entity_id = crate::entity_id::EntityId::zero();
entity_id.set_index(100 - i + 20);
assert_eq!(array.private_get(entity_id), Some(&i));
}
}