rapier2d/data/arena.rs
1//! Arena adapted from the generational-arena crate.
2//!
3//! See <https://github.com/fitzgen/generational-arena/blob/master/src/lib.rs>.
4//! This has been modified to have a fully deterministic deserialization (including for the order of
5//! Index attribution after a deserialization of the arena).
6#[cfg(feature = "alloc")]
7use crate::alloc_prelude::*;
8#[cfg(feature = "alloc")]
9use alloc::vec;
10#[cfg(feature = "alloc")]
11use core::cmp;
12#[cfg(feature = "alloc")]
13use core::iter::{self, Extend, FromIterator, FusedIterator};
14#[cfg(feature = "alloc")]
15use core::mem;
16#[cfg(feature = "alloc")]
17use core::ops;
18#[cfg(feature = "alloc")]
19use core::slice;
20
21/// The `Arena` allows inserting and removing elements that are referred to by
22/// `Index`.
23///
24/// [See the module-level documentation for example usage and motivation.](./index.html)
25#[cfg(feature = "alloc")]
26#[derive(Clone, Debug)]
27#[cfg_attr(feature = "serde-serialize", derive(Serialize, Deserialize))]
28pub struct Arena<T> {
29 items: Vec<Entry<T>>,
30 generation: u32,
31 free_list_head: Option<u32>,
32 len: usize,
33}
34
35#[cfg(feature = "alloc")]
36#[derive(Clone, Debug)]
37#[cfg_attr(feature = "serde-serialize", derive(Serialize, Deserialize))]
38enum Entry<T> {
39 Free { next_free: Option<u32> },
40 Occupied { generation: u32, value: T },
41}
42
43/// An index (and generation) into an `Arena`.
44///
45/// To get an `Index`, insert an element into an `Arena`, and the `Index` for
46/// that element will be returned.
47///
48/// # Examples
49///
50/// ```
51/// # use rapier3d::data::arena::Arena;
52/// let mut arena = Arena::new();
53/// let idx = arena.insert(123);
54/// assert_eq!(arena[idx], 123);
55/// ```
56#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
57#[cfg_attr(feature = "serde-serialize", derive(Serialize, Deserialize))]
58pub struct Index {
59 index: u32,
60 generation: u32,
61}
62
63impl Default for Index {
64 fn default() -> Self {
65 Self::from_raw_parts(crate::INVALID_U32, crate::INVALID_U32)
66 }
67}
68
69impl Index {
70 /// Create a new `Index` from its raw parts.
71 ///
72 /// The parts must have been returned from an earlier call to
73 /// `into_raw_parts`.
74 ///
75 /// Providing arbitrary values will lead to malformed indices and ultimately
76 /// panics.
77 pub fn from_raw_parts(index: u32, generation: u32) -> Index {
78 Index { index, generation }
79 }
80
81 /// Convert this `Index` into its raw parts.
82 ///
83 /// This niche method is useful for converting an `Index` into another
84 /// identifier type. Usually, you should prefer a newtype wrapper around
85 /// `Index` like `pub struct MyIdentifier(Index);`. However, for external
86 /// types whose definition you can't customize, but which you can construct
87 /// instances of, this method can be useful.
88 pub fn into_raw_parts(self) -> (u32, u32) {
89 (self.index, self.generation)
90 }
91}
92
93#[cfg(feature = "alloc")]
94const DEFAULT_CAPACITY: usize = 4;
95
96#[cfg(feature = "alloc")]
97impl<T> Default for Arena<T> {
98 fn default() -> Arena<T> {
99 Arena::new()
100 }
101}
102
103#[cfg(feature = "alloc")]
104impl<T> Arena<T> {
105 /// Constructs a new, empty `Arena`.
106 ///
107 /// # Examples
108 ///
109 /// ```
110 /// # use rapier3d::data::arena::Arena;
111 /// let mut arena = Arena::<usize>::new();
112 /// # let _ = arena;
113 /// ```
114 pub fn new() -> Arena<T> {
115 Arena::with_capacity(DEFAULT_CAPACITY)
116 }
117
118 /// Constructs a new, empty `Arena<T>` with the specified capacity.
119 ///
120 /// The `Arena<T>` will be able to hold `n` elements without further allocation.
121 ///
122 /// # Examples
123 ///
124 /// ```
125 /// # use rapier3d::data::arena::Arena;
126 /// let mut arena = Arena::with_capacity(10);
127 ///
128 /// // These insertions will not require further allocation.
129 /// for i in 0..10 {
130 /// assert!(arena.try_insert(i).is_ok());
131 /// }
132 ///
133 /// // But now we are at capacity, and there is no more room.
134 /// assert!(arena.try_insert(99).is_err());
135 /// ```
136 pub fn with_capacity(n: usize) -> Arena<T> {
137 let n = cmp::max(n, 1);
138 let mut arena = Arena {
139 items: Vec::new(),
140 generation: 0,
141 free_list_head: None,
142 len: 0,
143 };
144 arena.reserve(n);
145 arena
146 }
147
148 /// Clear all the items inside the arena, but keep its allocation.
149 ///
150 /// # Examples
151 ///
152 /// ```
153 /// # use rapier3d::data::arena::Arena;
154 /// let mut arena = Arena::with_capacity(1);
155 /// arena.insert(42);
156 /// arena.insert(43);
157 ///
158 /// arena.clear();
159 ///
160 /// assert_eq!(arena.capacity(), 2);
161 /// ```
162 pub fn clear(&mut self) {
163 self.items.clear();
164
165 let end = self.items.capacity() as u32;
166 self.items.extend((0..end).map(|i| {
167 if i == end - 1 {
168 Entry::Free { next_free: None }
169 } else {
170 Entry::Free {
171 next_free: Some(i + 1),
172 }
173 }
174 }));
175 self.free_list_head = Some(0);
176 self.len = 0;
177 }
178
179 /// Attempts to insert `value` into the arena using existing capacity.
180 ///
181 /// This method will never allocate new capacity in the arena.
182 ///
183 /// If insertion succeeds, then the `value`'s index is returned. If
184 /// insertion fails, then `Err(value)` is returned to give ownership of
185 /// `value` back to the caller.
186 ///
187 /// # Examples
188 ///
189 /// ```
190 /// # use rapier3d::data::arena::Arena;
191 /// let mut arena = Arena::new();
192 ///
193 /// match arena.try_insert(42) {
194 /// Ok(idx) => {
195 /// // Insertion succeeded.
196 /// assert_eq!(arena[idx], 42);
197 /// }
198 /// Err(x) => {
199 /// // Insertion failed.
200 /// assert_eq!(x, 42);
201 /// }
202 /// };
203 /// ```
204 #[inline]
205 pub fn try_insert(&mut self, value: T) -> Result<Index, T> {
206 match self.try_alloc_next_index() {
207 None => Err(value),
208 Some(index) => {
209 self.items[index.index as usize] = Entry::Occupied {
210 generation: self.generation,
211 value,
212 };
213 Ok(index)
214 }
215 }
216 }
217
218 /// Attempts to insert the value returned by `create` into the arena using existing capacity.
219 /// `create` is called with the new value's associated index, allowing values that know their own index.
220 ///
221 /// This method will never allocate new capacity in the arena.
222 ///
223 /// If insertion succeeds, then the new index is returned. If
224 /// insertion fails, then `Err(create)` is returned to give ownership of
225 /// `create` back to the caller.
226 ///
227 /// # Examples
228 ///
229 /// ```
230 /// # use rapier3d::data::arena::{Arena, Index};
231 /// let mut arena = Arena::new();
232 ///
233 /// match arena.try_insert_with(|idx| (42, idx)) {
234 /// Ok(idx) => {
235 /// // Insertion succeeded.
236 /// assert_eq!(arena[idx].0, 42);
237 /// assert_eq!(arena[idx].1, idx);
238 /// }
239 /// Err(x) => {
240 /// // Insertion failed.
241 /// }
242 /// };
243 /// ```
244 #[inline]
245 pub fn try_insert_with<F: FnOnce(Index) -> T>(&mut self, create: F) -> Result<Index, F> {
246 match self.try_alloc_next_index() {
247 None => Err(create),
248 Some(index) => {
249 self.items[index.index as usize] = Entry::Occupied {
250 generation: self.generation,
251 value: create(index),
252 };
253 Ok(index)
254 }
255 }
256 }
257
258 #[inline]
259 fn try_alloc_next_index(&mut self) -> Option<Index> {
260 match self.free_list_head {
261 None => None,
262 Some(i) => match self.items[i as usize] {
263 Entry::Occupied { .. } => panic!("corrupt free list"),
264 Entry::Free { next_free } => {
265 self.free_list_head = next_free;
266 self.len += 1;
267 Some(Index {
268 index: i,
269 generation: self.generation,
270 })
271 }
272 },
273 }
274 }
275
276 /// Insert `value` into the arena, allocating more capacity if necessary.
277 ///
278 /// The `value`'s associated index in the arena is returned.
279 ///
280 /// # Examples
281 ///
282 /// ```
283 /// # use rapier3d::data::arena::Arena;
284 /// let mut arena = Arena::new();
285 ///
286 /// let idx = arena.insert(42);
287 /// assert_eq!(arena[idx], 42);
288 /// ```
289 #[inline]
290 pub fn insert(&mut self, value: T) -> Index {
291 match self.try_insert(value) {
292 Ok(i) => i,
293 Err(value) => self.insert_slow_path(value),
294 }
295 }
296
297 /// Insert the value returned by `create` into the arena, allocating more capacity if necessary.
298 /// `create` is called with the new value's associated index, allowing values that know their own index.
299 ///
300 /// The new value's associated index in the arena is returned.
301 ///
302 /// # Examples
303 ///
304 /// ```
305 /// # use rapier3d::data::arena::{Arena, Index};
306 /// let mut arena = Arena::new();
307 ///
308 /// let idx = arena.insert_with(|idx| (42, idx));
309 /// assert_eq!(arena[idx].0, 42);
310 /// assert_eq!(arena[idx].1, idx);
311 /// ```
312 #[inline]
313 pub fn insert_with(&mut self, create: impl FnOnce(Index) -> T) -> Index {
314 match self.try_insert_with(create) {
315 Ok(i) => i,
316 Err(create) => self.insert_with_slow_path(create),
317 }
318 }
319
320 #[inline(never)]
321 fn insert_slow_path(&mut self, value: T) -> Index {
322 let len = self.items.len();
323 self.reserve(len);
324 self.try_insert(value)
325 .map_err(|_| ())
326 .expect("inserting will always succeed after reserving additional space")
327 }
328
329 #[inline(never)]
330 fn insert_with_slow_path(&mut self, create: impl FnOnce(Index) -> T) -> Index {
331 let len = self.items.len();
332 self.reserve(len);
333 self.try_insert_with(create)
334 .map_err(|_| ())
335 .expect("inserting will always succeed after reserving additional space")
336 }
337
338 /// Remove the element at index `i` from the arena.
339 ///
340 /// If the element at index `i` is still in the arena, then it is
341 /// returned. If it is not in the arena, then `None` is returned.
342 ///
343 /// # Examples
344 ///
345 /// ```
346 /// # use rapier3d::data::arena::Arena;
347 /// let mut arena = Arena::new();
348 /// let idx = arena.insert(42);
349 ///
350 /// assert_eq!(arena.remove(idx), Some(42));
351 /// assert_eq!(arena.remove(idx), None);
352 /// ```
353 pub fn remove(&mut self, i: Index) -> Option<T> {
354 if i.index >= self.items.len() as u32 {
355 return None;
356 }
357
358 match self.items[i.index as usize] {
359 Entry::Occupied { generation, .. } if i.generation == generation => {
360 let entry = mem::replace(
361 &mut self.items[i.index as usize],
362 Entry::Free {
363 next_free: self.free_list_head,
364 },
365 );
366 self.generation += 1;
367 self.free_list_head = Some(i.index);
368 self.len -= 1;
369
370 match entry {
371 Entry::Occupied {
372 generation: _,
373 value,
374 } => Some(value),
375 _ => unreachable!(),
376 }
377 }
378 _ => None,
379 }
380 }
381
382 /// Retains only the elements specified by the predicate.
383 ///
384 /// In other words, remove all indices such that `predicate(index, &value)` returns `false`.
385 ///
386 /// # Examples
387 ///
388 /// ```
389 /// # use rapier3d::data::arena::Arena;
390 /// let mut crew = Arena::new();
391 /// crew.extend(&["Jim Hawkins", "John Silver", "Alexander Smollett", "Israel Hands"]);
392 /// let pirates = ["John Silver", "Israel Hands"]; // too dangerous to keep them around
393 /// crew.retain(|_index, member| !pirates.contains(member));
394 /// let mut crew_members = crew.iter().map(|(_, member)| **member);
395 /// assert_eq!(crew_members.next(), Some("Jim Hawkins"));
396 /// assert_eq!(crew_members.next(), Some("Alexander Smollett"));
397 /// assert!(crew_members.next().is_none());
398 /// ```
399 pub fn retain(&mut self, mut predicate: impl FnMut(Index, &mut T) -> bool) {
400 for i in 0..self.capacity() as u32 {
401 let remove = match &mut self.items[i as usize] {
402 Entry::Occupied { generation, value } => {
403 let index = Index {
404 index: i,
405 generation: *generation,
406 };
407 if predicate(index, value) {
408 None
409 } else {
410 Some(index)
411 }
412 }
413
414 _ => None,
415 };
416 if let Some(index) = remove {
417 self.remove(index);
418 }
419 }
420 }
421
422 /// Is the element at index `i` in the arena?
423 ///
424 /// Returns `true` if the element at `i` is in the arena, `false` otherwise.
425 ///
426 /// # Examples
427 ///
428 /// ```
429 /// # use rapier3d::data::arena::Arena;
430 /// let mut arena = Arena::new();
431 /// let idx = arena.insert(42);
432 ///
433 /// assert!(arena.contains(idx));
434 /// arena.remove(idx);
435 /// assert!(!arena.contains(idx));
436 /// ```
437 pub fn contains(&self, i: Index) -> bool {
438 self.get(i).is_some()
439 }
440
441 /// Get a shared reference to the element at index `i` if it is in the
442 /// arena.
443 ///
444 /// If the element at index `i` is not in the arena, then `None` is returned.
445 ///
446 /// # Examples
447 ///
448 /// ```
449 /// # use rapier3d::data::arena::Arena;
450 /// let mut arena = Arena::new();
451 /// let idx = arena.insert(42);
452 ///
453 /// assert_eq!(arena.get(idx), Some(&42));
454 /// arena.remove(idx);
455 /// assert!(arena.get(idx).is_none());
456 /// ```
457 pub fn get(&self, i: Index) -> Option<&T> {
458 match self.items.get(i.index as usize) {
459 Some(Entry::Occupied { generation, value }) if *generation == i.generation => {
460 Some(value)
461 }
462 _ => None,
463 }
464 }
465
466 /// Get an exclusive reference to the element at index `i` if it is in the
467 /// arena.
468 ///
469 /// If the element at index `i` is not in the arena, then `None` is returned.
470 ///
471 /// # Examples
472 ///
473 /// ```
474 /// # use rapier3d::data::arena::Arena;
475 /// let mut arena = Arena::new();
476 /// let idx = arena.insert(42);
477 ///
478 /// *arena.get_mut(idx).unwrap() += 1;
479 /// assert_eq!(arena.remove(idx), Some(43));
480 /// assert!(arena.get_mut(idx).is_none());
481 /// ```
482 pub fn get_mut(&mut self, i: Index) -> Option<&mut T> {
483 match self.items.get_mut(i.index as usize) {
484 Some(Entry::Occupied { generation, value }) if *generation == i.generation => {
485 Some(value)
486 }
487 _ => None,
488 }
489 }
490
491 /// Get a pair of exclusive references to the elements at index `i1` and `i2` if it is in the
492 /// arena.
493 ///
494 /// If the element at index `i1` or `i2` is not in the arena, then `None` is returned for this
495 /// element.
496 ///
497 /// # Panics
498 ///
499 /// Panics if `i1` and `i2` are pointing to the same item of the arena.
500 ///
501 /// # Examples
502 ///
503 /// ```
504 /// # use rapier3d::data::arena::Arena;
505 /// let mut arena = Arena::new();
506 /// let idx1 = arena.insert(0);
507 /// let idx2 = arena.insert(1);
508 ///
509 /// {
510 /// let (item1, item2) = arena.get2_mut(idx1, idx2);
511 ///
512 /// *item1.unwrap() = 3;
513 /// *item2.unwrap() = 4;
514 /// }
515 ///
516 /// assert_eq!(arena[idx1], 3);
517 /// assert_eq!(arena[idx2], 4);
518 /// ```
519 pub fn get2_mut(&mut self, i1: Index, i2: Index) -> (Option<&mut T>, Option<&mut T>) {
520 let len = self.items.len() as u32;
521
522 if i1.index == i2.index {
523 assert!(i1.generation != i2.generation);
524
525 if i1.generation > i2.generation {
526 return (self.get_mut(i1), None);
527 }
528 return (None, self.get_mut(i2));
529 }
530
531 if i1.index >= len {
532 return (None, self.get_mut(i2));
533 } else if i2.index >= len {
534 return (self.get_mut(i1), None);
535 }
536
537 let (raw_item1, raw_item2) = {
538 let (xs, ys) = self
539 .items
540 .split_at_mut(cmp::max(i1.index, i2.index) as usize);
541 if i1.index < i2.index {
542 (&mut xs[i1.index as usize], &mut ys[0])
543 } else {
544 (&mut ys[0], &mut xs[i2.index as usize])
545 }
546 };
547
548 let item1 = match raw_item1 {
549 Entry::Occupied { generation, value } if *generation == i1.generation => Some(value),
550 _ => None,
551 };
552
553 let item2 = match raw_item2 {
554 Entry::Occupied { generation, value } if *generation == i2.generation => Some(value),
555 _ => None,
556 };
557
558 (item1, item2)
559 }
560
561 /// Get the length of this arena.
562 ///
563 /// The length is the number of elements the arena holds.
564 ///
565 /// # Examples
566 ///
567 /// ```
568 /// # use rapier3d::data::arena::Arena;
569 /// let mut arena = Arena::new();
570 /// assert_eq!(arena.len(), 0);
571 ///
572 /// let idx = arena.insert(42);
573 /// assert_eq!(arena.len(), 1);
574 ///
575 /// let _ = arena.insert(0);
576 /// assert_eq!(arena.len(), 2);
577 ///
578 /// assert_eq!(arena.remove(idx), Some(42));
579 /// assert_eq!(arena.len(), 1);
580 /// ```
581 pub fn len(&self) -> usize {
582 self.len
583 }
584
585 /// Returns true if the arena contains no elements
586 ///
587 /// # Examples
588 ///
589 /// ```
590 /// # use rapier3d::data::arena::Arena;
591 /// let mut arena = Arena::new();
592 /// assert!(arena.is_empty());
593 ///
594 /// let idx = arena.insert(42);
595 /// assert!(!arena.is_empty());
596 ///
597 /// assert_eq!(arena.remove(idx), Some(42));
598 /// assert!(arena.is_empty());
599 /// ```
600 pub fn is_empty(&self) -> bool {
601 self.len == 0
602 }
603
604 /// Get the capacity of this arena.
605 ///
606 /// The capacity is the maximum number of elements the arena can hold
607 /// without further allocation, including however many it currently
608 /// contains.
609 ///
610 /// # Examples
611 ///
612 /// ```
613 /// # use rapier3d::data::arena::Arena;
614 /// let mut arena = Arena::with_capacity(10);
615 /// assert_eq!(arena.capacity(), 10);
616 ///
617 /// // `try_insert` does not allocate new capacity.
618 /// for i in 0..10 {
619 /// assert!(arena.try_insert(1).is_ok());
620 /// assert_eq!(arena.capacity(), 10);
621 /// }
622 ///
623 /// // But `insert` will if the arena is already at capacity.
624 /// arena.insert(0);
625 /// assert!(arena.capacity() > 10);
626 /// ```
627 pub fn capacity(&self) -> usize {
628 self.items.len()
629 }
630
631 /// Allocate space for `additional_capacity` more elements in the arena.
632 ///
633 /// # Panics
634 ///
635 /// Panics if this causes the capacity to overflow.
636 ///
637 /// # Examples
638 ///
639 /// ```
640 /// # use rapier3d::data::arena::Arena;
641 /// let mut arena = Arena::with_capacity(10);
642 /// arena.reserve(5);
643 /// assert_eq!(arena.capacity(), 15);
644 /// # let _: Arena<usize> = arena;
645 /// ```
646 pub fn reserve(&mut self, additional_capacity: usize) {
647 let start = self.items.len();
648 let end = self.items.len() + additional_capacity;
649 let old_head = self.free_list_head;
650 self.items.reserve_exact(additional_capacity);
651 self.items.extend((start..end).map(|i| {
652 if i == end - 1 {
653 Entry::Free {
654 next_free: old_head,
655 }
656 } else {
657 Entry::Free {
658 next_free: Some(i as u32 + 1),
659 }
660 }
661 }));
662 self.free_list_head = Some(start as u32);
663 }
664
665 /// Iterate over shared references to the elements in this arena.
666 ///
667 /// Yields pairs of `(Index, &T)` items.
668 ///
669 /// Order of iteration is not defined.
670 ///
671 /// # Examples
672 ///
673 /// ```
674 /// # use rapier3d::data::arena::Arena;
675 /// let mut arena = Arena::new();
676 /// for i in 0..10 {
677 /// arena.insert(i * i);
678 /// }
679 ///
680 /// for (idx, value) in arena.iter() {
681 /// println!("{} is at index {:?}", value, idx);
682 /// }
683 /// ```
684 pub fn iter(&self) -> Iter<'_, T> {
685 Iter {
686 len: self.len,
687 inner: self.items.iter().enumerate(),
688 }
689 }
690
691 /// Iterate over exclusive references to the elements in this arena.
692 ///
693 /// Yields pairs of `(Index, &mut T)` items.
694 ///
695 /// Order of iteration is not defined.
696 ///
697 /// # Examples
698 ///
699 /// ```
700 /// # use rapier3d::data::arena::Arena;
701 /// let mut arena = Arena::new();
702 /// for i in 0..10 {
703 /// arena.insert(i * i);
704 /// }
705 ///
706 /// for (_idx, value) in arena.iter_mut() {
707 /// *value += 5;
708 /// }
709 /// ```
710 pub fn iter_mut(&mut self) -> IterMut<'_, T> {
711 IterMut {
712 len: self.len,
713 inner: self.items.iter_mut().enumerate(),
714 }
715 }
716
717 /// Iterate over elements of the arena and remove them.
718 ///
719 /// Yields pairs of `(Index, T)` items.
720 ///
721 /// Order of iteration is not defined.
722 ///
723 /// Note: All elements are removed even if the iterator is only partially consumed or not consumed at all.
724 ///
725 /// # Examples
726 ///
727 /// ```
728 /// # use rapier3d::data::arena::Arena;
729 /// let mut arena = Arena::new();
730 /// let idx_1 = arena.insert("hello");
731 /// let idx_2 = arena.insert("world");
732 ///
733 /// assert!(arena.get(idx_1).is_some());
734 /// assert!(arena.get(idx_2).is_some());
735 /// for (idx, value) in arena.drain() {
736 /// assert!((idx == idx_1 && value == "hello") || (idx == idx_2 && value == "world"));
737 /// }
738 /// assert!(arena.get(idx_1).is_none());
739 /// assert!(arena.get(idx_2).is_none());
740 /// ```
741 pub fn drain(&mut self) -> Drain<'_, T> {
742 Drain {
743 inner: self.items.drain(..).enumerate(),
744 }
745 }
746
747 /// Given an i of `usize` without a generation, get a shared reference
748 /// to the element and the matching `Index` of the entry behind `i`.
749 ///
750 /// This method is useful when you know there might be an element at the
751 /// position i, but don't know its generation or precise Index.
752 ///
753 /// Use cases include using indexing such as Hierarchical BitMap Indexing or
754 /// other kinds of bit-efficient indexing.
755 ///
756 /// You should use the `get` method instead most of the time.
757 pub fn get_unknown_gen(&self, i: u32) -> Option<(&T, Index)> {
758 match self.items.get(i as usize) {
759 Some(Entry::Occupied { generation, value }) => Some((
760 value,
761 Index {
762 generation: *generation,
763 index: i,
764 },
765 )),
766 _ => None,
767 }
768 }
769
770 /// Given an i of `usize` without a generation, get an exclusive reference
771 /// to the element and the matching `Index` of the entry behind `i`.
772 ///
773 /// This method is useful when you know there might be an element at the
774 /// position i, but don't know its generation or precise Index.
775 ///
776 /// Use cases include using indexing such as Hierarchical BitMap Indexing or
777 /// other kinds of bit-efficient indexing.
778 ///
779 /// You should use the `get_mut` method instead most of the time.
780 pub fn get_unknown_gen_mut(&mut self, i: u32) -> Option<(&mut T, Index)> {
781 match self.items.get_mut(i as usize) {
782 Some(Entry::Occupied { generation, value }) => Some((
783 value,
784 Index {
785 generation: *generation,
786 index: i,
787 },
788 )),
789 _ => None,
790 }
791 }
792}
793
794#[cfg(feature = "alloc")]
795impl<T> IntoIterator for Arena<T> {
796 type Item = T;
797 type IntoIter = IntoIter<T>;
798 fn into_iter(self) -> Self::IntoIter {
799 IntoIter {
800 len: self.len,
801 inner: self.items.into_iter(),
802 }
803 }
804}
805
806/// An iterator over the elements in an arena.
807///
808/// Yields `T` items.
809///
810/// Order of iteration is not defined.
811///
812/// # Examples
813///
814/// ```
815/// # use rapier3d::data::arena::Arena;
816/// let mut arena = Arena::new();
817/// for i in 0..10 {
818/// arena.insert(i * i);
819/// }
820///
821/// for value in arena {
822/// assert!(value < 100);
823/// }
824/// ```
825#[cfg(feature = "alloc")]
826#[derive(Clone, Debug)]
827pub struct IntoIter<T> {
828 len: usize,
829 inner: vec::IntoIter<Entry<T>>,
830}
831
832#[cfg(feature = "alloc")]
833impl<T> Iterator for IntoIter<T> {
834 type Item = T;
835
836 fn next(&mut self) -> Option<Self::Item> {
837 loop {
838 match self.inner.next() {
839 Some(Entry::Free { .. }) => continue,
840 Some(Entry::Occupied { value, .. }) => {
841 self.len -= 1;
842 return Some(value);
843 }
844 None => {
845 debug_assert_eq!(self.len, 0);
846 return None;
847 }
848 }
849 }
850 }
851
852 fn size_hint(&self) -> (usize, Option<usize>) {
853 (self.len, Some(self.len))
854 }
855}
856
857#[cfg(feature = "alloc")]
858impl<T> DoubleEndedIterator for IntoIter<T> {
859 fn next_back(&mut self) -> Option<Self::Item> {
860 loop {
861 match self.inner.next_back() {
862 Some(Entry::Free { .. }) => continue,
863 Some(Entry::Occupied { value, .. }) => {
864 self.len -= 1;
865 return Some(value);
866 }
867 None => {
868 debug_assert_eq!(self.len, 0);
869 return None;
870 }
871 }
872 }
873 }
874}
875
876#[cfg(feature = "alloc")]
877impl<T> ExactSizeIterator for IntoIter<T> {
878 fn len(&self) -> usize {
879 self.len
880 }
881}
882
883#[cfg(feature = "alloc")]
884impl<T> FusedIterator for IntoIter<T> {}
885
886#[cfg(feature = "alloc")]
887impl<'a, T> IntoIterator for &'a Arena<T> {
888 type Item = (Index, &'a T);
889 type IntoIter = Iter<'a, T>;
890 fn into_iter(self) -> Self::IntoIter {
891 self.iter()
892 }
893}
894
895/// An iterator over shared references to the elements in an arena.
896///
897/// Yields pairs of `(Index, &T)` items.
898///
899/// Order of iteration is not defined.
900///
901/// # Examples
902///
903/// ```
904/// # use rapier3d::data::arena::Arena;
905/// let mut arena = Arena::new();
906/// for i in 0..10 {
907/// arena.insert(i * i);
908/// }
909///
910/// for (idx, value) in &arena {
911/// println!("{} is at index {:?}", value, idx);
912/// }
913/// ```
914#[cfg(feature = "alloc")]
915#[derive(Clone, Debug)]
916pub struct Iter<'a, T: 'a> {
917 len: usize,
918 inner: iter::Enumerate<slice::Iter<'a, Entry<T>>>,
919}
920
921#[cfg(feature = "alloc")]
922impl<'a, T> Iterator for Iter<'a, T> {
923 type Item = (Index, &'a T);
924
925 fn next(&mut self) -> Option<Self::Item> {
926 loop {
927 match self.inner.next() {
928 Some((_, &Entry::Free { .. })) => continue,
929 Some((
930 index,
931 &Entry::Occupied {
932 generation,
933 ref value,
934 },
935 )) => {
936 self.len -= 1;
937 let idx = Index {
938 index: index as u32,
939 generation,
940 };
941 return Some((idx, value));
942 }
943 None => {
944 debug_assert_eq!(self.len, 0);
945 return None;
946 }
947 }
948 }
949 }
950
951 fn size_hint(&self) -> (usize, Option<usize>) {
952 (self.len, Some(self.len))
953 }
954}
955
956#[cfg(feature = "alloc")]
957impl<T> DoubleEndedIterator for Iter<'_, T> {
958 fn next_back(&mut self) -> Option<Self::Item> {
959 loop {
960 match self.inner.next_back() {
961 Some((_, &Entry::Free { .. })) => continue,
962 Some((
963 index,
964 &Entry::Occupied {
965 generation,
966 ref value,
967 },
968 )) => {
969 self.len -= 1;
970 let idx = Index {
971 index: index as u32,
972 generation,
973 };
974 return Some((idx, value));
975 }
976 None => {
977 debug_assert_eq!(self.len, 0);
978 return None;
979 }
980 }
981 }
982 }
983}
984
985#[cfg(feature = "alloc")]
986impl<T> ExactSizeIterator for Iter<'_, T> {
987 fn len(&self) -> usize {
988 self.len
989 }
990}
991
992#[cfg(feature = "alloc")]
993impl<T> FusedIterator for Iter<'_, T> {}
994
995#[cfg(feature = "alloc")]
996impl<'a, T> IntoIterator for &'a mut Arena<T> {
997 type Item = (Index, &'a mut T);
998 type IntoIter = IterMut<'a, T>;
999 fn into_iter(self) -> Self::IntoIter {
1000 self.iter_mut()
1001 }
1002}
1003
1004/// An iterator over exclusive references to elements in this arena.
1005///
1006/// Yields pairs of `(Index, &mut T)` items.
1007///
1008/// Order of iteration is not defined.
1009///
1010/// # Examples
1011///
1012/// ```
1013/// # use rapier3d::data::arena::Arena;
1014/// let mut arena = Arena::new();
1015/// for i in 0..10 {
1016/// arena.insert(i * i);
1017/// }
1018///
1019/// for (_idx, value) in &mut arena {
1020/// *value += 5;
1021/// }
1022/// ```
1023#[cfg(feature = "alloc")]
1024#[derive(Debug)]
1025pub struct IterMut<'a, T: 'a> {
1026 len: usize,
1027 inner: iter::Enumerate<slice::IterMut<'a, Entry<T>>>,
1028}
1029
1030#[cfg(feature = "alloc")]
1031impl<'a, T> Iterator for IterMut<'a, T> {
1032 type Item = (Index, &'a mut T);
1033
1034 fn next(&mut self) -> Option<Self::Item> {
1035 loop {
1036 match self.inner.next() {
1037 Some((_, &mut Entry::Free { .. })) => continue,
1038 Some((
1039 index,
1040 &mut Entry::Occupied {
1041 generation,
1042 ref mut value,
1043 },
1044 )) => {
1045 self.len -= 1;
1046 let idx = Index {
1047 index: index as u32,
1048 generation,
1049 };
1050 return Some((idx, value));
1051 }
1052 None => {
1053 debug_assert_eq!(self.len, 0);
1054 return None;
1055 }
1056 }
1057 }
1058 }
1059
1060 fn size_hint(&self) -> (usize, Option<usize>) {
1061 (self.len, Some(self.len))
1062 }
1063}
1064
1065#[cfg(feature = "alloc")]
1066impl<T> DoubleEndedIterator for IterMut<'_, T> {
1067 fn next_back(&mut self) -> Option<Self::Item> {
1068 loop {
1069 match self.inner.next_back() {
1070 Some((_, &mut Entry::Free { .. })) => continue,
1071 Some((
1072 index,
1073 &mut Entry::Occupied {
1074 generation,
1075 ref mut value,
1076 },
1077 )) => {
1078 self.len -= 1;
1079 let idx = Index {
1080 index: index as u32,
1081 generation,
1082 };
1083 return Some((idx, value));
1084 }
1085 None => {
1086 debug_assert_eq!(self.len, 0);
1087 return None;
1088 }
1089 }
1090 }
1091 }
1092}
1093
1094#[cfg(feature = "alloc")]
1095impl<T> ExactSizeIterator for IterMut<'_, T> {
1096 fn len(&self) -> usize {
1097 self.len
1098 }
1099}
1100
1101#[cfg(feature = "alloc")]
1102impl<T> FusedIterator for IterMut<'_, T> {}
1103
1104/// An iterator that removes elements from the arena.
1105///
1106/// Yields pairs of `(Index, T)` items.
1107///
1108/// Order of iteration is not defined.
1109///
1110/// Note: All elements are removed even if the iterator is only partially consumed or not consumed at all.
1111///
1112/// # Examples
1113///
1114/// ```
1115/// # use rapier3d::data::arena::Arena;
1116/// let mut arena = Arena::new();
1117/// let idx_1 = arena.insert("hello");
1118/// let idx_2 = arena.insert("world");
1119///
1120/// assert!(arena.get(idx_1).is_some());
1121/// assert!(arena.get(idx_2).is_some());
1122/// for (idx, value) in arena.drain() {
1123/// assert!((idx == idx_1 && value == "hello") || (idx == idx_2 && value == "world"));
1124/// }
1125/// assert!(arena.get(idx_1).is_none());
1126/// assert!(arena.get(idx_2).is_none());
1127/// ```
1128#[cfg(feature = "alloc")]
1129#[derive(Debug)]
1130pub struct Drain<'a, T: 'a> {
1131 inner: iter::Enumerate<vec::Drain<'a, Entry<T>>>,
1132}
1133
1134#[cfg(feature = "alloc")]
1135impl<T> Iterator for Drain<'_, T> {
1136 type Item = (Index, T);
1137
1138 fn next(&mut self) -> Option<Self::Item> {
1139 loop {
1140 match self.inner.next() {
1141 Some((_, Entry::Free { .. })) => continue,
1142 Some((index, Entry::Occupied { generation, value })) => {
1143 let idx = Index {
1144 index: index as u32,
1145 generation,
1146 };
1147 return Some((idx, value));
1148 }
1149 None => return None,
1150 }
1151 }
1152 }
1153}
1154
1155#[cfg(feature = "alloc")]
1156impl<T> Extend<T> for Arena<T> {
1157 fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
1158 for t in iter {
1159 self.insert(t);
1160 }
1161 }
1162}
1163
1164#[cfg(feature = "alloc")]
1165impl<T> FromIterator<T> for Arena<T> {
1166 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
1167 let iter = iter.into_iter();
1168 let (lower, upper) = iter.size_hint();
1169 let cap = upper.unwrap_or(lower);
1170 let cap = cmp::max(cap, 1);
1171 let mut arena = Arena::with_capacity(cap);
1172 arena.extend(iter);
1173 arena
1174 }
1175}
1176
1177#[cfg(feature = "alloc")]
1178impl<T> ops::Index<Index> for Arena<T> {
1179 type Output = T;
1180
1181 fn index(&self, index: Index) -> &Self::Output {
1182 self.get(index).expect("No element at index")
1183 }
1184}
1185
1186#[cfg(feature = "alloc")]
1187impl<T> ops::IndexMut<Index> for Arena<T> {
1188 fn index_mut(&mut self, index: Index) -> &mut Self::Output {
1189 self.get_mut(index).expect("No element at index")
1190 }
1191}