generational_array/
lib.rs

1use std::fmt;
2use std::collections::VecDeque;
3
4#[derive(Copy, Clone)] // FIXME: Do I really want it to be clonable and copiable
5pub struct GenerationalIndex {
6    pub index: usize,
7    pub generation: usize,
8}
9
10impl fmt::Display for GenerationalIndex {
11    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
12        write!(f, "(index: {}, generation: {})", self.index, self.generation)
13    }
14}
15
16#[derive(Debug)]
17pub struct GenerationalArray<ValueType> {
18
19    values: Vec<Option<ValueType>>,
20    generations: Vec<usize>,
21    free_indices: VecDeque<usize>,
22    size: usize,
23    used_size: usize,
24
25}
26
27#[derive(Debug)]
28pub enum GenerationalArrayResult<'a, ValueType> {
29    None,
30    OutDated,
31    OutOfBounds,
32    Some(&'a ValueType),
33}
34
35#[derive(Debug)]
36pub enum GenerationalArrayResultMut<'a, ValueType> {
37    None,
38    OutDated,
39    OutOfBounds,
40    Some(&'a mut ValueType),
41}
42
43impl<ValueType> GenerationalArray<ValueType> {
44
45    pub fn new() -> GenerationalArray<ValueType> {
46        GenerationalArray::<ValueType> {
47            values: Vec::<Option<ValueType>>::new(),
48            generations: Vec::<usize>::new(),
49            free_indices: VecDeque::<usize>::new(),
50            size: 0,
51            used_size: 0,
52        }
53    }
54
55    pub fn insert(&mut self, value: ValueType) -> GenerationalIndex {
56
57        // Find the index to put our new value
58        let next_index: usize = match self.free_indices.pop_front() {
59            None => {
60                // No more empty space, grow the index by one
61                self.values.push(None);
62                self.generations.push(0);
63                self.size += 1;
64                self.size - 1
65            }
66            Some(idx) => {
67                idx
68            }
69        };
70
71        // Add the value
72        self.values[next_index] = Some(value);
73        self.used_size += 1;
74        // generations[next_index] += 1;
75
76        // return the index
77        GenerationalIndex { index: next_index, generation: self.generations[next_index] }
78
79    }
80
81    pub fn remove(&mut self, index: GenerationalIndex) -> Result<(), &'static str> {
82
83        // Validate the generation
84        if index.generation != self.generations[index.index] {
85            return Err("The generation is outdated");
86        }
87
88        // Validate index
89        if index.index >=self.size{
90            return Err("The index is out of range");
91        }
92
93        // Remove the element
94        self.values[index.index] = None;
95        self.generations[index.index] += 1;
96
97        self.free_indices.push_back(index.index);
98        self.used_size -= 1;
99
100        Ok(())
101
102    }
103
104    pub fn get(&self, index: &GenerationalIndex) -> GenerationalArrayResult<ValueType> {
105
106        // Validate the generation
107        if index.generation != self.generations[index.index] {
108            return GenerationalArrayResult::OutDated;
109        }
110
111        // Validate index
112        if index.index >=self.size{
113            return GenerationalArrayResult::OutOfBounds;
114        }
115
116        match &self.values[index.index] {
117            None => GenerationalArrayResult::None,
118            Some(val) => GenerationalArrayResult::Some(val),
119        }
120
121    }
122
123    pub fn get_mut(&mut self, index: &GenerationalIndex) -> GenerationalArrayResultMut<ValueType> {
124
125        // Validate the generation
126        if index.generation != self.generations[index.index] {
127            return GenerationalArrayResultMut::OutDated;
128        }
129
130        // Validate index
131        if index.index >= self.size{
132            return GenerationalArrayResultMut::OutOfBounds;
133        }
134
135        if self.values[index.index].is_none() {
136            return GenerationalArrayResultMut::None;
137        }
138
139        GenerationalArrayResultMut::Some(self.values[index.index].as_mut().unwrap())
140
141    }
142
143    pub fn is_empty(&self) -> bool {
144        self.used_size == 0
145    }
146
147    pub fn size(&self) -> usize {
148        self.size
149    }
150
151    pub fn used_size(&self) -> usize {
152        self.used_size
153    }
154
155}
generational_array/lib.rs

generational_array/
lib.rs
