use crate::{index::Allocator, unmanaged::UnmanagedGenVec, Error, Incrementable};
#[derive(Debug)]
#[allow(clippy::module_name_repetitions)]
pub struct GenVec<T, G = usize, I = usize, GenIndex = (I, G)> {
allocator: Allocator<G, I, GenIndex>,
inner: UnmanagedGenVec<T, G, I, GenIndex>,
}
impl<T, G, I, GenIndex> GenVec<T, G, I, GenIndex> {
#[must_use]
#[inline]
pub fn new() -> Self
where
I: Default,
{
Self {
allocator: Allocator::new(),
inner: UnmanagedGenVec::new(),
}
}
#[must_use]
#[inline]
pub fn with_capacity(capacity: usize) -> Self
where
I: Default,
{
Self {
allocator: Allocator::new(),
inner: UnmanagedGenVec::with_capacity(capacity),
}
}
#[must_use]
#[inline]
pub fn len(&self) -> usize {
self.inner.len()
}
#[must_use]
#[inline]
pub fn is_empty(&self) -> bool {
self.inner.is_empty()
}
#[must_use]
#[inline]
pub fn capacity(&self) -> usize {
self.inner.capacity()
}
#[inline]
pub fn reserve(&mut self, additional: usize) {
self.inner.reserve(additional);
}
#[inline]
pub fn reserve_exact(&mut self, additional: usize) {
self.inner.reserve_exact(additional);
}
}
impl<T, G, I, GenIndex> Default for GenVec<T, G, I, GenIndex>
where
I: Default,
{
fn default() -> Self {
Self {
allocator: Allocator::default(),
inner: UnmanagedGenVec::default(),
}
}
}
impl<T, G, I, GenIndex> GenVec<T, G, I, GenIndex>
where
I: Into<usize>,
{
pub fn insert(&mut self, value: T) -> Result<GenIndex, Error>
where
GenIndex: From<(I, G)> + Into<(I, G)>,
G: Clone + Default + PartialOrd,
I: Clone + Incrementable,
{
let gen_index = self
.allocator
.alloc()
.ok_or_else(Error::cannot_allocate_generational_index)?;
let (index, generation) = gen_index.into();
self.inner
.set_or_push(GenIndex::from((index.clone(), generation.clone())), value)
.expect("set or push should have succeeded");
Ok(GenIndex::from((index, generation)))
}
#[must_use]
#[inline]
pub fn contains_index(&self, gen_index: GenIndex) -> bool
where
GenIndex: Into<(I, G)>,
G: PartialEq,
{
self.inner.contains_index(gen_index)
}
#[inline]
pub fn get(&self, gen_index: GenIndex) -> Result<&T, Error>
where
GenIndex: Into<(I, G)>,
G: PartialEq,
{
self.inner.get(gen_index)
}
#[inline]
pub fn get_mut(&mut self, gen_index: GenIndex) -> Result<&mut T, Error>
where
GenIndex: Into<(I, G)>,
G: PartialEq,
{
self.inner.get_mut(gen_index)
}
#[inline]
#[must_use]
pub unsafe fn get_unchecked(&self, index: usize) -> &T {
self.inner.get_unchecked(index)
}
#[inline]
#[must_use]
pub unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut T {
self.inner.get_unchecked_mut(index)
}
#[inline]
pub fn set(&mut self, gen_index: GenIndex, value: T) -> Result<(G, T), Error>
where
GenIndex: Into<(I, G)>,
G: PartialOrd,
{
self.inner.set(gen_index, value)
}
pub fn remove(&mut self, gen_index: GenIndex) -> Result<(), Error>
where
GenIndex: From<(I, G)> + Into<(I, G)>,
G: Clone + PartialOrd + Incrementable,
I: Clone,
{
let (index, generation) = gen_index.into();
if let Some(next_gen) = generation.next() {
let _prev_gen = self
.inner
.set_next_gen(GenIndex::from((index.clone(), next_gen)))?;
self.allocator.dealloc(GenIndex::from((index, generation)));
} else {
panic!("generation could not be incremented");
}
Ok(())
}
}
impl<T, G, I, GenIndex> core::ops::Index<GenIndex> for GenVec<T, G, I, GenIndex>
where
GenIndex: Into<(I, G)>,
I: Into<usize>,
G: PartialEq,
{
type Output = T;
fn index(&self, gen_index: GenIndex) -> &Self::Output {
&self.inner[gen_index]
}
}
impl<T, G, I, GenIndex> core::ops::IndexMut<GenIndex> for GenVec<T, G, I, GenIndex>
where
I: Into<usize>,
GenIndex: Into<(I, G)>,
G: PartialEq,
{
fn index_mut(&mut self, gen_index: GenIndex) -> &mut Self::Output {
&mut self.inner[gen_index]
}
}
#[cfg(test)]
mod tests {
use super::*;
#[derive(Debug, PartialEq)]
struct Value<T>(T);
impl<T> Value<T> {
fn set(&mut self, value: T) {
self.0 = value;
}
}
#[test]
fn test_contains_index_out_of_bounds() {
let gen_vec = GenVec::<Value<u32>, u8>::default();
assert!(!gen_vec.contains_index((0, 0)));
}
#[test]
fn test_contains_index_generation_less_than_existing() {
let mut gen_vec = GenVec::<Value<u32>, u8>::default();
let _ = gen_vec.insert(Value(0)).unwrap();
assert!(!gen_vec.contains_index((0, 1)));
}
#[test]
fn test_contains_index_generation_greater_than_existing() {
let mut gen_vec = GenVec::<Value<u32>, u8>::default();
let _ = gen_vec.insert(Value(0)).unwrap();
assert!(!gen_vec.contains_index((2, 0)));
}
#[test]
fn test_insert_generational_index_unavailable_by_index() {
let mut gen_vec = GenVec::<Value<u32>, u8, u8>::default();
for n in 0..=u8::MAX {
let _ = gen_vec.insert(Value(u32::from(n))).unwrap();
}
let err = gen_vec.insert(Value(0)).unwrap_err();
assert!(err.is_generational_index_allocation_error());
}
#[test]
fn test_insert_generational_index_unavailable_by_generation() {
let mut gen_vec = GenVec::<Value<(u8, u8)>, u8, u8>::default();
for idx in 0..=u8::MAX {
for gen in 0..u8::MAX {
let gen_index = gen_vec.insert(Value((idx, gen))).unwrap();
gen_vec.remove(gen_index).unwrap();
}
}
let err = gen_vec.insert(Value((0, 0))).unwrap_err();
assert!(err.is_generational_index_allocation_error());
}
#[test]
fn test_get_index_out_of_bounds() {
let gen_vec = GenVec::<Value<u32>, u8>::default();
let err = gen_vec.get((0, 0)).unwrap_err();
assert!(err.is_index_out_of_bounds());
}
#[test]
fn test_get_generation_less_than_existing() {
let mut gen_vec = GenVec::<Value<u32>, u8>::default();
let gen_index = gen_vec.insert(Value(0)).unwrap();
gen_vec.remove(gen_index).unwrap();
let gen_index = gen_vec.insert(Value(0)).unwrap();
assert_eq!(gen_index, (0, 1));
let err = gen_vec.get((0, 0)).unwrap_err();
assert!(err.is_not_equal_generation_error());
}
#[test]
fn test_get_generation_greater_than_existing() {
let mut gen_vec = GenVec::<Value<u32>, u8>::default();
let _ = gen_vec.insert(Value(0)).unwrap();
let err = gen_vec.get((0, 1)).unwrap_err();
assert!(err.is_not_equal_generation_error());
}
#[test]
fn test_get_mut_index_out_of_bounds() {
let mut gen_vec = GenVec::<Value<u32>, u8>::default();
let err = gen_vec.get_mut((0, 0)).unwrap_err();
assert!(err.is_index_out_of_bounds());
}
#[test]
fn test_get_mut_generation_less_than_existing() {
let mut gen_vec = GenVec::<Value<u32>, u8>::default();
let gen_index = gen_vec.insert(Value(0)).unwrap();
gen_vec.remove(gen_index).unwrap();
let gen_index = gen_vec.insert(Value(0)).unwrap();
assert_eq!(gen_index, (0, 1));
let err = gen_vec.get_mut((0, 0)).unwrap_err();
assert!(err.is_not_equal_generation_error());
}
#[test]
fn test_get_mut_generation_greater_than_existing() {
let mut gen_vec = GenVec::<Value<u32>, u8>::default();
let _ = gen_vec.insert(Value(0)).unwrap();
let err = gen_vec.get_mut((0, 1)).unwrap_err();
assert!(err.is_not_equal_generation_error());
}
#[test]
fn test_set_index_out_of_bounds() {
let mut gen_vec = GenVec::<Value<u32>, u8>::default();
let err = gen_vec.set((0, 0), Value(1)).unwrap_err();
assert!(err.is_index_out_of_bounds());
}
#[test]
fn test_set_generation_less_than_existing() {
let mut gen_vec = GenVec::<Value<u32>, u8>::default();
let gen_index = gen_vec.insert(Value(0)).unwrap();
gen_vec.remove(gen_index).unwrap();
let gen_index = gen_vec.insert(Value(0)).unwrap();
assert_eq!((0, 1), gen_index);
let err = gen_vec.set((0, 0), Value(1)).unwrap_err();
assert!(err.is_generation_less_than_existing());
}
#[test]
#[should_panic(expected = "generation is greater than generation associated with element")]
fn test_set_generation_greater_than_existing() {
let mut gen_vec = GenVec::<Value<u32>, u8>::default();
let _ = gen_vec.insert(Value(0)).unwrap();
gen_vec.set((0, 1), Value(1)).unwrap();
}
#[test]
fn test_remove_index_out_of_bounds() {
let mut gen_vec = GenVec::<Value<u32>, u8>::default();
let err = gen_vec.remove((0, 0)).unwrap_err();
assert!(err.is_index_out_of_bounds());
}
#[test]
fn test_remove_generation_one_less_than_existing() {
let mut gen_vec = GenVec::<Value<u32>, u8>::default();
let gen_index = gen_vec.insert(Value(0)).unwrap();
gen_vec.remove(gen_index).unwrap();
let gen_index = gen_vec.insert(Value(0)).unwrap();
assert_eq!((0, 1), gen_index);
let err = gen_vec.remove((0, 0)).unwrap_err();
assert!(err.is_already_equal_generation_error());
}
#[test]
fn test_remove_generation_more_than_one_less_than_existing() {
let mut gen_vec = GenVec::<Value<u32>, u8>::default();
let gen_index = gen_vec.insert(Value(0)).unwrap();
gen_vec.remove(gen_index).unwrap();
let gen_index = gen_vec.insert(Value(0)).unwrap();
gen_vec.remove(gen_index).unwrap();
let gen_index = gen_vec.insert(Value(0)).unwrap();
assert_eq!((0, 2), gen_index);
gen_vec.remove(gen_index).unwrap();
let err = gen_vec.remove((0, 0)).unwrap_err();
assert!(err.is_generation_less_than_existing());
}
#[test]
#[should_panic(expected = "generation is not the next generation of the current element")]
fn test_remove_generation_greater_than_existing() {
let mut gen_vec = GenVec::<Value<u32>, u8>::default();
let _ = gen_vec.insert(Value(0)).unwrap();
gen_vec.remove((0, 1)).unwrap();
}
#[test]
#[should_panic(expected = "generation could not be incremented")]
fn test_remove_generation_no_next_generation() {
let mut gen_vec = GenVec::<Value<u32>, u8>::default();
for _ in 0..u8::MAX {
let gen_index = gen_vec.insert(Value(0)).unwrap();
gen_vec.remove(gen_index).unwrap();
}
gen_vec.remove((0, 255)).unwrap();
}
#[test]
#[should_panic(expected = "index out of bounds")]
fn test_index_out_of_bounds_index() {
let gen_vec = GenVec::<Value<u32>, u8>::default();
let _ = gen_vec[(0, 0)];
}
#[test]
#[should_panic(expected = "generation is not equal")]
fn test_index_generation_less_than_existing() {
let mut gen_vec = GenVec::<Value<u32>, u8>::default();
let gen_index = gen_vec.insert(Value(0)).unwrap();
gen_vec.remove(gen_index).unwrap();
let gen_index = gen_vec.insert(Value(0)).unwrap();
assert_eq!(gen_index, (0, 1));
let _ = &gen_vec[(0, 0)];
}
#[test]
#[should_panic(expected = "generation is not equal")]
fn test_index_generation_greater_than_existing() {
let mut gen_vec = GenVec::<Value<u32>, u8>::default();
let gen_index = gen_vec.insert(Value(0)).unwrap();
assert_eq!(gen_index, (0, 0));
let _ = &gen_vec[(0, 1)];
}
#[test]
#[should_panic(expected = "index out of bounds")]
fn test_index_mut_out_of_bounds_index() {
let mut gen_vec = GenVec::<Value<u32>, u8>::default();
let _ = &mut gen_vec[(0, 0)];
}
#[test]
#[should_panic(expected = "generation is not equal")]
fn test_index_mut_generation_less_than_existing() {
let mut gen_vec = GenVec::<Value<u32>, u8>::default();
let gen_index = gen_vec.insert(Value(0)).unwrap();
gen_vec.remove(gen_index).unwrap();
let gen_index = gen_vec.insert(Value(0)).unwrap();
assert_eq!(gen_index, (0, 1));
let _ = &mut gen_vec[(0, 0)];
}
#[test]
#[should_panic(expected = "generation is not equal")]
fn test_index_mut_generation_greater_than_existing() {
let mut gen_vec = GenVec::<Value<u32>, u8>::default();
let gen_index = gen_vec.insert(Value(0)).unwrap();
assert_eq!(gen_index, (0, 0));
let _ = &mut gen_vec[(0, 1)];
}
#[test]
fn test_usage() -> Result<(), Error> {
let mut gen_vec = GenVec::<Value<u32>, u32, usize, (usize, u32)>::default();
assert_eq!(gen_vec.len(), 0);
assert!(gen_vec.is_empty());
let first_entity_index = gen_vec.insert(Value(42))?;
assert_eq!(*gen_vec.get(first_entity_index)?, Value(42));
assert!(gen_vec.contains_index(first_entity_index));
assert_eq!(gen_vec.len(), 1);
assert!(!gen_vec.is_empty());
let first_entity_value = gen_vec.get_mut(first_entity_index)?;
first_entity_value.set(1001);
assert_eq!(*gen_vec.get(first_entity_index)?, Value(1001));
assert_eq!(gen_vec.get(first_entity_index).ok(), Some(&Value(1001)));
assert_eq!(gen_vec.len(), 1);
let set_first_entity_result = gen_vec.set(first_entity_index, Value(1002))?;
assert_eq!(set_first_entity_result, (0, Value(1001)));
assert_eq!(*gen_vec.get(first_entity_index)?, Value(1002));
assert_eq!(gen_vec.len(), 1);
let other_entity_index = gen_vec.insert(Value(9))?;
assert_eq!(*gen_vec.get(first_entity_index)?, Value(1002));
assert_eq!(*gen_vec.get(other_entity_index)?, Value(9));
assert_eq!(gen_vec.len(), 2);
gen_vec.remove(first_entity_index)?;
assert!(!gen_vec.contains_index(first_entity_index));
{
let get_first_entity_result = gen_vec.get(first_entity_index);
assert!(get_first_entity_result.is_err());
assert!(get_first_entity_result
.unwrap_err()
.is_not_equal_generation_error());
}
{
let set_first_entity_result = gen_vec.set(first_entity_index, Value(1002));
assert!(set_first_entity_result.is_err());
assert!(set_first_entity_result
.unwrap_err()
.is_generation_less_than_existing());
}
assert_eq!(*gen_vec.get(other_entity_index)?, Value(9));
assert_eq!(gen_vec.len(), 2);
let last_entity_index = gen_vec.insert(Value(3))?;
assert_eq!(*gen_vec.get(other_entity_index)?, Value(9));
assert_eq!(*gen_vec.get(last_entity_index)?, Value(3));
assert_eq!(gen_vec.len(), 2);
assert!(gen_vec.get(first_entity_index).is_err());
assert_eq!(first_entity_index, (0, 0));
assert_eq!(other_entity_index, (1, 0));
assert_eq!(last_entity_index, (0, 1));
Ok::<_, Error>(())
}
#[test]
fn test_exhaust_single_index() -> Result<(), Error> {
let mut gen_vec = GenVec::<Value<u32>, u8>::default();
let mut gen_index = (0, 0);
for i in 0..u8::MAX {
gen_index = gen_vec.insert(Value(u32::from(i)))?;
assert_eq!((0, i), gen_index);
gen_vec.remove(gen_index)?;
}
assert_eq!(gen_vec.len(), 1);
assert!(!gen_vec.is_empty());
let new_gen_index = gen_vec.insert(Value(256))?;
assert_eq!((1, 0), new_gen_index);
assert_eq!((0, 254), gen_index);
let err = gen_vec.remove(gen_index).unwrap_err();
assert!(err.is_already_equal_generation_error());
let new_gen_index = gen_vec.insert(Value(257))?;
assert_eq!((2, 0), new_gen_index);
Ok::<_, Error>(())
}
#[test]
fn test_remove_old_index_repeatedly() -> Result<(), Error> {
let mut gen_vec = GenVec::<Value<u32>, u8>::default();
let gen_index = gen_vec.insert(Value(0))?;
assert_eq!(gen_index, (0, 0));
gen_vec.remove(gen_index)?;
let err = gen_vec.remove(gen_index).unwrap_err();
assert!(err.is_already_equal_generation_error());
let newer_gen_index = gen_vec.insert(Value(1))?;
assert_eq!(newer_gen_index, (0, 1));
assert_eq!(gen_vec.len(), 1);
let err = gen_vec.remove(gen_index).unwrap_err();
assert!(err.is_already_equal_generation_error());
let newer_gen_index = gen_vec.insert(Value(2))?;
assert_eq!(newer_gen_index, (1, 0));
assert_eq!(gen_vec.len(), 2);
Ok::<_, Error>(())
}
}