use core::{cmp::Ordering, marker::PhantomData};
#[cfg(all(feature = "alloc", not(feature = "std")))]
use alloc::vec::Vec;
#[cfg(feature = "std")]
use std::vec::Vec;
use crate::{Error, Incrementable};
#[derive(Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord)]
#[allow(clippy::module_name_repetitions)]
pub struct UnmanagedGenVec<T, G = usize, I = usize, GenIndex = (I, G)> {
inner: Vec<(G, T)>,
index_ty: PhantomData<I>,
gen_index_ty: PhantomData<GenIndex>,
}
impl<T, G, I, GenIndex> UnmanagedGenVec<T, G, I, GenIndex> {
#[must_use]
pub fn new() -> Self {
Self {
inner: Vec::new(),
index_ty: PhantomData,
gen_index_ty: PhantomData,
}
}
#[must_use]
pub fn with_capacity(capacity: usize) -> Self {
Self {
inner: Vec::with_capacity(capacity),
index_ty: PhantomData,
gen_index_ty: PhantomData,
}
}
#[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 UnmanagedGenVec<T, G, I, GenIndex> {
fn default() -> Self {
Self {
inner: Vec::default(),
index_ty: PhantomData,
gen_index_ty: PhantomData,
}
}
}
impl<T, G, I, GenIndex> UnmanagedGenVec<T, G, I, GenIndex> {
#[inline]
pub fn push(&mut self, value: T)
where
G: Default,
{
self.inner.push((G::default(), value));
}
#[inline]
pub fn push_with_gen(&mut self, generation: G, value: T) {
self.inner.push((generation, value));
}
#[must_use]
#[inline]
pub fn contains_index(&self, gen_index: GenIndex) -> bool
where
GenIndex: Into<(I, G)>,
I: Into<usize>,
G: PartialEq,
{
self.get(gen_index).is_ok()
}
pub fn get(&self, gen_index: GenIndex) -> Result<&T, Error>
where
GenIndex: Into<(I, G)>,
I: Into<usize>,
G: PartialEq,
{
let gen_index = gen_index.into();
self.inner
.get(gen_index.0.into())
.ok_or_else(Error::index_out_of_bounds)
.map(|(gen, elem)| (gen_index.1 == *gen).then(|| elem))?
.ok_or_else(Error::not_equal_generation)
}
pub fn get_mut(&mut self, gen_index: GenIndex) -> Result<&mut T, Error>
where
GenIndex: Into<(I, G)>,
I: Into<usize>,
G: PartialEq,
{
let gen_index = gen_index.into();
let elem = self
.inner
.get_mut(gen_index.0.into())
.ok_or_else(Error::index_out_of_bounds)?;
if elem.0 == gen_index.1 {
Ok(&mut elem.1)
} else {
Err(Error::not_equal_generation())
}
}
#[inline]
#[must_use]
pub unsafe fn get_unchecked(&self, index: usize) -> &T {
&self.inner.get_unchecked(index).1
}
#[inline]
#[must_use]
pub unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut T {
&mut self.inner.get_unchecked_mut(index).1
}
#[inline]
pub fn get_gen(&self, index: I) -> Option<&G>
where
I: Into<usize>,
{
self.inner.get(index.into()).map(|(gen, _value)| gen)
}
fn internal_set(&mut self, index: usize, generation: G, value: T) -> Result<(G, T), Error>
where
G: PartialOrd,
{
let elem = self
.inner
.get_mut(index)
.ok_or_else(Error::index_out_of_bounds)?;
if elem.0 == generation {
let prev_value = core::mem::replace(elem, (generation, value));
Ok(prev_value)
} else {
assert!(
generation < elem.0,
"generation is greater than generation associated with element"
);
Err(Error::less_than_existing_generation())
}
}
#[inline]
pub fn set(&mut self, gen_index: GenIndex, value: T) -> Result<(G, T), Error>
where
GenIndex: Into<(I, G)>,
G: PartialOrd,
I: Into<usize>,
{
let gen_index = gen_index.into();
self.internal_set(gen_index.0.into(), gen_index.1, value)
}
pub fn set_or_push(&mut self, gen_index: GenIndex, value: T) -> Result<Option<(G, T)>, Error>
where
GenIndex: Into<(I, G)>,
G: PartialOrd,
I: Into<usize>,
{
let (index, generation) = gen_index.into();
let index = index.into();
match index.cmp(&self.len()) {
Ordering::Less => self.internal_set(index, generation, value).map(Some),
Ordering::Equal => {
debug_assert_eq!(index, self.len());
self.push_with_gen(generation, value);
Ok(None)
}
Ordering::Greater => Err(Error::index_out_of_bounds()),
}
}
pub fn set_next_gen(&mut self, gen_index: GenIndex) -> Result<G, Error>
where
GenIndex: Into<(I, G)>,
G: PartialOrd + Incrementable,
I: Into<usize>,
{
let (index, generation) = gen_index.into();
let elem = self
.inner
.get_mut(index.into())
.ok_or_else(Error::index_out_of_bounds)?;
if elem.0 < generation {
assert!(
elem.0.next().as_ref() == Some(&generation),
"generation is not the next generation of the current element"
);
let prev_value = core::mem::replace(&mut elem.0, generation);
Ok(prev_value)
} else if elem.0 == generation {
Err(Error::already_equal_generation())
} else {
Err(Error::less_than_existing_generation())
}
}
}
impl<T, G, I, GenIndex> core::ops::Index<GenIndex> for UnmanagedGenVec<T, G, I, GenIndex>
where
I: Into<usize>,
GenIndex: Into<(I, G)>,
G: PartialEq,
{
type Output = T;
fn index(&self, gen_index: GenIndex) -> &Self::Output {
let gen_index = gen_index.into();
let idx = gen_index.0.into();
let (cur_gen, elem) = &self.inner[idx];
let expected_gen = gen_index.1;
if expected_gen == *cur_gen {
elem
} else {
panic!("generation is not equal");
}
}
}
impl<T, G, I, GenIndex> core::ops::IndexMut<GenIndex> for UnmanagedGenVec<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 {
let gen_index = gen_index.into();
let idx = gen_index.0.into();
let (cur_gen, elem) = &mut self.inner[idx];
let expected_gen = gen_index.1;
if expected_gen == *cur_gen {
elem
} else {
panic!("generation is not equal");
}
}
}
#[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 = UnmanagedGenVec::<Value<u32>, u8>::default();
assert!(!gen_vec.contains_index((0, 0)));
}
#[test]
fn test_contains_index_generation_less_than_existing() {
let mut gen_vec = UnmanagedGenVec::<Value<u32>, u8>::default();
gen_vec.push_with_gen(1, Value(0));
assert!(!gen_vec.contains_index((0, 0)));
}
#[test]
fn test_contains_index_generation_greater_than_existing() {
let mut gen_vec = UnmanagedGenVec::<Value<u32>, u8>::default();
gen_vec.push_with_gen(1, Value(0));
assert!(!gen_vec.contains_index((2, 0)));
}
#[test]
fn test_get_index_out_of_bounds() {
let gen_vec = UnmanagedGenVec::<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 = UnmanagedGenVec::<Value<u32>, u8>::default();
gen_vec.push_with_gen(1, Value(0));
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 = UnmanagedGenVec::<Value<u32>, u8>::default();
gen_vec.push_with_gen(1, Value(0));
let err = gen_vec.get((0, 2)).unwrap_err();
assert!(err.is_not_equal_generation_error());
}
#[test]
fn test_get_mut_index_out_of_bounds() {
let mut gen_vec = UnmanagedGenVec::<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 = UnmanagedGenVec::<Value<u32>, u8>::default();
gen_vec.push_with_gen(1, Value(0));
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 = UnmanagedGenVec::<Value<u32>, u8>::default();
gen_vec.push_with_gen(1, Value(0));
let err = gen_vec.get_mut((0, 2)).unwrap_err();
assert!(err.is_not_equal_generation_error());
}
#[test]
fn test_get_gen_index_out_of_bounds() {
let gen_vec = UnmanagedGenVec::<Value<u32>, u8>::default();
assert_eq!(gen_vec.get_gen(0), None);
}
#[test]
fn test_set_index_out_of_bounds() {
let mut gen_vec = UnmanagedGenVec::<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 = UnmanagedGenVec::<Value<u32>, u8>::default();
gen_vec.push_with_gen(1, Value(0));
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 = UnmanagedGenVec::<Value<u32>, u8>::default();
gen_vec.push_with_gen(0, Value(0));
gen_vec.set((0, 1), Value(1)).unwrap();
}
#[test]
fn test_set_or_push_index_out_of_bounds() {
let mut gen_vec = UnmanagedGenVec::<Value<u32>, u8>::default();
let err = gen_vec.set_or_push((1, 0), Value(1)).unwrap_err();
assert!(err.is_index_out_of_bounds());
}
#[test]
fn test_set_or_push_generation_less_than_existing() {
let mut gen_vec = UnmanagedGenVec::<Value<u32>, u8>::default();
gen_vec.push_with_gen(1, Value(0));
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_or_push_generation_greater_than_existing() {
let mut gen_vec = UnmanagedGenVec::<Value<u32>, u8>::default();
gen_vec.push_with_gen(0, Value(0));
gen_vec.set((0, 1), Value(1)).unwrap();
}
#[test]
fn test_set_next_gen_index_out_of_bounds() {
let mut gen_vec = UnmanagedGenVec::<Value<u32>, u8>::default();
let err = gen_vec.set_next_gen((0, 1)).unwrap_err();
assert!(err.is_index_out_of_bounds());
}
#[test]
fn test_set_next_gen_generation_already_equal() {
let mut gen_vec = UnmanagedGenVec::<Value<u32>, u8>::default();
gen_vec.push_with_gen(1, Value(0));
let err = gen_vec.set_next_gen((0, 1)).unwrap_err();
assert!(err.is_already_equal_generation_error());
}
#[test]
fn test_set_next_gen_generation_less_than_existing() {
let mut gen_vec = UnmanagedGenVec::<Value<u32>, u8>::default();
gen_vec.push_with_gen(2, Value(0));
let err = gen_vec.set_next_gen((0, 1)).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_set_next_gen_generation_greater_than_more_than_one_existing() {
let mut gen_vec = UnmanagedGenVec::<Value<u32>, u8>::default();
gen_vec.push_with_gen(1, Value(0));
let _ = gen_vec.set_next_gen((0, 3));
}
#[test]
#[should_panic(expected = "index out of bounds")]
fn test_index_out_of_bounds_index() {
let gen_vec = UnmanagedGenVec::<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 = UnmanagedGenVec::<Value<u32>, u8>::default();
gen_vec.push_with_gen(1, Value(0));
let _ = &gen_vec[(0, 0)];
}
#[test]
#[should_panic(expected = "generation is not equal")]
fn test_index_generation_greater_than_existing() {
let mut gen_vec = UnmanagedGenVec::<Value<u32>, u8>::default();
gen_vec.push_with_gen(0, Value(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 = UnmanagedGenVec::<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 = UnmanagedGenVec::<Value<u32>, u8>::default();
gen_vec.push_with_gen(1, Value(0));
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 = UnmanagedGenVec::<Value<u32>, u8>::default();
gen_vec.push_with_gen(0, Value(0));
let _ = &mut gen_vec[(0, 1)];
}
#[test]
fn test_index_mut() {
let mut gen_vec = UnmanagedGenVec::<Value<u32>, u8>::default();
let index = gen_vec.len();
assert_eq!(index, 0);
let generation = 0;
gen_vec.push_with_gen(generation, Value(0));
assert_eq!(gen_vec[(index, generation)], Value(0));
let value = &mut gen_vec[(index, generation)];
value.set(9);
assert_eq!(gen_vec[(index, generation)], Value(9));
}
}