goud_engine/ecs/sparse_set.rs
1//! Sparse set data structure for component storage.
2//!
3//! A sparse set provides O(1) insertion, deletion, and lookup while maintaining
4//! cache-friendly iteration over dense data. This is the foundation for ECS
5//! component storage.
6//!
7//! # Design Pattern: Sparse Set
8//!
9//! The sparse set uses two arrays:
10//!
11//! - **Sparse**: Maps entity indices to dense array indices (may have gaps)
12//! - **Dense**: Packed array of entities for cache-friendly iteration
13//! - **Values**: Packed array of component values, parallel to dense
14//!
15//! ```text
16//! Entity(3) has component "A"
17//! Entity(7) has component "B"
18//! Entity(1) has component "C"
19//!
20//! Sparse: [_, Some(2), _, Some(0), _, _, _, Some(1)]
21//! 0 1 2 3 4 5 6 7
22//!
23//! Dense: [Entity(3), Entity(7), Entity(1)]
24//! 0 1 2
25//!
26//! Values: ["A", "B", "C"]
27//! 0 1 2
28//! ```
29//!
30//! # Performance Characteristics
31//!
32//! | Operation | Time Complexity | Notes |
33//! |-----------|-----------------|-------|
34//! | insert | O(1) amortized | May grow sparse vec |
35//! | remove | O(1) | Uses swap-remove |
36//! | get | O(1) | |
37//! | contains | O(1) | |
38//! | iterate | O(n) | Cache-friendly, contiguous |
39//!
40//! # Example
41//!
42//! ```
43//! use goud_engine::ecs::{Entity, SparseSet};
44//!
45//! let mut set: SparseSet<String> = SparseSet::new();
46//!
47//! let e1 = Entity::new(0, 1);
48//! let e2 = Entity::new(5, 1);
49//!
50//! set.insert(e1, "Hello".to_string());
51//! set.insert(e2, "World".to_string());
52//!
53//! assert_eq!(set.get(e1), Some(&"Hello".to_string()));
54//! assert!(set.contains(e2));
55//!
56//! // Cache-friendly iteration
57//! for (entity, value) in set.iter() {
58//! println!("{}: {}", entity, value);
59//! }
60//! ```
61//!
62//! # Thread Safety
63//!
64//! `SparseSet<T>` is `Send` if `T: Send` and `Sync` if `T: Sync`.
65//! The sparse set itself is not internally synchronized - wrap in
66//! `RwLock` or similar for concurrent access.
67
68use super::Entity;
69
70/// A sparse set storing values of type `T` indexed by [`Entity`].
71///
72/// Provides O(1) access operations while maintaining cache-friendly iteration.
73/// This is the primary storage backend for ECS components.
74///
75/// # Type Parameters
76///
77/// - `T`: The value type stored in the set
78///
79/// # Memory Layout
80///
81/// The sparse set trades memory for performance:
82///
83/// - Sparse vec grows to max entity index seen (sparse memory usage)
84/// - Dense and values vecs are tightly packed (no gaps)
85///
86/// For entities with indices 0, 100, 1000, the sparse vec will have 1001 entries,
87/// but dense/values will only have 3 entries.
88#[derive(Debug)]
89pub struct SparseSet<T> {
90 /// Maps entity index to position in dense array.
91 /// `sparse[entity.index()]` = Some(dense_index) if entity has a value.
92 sparse: Vec<Option<usize>>,
93
94 /// Packed array of entities that have values.
95 /// Enables O(1) removal via swap-remove.
96 dense: Vec<Entity>,
97
98 /// Packed array of values, parallel to `dense`.
99 /// `values[i]` is the value for `dense[i]`.
100 values: Vec<T>,
101}
102
103impl<T> SparseSet<T> {
104 /// Creates a new, empty sparse set.
105 ///
106 /// # Example
107 ///
108 /// ```
109 /// use goud_engine::ecs::SparseSet;
110 ///
111 /// let set: SparseSet<i32> = SparseSet::new();
112 /// assert!(set.is_empty());
113 /// assert_eq!(set.len(), 0);
114 /// ```
115 #[inline]
116 pub fn new() -> Self {
117 Self {
118 sparse: Vec::new(),
119 dense: Vec::new(),
120 values: Vec::new(),
121 }
122 }
123
124 /// Creates a sparse set with pre-allocated capacity.
125 ///
126 /// This pre-allocates the dense and values vectors, but not the sparse
127 /// vector (which grows on demand based on entity indices).
128 ///
129 /// # Arguments
130 ///
131 /// * `capacity` - Number of elements to pre-allocate
132 ///
133 /// # Example
134 ///
135 /// ```
136 /// use goud_engine::ecs::SparseSet;
137 ///
138 /// let set: SparseSet<String> = SparseSet::with_capacity(1000);
139 /// assert!(set.is_empty());
140 /// ```
141 #[inline]
142 pub fn with_capacity(capacity: usize) -> Self {
143 Self {
144 sparse: Vec::new(),
145 dense: Vec::with_capacity(capacity),
146 values: Vec::with_capacity(capacity),
147 }
148 }
149
150 /// Inserts a value for the given entity.
151 ///
152 /// If the entity already has a value, it is replaced and the old value
153 /// is returned. Otherwise, `None` is returned.
154 ///
155 /// # Arguments
156 ///
157 /// * `entity` - The entity to associate with the value
158 /// * `value` - The value to store
159 ///
160 /// # Returns
161 ///
162 /// The previous value if one existed, or `None`.
163 ///
164 /// # Panics
165 ///
166 /// Panics if the entity is a placeholder (`Entity::PLACEHOLDER`).
167 ///
168 /// # Example
169 ///
170 /// ```
171 /// use goud_engine::ecs::{Entity, SparseSet};
172 ///
173 /// let mut set = SparseSet::new();
174 /// let entity = Entity::new(0, 1);
175 ///
176 /// assert_eq!(set.insert(entity, 42), None);
177 /// assert_eq!(set.insert(entity, 99), Some(42)); // Returns old value
178 /// assert_eq!(set.get(entity), Some(&99));
179 /// ```
180 pub fn insert(&mut self, entity: Entity, value: T) -> Option<T> {
181 assert!(
182 !entity.is_placeholder(),
183 "Cannot insert with placeholder entity"
184 );
185
186 let index = entity.index() as usize;
187
188 // Grow sparse vec if needed
189 if index >= self.sparse.len() {
190 self.sparse.resize(index + 1, None);
191 }
192
193 if let Some(dense_index) = self.sparse[index] {
194 // Entity already has a value - replace it
195 let old_value = std::mem::replace(&mut self.values[dense_index], value);
196 Some(old_value)
197 } else {
198 // New entity - add to dense arrays
199 let dense_index = self.dense.len();
200 self.sparse[index] = Some(dense_index);
201 self.dense.push(entity);
202 self.values.push(value);
203 None
204 }
205 }
206
207 /// Removes the value for the given entity.
208 ///
209 /// Uses swap-remove to maintain dense packing: the last element is
210 /// moved to fill the gap, keeping iteration cache-friendly.
211 ///
212 /// # Arguments
213 ///
214 /// * `entity` - The entity whose value to remove
215 ///
216 /// # Returns
217 ///
218 /// The removed value if one existed, or `None`.
219 ///
220 /// # Example
221 ///
222 /// ```
223 /// use goud_engine::ecs::{Entity, SparseSet};
224 ///
225 /// let mut set = SparseSet::new();
226 /// let entity = Entity::new(0, 1);
227 ///
228 /// set.insert(entity, "hello");
229 /// assert_eq!(set.remove(entity), Some("hello"));
230 /// assert_eq!(set.remove(entity), None); // Already removed
231 /// ```
232 pub fn remove(&mut self, entity: Entity) -> Option<T> {
233 if entity.is_placeholder() {
234 return None;
235 }
236
237 let index = entity.index() as usize;
238
239 // Check bounds
240 if index >= self.sparse.len() {
241 return None;
242 }
243
244 // Get dense index
245 let dense_index = self.sparse[index]?;
246 self.sparse[index] = None;
247
248 // Get the last entity in the dense array
249 let last_index = self.dense.len() - 1;
250
251 if dense_index != last_index {
252 // Swap with last element
253 let last_entity = self.dense[last_index];
254 self.dense.swap(dense_index, last_index);
255 self.values.swap(dense_index, last_index);
256
257 // Update sparse pointer for swapped entity
258 self.sparse[last_entity.index() as usize] = Some(dense_index);
259 }
260
261 // Remove last element (which is now our removed entity)
262 self.dense.pop();
263 self.values.pop()
264 }
265
266 /// Returns a reference to the value for the given entity.
267 ///
268 /// # Arguments
269 ///
270 /// * `entity` - The entity to look up
271 ///
272 /// # Returns
273 ///
274 /// A reference to the value if the entity has one, or `None`.
275 ///
276 /// # Example
277 ///
278 /// ```
279 /// use goud_engine::ecs::{Entity, SparseSet};
280 ///
281 /// let mut set = SparseSet::new();
282 /// let entity = Entity::new(0, 1);
283 ///
284 /// set.insert(entity, 42);
285 /// assert_eq!(set.get(entity), Some(&42));
286 ///
287 /// let missing = Entity::new(999, 1);
288 /// assert_eq!(set.get(missing), None);
289 /// ```
290 #[inline]
291 pub fn get(&self, entity: Entity) -> Option<&T> {
292 if entity.is_placeholder() {
293 return None;
294 }
295
296 let index = entity.index() as usize;
297
298 if index >= self.sparse.len() {
299 return None;
300 }
301
302 let dense_index = self.sparse[index]?;
303 Some(&self.values[dense_index])
304 }
305
306 /// Returns a mutable reference to the value for the given entity.
307 ///
308 /// # Arguments
309 ///
310 /// * `entity` - The entity to look up
311 ///
312 /// # Returns
313 ///
314 /// A mutable reference to the value if the entity has one, or `None`.
315 ///
316 /// # Example
317 ///
318 /// ```
319 /// use goud_engine::ecs::{Entity, SparseSet};
320 ///
321 /// let mut set = SparseSet::new();
322 /// let entity = Entity::new(0, 1);
323 ///
324 /// set.insert(entity, 42);
325 ///
326 /// if let Some(value) = set.get_mut(entity) {
327 /// *value = 100;
328 /// }
329 ///
330 /// assert_eq!(set.get(entity), Some(&100));
331 /// ```
332 #[inline]
333 pub fn get_mut(&mut self, entity: Entity) -> Option<&mut T> {
334 if entity.is_placeholder() {
335 return None;
336 }
337
338 let index = entity.index() as usize;
339
340 if index >= self.sparse.len() {
341 return None;
342 }
343
344 let dense_index = self.sparse[index]?;
345 Some(&mut self.values[dense_index])
346 }
347
348 /// Returns `true` if the entity has a value in this set.
349 ///
350 /// # Arguments
351 ///
352 /// * `entity` - The entity to check
353 ///
354 /// # Example
355 ///
356 /// ```
357 /// use goud_engine::ecs::{Entity, SparseSet};
358 ///
359 /// let mut set = SparseSet::new();
360 /// let entity = Entity::new(0, 1);
361 ///
362 /// assert!(!set.contains(entity));
363 /// set.insert(entity, "value");
364 /// assert!(set.contains(entity));
365 /// ```
366 #[inline]
367 pub fn contains(&self, entity: Entity) -> bool {
368 if entity.is_placeholder() {
369 return false;
370 }
371
372 let index = entity.index() as usize;
373
374 if index >= self.sparse.len() {
375 return false;
376 }
377
378 self.sparse[index].is_some()
379 }
380
381 /// Returns the number of entities with values in this set.
382 ///
383 /// # Example
384 ///
385 /// ```
386 /// use goud_engine::ecs::{Entity, SparseSet};
387 ///
388 /// let mut set = SparseSet::new();
389 /// assert_eq!(set.len(), 0);
390 ///
391 /// set.insert(Entity::new(0, 1), "a");
392 /// set.insert(Entity::new(5, 1), "b");
393 /// assert_eq!(set.len(), 2);
394 /// ```
395 #[inline]
396 pub fn len(&self) -> usize {
397 self.dense.len()
398 }
399
400 /// Returns `true` if the set contains no values.
401 ///
402 /// # Example
403 ///
404 /// ```
405 /// use goud_engine::ecs::{Entity, SparseSet};
406 ///
407 /// let mut set: SparseSet<i32> = SparseSet::new();
408 /// assert!(set.is_empty());
409 ///
410 /// set.insert(Entity::new(0, 1), 42);
411 /// assert!(!set.is_empty());
412 /// ```
413 #[inline]
414 pub fn is_empty(&self) -> bool {
415 self.dense.is_empty()
416 }
417
418 /// Removes all values from the set.
419 ///
420 /// This clears all three internal arrays. After calling `clear()`,
421 /// `len()` will return 0.
422 ///
423 /// # Example
424 ///
425 /// ```
426 /// use goud_engine::ecs::{Entity, SparseSet};
427 ///
428 /// let mut set = SparseSet::new();
429 /// set.insert(Entity::new(0, 1), "a");
430 /// set.insert(Entity::new(1, 1), "b");
431 /// assert_eq!(set.len(), 2);
432 ///
433 /// set.clear();
434 /// assert!(set.is_empty());
435 /// ```
436 pub fn clear(&mut self) {
437 self.sparse.clear();
438 self.dense.clear();
439 self.values.clear();
440 }
441
442 /// Reserves capacity for at least `additional` more elements.
443 ///
444 /// This affects the dense and values arrays, not the sparse array
445 /// (which grows based on entity indices).
446 ///
447 /// # Arguments
448 ///
449 /// * `additional` - Number of additional elements to reserve
450 ///
451 /// # Example
452 ///
453 /// ```
454 /// use goud_engine::ecs::SparseSet;
455 ///
456 /// let mut set: SparseSet<i32> = SparseSet::new();
457 /// set.reserve(1000);
458 /// ```
459 pub fn reserve(&mut self, additional: usize) {
460 self.dense.reserve(additional);
461 self.values.reserve(additional);
462 }
463
464 // =========================================================================
465 // Iteration
466 // =========================================================================
467
468 /// Returns an iterator over `(Entity, &T)` pairs.
469 ///
470 /// Iteration is cache-friendly because it traverses the dense array
471 /// sequentially.
472 ///
473 /// # Example
474 ///
475 /// ```
476 /// use goud_engine::ecs::{Entity, SparseSet};
477 ///
478 /// let mut set = SparseSet::new();
479 /// set.insert(Entity::new(0, 1), "a");
480 /// set.insert(Entity::new(1, 1), "b");
481 ///
482 /// for (entity, value) in set.iter() {
483 /// println!("{}: {}", entity, value);
484 /// }
485 /// ```
486 #[inline]
487 pub fn iter(&self) -> SparseSetIter<'_, T> {
488 SparseSetIter {
489 dense: self.dense.iter(),
490 values: self.values.iter(),
491 }
492 }
493
494 /// Returns a mutable iterator over `(Entity, &mut T)` pairs.
495 ///
496 /// # Example
497 ///
498 /// ```
499 /// use goud_engine::ecs::{Entity, SparseSet};
500 ///
501 /// let mut set = SparseSet::new();
502 /// set.insert(Entity::new(0, 1), 1);
503 /// set.insert(Entity::new(1, 1), 2);
504 ///
505 /// for (_, value) in set.iter_mut() {
506 /// *value *= 10;
507 /// }
508 ///
509 /// assert_eq!(set.get(Entity::new(0, 1)), Some(&10));
510 /// assert_eq!(set.get(Entity::new(1, 1)), Some(&20));
511 /// ```
512 #[inline]
513 pub fn iter_mut(&mut self) -> SparseSetIterMut<'_, T> {
514 SparseSetIterMut {
515 dense: self.dense.iter(),
516 values: self.values.iter_mut(),
517 }
518 }
519
520 /// Returns an iterator over all entities in the set.
521 ///
522 /// # Example
523 ///
524 /// ```
525 /// use goud_engine::ecs::{Entity, SparseSet};
526 ///
527 /// let mut set = SparseSet::new();
528 /// set.insert(Entity::new(0, 1), "a");
529 /// set.insert(Entity::new(5, 1), "b");
530 ///
531 /// let entities: Vec<_> = set.entities().collect();
532 /// assert_eq!(entities.len(), 2);
533 /// ```
534 #[inline]
535 pub fn entities(&self) -> impl Iterator<Item = Entity> + '_ {
536 self.dense.iter().copied()
537 }
538
539 /// Returns an iterator over all values in the set.
540 ///
541 /// # Example
542 ///
543 /// ```
544 /// use goud_engine::ecs::{Entity, SparseSet};
545 ///
546 /// let mut set = SparseSet::new();
547 /// set.insert(Entity::new(0, 1), 10);
548 /// set.insert(Entity::new(5, 1), 20);
549 ///
550 /// let sum: i32 = set.values().sum();
551 /// assert_eq!(sum, 30);
552 /// ```
553 #[inline]
554 pub fn values(&self) -> impl Iterator<Item = &T> {
555 self.values.iter()
556 }
557
558 /// Returns a mutable iterator over all values in the set.
559 ///
560 /// # Example
561 ///
562 /// ```
563 /// use goud_engine::ecs::{Entity, SparseSet};
564 ///
565 /// let mut set = SparseSet::new();
566 /// set.insert(Entity::new(0, 1), 10);
567 /// set.insert(Entity::new(1, 1), 20);
568 ///
569 /// for value in set.values_mut() {
570 /// *value += 1;
571 /// }
572 ///
573 /// let sum: i32 = set.values().sum();
574 /// assert_eq!(sum, 32); // 11 + 21
575 /// ```
576 #[inline]
577 pub fn values_mut(&mut self) -> impl Iterator<Item = &mut T> {
578 self.values.iter_mut()
579 }
580
581 // =========================================================================
582 // Advanced / Internal Methods
583 // =========================================================================
584
585 /// Returns the raw entity array for direct access.
586 ///
587 /// This is useful for bulk operations or implementing custom iterators.
588 ///
589 /// # Example
590 ///
591 /// ```
592 /// use goud_engine::ecs::{Entity, SparseSet};
593 ///
594 /// let mut set = SparseSet::new();
595 /// set.insert(Entity::new(0, 1), "a");
596 /// set.insert(Entity::new(1, 1), "b");
597 ///
598 /// let dense = set.dense();
599 /// assert_eq!(dense.len(), 2);
600 /// ```
601 #[inline]
602 pub fn dense(&self) -> &[Entity] {
603 &self.dense
604 }
605
606 /// Returns the dense index for an entity, if it exists.
607 ///
608 /// This is an advanced method for implementing custom storage operations.
609 ///
610 /// # Arguments
611 ///
612 /// * `entity` - The entity to look up
613 ///
614 /// # Returns
615 ///
616 /// The index in the dense array, or `None` if the entity has no value.
617 #[inline]
618 pub fn dense_index(&self, entity: Entity) -> Option<usize> {
619 if entity.is_placeholder() {
620 return None;
621 }
622
623 let index = entity.index() as usize;
624
625 if index >= self.sparse.len() {
626 return None;
627 }
628
629 self.sparse[index]
630 }
631
632 /// Returns the value at the given dense index.
633 ///
634 /// # Safety
635 ///
636 /// This method does not validate the index. Use `dense_index()` to get
637 /// a valid index first.
638 ///
639 /// # Arguments
640 ///
641 /// * `dense_index` - Index into the dense/values arrays
642 #[inline]
643 pub fn get_by_dense_index(&self, dense_index: usize) -> Option<&T> {
644 self.values.get(dense_index)
645 }
646
647 /// Returns a mutable reference to the value at the given dense index.
648 #[inline]
649 pub fn get_mut_by_dense_index(&mut self, dense_index: usize) -> Option<&mut T> {
650 self.values.get_mut(dense_index)
651 }
652}
653
654impl<T> Default for SparseSet<T> {
655 fn default() -> Self {
656 Self::new()
657 }
658}
659
660impl<T: Clone> Clone for SparseSet<T> {
661 fn clone(&self) -> Self {
662 Self {
663 sparse: self.sparse.clone(),
664 dense: self.dense.clone(),
665 values: self.values.clone(),
666 }
667 }
668}
669
670// =============================================================================
671// Iterator Types
672// =============================================================================
673
674/// An iterator over `(Entity, &T)` pairs in a sparse set.
675///
676/// Created by [`SparseSet::iter()`].
677#[derive(Debug)]
678pub struct SparseSetIter<'a, T> {
679 dense: std::slice::Iter<'a, Entity>,
680 values: std::slice::Iter<'a, T>,
681}
682
683impl<'a, T> Iterator for SparseSetIter<'a, T> {
684 type Item = (Entity, &'a T);
685
686 #[inline]
687 fn next(&mut self) -> Option<Self::Item> {
688 let entity = *self.dense.next()?;
689 let value = self.values.next()?;
690 Some((entity, value))
691 }
692
693 #[inline]
694 fn size_hint(&self) -> (usize, Option<usize>) {
695 self.dense.size_hint()
696 }
697}
698
699impl<T> ExactSizeIterator for SparseSetIter<'_, T> {
700 #[inline]
701 fn len(&self) -> usize {
702 self.dense.len()
703 }
704}
705
706impl<T> std::iter::FusedIterator for SparseSetIter<'_, T> {}
707
708/// A mutable iterator over `(Entity, &mut T)` pairs in a sparse set.
709///
710/// Created by [`SparseSet::iter_mut()`].
711#[derive(Debug)]
712pub struct SparseSetIterMut<'a, T> {
713 dense: std::slice::Iter<'a, Entity>,
714 values: std::slice::IterMut<'a, T>,
715}
716
717impl<'a, T> Iterator for SparseSetIterMut<'a, T> {
718 type Item = (Entity, &'a mut T);
719
720 #[inline]
721 fn next(&mut self) -> Option<Self::Item> {
722 let entity = *self.dense.next()?;
723 let value = self.values.next()?;
724 Some((entity, value))
725 }
726
727 #[inline]
728 fn size_hint(&self) -> (usize, Option<usize>) {
729 self.dense.size_hint()
730 }
731}
732
733impl<T> ExactSizeIterator for SparseSetIterMut<'_, T> {
734 #[inline]
735 fn len(&self) -> usize {
736 self.dense.len()
737 }
738}
739
740impl<T> std::iter::FusedIterator for SparseSetIterMut<'_, T> {}
741
742// =============================================================================
743// IntoIterator Implementations
744// =============================================================================
745
746impl<'a, T> IntoIterator for &'a SparseSet<T> {
747 type Item = (Entity, &'a T);
748 type IntoIter = SparseSetIter<'a, T>;
749
750 fn into_iter(self) -> Self::IntoIter {
751 self.iter()
752 }
753}
754
755impl<'a, T> IntoIterator for &'a mut SparseSet<T> {
756 type Item = (Entity, &'a mut T);
757 type IntoIter = SparseSetIterMut<'a, T>;
758
759 fn into_iter(self) -> Self::IntoIter {
760 self.iter_mut()
761 }
762}
763
764// =============================================================================
765// Unit Tests
766// =============================================================================
767
768#[cfg(test)]
769mod tests {
770 use super::*;
771
772 // =========================================================================
773 // Construction Tests
774 // =========================================================================
775
776 #[test]
777 fn test_new() {
778 let set: SparseSet<i32> = SparseSet::new();
779 assert!(set.is_empty());
780 assert_eq!(set.len(), 0);
781 }
782
783 #[test]
784 fn test_with_capacity() {
785 let set: SparseSet<i32> = SparseSet::with_capacity(100);
786 assert!(set.is_empty());
787 assert_eq!(set.len(), 0);
788 }
789
790 #[test]
791 fn test_default() {
792 let set: SparseSet<i32> = SparseSet::default();
793 assert!(set.is_empty());
794 }
795
796 // =========================================================================
797 // Insert Tests
798 // =========================================================================
799
800 #[test]
801 fn test_insert_single() {
802 let mut set = SparseSet::new();
803 let entity = Entity::new(0, 1);
804
805 let old = set.insert(entity, 42);
806 assert_eq!(old, None);
807 assert_eq!(set.len(), 1);
808 assert!(set.contains(entity));
809 assert_eq!(set.get(entity), Some(&42));
810 }
811
812 #[test]
813 fn test_insert_multiple() {
814 let mut set = SparseSet::new();
815
816 let e1 = Entity::new(0, 1);
817 let e2 = Entity::new(5, 1);
818 let e3 = Entity::new(10, 1);
819
820 set.insert(e1, "a");
821 set.insert(e2, "b");
822 set.insert(e3, "c");
823
824 assert_eq!(set.len(), 3);
825 assert_eq!(set.get(e1), Some(&"a"));
826 assert_eq!(set.get(e2), Some(&"b"));
827 assert_eq!(set.get(e3), Some(&"c"));
828 }
829
830 #[test]
831 fn test_insert_replace() {
832 let mut set = SparseSet::new();
833 let entity = Entity::new(0, 1);
834
835 let old1 = set.insert(entity, 10);
836 assert_eq!(old1, None);
837
838 let old2 = set.insert(entity, 20);
839 assert_eq!(old2, Some(10));
840
841 assert_eq!(set.len(), 1); // Still just one entry
842 assert_eq!(set.get(entity), Some(&20));
843 }
844
845 #[test]
846 #[should_panic(expected = "Cannot insert with placeholder")]
847 fn test_insert_placeholder_panics() {
848 let mut set: SparseSet<i32> = SparseSet::new();
849 set.insert(Entity::PLACEHOLDER, 42);
850 }
851
852 #[test]
853 fn test_insert_sparse_indices() {
854 // Test with widely spread entity indices
855 let mut set = SparseSet::new();
856
857 let e1 = Entity::new(0, 1);
858 let e2 = Entity::new(1000, 1);
859 let e3 = Entity::new(5000, 1);
860
861 set.insert(e1, 1);
862 set.insert(e2, 2);
863 set.insert(e3, 3);
864
865 assert_eq!(set.len(), 3);
866 assert_eq!(set.get(e1), Some(&1));
867 assert_eq!(set.get(e2), Some(&2));
868 assert_eq!(set.get(e3), Some(&3));
869 }
870
871 // =========================================================================
872 // Remove Tests
873 // =========================================================================
874
875 #[test]
876 fn test_remove_single() {
877 let mut set = SparseSet::new();
878 let entity = Entity::new(0, 1);
879
880 set.insert(entity, 42);
881 let removed = set.remove(entity);
882
883 assert_eq!(removed, Some(42));
884 assert!(set.is_empty());
885 assert!(!set.contains(entity));
886 }
887
888 #[test]
889 fn test_remove_nonexistent() {
890 let mut set: SparseSet<i32> = SparseSet::new();
891 let entity = Entity::new(0, 1);
892
893 let removed = set.remove(entity);
894 assert_eq!(removed, None);
895 }
896
897 #[test]
898 fn test_remove_placeholder() {
899 let mut set: SparseSet<i32> = SparseSet::new();
900 let removed = set.remove(Entity::PLACEHOLDER);
901 assert_eq!(removed, None);
902 }
903
904 #[test]
905 fn test_remove_double() {
906 let mut set = SparseSet::new();
907 let entity = Entity::new(0, 1);
908
909 set.insert(entity, 42);
910
911 let first = set.remove(entity);
912 let second = set.remove(entity);
913
914 assert_eq!(first, Some(42));
915 assert_eq!(second, None);
916 }
917
918 #[test]
919 fn test_remove_swap_correctness() {
920 // Test that swap-remove maintains correctness
921 let mut set = SparseSet::new();
922
923 let e1 = Entity::new(0, 1);
924 let e2 = Entity::new(1, 1);
925 let e3 = Entity::new(2, 1);
926
927 set.insert(e1, "first");
928 set.insert(e2, "second");
929 set.insert(e3, "third");
930
931 // Remove e1 (first) - e3 should be swapped in
932 set.remove(e1);
933
934 // e2 and e3 should still be accessible
935 assert_eq!(set.get(e2), Some(&"second"));
936 assert_eq!(set.get(e3), Some(&"third"));
937 assert_eq!(set.len(), 2);
938
939 // Dense array should have e3 at index 0, e2 at index 1
940 let entities: Vec<_> = set.entities().collect();
941 assert_eq!(entities.len(), 2);
942 assert!(entities.contains(&e2));
943 assert!(entities.contains(&e3));
944 }
945
946 #[test]
947 fn test_remove_middle() {
948 let mut set = SparseSet::new();
949
950 let e1 = Entity::new(0, 1);
951 let e2 = Entity::new(1, 1);
952 let e3 = Entity::new(2, 1);
953
954 set.insert(e1, 1);
955 set.insert(e2, 2);
956 set.insert(e3, 3);
957
958 // Remove middle element
959 set.remove(e2);
960
961 assert_eq!(set.get(e1), Some(&1));
962 assert_eq!(set.get(e2), None);
963 assert_eq!(set.get(e3), Some(&3));
964 assert_eq!(set.len(), 2);
965 }
966
967 #[test]
968 fn test_remove_last() {
969 let mut set = SparseSet::new();
970
971 let e1 = Entity::new(0, 1);
972 let e2 = Entity::new(1, 1);
973
974 set.insert(e1, 1);
975 set.insert(e2, 2);
976
977 // Remove last element (no swap needed)
978 set.remove(e2);
979
980 assert_eq!(set.get(e1), Some(&1));
981 assert_eq!(set.get(e2), None);
982 assert_eq!(set.len(), 1);
983 }
984
985 // =========================================================================
986 // Get Tests
987 // =========================================================================
988
989 #[test]
990 fn test_get() {
991 let mut set = SparseSet::new();
992 let entity = Entity::new(0, 1);
993
994 set.insert(entity, 42);
995
996 assert_eq!(set.get(entity), Some(&42));
997 }
998
999 #[test]
1000 fn test_get_nonexistent() {
1001 let set: SparseSet<i32> = SparseSet::new();
1002 let entity = Entity::new(0, 1);
1003
1004 assert_eq!(set.get(entity), None);
1005 }
1006
1007 #[test]
1008 fn test_get_placeholder() {
1009 let mut set = SparseSet::new();
1010 set.insert(Entity::new(0, 1), 42);
1011
1012 assert_eq!(set.get(Entity::PLACEHOLDER), None);
1013 }
1014
1015 #[test]
1016 fn test_get_out_of_bounds() {
1017 let mut set = SparseSet::new();
1018 set.insert(Entity::new(0, 1), 42);
1019
1020 // Entity index beyond sparse array
1021 let entity = Entity::new(1000, 1);
1022 assert_eq!(set.get(entity), None);
1023 }
1024
1025 #[test]
1026 fn test_get_mut() {
1027 let mut set = SparseSet::new();
1028 let entity = Entity::new(0, 1);
1029
1030 set.insert(entity, 42);
1031
1032 if let Some(value) = set.get_mut(entity) {
1033 *value = 100;
1034 }
1035
1036 assert_eq!(set.get(entity), Some(&100));
1037 }
1038
1039 #[test]
1040 fn test_get_mut_nonexistent() {
1041 let mut set: SparseSet<i32> = SparseSet::new();
1042 let entity = Entity::new(0, 1);
1043
1044 assert_eq!(set.get_mut(entity), None);
1045 }
1046
1047 // =========================================================================
1048 // Contains Tests
1049 // =========================================================================
1050
1051 #[test]
1052 fn test_contains() {
1053 let mut set = SparseSet::new();
1054 let e1 = Entity::new(0, 1);
1055 let e2 = Entity::new(1, 1);
1056
1057 set.insert(e1, 42);
1058
1059 assert!(set.contains(e1));
1060 assert!(!set.contains(e2));
1061 }
1062
1063 #[test]
1064 fn test_contains_placeholder() {
1065 let set: SparseSet<i32> = SparseSet::new();
1066 assert!(!set.contains(Entity::PLACEHOLDER));
1067 }
1068
1069 #[test]
1070 fn test_contains_after_remove() {
1071 let mut set = SparseSet::new();
1072 let entity = Entity::new(0, 1);
1073
1074 set.insert(entity, 42);
1075 assert!(set.contains(entity));
1076
1077 set.remove(entity);
1078 assert!(!set.contains(entity));
1079 }
1080
1081 // =========================================================================
1082 // Len / IsEmpty Tests
1083 // =========================================================================
1084
1085 #[test]
1086 fn test_len_empty() {
1087 let set: SparseSet<i32> = SparseSet::new();
1088 assert_eq!(set.len(), 0);
1089 assert!(set.is_empty());
1090 }
1091
1092 #[test]
1093 fn test_len_after_insert() {
1094 let mut set = SparseSet::new();
1095
1096 set.insert(Entity::new(0, 1), 1);
1097 assert_eq!(set.len(), 1);
1098
1099 set.insert(Entity::new(1, 1), 2);
1100 assert_eq!(set.len(), 2);
1101 }
1102
1103 #[test]
1104 fn test_len_after_remove() {
1105 let mut set = SparseSet::new();
1106
1107 let e1 = Entity::new(0, 1);
1108 let e2 = Entity::new(1, 1);
1109
1110 set.insert(e1, 1);
1111 set.insert(e2, 2);
1112 assert_eq!(set.len(), 2);
1113
1114 set.remove(e1);
1115 assert_eq!(set.len(), 1);
1116
1117 set.remove(e2);
1118 assert_eq!(set.len(), 0);
1119 assert!(set.is_empty());
1120 }
1121
1122 #[test]
1123 fn test_len_after_replace() {
1124 let mut set = SparseSet::new();
1125 let entity = Entity::new(0, 1);
1126
1127 set.insert(entity, 1);
1128 assert_eq!(set.len(), 1);
1129
1130 set.insert(entity, 2); // Replace
1131 assert_eq!(set.len(), 1); // Still 1
1132 }
1133
1134 // =========================================================================
1135 // Clear Tests
1136 // =========================================================================
1137
1138 #[test]
1139 fn test_clear() {
1140 let mut set = SparseSet::new();
1141
1142 set.insert(Entity::new(0, 1), 1);
1143 set.insert(Entity::new(1, 1), 2);
1144 set.insert(Entity::new(2, 1), 3);
1145
1146 assert_eq!(set.len(), 3);
1147
1148 set.clear();
1149
1150 assert!(set.is_empty());
1151 assert_eq!(set.get(Entity::new(0, 1)), None);
1152 assert_eq!(set.get(Entity::new(1, 1)), None);
1153 assert_eq!(set.get(Entity::new(2, 1)), None);
1154 }
1155
1156 // =========================================================================
1157 // Iteration Tests
1158 // =========================================================================
1159
1160 #[test]
1161 fn test_iter() {
1162 let mut set = SparseSet::new();
1163
1164 let e1 = Entity::new(0, 1);
1165 let e2 = Entity::new(1, 1);
1166 let e3 = Entity::new(2, 1);
1167
1168 set.insert(e1, 10);
1169 set.insert(e2, 20);
1170 set.insert(e3, 30);
1171
1172 let mut items: Vec<_> = set.iter().map(|(e, v)| (e, *v)).collect();
1173 items.sort_by_key(|(e, _)| e.index());
1174
1175 assert_eq!(items, vec![(e1, 10), (e2, 20), (e3, 30)]);
1176 }
1177
1178 #[test]
1179 fn test_iter_empty() {
1180 let set: SparseSet<i32> = SparseSet::new();
1181 let items: Vec<_> = set.iter().collect();
1182 assert!(items.is_empty());
1183 }
1184
1185 #[test]
1186 fn test_iter_mut() {
1187 let mut set = SparseSet::new();
1188
1189 set.insert(Entity::new(0, 1), 1);
1190 set.insert(Entity::new(1, 1), 2);
1191 set.insert(Entity::new(2, 1), 3);
1192
1193 for (_, value) in set.iter_mut() {
1194 *value *= 10;
1195 }
1196
1197 assert_eq!(set.get(Entity::new(0, 1)), Some(&10));
1198 assert_eq!(set.get(Entity::new(1, 1)), Some(&20));
1199 assert_eq!(set.get(Entity::new(2, 1)), Some(&30));
1200 }
1201
1202 #[test]
1203 fn test_entities() {
1204 let mut set = SparseSet::new();
1205
1206 let e1 = Entity::new(0, 1);
1207 let e2 = Entity::new(5, 1);
1208 let e3 = Entity::new(10, 1);
1209
1210 set.insert(e1, "a");
1211 set.insert(e2, "b");
1212 set.insert(e3, "c");
1213
1214 let entities: Vec<_> = set.entities().collect();
1215 assert_eq!(entities.len(), 3);
1216 assert!(entities.contains(&e1));
1217 assert!(entities.contains(&e2));
1218 assert!(entities.contains(&e3));
1219 }
1220
1221 #[test]
1222 fn test_values() {
1223 let mut set = SparseSet::new();
1224
1225 set.insert(Entity::new(0, 1), 10);
1226 set.insert(Entity::new(1, 1), 20);
1227 set.insert(Entity::new(2, 1), 30);
1228
1229 let sum: i32 = set.values().sum();
1230 assert_eq!(sum, 60);
1231 }
1232
1233 #[test]
1234 fn test_values_mut() {
1235 let mut set = SparseSet::new();
1236
1237 set.insert(Entity::new(0, 1), 1);
1238 set.insert(Entity::new(1, 1), 2);
1239 set.insert(Entity::new(2, 1), 3);
1240
1241 for value in set.values_mut() {
1242 *value += 10;
1243 }
1244
1245 let sum: i32 = set.values().sum();
1246 assert_eq!(sum, 36); // 11 + 12 + 13
1247 }
1248
1249 #[test]
1250 fn test_into_iter_ref() {
1251 let mut set = SparseSet::new();
1252 set.insert(Entity::new(0, 1), 42);
1253
1254 let mut count = 0;
1255 for (_, _) in &set {
1256 count += 1;
1257 }
1258 assert_eq!(count, 1);
1259 }
1260
1261 #[test]
1262 fn test_into_iter_mut() {
1263 let mut set = SparseSet::new();
1264 set.insert(Entity::new(0, 1), 42);
1265
1266 for (_, value) in &mut set {
1267 *value = 100;
1268 }
1269
1270 assert_eq!(set.get(Entity::new(0, 1)), Some(&100));
1271 }
1272
1273 #[test]
1274 fn test_iter_size_hint() {
1275 let mut set = SparseSet::new();
1276 set.insert(Entity::new(0, 1), 1);
1277 set.insert(Entity::new(1, 1), 2);
1278 set.insert(Entity::new(2, 1), 3);
1279
1280 let iter = set.iter();
1281 assert_eq!(iter.size_hint(), (3, Some(3)));
1282 assert_eq!(iter.len(), 3);
1283 }
1284
1285 // =========================================================================
1286 // Advanced Method Tests
1287 // =========================================================================
1288
1289 #[test]
1290 fn test_dense() {
1291 let mut set = SparseSet::new();
1292
1293 let e1 = Entity::new(0, 1);
1294 let e2 = Entity::new(1, 1);
1295
1296 set.insert(e1, "a");
1297 set.insert(e2, "b");
1298
1299 let dense = set.dense();
1300 assert_eq!(dense.len(), 2);
1301 assert_eq!(dense[0], e1);
1302 assert_eq!(dense[1], e2);
1303 }
1304
1305 #[test]
1306 fn test_dense_index() {
1307 let mut set = SparseSet::new();
1308
1309 let e1 = Entity::new(5, 1);
1310 let e2 = Entity::new(10, 1);
1311
1312 set.insert(e1, "a");
1313 set.insert(e2, "b");
1314
1315 assert_eq!(set.dense_index(e1), Some(0));
1316 assert_eq!(set.dense_index(e2), Some(1));
1317 assert_eq!(set.dense_index(Entity::new(0, 1)), None);
1318 assert_eq!(set.dense_index(Entity::PLACEHOLDER), None);
1319 }
1320
1321 #[test]
1322 fn test_get_by_dense_index() {
1323 let mut set = SparseSet::new();
1324
1325 set.insert(Entity::new(0, 1), "first");
1326 set.insert(Entity::new(1, 1), "second");
1327
1328 assert_eq!(set.get_by_dense_index(0), Some(&"first"));
1329 assert_eq!(set.get_by_dense_index(1), Some(&"second"));
1330 assert_eq!(set.get_by_dense_index(2), None);
1331 }
1332
1333 #[test]
1334 fn test_get_mut_by_dense_index() {
1335 let mut set = SparseSet::new();
1336
1337 set.insert(Entity::new(0, 1), 10);
1338 set.insert(Entity::new(1, 1), 20);
1339
1340 if let Some(value) = set.get_mut_by_dense_index(0) {
1341 *value = 100;
1342 }
1343
1344 assert_eq!(set.get(Entity::new(0, 1)), Some(&100));
1345 }
1346
1347 // =========================================================================
1348 // Clone Tests
1349 // =========================================================================
1350
1351 #[test]
1352 fn test_clone() {
1353 let mut set = SparseSet::new();
1354
1355 let e1 = Entity::new(0, 1);
1356 let e2 = Entity::new(1, 1);
1357
1358 set.insert(e1, 10);
1359 set.insert(e2, 20);
1360
1361 let cloned = set.clone();
1362
1363 assert_eq!(cloned.len(), 2);
1364 assert_eq!(cloned.get(e1), Some(&10));
1365 assert_eq!(cloned.get(e2), Some(&20));
1366
1367 // Modifications to original don't affect clone
1368 set.insert(e1, 100);
1369 assert_eq!(cloned.get(e1), Some(&10));
1370 }
1371
1372 // =========================================================================
1373 // Stress Tests
1374 // =========================================================================
1375
1376 #[test]
1377 fn test_stress_many_entities() {
1378 let mut set = SparseSet::new();
1379 const COUNT: usize = 10_000;
1380
1381 // Insert many entities
1382 for i in 0..COUNT {
1383 let entity = Entity::new(i as u32, 1);
1384 set.insert(entity, i as i32);
1385 }
1386
1387 assert_eq!(set.len(), COUNT);
1388
1389 // Verify all accessible
1390 for i in 0..COUNT {
1391 let entity = Entity::new(i as u32, 1);
1392 assert_eq!(set.get(entity), Some(&(i as i32)));
1393 }
1394
1395 // Remove half
1396 for i in (0..COUNT).step_by(2) {
1397 let entity = Entity::new(i as u32, 1);
1398 set.remove(entity);
1399 }
1400
1401 assert_eq!(set.len(), COUNT / 2);
1402
1403 // Verify removed vs remaining
1404 for i in 0..COUNT {
1405 let entity = Entity::new(i as u32, 1);
1406 if i % 2 == 0 {
1407 assert_eq!(set.get(entity), None);
1408 } else {
1409 assert_eq!(set.get(entity), Some(&(i as i32)));
1410 }
1411 }
1412 }
1413
1414 #[test]
1415 fn test_stress_sparse_indices() {
1416 let mut set = SparseSet::new();
1417
1418 // Insert with very sparse indices
1419 let indices: Vec<u32> = vec![0, 100, 1000, 10000, 50000];
1420
1421 for (i, &idx) in indices.iter().enumerate() {
1422 let entity = Entity::new(idx, 1);
1423 set.insert(entity, i as i32);
1424 }
1425
1426 assert_eq!(set.len(), 5);
1427
1428 // Verify all accessible
1429 for (i, &idx) in indices.iter().enumerate() {
1430 let entity = Entity::new(idx, 1);
1431 assert_eq!(set.get(entity), Some(&(i as i32)));
1432 }
1433 }
1434
1435 #[test]
1436 fn test_stress_insert_remove_cycle() {
1437 let mut set = SparseSet::new();
1438 const ITERATIONS: usize = 100;
1439 const BATCH_SIZE: usize = 100;
1440
1441 for _ in 0..ITERATIONS {
1442 // Insert batch
1443 for i in 0..BATCH_SIZE {
1444 let entity = Entity::new(i as u32, 1);
1445 set.insert(entity, i as i32);
1446 }
1447
1448 assert_eq!(set.len(), BATCH_SIZE);
1449
1450 // Remove all
1451 for i in 0..BATCH_SIZE {
1452 let entity = Entity::new(i as u32, 1);
1453 set.remove(entity);
1454 }
1455
1456 assert!(set.is_empty());
1457 }
1458 }
1459
1460 // =========================================================================
1461 // Thread Safety Tests (Compile-time)
1462 // =========================================================================
1463
1464 #[test]
1465 fn test_send_sync() {
1466 fn assert_send<T: Send>() {}
1467 fn assert_sync<T: Sync>() {}
1468
1469 // SparseSet<T> is Send if T is Send
1470 assert_send::<SparseSet<i32>>();
1471 assert_send::<SparseSet<String>>();
1472
1473 // SparseSet<T> is Sync if T is Sync
1474 assert_sync::<SparseSet<i32>>();
1475 assert_sync::<SparseSet<String>>();
1476 }
1477}