aboutsummaryrefslogtreecommitdiff
path: root/lib/arena
diff options
context:
space:
mode:
Diffstat (limited to 'lib/arena')
-rw-r--r--lib/arena/src/lib.rs58
-rw-r--r--lib/arena/src/map.rs37
2 files changed, 49 insertions, 46 deletions
diff --git a/lib/arena/src/lib.rs b/lib/arena/src/lib.rs
index 1de3a1d2f..230a50291 100644
--- a/lib/arena/src/lib.rs
+++ b/lib/arena/src/lib.rs
@@ -1,4 +1,4 @@
1//! Yet another ID-based arena. 1//! Yet another index-based arena.
2 2
3#![warn(missing_docs)] 3#![warn(missing_docs)]
4 4
@@ -13,37 +13,37 @@ use std::{
13mod map; 13mod map;
14pub use map::ArenaMap; 14pub use map::ArenaMap;
15 15
16/// The raw ID of a value in an arena. 16/// The raw index of a value in an arena.
17#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)] 17#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
18pub struct RawId(u32); 18pub struct RawIdx(u32);
19 19
20impl From<RawId> for u32 { 20impl From<RawIdx> for u32 {
21 fn from(raw: RawId) -> u32 { 21 fn from(raw: RawIdx) -> u32 {
22 raw.0 22 raw.0
23 } 23 }
24} 24}
25 25
26impl From<u32> for RawId { 26impl From<u32> for RawIdx {
27 fn from(id: u32) -> RawId { 27 fn from(idx: u32) -> RawIdx {
28 RawId(id) 28 RawIdx(idx)
29 } 29 }
30} 30}
31 31
32impl fmt::Debug for RawId { 32impl fmt::Debug for RawIdx {
33 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 33 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
34 self.0.fmt(f) 34 self.0.fmt(f)
35 } 35 }
36} 36}
37 37
38impl fmt::Display for RawId { 38impl fmt::Display for RawIdx {
39 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 39 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
40 self.0.fmt(f) 40 self.0.fmt(f)
41 } 41 }
42} 42}
43 43
44/// The ID of a value allocated in an arena that holds `T`s. 44/// The index of a value allocated in an arena that holds `T`s.
45pub struct Idx<T> { 45pub struct Idx<T> {
46 raw: RawId, 46 raw: RawIdx,
47 _ty: PhantomData<fn() -> T>, 47 _ty: PhantomData<fn() -> T>,
48} 48}
49 49
@@ -78,18 +78,18 @@ impl<T> fmt::Debug for Idx<T> {
78} 78}
79 79
80impl<T> Idx<T> { 80impl<T> Idx<T> {
81 /// Creates a new ID from a [`RawId`]. 81 /// Creates a new index from a [`RawIdx`].
82 pub fn from_raw(raw: RawId) -> Self { 82 pub fn from_raw(raw: RawIdx) -> Self {
83 Idx { raw, _ty: PhantomData } 83 Idx { raw, _ty: PhantomData }
84 } 84 }
85 85
86 /// Converts this ID into the underlying [`RawId`]. 86 /// Converts this index into the underlying [`RawIdx`].
87 pub fn into_raw(self) -> RawId { 87 pub fn into_raw(self) -> RawIdx {
88 self.raw 88 self.raw
89 } 89 }
90} 90}
91 91
92/// Yet another ID-based arena. 92/// Yet another index-based arena.
93#[derive(Clone, PartialEq, Eq)] 93#[derive(Clone, PartialEq, Eq)]
94pub struct Arena<T> { 94pub struct Arena<T> {
95 data: Vec<T>, 95 data: Vec<T>,
@@ -161,37 +161,37 @@ impl<T> Arena<T> {
161 self.data.is_empty() 161 self.data.is_empty()
162 } 162 }
163 163
164 /// Allocates a new value on the arena, returning the value’s ID. 164 /// Allocates a new value on the arena, returning the value’s index.
165 /// 165 ///
166 /// ``` 166 /// ```
167 /// let mut arena = la_arena::Arena::new(); 167 /// let mut arena = la_arena::Arena::new();
168 /// let id = arena.alloc(50); 168 /// let idx = arena.alloc(50);
169 /// 169 ///
170 /// assert_eq!(arena[id], 50); 170 /// assert_eq!(arena[idx], 50);
171 /// ``` 171 /// ```
172 pub fn alloc(&mut self, value: T) -> Idx<T> { 172 pub fn alloc(&mut self, value: T) -> Idx<T> {
173 let id = RawId(self.data.len() as u32); 173 let idx = RawIdx(self.data.len() as u32);
174 self.data.push(value); 174 self.data.push(value);
175 Idx::from_raw(id) 175 Idx::from_raw(idx)
176 } 176 }
177 177
178 /// Returns an iterator over the arena’s elements. 178 /// Returns an iterator over the arena’s elements.
179 /// 179 ///
180 /// ``` 180 /// ```
181 /// let mut arena = la_arena::Arena::new(); 181 /// let mut arena = la_arena::Arena::new();
182 /// let id1 = arena.alloc(20); 182 /// let idx1 = arena.alloc(20);
183 /// let id2 = arena.alloc(40); 183 /// let idx2 = arena.alloc(40);
184 /// let id3 = arena.alloc(60); 184 /// let idx3 = arena.alloc(60);
185 /// 185 ///
186 /// let mut iterator = arena.iter(); 186 /// let mut iterator = arena.iter();
187 /// assert_eq!(iterator.next(), Some((id1, &20))); 187 /// assert_eq!(iterator.next(), Some((idx1, &20)));
188 /// assert_eq!(iterator.next(), Some((id2, &40))); 188 /// assert_eq!(iterator.next(), Some((idx2, &40)));
189 /// assert_eq!(iterator.next(), Some((id3, &60))); 189 /// assert_eq!(iterator.next(), Some((idx3, &60)));
190 /// ``` 190 /// ```
191 pub fn iter( 191 pub fn iter(
192 &self, 192 &self,
193 ) -> impl Iterator<Item = (Idx<T>, &T)> + ExactSizeIterator + DoubleEndedIterator { 193 ) -> impl Iterator<Item = (Idx<T>, &T)> + ExactSizeIterator + DoubleEndedIterator {
194 self.data.iter().enumerate().map(|(idx, value)| (Idx::from_raw(RawId(idx as u32)), value)) 194 self.data.iter().enumerate().map(|(idx, value)| (Idx::from_raw(RawIdx(idx as u32)), value))
195 } 195 }
196 196
197 /// Reallocates the arena to make it take up as little space as possible. 197 /// Reallocates the arena to make it take up as little space as possible.
diff --git a/lib/arena/src/map.rs b/lib/arena/src/map.rs
index 5ebaa9b82..d8acfe051 100644
--- a/lib/arena/src/map.rs
+++ b/lib/arena/src/map.rs
@@ -2,30 +2,33 @@ use std::marker::PhantomData;
2 2
3use crate::Idx; 3use crate::Idx;
4 4
5/// A map from arena IDs to some other type. Space requirement is O(highest ID). 5/// A map from arena indexes to some other type.
6/// Space requirement is O(highest index).
6#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] 7#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
7pub struct ArenaMap<ID, V> { 8pub struct ArenaMap<IDX, V> {
8 v: Vec<Option<V>>, 9 v: Vec<Option<V>>,
9 _ty: PhantomData<ID>, 10 _ty: PhantomData<IDX>,
10} 11}
11 12
12impl<T, V> ArenaMap<Idx<T>, V> { 13impl<T, V> ArenaMap<Idx<T>, V> {
13 /// Inserts a value associated with a given arena ID into the map. 14 /// Inserts a value associated with a given arena index into the map.
14 pub fn insert(&mut self, id: Idx<T>, t: V) { 15 pub fn insert(&mut self, idx: Idx<T>, t: V) {
15 let idx = Self::to_idx(id); 16 let idx = Self::to_idx(idx);
16 17
17 self.v.resize_with((idx + 1).max(self.v.len()), || None); 18 self.v.resize_with((idx + 1).max(self.v.len()), || None);
18 self.v[idx] = Some(t); 19 self.v[idx] = Some(t);
19 } 20 }
20 21
21 /// Returns a reference to the value associated with the provided ID if it is present. 22 /// Returns a reference to the value associated with the provided index
22 pub fn get(&self, id: Idx<T>) -> Option<&V> { 23 /// if it is present.
23 self.v.get(Self::to_idx(id)).and_then(|it| it.as_ref()) 24 pub fn get(&self, idx: Idx<T>) -> Option<&V> {
25 self.v.get(Self::to_idx(idx)).and_then(|it| it.as_ref())
24 } 26 }
25 27
26 /// Returns a mutable reference to the value associated with the provided ID if it is present. 28 /// Returns a mutable reference to the value associated with the provided index
27 pub fn get_mut(&mut self, id: Idx<T>) -> Option<&mut V> { 29 /// if it is present.
28 self.v.get_mut(Self::to_idx(id)).and_then(|it| it.as_mut()) 30 pub fn get_mut(&mut self, idx: Idx<T>) -> Option<&mut V> {
31 self.v.get_mut(Self::to_idx(idx)).and_then(|it| it.as_mut())
29 } 32 }
30 33
31 /// Returns an iterator over the values in the map. 34 /// Returns an iterator over the values in the map.
@@ -38,13 +41,13 @@ impl<T, V> ArenaMap<Idx<T>, V> {
38 self.v.iter_mut().filter_map(|o| o.as_mut()) 41 self.v.iter_mut().filter_map(|o| o.as_mut())
39 } 42 }
40 43
41 /// Returns an iterator over the arena IDs and values in the map. 44 /// Returns an iterator over the arena indexes and values in the map.
42 pub fn iter(&self) -> impl Iterator<Item = (Idx<T>, &V)> { 45 pub fn iter(&self) -> impl Iterator<Item = (Idx<T>, &V)> {
43 self.v.iter().enumerate().filter_map(|(idx, o)| Some((Self::from_idx(idx), o.as_ref()?))) 46 self.v.iter().enumerate().filter_map(|(idx, o)| Some((Self::from_idx(idx), o.as_ref()?)))
44 } 47 }
45 48
46 fn to_idx(id: Idx<T>) -> usize { 49 fn to_idx(idx: Idx<T>) -> usize {
47 u32::from(id.into_raw()) as usize 50 u32::from(idx.into_raw()) as usize
48 } 51 }
49 52
50 fn from_idx(idx: usize) -> Idx<T> { 53 fn from_idx(idx: usize) -> Idx<T> {
@@ -54,8 +57,8 @@ impl<T, V> ArenaMap<Idx<T>, V> {
54 57
55impl<T, V> std::ops::Index<Idx<V>> for ArenaMap<Idx<V>, T> { 58impl<T, V> std::ops::Index<Idx<V>> for ArenaMap<Idx<V>, T> {
56 type Output = T; 59 type Output = T;
57 fn index(&self, id: Idx<V>) -> &T { 60 fn index(&self, idx: Idx<V>) -> &T {
58 self.v[Self::to_idx(id)].as_ref().unwrap() 61 self.v[Self::to_idx(idx)].as_ref().unwrap()
59 } 62 }
60} 63}
61 64