diff options
Diffstat (limited to 'lib/arena/src/map.rs')
-rw-r--r-- | lib/arena/src/map.rs | 37 |
1 files changed, 20 insertions, 17 deletions
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 | ||