auto_diff/collection/
generational_index.rs

1//! A generational index implementation.
2//! A generational index is a map-a-like container, which
3//! invalidate index/key when the item is removed,
4//! even the container itself don't have the access to that index/key.
5use std::fmt;
6
7#[cfg(feature = "use-serde")]
8use serde::{Serialize, Deserialize};
9
10use crate::err::AutoDiffError;
11
12/// GenKey index used for generational index.
13#[cfg_attr(feature = "use-serde", derive(Serialize, Deserialize))]
14#[derive(Debug, PartialEq, Eq, Ord, PartialOrd, Copy, Clone)]
15pub struct GenKey {
16    id: usize,
17    gen: usize,
18}
19    
20impl GenKey {
21    pub fn new(id: usize, gen: usize) -> GenKey {
22        GenKey { id, gen }
23    }
24}
25
26impl fmt::Display for GenKey {
27    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
28        write!(f, "({}, {})", self.id, self.gen)
29    }
30}
31
32/// A simple generational index implementation.
33/// The data is stored in a read-only manner,
34/// Use RefCell to get mutability.
35/// Not secure, no index validity check.
36#[cfg_attr(feature = "use-serde", derive(Serialize, Deserialize))]
37#[derive(Clone)]
38pub struct GenIndex<T> {
39    data: Vec<T>,
40    generation: Vec<usize>,
41    available: Vec<usize>,
42}
43
44impl<T> GenIndex<T> {
45    /// Create an empty GenIndex
46    pub fn new() -> GenIndex<T> {
47        GenIndex::<T> {
48            data: Vec::new(),
49            generation: Vec::new(),
50            available: Vec::new(),
51        }
52    }
53
54    /// Clear the GenIndex
55    pub fn clear(&mut self) {
56        self.data = Vec::new();
57        self.generation = Vec::new();
58        self.available = Vec::new();
59    }
60
61    ///
62    /// Check if a key is in the collection
63    ///
64    pub fn contains(&self, index: &GenKey) -> bool {
65        index.id < self.generation.len() && self.generation[index.id] == index.gen
66    }
67
68    /// Return the registered item
69    pub fn get(&self, index: &GenKey) -> Result<&T, AutoDiffError> {
70        if index.id < self.generation.len() && self.generation[index.id] == index.gen {
71            Ok(&self.data[index.id])
72        } else {
73            Err(AutoDiffError::new(&format!("GenIndex cannot find the item by key {:?}!", index)))
74        }
75    }
76
77    /// Return a mut reference.
78    pub fn get_mut(&mut self, index: &GenKey) -> Option<&mut T> {
79        if index.id < self.generation.len() && self.generation[index.id] == index.gen {
80            Option::Some(&mut self.data[index.id])
81        } else {
82            Option::None
83        }
84    }
85
86    /// Number of item in the list.
87    pub fn len(&self) -> usize {
88        self.data.len() - self.available.len()
89    }
90    pub fn is_empty(&self) -> bool {
91        self.len() == 0
92    }
93
94    /// Add a new item to the list.
95    pub fn insert(&mut self, val: T) -> GenKey {
96        let mut ret = GenKey::new(0, 0);
97        if self.available.is_empty() {
98            ret.id = self.data.len();
99            self.data.push(val);
100            self.generation.push(0);
101            ret.gen = 0;
102        } else {
103            ret.id = self.available.pop().expect("id in available");
104            self.data[ret.id] = val;
105            ret.gen = self.generation[ret.id];
106        }
107        ret
108    }
109
110    /// Remove an item from the list.
111    pub fn remove(&mut self, index: &GenKey) -> Result<(), AutoDiffError> {
112        if index.id < self.generation.len() && self.generation[index.id] == index.gen {
113            self.generation[index.id] += 1;
114            self.available.push(index.id);
115            Ok(())
116        } else {
117            Err(AutoDiffError::new(&format!("index is not valid! {}", index)))
118        }
119    }
120
121    /// Replace the item of the index with a new one.
122    pub fn replace(&mut self, index: &GenKey, val: T) -> Result<(), AutoDiffError> {
123        if index.id < self.data.len() && self.generation[index.id] == index.gen {
124            self.data[index.id] = val;
125            Ok(())
126        } else {
127            Err(AutoDiffError::new(&format!("index is not valid! {}", index)))
128        }
129    }
130
131    pub fn iter_key(&self) -> GenIndexIter<T> {
132        GenIndexIter::<T>::new(self)
133    }
134}
135
136
137pub struct GenIndexIter<'a, T> {
138    index: usize,
139    gen_index_ref: &'a GenIndex<T>,
140}
141impl<'a, T> GenIndexIter<'a, T> {
142    pub fn new(index_ref: &GenIndex<T>) -> GenIndexIter<T> {
143        GenIndexIter {
144            index: 0,
145            gen_index_ref: index_ref,
146        }
147    }
148}
149impl<'a, T> Iterator for GenIndexIter<'a, T> {
150    type Item = GenKey;
151    
152    fn next(&mut self) -> Option<GenKey> { // TODO: don't return Option<GenKey>, return Option<&GenKey>
153        let ret: GenKey;
154        if self.gen_index_ref.data.is_empty() {
155            return None;
156        }
157        if self.gen_index_ref.data.len() == self.index {
158            None
159        } else {
160            if self.gen_index_ref.available.is_empty() {
161                ret = GenKey::new(self.index,
162                                    self.gen_index_ref.generation[self.index]);
163            } else {
164                loop {
165                    if self.gen_index_ref.data.len() == self.index {
166                        return None;
167                    }
168                    if self.gen_index_ref.available.contains(&self.index) {
169                        self.index += 1;
170                    } else {
171                        ret = GenKey::new(self.index,
172                                            self.gen_index_ref.generation[self.index]);
173                        break;
174                    }
175                }
176            }
177            
178            self.index += 1;
179            Some(ret)
180        }
181    }
182}
183
184impl<T> Default for GenIndex<T> {
185    fn default() -> Self {
186        Self::new()
187    }
188}
189
190impl<T: PartialEq> PartialEq for GenIndex<T> {
191    fn eq(&self, other: &Self) -> bool {
192	if self.len() != other.len() {
193	    false
194	} else {
195	    for (self_key, other_key) in
196		self.iter_key().zip(other.iter_key()) {
197		    if ! self.get(&self_key).expect("GenIndex bad").eq(
198			other.get(&other_key).expect("GenIndex bad")) {
199			return false;
200		    }
201		}
202	    true
203	}
204    }
205}
206
207impl<T: Eq> Eq for GenIndex<T> {}
208
209impl<T: fmt::Debug> fmt::Debug for GenIndex<T> {
210    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
211	writeln!(f, "generation: {:?}", self.generation)?;
212	writeln!(f, "available: {:?}", self.available)?;
213	writeln!(f, "data: {:?}", self.data)
214    }
215}
216
217
218
219#[cfg(test)]
220mod tests {
221    use super::*;
222
223    #[test]
224    fn genindex_new_add_del() {
225        let mut g = GenIndex::<f32>::new();
226        assert_eq!(g.len(), 0);
227        let index1 = g.insert(1.);
228        assert_eq!(g.len(), 1);
229        assert_eq!(g.remove(&index1).expect(""), ());
230
231        let index2 = g.insert(2.);
232        let index3 = g.insert(3.);
233        assert_eq!(g.len(), 2);
234        assert_eq!(*g.get(&index2).expect(""), 2.);
235        assert_eq!(*g.get(&index3).expect(""), 3.);
236
237        g.clear();
238    }
239
240    #[test]
241    fn test_gen_index() {
242        #[derive(Debug, Copy, Clone)]
243        struct A {
244            v: u32,
245        }
246        let mut a = GenIndex::<A>::new();
247    
248        let index1 = a.insert(A { v: 10 });
249        assert_eq!(index1, GenKey::new(0, 0));
250        let index2 = a.insert(A { v: 20 });
251        assert_eq!(index2, GenKey::new(1, 0));
252    
253        let tv1 = a.get(&index1).unwrap().v;
254        assert_eq!(tv1, 10);
255        let tv2 = a.get(&index2).unwrap().v;
256        assert_eq!(tv2, 20);
257        //let tv_none = a.get(&GenKey::new(0, 1));
258        //assert_eq!(tv_none.unwrap().is_none(), true);
259    
260        let a2 = a.remove(&index2);
261        let tv_none = a.get(&index2);
262        //assert_eq!(tv_none.unwrap().is_none(), true);
263        assert_eq!(a2.expect(""), ());
264    
265        let index3 = a.insert(A { v: 30 });
266        assert_eq!(index3, GenKey::new(1, 1));
267    }
268
269    #[test]
270    fn iter() {
271        #[derive(Debug, Copy, Clone)]
272        struct A {
273            v: u32,
274        }
275        let mut a = GenIndex::<A>::new();
276
277        let index1 = a.insert(A { v: 10 });
278        let index2 = a.insert(A { v: 20 });
279        let index3 = a.insert(A { v: 30 });
280
281        let keys: Vec<GenKey> = a.iter_key().collect();
282        assert_eq!(keys, vec![GenKey::new(0, 0), GenKey::new(1, 0), GenKey::new(2, 0)]);
283
284        a.remove(&index2).expect("");
285        let keys: Vec<GenKey> = a.iter_key().collect();
286        assert_eq!(keys, vec![GenKey::new(0, 0), GenKey::new(2, 0)]);
287
288        a.remove(&index3).expect("");
289        let keys: Vec<GenKey> = a.iter_key().collect();
290        assert_eq!(keys, vec![GenKey::new(0, 0)]);
291
292        a.remove(&index1).expect("");
293        let keys: Vec<GenKey> = a.iter_key().collect();
294        assert_eq!(keys, vec![]);
295    }
296}
auto_diff/collection/generational_index.rs

auto_diff/collection/
generational_index.rs
