hexga_generational/
gen_vec.rs

1use crate::*;
2use std::{collections::HashMap, fmt::Debug, hash::{Hash, Hasher}, iter::FusedIterator, marker::PhantomData, ops::{Index, IndexMut}};
3
4// Todo : introduce a new type
5pub type SlotVec<T> = GenVec<T>;
6pub type SlotID<T> = GenID<T>;
7
8pub type Generation = u32;
9
10pub type GenVec<T> = GenVecOf<T,Generation>;
11pub type GenID<T>  = GenIDOf<T,Generation>;
12
13pub trait IGeneration             : Eq + Hash + Ord + Increase + Decrease + OverflowBehavior + Debug + MaxValue + MinValue + Copy {}
14impl<T> IGeneration for T where T: Eq + Hash + Ord + Increase + Decrease + OverflowBehavior + Debug + MaxValue + MinValue + Copy {}
15
16#[cfg_attr(feature = "hexga_io", derive(Save, Load))]
17#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
18#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
19pub enum SlotValue<T>
20{
21    Used(T),
22    // Next free
23    Free(usize),
24}
25impl<T> SlotValue<T>
26{
27    pub fn get(&self) -> Option<&T> { if let Self::Used(v) = self { Some(v) } else { None }}
28    pub fn get_mut(&mut self) -> Option<&mut T> { if let Self::Used(v) = self { Some(v) } else { None }}
29
30    pub fn take_and_free(&mut self, free_index: usize) -> T {
31        match std::mem::replace(self, SlotValue::Free(free_index)) {
32            SlotValue::Used(value) => value,
33            SlotValue::Free(_) => panic!("Slot was already free"),
34        }
35    }
36
37    pub fn is_free(&self) -> bool { matches!(self, Self::Free(_))}
38    pub fn is_used(&self) -> bool { matches!(self, Self::Used(_))}
39}
40
41#[cfg_attr(feature = "hexga_io", derive(Save, Load))]
42#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
43#[derive(Clone, Debug, PartialEq, Eq, Hash)]
44pub struct Slot<T,Gen:IGeneration=Generation>
45{
46    value      : SlotValue<T>,
47    #[cfg_attr(feature = "serde", serde(rename = "gen"))]
48    generation : Gen,
49}
50impl <T,Gen:IGeneration> Slot<T,Gen>
51{
52    pub fn new(value : SlotValue<T>, generation : Gen) -> Self { Self { value, generation }}
53    pub fn generation(&self) -> Gen { self.generation }
54
55    pub fn have_value(&self) -> bool { self.value().is_some() }
56
57    pub fn value(&self) -> Option<&T> { self.value.get() }
58    pub fn value_mut(&mut self) -> Option<&mut T> { self.value.get_mut() }
59
60    pub fn get_id(&self, idx : usize) -> GenIDOf<T,Gen> { GenIDOf::new(idx, self.generation) }
61
62    pub fn generation_increase(&mut self) -> bool { if self.can_generation_increase() { self.generation.increase(); true } else { false } }
63    pub fn can_generation_increase(&self) -> bool { self.generation.can_increase() }
64
65    pub fn generation_decrease(&mut self) -> bool { if self.can_generation_decrease() { self.generation.decrease(); true } else { false } }
66    pub fn can_generation_decrease(&self) -> bool { self.generation.can_decrease() }
67
68    pub fn is_generation_saturated(&self) -> bool { !self.can_generation_increase() }
69}
70
71#[cfg_attr(feature = "hexga_io", derive(Save, Load))]
72#[derive(Debug, Clone, Eq)]
73pub struct GenVecOf<T,Gen:IGeneration=Generation>
74{
75    slot  : Vec<Slot<T,Gen>>,
76    head  : usize,
77    len   : usize,
78}
79
80impl<T, Gen:IGeneration> Hash for GenVecOf<T,Gen> where T: Hash
81{
82    fn hash<H: Hasher>(&self, state: &mut H)
83    {
84        self.len.hash(state);
85
86        if !Gen::OVERFLOW_BEHAVIOR.is_wrapping()
87        {
88            self.slot.hash(state);
89            self.head.hash(state);
90        }else
91        {
92            for (id, value) in self.iter()
93            {
94                id.hash(state);
95                value.hash(state);
96            }
97        }
98    }
99}
100
101impl<T, Gen:IGeneration> PartialEq for GenVecOf<T,Gen> where T: PartialEq
102{
103    fn eq(&self, other: &Self) -> bool
104    {
105        if !Gen::OVERFLOW_BEHAVIOR.is_wrapping()
106        {
107            self.len == other.len && self.slot == other.slot && self.head == other.head
108        }else
109        {
110            /*
111                We can't know if the gen vec is new or if the gen vec just wrapped arround.
112
113                Those two are equal: (Assuming Gen::MIN value is 0)
114                A: GenVecOf { slot: [Slot { value: Free(18446744073709551615), generation: 0 }], head: 0, len: 0 }
115                B: GenVecOf { slot: [], head: 18446744073709551615, len: 0 }
116
117                Both can represent unused wrapped gen vec.
118
119                doing :
120
121                let id = B.insert(10);
122                B.rollback_insert(id);
123
124                will put A in the same equal state/representation as B.
125
126
127                But these 2 are different, because that generation was already used.
128
129                X: GenVecOf { slot: [Slot { value: Free(18446744073709551615), generation: 1 }], head: 0, len: 0 }
130                Y: GenVecOf { slot: [], head: 18446744073709551615, len: 0 }
131            */
132
133            if self.len != other.len { return false; }
134            if self.head == other.head { return self.slot == other.slot; }
135            if !(self.head.is_max_value() ^ other.head.is_max_value()) { return false; }
136
137            if self.head.is_max_value()
138            {
139                if self.slot.len() + 1 != other.slot.len() { return false; }
140                let mid = other.head;
141                debug_assert!(!mid.is_max_value());
142
143                let slot = other.get_slot_index(mid).unwrap();
144                let SlotValue::Free(f) = slot.value else { return false; };
145                if !f.is_max_value() || !slot.generation().is_min_value() { return false; }
146
147                let self_left = &self.slot[0..mid];
148                let self_right = &self.slot[mid..];
149
150                let other_left = &other.slot[0..mid];
151                let other_right = &other.slot[mid+1..];
152
153                self_left == other_left && self_right == other_right
154            }else if other.head.is_max_value()
155            {
156                if other.slot.len() + 1 != self.slot.len() { return false; }
157                let mid = self.head;
158                debug_assert!(!mid.is_max_value());
159
160                let slot = self.get_slot_index(mid).unwrap();
161                let SlotValue::Free(f) = slot.value else { return false; };
162                if !f.is_max_value() || !slot.generation().is_min_value() { return false; }
163
164                let other_left = &other.slot[0..mid];
165                let other_right = &other.slot[mid..];
166
167                let self_left = &self.slot[0..mid];
168                let self_right = &self.slot[mid+1..];
169
170                other_left == self_left && other_right == self_right
171            }else
172            {
173                unreachable!()
174            }
175        }
176    }
177}
178
179#[cfg(feature = "serde")]
180impl<T, Gen:IGeneration> Serialize for GenVecOf<T,Gen> where Slot<T, Gen> : Serialize {
181    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> where S: Serializer,
182    {
183        let mut state = serializer.serialize_struct("GenVec", 2)?;
184        state.serialize_field("slot", &self.slot)?;
185        // need to be in the same order on all machine for determinist
186        state.serialize_field("free", &self.head)?;
187        state.end()
188    }
189}
190
191
192impl<T, Gen:IGeneration> GenVecOf<T,Gen>
193{
194    pub(crate) fn new_and_check_invariant(slot : Vec<Slot<T, Gen>>, head : usize) -> Result<Self, String>
195    {
196        let len = slot.iter().filter(|s| s.have_value()).count();
197
198        if slot.len() == usize::MAX
199        {
200            return Err("GenVec : the last usize value is used for null in a GenVec and cannot be used".to_owned());
201        }
202
203        let mut nb_use = len;
204        let mut cur_head = head;
205
206        while nb_use != 0
207        {
208            let Some(next_slot) = slot.get(cur_head) else { return Err(format!("GenVec : slot {:?} is out of range", cur_head)); };
209            let SlotValue::Free(f) = next_slot.value else { return Err(format!("GenVec : slot {:?} was not free", cur_head)); };
210            if f == usize::MAX { return Err(format!("GenVec : invalid free head {:?} at {:?}", f, cur_head));}
211            cur_head = f;
212            nb_use -= 1;
213        }
214
215        Ok(Self{ slot, head, len})
216    }
217}
218
219
220#[cfg(feature = "serde")]
221impl<'de,T, Gen> Deserialize<'de> for GenVecOf<T, Gen>
222where
223    Gen: IGeneration + Deserialize<'de>,
224    Slot<T, Gen>: Deserialize<'de>,
225{
226    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
227    where
228        D: serde::Deserializer<'de>,
229    {
230        use serde::de::{self, MapAccess, Visitor};
231        use std::fmt;
232
233        struct GenVecVisitor<T, Gen> {
234            marker: std::marker::PhantomData<(T, Gen)>,
235        }
236
237        impl<'de, T, Gen> Visitor<'de> for GenVecVisitor<T, Gen>
238        where
239            Gen: IGeneration + Deserialize<'de>,
240            Slot<T, Gen>: Deserialize<'de>,
241        {
242            type Value = GenVecOf<T, Gen>;
243
244            fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
245                formatter.write_str("a struct representing GenVec")
246            }
247
248            fn visit_map<A>(self, mut map: A) -> Result<Self::Value, A::Error>
249            where
250                A: MapAccess<'de>,
251            {
252                let mut values : Option<Vec<Slot<T, Gen>>> = None;
253                let mut free_index : Option<usize> = None;
254
255                while let Some(key) = map.next_key::<&'de str>()?
256                {
257                    match key
258                    {
259                        "slot" => {
260                            if values.is_some() {
261                                return Err(de::Error::duplicate_field("slot"));
262                            }
263                            values = Some(map.next_value()?);
264                        }
265                        "free" => {
266                            if free_index.is_some() {
267                                return Err(de::Error::duplicate_field("free"));
268                            }
269                            free_index = Some(map.next_value()?);
270                        }
271                        _ => {
272                            return Err(de::Error::unknown_field(
273                                &key,
274                                &["slot", "free"],
275                            ));
276                        }
277                    }
278                }
279
280                let slot = values.ok_or_else(|| de::Error::missing_field("slot"))?;
281                let free = free_index.ok_or_else(|| de::Error::missing_field("free"))?;
282                GenVecOf::<T,Gen>::new_and_check_invariant(slot, free).map_err(|e| de::Error::custom(e))
283            }
284        }
285
286        const FIELDS: &[&str] = &["slot", "free"];
287        deserializer.deserialize_struct(
288            "GenVec",
289            FIELDS,
290            GenVecVisitor {
291                marker: std::marker::PhantomData,
292            },
293        )
294    }
295}
296
297#[cfg_attr(feature = "hexga_io", derive(Save, Load))]
298pub struct GenIDOf<T,Gen:IGeneration>
299{
300    index      : usize,
301    generation : Gen,
302    value      : PhantomData<T>,
303}
304
305impl<T,Gen:IGeneration> Default for GenIDOf<T,Gen>
306{
307    fn default() -> Self { Self::NULL }
308}
309
310#[cfg(feature = "serde")]
311impl<T, Gen:IGeneration> Serialize for GenIDOf<T,Gen> where T: Serialize, Gen : Serialize {
312    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> where S: Serializer,
313    {
314        if self.index.is_max_value()
315        {
316            Some((self.index, self.generation))
317        }else
318        {
319            None
320        }.serialize(serializer)
321    }
322}
323
324#[cfg(feature = "serde")]
325impl<'de, T, Gen:IGeneration> Deserialize<'de> for GenIDOf<T,Gen> where T: Deserialize<'de>, Gen : Deserialize<'de> {
326    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error> where D: Deserializer<'de>,
327    {
328        match Option::deserialize(deserializer)?
329        {
330            Some((index, generation)) => Ok(Self::new(index, generation)),
331            None => Ok(Self::new(usize::MAX, Gen::MIN)),
332        }
333    }
334}
335
336impl<T,Gen:IGeneration> Clone for GenIDOf<T,Gen>{ fn clone(&self) -> Self { Self { index: self.index.clone(), generation: self.generation.clone(), value: PhantomData } } }
337impl<T,Gen:IGeneration> Copy for GenIDOf<T,Gen> {}
338
339impl<T,Gen:IGeneration> PartialEq for GenIDOf<T,Gen> { fn eq(&self, other: &Self) -> bool { self.index == other.index && self.generation == other.generation } }
340impl<T,Gen:IGeneration> Eq for GenIDOf<T,Gen> {}
341
342impl<T,Gen:IGeneration> Hash for GenIDOf<T,Gen> { fn hash<H: Hasher>(&self, state: &mut H) { self.index.hash(state); self.generation.hash(state); } }
343
344impl<T,Gen:IGeneration> Ord for GenIDOf<T,Gen> { fn cmp(&self, other: &Self) -> std::cmp::Ordering { (self.index, self.generation).cmp(&(other.index, other.generation)) } }
345impl<T,Gen:IGeneration> PartialOrd for GenIDOf<T,Gen> { fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> { Some(self.cmp(&other)) } }
346
347impl<T,Gen:IGeneration> Debug for GenIDOf<T,Gen> { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!(f, "{:?}#{:?}", self.index, self.generation) } }
348
349impl<T,Gen:IGeneration> GenIDOf<T,Gen>
350{
351    pub const fn new(index : usize, generation : Gen) -> Self { Self { index, generation, value: PhantomData }}
352
353    pub const fn index(self) -> usize { self.index }
354    pub const fn generation(self) -> Gen { self.generation }
355
356    pub fn is_null(self) -> bool { self == Self::NULL }
357    pub fn is_not_null(self) -> bool { self != Self::NULL }
358
359    pub fn get(self, gen_vec : &GenVecOf<T,Gen>) -> Option<&T> { gen_vec.get(self) }
360    pub fn get_mut(self, gen_vec : &mut GenVecOf<T,Gen>) -> Option<&mut T> { gen_vec.get_mut(self) }
361
362    pub fn remove(self, gen_vec : &mut GenVecOf<T,Gen>) -> Option<T> { gen_vec.remove(self) }
363    pub fn exist(self, gen_vec : &GenVecOf<T,Gen>) -> bool { self.get(gen_vec).is_some() }
364
365    pub const NULL : Self = GenIDOf { index: usize::MAX, generation: Gen::MIN, value: PhantomData };
366}
367impl<T,Gen:IGeneration> From<(usize,Gen)> for GenIDOf<T,Gen>
368{
369    fn from((index,generation): (usize,Gen)) -> Self {
370        Self::new(index, generation)
371    }
372}
373impl<T,Gen:IGeneration> Into<(usize,Gen)> for GenIDOf<T,Gen>
374{
375    fn into(self) -> (usize,Gen) {
376        (self.index, self.generation)
377    }
378}
379
380impl<T,Gen:IGeneration> Default for GenVecOf<T,Gen>
381{
382    fn default() -> Self { Self::new() }
383}
384
385impl<T,Gen:IGeneration> GenVecOf<T,Gen>
386{
387    pub const fn new() -> Self { Self { slot: Vec::new(), head : usize::MAX, len : 0 }}
388    pub fn with_capacity(capacity : usize) -> Self { Self { slot: Vec::with_capacity(capacity), head : usize::MAX, len : 0 }}
389
390    pub fn capacity(&self) -> usize { self.slot.capacity() }
391    pub fn shrink_to_fit(mut self) { self.slot.shrink_to_fit(); }
392
393
394    /// Clear the [GenVec] but don't invalidate all previous [GenID].
395    pub fn clear(&mut self)
396    {
397        self.head = usize::MAX;
398        self.len = 0;
399        self.slot.clear();
400    }
401
402    /// Clear the [GenVec] and also invalidate all previous [GenID].
403    pub fn remove_all(&mut self)
404    {
405        for (idx, v) in self.slot.iter_mut().enumerate()
406        {
407            if v.have_value()
408            {
409                if v.generation_increase()
410                {
411                    v.value = SlotValue::Free(self.head);
412                    self.head = idx;
413                }else
414                {
415                    v.value = SlotValue::Free(usize::MAX);
416                }
417            }
418        }
419        self.len = 0;
420    }
421
422    pub fn rollback_insert(&mut self, id : GenIDOf<T,Gen>) -> Result<T,()>
423    {
424        let idx = id.index;
425        let head = self.head;
426
427        let slot_len = self.slot.len();
428
429        let Some(slot) = self.get_slot_index_mut(idx) else { return Err(()); };
430        if slot.value.is_free() { return Err(()); }
431
432        if head.is_max_value()
433        {
434            if idx + 1 != slot_len { return Err(()); }
435        }
436
437        let can_not_decrease = !slot.can_generation_decrease();
438        let val = slot.value.take_and_free(head);
439        self.len -= 1;
440
441        if head.is_max_value() && can_not_decrease
442        {
443            self.slot.pop().ok_or(())?;
444        }else
445        {
446            self.head = idx;
447        }
448
449        Ok(val)
450    }
451    pub fn insert(&mut self, value : T) ->  GenIDOf<T,Gen>
452    {
453        self.len += 1;
454
455        if self.head == usize::MAX
456        {
457            let index = self.slot.len();
458
459            // The last index is used for the null() key
460            assert!(index != usize::MAX, "How you didn't run out of memory before ?");
461
462            let generation = Gen::MIN;
463            self.slot.push(Slot { value: SlotValue::Used(value), generation });
464            return GenIDOf::new(index, generation);
465        }
466
467        let SlotValue::Free(next_free_idx) = self.slot[self.head].value else { unreachable!(); };
468        let head = self.head;
469        self.head = next_free_idx;
470        self.slot[head].value = SlotValue::Used(value);
471        return GenIDOf::new(head, self.slot[head].generation);
472    }
473
474    #[inline(always)]
475    pub fn get_slot_index(&self, idx : usize) -> Option<&Slot<T,Gen>> { self.slot.get(idx) }
476    #[inline(always)]
477    pub(crate) fn get_slot_index_mut(&mut self, idx : usize) -> Option<&mut Slot<T,Gen>> { self.slot.get_mut(idx) }
478
479    #[inline(always)]
480    pub fn get_index(&self, idx : usize) -> Option<&T> { self.get_slot_index(idx).and_then(|s| s.value()) }
481    #[inline(always)]
482    pub fn get_index_mut(&mut self, idx : usize) -> Option<&mut T> { self.get_slot_index_mut(idx).and_then(|s| s.value_mut()) }
483
484    #[inline(always)]
485    pub fn get_slot(&self, id : GenIDOf<T,Gen>) -> Option<&Slot<T,Gen>> { self.get_slot_index(id.index).filter(|v| v.generation() == id.generation()) }
486    #[inline(always)]
487    pub(crate) fn get_slot_mut(&mut self, id : GenIDOf<T,Gen>) -> Option<&mut Slot<T,Gen>> { self.get_slot_index_mut(id.index).filter(|v| v.generation() == id.generation()) }
488
489    #[inline(always)]
490    pub fn get(&self, id : GenIDOf<T,Gen>) -> Option<&T> { self.get_slot(id).and_then(|v| v.value()) }
491    #[inline(always)]
492    pub fn get_mut(&mut self, id : GenIDOf<T,Gen>) -> Option<&mut T> { self.get_slot_mut(id).and_then(|v| v.value_mut()) }
493
494    /// Return a valid [GenID] to the current index or return null if the idx is outside the range
495    pub fn get_id(&self, idx : usize) -> GenIDOf<T, Gen>
496    {
497        self.get_slot_index(idx).map(|v| v.get_id(idx)).unwrap_or(GenIDOf::NULL)
498    }
499
500    /// The operation that once done just after an [Self::remove_index], put this data structure in the same state as before
501    pub fn rollback_remove_index(&mut self, idx : usize, value : T) -> Result<(), ()>
502    {
503        let mut head = self.head;
504        let slot = self.get_slot_index_mut(idx).ok_or(())?;
505        let SlotValue::Free(f) = slot.value else { return Err(()); };
506        let free = f;
507
508        if f.is_non_max_value()
509        {
510            if head != idx { return Err(()); }
511            head = free;
512            if !slot.generation_decrease() { return Err(()); }
513        }else
514        {
515            // Slot don't have a next free slot
516            if head == idx
517            {
518                head = usize::MAX;
519                if !slot.generation_decrease() { return Err(()); }
520            }else if !slot.is_generation_saturated()
521            {
522                return Err(());
523            }
524        }
525
526        slot.value = SlotValue::Used(value);
527
528        self.head = head;
529        self.len += 1;
530
531        Ok(())
532    }
533    pub fn remove_index(&mut self, idx : usize) -> Option<T>
534    {
535        let head = self.head;
536
537        let Some(slot) = self.get_slot_index_mut(idx) else { return None; };
538        if slot.value.is_free() { return None; }
539
540        let val = slot.value.take_and_free(head);
541
542        if slot.generation_increase()
543        {
544            self.head = idx;
545        }else
546        {
547            slot.value = SlotValue::Free(usize::MAX);
548        }
549        self.len -= 1;
550
551        Some(val)
552    }
553
554    pub fn rollback_remove(&mut self, id : GenIDOf<T,Gen>, value : T) -> Result<(), ()>
555    {
556        // Todo : missing some check to see if the last operation removal was done with id
557        self.rollback_remove_index(id.index, value)
558    }
559    pub fn remove(&mut self, id : GenIDOf<T,Gen>) -> Option<T>
560    {
561        if self.get(id).is_none() { return None; }
562        self.remove_index(id.index)
563    }
564
565    /*
566    pub(crate) fn iter_slot(&self) -> impl Iterator<Item = &Slot<T,Gen>> { self.slot.iter() }
567    pub(crate) fn iter_slot_mut(&mut self) -> impl Iterator<Item = &mut Slot<T,Gen>> { self.slot.iter_mut() }
568
569    pub(crate) fn iter_slot_with_value(&self) -> impl Iterator<Item = &Slot<T,Gen>> { self.iter_slot().filter(|e| e.have_value()) }
570    pub(crate) fn iter_slot_with_value_mut(&mut self) -> impl Iterator<Item = &mut Slot<T,Gen>> { self.iter_slot_mut().filter(|e| e.have_value()) }
571    */
572
573    pub fn iter(&self) -> Iter<'_, T, Gen> { self.into_iter() }
574    pub fn iter_mut(&mut self) -> IterMut<'_, T, Gen> { self.into_iter() }
575
576    pub fn ids(&self) -> impl Iterator<Item = GenIDOf<T,Gen>> { self.into_iter().map(|(id, _val)| id) }
577    pub fn values(&self) -> impl Iterator<Item = &T> { self.iter().map(|(_,val)| val) }
578
579    pub fn into_ids(self) -> impl Iterator<Item = GenIDOf<T,Gen>> { self.into_iter().map(|(id, _val)| id) }
580    pub fn into_values(self) -> impl Iterator<Item = T> { self.into_iter().map(|(_id, val)| val) }
581
582    /// The correct way to iterate over all slot index.
583    /// Use this instead of `0..gen_vec.len()`.
584    pub fn iter_index(&self) -> impl Iterator<Item = usize> + use<T, Gen> { 0..self.slot.len() }
585
586
587    pub fn retain<F>(&mut self, mut f: F) where F: FnMut(&T) -> bool
588    {
589        self.retain_mut(|elem| f(elem));
590    }
591
592    pub fn retain_mut<F>(&mut self, mut f: F) where F: FnMut(&mut T) -> bool
593    {
594        for idx in self.iter_index()
595        {
596            let Some(v) = self.get_index_mut(idx) else { continue; };
597            if !f(v)
598            {
599                self.remove_index(idx);
600            }
601        }
602    }
603}
604
605impl<T, Gen:IGeneration> Index<GenIDOf<T,Gen>> for GenVecOf<T,Gen>
606{
607    type Output=T;
608    fn index(&self, index: GenIDOf<T,Gen>) -> &Self::Output { self.get_or_panic(index) }
609}
610impl<T, Gen:IGeneration> IndexMut<GenIDOf<T,Gen>> for GenVecOf<T,Gen>
611{
612    fn index_mut(&mut self, index: GenIDOf<T,Gen>) -> &mut Self::Output { self.get_mut_or_panic(index) }
613}
614
615impl<T, Gen:IGeneration> Index<usize> for GenVecOf<T,Gen>
616{
617    type Output=T;
618    fn index(&self, index: usize) -> &Self::Output { self.get_index(index).unwrap() }
619}
620impl<T, Gen:IGeneration> IndexMut<usize> for GenVecOf<T,Gen>
621{
622    fn index_mut(&mut self, index: usize) -> &mut Self::Output { self.get_index_mut(index).unwrap() }
623}
624
625impl<T, Gen:IGeneration> FromIterator<T> for GenVecOf<T, Gen>
626{
627    fn from_iter<K: IntoIterator<Item = T>>(iter: K) -> Self {
628        let slots : Vec<Slot<T,Gen>> = iter.into_iter().map(|v| Slot::new(SlotValue::Used(v), Gen::MIN)).collect();
629        let len = slots.len();
630        Self{ slot: slots, head: usize::MAX, len }
631    }
632}
633
634impl<T, Gen: IGeneration> IntoIterator for GenVecOf<T, Gen> {
635    type Item = (GenIDOf<T, Gen>, T);
636    type IntoIter = IntoIter<T, Gen>;
637
638    fn into_iter(self) -> Self::IntoIter {
639        IntoIter
640        {
641            iter: self.slot.into_iter().enumerate(),
642            len_remaining: self.len,
643        }
644    }
645}
646
647#[derive(Clone, Debug)]
648pub struct IntoIter<T, Gen: IGeneration>
649{
650    iter: std::iter::Enumerate<std::vec::IntoIter<Slot<T, Gen>>>,
651    len_remaining : usize,
652}
653
654impl<T, Gen: IGeneration> Iterator for IntoIter<T, Gen> {
655    type Item = (GenIDOf<T, Gen>, T);
656
657    fn next(&mut self) -> Option<Self::Item>
658    {
659        while let Some((idx, slot)) = self.iter.next()
660        {
661            if let SlotValue::Used(value) = slot.value
662            {
663                self.len_remaining -= 1;
664                return Some((GenIDOf::new(idx, slot.generation), value));
665            }
666        }
667        None
668    }
669
670    fn size_hint(&self) -> (usize, Option<usize>) { (self.len_remaining, Some(self.len_remaining)) }
671}
672impl<T, Gen: IGeneration> FusedIterator for IntoIter<T, Gen> {}
673impl<T, Gen: IGeneration> ExactSizeIterator for IntoIter<T, Gen> { fn len(&self) -> usize { self.len_remaining } }
674
675impl<'a, T, Gen: IGeneration> IntoIterator for &'a GenVecOf<T, Gen> {
676    type Item = (GenIDOf<T, Gen>, &'a T);
677    type IntoIter = Iter<'a, T, Gen>;
678
679    fn into_iter(self) -> Self::IntoIter {
680        Iter {
681            iter: self.slot.iter().enumerate(),
682            len_remaining : self.len,
683        }
684    }
685}
686
687#[derive(Clone, Debug)]
688pub struct Iter<'a, T, Gen: IGeneration>
689{
690    iter: std::iter::Enumerate<std::slice::Iter<'a, Slot<T, Gen>>>,
691    len_remaining : usize,
692}
693
694impl<'a, T, Gen: IGeneration> Iterator for Iter<'a, T, Gen> {
695    type Item = (GenIDOf<T, Gen>, &'a T);
696
697    fn next(&mut self) -> Option<Self::Item> {
698        while let Some((idx, slot)) = self.iter.next() {
699            if let Some(value) = slot.value() {
700                self.len_remaining -= 1;
701                return Some((GenIDOf::new(idx, slot.generation), value));
702            }
703        }
704        None
705    }
706
707    fn size_hint(&self) -> (usize, Option<usize>) { (self.len_remaining, Some(self.len_remaining)) }
708}
709impl<'a, T, Gen: IGeneration> FusedIterator for Iter<'a, T, Gen> {}
710impl<'a, T, Gen: IGeneration> ExactSizeIterator for Iter<'a, T, Gen> { fn len(&self) -> usize { self.len_remaining } }
711
712
713
714impl<'a, T, Gen: IGeneration> IntoIterator for &'a mut GenVecOf<T, Gen>
715{
716    type Item = (GenIDOf<T, Gen>, &'a mut T);
717    type IntoIter = IterMut<'a, T, Gen>;
718
719    fn into_iter(self) -> Self::IntoIter {
720        IterMut {
721            iter: self.slot.iter_mut().enumerate(),
722            len_remaining : self.len,
723        }
724    }
725}
726
727#[derive(Debug)]
728pub struct IterMut<'a, T, Gen: IGeneration>
729{
730    iter: std::iter::Enumerate<std::slice::IterMut<'a, Slot<T, Gen>>>,
731    len_remaining : usize,
732}
733
734impl<'a, T, Gen: IGeneration> Iterator for IterMut<'a, T, Gen> {
735    type Item = (GenIDOf<T, Gen>, &'a mut T);
736
737    fn next(&mut self) -> Option<Self::Item> {
738        while let Some((idx, slot)) = self.iter.next() {
739            let generation = slot.generation();
740            if let Some(value) = slot.value_mut() {
741                self.len_remaining -= 1;
742                return Some((GenIDOf::new(idx, generation), value));
743            }
744        }
745        None
746    }
747
748    fn size_hint(&self) -> (usize, Option<usize>) { (self.len_remaining, Some(self.len_remaining)) }
749}
750impl<'a, T, Gen: IGeneration> FusedIterator for IterMut<'a, T, Gen> {}
751impl<'a, T, Gen: IGeneration> ExactSizeIterator for IterMut<'a, T, Gen> { fn len(&self) -> usize { self.len_remaining } }
752
753
754impl<T,Gen:IGeneration> Length for GenVecOf<T,Gen> { #[inline(always)] fn len(&self) -> usize { self.len } }
755impl<T,Gen:IGeneration> Capacity for GenVecOf<T,Gen>
756{
757    type Param=();
758
759    #[inline(always)]
760    fn capacity(&self) -> usize { self.slot.capacity() }
761
762    #[inline(always)]
763    fn with_capacity_and_param(capacity: usize, _ : Self::Param) -> Self { Self::with_capacity(capacity) }
764
765    #[inline(always)]
766    fn reserve(&mut self, additional: usize) { self.slot.reserve(additional); }
767    #[inline(always)]
768    fn reserve_exact(&mut self, additional: usize) { self.slot.reserve_exact(additional); }
769
770    #[inline(always)]
771    fn try_reserve(&mut self, additional: usize) -> Result<(), std::collections::TryReserveError> { self.slot.try_reserve(additional) }
772    #[inline(always)]
773    fn try_reserve_exact(&mut self, additional: usize) -> Result<(), std::collections::TryReserveError> { self.slot.try_reserve_exact(additional) }
774}
775impl<T,Gen:IGeneration> Clearable for GenVecOf<T,Gen> { #[inline(always)] fn clear(&mut self) { self.clear(); } }
776
777impl<T,Gen:IGeneration> Get<usize> for GenVecOf<T,Gen>
778{
779    type Output = <Self as Index<usize>>::Output;
780    #[inline(always)]
781    fn try_get(&self, idx : usize) -> Result<&Self::Output, ()> { self.get_index(idx).ok_or_void() }
782    #[inline(always)]
783    fn get(&self, idx : usize) -> Option<&Self::Output> { self.get_index(idx) }
784}
785impl<T,Gen:IGeneration> Get<GenIDOf<T,Gen>> for GenVecOf<T,Gen>
786{
787    type Output = <Self as Index<GenIDOf<T,Gen>>>::Output;
788    #[inline(always)]
789    fn try_get(&self, idx : GenIDOf<T,Gen>) -> Result<&Self::Output, ()> { self.get(idx).ok_or_void() }
790    #[inline(always)]
791    fn get(&self, idx : GenIDOf<T,Gen>) -> Option<&Self::Output> { self.get(idx) }
792}
793
794impl<T,Gen:IGeneration> GetMut<usize> for GenVecOf<T,Gen>
795{
796    #[inline(always)]
797    fn try_get_mut(&mut self, idx : usize) -> Result<&mut Self::Output, ()> { self.get_index_mut(idx).ok_or_void() }
798    #[inline(always)]
799    fn get_mut(&mut self, idx : usize) -> Option<&mut Self::Output> { self.get_index_mut(idx) }
800}
801
802impl<T,Gen:IGeneration> GetManyMut<usize> for GenVecOf<T,Gen>
803{
804    #[inline(always)]
805    fn try_get_many_mut<const N: usize>(&mut self, indices: [usize; N]) -> Result<[&mut Self::Output;N], ()>
806    {
807        // Use try_map https://doc.rust-lang.org/std/primitive.array.html#method.try_map when #stabilized
808        match self.slot.try_get_many_mut(indices).map(|slots| slots.map(|v| v.value_mut()))
809        {
810            Ok(values) => if values.iter().any(|v| v.is_none()) { Err(()) } else { Ok(values.map(|v| v.unwrap())) },
811            Err(()) => Err(()),
812        }
813    }
814
815    #[inline(always)]
816    #[track_caller]
817    unsafe fn get_many_unchecked_mut<const N: usize>(&mut self, indices: [usize; N]) -> [&mut Self::Output;N] {
818        // Use try_map https://doc.rust-lang.org/std/primitive.array.html#method.try_map when #stabilized
819        unsafe { self.slot.get_many_unchecked_mut(indices).map(|v| v.value_mut().unwrap()) }
820    }
821}
822impl<T,Gen:IGeneration> GetMut<GenIDOf<T,Gen>> for GenVecOf<T,Gen>
823{
824    #[inline(always)]
825    fn try_get_mut(&mut self, idx : GenIDOf<T,Gen>) -> Result<&mut Self::Output, ()> { self.get_mut(idx).ok_or_void() }
826    #[inline(always)]
827    fn get_mut(&mut self, idx : GenIDOf<T,Gen>) -> Option<&mut Self::Output> { self.get_mut(idx) }
828}
829
830impl<T,Gen:IGeneration> GetManyMut<GenIDOf<T,Gen>> for GenVecOf<T,Gen>
831{
832    #[inline(always)]
833    fn try_get_many_mut<const N: usize>(&mut self, indices: [GenIDOf<T,Gen>; N]) -> Result<[&mut Self::Output;N], ()>
834    {
835        // Todo: use O(N) complexity to check the overlaping
836        // Check SlotMap imply that put tmp Free slot in the current indices to
837
838        // Use try_map https://doc.rust-lang.org/std/primitive.array.html#method.try_map when #stabilized
839        match self.slot.try_get_many_mut(indices.map(|i| i.index))
840        {
841            Ok(values) => if values.iter().enumerate().any(|(idx,v)| !v.have_value() || v.generation() != indices[idx].generation)
842            { Err(()) } else { Ok(values.map(|v| v.value_mut().unwrap())) },
843            Err(_) => Err(()),
844        }
845    }
846}
847
848
849
850impl<T,Gen:IGeneration> GenVecOf<T,Gen>
851{
852    /// Moves all the elements of `other` into `self`, leaving `other` empty by clearing it (don't invalidate all previous [GenID]).
853    pub fn append(&mut self, other: &mut GenVecOf<T,Gen>) -> impl GenIDUpdater<T,Gen> + use<T,Gen> where T: GenIDUpdatable<T,Gen>
854    {
855        let capacity = other.len();
856        let mut h = HashMap::with_capacity(capacity);
857
858        for (idx, slot) in other.slot.iter_mut().enumerate().filter(|(_,s)| s.have_value())
859        {
860            let val = slot.value.take_and_free(usize::MAX);
861            let old_id = slot.get_id(idx);
862            let new_id = self.insert(val);
863            h.insert(old_id, new_id);
864        }
865        other.clear();
866
867        for new_id in h.values()
868        {
869            unsafe { self.get_unchecked_mut(*new_id) }.update_id(&h);
870        }
871        h
872    }
873}
874
875impl<A,Gen:IGeneration> Extend<A> for GenVecOf<A,Gen>
876{
877    fn extend<T: IntoIterator<Item = A>>(&mut self, iter: T)
878    {
879        for val in iter.into_iter()
880        {
881            self.insert(val);
882        }
883    }
884}
885
886pub trait GenIDUpdater<T,Gen:IGeneration>
887{
888    fn update(&self, dest : &mut GenIDOf<T,Gen>);
889}
890impl<T,Gen:IGeneration> GenIDUpdater<T,Gen> for HashMap<GenIDOf<T,Gen>,GenIDOf<T,Gen>>
891{
892    fn update(&self, dest : &mut GenIDOf<T,Gen>) {
893        debug_assert!(dest.is_null() || self.get(&dest).is_some());
894        *dest = self.get(&dest).copied().unwrap_or(GenIDOf::NULL);
895    }
896}
897
898
899pub trait GenIDUpdatable<T=Self,Gen:IGeneration=Generation> : Sized
900{
901    fn update_id<U : GenIDUpdater<T,Gen>>(&mut self, updater : &U);
902}
903impl<T,Gen:IGeneration> GenIDUpdatable<T,Gen> for GenIDOf<T,Gen>
904{
905    fn update_id<U : GenIDUpdater<T,Gen>>(&mut self, updater : &U) {
906        updater.update(self);
907    }
908}
909
910impl<A,Gen:IGeneration> Extend<(GenIDOf<A,Gen>, A)> for GenVecOf<A,Gen> where A : GenIDUpdatable<A,Gen>
911{
912    fn extend<T: IntoIterator<Item = (GenIDOf<A,Gen>, A)>>(&mut self, iter: T)
913    {
914        let it = iter.into_iter();
915        let mut h = HashMap::with_capacity(it.size_hint().0);
916
917        for (old_id, val) in it
918        {
919            let new_id = self.insert(val);
920            h.insert(old_id, new_id);
921        }
922
923        for new_id in h.values()
924        {
925            unsafe { self.get_unchecked_mut(*new_id) }.update_id(&h);
926        }
927    }
928}
929
930pub trait CollectToGenVecExtension<T,Gen:IGeneration=Generation> : Sized + IntoIterator<Item = T>
931{
932    fn to_genvec(self) -> GenVecOf<T,Generation>
933    {
934        GenVecOf::from_iter(self)
935    }
936}
937impl<I,T1> CollectToGenVecExtension<T1> for I where I : IntoIterator<Item = T1> {}
938
939/*
940pub trait CollectToGenVecWithIDExtension<T,Gen:IGeneration=Generation> : Sized + IntoIterator<Item = (GenIDOf<T,Gen>, T)>
941{
942    fn to_genvec(self) -> GenVecOf<T,Generation>
943    {
944        GenVecOf::from_iter(self)
945    }
946}
947impl<I,T> CollectToGenVecWithIDExtension<T> for I where I : IntoIterator<Item = (GenIDOf<T,Gen>, T)> {}
948
949impl<I,T> CollectToGenVecWithIndexExtension<T> for I where I : IntoIterator<Item = (usize, T)> {}
950*/
951
952#[allow(dead_code)]
953#[cfg(test)]
954mod tests
955{
956    use std::num::Wrapping;
957
958    use super::*;
959
960    #[derive(Debug, Clone, Copy)]
961    struct Cell
962    {
963        next : GenID<Cell>,
964        value : i32,
965    }
966
967    impl GenIDUpdatable for Cell
968    {
969        fn update_id<U : GenIDUpdater<Self,u32>>(&mut self, updater : &U) {
970            self.next.update_id(updater);
971        }
972    }
973
974    #[test]
975    fn extend_complexe_struct()
976    {
977        let mut src = GenVec::new();
978        let first = src.insert(Cell{ next: GenID::NULL, value: 1 });
979        src.insert(Cell{ next: first, value: 2 });
980
981        let mut dest = GenVec::new();
982        let first = dest.insert(Cell{ next: GenID::NULL, value: 3 });
983        dest.insert(Cell{ next: first, value: 4 });
984
985        src.extend(dest.into_iter());
986
987        let ids = src.iter().map(|(_,v)| v.value).collect::<std::collections::HashSet<_>>();
988        assert_eq!(ids.len(), 4);
989    }
990
991
992    #[test]
993    fn append_complexe_struct()
994    {
995        let mut src = GenVec::new();
996        let first = src.insert(Cell{ next: GenID::NULL, value: 1 });
997        src.insert(Cell{ next: first, value: 2 });
998
999        let mut dest = GenVec::new();
1000        let mut first = dest.insert(Cell{ next: GenID::NULL, value: 3 });
1001        let mut second = dest.insert(Cell{ next: first, value: 4 });
1002
1003        let updater = src.append(&mut dest);
1004
1005        assert_eq!(dest.len(), 0);
1006
1007        first.update_id(&updater);
1008        second.update_id(&updater);
1009
1010        assert_eq!(src[first].next, GenID::NULL);
1011        assert_eq!(src[first].value, 3);
1012        assert_eq!(src[second].next, first);
1013        assert_eq!(src[second].value, 4);
1014    }
1015
1016    #[test]
1017    fn extend_common_struct()
1018    {
1019        let mut g = [1,2,3].into_iter().collect::<GenVec<_>>();
1020        assert_eq!(g.len(), 3);
1021
1022        g.extend([4,5]);
1023        assert_eq!(g.len, 5);
1024    }
1025
1026    #[test]
1027    fn iter_size_hint_check()
1028    {
1029        let g = [1,2,3,4,5].into_iter().collect::<GenVec<_>>();
1030        let mut it = g.iter();
1031
1032        for i in (1..=5).rev()
1033        {
1034            assert_eq!(it.size_hint().0, i);
1035            assert_eq!(it.size_hint().1, Some(i));
1036            it.next();
1037        }
1038    }
1039
1040    #[test]
1041    fn iter_mut_size_hint_check()
1042    {
1043        let mut g = [1,2,3,4,5].into_iter().collect::<GenVec<_>>();
1044        let mut it = g.iter_mut();
1045
1046        for i in (1..=5).rev()
1047        {
1048            assert_eq!(it.size_hint().0, i);
1049            assert_eq!(it.size_hint().1, Some(i));
1050            it.next();
1051        }
1052    }
1053
1054    #[test]
1055    fn into_iter_mut_size_hint_check()
1056    {
1057        let g = [1,2,3,4,5].into_iter().collect::<GenVec<_>>();
1058        let mut it = g.into_iter();
1059
1060        for i in (1..=5).rev()
1061        {
1062            assert_eq!(it.size_hint().0, i);
1063            assert_eq!(it.size_hint().1, Some(i));
1064            it.next();
1065        }
1066    }
1067
1068    #[test]
1069    fn basic()
1070    {
1071        let mut g = GenVec::new();
1072        assert_eq!(g.len(), 0);
1073
1074        let a = g.insert(42);
1075        assert_eq!(g.len(), 1);
1076        assert_eq!(g[a], 42);
1077        assert_eq!(g.get(a), Some(&42));
1078
1079        let b = g.insert(43);
1080        assert_eq!(g.len(), 2);
1081        assert_eq!(g[b], 43);
1082        assert_eq!(g.get(b), Some(&43));
1083
1084        assert_eq!(g.remove(a).unwrap(), 42);
1085        assert_eq!(g.remove(a), None);
1086        assert_eq!(g.len(), 1);
1087
1088        assert_eq!(g.remove(b).unwrap(), 43);
1089        assert_eq!(g.len(), 0);
1090    }
1091
1092    #[test]
1093    fn into_iter()
1094    {
1095        assert_eq!(GenVec::<i32>::new().into_iter().next(), None);
1096
1097        let x = GenVec::from_iter([10,20,30]);
1098        assert_eq!(x.len(), 3);
1099
1100        assert_eq!(x[x.get_id(0)], 10);
1101        assert_eq!(x[x.get_id(1)], 20);
1102        assert_eq!(x[x.get_id(2)], 30);
1103
1104        assert_eq!(x.into_values().collect::<Vec<_>>(), vec![10, 20, 30]);
1105    }
1106
1107
1108    #[test]
1109    fn clear_check()
1110    {
1111        let mut v = GenVec::new();
1112        let a = v.insert(42);
1113
1114        assert_eq!(v.get(a), Some(&42));
1115        v.remove_all();
1116        assert_eq!(v.get(a), None);
1117    }
1118
1119    #[test]
1120    fn check_generation()
1121    {
1122        let mut v = GenVec::new();
1123        let a = v.insert(42);
1124        assert_eq!(v.get(a), Some(&42));
1125        assert_eq!(v.remove(a), Some(42));
1126        let b = v.insert(50);
1127        assert_eq!(v.get(b), Some(&50));
1128        assert_eq!(v.get(a), None);
1129        assert_ne!(a, b);
1130    }
1131
1132
1133    #[test]
1134    fn saturation()
1135    {
1136        let mut v = GenVecOf::<i32, u8>::new();
1137
1138        assert_eq!(v.len(), 0);
1139
1140        for i in 0..300
1141        {
1142            let a = v.insert(i);
1143            v.remove(a);
1144        }
1145
1146        assert_eq!(v.len(), 0);
1147        //dbg!(v);
1148    }
1149
1150    #[test]
1151    fn wrapping()
1152    {
1153        let mut v = GenVecOf::<i32, Wrapping<u8>>::new();
1154
1155        assert_eq!(v.len(), 0);
1156
1157        let first_key = v.insert(1000);
1158        v.remove(first_key);
1159
1160        let second_key = v.insert(2000);
1161        v.remove(second_key);
1162
1163        for i in 0..254
1164        {
1165            let a = v.insert(i);
1166            v.remove(a);
1167        }
1168
1169        let first_key_wrapped = v.insert(3000);
1170
1171        assert_eq!(v.len(), 1);
1172        assert_eq!(first_key_wrapped, first_key);
1173        assert_ne!(second_key, first_key);
1174
1175        // dbg!(first_key_wrapped);
1176        // dbg!(first_key);
1177        debug_assert_eq!(v.get(first_key_wrapped), Some(&3000));
1178        // the key was wrapped
1179        debug_assert_eq!(v.get(first_key), Some(&3000));
1180
1181        debug_assert_eq!(v.get(second_key), None);
1182    }
1183
1184    #[test]
1185    fn showcase()
1186    {
1187        let mut entities = GenVec::new();
1188        let enemy = entities.insert("zoombie");
1189
1190        assert_eq!(enemy.get(&entities), Some(&"zoombie"));
1191        assert_eq!(entities[enemy], "zoombie");
1192        assert!(entities.get(enemy).is_some());
1193
1194        entities.remove(enemy); // the key is no longer valid
1195        assert!(entities.get(enemy).is_none()); // the value don't exist
1196
1197        entities.insert("slime");
1198        entities.insert("skeleton");
1199
1200        for (id, entity) in entities
1201        {
1202            println!("{:?} => {}", id, entity)
1203        }
1204    }
1205
1206
1207    fn wrapping_about_to_wrap() -> GenVecOf::<i32, Wrapping<u8>>
1208    {
1209        let mut v = GenVecOf::<i32, Wrapping<u8>>::new();
1210
1211        for i in 0..255
1212        {
1213            let a = v.insert(i);
1214            v.remove(a);
1215        }
1216
1217        //dbg!(v);
1218        v
1219    }
1220
1221    fn non_wrapping_about_to_wrap() -> GenVecOf::<i32, u8>
1222    {
1223        let mut v = GenVecOf::<i32, u8>::new();
1224
1225        for i in 0..255
1226        {
1227            let a = v.insert(i);
1228            v.remove(a);
1229        }
1230
1231        //dbg!(v);
1232        v
1233    }
1234
1235    #[test]
1236    fn rollback_remove_empty()
1237    {
1238        let mut gen_vec = GenVec::new();
1239        // dbg!(&gen_vec);
1240
1241        let id = gen_vec.insert(42);
1242
1243        let old_gen = gen_vec.clone();
1244
1245        // dbg!(&gen_vec);
1246        let removed = gen_vec.remove_index(id.index).unwrap();
1247        // dbg!(&gen_vec);
1248        gen_vec.rollback_remove_index(id.index, removed).unwrap();
1249        // dbg!(&gen_vec);
1250
1251        assert_eq!(gen_vec, old_gen);
1252    }
1253
1254    #[test]
1255    fn rollback_remove_wrapping_empty()
1256    {
1257        let mut gen_vec = GenVecOf::<i32,Wrapping<Generation>>::new();
1258        let id = gen_vec.insert(42);
1259
1260        let old_gen = gen_vec.clone();
1261
1262        let removed = gen_vec.remove_index(id.index).unwrap();
1263        gen_vec.rollback_remove_index(id.index, removed).unwrap();
1264
1265        assert_eq!(gen_vec, old_gen);
1266    }
1267
1268    #[test]
1269    fn rollback_remove_wrapping()
1270    {
1271        let mut gen_vec = wrapping_about_to_wrap();
1272        let id = gen_vec.insert(42);
1273
1274        let old_gen = gen_vec.clone();
1275
1276        let removed = gen_vec.remove_index(id.index).unwrap();
1277        gen_vec.rollback_remove_index(id.index, removed).unwrap();
1278
1279        assert_eq!(gen_vec, old_gen);
1280    }
1281
1282    #[test]
1283    fn rollback_remove_wrapping_2()
1284    {
1285        let mut gen_vec = wrapping_about_to_wrap();
1286        gen_vec.insert(50);
1287
1288        let id = gen_vec.insert(42);
1289
1290        let old_gen = gen_vec.clone();
1291
1292        let removed = gen_vec.remove_index(id.index).unwrap();
1293        gen_vec.rollback_remove_index(id.index, removed).unwrap();
1294
1295        assert_eq!(gen_vec, old_gen);
1296    }
1297
1298    #[test]
1299    fn rollback_remove_non_wrapping()
1300    {
1301        let mut gen_vec = non_wrapping_about_to_wrap();
1302        // dbg!(&gen_vec);
1303        let id = gen_vec.insert(42);
1304        // dbg!(&gen_vec);
1305
1306        let old_gen = gen_vec.clone();
1307
1308        let removed = gen_vec.remove_index(id.index).unwrap();
1309        // dbg!(&gen_vec);
1310
1311        gen_vec.rollback_remove_index(id.index, removed).unwrap();
1312        // dbg!(&gen_vec);
1313
1314        assert_eq!(gen_vec, old_gen);
1315    }
1316
1317    #[test]
1318    fn rollback_remove_non_wrapping_2()
1319    {
1320        let mut gen_vec = non_wrapping_about_to_wrap();
1321        gen_vec.insert(50);
1322
1323        // dbg!(&gen_vec);
1324        let id = gen_vec.insert(42);
1325        // dbg!(&gen_vec);
1326
1327        let old_gen = gen_vec.clone();
1328
1329        let removed = gen_vec.remove_index(id.index).unwrap();
1330        // dbg!(&gen_vec);
1331
1332        gen_vec.rollback_remove_index(id.index, removed).unwrap();
1333        // dbg!(&gen_vec);
1334
1335        assert_eq!(gen_vec, old_gen);
1336    }
1337
1338
1339    // rollback_insert
1340
1341    #[test]
1342    fn rollback_insert_empty()
1343    {
1344        let mut gen_vec = GenVec::new();
1345        let old_gen = gen_vec.clone();
1346
1347        // dbg!(&gen_vec);
1348        let id = gen_vec.insert(42);
1349        // dbg!(&gen_vec);
1350        gen_vec.rollback_insert(id).unwrap();
1351
1352        assert_eq!(gen_vec, old_gen);
1353    }
1354
1355
1356    #[test]
1357    fn rollback_insert_wrapping_empty()
1358    {
1359        // We can't know if the gen vec is new or if the gen vec just wrapped
1360
1361        let mut gen_vec = GenVecOf::<i32,Wrapping<Generation>>::new();
1362        let old_gen = gen_vec.clone();
1363
1364         dbg!(&gen_vec);
1365        let id = gen_vec.insert(42);
1366         dbg!(&gen_vec);
1367        gen_vec.rollback_insert(id).unwrap();
1368         dbg!(&gen_vec);
1369
1370        assert_eq!(gen_vec, old_gen);
1371    }
1372
1373    #[test]
1374    fn rollback_insert_wrapping_3()
1375    {
1376        // We can't know if the gen vec is new or if the gen vec just wrapped
1377
1378        let mut gen_vec = GenVecOf::<i32,Wrapping<Generation>>::new();
1379        let _id = gen_vec.insert(45);
1380
1381        let old_gen = gen_vec.clone();
1382
1383         dbg!(&gen_vec);
1384        let id = gen_vec.insert(42);
1385         dbg!(&gen_vec);
1386        gen_vec.rollback_insert(id).unwrap();
1387         dbg!(&gen_vec);
1388
1389        assert_eq!(gen_vec, old_gen);
1390    }
1391
1392    #[test]
1393    fn rollback_insert_wrapping_dif()
1394    {
1395        let mut gen_vec = GenVecOf::<i32,Wrapping<Generation>>::new();
1396        let id = gen_vec.insert(45);
1397        gen_vec.remove(id);
1398        assert_ne!(gen_vec, GenVecOf::<i32,Wrapping<Generation>>::new());
1399    }
1400
1401    #[test]
1402    fn rollback_insert_wrapping_4()
1403    {
1404        let mut gen_vec = GenVecOf::<i32,Wrapping<Generation>>::new();
1405        let _ = gen_vec.insert(45);
1406
1407         //dbg!(&gen_vec);
1408        let id = gen_vec.insert(42);
1409         //dbg!(&gen_vec);
1410        gen_vec.rollback_insert(id).unwrap();
1411         //dbg!(&gen_vec);
1412
1413         let mut old_gen = GenVecOf::new();
1414         old_gen.insert(50);
1415
1416        assert_ne!(gen_vec, old_gen);
1417    }
1418
1419    #[test]
1420    fn rollback_insert_wrapping()
1421    {
1422        let mut gen_vec = wrapping_about_to_wrap();
1423        let old_gen = gen_vec.clone();
1424
1425        // dbg!(&gen_vec);
1426        let id = gen_vec.insert(42);
1427        // dbg!(&gen_vec);
1428        gen_vec.rollback_insert(id).unwrap();
1429        // dbg!(&gen_vec);
1430
1431        assert_eq!(gen_vec, old_gen);
1432    }
1433
1434
1435    #[test]
1436    fn rollback_insert_wrapping_2()
1437    {
1438        let mut gen_vec = wrapping_about_to_wrap();
1439        let old_gen = gen_vec.clone();
1440
1441        // dbg!(&gen_vec);
1442        let id = gen_vec.insert(42);
1443        // dbg!(&gen_vec);
1444        gen_vec.rollback_insert(id).unwrap();
1445
1446        assert_eq!(gen_vec, old_gen);
1447    }
1448
1449    #[test]
1450    fn rollback_insert_non_wrapping()
1451    {
1452        let mut gen_vec = non_wrapping_about_to_wrap();
1453        let old_gen = gen_vec.clone();
1454
1455        // dbg!(&gen_vec);
1456        let id = gen_vec.insert(42);
1457        // dbg!(&gen_vec);
1458        gen_vec.rollback_insert(id).unwrap();
1459
1460        assert_eq!(gen_vec, old_gen);
1461    }
1462
1463    #[test]
1464    fn rollback_insert_non_wrapping_2()
1465    {
1466        let mut gen_vec = non_wrapping_about_to_wrap();
1467        let old_gen = gen_vec.clone();
1468
1469        // dbg!(&gen_vec);
1470        let id = gen_vec.insert(42);
1471        // dbg!(&gen_vec);
1472        gen_vec.rollback_insert(id).unwrap();
1473
1474        assert_eq!(gen_vec, old_gen);
1475    }
1476
1477
1478    #[test]
1479    fn retain_test() {
1480        let mut g = GenVec::from_iter([1,2,3,4,5,6,7,8]);
1481        assert_eq!(g.len(), 8);
1482
1483        g.retain(|x| x % 2  == 0);
1484        assert_eq!(g.len(), 4);
1485
1486        assert!(g.into_values().eq([2,4,6,8]));
1487    }
1488
1489}
hexga_generational/gen_vec.rs

hexga_generational/
gen_vec.rs
