diff options
Diffstat (limited to 'lib/arena')
-rw-r--r-- | lib/arena/src/lib.rs | 58 | ||||
-rw-r--r-- | lib/arena/src/map.rs | 37 |
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::{ | |||
13 | mod map; | 13 | mod map; |
14 | pub use map::ArenaMap; | 14 | pub 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)] |
18 | pub struct RawId(u32); | 18 | pub struct RawIdx(u32); |
19 | 19 | ||
20 | impl From<RawId> for u32 { | 20 | impl 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 | ||
26 | impl From<u32> for RawId { | 26 | impl 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 | ||
32 | impl fmt::Debug for RawId { | 32 | impl 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 | ||
38 | impl fmt::Display for RawId { | 38 | impl 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. |
45 | pub struct Idx<T> { | 45 | pub 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 | ||
80 | impl<T> Idx<T> { | 80 | impl<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)] |
94 | pub struct Arena<T> { | 94 | pub 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 | ||
3 | use crate::Idx; | 3 | use 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)] |
7 | pub struct ArenaMap<ID, V> { | 8 | pub 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 | ||
12 | impl<T, V> ArenaMap<Idx<T>, V> { | 13 | impl<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 | ||
55 | impl<T, V> std::ops::Index<Idx<V>> for ArenaMap<Idx<V>, T> { | 58 | impl<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 | ||