aboutsummaryrefslogtreecommitdiff
path: root/lib/arena/src/map.rs
diff options
context:
space:
mode:
Diffstat (limited to 'lib/arena/src/map.rs')
-rw-r--r--lib/arena/src/map.rs39
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
3use std::marker::PhantomData; 1use std::marker::PhantomData;
4 2
5use crate::Idx; 3use 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)]
9pub struct ArenaMap<ID, V> { 8pub 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
14impl<T, V> ArenaMap<Idx<T>, V> { 13impl<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
57impl<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> {
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