diff options
Diffstat (limited to 'lib/arena/src/map.rs')
-rw-r--r-- | lib/arena/src/map.rs | 39 |
1 files changed, 20 insertions, 19 deletions
diff --git a/lib/arena/src/map.rs b/lib/arena/src/map.rs index 980198247..d8acfe051 100644 --- a/lib/arena/src/map.rs +++ b/lib/arena/src/map.rs | |||
@@ -1,33 +1,34 @@ | |||
1 | //! A map from arena IDs to some other type. Space requirement is O(highest ID). | ||
2 | |||
3 | use std::marker::PhantomData; | 1 | use std::marker::PhantomData; |
4 | 2 | ||
5 | use crate::Idx; | 3 | use crate::Idx; |
6 | 4 | ||
7 | /// 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). | ||
8 | #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] | 7 | #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] |
9 | pub struct ArenaMap<ID, V> { | 8 | pub struct ArenaMap<IDX, V> { |
10 | v: Vec<Option<V>>, | 9 | v: Vec<Option<V>>, |
11 | _ty: PhantomData<ID>, | 10 | _ty: PhantomData<IDX>, |
12 | } | 11 | } |
13 | 12 | ||
14 | impl<T, V> ArenaMap<Idx<T>, V> { | 13 | impl<T, V> ArenaMap<Idx<T>, V> { |
15 | /// 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. |
16 | pub fn insert(&mut self, id: Idx<T>, t: V) { | 15 | pub fn insert(&mut self, idx: Idx<T>, t: V) { |
17 | let idx = Self::to_idx(id); | 16 | let idx = Self::to_idx(idx); |
18 | 17 | ||
19 | self.v.resize_with((idx + 1).max(self.v.len()), || None); | 18 | self.v.resize_with((idx + 1).max(self.v.len()), || None); |
20 | self.v[idx] = Some(t); | 19 | self.v[idx] = Some(t); |
21 | } | 20 | } |
22 | 21 | ||
23 | /// 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 |
24 | pub fn get(&self, id: Idx<T>) -> Option<&V> { | 23 | /// if it is present. |
25 | 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()) | ||
26 | } | 26 | } |
27 | 27 | ||
28 | /// 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 |
29 | pub fn get_mut(&mut self, id: Idx<T>) -> Option<&mut V> { | 29 | /// if it is present. |
30 | 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()) | ||
31 | } | 32 | } |
32 | 33 | ||
33 | /// Returns an iterator over the values in the map. | 34 | /// Returns an iterator over the values in the map. |
@@ -40,13 +41,13 @@ impl<T, V> ArenaMap<Idx<T>, V> { | |||
40 | self.v.iter_mut().filter_map(|o| o.as_mut()) | 41 | self.v.iter_mut().filter_map(|o| o.as_mut()) |
41 | } | 42 | } |
42 | 43 | ||
43 | /// 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. |
44 | pub fn iter(&self) -> impl Iterator<Item = (Idx<T>, &V)> { | 45 | pub fn iter(&self) -> impl Iterator<Item = (Idx<T>, &V)> { |
45 | 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()?))) |
46 | } | 47 | } |
47 | 48 | ||
48 | fn to_idx(id: Idx<T>) -> usize { | 49 | fn to_idx(idx: Idx<T>) -> usize { |
49 | u32::from(id.into_raw()) as usize | 50 | u32::from(idx.into_raw()) as usize |
50 | } | 51 | } |
51 | 52 | ||
52 | fn from_idx(idx: usize) -> Idx<T> { | 53 | fn from_idx(idx: usize) -> Idx<T> { |
@@ -56,8 +57,8 @@ impl<T, V> ArenaMap<Idx<T>, V> { | |||
56 | 57 | ||
57 | 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> { |
58 | type Output = T; | 59 | type Output = T; |
59 | fn index(&self, id: Idx<V>) -> &T { | 60 | fn index(&self, idx: Idx<V>) -> &T { |
60 | self.v[Self::to_idx(id)].as_ref().unwrap() | 61 | self.v[Self::to_idx(idx)].as_ref().unwrap() |
61 | } | 62 | } |
62 | } | 63 | } |
63 | 64 | ||