1#![no_std]
8#![warn(
9 clippy::cast_lossless,
10 clippy::missing_errors_doc,
11 clippy::used_underscore_binding,
12 clippy::redundant_closure_for_method_calls,
13 clippy::type_repetition_in_bounds,
14 clippy::inconsistent_struct_constructor,
15 clippy::default_trait_access,
16 clippy::map_unwrap_or,
17 clippy::items_after_statements
18)]
19
20#[cfg(not(feature = "std"))]
21extern crate alloc as std;
22
23#[cfg(feature = "std")]
24extern crate std;
25
26mod component_vec;
27mod dedup;
28mod guarded;
29
30#[cfg(test)]
31mod tests;
32
33pub use self::{component_vec::ComponentVec, dedup::DedupArena, guarded::GuardedEntity};
34use core::{
35 iter::Enumerate,
36 marker::PhantomData,
37 ops::{Index, IndexMut},
38 slice,
39};
40use std::vec::Vec;
41
42pub trait ArenaIndex: Copy {
44 fn into_usize(self) -> usize;
46 fn from_usize(value: usize) -> Self;
48}
49
50#[derive(Debug)]
54pub struct Arena<Idx, T> {
55 entities: Vec<T>,
56 marker: PhantomData<Idx>,
57}
58
59unsafe impl<Idx, T> Send for Arena<Idx, T> where T: Send {}
61
62unsafe impl<Idx, T> Sync for Arena<Idx, T> where T: Send {}
64
65impl<Idx, T> Default for Arena<Idx, T> {
66 fn default() -> Self {
67 Self::new()
68 }
69}
70
71impl<Idx, T> PartialEq for Arena<Idx, T>
72where
73 T: PartialEq,
74{
75 fn eq(&self, other: &Self) -> bool {
76 self.entities.eq(&other.entities)
77 }
78}
79
80impl<Idx, T> Eq for Arena<Idx, T> where T: Eq {}
81
82impl<Idx, T> Arena<Idx, T> {
83 pub fn new() -> Self {
85 Self {
86 entities: Vec::new(),
87 marker: PhantomData,
88 }
89 }
90
91 #[inline]
93 pub fn len(&self) -> usize {
94 self.entities.len()
95 }
96
97 #[inline]
99 pub fn is_empty(&self) -> bool {
100 self.len() == 0
101 }
102
103 pub fn clear(&mut self) {
105 self.entities.clear();
106 }
107
108 pub fn iter(&self) -> Iter<Idx, T> {
110 Iter {
111 iter: self.entities.iter().enumerate(),
112 marker: PhantomData,
113 }
114 }
115
116 pub fn iter_mut(&mut self) -> IterMut<Idx, T> {
118 IterMut {
119 iter: self.entities.iter_mut().enumerate(),
120 marker: PhantomData,
121 }
122 }
123}
124
125impl<Idx, T> Arena<Idx, T>
126where
127 Idx: ArenaIndex,
128{
129 fn next_index(&self) -> Idx {
131 Idx::from_usize(self.entities.len())
132 }
133
134 #[inline]
136 pub fn alloc(&mut self, entity: T) -> Idx {
137 let index = self.next_index();
138 self.entities.push(entity);
139 index
140 }
141
142 #[inline]
144 pub fn get(&self, index: Idx) -> Option<&T> {
145 self.entities.get(index.into_usize())
146 }
147
148 #[inline]
150 pub fn get_mut(&mut self, index: Idx) -> Option<&mut T> {
151 self.entities.get_mut(index.into_usize())
152 }
153
154 #[inline]
159 pub fn get_pair_mut(&mut self, fst: Idx, snd: Idx) -> Option<(&mut T, &mut T)> {
160 let fst_index = fst.into_usize();
161 let snd_index = snd.into_usize();
162 if fst_index == snd_index {
163 return None;
164 }
165 if fst_index > snd_index {
166 let (fst, snd) = self.get_pair_mut(snd, fst)?;
167 return Some((snd, fst));
168 }
169 let (fst_set, snd_set) = self.entities.split_at_mut(snd_index);
171 let fst = fst_set.get_mut(fst_index)?;
172 let snd = snd_set.get_mut(0)?;
173 Some((fst, snd))
174 }
175}
176
177impl<Idx, T> FromIterator<T> for Arena<Idx, T> {
178 fn from_iter<I>(iter: I) -> Self
179 where
180 I: IntoIterator<Item = T>,
181 {
182 Self {
183 entities: Vec::from_iter(iter),
184 marker: PhantomData,
185 }
186 }
187}
188
189impl<'a, Idx, T> IntoIterator for &'a Arena<Idx, T>
190where
191 Idx: ArenaIndex,
192{
193 type Item = (Idx, &'a T);
194 type IntoIter = Iter<'a, Idx, T>;
195
196 fn into_iter(self) -> Self::IntoIter {
197 self.iter()
198 }
199}
200
201impl<'a, Idx, T> IntoIterator for &'a mut Arena<Idx, T>
202where
203 Idx: ArenaIndex,
204{
205 type Item = (Idx, &'a mut T);
206 type IntoIter = IterMut<'a, Idx, T>;
207
208 fn into_iter(self) -> Self::IntoIter {
209 self.iter_mut()
210 }
211}
212
213#[derive(Debug)]
215pub struct Iter<'a, Idx, T> {
216 iter: Enumerate<slice::Iter<'a, T>>,
217 marker: PhantomData<fn() -> Idx>,
218}
219
220impl<'a, Idx, T> Iterator for Iter<'a, Idx, T>
221where
222 Idx: ArenaIndex,
223{
224 type Item = (Idx, &'a T);
225
226 #[inline]
227 fn next(&mut self) -> Option<Self::Item> {
228 self.iter
229 .next()
230 .map(|(idx, entity)| (Idx::from_usize(idx), entity))
231 }
232
233 #[inline]
234 fn size_hint(&self) -> (usize, Option<usize>) {
235 self.iter.size_hint()
236 }
237}
238
239impl<'a, Idx, T> DoubleEndedIterator for Iter<'a, Idx, T>
240where
241 Idx: ArenaIndex,
242{
243 #[inline]
244 fn next_back(&mut self) -> Option<Self::Item> {
245 self.iter
246 .next()
247 .map(|(idx, entity)| (Idx::from_usize(idx), entity))
248 }
249}
250
251impl<'a, Idx, T> ExactSizeIterator for Iter<'a, Idx, T>
252where
253 Idx: ArenaIndex,
254{
255 fn len(&self) -> usize {
256 self.iter.len()
257 }
258}
259
260#[derive(Debug)]
262pub struct IterMut<'a, Idx, T> {
263 iter: Enumerate<slice::IterMut<'a, T>>,
264 marker: PhantomData<fn() -> Idx>,
265}
266
267impl<'a, Idx, T> Iterator for IterMut<'a, Idx, T>
268where
269 Idx: ArenaIndex,
270{
271 type Item = (Idx, &'a mut T);
272
273 #[inline]
274 fn next(&mut self) -> Option<Self::Item> {
275 self.iter
276 .next()
277 .map(|(idx, entity)| (Idx::from_usize(idx), entity))
278 }
279
280 #[inline]
281 fn size_hint(&self) -> (usize, Option<usize>) {
282 self.iter.size_hint()
283 }
284}
285
286impl<'a, Idx, T> DoubleEndedIterator for IterMut<'a, Idx, T>
287where
288 Idx: ArenaIndex,
289{
290 #[inline]
291 fn next_back(&mut self) -> Option<Self::Item> {
292 self.iter
293 .next()
294 .map(|(idx, entity)| (Idx::from_usize(idx), entity))
295 }
296}
297
298impl<'a, Idx, T> ExactSizeIterator for IterMut<'a, Idx, T>
299where
300 Idx: ArenaIndex,
301{
302 #[inline]
303 fn len(&self) -> usize {
304 self.iter.len()
305 }
306}
307
308impl<Idx, T> Arena<Idx, T> {
309 fn index_out_of_bounds(len: usize, index: usize) -> ! {
311 panic!("index out of bounds: the len is {len} but the index is {index}")
312 }
313}
314
315impl<Idx, T> Index<Idx> for Arena<Idx, T>
316where
317 Idx: ArenaIndex,
318{
319 type Output = T;
320
321 #[inline]
322 fn index(&self, index: Idx) -> &Self::Output {
323 self.get(index)
324 .unwrap_or_else(|| Self::index_out_of_bounds(self.len(), index.into_usize()))
325 }
326}
327
328impl<Idx, T> IndexMut<Idx> for Arena<Idx, T>
329where
330 Idx: ArenaIndex,
331{
332 #[inline]
333 fn index_mut(&mut self, index: Idx) -> &mut Self::Output {
334 let len = self.len();
335 self.get_mut(index)
336 .unwrap_or_else(|| Self::index_out_of_bounds(len, index.into_usize()))
337 }
338}