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