diff options
author | Aleksey Kladov <[email protected]> | 2021-01-14 15:47:42 +0000 |
---|---|---|
committer | Aleksey Kladov <[email protected]> | 2021-01-14 16:06:02 +0000 |
commit | 4c4e54ac8a9782439744fe15aa31a3bedab92b74 (patch) | |
tree | 6f1653b0d60298cd2932fe7c3ba4cc802f7e8b14 /crates/arena/src | |
parent | aeacaeed4e49dd71ba0de30a21d9f3d1cc153cec (diff) |
prepare to publish el libro de arena
Diffstat (limited to 'crates/arena/src')
-rw-r--r-- | crates/arena/src/lib.rs | 152 | ||||
-rw-r--r-- | crates/arena/src/map.rs | 62 |
2 files changed, 0 insertions, 214 deletions
diff --git a/crates/arena/src/lib.rs b/crates/arena/src/lib.rs deleted file mode 100644 index 3169aa5b8..000000000 --- a/crates/arena/src/lib.rs +++ /dev/null | |||
@@ -1,152 +0,0 @@ | |||
1 | //! Yet another index-based arena. | ||
2 | |||
3 | use std::{ | ||
4 | fmt, | ||
5 | hash::{Hash, Hasher}, | ||
6 | iter::FromIterator, | ||
7 | marker::PhantomData, | ||
8 | ops::{Index, IndexMut}, | ||
9 | }; | ||
10 | |||
11 | pub mod map; | ||
12 | |||
13 | #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)] | ||
14 | pub struct RawId(u32); | ||
15 | |||
16 | impl From<RawId> for u32 { | ||
17 | fn from(raw: RawId) -> u32 { | ||
18 | raw.0 | ||
19 | } | ||
20 | } | ||
21 | |||
22 | impl From<u32> for RawId { | ||
23 | fn from(id: u32) -> RawId { | ||
24 | RawId(id) | ||
25 | } | ||
26 | } | ||
27 | |||
28 | impl fmt::Debug for RawId { | ||
29 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | ||
30 | self.0.fmt(f) | ||
31 | } | ||
32 | } | ||
33 | |||
34 | impl fmt::Display for RawId { | ||
35 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | ||
36 | self.0.fmt(f) | ||
37 | } | ||
38 | } | ||
39 | |||
40 | pub struct Idx<T> { | ||
41 | raw: RawId, | ||
42 | _ty: PhantomData<fn() -> T>, | ||
43 | } | ||
44 | |||
45 | impl<T> Clone for Idx<T> { | ||
46 | fn clone(&self) -> Self { | ||
47 | *self | ||
48 | } | ||
49 | } | ||
50 | impl<T> Copy for Idx<T> {} | ||
51 | |||
52 | impl<T> PartialEq for Idx<T> { | ||
53 | fn eq(&self, other: &Idx<T>) -> bool { | ||
54 | self.raw == other.raw | ||
55 | } | ||
56 | } | ||
57 | impl<T> Eq for Idx<T> {} | ||
58 | |||
59 | impl<T> Hash for Idx<T> { | ||
60 | fn hash<H: Hasher>(&self, state: &mut H) { | ||
61 | self.raw.hash(state) | ||
62 | } | ||
63 | } | ||
64 | |||
65 | impl<T> fmt::Debug for Idx<T> { | ||
66 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | ||
67 | let mut type_name = std::any::type_name::<T>(); | ||
68 | if let Some(idx) = type_name.rfind(':') { | ||
69 | type_name = &type_name[idx + 1..] | ||
70 | } | ||
71 | write!(f, "Idx::<{}>({})", type_name, self.raw) | ||
72 | } | ||
73 | } | ||
74 | |||
75 | impl<T> Idx<T> { | ||
76 | pub fn from_raw(raw: RawId) -> Self { | ||
77 | Idx { raw, _ty: PhantomData } | ||
78 | } | ||
79 | pub fn into_raw(self) -> RawId { | ||
80 | self.raw | ||
81 | } | ||
82 | } | ||
83 | |||
84 | #[derive(Clone, PartialEq, Eq)] | ||
85 | pub struct Arena<T> { | ||
86 | data: Vec<T>, | ||
87 | } | ||
88 | |||
89 | impl<T: fmt::Debug> fmt::Debug for Arena<T> { | ||
90 | fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { | ||
91 | fmt.debug_struct("Arena").field("len", &self.len()).field("data", &self.data).finish() | ||
92 | } | ||
93 | } | ||
94 | |||
95 | impl<T> Arena<T> { | ||
96 | pub const fn new() -> Arena<T> { | ||
97 | Arena { data: Vec::new() } | ||
98 | } | ||
99 | pub fn clear(&mut self) { | ||
100 | self.data.clear(); | ||
101 | } | ||
102 | |||
103 | pub fn len(&self) -> usize { | ||
104 | self.data.len() | ||
105 | } | ||
106 | pub fn is_empty(&self) -> bool { | ||
107 | self.data.is_empty() | ||
108 | } | ||
109 | pub fn alloc(&mut self, value: T) -> Idx<T> { | ||
110 | let id = RawId(self.data.len() as u32); | ||
111 | self.data.push(value); | ||
112 | Idx::from_raw(id) | ||
113 | } | ||
114 | pub fn iter( | ||
115 | &self, | ||
116 | ) -> impl Iterator<Item = (Idx<T>, &T)> + ExactSizeIterator + DoubleEndedIterator { | ||
117 | self.data.iter().enumerate().map(|(idx, value)| (Idx::from_raw(RawId(idx as u32)), value)) | ||
118 | } | ||
119 | pub fn shrink_to_fit(&mut self) { | ||
120 | self.data.shrink_to_fit(); | ||
121 | } | ||
122 | } | ||
123 | |||
124 | impl<T> Default for Arena<T> { | ||
125 | fn default() -> Arena<T> { | ||
126 | Arena { data: Vec::new() } | ||
127 | } | ||
128 | } | ||
129 | |||
130 | impl<T> Index<Idx<T>> for Arena<T> { | ||
131 | type Output = T; | ||
132 | fn index(&self, idx: Idx<T>) -> &T { | ||
133 | let idx = idx.into_raw().0 as usize; | ||
134 | &self.data[idx] | ||
135 | } | ||
136 | } | ||
137 | |||
138 | impl<T> IndexMut<Idx<T>> for Arena<T> { | ||
139 | fn index_mut(&mut self, idx: Idx<T>) -> &mut T { | ||
140 | let idx = idx.into_raw().0 as usize; | ||
141 | &mut self.data[idx] | ||
142 | } | ||
143 | } | ||
144 | |||
145 | impl<T> FromIterator<T> for Arena<T> { | ||
146 | fn from_iter<I>(iter: I) -> Self | ||
147 | where | ||
148 | I: IntoIterator<Item = T>, | ||
149 | { | ||
150 | Arena { data: Vec::from_iter(iter) } | ||
151 | } | ||
152 | } | ||
diff --git a/crates/arena/src/map.rs b/crates/arena/src/map.rs deleted file mode 100644 index 0f33907c0..000000000 --- a/crates/arena/src/map.rs +++ /dev/null | |||
@@ -1,62 +0,0 @@ | |||
1 | //! A map from arena IDs to some other type. Space requirement is O(highest ID). | ||
2 | |||
3 | use std::marker::PhantomData; | ||
4 | |||
5 | use crate::Idx; | ||
6 | |||
7 | /// A map from arena IDs to some other type. Space requirement is O(highest ID). | ||
8 | #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] | ||
9 | pub struct ArenaMap<ID, V> { | ||
10 | v: Vec<Option<V>>, | ||
11 | _ty: PhantomData<ID>, | ||
12 | } | ||
13 | |||
14 | impl<T, V> ArenaMap<Idx<T>, V> { | ||
15 | pub fn insert(&mut self, id: Idx<T>, t: V) { | ||
16 | let idx = Self::to_idx(id); | ||
17 | |||
18 | self.v.resize_with((idx + 1).max(self.v.len()), || None); | ||
19 | self.v[idx] = Some(t); | ||
20 | } | ||
21 | |||
22 | pub fn get(&self, id: Idx<T>) -> Option<&V> { | ||
23 | self.v.get(Self::to_idx(id)).and_then(|it| it.as_ref()) | ||
24 | } | ||
25 | |||
26 | pub fn get_mut(&mut self, id: Idx<T>) -> Option<&mut V> { | ||
27 | self.v.get_mut(Self::to_idx(id)).and_then(|it| it.as_mut()) | ||
28 | } | ||
29 | |||
30 | pub fn values(&self) -> impl Iterator<Item = &V> { | ||
31 | self.v.iter().filter_map(|o| o.as_ref()) | ||
32 | } | ||
33 | |||
34 | pub fn values_mut(&mut self) -> impl Iterator<Item = &mut V> { | ||
35 | self.v.iter_mut().filter_map(|o| o.as_mut()) | ||
36 | } | ||
37 | |||
38 | pub fn iter(&self) -> impl Iterator<Item = (Idx<T>, &V)> { | ||
39 | self.v.iter().enumerate().filter_map(|(idx, o)| Some((Self::from_idx(idx), o.as_ref()?))) | ||
40 | } | ||
41 | |||
42 | fn to_idx(id: Idx<T>) -> usize { | ||
43 | u32::from(id.into_raw()) as usize | ||
44 | } | ||
45 | |||
46 | fn from_idx(idx: usize) -> Idx<T> { | ||
47 | Idx::from_raw((idx as u32).into()) | ||
48 | } | ||
49 | } | ||
50 | |||
51 | impl<T, V> std::ops::Index<Idx<V>> for ArenaMap<Idx<V>, T> { | ||
52 | type Output = T; | ||
53 | fn index(&self, id: Idx<V>) -> &T { | ||
54 | self.v[Self::to_idx(id)].as_ref().unwrap() | ||
55 | } | ||
56 | } | ||
57 | |||
58 | impl<T, V> Default for ArenaMap<Idx<V>, T> { | ||
59 | fn default() -> Self { | ||
60 | ArenaMap { v: Vec::new(), _ty: PhantomData } | ||
61 | } | ||
62 | } | ||