typed_generational_arena/lib.rs
1/*!
2[](https://docs.rs/typed-generational-arena/)
3[](https://crates.io/crates/typed-generational-arena)
4[](https://crates.io/crates/typed-generational-arena)
5
6A safe arena allocator that allows deletion without suffering from [the ABA
7problem](https://en.wikipedia.org/wiki/ABA_problem) by using generational type-safe
8indices. Forked from [generational-arena](https://github.com/fitzgen/generational-arena/).
9
10Inspired by [Catherine West's closing keynote at RustConf
112018](http://rustconf.com/program.html#closingkeynote), where these ideas
12were presented in the context of an Entity-Component-System for games
13programming.
14
15## What? Why?
16
17Imagine you are working with a graph and you want to add and delete individual
18nodes at a time, or you are writing a game and its world consists of many
19inter-referencing objects with dynamic lifetimes that depend on user
20input. These are situations where matching Rust's ownership and lifetime rules
21can get tricky.
22
23It doesn't make sense to use shared ownership with interior mutability (ie
24`Rc<RefCell<T>>` or `Arc<Mutex<T>>`) nor borrowed references (ie `&'a T` or `&'a
25mut T`) for structures. The cycles rule out reference counted types, and the
26required shared mutability rules out borrows. Furthermore, lifetimes are dynamic
27and don't follow the borrowed-data-outlives-the-borrower discipline.
28
29In these situations, it is tempting to store objects in a `Vec<T>` and have them
30reference each other via their indices. No more borrow checker or ownership
31problems! Often, this solution is good enough.
32
33However, now we can't delete individual items from that `Vec<T>` when we no
34longer need them, because we end up either
35
36* messing up the indices of every element that follows the deleted one, or
37
38* suffering from the [ABA
39 problem](https://en.wikipedia.org/wiki/ABA_problem). To elaborate further, if
40 we tried to replace the `Vec<T>` with a `Vec<Option<T>>`, and delete an
41 element by setting it to `None`, then we create the possibility for this buggy
42 sequence:
43
44 * `obj1` references `obj2` at index `i`
45
46 * someone else deletes `obj2` from index `i`, setting that element to `None`
47
48 * a third thing allocates `obj3`, which ends up at index `i`, because the
49 element at that index is `None` and therefore available for allocation
50
51 * `obj1` attempts to get `obj2` at index `i`, but incorrectly is given
52 `obj3`, when instead the get should fail.
53
54By introducing a monotonically increasing generation counter to the collection,
55associating each element in the collection with the generation when it was
56inserted, and getting elements from the collection with the *pair* of index and
57the generation at the time when the element was inserted, then we can solve the
58aforementioned ABA problem. When indexing into the collection, if the index
59pair's generation does not match the generation of the element at that index,
60then the operation fails.
61
62## Features
63
64* Zero `unsafe`
65* Well tested, including quickchecks
66* `no_std` compatibility
67* All the trait implementations you expect: `IntoIterator`, `FromIterator`,
68 `Extend`, etc...
69
70## Usage
71
72First, add `typed-generational-arena` to your `Cargo.toml`:
73
74```toml
75[dependencies]
76typed-generational-arena = "0.2"
77```
78
79Then, import the crate and use one of the variations of the
80[`typed_generational_arena::Arena`](./struct.Arena.html) type!
81In these examples, we use `typed_generational_arena::StandardArena`,
82but you can use any combination of index and generation ID
83best fits your purposes.
84
85```rust
86extern crate typed_generational_arena;
87use typed_generational_arena::StandardArena;
88
89let mut arena = StandardArena::new();
90
91// Insert some elements into the arena.
92let rza = arena.insert("Robert Fitzgerald Diggs");
93let gza = arena.insert("Gary Grice");
94let bill = arena.insert("Bill Gates");
95
96// Inserted elements can be accessed infallibly via indexing (and missing
97// entries will panic).
98assert_eq!(arena[rza], "Robert Fitzgerald Diggs");
99
100// Alternatively, the `get` and `get_mut` methods provide fallible lookup.
101if let Some(genius) = arena.get(gza) {
102 println!("The gza gza genius: {}", genius);
103}
104if let Some(val) = arena.get_mut(bill) {
105 *val = "Bill Gates doesn't belong in this set...";
106}
107
108// We can remove elements.
109arena.remove(bill);
110
111// Insert a new one.
112let murray = arena.insert("Bill Murray");
113
114// The arena does not contain `bill` anymore, but it does contain `murray`, even
115// though they are almost certainly at the same index within the arena in
116// practice. Ambiguities are resolved with an associated generation tag.
117assert!(!arena.contains(bill));
118assert!(arena.contains(murray));
119
120// Iterate over everything inside the arena.
121for (idx, value) in &arena {
122 println!("{:?} is at {:?}", value, idx);
123}
124```
125
126## `no_std`
127
128To enable `no_std` compatibility, disable the on-by-default "std" feature. This
129currently requires nightly Rust and `feature(alloc)` to get access to `Vec`.
130
131```toml
132[dependencies]
133typed-generational-arena = { version = "0.2", default-features = false }
134```
135
136### Serialization and Deserialization with [`serde`](https://crates.io/crates/serde)
137
138To enable serialization/deserialization support, enable the "serde" feature.
139
140```toml
141[dependencies]
142typed-generational-arena = { version = "0.2", features = ["serde"] }
143```
144 */
145
146#![forbid(unsafe_code, missing_docs, missing_debug_implementations)]
147#![no_std]
148#![cfg_attr(not(feature = "std"), feature(alloc))]
149
150extern crate nonzero_ext;
151extern crate num_traits;
152#[macro_use]
153extern crate cfg_if;
154#[cfg(feature = "serde")]
155extern crate serde;
156
157cfg_if! {
158 if #[cfg(feature = "std")] {
159 extern crate std;
160 use std::vec::{self, Vec};
161 } else {
162 extern crate alloc;
163 use alloc::vec::{self, Vec};
164 }
165}
166
167use core::cmp::{self, Ordering};
168use core::default::Default;
169use core::fmt::Debug;
170use core::hash::Hash;
171use core::iter::{self, Extend, FromIterator, FusedIterator};
172use core::mem;
173use core::ops::{self, Add, AddAssign};
174use core::slice;
175
176use nonzero_ext::{NonZero, NonZeroAble};
177use num_traits::{FromPrimitive, One, ToPrimitive, WrappingAdd, Zero};
178
179#[cfg(feature = "serde")]
180mod serde_impl;
181#[cfg(feature = "serde")]
182use serde::{Deserialize, Serialize};
183
184mod presets;
185pub use presets::*;
186
187/// A type which can be used as the index of a generation which may not be able to be incremented
188pub trait FixedGenerationalIndex: Copy + Eq {
189 /// Get an object representing the first possible generation
190 fn first_generation() -> Self;
191 /// Compare this generation with another.
192 fn generation_lt(&self, other: &Self) -> bool;
193}
194
195/// A type which can be used as the index of a generation, which can be incremented
196pub trait GenerationalIndex: FixedGenerationalIndex {
197 /// Increment the generation of this object. May wrap or panic on overflow depending on type.
198 fn increment_generation(&mut self);
199}
200
201/// A generation counter which is always nonzero. Useful for size optimizations on Option<Index>
202#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Default)]
203#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
204pub struct NonzeroGeneration<T: NonZeroAble> {
205 gen: T::NonZero,
206}
207
208impl<T> NonzeroGeneration<T>
209where
210 T: NonZeroAble + From<<<T as NonZeroAble>::NonZero as NonZero>::Primitive>,
211{
212 /// Get this generation as an index
213 #[inline(always)]
214 pub fn to_idx(self) -> T {
215 T::from(self.gen.get())
216 }
217
218 /// Attempt to construct a generation from an index
219 #[inline(always)]
220 pub fn from_idx(ix: T) -> Option<Self> {
221 ix.as_nonzero().map(|gen| NonzeroGeneration { gen })
222 }
223}
224
225impl<T> FixedGenerationalIndex for NonzeroGeneration<T>
226where
227 T: NonZeroAble
228 + One
229 + Add<Output = T>
230 + Copy
231 + Eq
232 + From<<<T as NonZeroAble>::NonZero as NonZero>::Primitive>,
233 T::NonZero: PartialOrd + Eq + Copy,
234{
235 #[inline(always)]
236 fn first_generation() -> Self {
237 NonzeroGeneration {
238 gen: T::one().as_nonzero().unwrap(),
239 }
240 }
241 #[inline(always)]
242 fn generation_lt(&self, other: &Self) -> bool {
243 self.gen < other.gen
244 }
245}
246
247impl<T> GenerationalIndex for NonzeroGeneration<T>
248where
249 T: NonZeroAble
250 + One
251 + Add<Output = T>
252 + Copy
253 + Eq
254 + From<<<T as NonZeroAble>::NonZero as NonZero>::Primitive>,
255 T::NonZero: PartialOrd + Eq + Copy,
256{
257 #[inline(always)]
258 fn increment_generation(&mut self) {
259 self.gen = (T::from(self.gen.get()) + T::one()).as_nonzero().unwrap()
260 }
261}
262
263/// A wrapping generation counter which is always nonzero.
264/// Useful for size optimizations on Option<Index>
265#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
266#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
267pub struct NonzeroWrapGeneration<T: NonZeroAble> {
268 gen: T::NonZero,
269}
270
271impl<T> FixedGenerationalIndex for NonzeroWrapGeneration<T>
272where
273 T: NonZeroAble
274 + One
275 + Zero
276 + Copy
277 + Eq
278 + WrappingAdd
279 + From<<<T as NonZeroAble>::NonZero as NonZero>::Primitive>,
280 T::NonZero: PartialOrd + Eq + Copy,
281{
282 #[inline(always)]
283 fn first_generation() -> Self {
284 NonzeroWrapGeneration {
285 gen: T::one().as_nonzero().unwrap(),
286 }
287 }
288 #[inline(always)]
289 fn generation_lt(&self, other: &Self) -> bool {
290 self.gen < other.gen
291 }
292}
293
294impl<T> GenerationalIndex for NonzeroWrapGeneration<T>
295where
296 T: NonZeroAble
297 + One
298 + Zero
299 + Copy
300 + Eq
301 + WrappingAdd
302 + From<<<T as NonZeroAble>::NonZero as NonZero>::Primitive>,
303 T::NonZero: PartialOrd + Eq + Copy,
304{
305 #[inline(always)]
306 fn increment_generation(&mut self) {
307 let new = T::from(self.gen.get()).wrapping_add(&T::one());
308 self.gen = if T::zero() == new {
309 Self::first_generation().gen
310 } else {
311 new.as_nonzero().unwrap()
312 }
313 }
314}
315
316impl<T: Eq + One + AddAssign + Default + PartialOrd + Copy> FixedGenerationalIndex for T {
317 #[inline(always)]
318 fn first_generation() -> Self {
319 Default::default()
320 }
321 #[inline(always)]
322 fn generation_lt(&self, other: &Self) -> bool {
323 self.lt(other)
324 }
325}
326
327impl<T: Eq + One + AddAssign + Default + PartialOrd + Copy> GenerationalIndex for T {
328 #[inline(always)]
329 fn increment_generation(&mut self) {
330 *self += Self::one()
331 }
332}
333
334/// If this is used as a generational index, then the arena ignores generation
335#[derive(Debug, Copy, Clone, PartialEq, Eq, Ord, PartialOrd, Hash)]
336#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
337pub struct IgnoreGeneration;
338
339impl FixedGenerationalIndex for IgnoreGeneration {
340 #[inline(always)]
341 fn first_generation() -> Self {
342 IgnoreGeneration
343 }
344 #[inline(always)]
345 fn generation_lt(&self, _other: &Self) -> bool {
346 false
347 }
348}
349
350impl GenerationalIndex for IgnoreGeneration {
351 #[inline(always)]
352 fn increment_generation(&mut self) {}
353}
354
355/// A marker trait which says that a generation type is ignored
356pub trait IgnoredGeneration: FixedGenerationalIndex {}
357impl IgnoredGeneration for IgnoreGeneration {}
358
359/// If this is used as a generational index, then the arena is no longer generational
360/// and does not allow element removal
361#[derive(Debug, Copy, Clone, PartialEq, Eq, Ord, PartialOrd, Hash)]
362#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
363pub struct DisableRemoval;
364
365impl FixedGenerationalIndex for DisableRemoval {
366 #[inline(always)]
367 fn first_generation() -> Self {
368 DisableRemoval
369 }
370 #[inline(always)]
371 fn generation_lt(&self, _other: &Self) -> bool {
372 false
373 }
374}
375
376impl IgnoredGeneration for DisableRemoval {}
377
378/// A type which can be used as an index to an arena
379pub trait ArenaIndex: Copy {
380 /// Create an arena index from a usize
381 fn from_idx(idx: usize) -> Self;
382 /// Transform an arena index into a usize
383 fn to_idx(self) -> usize;
384}
385impl<T: ToPrimitive + FromPrimitive + Copy> ArenaIndex for T {
386 #[inline(always)]
387 fn from_idx(idx: usize) -> Self {
388 Self::from_usize(idx).unwrap()
389 }
390 #[inline(always)]
391 fn to_idx(self) -> usize {
392 self.to_usize().unwrap()
393 }
394}
395
396/// An arena index which is always nonzero. Useful for Option<T> size optimizations
397#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
398#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
399pub struct NonZeroIndex<T: NonZeroAble> {
400 idx: T::NonZero,
401}
402
403impl<T> ArenaIndex for NonZeroIndex<T>
404where
405 T: NonZeroAble + FromPrimitive,
406 NonZeroIndex<T>: Copy,
407 <<T as NonZeroAble>::NonZero as NonZero>::Primitive: ToPrimitive,
408{
409 #[inline(always)]
410 fn from_idx(idx: usize) -> Self {
411 NonZeroIndex {
412 idx: T::from_usize(idx + 1).unwrap().as_nonzero().unwrap(),
413 }
414 }
415 #[inline(always)]
416 fn to_idx(self) -> usize {
417 self.idx.get().to_usize().unwrap() - 1
418 }
419}
420
421/// The `Arena` allows inserting and removing elements that are referred to by
422/// `Index`.
423///
424/// [See the module-level documentation for example usage and motivation.](./index.html)
425#[derive(Clone, Debug)]
426pub struct Arena<T, I = usize, G = usize> {
427 // It is a breaking change to modify these three members, as they are needed for serialization
428 items: Vec<Entry<T, I, G>>,
429 generation: G,
430 len: usize,
431 free_list_head: Option<I>,
432}
433
434impl<T, I: ArenaIndex, G: FixedGenerationalIndex> Default for Arena<T, I, G> {
435 fn default() -> Self {
436 Arena::new()
437 }
438}
439
440#[derive(Clone, Debug)]
441enum Entry<T, I = usize, G = u64> {
442 Free { next_free: Option<I> },
443 Occupied { generation: G, value: T },
444}
445
446/// An index (and generation) into an `Arena`.
447///
448/// To get an `Index`, insert an element into an `Arena`, and the `Index` for
449/// that element will be returned.
450///
451/// # Examples
452///
453/// ```
454/// use typed_generational_arena::StandardArena;
455///
456/// let mut arena = StandardArena::new();
457/// let idx = arena.insert(123);
458/// assert_eq!(arena[idx], 123);
459/// ```
460#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
461pub struct Index<T, I = usize, G = u64> {
462 /// The array index of the given value
463 index: I,
464 /// The generation of the given value
465 generation: G,
466 #[cfg_attr(feature = "serde", serde(skip))]
467 _phantom: core::marker::PhantomData<fn() -> T>,
468}
469
470impl<T, I: ArenaIndex + Copy, G: FixedGenerationalIndex + Copy> Index<T, I, G> {
471 /// Get this index as a `usize`
472 pub fn to_idx(&self) -> usize {
473 self.index.to_idx()
474 }
475 /// Get this index's array index into the arena
476 pub fn arr_idx(&self) -> I {
477 self.index
478 }
479 /// Get this index's generation
480 pub fn gen(&self) -> G {
481 self.generation
482 }
483}
484
485impl<T, I: ArenaIndex + Copy, G: FixedGenerationalIndex> Index<T, I, G> {
486 /// Convert a `usize` to an index at the first generation
487 #[inline]
488 pub fn from_idx_first_gen(n: usize) -> Self {
489 Index {
490 index: I::from_idx(n),
491 generation: G::first_generation(),
492 _phantom: core::marker::PhantomData,
493 }
494 }
495}
496
497impl<T, I: Debug, G: Debug> Debug for Index<T, I, G> {
498 fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
499 f.debug_struct("Index")
500 .field("index", &self.index)
501 .field("generation", &self.generation)
502 .finish()
503 }
504}
505
506impl<T, I: Copy, G: Copy> Copy for Index<T, I, G> {}
507
508impl<T, I: Clone, G: Clone> Clone for Index<T, I, G> {
509 fn clone(&self) -> Self {
510 Index {
511 index: self.index.clone(),
512 generation: self.generation.clone(),
513 _phantom: core::marker::PhantomData,
514 }
515 }
516}
517
518impl<T, I: Eq, G: Eq> Eq for Index<T, I, G> {}
519
520impl<T, I: PartialEq, G: PartialEq> PartialEq for Index<T, I, G> {
521 fn eq(&self, other: &Self) -> bool {
522 self.index == other.index && self.generation == other.generation
523 }
524}
525
526impl<T, I: Hash, G: Hash> Hash for Index<T, I, G> {
527 fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
528 self.index.hash(state);
529 self.generation.hash(state);
530 }
531}
532
533impl<T, I: ArenaIndex + Copy, G: IgnoredGeneration> Index<T, I, G> {
534 /// Convert a `usize` to an index (with generations ignored)
535 #[inline(always)]
536 pub fn from_idx(n: usize) -> Self {
537 Self::from_idx_first_gen(n)
538 }
539}
540
541impl<T, I: ArenaIndex, G: FixedGenerationalIndex> Index<T, I, G> {
542 /// Create a new index from a given array index and generation
543 #[inline]
544 pub fn new(index: I, generation: G) -> Index<T, I, G> {
545 Index {
546 index: index,
547 generation: generation,
548 _phantom: std::marker::PhantomData,
549 }
550 }
551}
552
553impl<T, I: PartialOrd, G: FixedGenerationalIndex> PartialOrd for Index<T, I, G> {
554 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
555 match self.index.partial_cmp(&other.index) {
556 Some(ordering) => {
557 if ordering == Ordering::Equal {
558 if self.generation.generation_lt(&other.generation) {
559 Some(Ordering::Less)
560 } else if self.generation == other.generation {
561 Some(Ordering::Equal)
562 } else {
563 Some(Ordering::Greater)
564 }
565 } else {
566 Some(ordering)
567 }
568 }
569 None => {
570 if self.generation.generation_lt(&other.generation) {
571 Some(Ordering::Less)
572 } else if self.generation == other.generation {
573 None
574 } else {
575 Some(Ordering::Greater)
576 }
577 }
578 }
579 }
580}
581
582impl<T, I: Ord, G: FixedGenerationalIndex> Ord for Index<T, I, G> {
583 fn cmp(&self, other: &Self) -> Ordering {
584 self.partial_cmp(other).unwrap()
585 }
586}
587
588const DEFAULT_CAPACITY: usize = 4;
589
590impl<T, I: ArenaIndex, G: FixedGenerationalIndex> Arena<T, I, G> {
591 /// Constructs a new, empty `Arena`.
592 ///
593 /// # Examples
594 ///
595 /// ```
596 /// use typed_generational_arena::StandardArena;
597 ///
598 /// let mut arena = StandardArena::<usize>::new();
599 /// # let _ = arena;
600 /// ```
601 pub fn new() -> Arena<T, I, G> {
602 Arena::with_capacity(DEFAULT_CAPACITY)
603 }
604
605 /// Constructs a new, empty `Arena<T>` with the specified capacity.
606 ///
607 /// The `Arena<T>` will be able to hold `n` elements without further allocation.
608 ///
609 /// # Examples
610 ///
611 /// ```
612 /// use typed_generational_arena::StandardArena;
613 ///
614 /// let mut arena = StandardArena::with_capacity(10);
615 ///
616 /// // These insertions will not require further allocation.
617 /// for i in 0..10 {
618 /// assert!(arena.try_insert(i).is_ok());
619 /// }
620 ///
621 /// // But now we are at capacity, and there is no more room.
622 /// assert!(arena.try_insert(99).is_err());
623 /// ```
624 pub fn with_capacity(n: usize) -> Arena<T, I, G> {
625 let n = cmp::max(n, 1);
626 let mut arena = Arena {
627 items: Vec::new(),
628 generation: G::first_generation(),
629 free_list_head: None,
630 len: 0,
631 };
632 arena.reserve(n);
633 arena
634 }
635
636 /// Clear all the items inside the arena, but keep its allocation.
637 ///
638 /// # Examples
639 ///
640 /// ```
641 /// use typed_generational_arena::StandardArena;
642 ///
643 /// let mut arena = StandardArena::with_capacity(1);
644 /// arena.insert(42);
645 /// arena.insert(43);
646 ///
647 /// arena.clear();
648 ///
649 /// assert_eq!(arena.capacity(), 2);
650 /// ```
651 pub fn clear(&mut self) {
652 self.items.clear();
653
654 let end = self.items.capacity();
655 self.items.extend((0..end).map(|i| {
656 if i == end - 1 {
657 Entry::Free { next_free: None }
658 } else {
659 Entry::Free {
660 next_free: Some(I::from_idx(i + 1)),
661 }
662 }
663 }));
664 self.free_list_head = Some(I::from_idx(0));
665 self.len = 0;
666 }
667
668 /// Attempts to insert `value` into the arena using existing capacity.
669 ///
670 /// This method will never allocate new capacity in the arena.
671 ///
672 /// If insertion succeeds, then the `value`'s index is returned. If
673 /// insertion fails, then `Err(value)` is returned to give ownership of
674 /// `value` back to the caller.
675 ///
676 /// # Examples
677 ///
678 /// ```
679 /// use typed_generational_arena::StandardArena;
680 ///
681 /// let mut arena = StandardArena::new();
682 ///
683 /// match arena.try_insert(42) {
684 /// Ok(idx) => {
685 /// // Insertion succeeded.
686 /// assert_eq!(arena[idx], 42);
687 /// }
688 /// Err(x) => {
689 /// // Insertion failed.
690 /// assert_eq!(x, 42);
691 /// }
692 /// };
693 /// ```
694 #[inline]
695 pub fn try_insert(&mut self, value: T) -> Result<Index<T, I, G>, T> {
696 match self.free_list_head {
697 None => Err(value),
698 Some(i) => {
699 let idx = i.to_idx();
700 match &self.items[idx] {
701 Entry::Occupied { .. } => panic!("corrupt free list"),
702 Entry::Free { next_free } => {
703 self.free_list_head = *next_free;
704 self.len += 1;
705 self.items[idx] = Entry::Occupied {
706 generation: self.generation,
707 value,
708 };
709 Ok(Index::new(i, self.generation))
710 }
711 }
712 }
713 }
714 }
715
716 /// Insert `value` into the arena, allocating more capacity if necessary.
717 ///
718 /// The `value`'s associated index in the arena is returned.
719 ///
720 /// # Examples
721 ///
722 /// ```
723 /// use typed_generational_arena::StandardArena;
724 ///
725 /// let mut arena = StandardArena::new();
726 ///
727 /// let idx = arena.insert(42);
728 /// assert_eq!(arena[idx], 42);
729 /// ```
730 #[inline]
731 pub fn insert(&mut self, value: T) -> Index<T, I, G> {
732 match self.try_insert(value) {
733 Ok(i) => i,
734 Err(value) => self.insert_slow_path(value),
735 }
736 }
737
738 #[inline(never)]
739 fn insert_slow_path(&mut self, value: T) -> Index<T, I, G> {
740 let len = self.items.len();
741 self.reserve(len);
742 self.try_insert(value)
743 .map_err(|_| ())
744 .expect("inserting will always succeed after reserving additional space")
745 }
746
747 /// Is the element at index `i` in the arena?
748 ///
749 /// Returns `true` if the element at `i` is in the arena, `false` otherwise.
750 ///
751 /// # Examples
752 ///
753 /// ```
754 /// use typed_generational_arena::StandardArena;
755 ///
756 /// let mut arena = StandardArena::new();
757 /// let idx = arena.insert(42);
758 ///
759 /// assert!(arena.contains(idx));
760 /// arena.remove(idx);
761 /// assert!(!arena.contains(idx));
762 /// ```
763 pub fn contains(&self, i: Index<T, I, G>) -> bool {
764 self.get(i).is_some()
765 }
766
767 /// Get a shared reference to the element at index `i` if it is in the
768 /// arena.
769 ///
770 /// If the element at index `i` is not in the arena, then `None` is returned.
771 ///
772 /// # Examples
773 ///
774 /// ```
775 /// use typed_generational_arena::StandardArena;
776 ///
777 /// let mut arena = StandardArena::new();
778 /// let idx = arena.insert(42);
779 ///
780 /// assert_eq!(arena.get(idx), Some(&42));
781 /// arena.remove(idx);
782 /// assert!(arena.get(idx).is_none());
783 /// ```
784 pub fn get(&self, i: Index<T, I, G>) -> Option<&T> {
785 match self.items.get(i.index.to_idx()) {
786 Some(Entry::Occupied {
787 generation,
788 ref value,
789 }) if *generation == i.generation => Some(value),
790 _ => None,
791 }
792 }
793
794 /// Get an exclusive reference to the element at index `i` if it is in the
795 /// arena.
796 ///
797 /// If the element at index `i` is not in the arena, then `None` is returned.
798 ///
799 /// # Examples
800 ///
801 /// ```
802 /// use typed_generational_arena::StandardArena;
803 ///
804 /// let mut arena = StandardArena::new();
805 /// let idx = arena.insert(42);
806 ///
807 /// *arena.get_mut(idx).unwrap() += 1;
808 /// assert_eq!(arena.remove(idx), Some(43));
809 /// assert!(arena.get_mut(idx).is_none());
810 /// ```
811 pub fn get_mut(&mut self, i: Index<T, I, G>) -> Option<&mut T> {
812 match self.items.get_mut(i.index.to_idx()) {
813 Some(Entry::Occupied {
814 generation,
815 ref mut value,
816 }) if *generation == i.generation => Some(value),
817 _ => None,
818 }
819 }
820
821 /// Get a pair of exclusive references to the elements at index `i1` and `i2` if it is in the
822 /// arena.
823 ///
824 /// If the element at index `i1` or `i2` is not in the arena, then `None` is returned for this
825 /// element.
826 ///
827 /// # Panics
828 ///
829 /// Panics if `i1` and `i2` are pointing to the same item of the arena.
830 ///
831 /// # Examples
832 ///
833 /// ```
834 /// use typed_generational_arena::StandardArena;
835 ///
836 /// let mut arena = StandardArena::new();
837 /// let idx1 = arena.insert(0);
838 /// let idx2 = arena.insert(1);
839 ///
840 /// {
841 /// let (item1, item2) = arena.get2_mut(idx1, idx2);
842 ///
843 /// *item1.unwrap() = 3;
844 /// *item2.unwrap() = 4;
845 /// }
846 ///
847 /// assert_eq!(arena[idx1], 3);
848 /// assert_eq!(arena[idx2], 4);
849 /// ```
850 pub fn get2_mut(
851 &mut self,
852 i1: Index<T, I, G>,
853 i2: Index<T, I, G>,
854 ) -> (Option<&mut T>, Option<&mut T>) {
855 let len = self.items.len();
856 let idx = (i1.index.to_idx(), i2.index.to_idx());
857 let gen = (i1.generation, i2.generation);
858
859 if idx.0 == idx.1 {
860 assert!(gen.0 != gen.1);
861
862 if gen.1.generation_lt(&gen.0) {
863 return (self.get_mut(i1), None);
864 }
865 return (None, self.get_mut(i2));
866 }
867
868 if idx.0 >= len {
869 return (None, self.get_mut(i2));
870 } else if idx.1 >= len {
871 return (self.get_mut(i1), None);
872 }
873
874 let (raw_item1, raw_item2) = {
875 let (xs, ys) = self.items.split_at_mut(cmp::max(idx.0, idx.1));
876 if idx.0 < idx.1 {
877 (&mut xs[idx.0], &mut ys[0])
878 } else {
879 (&mut ys[0], &mut xs[idx.1])
880 }
881 };
882
883 let item1 = match raw_item1 {
884 Entry::Occupied {
885 generation,
886 ref mut value,
887 } if *generation == gen.0 => Some(value),
888 _ => None,
889 };
890
891 let item2 = match raw_item2 {
892 Entry::Occupied {
893 generation,
894 ref mut value,
895 } if *generation == gen.1 => Some(value),
896 _ => None,
897 };
898
899 (item1, item2)
900 }
901
902 /// Get the length of this arena.
903 ///
904 /// The length is the number of elements the arena holds.
905 ///
906 /// # Examples
907 ///
908 /// ```
909 /// use typed_generational_arena::StandardArena;
910 ///
911 /// let mut arena = StandardArena::new();
912 /// assert_eq!(arena.len(), 0);
913 ///
914 /// let idx = arena.insert(42);
915 /// assert_eq!(arena.len(), 1);
916 ///
917 /// let _ = arena.insert(0);
918 /// assert_eq!(arena.len(), 2);
919 ///
920 /// assert_eq!(arena.remove(idx), Some(42));
921 /// assert_eq!(arena.len(), 1);
922 /// ```
923 pub fn len(&self) -> usize {
924 self.len
925 }
926
927 /// Returns true if the arena contains no elements
928 ///
929 /// # Examples
930 ///
931 /// ```
932 /// use typed_generational_arena::StandardArena;
933 ///
934 /// let mut arena = StandardArena::new();
935 /// assert!(arena.is_empty());
936 ///
937 /// let idx = arena.insert(42);
938 /// assert!(!arena.is_empty());
939 ///
940 /// assert_eq!(arena.remove(idx), Some(42));
941 /// assert!(arena.is_empty());
942 /// ```
943 pub fn is_empty(&self) -> bool {
944 self.len == 0
945 }
946
947 /// Get the capacity of this arena.
948 ///
949 /// The capacity is the maximum number of elements the arena can hold
950 /// without further allocation, including however many it currently
951 /// contains.
952 ///
953 /// # Examples
954 ///
955 /// ```
956 /// use typed_generational_arena::StandardArena;
957 ///
958 /// let mut arena = StandardArena::with_capacity(10);
959 /// assert_eq!(arena.capacity(), 10);
960 ///
961 /// // `try_insert` does not allocate new capacity.
962 /// for i in 0..10 {
963 /// assert!(arena.try_insert(1).is_ok());
964 /// assert_eq!(arena.capacity(), 10);
965 /// }
966 ///
967 /// // But `insert` will if the arena is already at capacity.
968 /// arena.insert(0);
969 /// assert!(arena.capacity() > 10);
970 /// ```
971 pub fn capacity(&self) -> usize {
972 self.items.len()
973 }
974
975 /// Allocate space for `additional_capacity` more elements in the arena.
976 ///
977 /// # Panics
978 ///
979 /// Panics if this causes the capacity to overflow.
980 ///
981 /// # Examples
982 ///
983 /// ```
984 /// use typed_generational_arena::StandardArena;
985 ///
986 /// let mut arena = StandardArena::with_capacity(10);
987 /// arena.reserve(5);
988 /// assert_eq!(arena.capacity(), 15);
989 /// # let _: StandardArena<usize> = arena;
990 /// ```
991 pub fn reserve(&mut self, additional_capacity: usize) {
992 let start = self.items.len();
993 let end = self.items.len() + additional_capacity;
994 let old_head = self.free_list_head;
995 self.items.reserve_exact(additional_capacity);
996 self.items.extend((start..end).map(|i| {
997 if i == end - 1 {
998 Entry::Free {
999 next_free: old_head,
1000 }
1001 } else {
1002 Entry::Free {
1003 next_free: Some(I::from_idx(i + 1)),
1004 }
1005 }
1006 }));
1007 self.free_list_head = Some(I::from_idx(start));
1008 }
1009
1010 /// Iterate over shared references to the elements in this arena.
1011 ///
1012 /// Yields pairs of `(Index<T>, &T)` items.
1013 ///
1014 /// Order of iteration is not defined.
1015 ///
1016 /// # Examples
1017 ///
1018 /// ```
1019 /// use typed_generational_arena::StandardArena;
1020 ///
1021 /// let mut arena = StandardArena::new();
1022 /// for i in 0..10 {
1023 /// arena.insert(i * i);
1024 /// }
1025 ///
1026 /// for (idx, value) in arena.iter() {
1027 /// println!("{} is at index {:?}", value, idx);
1028 /// }
1029 /// ```
1030 pub fn iter(&self) -> Iter<T, I, G> {
1031 Iter {
1032 len: self.len,
1033 inner: self.items.iter().enumerate(),
1034 }
1035 }
1036
1037 /// Iterate over exclusive references to the elements in this arena.
1038 ///
1039 /// Yields pairs of `(Index<T>, &mut T)` items.
1040 ///
1041 /// Order of iteration is not defined.
1042 ///
1043 /// # Examples
1044 ///
1045 /// ```
1046 /// use typed_generational_arena::StandardArena;
1047 ///
1048 /// let mut arena = StandardArena::new();
1049 /// for i in 0..10 {
1050 /// arena.insert(i * i);
1051 /// }
1052 ///
1053 /// for (_idx, value) in arena.iter_mut() {
1054 /// *value += 5;
1055 /// }
1056 /// ```
1057 pub fn iter_mut(&mut self) -> IterMut<T, I, G> {
1058 IterMut {
1059 len: self.len,
1060 inner: self.items.iter_mut().enumerate(),
1061 }
1062 }
1063
1064 /// Iterate over elements of the arena and remove them.
1065 ///
1066 /// Yields pairs of `(Index<T>, T)` items.
1067 ///
1068 /// Order of iteration is not defined.
1069 ///
1070 /// Note: All elements are removed even if the iterator is only partially consumed or not consumed at all.
1071 ///
1072 /// # Examples
1073 ///
1074 /// ```
1075 /// use typed_generational_arena::StandardArena;
1076 ///
1077 /// let mut arena = StandardArena::new();
1078 /// let idx_1 = arena.insert("hello");
1079 /// let idx_2 = arena.insert("world");
1080 ///
1081 /// assert!(arena.get(idx_1).is_some());
1082 /// assert!(arena.get(idx_2).is_some());
1083 /// for (idx, value) in arena.drain() {
1084 /// assert!((idx == idx_1 && value == "hello") || (idx == idx_2 && value == "world"));
1085 /// }
1086 /// assert!(arena.get(idx_1).is_none());
1087 /// assert!(arena.get(idx_2).is_none());
1088 /// ```
1089 pub fn drain(&mut self) -> Drain<T, I, G> {
1090 Drain {
1091 inner: self.items.drain(..).enumerate(),
1092 }
1093 }
1094
1095 /// If an integer index is valid, returns it as a generational index
1096 ///
1097 /// # Examples
1098 /// ```
1099 /// use typed_generational_arena::StandardArena;
1100 ///
1101 /// let mut arena = StandardArena::new();
1102 /// assert_eq!(arena.get_idx(0), None);
1103 /// let ix = arena.insert(4);
1104 /// assert_eq!(arena.get_idx(0), Some(ix));
1105 /// arena.remove(ix);
1106 /// assert_eq!(arena.get_idx(0), None);
1107 /// ```
1108 pub fn get_idx(&self, i: I) -> Option<Index<T, I, G>> {
1109 match self.items.get(i.to_idx()) {
1110 Some(Entry::Occupied { generation, .. }) => Some(Index::new(i, *generation)),
1111 _ => None,
1112 }
1113 }
1114}
1115
1116impl<T, I: ArenaIndex, G: GenerationalIndex> Arena<T, I, G> {
1117 /// Remove the element at index `i` from the arena.
1118 ///
1119 /// If the element at index `i` is still in the arena, then it is
1120 /// returned. If it is not in the arena, then `None` is returned.
1121 ///
1122 /// # Examples
1123 ///
1124 /// ```
1125 /// use typed_generational_arena::StandardArena;
1126 ///
1127 /// let mut arena = StandardArena::new();
1128 /// let idx = arena.insert(42);
1129 ///
1130 /// assert_eq!(arena.remove(idx), Some(42));
1131 /// assert_eq!(arena.remove(idx), None);
1132 /// ```
1133 pub fn remove(&mut self, i: Index<T, I, G>) -> Option<T> {
1134 if i.index.to_idx() >= self.items.len() {
1135 return None;
1136 }
1137
1138 let entry = mem::replace(
1139 &mut self.items[i.index.to_idx()],
1140 Entry::Free {
1141 next_free: self.free_list_head,
1142 },
1143 );
1144 match entry {
1145 Entry::Occupied { generation, value } => {
1146 if generation == i.generation {
1147 self.generation.increment_generation();
1148 self.free_list_head = Some(i.index);
1149 self.len -= 1;
1150 Some(value)
1151 } else {
1152 self.items[i.index.to_idx()] = Entry::Occupied { generation, value };
1153 None
1154 }
1155 }
1156 e @ Entry::Free { .. } => {
1157 self.items[i.index.to_idx()] = e;
1158 None
1159 }
1160 }
1161 }
1162
1163 /// Retains only the elements specified by the predicate.
1164 ///
1165 /// In other words, remove all indices such that `predicate(index, &value)` returns `false`.
1166 ///
1167 /// # Examples
1168 ///
1169 /// ```
1170 /// use typed_generational_arena::StandardArena;
1171 ///
1172 /// let mut crew = StandardArena::new();
1173 /// crew.extend(&["Jim Hawkins", "John Silver", "Alexander Smollett", "Israel Hands"]);
1174 /// let pirates = ["John Silver", "Israel Hands"]; // too dangerous to keep them around
1175 /// crew.retain(|_index, member| !pirates.contains(member));
1176 /// let mut crew_members = crew.iter().map(|(_, member)| **member);
1177 /// assert_eq!(crew_members.next(), Some("Jim Hawkins"));
1178 /// assert_eq!(crew_members.next(), Some("Alexander Smollett"));
1179 /// assert!(crew_members.next().is_none());
1180 /// ```
1181 pub fn retain(&mut self, mut predicate: impl FnMut(Index<T, I, G>, &T) -> bool) {
1182 for i in 0..self.items.len() {
1183 let remove = match &self.items[i] {
1184 Entry::Occupied { generation, value } => {
1185 let index = Index::new(I::from_idx(i), *generation);
1186 if predicate(index, value) {
1187 None
1188 } else {
1189 Some(index)
1190 }
1191 }
1192 _ => None,
1193 };
1194 if let Some(index) = remove {
1195 self.remove(index);
1196 }
1197 }
1198 }
1199}
1200
1201impl<T, I: ArenaIndex, G: FixedGenerationalIndex> IntoIterator for Arena<T, I, G> {
1202 type Item = T;
1203 type IntoIter = IntoIter<T, I, G>;
1204 fn into_iter(self) -> Self::IntoIter {
1205 IntoIter {
1206 len: self.len,
1207 inner: self.items.into_iter(),
1208 }
1209 }
1210}
1211
1212/// An iterator over the elements in an arena.
1213///
1214/// Yields `T` items.
1215///
1216/// Order of iteration is not defined.
1217///
1218/// # Examples
1219///
1220/// ```
1221/// use typed_generational_arena::StandardArena;
1222///
1223/// let mut arena = StandardArena::new();
1224/// for i in 0..10 {
1225/// arena.insert(i * i);
1226/// }
1227///
1228/// for value in arena {
1229/// assert!(value < 100);
1230/// }
1231/// ```
1232#[derive(Clone, Debug)]
1233pub struct IntoIter<T, I: ArenaIndex, G: FixedGenerationalIndex> {
1234 len: usize,
1235 inner: vec::IntoIter<Entry<T, I, G>>,
1236}
1237
1238impl<T, I: ArenaIndex, G: FixedGenerationalIndex> Iterator for IntoIter<T, I, G> {
1239 type Item = T;
1240
1241 fn next(&mut self) -> Option<Self::Item> {
1242 loop {
1243 match self.inner.next() {
1244 Some(Entry::Free { .. }) => continue,
1245 Some(Entry::Occupied { value, .. }) => {
1246 self.len -= 1;
1247 return Some(value);
1248 }
1249 None => {
1250 debug_assert_eq!(self.len, 0);
1251 return None;
1252 }
1253 }
1254 }
1255 }
1256
1257 fn size_hint(&self) -> (usize, Option<usize>) {
1258 (self.len, Some(self.len))
1259 }
1260}
1261
1262impl<T, I: ArenaIndex, G: FixedGenerationalIndex> DoubleEndedIterator for IntoIter<T, I, G> {
1263 fn next_back(&mut self) -> Option<Self::Item> {
1264 loop {
1265 match self.inner.next_back() {
1266 Some(Entry::Free { .. }) => continue,
1267 Some(Entry::Occupied { value, .. }) => {
1268 self.len -= 1;
1269 return Some(value);
1270 }
1271 None => {
1272 debug_assert_eq!(self.len, 0);
1273 return None;
1274 }
1275 }
1276 }
1277 }
1278}
1279
1280impl<T, I: ArenaIndex, G: FixedGenerationalIndex> ExactSizeIterator for IntoIter<T, I, G> {
1281 fn len(&self) -> usize {
1282 self.len
1283 }
1284}
1285
1286impl<T, I: ArenaIndex, G: FixedGenerationalIndex> FusedIterator for IntoIter<T, I, G> {}
1287
1288impl<'a, T, I: ArenaIndex, G: FixedGenerationalIndex> IntoIterator for &'a Arena<T, I, G> {
1289 type Item = (Index<T, I, G>, &'a T);
1290 type IntoIter = Iter<'a, T, I, G>;
1291 fn into_iter(self) -> Self::IntoIter {
1292 self.iter()
1293 }
1294}
1295
1296/// An iterator over shared references to the elements in an arena.
1297///
1298/// Yields pairs of `(Index<T>, &T)` items.
1299///
1300/// Order of iteration is not defined.
1301///
1302/// # Examples
1303///
1304/// ```
1305/// use typed_generational_arena::StandardArena;
1306///
1307/// let mut arena = StandardArena::new();
1308/// for i in 0..10 {
1309/// arena.insert(i * i);
1310/// }
1311///
1312/// for (idx, value) in &arena {
1313/// println!("{} is at index {:?}", value, idx);
1314/// }
1315/// ```
1316#[derive(Clone, Debug)]
1317pub struct Iter<'a, T: 'a, I: 'a + ArenaIndex, G: 'a + FixedGenerationalIndex> {
1318 len: usize,
1319 inner: iter::Enumerate<slice::Iter<'a, Entry<T, I, G>>>,
1320}
1321
1322impl<'a, T, I: 'a + ArenaIndex, G: 'a + FixedGenerationalIndex> Iterator for Iter<'a, T, I, G> {
1323 type Item = (Index<T, I, G>, &'a T);
1324
1325 fn next(&mut self) -> Option<Self::Item> {
1326 loop {
1327 match self.inner.next() {
1328 Some((_, &Entry::Free { .. })) => continue,
1329 Some((
1330 index,
1331 &Entry::Occupied {
1332 generation,
1333 ref value,
1334 },
1335 )) => {
1336 self.len -= 1;
1337 let idx = Index::new(I::from_idx(index), generation);
1338 return Some((idx, value));
1339 }
1340 None => {
1341 debug_assert_eq!(self.len, 0);
1342 return None;
1343 }
1344 }
1345 }
1346 }
1347
1348 fn size_hint(&self) -> (usize, Option<usize>) {
1349 (self.len, Some(self.len))
1350 }
1351}
1352
1353impl<'a, T, I: 'a + ArenaIndex, G: 'a + FixedGenerationalIndex> DoubleEndedIterator
1354 for Iter<'a, T, I, G>
1355{
1356 fn next_back(&mut self) -> Option<Self::Item> {
1357 loop {
1358 match self.inner.next_back() {
1359 Some((_, &Entry::Free { .. })) => continue,
1360 Some((
1361 index,
1362 &Entry::Occupied {
1363 generation,
1364 ref value,
1365 },
1366 )) => {
1367 self.len -= 1;
1368 let idx = Index::new(I::from_idx(index), generation);
1369 return Some((idx, value));
1370 }
1371 None => {
1372 debug_assert_eq!(self.len, 0);
1373 return None;
1374 }
1375 }
1376 }
1377 }
1378}
1379
1380impl<'a, T, I: ArenaIndex, G: FixedGenerationalIndex> ExactSizeIterator for Iter<'a, T, I, G> {
1381 fn len(&self) -> usize {
1382 self.len
1383 }
1384}
1385
1386impl<'a, T, I: ArenaIndex, G: FixedGenerationalIndex> FusedIterator for Iter<'a, T, I, G> {}
1387
1388impl<'a, T, I: ArenaIndex, G: FixedGenerationalIndex> IntoIterator for &'a mut Arena<T, I, G> {
1389 type Item = (Index<T, I, G>, &'a mut T);
1390 type IntoIter = IterMut<'a, T, I, G>;
1391 fn into_iter(self) -> Self::IntoIter {
1392 self.iter_mut()
1393 }
1394}
1395
1396/// An iterator over exclusive references to elements in this arena.
1397///
1398/// Yields pairs of `(Index<T>, &mut T)` items.
1399///
1400/// Order of iteration is not defined.
1401///
1402/// # Examples
1403///
1404/// ```
1405/// use typed_generational_arena::StandardArena;
1406///
1407/// let mut arena = StandardArena::new();
1408/// for i in 0..10 {
1409/// arena.insert(i * i);
1410/// }
1411///
1412/// for (_idx, value) in &mut arena {
1413/// *value += 5;
1414/// }
1415/// ```
1416#[derive(Debug)]
1417pub struct IterMut<'a, T: 'a, I: 'a + ArenaIndex, G: 'a + FixedGenerationalIndex> {
1418 len: usize,
1419 inner: iter::Enumerate<slice::IterMut<'a, Entry<T, I, G>>>,
1420}
1421
1422impl<'a, T, I: 'a + ArenaIndex, G: 'a + FixedGenerationalIndex> Iterator for IterMut<'a, T, I, G> {
1423 type Item = (Index<T, I, G>, &'a mut T);
1424
1425 fn next(&mut self) -> Option<Self::Item> {
1426 loop {
1427 match self.inner.next() {
1428 Some((_, &mut Entry::Free { .. })) => continue,
1429 Some((
1430 index,
1431 &mut Entry::Occupied {
1432 generation,
1433 ref mut value,
1434 },
1435 )) => {
1436 self.len -= 1;
1437 let idx = Index::new(I::from_idx(index), generation);
1438 return Some((idx, value));
1439 }
1440 None => {
1441 debug_assert_eq!(self.len, 0);
1442 return None;
1443 }
1444 }
1445 }
1446 }
1447
1448 fn size_hint(&self) -> (usize, Option<usize>) {
1449 (self.len, Some(self.len))
1450 }
1451}
1452
1453impl<'a, T, I: 'a + ArenaIndex, G: 'a + FixedGenerationalIndex> DoubleEndedIterator
1454 for IterMut<'a, T, I, G>
1455{
1456 fn next_back(&mut self) -> Option<Self::Item> {
1457 loop {
1458 match self.inner.next_back() {
1459 Some((_, &mut Entry::Free { .. })) => continue,
1460 Some((
1461 index,
1462 &mut Entry::Occupied {
1463 generation,
1464 ref mut value,
1465 },
1466 )) => {
1467 self.len -= 1;
1468 let idx = Index::new(I::from_idx(index), generation);
1469 return Some((idx, value));
1470 }
1471 None => {
1472 debug_assert_eq!(self.len, 0);
1473 return None;
1474 }
1475 }
1476 }
1477 }
1478}
1479
1480impl<'a, T, I: 'a + ArenaIndex, G: 'a + FixedGenerationalIndex> ExactSizeIterator
1481 for IterMut<'a, T, I, G>
1482{
1483 fn len(&self) -> usize {
1484 self.len
1485 }
1486}
1487
1488impl<'a, T, I: 'a + ArenaIndex, G: 'a + FixedGenerationalIndex> FusedIterator
1489 for IterMut<'a, T, I, G>
1490{
1491}
1492
1493/// An iterator that removes elements from the arena.
1494///
1495/// Yields pairs of `(Index<T>, T)` items.
1496///
1497/// Order of iteration is not defined.
1498///
1499/// Note: All elements are removed even if the iterator is only partially consumed or not consumed at all.
1500///
1501/// # Examples
1502///
1503/// ```
1504/// use typed_generational_arena::StandardArena;
1505///
1506/// let mut arena = StandardArena::new();
1507/// let idx_1 = arena.insert("hello");
1508/// let idx_2 = arena.insert("world");
1509///
1510/// assert!(arena.get(idx_1).is_some());
1511/// assert!(arena.get(idx_2).is_some());
1512/// for (idx, value) in arena.drain() {
1513/// assert!((idx == idx_1 && value == "hello") || (idx == idx_2 && value == "world"));
1514/// }
1515/// assert!(arena.get(idx_1).is_none());
1516/// assert!(arena.get(idx_2).is_none());
1517/// ```
1518#[derive(Debug)]
1519pub struct Drain<'a, T: 'a, I: ArenaIndex, G: FixedGenerationalIndex> {
1520 inner: iter::Enumerate<vec::Drain<'a, Entry<T, I, G>>>,
1521}
1522
1523impl<'a, T, I: ArenaIndex, G: FixedGenerationalIndex> Iterator for Drain<'a, T, I, G> {
1524 type Item = (Index<T, I, G>, T);
1525
1526 fn next(&mut self) -> Option<Self::Item> {
1527 loop {
1528 match self.inner.next() {
1529 Some((_, Entry::Free { .. })) => continue,
1530 Some((index, Entry::Occupied { generation, value })) => {
1531 let idx = Index::new(I::from_idx(index), generation);
1532 return Some((idx, value));
1533 }
1534 None => return None,
1535 }
1536 }
1537 }
1538}
1539
1540impl<T, Idx: ArenaIndex, G: FixedGenerationalIndex> Extend<T> for Arena<T, Idx, G> {
1541 fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
1542 for t in iter {
1543 self.insert(t);
1544 }
1545 }
1546}
1547
1548impl<T, Idx: ArenaIndex, G: FixedGenerationalIndex> FromIterator<T> for Arena<T, Idx, G> {
1549 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
1550 let iter = iter.into_iter();
1551 let (lower, upper) = iter.size_hint();
1552 let cap = upper.unwrap_or(lower);
1553 let cap = cmp::max(cap, 1);
1554 let mut arena = Arena::with_capacity(cap);
1555 arena.extend(iter);
1556 arena
1557 }
1558}
1559
1560impl<T, I: ArenaIndex, G: FixedGenerationalIndex> ops::Index<Index<T, I, G>> for Arena<T, I, G> {
1561 type Output = T;
1562
1563 fn index(&self, index: Index<T, I, G>) -> &Self::Output {
1564 self.get(index).expect("No element at index")
1565 }
1566}
1567
1568impl<T, I: ArenaIndex, G: FixedGenerationalIndex> ops::IndexMut<Index<T, I, G>> for Arena<T, I, G> {
1569 fn index_mut(&mut self, index: Index<T, I, G>) -> &mut Self::Output {
1570 self.get_mut(index).expect("No element at index")
1571 }
1572}