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