1 //! Yet another index-based arena.
3 #![warn(rust_2018_idioms, unused_lifetimes, semicolon_in_expressions_from_macros)]
10 ops::{Index, IndexMut, Range, RangeInclusive},
14 pub use map::{ArenaMap, Entry, OccupiedEntry, VacantEntry};
16 /// The raw index of a value in an arena.
17 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
18 pub struct RawIdx(u32);
20 impl From<RawIdx> for u32 {
21 fn from(raw: RawIdx) -> u32 {
26 impl From<u32> for RawIdx {
27 fn from(idx: u32) -> RawIdx {
32 impl fmt::Debug for RawIdx {
33 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
38 impl fmt::Display for RawIdx {
39 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
44 /// The index of a value allocated in an arena that holds `T`s.
47 _ty: PhantomData<fn() -> T>,
50 impl<T> Clone for Idx<T> {
51 fn clone(&self) -> Self {
55 impl<T> Copy for Idx<T> {}
57 impl<T> PartialEq for Idx<T> {
58 fn eq(&self, other: &Idx<T>) -> bool {
62 impl<T> Eq for Idx<T> {}
64 impl<T> Hash for Idx<T> {
65 fn hash<H: Hasher>(&self, state: &mut H) {
70 impl<T> fmt::Debug for Idx<T> {
71 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
72 let mut type_name = std::any::type_name::<T>();
73 if let Some(idx) = type_name.rfind(':') {
74 type_name = &type_name[idx + 1..];
76 write!(f, "Idx::<{}>({})", type_name, self.raw)
81 /// Creates a new index from a [`RawIdx`].
82 pub fn from_raw(raw: RawIdx) -> Self {
83 Idx { raw, _ty: PhantomData }
86 /// Converts this index into the underlying [`RawIdx`].
87 pub fn into_raw(self) -> RawIdx {
92 /// A range of densely allocated arena values.
93 pub struct IdxRange<T> {
99 /// Creates a new index range
100 /// inclusive of the start value and exclusive of the end value.
103 /// let mut arena = la_arena::Arena::new();
104 /// let a = arena.alloc("a");
105 /// let b = arena.alloc("b");
106 /// let c = arena.alloc("c");
107 /// let d = arena.alloc("d");
109 /// let range = la_arena::IdxRange::new(b..d);
110 /// assert_eq!(&arena[range], &["b", "c"]);
112 pub fn new(range: Range<Idx<T>>) -> Self {
113 Self { range: range.start.into_raw().into()..range.end.into_raw().into(), _p: PhantomData }
116 /// Creates a new index range
117 /// inclusive of the start value and end value.
120 /// let mut arena = la_arena::Arena::new();
121 /// let foo = arena.alloc("foo");
122 /// let bar = arena.alloc("bar");
123 /// let baz = arena.alloc("baz");
125 /// let range = la_arena::IdxRange::new_inclusive(foo..=baz);
126 /// assert_eq!(&arena[range], &["foo", "bar", "baz"]);
128 /// let range = la_arena::IdxRange::new_inclusive(foo..=foo);
129 /// assert_eq!(&arena[range], &["foo"]);
131 pub fn new_inclusive(range: RangeInclusive<Idx<T>>) -> Self {
133 range: u32::from(range.start().into_raw())..u32::from(range.end().into_raw()) + 1,
138 /// Returns whether the index range is empty.
141 /// let mut arena = la_arena::Arena::new();
142 /// let one = arena.alloc(1);
143 /// let two = arena.alloc(2);
145 /// assert!(la_arena::IdxRange::new(one..one).is_empty());
147 pub fn is_empty(&self) -> bool {
148 self.range.is_empty()
152 impl<T> Iterator for IdxRange<T> {
154 fn next(&mut self) -> Option<Self::Item> {
155 self.range.next().map(|raw| Idx::from_raw(raw.into()))
159 impl<T> DoubleEndedIterator for IdxRange<T> {
160 fn next_back(&mut self) -> Option<Self::Item> {
161 self.range.next_back().map(|raw| Idx::from_raw(raw.into()))
165 impl<T> fmt::Debug for IdxRange<T> {
166 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
167 f.debug_tuple(&format!("IdxRange::<{}>", std::any::type_name::<T>()))
173 impl<T> Clone for IdxRange<T> {
174 fn clone(&self) -> Self {
175 Self { range: self.range.clone(), _p: PhantomData }
179 impl<T> PartialEq for IdxRange<T> {
180 fn eq(&self, other: &Self) -> bool {
181 self.range == other.range
185 impl<T> Eq for IdxRange<T> {}
187 /// Yet another index-based arena.
188 #[derive(Clone, PartialEq, Eq, Hash)]
189 pub struct Arena<T> {
193 impl<T: fmt::Debug> fmt::Debug for Arena<T> {
194 fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
195 fmt.debug_struct("Arena").field("len", &self.len()).field("data", &self.data).finish()
200 /// Creates a new empty arena.
203 /// let arena: la_arena::Arena<i32> = la_arena::Arena::new();
204 /// assert!(arena.is_empty());
206 pub const fn new() -> Arena<T> {
207 Arena { data: Vec::new() }
210 /// Create a new empty arena with specific capacity.
213 /// let arena: la_arena::Arena<i32> = la_arena::Arena::with_capacity(42);
214 /// assert!(arena.is_empty());
216 pub fn with_capacity(capacity: usize) -> Arena<T> {
217 Arena { data: Vec::with_capacity(capacity) }
220 /// Empties the arena, removing all contained values.
223 /// let mut arena = la_arena::Arena::new();
228 /// assert_eq!(arena.len(), 3);
231 /// assert!(arena.is_empty());
233 pub fn clear(&mut self) {
237 /// Returns the length of the arena.
240 /// let mut arena = la_arena::Arena::new();
241 /// assert_eq!(arena.len(), 0);
243 /// arena.alloc("foo");
244 /// assert_eq!(arena.len(), 1);
246 /// arena.alloc("bar");
247 /// assert_eq!(arena.len(), 2);
249 /// arena.alloc("baz");
250 /// assert_eq!(arena.len(), 3);
252 pub fn len(&self) -> usize {
256 /// Returns whether the arena contains no elements.
259 /// let mut arena = la_arena::Arena::new();
260 /// assert!(arena.is_empty());
262 /// arena.alloc(0.5);
263 /// assert!(!arena.is_empty());
265 pub fn is_empty(&self) -> bool {
269 /// Allocates a new value on the arena, returning the value’s index.
272 /// let mut arena = la_arena::Arena::new();
273 /// let idx = arena.alloc(50);
275 /// assert_eq!(arena[idx], 50);
277 pub fn alloc(&mut self, value: T) -> Idx<T> {
278 let idx = self.next_idx();
279 self.data.push(value);
283 /// Returns an iterator over the arena’s elements.
286 /// let mut arena = la_arena::Arena::new();
287 /// let idx1 = arena.alloc(20);
288 /// let idx2 = arena.alloc(40);
289 /// let idx3 = arena.alloc(60);
291 /// let mut iterator = arena.iter();
292 /// assert_eq!(iterator.next(), Some((idx1, &20)));
293 /// assert_eq!(iterator.next(), Some((idx2, &40)));
294 /// assert_eq!(iterator.next(), Some((idx3, &60)));
298 ) -> impl Iterator<Item = (Idx<T>, &T)> + ExactSizeIterator + DoubleEndedIterator {
299 self.data.iter().enumerate().map(|(idx, value)| (Idx::from_raw(RawIdx(idx as u32)), value))
302 /// Returns an iterator over the arena’s mutable elements.
305 /// let mut arena = la_arena::Arena::new();
306 /// let idx1 = arena.alloc(20);
308 /// assert_eq!(arena[idx1], 20);
310 /// let mut iterator = arena.iter_mut();
311 /// *iterator.next().unwrap().1 = 10;
314 /// assert_eq!(arena[idx1], 10);
318 ) -> impl Iterator<Item = (Idx<T>, &mut T)> + ExactSizeIterator + DoubleEndedIterator {
322 .map(|(idx, value)| (Idx::from_raw(RawIdx(idx as u32)), value))
325 /// Returns an iterator over the arena’s values.
328 /// let mut arena = la_arena::Arena::new();
329 /// let idx1 = arena.alloc(20);
330 /// let idx2 = arena.alloc(40);
331 /// let idx3 = arena.alloc(60);
333 /// let mut iterator = arena.values();
334 /// assert_eq!(iterator.next(), Some(&20));
335 /// assert_eq!(iterator.next(), Some(&40));
336 /// assert_eq!(iterator.next(), Some(&60));
338 pub fn values(&mut self) -> impl Iterator<Item = &T> + ExactSizeIterator + DoubleEndedIterator {
342 /// Returns an iterator over the arena’s mutable values.
345 /// let mut arena = la_arena::Arena::new();
346 /// let idx1 = arena.alloc(20);
348 /// assert_eq!(arena[idx1], 20);
350 /// let mut iterator = arena.values_mut();
351 /// *iterator.next().unwrap() = 10;
354 /// assert_eq!(arena[idx1], 10);
358 ) -> impl Iterator<Item = &mut T> + ExactSizeIterator + DoubleEndedIterator {
362 /// Reallocates the arena to make it take up as little space as possible.
363 pub fn shrink_to_fit(&mut self) {
364 self.data.shrink_to_fit();
367 /// Returns the index of the next value allocated on the arena.
369 /// This method should remain private to make creating invalid `Idx`s harder.
370 fn next_idx(&self) -> Idx<T> {
371 Idx::from_raw(RawIdx(self.data.len() as u32))
375 impl<T> Default for Arena<T> {
376 fn default() -> Arena<T> {
377 Arena { data: Vec::new() }
381 impl<T> Index<Idx<T>> for Arena<T> {
383 fn index(&self, idx: Idx<T>) -> &T {
384 let idx = idx.into_raw().0 as usize;
389 impl<T> IndexMut<Idx<T>> for Arena<T> {
390 fn index_mut(&mut self, idx: Idx<T>) -> &mut T {
391 let idx = idx.into_raw().0 as usize;
396 impl<T> Index<IdxRange<T>> for Arena<T> {
398 fn index(&self, range: IdxRange<T>) -> &[T] {
399 let start = range.range.start as usize;
400 let end = range.range.end as usize;
401 &self.data[start..end]
405 impl<T> FromIterator<T> for Arena<T> {
406 fn from_iter<I>(iter: I) -> Self
408 I: IntoIterator<Item = T>,
410 Arena { data: Vec::from_iter(iter) }