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)]
203#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
204pub struct NonzeroGeneration<T: NonZeroAble> {
205 gen: T::NonZero,
206}
207
208impl<T> FixedGenerationalIndex for NonzeroGeneration<T>
209where
210 T: NonZeroAble
211 + One
212 + Add<Output = T>
213 + Copy
214 + Eq
215 + From<<<T as NonZeroAble>::NonZero as NonZero>::Primitive>,
216 T::NonZero: PartialOrd + Eq + Copy,
217{
218 #[inline(always)]
219 fn first_generation() -> Self {
220 NonzeroGeneration {
221 gen: T::one().as_nonzero().unwrap(),
222 }
223 }
224 #[inline(always)]
225 fn generation_lt(&self, other: &Self) -> bool {
226 self.gen < other.gen
227 }
228}
229
230impl<T> GenerationalIndex for NonzeroGeneration<T>
231where
232 T: NonZeroAble
233 + One
234 + Add<Output = T>
235 + Copy
236 + Eq
237 + From<<<T as NonZeroAble>::NonZero as NonZero>::Primitive>,
238 T::NonZero: PartialOrd + Eq + Copy,
239{
240 #[inline(always)]
241 fn increment_generation(&mut self) {
242 self.gen = (T::from(self.gen.get()) + T::one()).as_nonzero().unwrap()
243 }
244}
245
246/// A wrapping generation counter which is always nonzero.
247/// Useful for size optimizations on Option<Index>
248#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd)]
249#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
250pub struct NonzeroWrapGeneration<T: NonZeroAble> {
251 gen: T::NonZero,
252}
253
254impl<T> FixedGenerationalIndex for NonzeroWrapGeneration<T>
255where
256 T: NonZeroAble
257 + One
258 + Zero
259 + Copy
260 + Eq
261 + WrappingAdd
262 + From<<<T as NonZeroAble>::NonZero as NonZero>::Primitive>,
263 T::NonZero: PartialOrd + Eq + Copy,
264{
265 #[inline(always)]
266 fn first_generation() -> Self {
267 NonzeroWrapGeneration {
268 gen: T::one().as_nonzero().unwrap(),
269 }
270 }
271 #[inline(always)]
272 fn generation_lt(&self, other: &Self) -> bool {
273 self.gen < other.gen
274 }
275}
276
277impl<T> GenerationalIndex for NonzeroWrapGeneration<T>
278where
279 T: NonZeroAble
280 + One
281 + Zero
282 + Copy
283 + Eq
284 + WrappingAdd
285 + From<<<T as NonZeroAble>::NonZero as NonZero>::Primitive>,
286 T::NonZero: PartialOrd + Eq + Copy,
287{
288 #[inline(always)]
289 fn increment_generation(&mut self) {
290 let new = T::from(self.gen.get()).wrapping_add(&T::one());
291 self.gen = if T::zero() == new {
292 Self::first_generation().gen
293 } else {
294 new.as_nonzero().unwrap()
295 }
296 }
297}
298
299impl<T: Eq + One + AddAssign + Default + PartialOrd + Copy> FixedGenerationalIndex for T {
300 #[inline(always)]
301 fn first_generation() -> Self {
302 Default::default()
303 }
304 #[inline(always)]
305 fn generation_lt(&self, other: &Self) -> bool {
306 self.lt(other)
307 }
308}
309
310impl<T: Eq + One + AddAssign + Default + PartialOrd + Copy> GenerationalIndex for T {
311 #[inline(always)]
312 fn increment_generation(&mut self) {
313 *self += Self::one()
314 }
315}
316
317/// If this is used as a generational index, then the arena ignores generation
318#[derive(Debug, Copy, Clone, PartialEq, Eq, Ord, PartialOrd, Hash)]
319#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
320pub struct IgnoreGeneration;
321
322impl FixedGenerationalIndex for IgnoreGeneration {
323 #[inline(always)]
324 fn first_generation() -> Self {
325 IgnoreGeneration
326 }
327 #[inline(always)]
328 fn generation_lt(&self, _other: &Self) -> bool {
329 false
330 }
331}
332
333impl GenerationalIndex for IgnoreGeneration {
334 #[inline(always)]
335 fn increment_generation(&mut self) {}
336}
337
338/// A marker trait which says that a generation type is ignored
339pub trait IgnoredGeneration: FixedGenerationalIndex {}
340impl IgnoredGeneration for IgnoreGeneration {}
341
342/// If this is used as a generational index, then the arena is no longer generational
343/// and does not allow element removal
344#[derive(Debug, Copy, Clone, PartialEq, Eq, Ord, PartialOrd, Hash)]
345#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
346pub struct DisableRemoval;
347
348impl FixedGenerationalIndex for DisableRemoval {
349 #[inline(always)]
350 fn first_generation() -> Self {
351 DisableRemoval
352 }
353 #[inline(always)]
354 fn generation_lt(&self, _other: &Self) -> bool {
355 false
356 }
357}
358
359impl IgnoredGeneration for DisableRemoval {}
360
361/// A type which can be used as an index to an arena
362pub trait ArenaIndex: Copy {
363 /// Create an arena index from a usize
364 fn from_idx(idx: usize) -> Self;
365 /// Transform an arena index into a usize
366 fn to_idx(self) -> usize;
367}
368impl<T: ToPrimitive + FromPrimitive + Copy> ArenaIndex for T {
369 #[inline(always)]
370 fn from_idx(idx: usize) -> Self {
371 Self::from_usize(idx).unwrap()
372 }
373 #[inline(always)]
374 fn to_idx(self) -> usize {
375 self.to_usize().unwrap()
376 }
377}
378
379/// An arena index which is always nonzero. Useful for Option<T> size optimizations
380#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
381#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
382pub struct NonZeroIndex<T: NonZeroAble> {
383 idx: T::NonZero,
384}
385
386impl<T> ArenaIndex for NonZeroIndex<T>
387where
388 T: NonZeroAble + FromPrimitive,
389 NonZeroIndex<T>: Copy,
390 <<T as NonZeroAble>::NonZero as NonZero>::Primitive: ToPrimitive,
391{
392 #[inline(always)]
393 fn from_idx(idx: usize) -> Self {
394 NonZeroIndex {
395 idx: T::from_usize(idx + 1).unwrap().as_nonzero().unwrap(),
396 }
397 }
398 #[inline(always)]
399 fn to_idx(self) -> usize {
400 self.idx.get().to_usize().unwrap() - 1
401 }
402}
403
404/// The `Arena` allows inserting and removing elements that are referred to by
405/// `Index`.
406///
407/// [See the module-level documentation for example usage and motivation.](./index.html)
408#[derive(Clone, Debug)]
409pub struct Arena<T, I = usize, G = usize> {
410 // It is a breaking change to modify these three members, as they are needed for serialization
411 items: Vec<Entry<T, I, G>>,
412 generation: G,
413 len: usize,
414 free_list_head: Option<I>,
415}
416
417#[derive(Clone, Debug)]
418enum Entry<T, I = usize, G = u64> {
419 Free { next_free: Option<I> },
420 Occupied { generation: G, value: T },
421}
422
423/// An index (and generation) into an `Arena`.
424///
425/// To get an `Index`, insert an element into an `Arena`, and the `Index` for
426/// that element will be returned.
427///
428/// # Examples
429///
430/// ```
431/// use typed_generational_arena::StandardArena;
432///
433/// let mut arena = StandardArena::new();
434/// let idx = arena.insert(123);
435/// assert_eq!(arena[idx], 123);
436/// ```
437#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
438pub struct Index<T, I = usize, G = u64> {
439 /// The array index of the given value
440 index: I,
441 /// The generation of the given value
442 generation: G,
443 #[cfg_attr(feature = "serde", serde(skip))]
444 _phantom: core::marker::PhantomData<fn() -> T>,
445}
446
447impl<T, I: ArenaIndex + Copy, G: FixedGenerationalIndex + Copy> Index<T, I, G> {
448 /// Get this index as a `usize`
449 pub fn to_idx(&self) -> usize {
450 self.index.to_idx()
451 }
452 /// Get this index's array index into the arena
453 pub fn arr_idx(&self) -> I {
454 self.index
455 }
456 /// Get this index's generation
457 pub fn gen(&self) -> G {
458 self.generation
459 }
460}
461
462impl<T, I: ArenaIndex + Copy, G: FixedGenerationalIndex> Index<T, I, G> {
463 /// Convert a `usize` to an index at the first generation
464 #[inline]
465 pub fn from_idx_first_gen(n: usize) -> Self {
466 Index {
467 index: I::from_idx(n),
468 generation: G::first_generation(),
469 _phantom: core::marker::PhantomData,
470 }
471 }
472}
473
474impl<T, I: Debug, G: Debug> Debug for Index<T, I, G> {
475 fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
476 f.debug_struct("Index")
477 .field("index", &self.index)
478 .field("generation", &self.generation)
479 .finish()
480 }
481}
482
483impl<T, I: Copy, G: Copy> Copy for Index<T, I, G> {}
484
485impl<T, I: Clone, G: Clone> Clone for Index<T, I, G> {
486 fn clone(&self) -> Self {
487 Index {
488 index: self.index.clone(),
489 generation: self.generation.clone(),
490 _phantom: core::marker::PhantomData,
491 }
492 }
493}
494
495impl<T, I: Eq, G: Eq> Eq for Index<T, I, G> {}
496
497impl<T, I: PartialEq, G: PartialEq> PartialEq for Index<T, I, G> {
498 fn eq(&self, other: &Self) -> bool {
499 self.index == other.index && self.generation == other.generation
500 }
501}
502
503impl<T, I: Hash, G: Hash> Hash for Index<T, I, G> {
504 fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
505 self.index.hash(state);
506 self.generation.hash(state);
507 }
508}
509
510impl<T, I: ArenaIndex + Copy, G: IgnoredGeneration> Index<T, I, G> {
511 /// Convert a `usize` to an index (with generations ignored)
512 #[inline(always)]
513 pub fn from_idx(n: usize) -> Self {
514 Self::from_idx_first_gen(n)
515 }
516}
517
518impl<T, I: ArenaIndex, G: FixedGenerationalIndex> Index<T, I, G> {
519 /// Create a new index from a given array index and generation
520 #[inline]
521 pub fn new(index: I, generation: G) -> Index<T, I, G> {
522 Index {
523 index: index,
524 generation: generation,
525 _phantom: std::marker::PhantomData,
526 }
527 }
528}
529
530impl<T, I: PartialOrd, G: FixedGenerationalIndex> PartialOrd for Index<T, I, G> {
531 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
532 match self.index.partial_cmp(&other.index) {
533 Some(ordering) => {
534 if ordering == Ordering::Equal {
535 if self.generation.generation_lt(&other.generation) {
536 Some(Ordering::Less)
537 } else if self.generation == other.generation {
538 Some(Ordering::Equal)
539 } else {
540 Some(Ordering::Greater)
541 }
542 } else {
543 Some(ordering)
544 }
545 }
546 None => {
547 if self.generation.generation_lt(&other.generation) {
548 Some(Ordering::Less)
549 } else if self.generation == other.generation {
550 None
551 } else {
552 Some(Ordering::Greater)
553 }
554 }
555 }
556 }
557}
558
559impl<T, I: Ord, G: FixedGenerationalIndex> Ord for Index<T, I, G> {
560 fn cmp(&self, other: &Self) -> Ordering {
561 self.partial_cmp(other).unwrap()
562 }
563}
564
565const DEFAULT_CAPACITY: usize = 4;
566
567impl<T, I: ArenaIndex, G: FixedGenerationalIndex> Arena<T, I, G> {
568 /// Constructs a new, empty `Arena`.
569 ///
570 /// # Examples
571 ///
572 /// ```
573 /// use typed_generational_arena::StandardArena;
574 ///
575 /// let mut arena = StandardArena::<usize>::new();
576 /// # let _ = arena;
577 /// ```
578 pub fn new() -> Arena<T, I, G> {
579 Arena::with_capacity(DEFAULT_CAPACITY)
580 }
581
582 /// Constructs a new, empty `Arena<T>` with the specified capacity.
583 ///
584 /// The `Arena<T>` will be able to hold `n` elements without further allocation.
585 ///
586 /// # Examples
587 ///
588 /// ```
589 /// use typed_generational_arena::StandardArena;
590 ///
591 /// let mut arena = StandardArena::with_capacity(10);
592 ///
593 /// // These insertions will not require further allocation.
594 /// for i in 0..10 {
595 /// assert!(arena.try_insert(i).is_ok());
596 /// }
597 ///
598 /// // But now we are at capacity, and there is no more room.
599 /// assert!(arena.try_insert(99).is_err());
600 /// ```
601 pub fn with_capacity(n: usize) -> Arena<T, I, G> {
602 let n = cmp::max(n, 1);
603 let mut arena = Arena {
604 items: Vec::new(),
605 generation: G::first_generation(),
606 free_list_head: None,
607 len: 0,
608 };
609 arena.reserve(n);
610 arena
611 }
612
613 /// Clear all the items inside the arena, but keep its allocation.
614 ///
615 /// # Examples
616 ///
617 /// ```
618 /// use typed_generational_arena::StandardArena;
619 ///
620 /// let mut arena = StandardArena::with_capacity(1);
621 /// arena.insert(42);
622 /// arena.insert(43);
623 ///
624 /// arena.clear();
625 ///
626 /// assert_eq!(arena.capacity(), 2);
627 /// ```
628 pub fn clear(&mut self) {
629 self.items.clear();
630
631 let end = self.items.capacity();
632 self.items.extend((0..end).map(|i| {
633 if i == end - 1 {
634 Entry::Free { next_free: None }
635 } else {
636 Entry::Free {
637 next_free: Some(I::from_idx(i + 1)),
638 }
639 }
640 }));
641 self.free_list_head = Some(I::from_idx(0));
642 self.len = 0;
643 }
644
645 /// Attempts to insert `value` into the arena using existing capacity.
646 ///
647 /// This method will never allocate new capacity in the arena.
648 ///
649 /// If insertion succeeds, then the `value`'s index is returned. If
650 /// insertion fails, then `Err(value)` is returned to give ownership of
651 /// `value` back to the caller.
652 ///
653 /// # Examples
654 ///
655 /// ```
656 /// use typed_generational_arena::StandardArena;
657 ///
658 /// let mut arena = StandardArena::new();
659 ///
660 /// match arena.try_insert(42) {
661 /// Ok(idx) => {
662 /// // Insertion succeeded.
663 /// assert_eq!(arena[idx], 42);
664 /// }
665 /// Err(x) => {
666 /// // Insertion failed.
667 /// assert_eq!(x, 42);
668 /// }
669 /// };
670 /// ```
671 #[inline]
672 pub fn try_insert(&mut self, value: T) -> Result<Index<T, I, G>, T> {
673 match self.free_list_head {
674 None => Err(value),
675 Some(i) => {
676 let idx = i.to_idx();
677 match &self.items[idx] {
678 Entry::Occupied { .. } => panic!("corrupt free list"),
679 Entry::Free { next_free } => {
680 self.free_list_head = *next_free;
681 self.len += 1;
682 self.items[idx] = Entry::Occupied {
683 generation: self.generation,
684 value,
685 };
686 Ok(Index::new(i, self.generation))
687 }
688 }
689 }
690 }
691 }
692
693 /// Insert `value` into the arena, allocating more capacity if necessary.
694 ///
695 /// The `value`'s associated index in the arena is returned.
696 ///
697 /// # Examples
698 ///
699 /// ```
700 /// use typed_generational_arena::StandardArena;
701 ///
702 /// let mut arena = StandardArena::new();
703 ///
704 /// let idx = arena.insert(42);
705 /// assert_eq!(arena[idx], 42);
706 /// ```
707 #[inline]
708 pub fn insert(&mut self, value: T) -> Index<T, I, G> {
709 match self.try_insert(value) {
710 Ok(i) => i,
711 Err(value) => self.insert_slow_path(value),
712 }
713 }
714
715 #[inline(never)]
716 fn insert_slow_path(&mut self, value: T) -> Index<T, I, G> {
717 let len = self.items.len();
718 self.reserve(len);
719 self.try_insert(value)
720 .map_err(|_| ())
721 .expect("inserting will always succeed after reserving additional space")
722 }
723
724 /// Is the element at index `i` in the arena?
725 ///
726 /// Returns `true` if the element at `i` is in the arena, `false` otherwise.
727 ///
728 /// # Examples
729 ///
730 /// ```
731 /// use typed_generational_arena::StandardArena;
732 ///
733 /// let mut arena = StandardArena::new();
734 /// let idx = arena.insert(42);
735 ///
736 /// assert!(arena.contains(idx));
737 /// arena.remove(idx);
738 /// assert!(!arena.contains(idx));
739 /// ```
740 pub fn contains(&self, i: Index<T, I, G>) -> bool {
741 self.get(i).is_some()
742 }
743
744 /// Get a shared reference to the element at index `i` if it is in the
745 /// arena.
746 ///
747 /// If the element at index `i` is not in the arena, then `None` is returned.
748 ///
749 /// # Examples
750 ///
751 /// ```
752 /// use typed_generational_arena::StandardArena;
753 ///
754 /// let mut arena = StandardArena::new();
755 /// let idx = arena.insert(42);
756 ///
757 /// assert_eq!(arena.get(idx), Some(&42));
758 /// arena.remove(idx);
759 /// assert!(arena.get(idx).is_none());
760 /// ```
761 pub fn get(&self, i: Index<T, I, G>) -> Option<&T> {
762 match self.items.get(i.index.to_idx()) {
763 Some(Entry::Occupied {
764 generation,
765 ref value,
766 }) if *generation == i.generation => Some(value),
767 _ => None,
768 }
769 }
770
771 /// Get an exclusive reference to the element at index `i` if it is in the
772 /// arena.
773 ///
774 /// If the element at index `i` is not in the arena, then `None` is returned.
775 ///
776 /// # Examples
777 ///
778 /// ```
779 /// use typed_generational_arena::StandardArena;
780 ///
781 /// let mut arena = StandardArena::new();
782 /// let idx = arena.insert(42);
783 ///
784 /// *arena.get_mut(idx).unwrap() += 1;
785 /// assert_eq!(arena.remove(idx), Some(43));
786 /// assert!(arena.get_mut(idx).is_none());
787 /// ```
788 pub fn get_mut(&mut self, i: Index<T, I, G>) -> Option<&mut T> {
789 match self.items.get_mut(i.index.to_idx()) {
790 Some(Entry::Occupied {
791 generation,
792 ref mut value,
793 }) if *generation == i.generation => Some(value),
794 _ => None,
795 }
796 }
797
798 /// Get a pair of exclusive references to the elements at index `i1` and `i2` if it is in the
799 /// arena.
800 ///
801 /// If the element at index `i1` or `i2` is not in the arena, then `None` is returned for this
802 /// element.
803 ///
804 /// # Panics
805 ///
806 /// Panics if `i1` and `i2` are pointing to the same item of the arena.
807 ///
808 /// # Examples
809 ///
810 /// ```
811 /// use typed_generational_arena::StandardArena;
812 ///
813 /// let mut arena = StandardArena::new();
814 /// let idx1 = arena.insert(0);
815 /// let idx2 = arena.insert(1);
816 ///
817 /// {
818 /// let (item1, item2) = arena.get2_mut(idx1, idx2);
819 ///
820 /// *item1.unwrap() = 3;
821 /// *item2.unwrap() = 4;
822 /// }
823 ///
824 /// assert_eq!(arena[idx1], 3);
825 /// assert_eq!(arena[idx2], 4);
826 /// ```
827 pub fn get2_mut(
828 &mut self,
829 i1: Index<T, I, G>,
830 i2: Index<T, I, G>,
831 ) -> (Option<&mut T>, Option<&mut T>) {
832 let len = self.items.len();
833 let idx = (i1.index.to_idx(), i2.index.to_idx());
834 let gen = (i1.generation, i2.generation);
835
836 if idx.0 == idx.1 {
837 assert!(gen.0 != gen.1);
838
839 if gen.1.generation_lt(&gen.0) {
840 return (self.get_mut(i1), None);
841 }
842 return (None, self.get_mut(i2));
843 }
844
845 if idx.0 >= len {
846 return (None, self.get_mut(i2));
847 } else if idx.1 >= len {
848 return (self.get_mut(i1), None);
849 }
850
851 let (raw_item1, raw_item2) = {
852 let (xs, ys) = self.items.split_at_mut(cmp::max(idx.0, idx.1));
853 if idx.0 < idx.1 {
854 (&mut xs[idx.0], &mut ys[0])
855 } else {
856 (&mut ys[0], &mut xs[idx.1])
857 }
858 };
859
860 let item1 = match raw_item1 {
861 Entry::Occupied {
862 generation,
863 ref mut value,
864 } if *generation == gen.0 => Some(value),
865 _ => None,
866 };
867
868 let item2 = match raw_item2 {
869 Entry::Occupied {
870 generation,
871 ref mut value,
872 } if *generation == gen.1 => Some(value),
873 _ => None,
874 };
875
876 (item1, item2)
877 }
878
879 /// Get the length of this arena.
880 ///
881 /// The length is the number of elements the arena holds.
882 ///
883 /// # Examples
884 ///
885 /// ```
886 /// use typed_generational_arena::StandardArena;
887 ///
888 /// let mut arena = StandardArena::new();
889 /// assert_eq!(arena.len(), 0);
890 ///
891 /// let idx = arena.insert(42);
892 /// assert_eq!(arena.len(), 1);
893 ///
894 /// let _ = arena.insert(0);
895 /// assert_eq!(arena.len(), 2);
896 ///
897 /// assert_eq!(arena.remove(idx), Some(42));
898 /// assert_eq!(arena.len(), 1);
899 /// ```
900 pub fn len(&self) -> usize {
901 self.len
902 }
903
904 /// Returns true if the arena contains no elements
905 ///
906 /// # Examples
907 ///
908 /// ```
909 /// use typed_generational_arena::StandardArena;
910 ///
911 /// let mut arena = StandardArena::new();
912 /// assert!(arena.is_empty());
913 ///
914 /// let idx = arena.insert(42);
915 /// assert!(!arena.is_empty());
916 ///
917 /// assert_eq!(arena.remove(idx), Some(42));
918 /// assert!(arena.is_empty());
919 /// ```
920 pub fn is_empty(&self) -> bool {
921 self.len == 0
922 }
923
924 /// Get the capacity of this arena.
925 ///
926 /// The capacity is the maximum number of elements the arena can hold
927 /// without further allocation, including however many it currently
928 /// contains.
929 ///
930 /// # Examples
931 ///
932 /// ```
933 /// use typed_generational_arena::StandardArena;
934 ///
935 /// let mut arena = StandardArena::with_capacity(10);
936 /// assert_eq!(arena.capacity(), 10);
937 ///
938 /// // `try_insert` does not allocate new capacity.
939 /// for i in 0..10 {
940 /// assert!(arena.try_insert(1).is_ok());
941 /// assert_eq!(arena.capacity(), 10);
942 /// }
943 ///
944 /// // But `insert` will if the arena is already at capacity.
945 /// arena.insert(0);
946 /// assert!(arena.capacity() > 10);
947 /// ```
948 pub fn capacity(&self) -> usize {
949 self.items.len()
950 }
951
952 /// Allocate space for `additional_capacity` more elements in the arena.
953 ///
954 /// # Panics
955 ///
956 /// Panics if this causes the capacity to overflow.
957 ///
958 /// # Examples
959 ///
960 /// ```
961 /// use typed_generational_arena::StandardArena;
962 ///
963 /// let mut arena = StandardArena::with_capacity(10);
964 /// arena.reserve(5);
965 /// assert_eq!(arena.capacity(), 15);
966 /// # let _: StandardArena<usize> = arena;
967 /// ```
968 pub fn reserve(&mut self, additional_capacity: usize) {
969 let start = self.items.len();
970 let end = self.items.len() + additional_capacity;
971 let old_head = self.free_list_head;
972 self.items.reserve_exact(additional_capacity);
973 self.items.extend((start..end).map(|i| {
974 if i == end - 1 {
975 Entry::Free {
976 next_free: old_head,
977 }
978 } else {
979 Entry::Free {
980 next_free: Some(I::from_idx(i + 1)),
981 }
982 }
983 }));
984 self.free_list_head = Some(I::from_idx(start));
985 }
986
987 /// Iterate over shared references to the elements in this arena.
988 ///
989 /// Yields pairs of `(Index<T>, &T)` items.
990 ///
991 /// Order of iteration is not defined.
992 ///
993 /// # Examples
994 ///
995 /// ```
996 /// use typed_generational_arena::StandardArena;
997 ///
998 /// let mut arena = StandardArena::new();
999 /// for i in 0..10 {
1000 /// arena.insert(i * i);
1001 /// }
1002 ///
1003 /// for (idx, value) in arena.iter() {
1004 /// println!("{} is at index {:?}", value, idx);
1005 /// }
1006 /// ```
1007 pub fn iter(&self) -> Iter<T, I, G> {
1008 Iter {
1009 len: self.len,
1010 inner: self.items.iter().enumerate(),
1011 }
1012 }
1013
1014 /// Iterate over exclusive references to the elements in this arena.
1015 ///
1016 /// Yields pairs of `(Index<T>, &mut T)` items.
1017 ///
1018 /// Order of iteration is not defined.
1019 ///
1020 /// # Examples
1021 ///
1022 /// ```
1023 /// use typed_generational_arena::StandardArena;
1024 ///
1025 /// let mut arena = StandardArena::new();
1026 /// for i in 0..10 {
1027 /// arena.insert(i * i);
1028 /// }
1029 ///
1030 /// for (_idx, value) in arena.iter_mut() {
1031 /// *value += 5;
1032 /// }
1033 /// ```
1034 pub fn iter_mut(&mut self) -> IterMut<T, I, G> {
1035 IterMut {
1036 len: self.len,
1037 inner: self.items.iter_mut().enumerate(),
1038 }
1039 }
1040
1041 /// Iterate over elements of the arena and remove them.
1042 ///
1043 /// Yields pairs of `(Index<T>, T)` items.
1044 ///
1045 /// Order of iteration is not defined.
1046 ///
1047 /// Note: All elements are removed even if the iterator is only partially consumed or not consumed at all.
1048 ///
1049 /// # Examples
1050 ///
1051 /// ```
1052 /// use typed_generational_arena::StandardArena;
1053 ///
1054 /// let mut arena = StandardArena::new();
1055 /// let idx_1 = arena.insert("hello");
1056 /// let idx_2 = arena.insert("world");
1057 ///
1058 /// assert!(arena.get(idx_1).is_some());
1059 /// assert!(arena.get(idx_2).is_some());
1060 /// for (idx, value) in arena.drain() {
1061 /// assert!((idx == idx_1 && value == "hello") || (idx == idx_2 && value == "world"));
1062 /// }
1063 /// assert!(arena.get(idx_1).is_none());
1064 /// assert!(arena.get(idx_2).is_none());
1065 /// ```
1066 pub fn drain(&mut self) -> Drain<T, I, G> {
1067 Drain {
1068 inner: self.items.drain(..).enumerate(),
1069 }
1070 }
1071}
1072
1073impl<T, I: ArenaIndex, G: GenerationalIndex> Arena<T, I, G> {
1074 /// Remove the element at index `i` from the arena.
1075 ///
1076 /// If the element at index `i` is still in the arena, then it is
1077 /// returned. If it is not in the arena, then `None` is returned.
1078 ///
1079 /// # Examples
1080 ///
1081 /// ```
1082 /// use typed_generational_arena::StandardArena;
1083 ///
1084 /// let mut arena = StandardArena::new();
1085 /// let idx = arena.insert(42);
1086 ///
1087 /// assert_eq!(arena.remove(idx), Some(42));
1088 /// assert_eq!(arena.remove(idx), None);
1089 /// ```
1090 pub fn remove(&mut self, i: Index<T, I, G>) -> Option<T> {
1091 if i.index.to_idx() >= self.items.len() {
1092 return None;
1093 }
1094
1095 let entry = mem::replace(
1096 &mut self.items[i.index.to_idx()],
1097 Entry::Free {
1098 next_free: self.free_list_head,
1099 },
1100 );
1101 match entry {
1102 Entry::Occupied { generation, value } => {
1103 if generation == i.generation {
1104 self.generation.increment_generation();
1105 self.free_list_head = Some(i.index);
1106 self.len -= 1;
1107 Some(value)
1108 } else {
1109 self.items[i.index.to_idx()] = Entry::Occupied { generation, value };
1110 None
1111 }
1112 }
1113 e @ Entry::Free { .. } => {
1114 self.items[i.index.to_idx()] = e;
1115 None
1116 }
1117 }
1118 }
1119
1120 /// Retains only the elements specified by the predicate.
1121 ///
1122 /// In other words, remove all indices such that `predicate(index, &value)` returns `false`.
1123 ///
1124 /// # Examples
1125 ///
1126 /// ```
1127 /// use typed_generational_arena::StandardArena;
1128 ///
1129 /// let mut crew = StandardArena::new();
1130 /// crew.extend(&["Jim Hawkins", "John Silver", "Alexander Smollett", "Israel Hands"]);
1131 /// let pirates = ["John Silver", "Israel Hands"]; // too dangerous to keep them around
1132 /// crew.retain(|_index, member| !pirates.contains(member));
1133 /// let mut crew_members = crew.iter().map(|(_, member)| **member);
1134 /// assert_eq!(crew_members.next(), Some("Jim Hawkins"));
1135 /// assert_eq!(crew_members.next(), Some("Alexander Smollett"));
1136 /// assert!(crew_members.next().is_none());
1137 /// ```
1138 pub fn retain(&mut self, mut predicate: impl FnMut(Index<T, I, G>, &T) -> bool) {
1139 for i in 0..self.items.len() {
1140 let remove = match &self.items[i] {
1141 Entry::Occupied { generation, value } => {
1142 let index = Index::new(I::from_idx(i), *generation);
1143 if predicate(index, value) {
1144 None
1145 } else {
1146 Some(index)
1147 }
1148 }
1149 _ => None,
1150 };
1151 if let Some(index) = remove {
1152 self.remove(index);
1153 }
1154 }
1155 }
1156}
1157
1158impl<T, I: ArenaIndex, G: FixedGenerationalIndex> IntoIterator for Arena<T, I, G> {
1159 type Item = T;
1160 type IntoIter = IntoIter<T, I, G>;
1161 fn into_iter(self) -> Self::IntoIter {
1162 IntoIter {
1163 len: self.len,
1164 inner: self.items.into_iter(),
1165 }
1166 }
1167}
1168
1169/// An iterator over the elements in an arena.
1170///
1171/// Yields `T` items.
1172///
1173/// Order of iteration is not defined.
1174///
1175/// # Examples
1176///
1177/// ```
1178/// use typed_generational_arena::StandardArena;
1179///
1180/// let mut arena = StandardArena::new();
1181/// for i in 0..10 {
1182/// arena.insert(i * i);
1183/// }
1184///
1185/// for value in arena {
1186/// assert!(value < 100);
1187/// }
1188/// ```
1189#[derive(Clone, Debug)]
1190pub struct IntoIter<T, I: ArenaIndex, G: FixedGenerationalIndex> {
1191 len: usize,
1192 inner: vec::IntoIter<Entry<T, I, G>>,
1193}
1194
1195impl<T, I: ArenaIndex, G: FixedGenerationalIndex> Iterator for IntoIter<T, I, G> {
1196 type Item = T;
1197
1198 fn next(&mut self) -> Option<Self::Item> {
1199 loop {
1200 match self.inner.next() {
1201 Some(Entry::Free { .. }) => continue,
1202 Some(Entry::Occupied { value, .. }) => {
1203 self.len -= 1;
1204 return Some(value);
1205 }
1206 None => {
1207 debug_assert_eq!(self.len, 0);
1208 return None;
1209 }
1210 }
1211 }
1212 }
1213
1214 fn size_hint(&self) -> (usize, Option<usize>) {
1215 (self.len, Some(self.len))
1216 }
1217}
1218
1219impl<T, I: ArenaIndex, G: FixedGenerationalIndex> DoubleEndedIterator for IntoIter<T, I, G> {
1220 fn next_back(&mut self) -> Option<Self::Item> {
1221 loop {
1222 match self.inner.next_back() {
1223 Some(Entry::Free { .. }) => continue,
1224 Some(Entry::Occupied { value, .. }) => {
1225 self.len -= 1;
1226 return Some(value);
1227 }
1228 None => {
1229 debug_assert_eq!(self.len, 0);
1230 return None;
1231 }
1232 }
1233 }
1234 }
1235}
1236
1237impl<T, I: ArenaIndex, G: FixedGenerationalIndex> ExactSizeIterator for IntoIter<T, I, G> {
1238 fn len(&self) -> usize {
1239 self.len
1240 }
1241}
1242
1243impl<T, I: ArenaIndex, G: FixedGenerationalIndex> FusedIterator for IntoIter<T, I, G> {}
1244
1245impl<'a, T, I: ArenaIndex, G: FixedGenerationalIndex> IntoIterator for &'a Arena<T, I, G> {
1246 type Item = (Index<T, I, G>, &'a T);
1247 type IntoIter = Iter<'a, T, I, G>;
1248 fn into_iter(self) -> Self::IntoIter {
1249 self.iter()
1250 }
1251}
1252
1253/// An iterator over shared references to the elements in an arena.
1254///
1255/// Yields pairs of `(Index<T>, &T)` items.
1256///
1257/// Order of iteration is not defined.
1258///
1259/// # Examples
1260///
1261/// ```
1262/// use typed_generational_arena::StandardArena;
1263///
1264/// let mut arena = StandardArena::new();
1265/// for i in 0..10 {
1266/// arena.insert(i * i);
1267/// }
1268///
1269/// for (idx, value) in &arena {
1270/// println!("{} is at index {:?}", value, idx);
1271/// }
1272/// ```
1273#[derive(Clone, Debug)]
1274pub struct Iter<'a, T: 'a, I: 'a + ArenaIndex, G: 'a + FixedGenerationalIndex> {
1275 len: usize,
1276 inner: iter::Enumerate<slice::Iter<'a, Entry<T, I, G>>>,
1277}
1278
1279impl<'a, T, I: 'a + ArenaIndex, G: 'a + FixedGenerationalIndex> Iterator for Iter<'a, T, I, G> {
1280 type Item = (Index<T, I, G>, &'a T);
1281
1282 fn next(&mut self) -> Option<Self::Item> {
1283 loop {
1284 match self.inner.next() {
1285 Some((_, &Entry::Free { .. })) => continue,
1286 Some((
1287 index,
1288 &Entry::Occupied {
1289 generation,
1290 ref value,
1291 },
1292 )) => {
1293 self.len -= 1;
1294 let idx = Index::new(I::from_idx(index), generation);
1295 return Some((idx, value));
1296 }
1297 None => {
1298 debug_assert_eq!(self.len, 0);
1299 return None;
1300 }
1301 }
1302 }
1303 }
1304
1305 fn size_hint(&self) -> (usize, Option<usize>) {
1306 (self.len, Some(self.len))
1307 }
1308}
1309
1310impl<'a, T, I: 'a + ArenaIndex, G: 'a + FixedGenerationalIndex> DoubleEndedIterator
1311 for Iter<'a, T, I, G>
1312{
1313 fn next_back(&mut self) -> Option<Self::Item> {
1314 loop {
1315 match self.inner.next_back() {
1316 Some((_, &Entry::Free { .. })) => continue,
1317 Some((
1318 index,
1319 &Entry::Occupied {
1320 generation,
1321 ref value,
1322 },
1323 )) => {
1324 self.len -= 1;
1325 let idx = Index::new(I::from_idx(index), generation);
1326 return Some((idx, value));
1327 }
1328 None => {
1329 debug_assert_eq!(self.len, 0);
1330 return None;
1331 }
1332 }
1333 }
1334 }
1335}
1336
1337impl<'a, T, I: ArenaIndex, G: FixedGenerationalIndex> ExactSizeIterator for Iter<'a, T, I, G> {
1338 fn len(&self) -> usize {
1339 self.len
1340 }
1341}
1342
1343impl<'a, T, I: ArenaIndex, G: FixedGenerationalIndex> FusedIterator for Iter<'a, T, I, G> {}
1344
1345impl<'a, T, I: ArenaIndex, G: FixedGenerationalIndex> IntoIterator for &'a mut Arena<T, I, G> {
1346 type Item = (Index<T, I, G>, &'a mut T);
1347 type IntoIter = IterMut<'a, T, I, G>;
1348 fn into_iter(self) -> Self::IntoIter {
1349 self.iter_mut()
1350 }
1351}
1352
1353/// An iterator over exclusive references to elements in this arena.
1354///
1355/// Yields pairs of `(Index<T>, &mut T)` items.
1356///
1357/// Order of iteration is not defined.
1358///
1359/// # Examples
1360///
1361/// ```
1362/// use typed_generational_arena::StandardArena;
1363///
1364/// let mut arena = StandardArena::new();
1365/// for i in 0..10 {
1366/// arena.insert(i * i);
1367/// }
1368///
1369/// for (_idx, value) in &mut arena {
1370/// *value += 5;
1371/// }
1372/// ```
1373#[derive(Debug)]
1374pub struct IterMut<'a, T: 'a, I: 'a + ArenaIndex, G: 'a + FixedGenerationalIndex> {
1375 len: usize,
1376 inner: iter::Enumerate<slice::IterMut<'a, Entry<T, I, G>>>,
1377}
1378
1379impl<'a, T, I: 'a + ArenaIndex, G: 'a + FixedGenerationalIndex> Iterator for IterMut<'a, T, I, G> {
1380 type Item = (Index<T, I, G>, &'a mut T);
1381
1382 fn next(&mut self) -> Option<Self::Item> {
1383 loop {
1384 match self.inner.next() {
1385 Some((_, &mut Entry::Free { .. })) => continue,
1386 Some((
1387 index,
1388 &mut Entry::Occupied {
1389 generation,
1390 ref mut value,
1391 },
1392 )) => {
1393 self.len -= 1;
1394 let idx = Index::new(I::from_idx(index), generation);
1395 return Some((idx, value));
1396 }
1397 None => {
1398 debug_assert_eq!(self.len, 0);
1399 return None;
1400 }
1401 }
1402 }
1403 }
1404
1405 fn size_hint(&self) -> (usize, Option<usize>) {
1406 (self.len, Some(self.len))
1407 }
1408}
1409
1410impl<'a, T, I: 'a + ArenaIndex, G: 'a + FixedGenerationalIndex> DoubleEndedIterator
1411 for IterMut<'a, T, I, G>
1412{
1413 fn next_back(&mut self) -> Option<Self::Item> {
1414 loop {
1415 match self.inner.next_back() {
1416 Some((_, &mut Entry::Free { .. })) => continue,
1417 Some((
1418 index,
1419 &mut Entry::Occupied {
1420 generation,
1421 ref mut value,
1422 },
1423 )) => {
1424 self.len -= 1;
1425 let idx = Index::new(I::from_idx(index), generation);
1426 return Some((idx, value));
1427 }
1428 None => {
1429 debug_assert_eq!(self.len, 0);
1430 return None;
1431 }
1432 }
1433 }
1434 }
1435}
1436
1437impl<'a, T, I: 'a + ArenaIndex, G: 'a + FixedGenerationalIndex> ExactSizeIterator
1438 for IterMut<'a, T, I, G>
1439{
1440 fn len(&self) -> usize {
1441 self.len
1442 }
1443}
1444
1445impl<'a, T, I: 'a + ArenaIndex, G: 'a + FixedGenerationalIndex> FusedIterator
1446 for IterMut<'a, T, I, G>
1447{
1448}
1449
1450/// An iterator that removes elements from the arena.
1451///
1452/// Yields pairs of `(Index<T>, T)` items.
1453///
1454/// Order of iteration is not defined.
1455///
1456/// Note: All elements are removed even if the iterator is only partially consumed or not consumed at all.
1457///
1458/// # Examples
1459///
1460/// ```
1461/// use typed_generational_arena::StandardArena;
1462///
1463/// let mut arena = StandardArena::new();
1464/// let idx_1 = arena.insert("hello");
1465/// let idx_2 = arena.insert("world");
1466///
1467/// assert!(arena.get(idx_1).is_some());
1468/// assert!(arena.get(idx_2).is_some());
1469/// for (idx, value) in arena.drain() {
1470/// assert!((idx == idx_1 && value == "hello") || (idx == idx_2 && value == "world"));
1471/// }
1472/// assert!(arena.get(idx_1).is_none());
1473/// assert!(arena.get(idx_2).is_none());
1474/// ```
1475#[derive(Debug)]
1476pub struct Drain<'a, T: 'a, I: ArenaIndex, G: FixedGenerationalIndex> {
1477 inner: iter::Enumerate<vec::Drain<'a, Entry<T, I, G>>>,
1478}
1479
1480impl<'a, T, I: ArenaIndex, G: FixedGenerationalIndex> Iterator for Drain<'a, T, I, G> {
1481 type Item = (Index<T, I, G>, T);
1482
1483 fn next(&mut self) -> Option<Self::Item> {
1484 loop {
1485 match self.inner.next() {
1486 Some((_, Entry::Free { .. })) => continue,
1487 Some((index, Entry::Occupied { generation, value })) => {
1488 let idx = Index::new(I::from_idx(index), generation);
1489 return Some((idx, value));
1490 }
1491 None => return None,
1492 }
1493 }
1494 }
1495}
1496
1497impl<T, Idx: ArenaIndex, G: FixedGenerationalIndex> Extend<T> for Arena<T, Idx, G> {
1498 fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
1499 for t in iter {
1500 self.insert(t);
1501 }
1502 }
1503}
1504
1505impl<T, Idx: ArenaIndex, G: FixedGenerationalIndex> FromIterator<T> for Arena<T, Idx, G> {
1506 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
1507 let iter = iter.into_iter();
1508 let (lower, upper) = iter.size_hint();
1509 let cap = upper.unwrap_or(lower);
1510 let cap = cmp::max(cap, 1);
1511 let mut arena = Arena::with_capacity(cap);
1512 arena.extend(iter);
1513 arena
1514 }
1515}
1516
1517impl<T, I: ArenaIndex, G: FixedGenerationalIndex> ops::Index<Index<T, I, G>> for Arena<T, I, G> {
1518 type Output = T;
1519
1520 fn index(&self, index: Index<T, I, G>) -> &Self::Output {
1521 self.get(index).expect("No element at index")
1522 }
1523}
1524
1525impl<T, I: ArenaIndex, G: FixedGenerationalIndex> ops::IndexMut<Index<T, I, G>> for Arena<T, I, G> {
1526 fn index_mut(&mut self, index: Index<T, I, G>) -> &mut Self::Output {
1527 self.get_mut(index).expect("No element at index")
1528 }
1529}