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