gen_vec/exposed/gen_vec.rs
1use std::
2{
3 vec,
4 vec::Vec,
5 iter,
6 slice
7};
8use crate::{Index, Item};
9
10#[cfg(feature = "serde")]
11use serde::{Serialize, Deserialize};
12
13/// Generationally indexed vector that relies on an independent `IndexAllocator`
14#[derive(Default, Debug)]
15#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
16pub struct ExposedGenVec<T>
17{
18 items: Vec<Option<Item<T>>>
19}
20
21impl<T> ExposedGenVec<T>
22{
23 /// Returns an empty `ExposedGenVec`
24 ///
25 /// # Examples
26 ///
27 /// ```
28 /// use gen_vec::exposed::ExposedGenVec;
29 /// let mut vec: ExposedGenVec<i32> = ExposedGenVec::new();
30 /// ```
31 pub fn new() -> ExposedGenVec<T>
32 {
33 ExposedGenVec
34 {
35 items: Vec::new()
36 }
37 }
38
39 /// Returns a `ExposedGenVec` with initial capacity of `capacity`
40 ///
41 /// Allows the `ExposedGenVec` to hold `capacity` elements before
42 /// allocating more space
43 ///
44 /// # Examples
45 ///
46 /// ```
47 /// use gen_vec::exposed::ExposedGenVec;
48 /// let mut vec: ExposedGenVec<i32> = ExposedGenVec::with_capacity(5);
49 /// ```
50 pub fn with_capacity(capacity: usize) -> ExposedGenVec<T>
51 {
52 ExposedGenVec
53 {
54 items: Vec::with_capacity(capacity)
55 }
56 }
57
58 /// Reserved capacity within the `ExposedGenVec`
59 ///
60 /// # Examples
61 ///
62 /// ```
63 /// use gen_vec::exposed::ExposedGenVec;
64 /// let mut vec: ExposedGenVec<i32> = ExposedGenVec::with_capacity(5);
65 /// assert_eq!(vec.capacity(), 5);
66 /// ```
67 pub fn capacity(&self) -> usize
68 {
69 self.items.capacity()
70 }
71
72 /// Reserves extra space for *at least* `additional` more elements
73 ///
74 /// More space may be allocated to avoid frequent re-allocations
75 /// (as per the specifications of std::vec::Vec)
76 ///
77 /// # Examples
78 ///
79 /// ```
80 /// use gen_vec::Index;
81 /// use gen_vec::exposed::{IndexAllocator, ExposedGenVec};
82 ///
83 /// let mut allocator: IndexAllocator = IndexAllocator::new();
84 /// let index: Index = allocator.allocate();
85 ///
86 /// let mut vec: ExposedGenVec<i32> = ExposedGenVec::new();
87 /// assert_eq!(vec.capacity(), 0);
88 ///
89 /// vec.set(index, 0);
90 ///
91 /// vec.reserve(4);
92 /// assert!(vec.capacity() >= 4);
93 /// ```
94 pub fn reserve(&mut self, additional: usize)
95 {
96 self.items.reserve(additional)
97 }
98
99 /// Returns `true` if the `index` points to a valid item
100 ///
101 /// # Examples
102 ///
103 /// ```
104 /// use gen_vec::Index;
105 /// use gen_vec::exposed::{IndexAllocator, ExposedGenVec};
106 ///
107 /// let mut allocator: IndexAllocator = IndexAllocator::new();
108 /// let index: Index = allocator.allocate();
109 ///
110 /// let mut vec: ExposedGenVec<i32> = ExposedGenVec::new();
111 /// assert!(!vec.contains(index));
112 /// vec.set(index, 0);
113 /// assert!(vec.contains(index));
114 /// ```
115 pub fn contains(&self, index: Index) -> bool
116 {
117 self.get(index).is_some()
118 }
119
120 /// Set the value for the given `index` and returns the previous value (if any)
121 ///
122 /// This may overwrite past (but not future) generations
123 ///
124 /// # Examples
125 ///
126 /// ```
127 /// use gen_vec::Index;
128 /// use gen_vec::exposed::{IndexAllocator, ExposedGenVec};
129 ///
130 /// let mut allocator: IndexAllocator = IndexAllocator::new();
131 /// let index: Index = allocator.allocate();
132 ///
133 /// let mut vec: ExposedGenVec<i32> = ExposedGenVec::new();
134 /// vec.set(index, 0);
135 /// assert!(vec.contains(index));
136 ///
137 /// let replaced: i32 = vec.set(index, 1).expect("0");
138 /// assert_eq!(replaced, 0);
139 /// ```
140 pub fn set(&mut self, index: Index, value: T) -> Option<T>
141 {
142 // If vec is smaller than the index, resize it and fill intermittent indices with None
143 if self.items.len() < index.index + 1
144 {
145 self.items.resize_with(index.index + 1, | | None);
146 }
147
148 match self.items.get_mut(index.index)
149 {
150 Some(Some(item)) if item.generation <= index.generation =>
151 {
152 match std::mem::replace(&mut self.items[index.index], Some(Item { value, generation: index.generation }))
153 {
154 Some(item) => Some(item.value),
155 _ => None
156 }
157 },
158 Some(_) =>
159 {
160 self.items[index.index] = Some(Item { value, generation: index.generation });
161 None
162 }
163 _ => panic!(format!("Index is out of bounds despite internal vec being resized: {:?}", index))
164 }
165 }
166
167 /// Removes the value of `index` from the vec and internally sets the element to `None`
168 ///
169 /// # Examples
170 ///
171 /// ```
172 /// use gen_vec::exposed::{IndexAllocator, ExposedGenVec};
173 ///
174 /// let mut allocater: IndexAllocator = IndexAllocator::new();
175 /// let index = allocater.allocate();
176 ///
177 /// let mut vec: ExposedGenVec<i32> = ExposedGenVec::new();
178 /// vec.set(index, 0);
179 /// let replaced: Option<i32> = vec.set(index, 1);
180 ///
181 /// assert_eq!(replaced, Some(0));
182 /// ```
183 pub fn remove(&mut self, index: Index) -> Option<T>
184 {
185 match self.items.get(index.index)
186 {
187 Some(Some(item)) if index.generation == item.generation =>
188 {
189 let removed = std::mem::replace(&mut self.items[index.index], None)
190 .expect(format!("{:?} shouldn't access a None", index).as_str());
191 Some(removed.value)
192 },
193 _ => None
194 }
195 }
196
197 /// Returns an immutable reference to the value of `index` if `index` is valid
198 ///
199 /// # Examples
200 ///
201 /// ```
202 /// use gen_vec::Index;
203 /// use gen_vec::exposed::{IndexAllocator, ExposedGenVec};
204 ///
205 /// let mut allocator: IndexAllocator = IndexAllocator::new();
206 /// let index: Index = allocator.allocate();
207 ///
208 /// let mut vec: ExposedGenVec<i32> = ExposedGenVec::new();
209 /// vec.set(index, 0);
210 /// let value: Option<&i32> = vec.get(index);
211 /// assert_eq!(value, Some(&0));
212 /// ```
213 pub fn get(&self, index: Index) -> Option<&T>
214 {
215 match self.items.get(index.index)
216 {
217 Some(Some(item)) if item.generation == index.generation => Some(&item.value),
218 _ => None
219 }
220 }
221
222 /// Returns a mutable reference to the value of `index` if `index` is valid
223 ///
224 /// # Examples
225 ///
226 /// ```
227 /// use gen_vec::Index;
228 /// use gen_vec::exposed::{IndexAllocator, ExposedGenVec};
229 ///
230 /// let mut allocator: IndexAllocator = IndexAllocator::new();
231 /// let index: Index = allocator.allocate();
232 ///
233 /// let mut vec: ExposedGenVec<i32> = ExposedGenVec::new();
234 /// vec.set(index, 0);
235 ///
236 /// let mut value: Option<&mut i32> = vec.get_mut(index);
237 /// assert_eq!(value, Some(&mut 0));
238 ///
239 /// if let Some(value) = value
240 /// {
241 /// *value = 1;
242 /// }
243 ///
244 /// let value: Option<&i32> = vec.get(index);
245 /// assert_eq!(value, Some(&1));
246 /// ```
247 pub fn get_mut(&mut self, index: Index) -> Option<&mut T>
248 {
249 match self.items.get_mut(index.index)
250 {
251 Some(Some(item)) if item.generation == index.generation => Some(&mut item.value),
252 _ => None
253 }
254 }
255
256 /// Returns an iterator of immutable references to the vec elements
257 ///
258 /// Each iterator step returns (Index, &T)
259 ///
260 /// # Examples
261 ///
262 /// ```
263 /// use gen_vec::Index;
264 /// use gen_vec::exposed::{IndexAllocator, ExposedGenVec};
265 ///
266 /// let mut allocator: IndexAllocator = IndexAllocator::new();
267 ///
268 /// let mut vec: ExposedGenVec<i32> = ExposedGenVec::new();
269 /// vec.set(allocator.allocate(), 0);
270 /// vec.set(allocator.allocate(), 1);
271 ///
272 /// for (index, value) in vec.iter()
273 /// {
274 /// println!("Index: {:?}, Value: {}", index, value);
275 /// }
276 ///
277 /// // This works as well
278 /// for (index, value) in vec
279 /// {
280 /// println!("Index: {:?}, Value: {}", index, value);
281 /// }
282 /// ```
283 pub fn iter(&self) -> Iter<T>
284 {
285 Iter
286 {
287 internal: self.items.iter().enumerate()
288 }
289 }
290
291 /// Returns an iterator of mutable references to the vec elements
292 ///
293 /// Each iterator step returns (Index, &mut T)
294 ///
295 /// # Examples
296 ///
297 /// ```
298 /// use gen_vec::Index;
299 /// use gen_vec::exposed::{IndexAllocator, ExposedGenVec};
300 ///
301 /// let mut allocator: IndexAllocator = IndexAllocator::new();
302 ///
303 /// let mut vec: ExposedGenVec<i32> = ExposedGenVec::new();
304 /// vec.set(allocator.allocate(), 0);
305 /// vec.set(allocator.allocate(), 1);
306 ///
307 /// for (index, value) in vec.iter_mut()
308 /// {
309 /// *value = 30;
310 /// }
311 /// ```
312 pub fn iter_mut(&mut self) -> IterMut<T>
313 {
314 IterMut
315 {
316 internal: self.items.iter_mut().enumerate()
317 }
318 }
319}
320
321/// Struct for consuming a `ExposedGenVec` into an iterator
322#[derive(Debug)]
323pub struct IntoIter<T>
324{
325 internal: iter::Enumerate<vec::IntoIter<Option<Item<T>>>>
326}
327
328impl<T> Iterator for IntoIter<T>
329{
330 type Item = (Index, T);
331
332 fn next(&mut self) -> Option<Self::Item>
333 {
334 loop
335 {
336 match self.internal.next()
337 {
338 Some((_, None)) => { continue; },
339 Some((index, Some(item))) => return Some((Index { index, generation: item.generation}, item.value)),
340 _ => return None
341 };
342 }
343 }
344}
345
346impl<T> IntoIterator for ExposedGenVec<T>
347{
348 type Item = (Index, T);
349 type IntoIter = IntoIter<T>;
350
351 fn into_iter(self) -> Self::IntoIter
352 {
353 IntoIter
354 {
355 internal: self.items.into_iter().enumerate()
356 }
357 }
358}
359
360/// Struct for creating an iterator over an immutable `ExposedGenVec` reference
361#[derive(Debug)]
362pub struct Iter<'a, T: 'a>
363{
364 internal: iter::Enumerate<slice::Iter<'a, Option<Item<T>>>>
365}
366
367impl<'a, T> Iterator for Iter<'a, T>
368{
369 type Item = (Index, &'a T);
370
371 fn next(&mut self) -> Option<Self::Item>
372 {
373 loop
374 {
375 match self.internal.next()
376 {
377 Some((_, None)) => { continue; },
378 Some((index, Some(item))) => return Some((Index { index, generation: item.generation}, &item.value)),
379 _ => return None
380 };
381 }
382 }
383}
384
385impl<'a, T> IntoIterator for &'a ExposedGenVec<T>
386{
387 type Item = (Index, &'a T);
388 type IntoIter = Iter<'a, T>;
389
390 fn into_iter(self) -> Self::IntoIter
391 {
392 self.iter()
393 }
394}
395
396/// Struct for creating an iterator over a mutable `ExposedGenVec` reference
397#[derive(Debug)]
398pub struct IterMut<'a, T: 'a>
399{
400 internal: iter::Enumerate<slice::IterMut<'a, Option<Item<T>>>>
401}
402
403impl<'a, T: 'a> Iterator for IterMut<'a, T>
404{
405 type Item = (Index, &'a mut T);
406
407 fn next(&mut self) -> Option<Self::Item>
408 {
409 loop
410 {
411 match self.internal.next()
412 {
413 Some((_, None)) => { continue; },
414 Some((index, Some(item))) => return Some((Index { index, generation: item.generation}, &mut item.value)),
415 _ => return None
416 };
417 }
418 }
419}
420
421impl<'a, T> IntoIterator for &'a mut ExposedGenVec<T>
422{
423 type Item = (Index, &'a mut T);
424 type IntoIter = IterMut<'a, T>;
425
426 fn into_iter(self) -> Self::IntoIter
427 {
428 self.iter_mut()
429 }
430}
431
432impl<T> std::ops::Index<Index> for ExposedGenVec<T>
433{
434 type Output = T;
435
436 fn index(&self, index: Index) -> &Self::Output
437 {
438 self.get(index).expect(format!("Index should be valid: {:?}", index).as_str())
439 }
440}
441
442impl<T> std::ops::IndexMut<Index> for ExposedGenVec<T>
443{
444 fn index_mut(&mut self, index: Index) -> &mut Self::Output
445 {
446 self.get_mut(index).expect(format!("Index should be valid: {:?}", index).as_str())
447 }
448}
449
450#[cfg(test)]
451mod vec_tests
452{
453 use crate::exposed::*;
454
455 #[test]
456 fn capacity()
457 {
458 let mut vec = ExposedGenVec::<i32>::new();
459 assert_eq!(vec.capacity(), 0);
460 vec.reserve(4);
461 assert_eq!(vec.capacity(), 4);
462 }
463
464 #[test]
465 fn set()
466 {
467 let mut allocator = IndexAllocator::new();
468 let index = allocator.allocate();
469
470 let mut vec = ExposedGenVec::new();
471 let replaced = vec.set(index, 0);
472 assert!(vec.contains(index));
473 assert_eq!(replaced, None);
474
475 allocator.deallocate(index);
476 let index1 = allocator.allocate();
477
478 let replaced = vec.set(index1, 1);
479 assert!(!vec.contains(index));
480 assert!(vec.contains(index1));
481 assert_eq!(replaced, Some(0));
482
483 for _ in 0..50
484 {
485 allocator.allocate();
486 }
487
488 let index = allocator.allocate();
489 let replaced = vec.set(index, 20);
490 assert!(vec.contains(index));
491 assert_eq!(replaced, None);
492
493 let new_val = vec.get(index);
494 assert_eq!(new_val, Some(&20));
495 }
496
497 #[test]
498 fn get()
499 {
500 let mut allocator = IndexAllocator::new();
501 let index = allocator.allocate();
502 let index1 = allocator.allocate();
503
504 let mut vec = ExposedGenVec::new();
505 vec.set(index, 0);
506 vec.set(index1, 1);
507
508 let value = vec.get(index);
509 assert_eq!(value, Some(&0));
510
511 let value = vec.get(index1);
512 assert_eq!(value, Some(&1));
513
514 if let Some(value) = vec.get_mut(index)
515 {
516 *value = 2;
517 }
518
519 let value = vec.get(index);
520 assert_eq!(value, Some(&2));
521 }
522
523 #[test]
524 fn iter()
525 {
526 let mut allocator = IndexAllocator::new();
527 let index = allocator.allocate();
528 let index1 = allocator.allocate();
529
530 let mut vec = ExposedGenVec::<i32>::new();
531 vec.set(index, 4);
532 vec.set(index1, 5);
533
534 let mut iter = vec.iter();
535
536 let (i, value) = iter.next().expect("Iterator should have next");
537 assert_eq!(i, index);
538 assert_eq!(*value, 4);
539
540 let (i, value) = iter.next().expect("Iterator should have next");
541 assert_eq!(i, index1);
542 assert_eq!(*value, 5);
543 }
544
545 #[test]
546 fn iter_mut()
547 {
548 let mut allocator = IndexAllocator::new();
549 let index = allocator.allocate();
550 let index1 = allocator.allocate();
551
552 let mut vec = ExposedGenVec::<i32>::new();
553 vec.set(index, 4);
554 vec.set(index1, 5);
555
556 let mut iter = vec.iter_mut();
557
558 let (i, value) = iter.next().expect("Iterator should have next");
559 assert_eq!(i, index);
560 assert_eq!(*value, 4);
561 *value = 0;
562
563 let (i, value) = iter.next().expect("Iterator should have next");
564 assert_eq!(i, index1);
565 assert_eq!(*value, 5);
566 *value = 1;
567
568 let value = vec.get(index);
569 assert_eq!(value, Some(&0));
570 let value = vec.get(index1);
571 assert_eq!(value, Some(&1));
572 }
573
574 #[test]
575 fn index()
576 {
577 let mut allocator = IndexAllocator::new();
578 let index = allocator.allocate();
579
580 let mut vec = ExposedGenVec::<i32>::new();
581 vec.set(index, 4);
582
583 assert_eq!(vec[index], 4);
584 }
585
586 #[test]
587 fn index_mut()
588 {
589 let mut allocator = IndexAllocator::new();
590 let index = allocator.allocate();
591
592 let mut vec = ExposedGenVec::<i32>::new();
593 vec.set(index, 3);
594
595 vec[index] = 5;
596 let value = vec.get(index);
597 assert_eq!(value, Some(&5));
598 }
599}